+static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
+ u64 owner, u64 owner_offset)
+{
+ u32 high_crc = ~(u32)0;
+ u32 low_crc = ~(u32)0;
+ __le64 lenum;
+ lenum = cpu_to_le64(root_objectid);
+ high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
+ lenum = cpu_to_le64(ref_generation);
+ low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
+ if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
+ lenum = cpu_to_le64(owner);
+ low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
+ lenum = cpu_to_le64(owner_offset);
+ low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
+ }
+ return ((u64)high_crc << 32) | (u64)low_crc;
+}
+
+static int match_extent_ref(struct extent_buffer *leaf,
+ struct btrfs_extent_ref *disk_ref,
+ struct btrfs_extent_ref *cpu_ref)
+{
+ int ret;
+ int len;
+
+ if (cpu_ref->objectid)
+ len = sizeof(*cpu_ref);
+ else
+ len = 2 * sizeof(u64);
+ ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
+ len);
+ return ret == 0;
+}
+
+static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path, u64 bytenr,
+ u64 root_objectid,
+ u64 ref_generation, u64 owner,
+ u64 owner_offset, int del)
+{
+ u64 hash;
+ struct btrfs_key key;
+ struct btrfs_key found_key;
+ struct btrfs_extent_ref ref;
+ struct extent_buffer *leaf;
+ struct btrfs_extent_ref *disk_ref;
+ int ret;
+ int ret2;
+
+ btrfs_set_stack_ref_root(&ref, root_objectid);
+ btrfs_set_stack_ref_generation(&ref, ref_generation);
+ btrfs_set_stack_ref_objectid(&ref, owner);
+ btrfs_set_stack_ref_offset(&ref, owner_offset);
+
+ hash = hash_extent_ref(root_objectid, ref_generation, owner,
+ owner_offset);
+ key.offset = hash;
+ key.objectid = bytenr;
+ key.type = BTRFS_EXTENT_REF_KEY;
+
+ while (1) {
+ ret = btrfs_search_slot(trans, root, &key, path,
+ del ? -1 : 0, del);
+ if (ret < 0)
+ goto out;
+ leaf = path->nodes[0];
+ if (ret != 0) {
+ u32 nritems = btrfs_header_nritems(leaf);
+ if (path->slots[0] >= nritems) {
+ ret2 = btrfs_next_leaf(root, path);
+ if (ret2)
+ goto out;
+ leaf = path->nodes[0];
+ }
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+ if (found_key.objectid != bytenr ||
+ found_key.type != BTRFS_EXTENT_REF_KEY)
+ goto out;
+ key.offset = found_key.offset;
+ if (del) {
+ btrfs_release_path(root, path);
+ continue;
+ }
+ }
+ disk_ref = btrfs_item_ptr(path->nodes[0],
+ path->slots[0],
+ struct btrfs_extent_ref);
+ if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
+ ret = 0;
+ goto out;
+ }
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+ key.offset = found_key.offset + 1;
+ btrfs_release_path(root, path);
+ }
+out:
+ return ret;
+}
+
+/*
+ * Back reference rules. Back refs have three main goals:
+ *
+ * 1) differentiate between all holders of references to an extent so that
+ * when a reference is dropped we can make sure it was a valid reference
+ * before freeing the extent.
+ *
+ * 2) Provide enough information to quickly find the holders of an extent
+ * if we notice a given block is corrupted or bad.
+ *
+ * 3) Make it easy to migrate blocks for FS shrinking or storage pool
+ * maintenance. This is actually the same as #2, but with a slightly
+ * different use case.
+ *
+ * File extents can be referenced by:
+ *
+ * - multiple snapshots, subvolumes, or different generations in one subvol
+ * - different files inside a single subvolume (in theory, not implemented yet)
+ * - different offsets inside a file (bookend extents in file.c)
+ *
+ * The extent ref structure has fields for:
+ *
+ * - Objectid of the subvolume root
+ * - Generation number of the tree holding the reference
+ * - objectid of the file holding the reference
+ * - offset in the file corresponding to the key holding the reference
+ *
+ * When a file extent is allocated the fields are filled in:
+ * (root_key.objectid, trans->transid, inode objectid, offset in file)
+ *
+ * When a leaf is cow'd new references are added for every file extent found
+ * in the leaf. It looks the same as the create case, but trans->transid
+ * will be different when the block is cow'd.
+ *
+ * (root_key.objectid, trans->transid, inode objectid, offset in file)
+ *
+ * When a file extent is removed either during snapshot deletion or file
+ * truncation, the corresponding back reference is found
+ * by searching for:
+ *
+ * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
+ * inode objectid, offset in file)
+ *
+ * Btree extents can be referenced by:
+ *
+ * - Different subvolumes
+ * - Different generations of the same subvolume
+ *
+ * Storing sufficient information for a full reverse mapping of a btree
+ * block would require storing the lowest key of the block in the backref,
+ * and it would require updating that lowest key either before write out or
+ * every time it changed. Instead, the objectid of the lowest key is stored
+ * along with the level of the tree block. This provides a hint
+ * about where in the btree the block can be found. Searches through the
+ * btree only need to look for a pointer to that block, so they stop one
+ * level higher than the level recorded in the backref.
+ *
+ * Some btrees do not do reference counting on their extents. These
+ * include the extent tree and the tree of tree roots. Backrefs for these
+ * trees always have a generation of zero.
+ *
+ * When a tree block is created, back references are inserted:
+ *
+ * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
+ *
+ * When a tree block is cow'd in a reference counted root,
+ * new back references are added for all the blocks it points to.
+ * These are of the form (trans->transid will have increased since creation):
+ *
+ * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
+ *
+ * Because the lowest_key_objectid and the level are just hints
+ * they are not used when backrefs are deleted. When a backref is deleted:
+ *
+ * if backref was for a tree root:
+ * root_objectid = root->root_key.objectid
+ * else
+ * root_objectid = btrfs_header_owner(parent)
+ *
+ * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
+ *
+ * Back Reference Key hashing:
+ *
+ * Back references have four fields, each 64 bits long. Unfortunately,
+ * This is hashed into a single 64 bit number and placed into the key offset.
+ * The key objectid corresponds to the first byte in the extent, and the
+ * key type is set to BTRFS_EXTENT_REF_KEY
+ */
+int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path, u64 bytenr,
+ u64 root_objectid, u64 ref_generation,
+ u64 owner, u64 owner_offset)
+{
+ u64 hash;
+ struct btrfs_key key;
+ struct btrfs_extent_ref ref;
+ struct btrfs_extent_ref *disk_ref;
+ int ret;
+
+ btrfs_set_stack_ref_root(&ref, root_objectid);
+ btrfs_set_stack_ref_generation(&ref, ref_generation);
+ btrfs_set_stack_ref_objectid(&ref, owner);
+ btrfs_set_stack_ref_offset(&ref, owner_offset);
+
+ hash = hash_extent_ref(root_objectid, ref_generation, owner,
+ owner_offset);
+ key.offset = hash;
+ key.objectid = bytenr;
+ key.type = BTRFS_EXTENT_REF_KEY;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
+ while (ret == -EEXIST) {
+ disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_extent_ref);
+ if (match_extent_ref(path->nodes[0], disk_ref, &ref))
+ goto out;
+ key.offset++;
+ btrfs_release_path(root, path);
+ ret = btrfs_insert_empty_item(trans, root, path, &key,
+ sizeof(ref));
+ }
+ if (ret)
+ goto out;
+ disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_extent_ref);
+ write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
+ sizeof(ref));
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+out:
+ btrfs_release_path(root, path);
+ return ret;
+}
+