- cache = search_cache_extent(reada, 0);
- if (cache) {
- bits[0].start = cache->start;
- bits[0].size = cache->size;
- *reada_bits = 1;
- return 1;
- }
- *reada_bits = 0;
- if (node_start > 32768)
- node_start -= 32768;
-
- cache = search_cache_extent(nodes, node_start);
- if (!cache)
- cache = search_cache_extent(nodes, 0);
-
- if (!cache) {
- cache = search_cache_extent(pending, 0);
- if (!cache)
- return 0;
- ret = 0;
- do {
- bits[ret].start = cache->start;
- bits[ret].size = cache->size;
- cache = next_cache_extent(cache);
- ret++;
- } while (cache && ret < bits_nr);
- return ret;
- }
-
- ret = 0;
- do {
- bits[ret].start = cache->start;
- bits[ret].size = cache->size;
- cache = next_cache_extent(cache);
- ret++;
- } while (cache && ret < bits_nr);
-
- if (bits_nr - ret > 8) {
- u64 lookup = bits[0].start + bits[0].size;
- struct cache_extent *next;
- next = search_cache_extent(pending, lookup);
- while(next) {
- if (next->start - lookup > 32768)
- break;
- bits[ret].start = next->start;
- bits[ret].size = next->size;
- lookup = next->start + next->size;
- ret++;
- if (ret == bits_nr)
- break;
- next = next_cache_extent(next);
- if (!next)
- break;
- }
- }
- return ret;
-}
-
-static void free_chunk_record(struct cache_extent *cache)
-{
- struct chunk_record *rec;
-
- rec = container_of(cache, struct chunk_record, cache);
- list_del_init(&rec->list);
- list_del_init(&rec->dextents);
- free(rec);
-}
-
-void free_chunk_cache_tree(struct cache_tree *chunk_cache)
-{
- cache_tree_free_extents(chunk_cache, free_chunk_record);
-}
-
-static void free_device_record(struct rb_node *node)
-{
- struct device_record *rec;
-
- rec = container_of(node, struct device_record, node);
- free(rec);
-}
-
-FREE_RB_BASED_TREE(device_cache, free_device_record);
-
-int insert_block_group_record(struct block_group_tree *tree,
- struct block_group_record *bg_rec)
-{
- int ret;
-
- ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
- if (ret)
- return ret;
-
- list_add_tail(&bg_rec->list, &tree->block_groups);
- return 0;
-}
-
-static void free_block_group_record(struct cache_extent *cache)
-{
- struct block_group_record *rec;
-
- rec = container_of(cache, struct block_group_record, cache);
- list_del_init(&rec->list);
- free(rec);
-}
-
-void free_block_group_tree(struct block_group_tree *tree)
-{
- cache_tree_free_extents(&tree->tree, free_block_group_record);
-}
-
-int insert_device_extent_record(struct device_extent_tree *tree,
- struct device_extent_record *de_rec)
-{
- int ret;
-
- /*
- * Device extent is a bit different from the other extents, because
- * the extents which belong to the different devices may have the
- * same start and size, so we need use the special extent cache
- * search/insert functions.
- */
- ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
- if (ret)
- return ret;
-
- list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
- list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
- return 0;
-}
-
-static void free_device_extent_record(struct cache_extent *cache)
-{
- struct device_extent_record *rec;
-
- rec = container_of(cache, struct device_extent_record, cache);
- if (!list_empty(&rec->chunk_list))
- list_del_init(&rec->chunk_list);
- if (!list_empty(&rec->device_list))
- list_del_init(&rec->device_list);
- free(rec);
-}
-
-void free_device_extent_tree(struct device_extent_tree *tree)
-{
- cache_tree_free_extents(&tree->tree, free_device_extent_record);
-}
-
-#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
-static int process_extent_ref_v0(struct cache_tree *extent_cache,
- struct extent_buffer *leaf, int slot)
-{
- struct btrfs_extent_ref_v0 *ref0;
- struct btrfs_key key;
- int ret;
-
- btrfs_item_key_to_cpu(leaf, &key, slot);
- ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
- if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
- ret = add_tree_backref(extent_cache, key.objectid, key.offset,
- 0, 0);
- } else {
- ret = add_data_backref(extent_cache, key.objectid, key.offset,
- 0, 0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
- }
- return ret;
-}
-#endif
-
-struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
- struct btrfs_key *key,
- int slot)
-{
- struct btrfs_chunk *ptr;
- struct chunk_record *rec;
- int num_stripes, i;
-
- ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
- num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
-
- rec = calloc(1, btrfs_chunk_record_size(num_stripes));
- if (!rec) {
- fprintf(stderr, "memory allocation failed\n");
- exit(-1);
- }
-
- INIT_LIST_HEAD(&rec->list);
- INIT_LIST_HEAD(&rec->dextents);
- rec->bg_rec = NULL;
-
- rec->cache.start = key->offset;
- rec->cache.size = btrfs_chunk_length(leaf, ptr);
-
- rec->generation = btrfs_header_generation(leaf);
-
- rec->objectid = key->objectid;
- rec->type = key->type;
- rec->offset = key->offset;
-
- rec->length = rec->cache.size;
- rec->owner = btrfs_chunk_owner(leaf, ptr);
- rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
- rec->type_flags = btrfs_chunk_type(leaf, ptr);
- rec->io_width = btrfs_chunk_io_width(leaf, ptr);
- rec->io_align = btrfs_chunk_io_align(leaf, ptr);
- rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
- rec->num_stripes = num_stripes;
- rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
-
- for (i = 0; i < rec->num_stripes; ++i) {
- rec->stripes[i].devid =
- btrfs_stripe_devid_nr(leaf, ptr, i);
- rec->stripes[i].offset =
- btrfs_stripe_offset_nr(leaf, ptr, i);
- read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
- (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
- BTRFS_UUID_SIZE);
- }
-
- return rec;
-}
-
-static int process_chunk_item(struct cache_tree *chunk_cache,
- struct btrfs_key *key, struct extent_buffer *eb,
- int slot)
-{
- struct chunk_record *rec;
- struct btrfs_chunk *chunk;
- int ret = 0;
-
- chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
- /*
- * Do extra check for this chunk item,
- *
- * It's still possible one can craft a leaf with CHUNK_ITEM, with
- * wrong onwer(3) out of chunk tree, to pass both chunk tree check
- * and owner<->key_type check.
- */
- ret = btrfs_check_chunk_valid(global_info, eb, chunk, slot,
- key->offset);
- if (ret < 0) {
- error("chunk(%llu, %llu) is not valid, ignore it",
- key->offset, btrfs_chunk_length(eb, chunk));
- return 0;
- }
- rec = btrfs_new_chunk_record(eb, key, slot);
- ret = insert_cache_extent(chunk_cache, &rec->cache);
- if (ret) {
- fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
- rec->offset, rec->length);
- free(rec);
- }
-
- return ret;
-}
-
-static int process_device_item(struct rb_root *dev_cache,
- struct btrfs_key *key, struct extent_buffer *eb, int slot)
-{
- struct btrfs_dev_item *ptr;
- struct device_record *rec;
- int ret = 0;
-
- ptr = btrfs_item_ptr(eb,
- slot, struct btrfs_dev_item);
-
- rec = malloc(sizeof(*rec));
- if (!rec) {
- fprintf(stderr, "memory allocation failed\n");
- return -ENOMEM;
- }
-
- rec->devid = key->offset;
- rec->generation = btrfs_header_generation(eb);
-
- rec->objectid = key->objectid;
- rec->type = key->type;
- rec->offset = key->offset;
-
- rec->devid = btrfs_device_id(eb, ptr);
- rec->total_byte = btrfs_device_total_bytes(eb, ptr);
- rec->byte_used = btrfs_device_bytes_used(eb, ptr);
-
- ret = rb_insert(dev_cache, &rec->node, device_record_compare);
- if (ret) {
- fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
- free(rec);
- }
-
- return ret;
-}
-
-struct block_group_record *
-btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
- int slot)
-{
- struct btrfs_block_group_item *ptr;
- struct block_group_record *rec;
-
- rec = calloc(1, sizeof(*rec));
- if (!rec) {
- fprintf(stderr, "memory allocation failed\n");
- exit(-1);
- }
-
- rec->cache.start = key->objectid;
- rec->cache.size = key->offset;
-
- rec->generation = btrfs_header_generation(leaf);
-
- rec->objectid = key->objectid;
- rec->type = key->type;
- rec->offset = key->offset;
-
- ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
- rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
-
- INIT_LIST_HEAD(&rec->list);
-
- return rec;
-}
-
-static int process_block_group_item(struct block_group_tree *block_group_cache,
- struct btrfs_key *key,
- struct extent_buffer *eb, int slot)
-{
- struct block_group_record *rec;
- int ret = 0;
-
- rec = btrfs_new_block_group_record(eb, key, slot);
- ret = insert_block_group_record(block_group_cache, rec);
- if (ret) {
- fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
- rec->objectid, rec->offset);
- free(rec);
- }
-
- return ret;
-}
-
-struct device_extent_record *
-btrfs_new_device_extent_record(struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
-{
- struct device_extent_record *rec;
- struct btrfs_dev_extent *ptr;
-
- rec = calloc(1, sizeof(*rec));
- if (!rec) {
- fprintf(stderr, "memory allocation failed\n");
- exit(-1);
- }
-
- rec->cache.objectid = key->objectid;
- rec->cache.start = key->offset;
-
- rec->generation = btrfs_header_generation(leaf);
-
- rec->objectid = key->objectid;
- rec->type = key->type;
- rec->offset = key->offset;
-
- ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
- rec->chunk_objecteid =
- btrfs_dev_extent_chunk_objectid(leaf, ptr);
- rec->chunk_offset =
- btrfs_dev_extent_chunk_offset(leaf, ptr);
- rec->length = btrfs_dev_extent_length(leaf, ptr);
- rec->cache.size = rec->length;
-
- INIT_LIST_HEAD(&rec->chunk_list);
- INIT_LIST_HEAD(&rec->device_list);
-
- return rec;
-}
-
-static int
-process_device_extent_item(struct device_extent_tree *dev_extent_cache,
- struct btrfs_key *key, struct extent_buffer *eb,
- int slot)
-{
- struct device_extent_record *rec;
- int ret;
-
- rec = btrfs_new_device_extent_record(eb, key, slot);
- ret = insert_device_extent_record(dev_extent_cache, rec);
- if (ret) {
- fprintf(stderr,
- "Device extent[%llu, %llu, %llu] existed.\n",
- rec->objectid, rec->offset, rec->length);
- free(rec);
- }
-
- return ret;
-}
-
-static int process_extent_item(struct btrfs_root *root,
- struct cache_tree *extent_cache,
- struct extent_buffer *eb, int slot)
-{
- struct btrfs_extent_item *ei;
- struct btrfs_extent_inline_ref *iref;
- struct btrfs_extent_data_ref *dref;
- struct btrfs_shared_data_ref *sref;
- struct btrfs_key key;
- struct extent_record tmpl;
- unsigned long end;
- unsigned long ptr;
- int ret;
- int type;
- u32 item_size = btrfs_item_size_nr(eb, slot);
- u64 refs = 0;
- u64 offset;
- u64 num_bytes;
- int metadata = 0;
-
- btrfs_item_key_to_cpu(eb, &key, slot);
-
- if (key.type == BTRFS_METADATA_ITEM_KEY) {
- metadata = 1;
- num_bytes = root->fs_info->nodesize;
- } else {
- num_bytes = key.offset;
- }
-
- if (!IS_ALIGNED(key.objectid, root->fs_info->sectorsize)) {
- error("ignoring invalid extent, bytenr %llu is not aligned to %u",
- key.objectid, root->fs_info->sectorsize);
- return -EIO;
- }
- if (item_size < sizeof(*ei)) {
-#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
- struct btrfs_extent_item_v0 *ei0;
- if (item_size != sizeof(*ei0)) {
- error(
- "invalid extent item format: ITEM[%llu %u %llu] leaf: %llu slot: %d",
- key.objectid, key.type, key.offset,
- btrfs_header_bytenr(eb), slot);
- BUG();
- }
- ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
- refs = btrfs_extent_refs_v0(eb, ei0);
-#else
- BUG();
-#endif
- memset(&tmpl, 0, sizeof(tmpl));
- tmpl.start = key.objectid;
- tmpl.nr = num_bytes;
- tmpl.extent_item_refs = refs;
- tmpl.metadata = metadata;
- tmpl.found_rec = 1;
- tmpl.max_size = num_bytes;
-
- return add_extent_rec(extent_cache, &tmpl);
- }
-
- ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
- refs = btrfs_extent_refs(eb, ei);
- if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
- metadata = 1;
- else
- metadata = 0;
- if (metadata && num_bytes != root->fs_info->nodesize) {
- error("ignore invalid metadata extent, length %llu does not equal to %u",
- num_bytes, root->fs_info->nodesize);
- return -EIO;
- }
- if (!metadata && !IS_ALIGNED(num_bytes, root->fs_info->sectorsize)) {
- error("ignore invalid data extent, length %llu is not aligned to %u",
- num_bytes, root->fs_info->sectorsize);
- return -EIO;
- }
-
- memset(&tmpl, 0, sizeof(tmpl));
- tmpl.start = key.objectid;
- tmpl.nr = num_bytes;
- tmpl.extent_item_refs = refs;
- tmpl.metadata = metadata;
- tmpl.found_rec = 1;
- tmpl.max_size = num_bytes;
- add_extent_rec(extent_cache, &tmpl);
-
- ptr = (unsigned long)(ei + 1);
- if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
- key.type == BTRFS_EXTENT_ITEM_KEY)
- ptr += sizeof(struct btrfs_tree_block_info);
-
- end = (unsigned long)ei + item_size;
- while (ptr < end) {
- iref = (struct btrfs_extent_inline_ref *)ptr;
- type = btrfs_extent_inline_ref_type(eb, iref);
- offset = btrfs_extent_inline_ref_offset(eb, iref);
- switch (type) {
- case BTRFS_TREE_BLOCK_REF_KEY:
- ret = add_tree_backref(extent_cache, key.objectid,
- 0, offset, 0);
- if (ret < 0)
- error(
- "add_tree_backref failed (extent items tree block): %s",
- strerror(-ret));
- break;
- case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = add_tree_backref(extent_cache, key.objectid,
- offset, 0, 0);
- if (ret < 0)
- error(
- "add_tree_backref failed (extent items shared block): %s",
- strerror(-ret));
- break;
- case BTRFS_EXTENT_DATA_REF_KEY:
- dref = (struct btrfs_extent_data_ref *)(&iref->offset);
- add_data_backref(extent_cache, key.objectid, 0,
- btrfs_extent_data_ref_root(eb, dref),
- btrfs_extent_data_ref_objectid(eb,
- dref),
- btrfs_extent_data_ref_offset(eb, dref),
- btrfs_extent_data_ref_count(eb, dref),
- 0, num_bytes);
- break;
- case BTRFS_SHARED_DATA_REF_KEY:
- sref = (struct btrfs_shared_data_ref *)(iref + 1);
- add_data_backref(extent_cache, key.objectid, offset,
- 0, 0, 0,
- btrfs_shared_data_ref_count(eb, sref),
- 0, num_bytes);
- break;
- default:
- fprintf(stderr, "corrupt extent record: key %Lu %u %Lu\n",
- key.objectid, key.type, num_bytes);
- goto out;
- }
- ptr += btrfs_extent_inline_ref_size(type);
- }
- WARN_ON(ptr > end);
-out:
- return 0;
-}
-
-static int check_cache_range(struct btrfs_root *root,
- struct btrfs_block_group_cache *cache,
- u64 offset, u64 bytes)
-{
- struct btrfs_free_space *entry;
- u64 *logical;
- u64 bytenr;
- int stripe_len;
- int i, nr, ret;
-
- for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
- bytenr = btrfs_sb_offset(i);
- ret = btrfs_rmap_block(root->fs_info,
- cache->key.objectid, bytenr, 0,
- &logical, &nr, &stripe_len);
- if (ret)
- return ret;
-
- while (nr--) {
- if (logical[nr] + stripe_len <= offset)
- continue;
- if (offset + bytes <= logical[nr])
- continue;
- if (logical[nr] == offset) {
- if (stripe_len >= bytes) {
- free(logical);
- return 0;
- }
- bytes -= stripe_len;
- offset += stripe_len;
- } else if (logical[nr] < offset) {
- if (logical[nr] + stripe_len >=
- offset + bytes) {
- free(logical);
- return 0;
- }
- bytes = (offset + bytes) -
- (logical[nr] + stripe_len);
- offset = logical[nr] + stripe_len;
- } else {
- /*
- * Could be tricky, the super may land in the
- * middle of the area we're checking. First
- * check the easiest case, it's at the end.
- */
- if (logical[nr] + stripe_len >=
- bytes + offset) {
- bytes = logical[nr] - offset;
- continue;
- }
-
- /* Check the left side */
- ret = check_cache_range(root, cache,
- offset,
- logical[nr] - offset);
- if (ret) {
- free(logical);
- return ret;
- }
-
- /* Now we continue with the right side */
- bytes = (offset + bytes) -
- (logical[nr] + stripe_len);
- offset = logical[nr] + stripe_len;
- }
- }
-
- free(logical);
- }
-
- entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
- if (!entry) {
- fprintf(stderr, "There is no free space entry for %Lu-%Lu\n",
- offset, offset+bytes);
- return -EINVAL;
- }
-
- if (entry->offset != offset) {
- fprintf(stderr, "Wanted offset %Lu, found %Lu\n", offset,
- entry->offset);
- return -EINVAL;
- }
-
- if (entry->bytes != bytes) {
- fprintf(stderr, "Wanted bytes %Lu, found %Lu for off %Lu\n",
- bytes, entry->bytes, offset);
- return -EINVAL;
- }
-
- unlink_free_space(cache->free_space_ctl, entry);
- free(entry);
- return 0;
-}
-
-static int verify_space_cache(struct btrfs_root *root,
- struct btrfs_block_group_cache *cache)
-{
- struct btrfs_path path;
- struct extent_buffer *leaf;
- struct btrfs_key key;
- u64 last;
- int ret = 0;
-
- root = root->fs_info->extent_root;
-
- last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
-
- btrfs_init_path(&path);
- key.objectid = last;
- key.offset = 0;
- key.type = BTRFS_EXTENT_ITEM_KEY;
- ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
- if (ret < 0)
- goto out;
- ret = 0;
- while (1) {
- if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
- ret = btrfs_next_leaf(root, &path);
- if (ret < 0)
- goto out;
- if (ret > 0) {
- ret = 0;
- break;
- }
- }
- leaf = path.nodes[0];
- btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
- if (key.objectid >= cache->key.offset + cache->key.objectid)
- break;
- if (key.type != BTRFS_EXTENT_ITEM_KEY &&
- key.type != BTRFS_METADATA_ITEM_KEY) {
- path.slots[0]++;
- continue;
- }
-
- if (last == key.objectid) {
- if (key.type == BTRFS_EXTENT_ITEM_KEY)
- last = key.objectid + key.offset;
- else
- last = key.objectid + root->fs_info->nodesize;
- path.slots[0]++;
- continue;
- }
-
- ret = check_cache_range(root, cache, last,
- key.objectid - last);
- if (ret)
- break;
- if (key.type == BTRFS_EXTENT_ITEM_KEY)
- last = key.objectid + key.offset;
- else
- last = key.objectid + root->fs_info->nodesize;
- path.slots[0]++;
- }
-
- if (last < cache->key.objectid + cache->key.offset)
- ret = check_cache_range(root, cache, last,
- cache->key.objectid +
- cache->key.offset - last);
-
-out:
- btrfs_release_path(&path);
-
- if (!ret &&
- !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
- fprintf(stderr, "There are still entries left in the space "
- "cache\n");
- ret = -EINVAL;
- }
-
- return ret;
-}
-
-static int check_space_cache(struct btrfs_root *root)
-{
- struct btrfs_block_group_cache *cache;
- u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
- int ret;
- int error = 0;
-
- if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
- btrfs_super_generation(root->fs_info->super_copy) !=
- btrfs_super_cache_generation(root->fs_info->super_copy)) {
- printf("cache and super generation don't match, space cache "
- "will be invalidated\n");
- return 0;
- }
-
- if (ctx.progress_enabled) {
- ctx.tp = TASK_FREE_SPACE;
- task_start(ctx.info);
- }
-
- while (1) {
- cache = btrfs_lookup_first_block_group(root->fs_info, start);
- if (!cache)
- break;
-
- start = cache->key.objectid + cache->key.offset;
- if (!cache->free_space_ctl) {
- if (btrfs_init_free_space_ctl(cache,
- root->fs_info->sectorsize)) {
- ret = -ENOMEM;
- break;
- }
- } else {
- btrfs_remove_free_space_cache(cache);
- }
-
- if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE)) {
- ret = exclude_super_stripes(root, cache);
- if (ret) {
- fprintf(stderr, "could not exclude super stripes: %s\n",
- strerror(-ret));
- error++;
- continue;
- }
- ret = load_free_space_tree(root->fs_info, cache);
- free_excluded_extents(root, cache);
- if (ret < 0) {
- fprintf(stderr, "could not load free space tree: %s\n",
- strerror(-ret));
- error++;
- continue;
- }
- error += ret;
- } else {
- ret = load_free_space_cache(root->fs_info, cache);
- if (!ret)
- continue;
- }
-
- ret = verify_space_cache(root, cache);
- if (ret) {
- fprintf(stderr, "cache appears valid but isn't %Lu\n",
- cache->key.objectid);
- error++;
- }
- }
-
- task_stop(ctx.info);
-
- return error ? -EINVAL : 0;
-}
-
-static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
- u64 num_bytes, unsigned long leaf_offset,
- struct extent_buffer *eb) {
-
- struct btrfs_fs_info *fs_info = root->fs_info;
- u64 offset = 0;
- u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
- char *data;
- unsigned long csum_offset;
- u32 csum;
- u32 csum_expected;
- u64 read_len;
- u64 data_checked = 0;
- u64 tmp;
- int ret = 0;
- int mirror;
- int num_copies;
-
- if (num_bytes % fs_info->sectorsize)
- return -EINVAL;
-
- data = malloc(num_bytes);
- if (!data)
- return -ENOMEM;
-
- while (offset < num_bytes) {
- mirror = 0;
-again:
- read_len = num_bytes - offset;
- /* read as much space once a time */
- ret = read_extent_data(fs_info, data + offset,
- bytenr + offset, &read_len, mirror);
- if (ret)
- goto out;
- data_checked = 0;
- /* verify every 4k data's checksum */
- while (data_checked < read_len) {
- csum = ~(u32)0;
- tmp = offset + data_checked;
-
- csum = btrfs_csum_data((char *)data + tmp,
- csum, fs_info->sectorsize);
- btrfs_csum_final(csum, (u8 *)&csum);
-
- csum_offset = leaf_offset +
- tmp / fs_info->sectorsize * csum_size;
- read_extent_buffer(eb, (char *)&csum_expected,
- csum_offset, csum_size);
- /* try another mirror */
- if (csum != csum_expected) {
- fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
- mirror, bytenr + tmp,
- csum, csum_expected);
- num_copies = btrfs_num_copies(root->fs_info,
- bytenr, num_bytes);
- if (mirror < num_copies - 1) {
- mirror += 1;
- goto again;
- }
- }
- data_checked += fs_info->sectorsize;
- }
- offset += read_len;
- }
-out:
- free(data);
- return ret;
-}
-
-static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
- u64 num_bytes)
-{
- struct btrfs_path path;
- struct extent_buffer *leaf;
- struct btrfs_key key;
- int ret;
-
- btrfs_init_path(&path);
- key.objectid = bytenr;
- key.type = BTRFS_EXTENT_ITEM_KEY;
- key.offset = (u64)-1;
-
-again:
- ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
- 0, 0);
- if (ret < 0) {
- fprintf(stderr, "Error looking up extent record %d\n", ret);
- btrfs_release_path(&path);
- return ret;
- } else if (ret) {
- if (path.slots[0] > 0) {
- path.slots[0]--;
- } else {
- ret = btrfs_prev_leaf(root, &path);
- if (ret < 0) {
- goto out;
- } else if (ret > 0) {
- ret = 0;
- goto out;
- }
- }
- }
-
- btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
-
- /*
- * Block group items come before extent items if they have the same
- * bytenr, so walk back one more just in case. Dear future traveller,
- * first congrats on mastering time travel. Now if it's not too much
- * trouble could you go back to 2006 and tell Chris to make the
- * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
- * EXTENT_ITEM_KEY please?
- */
- while (key.type > BTRFS_EXTENT_ITEM_KEY) {
- if (path.slots[0] > 0) {
- path.slots[0]--;
- } else {
- ret = btrfs_prev_leaf(root, &path);
- if (ret < 0) {
- goto out;
- } else if (ret > 0) {
- ret = 0;
- goto out;
- }
- }
- btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
- }
-
- while (num_bytes) {
- if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
- ret = btrfs_next_leaf(root, &path);
- if (ret < 0) {
- fprintf(stderr, "Error going to next leaf "
- "%d\n", ret);
- btrfs_release_path(&path);
- return ret;
- } else if (ret) {
- break;
- }
- }
- leaf = path.nodes[0];
- btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
- if (key.type != BTRFS_EXTENT_ITEM_KEY) {
- path.slots[0]++;
- continue;
- }
- if (key.objectid + key.offset < bytenr) {
- path.slots[0]++;
- continue;
- }
- if (key.objectid > bytenr + num_bytes)
- break;
-
- if (key.objectid == bytenr) {
- if (key.offset >= num_bytes) {
- num_bytes = 0;
- break;
- }
- num_bytes -= key.offset;
- bytenr += key.offset;
- } else if (key.objectid < bytenr) {
- if (key.objectid + key.offset >= bytenr + num_bytes) {
- num_bytes = 0;
- break;
- }
- num_bytes = (bytenr + num_bytes) -
- (key.objectid + key.offset);
- bytenr = key.objectid + key.offset;
- } else {
- if (key.objectid + key.offset < bytenr + num_bytes) {
- u64 new_start = key.objectid + key.offset;
- u64 new_bytes = bytenr + num_bytes - new_start;
-
- /*
- * Weird case, the extent is in the middle of
- * our range, we'll have to search one side
- * and then the other. Not sure if this happens
- * in real life, but no harm in coding it up
- * anyway just in case.
- */
- btrfs_release_path(&path);
- ret = check_extent_exists(root, new_start,
- new_bytes);
- if (ret) {
- fprintf(stderr, "Right section didn't "
- "have a record\n");
- break;
- }
- num_bytes = key.objectid - bytenr;
- goto again;
- }
- num_bytes = key.objectid - bytenr;
- }
- path.slots[0]++;
- }
- ret = 0;
-
-out:
- if (num_bytes && !ret) {
- fprintf(stderr, "There are no extents for csum range "
- "%Lu-%Lu\n", bytenr, bytenr+num_bytes);
- ret = 1;
- }
-
- btrfs_release_path(&path);
- return ret;
-}
-
-static int check_csums(struct btrfs_root *root)
-{
- struct btrfs_path path;
- struct extent_buffer *leaf;
- struct btrfs_key key;
- u64 offset = 0, num_bytes = 0;
- u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
- int errors = 0;
- int ret;
- u64 data_len;
- unsigned long leaf_offset;
-
- root = root->fs_info->csum_root;
- if (!extent_buffer_uptodate(root->node)) {
- fprintf(stderr, "No valid csum tree found\n");
- return -ENOENT;
- }
-
- btrfs_init_path(&path);
- key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
- key.type = BTRFS_EXTENT_CSUM_KEY;
- key.offset = 0;
- ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
- if (ret < 0) {
- fprintf(stderr, "Error searching csum tree %d\n", ret);
- btrfs_release_path(&path);
- return ret;
- }
-
- if (ret > 0 && path.slots[0])
- path.slots[0]--;
- ret = 0;
-
- while (1) {
- if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
- ret = btrfs_next_leaf(root, &path);
- if (ret < 0) {
- fprintf(stderr, "Error going to next leaf "
- "%d\n", ret);
- break;
- }
- if (ret)
- break;
- }
- leaf = path.nodes[0];
-
- btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
- if (key.type != BTRFS_EXTENT_CSUM_KEY) {
- path.slots[0]++;
- continue;
- }
-
- data_len = (btrfs_item_size_nr(leaf, path.slots[0]) /
- csum_size) * root->fs_info->sectorsize;
- if (!check_data_csum)
- goto skip_csum_check;
- leaf_offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
- ret = check_extent_csums(root, key.offset, data_len,
- leaf_offset, leaf);
- if (ret)
- break;
-skip_csum_check:
- if (!num_bytes) {
- offset = key.offset;
- } else if (key.offset != offset + num_bytes) {
- ret = check_extent_exists(root, offset, num_bytes);
- if (ret) {
- fprintf(stderr, "Csum exists for %Lu-%Lu but "
- "there is no extent record\n",
- offset, offset+num_bytes);
- errors++;
- }
- offset = key.offset;
- num_bytes = 0;
- }
- num_bytes += data_len;
- path.slots[0]++;
- }
-
- btrfs_release_path(&path);
- return errors;
-}
-
-static int is_dropped_key(struct btrfs_key *key,
- struct btrfs_key *drop_key) {
- if (key->objectid < drop_key->objectid)
- return 1;
- else if (key->objectid == drop_key->objectid) {
- if (key->type < drop_key->type)
- return 1;
- else if (key->type == drop_key->type) {
- if (key->offset < drop_key->offset)
- return 1;
- }
- }
- return 0;
-}
-
-/*
- * Here are the rules for FULL_BACKREF.
- *
- * 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
- * 2) If btrfs_header_owner(buf) no longer points to buf then we have
- * FULL_BACKREF set.
- * 3) We cowed the block walking down a reloc tree. This is impossible to tell
- * if it happened after the relocation occurred since we'll have dropped the
- * reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
- * have no real way to know for sure.
- *
- * We process the blocks one root at a time, and we start from the lowest root
- * objectid and go to the highest. So we can just lookup the owner backref for
- * the record and if we don't find it then we know it doesn't exist and we have
- * a FULL BACKREF.
- *
- * FIXME: if we ever start reclaiming root objectid's then we need to fix this
- * assumption and simply indicate that we _think_ that the FULL BACKREF needs to
- * be set or not and then we can check later once we've gathered all the refs.
- */
-static int calc_extent_flag(struct cache_tree *extent_cache,
- struct extent_buffer *buf,
- struct root_item_record *ri,
- u64 *flags)
-{
- struct extent_record *rec;
- struct cache_extent *cache;
- struct tree_backref *tback;
- u64 owner = 0;
-
- cache = lookup_cache_extent(extent_cache, buf->start, 1);
- /* we have added this extent before */
- if (!cache)
- return -ENOENT;
-
- rec = container_of(cache, struct extent_record, cache);
-
- /*
- * Except file/reloc tree, we can not have
- * FULL BACKREF MODE
- */
- if (ri->objectid < BTRFS_FIRST_FREE_OBJECTID)
- goto normal;
- /*
- * root node
- */
- if (buf->start == ri->bytenr)
- goto normal;
-
- if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
- goto full_backref;
-
- owner = btrfs_header_owner(buf);
- if (owner == ri->objectid)
- goto normal;
-
- tback = find_tree_backref(rec, 0, owner);
- if (!tback)
- goto full_backref;
-normal:
- *flags = 0;
- if (rec->flag_block_full_backref != FLAG_UNSET &&
- rec->flag_block_full_backref != 0)
- rec->bad_full_backref = 1;
- return 0;
-full_backref:
- *flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- if (rec->flag_block_full_backref != FLAG_UNSET &&
- rec->flag_block_full_backref != 1)
- rec->bad_full_backref = 1;
- return 0;
-}
-
-static void report_mismatch_key_root(u8 key_type, u64 rootid)
-{
- fprintf(stderr, "Invalid key type(");
- print_key_type(stderr, 0, key_type);
- fprintf(stderr, ") found in root(");
- print_objectid(stderr, rootid, 0);
- fprintf(stderr, ")\n");
-}
-
-/*
- * Check if the key is valid with its extent buffer.
- *
- * This is a early check in case invalid key exists in a extent buffer
- * This is not comprehensive yet, but should prevent wrong key/item passed
- * further
- */
-static int check_type_with_root(u64 rootid, u8 key_type)
-{
- switch (key_type) {
- /* Only valid in chunk tree */
- case BTRFS_DEV_ITEM_KEY:
- case BTRFS_CHUNK_ITEM_KEY:
- if (rootid != BTRFS_CHUNK_TREE_OBJECTID)
- goto err;
- break;
- /* valid in csum and log tree */
- case BTRFS_CSUM_TREE_OBJECTID:
- if (!(rootid == BTRFS_TREE_LOG_OBJECTID ||
- is_fstree(rootid)))
- goto err;
- break;
- case BTRFS_EXTENT_ITEM_KEY:
- case BTRFS_METADATA_ITEM_KEY:
- case BTRFS_BLOCK_GROUP_ITEM_KEY:
- if (rootid != BTRFS_EXTENT_TREE_OBJECTID)
- goto err;
- break;
- case BTRFS_ROOT_ITEM_KEY:
- if (rootid != BTRFS_ROOT_TREE_OBJECTID)
- goto err;
- break;
- case BTRFS_DEV_EXTENT_KEY:
- if (rootid != BTRFS_DEV_TREE_OBJECTID)
- goto err;
- break;
- }
- return 0;
-err:
- report_mismatch_key_root(key_type, rootid);
- return -EINVAL;
-}
-
-static int run_next_block(struct btrfs_root *root,
- struct block_info *bits,
- int bits_nr,
- u64 *last,
- struct cache_tree *pending,
- struct cache_tree *seen,
- struct cache_tree *reada,
- struct cache_tree *nodes,
- struct cache_tree *extent_cache,
- struct cache_tree *chunk_cache,
- struct rb_root *dev_cache,
- struct block_group_tree *block_group_cache,
- struct device_extent_tree *dev_extent_cache,
- struct root_item_record *ri)
-{
- struct btrfs_fs_info *fs_info = root->fs_info;
- struct extent_buffer *buf;
- struct extent_record *rec = NULL;
- u64 bytenr;
- u32 size;
- u64 parent;
- u64 owner;
- u64 flags;
- u64 ptr;
- u64 gen = 0;
- int ret = 0;
- int i;
- int nritems;
- struct btrfs_key key;
- struct cache_extent *cache;
- int reada_bits;
-
- nritems = pick_next_pending(pending, reada, nodes, *last, bits,
- bits_nr, &reada_bits);
- if (nritems == 0)
- return 1;
-
- if (!reada_bits) {
- for(i = 0; i < nritems; i++) {
- ret = add_cache_extent(reada, bits[i].start,
- bits[i].size);
- if (ret == -EEXIST)
- continue;
-
- /* fixme, get the parent transid */
- readahead_tree_block(fs_info, bits[i].start, 0);
- }
- }
- *last = bits[0].start;
- bytenr = bits[0].start;
- size = bits[0].size;
-
- cache = lookup_cache_extent(pending, bytenr, size);
- if (cache) {
- remove_cache_extent(pending, cache);
- free(cache);
- }
- cache = lookup_cache_extent(reada, bytenr, size);
- if (cache) {
- remove_cache_extent(reada, cache);
- free(cache);
- }
- cache = lookup_cache_extent(nodes, bytenr, size);
- if (cache) {
- remove_cache_extent(nodes, cache);
- free(cache);
- }
- cache = lookup_cache_extent(extent_cache, bytenr, size);
- if (cache) {
- rec = container_of(cache, struct extent_record, cache);
- gen = rec->parent_generation;
- }
-
- /* fixme, get the real parent transid */
- buf = read_tree_block(root->fs_info, bytenr, gen);
- if (!extent_buffer_uptodate(buf)) {
- record_bad_block_io(root->fs_info,
- extent_cache, bytenr, size);
- goto out;
- }
-
- nritems = btrfs_header_nritems(buf);
-
- flags = 0;
- if (!init_extent_tree) {
- ret = btrfs_lookup_extent_info(NULL, root, bytenr,
- btrfs_header_level(buf), 1, NULL,
- &flags);
- if (ret < 0) {
- ret = calc_extent_flag(extent_cache, buf, ri, &flags);
- if (ret < 0) {
- fprintf(stderr, "Couldn't calc extent flags\n");
- flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- }
- }
- } else {
- flags = 0;
- ret = calc_extent_flag(extent_cache, buf, ri, &flags);
- if (ret < 0) {
- fprintf(stderr, "Couldn't calc extent flags\n");
- flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- }
- }
-
- if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
- if (ri != NULL &&
- ri->objectid != BTRFS_TREE_RELOC_OBJECTID &&
- ri->objectid == btrfs_header_owner(buf)) {
- /*
- * Ok we got to this block from it's original owner and
- * we have FULL_BACKREF set. Relocation can leave
- * converted blocks over so this is altogether possible,
- * however it's not possible if the generation > the
- * last snapshot, so check for this case.
- */
- if (!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC) &&
- btrfs_header_generation(buf) > ri->last_snapshot) {
- flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
- rec->bad_full_backref = 1;
- }
- }
- } else {
- if (ri != NULL &&
- (ri->objectid == BTRFS_TREE_RELOC_OBJECTID ||
- btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) {
- flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- rec->bad_full_backref = 1;
- }
- }
-
- if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
- rec->flag_block_full_backref = 1;
- parent = bytenr;
- owner = 0;
- } else {
- rec->flag_block_full_backref = 0;
- parent = 0;
- owner = btrfs_header_owner(buf);
- }
-
- ret = check_block(root, extent_cache, buf, flags);
- if (ret)
- goto out;
-
- if (btrfs_is_leaf(buf)) {
- btree_space_waste += btrfs_leaf_free_space(root, buf);
- for (i = 0; i < nritems; i++) {
- struct btrfs_file_extent_item *fi;
- btrfs_item_key_to_cpu(buf, &key, i);
- /*
- * Check key type against the leaf owner.
- * Could filter quite a lot of early error if
- * owner is correct
- */
- if (check_type_with_root(btrfs_header_owner(buf),
- key.type)) {
- fprintf(stderr, "ignoring invalid key\n");
- continue;
- }
- if (key.type == BTRFS_EXTENT_ITEM_KEY) {
- process_extent_item(root, extent_cache, buf,
- i);
- continue;
- }
- if (key.type == BTRFS_METADATA_ITEM_KEY) {
- process_extent_item(root, extent_cache, buf,
- i);
- continue;
- }
- if (key.type == BTRFS_EXTENT_CSUM_KEY) {
- total_csum_bytes +=
- btrfs_item_size_nr(buf, i);
- continue;
- }
- if (key.type == BTRFS_CHUNK_ITEM_KEY) {
- process_chunk_item(chunk_cache, &key, buf, i);
- continue;
- }
- if (key.type == BTRFS_DEV_ITEM_KEY) {
- process_device_item(dev_cache, &key, buf, i);
- continue;
- }
- if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
- process_block_group_item(block_group_cache,
- &key, buf, i);
- continue;
- }
- if (key.type == BTRFS_DEV_EXTENT_KEY) {
- process_device_extent_item(dev_extent_cache,
- &key, buf, i);
- continue;
-
- }
- if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
-#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
- process_extent_ref_v0(extent_cache, buf, i);
-#else
- BUG();
-#endif
- continue;
- }
-
- if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
- ret = add_tree_backref(extent_cache,
- key.objectid, 0, key.offset, 0);
- if (ret < 0)
- error(
- "add_tree_backref failed (leaf tree block): %s",
- strerror(-ret));
- continue;
- }
- if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
- ret = add_tree_backref(extent_cache,
- key.objectid, key.offset, 0, 0);
- if (ret < 0)
- error(
- "add_tree_backref failed (leaf shared block): %s",
- strerror(-ret));
- continue;
- }
- if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
- struct btrfs_extent_data_ref *ref;
- ref = btrfs_item_ptr(buf, i,
- struct btrfs_extent_data_ref);
- add_data_backref(extent_cache,
- key.objectid, 0,
- btrfs_extent_data_ref_root(buf, ref),
- btrfs_extent_data_ref_objectid(buf,
- ref),
- btrfs_extent_data_ref_offset(buf, ref),
- btrfs_extent_data_ref_count(buf, ref),
- 0, root->fs_info->sectorsize);
- continue;
- }
- if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
- struct btrfs_shared_data_ref *ref;
- ref = btrfs_item_ptr(buf, i,
- struct btrfs_shared_data_ref);
- add_data_backref(extent_cache,
- key.objectid, key.offset, 0, 0, 0,
- btrfs_shared_data_ref_count(buf, ref),
- 0, root->fs_info->sectorsize);
- continue;
- }
- if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
- struct bad_item *bad;
-
- if (key.objectid == BTRFS_ORPHAN_OBJECTID)
- continue;
- if (!owner)
- continue;
- bad = malloc(sizeof(struct bad_item));
- if (!bad)
- continue;
- INIT_LIST_HEAD(&bad->list);
- memcpy(&bad->key, &key,
- sizeof(struct btrfs_key));
- bad->root_id = owner;
- list_add_tail(&bad->list, &delete_items);
- continue;
- }
- if (key.type != BTRFS_EXTENT_DATA_KEY)
- continue;
- fi = btrfs_item_ptr(buf, i,
- struct btrfs_file_extent_item);
- if (btrfs_file_extent_type(buf, fi) ==
- BTRFS_FILE_EXTENT_INLINE)
- continue;
- if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
- continue;
-
- data_bytes_allocated +=
- btrfs_file_extent_disk_num_bytes(buf, fi);
- if (data_bytes_allocated < root->fs_info->sectorsize) {
- abort();
- }
- data_bytes_referenced +=
- btrfs_file_extent_num_bytes(buf, fi);
- add_data_backref(extent_cache,
- btrfs_file_extent_disk_bytenr(buf, fi),
- parent, owner, key.objectid, key.offset -
- btrfs_file_extent_offset(buf, fi), 1, 1,
- btrfs_file_extent_disk_num_bytes(buf, fi));
- }
- } else {
- int level;
- struct btrfs_key first_key;
-
- first_key.objectid = 0;
-
- if (nritems > 0)
- btrfs_item_key_to_cpu(buf, &first_key, 0);
- level = btrfs_header_level(buf);
- for (i = 0; i < nritems; i++) {
- struct extent_record tmpl;
-
- ptr = btrfs_node_blockptr(buf, i);
- size = root->fs_info->nodesize;
- btrfs_node_key_to_cpu(buf, &key, i);
- if (ri != NULL) {
- if ((level == ri->drop_level)
- && is_dropped_key(&key, &ri->drop_key)) {
- continue;
- }
- }
-
- memset(&tmpl, 0, sizeof(tmpl));
- btrfs_cpu_key_to_disk(&tmpl.parent_key, &key);
- tmpl.parent_generation = btrfs_node_ptr_generation(buf, i);
- tmpl.start = ptr;
- tmpl.nr = size;
- tmpl.refs = 1;
- tmpl.metadata = 1;
- tmpl.max_size = size;
- ret = add_extent_rec(extent_cache, &tmpl);
- if (ret < 0)
- goto out;
-
- ret = add_tree_backref(extent_cache, ptr, parent,
- owner, 1);
- if (ret < 0) {
- error(
- "add_tree_backref failed (non-leaf block): %s",
- strerror(-ret));
- continue;
- }
-
- if (level > 1) {
- add_pending(nodes, seen, ptr, size);
- } else {
- add_pending(pending, seen, ptr, size);
- }
- }
- btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(fs_info) -
- nritems) * sizeof(struct btrfs_key_ptr);
- }
- total_btree_bytes += buf->len;
- if (fs_root_objectid(btrfs_header_owner(buf)))
- total_fs_tree_bytes += buf->len;
- if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
- total_extent_tree_bytes += buf->len;
-out:
- free_extent_buffer(buf);
- return ret;
-}
-
-static int add_root_to_pending(struct extent_buffer *buf,
- struct cache_tree *extent_cache,
- struct cache_tree *pending,
- struct cache_tree *seen,
- struct cache_tree *nodes,
- u64 objectid)
-{
- struct extent_record tmpl;
- int ret;
-
- if (btrfs_header_level(buf) > 0)
- add_pending(nodes, seen, buf->start, buf->len);
- else
- add_pending(pending, seen, buf->start, buf->len);
-
- memset(&tmpl, 0, sizeof(tmpl));
- tmpl.start = buf->start;
- tmpl.nr = buf->len;
- tmpl.is_root = 1;
- tmpl.refs = 1;
- tmpl.metadata = 1;
- tmpl.max_size = buf->len;
- add_extent_rec(extent_cache, &tmpl);
-
- if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
- btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
- ret = add_tree_backref(extent_cache, buf->start, buf->start,
- 0, 1);
- else
- ret = add_tree_backref(extent_cache, buf->start, 0, objectid,
- 1);
- return ret;
-}
-
-/* as we fix the tree, we might be deleting blocks that
- * we're tracking for repair. This hook makes sure we
- * remove any backrefs for blocks as we are fixing them.
- */
-static int free_extent_hook(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- u64 bytenr, u64 num_bytes, u64 parent,
- u64 root_objectid, u64 owner, u64 offset,
- int refs_to_drop)
-{
- struct extent_record *rec;
- struct cache_extent *cache;
- int is_data;
- struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
-
- is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
- cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
- if (!cache)
- return 0;
-
- rec = container_of(cache, struct extent_record, cache);
- if (is_data) {
- struct data_backref *back;
- back = find_data_backref(rec, parent, root_objectid, owner,
- offset, 1, bytenr, num_bytes);
- if (!back)
- goto out;
- if (back->node.found_ref) {
- back->found_ref -= refs_to_drop;
- if (rec->refs)
- rec->refs -= refs_to_drop;
- }
- if (back->node.found_extent_tree) {
- back->num_refs -= refs_to_drop;
- if (rec->extent_item_refs)
- rec->extent_item_refs -= refs_to_drop;
- }
- if (back->found_ref == 0)
- back->node.found_ref = 0;
- if (back->num_refs == 0)
- back->node.found_extent_tree = 0;
-
- if (!back->node.found_extent_tree && back->node.found_ref) {
- rb_erase(&back->node.node, &rec->backref_tree);
- free(back);
- }
- } else {
- struct tree_backref *back;
- back = find_tree_backref(rec, parent, root_objectid);
- if (!back)
- goto out;
- if (back->node.found_ref) {
- if (rec->refs)
- rec->refs--;
- back->node.found_ref = 0;
- }
- if (back->node.found_extent_tree) {
- if (rec->extent_item_refs)
- rec->extent_item_refs--;
- back->node.found_extent_tree = 0;
- }
- if (!back->node.found_extent_tree && back->node.found_ref) {
- rb_erase(&back->node.node, &rec->backref_tree);
- free(back);
- }
- }
- maybe_free_extent_rec(extent_cache, rec);
-out:
- return 0;
-}
-
-static int delete_extent_records(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- struct btrfs_path *path,
- u64 bytenr)
-{
- struct btrfs_key key;
- struct btrfs_key found_key;
- struct extent_buffer *leaf;
- int ret;
- int slot;
-
-
- key.objectid = bytenr;
- key.type = (u8)-1;
- key.offset = (u64)-1;
-
- while(1) {
- ret = btrfs_search_slot(trans, root->fs_info->extent_root,
- &key, path, 0, 1);
- if (ret < 0)
- break;
-
- if (ret > 0) {
- ret = 0;
- if (path->slots[0] == 0)
- break;
- path->slots[0]--;
- }
- ret = 0;
-
- leaf = path->nodes[0];
- slot = path->slots[0];
-
- btrfs_item_key_to_cpu(leaf, &found_key, slot);
- if (found_key.objectid != bytenr)
- break;
-
- if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
- found_key.type != BTRFS_METADATA_ITEM_KEY &&
- found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
- found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
- found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
- found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
- found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
- btrfs_release_path(path);
- if (found_key.type == 0) {
- if (found_key.offset == 0)
- break;
- key.offset = found_key.offset - 1;
- key.type = found_key.type;
- }
- key.type = found_key.type - 1;
- key.offset = (u64)-1;
- continue;
- }
-
- fprintf(stderr, "repair deleting extent record: key %Lu %u %Lu\n",
- found_key.objectid, found_key.type, found_key.offset);
-
- ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
- if (ret)
- break;
- btrfs_release_path(path);
-
- if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
- found_key.type == BTRFS_METADATA_ITEM_KEY) {
- u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
- found_key.offset : root->fs_info->nodesize;
-
- ret = btrfs_update_block_group(root, bytenr,
- bytes, 0, 0);
- if (ret)
- break;
- }
- }
-
- btrfs_release_path(path);
- return ret;
-}
-
-/*
- * for a single backref, this will allocate a new extent
- * and add the backref to it.
- */
-static int record_extent(struct btrfs_trans_handle *trans,
- struct btrfs_fs_info *info,
- struct btrfs_path *path,
- struct extent_record *rec,
- struct extent_backref *back,
- int allocated, u64 flags)
-{
- int ret = 0;
- struct btrfs_root *extent_root = info->extent_root;
- struct extent_buffer *leaf;
- struct btrfs_key ins_key;
- struct btrfs_extent_item *ei;
- struct data_backref *dback;
- struct btrfs_tree_block_info *bi;
-
- if (!back->is_data)
- rec->max_size = max_t(u64, rec->max_size,
- info->nodesize);
-
- if (!allocated) {
- u32 item_size = sizeof(*ei);
-
- if (!back->is_data)
- item_size += sizeof(*bi);
-
- ins_key.objectid = rec->start;
- ins_key.offset = rec->max_size;
- ins_key.type = BTRFS_EXTENT_ITEM_KEY;
-
- ret = btrfs_insert_empty_item(trans, extent_root, path,
- &ins_key, item_size);
- if (ret)
- goto fail;
-
- leaf = path->nodes[0];
- ei = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_extent_item);
-
- btrfs_set_extent_refs(leaf, ei, 0);
- btrfs_set_extent_generation(leaf, ei, rec->generation);
-
- if (back->is_data) {
- btrfs_set_extent_flags(leaf, ei,
- BTRFS_EXTENT_FLAG_DATA);
- } else {
- struct btrfs_disk_key copy_key;;
-
- bi = (struct btrfs_tree_block_info *)(ei + 1);
- memset_extent_buffer(leaf, 0, (unsigned long)bi,
- sizeof(*bi));
-
- btrfs_set_disk_key_objectid(©_key,
- rec->info_objectid);
- btrfs_set_disk_key_type(©_key, 0);
- btrfs_set_disk_key_offset(©_key, 0);
-
- btrfs_set_tree_block_level(leaf, bi, rec->info_level);
- btrfs_set_tree_block_key(leaf, bi, ©_key);
-
- btrfs_set_extent_flags(leaf, ei,
- BTRFS_EXTENT_FLAG_TREE_BLOCK | flags);
- }
-
- btrfs_mark_buffer_dirty(leaf);
- ret = btrfs_update_block_group(extent_root, rec->start,
- rec->max_size, 1, 0);
- if (ret)
- goto fail;
- btrfs_release_path(path);
- }
-
- if (back->is_data) {
- u64 parent;
- int i;
-
- dback = to_data_backref(back);
- if (back->full_backref)
- parent = dback->parent;
- else
- parent = 0;
-
- for (i = 0; i < dback->found_ref; i++) {
- /* if parent != 0, we're doing a full backref
- * passing BTRFS_FIRST_FREE_OBJECTID as the owner
- * just makes the backref allocator create a data
- * backref
- */
- ret = btrfs_inc_extent_ref(trans, info->extent_root,
- rec->start, rec->max_size,
- parent,
- dback->root,
- parent ?
- BTRFS_FIRST_FREE_OBJECTID :
- dback->owner,
- dback->offset);
- if (ret)
- break;
- }
- fprintf(stderr, "adding new data backref"
- " on %llu %s %llu owner %llu"
- " offset %llu found %d\n",
- (unsigned long long)rec->start,
- back->full_backref ?
- "parent" : "root",
- back->full_backref ?
- (unsigned long long)parent :
- (unsigned long long)dback->root,
- (unsigned long long)dback->owner,
- (unsigned long long)dback->offset,
- dback->found_ref);
- } else {
- u64 parent;
- struct tree_backref *tback;
-
- tback = to_tree_backref(back);
- if (back->full_backref)
- parent = tback->parent;
- else
- parent = 0;
-
- ret = btrfs_inc_extent_ref(trans, info->extent_root,
- rec->start, rec->max_size,
- parent, tback->root, 0, 0);
- fprintf(stderr, "adding new tree backref on "
- "start %llu len %llu parent %llu root %llu\n",
- rec->start, rec->max_size, parent, tback->root);
- }
-fail:
- btrfs_release_path(path);
- return ret;
-}
-
-static struct extent_entry *find_entry(struct list_head *entries,
- u64 bytenr, u64 bytes)
-{
- struct extent_entry *entry = NULL;
-
- list_for_each_entry(entry, entries, list) {
- if (entry->bytenr == bytenr && entry->bytes == bytes)
- return entry;
- }
-
- return NULL;
-}
-
-static struct extent_entry *find_most_right_entry(struct list_head *entries)
-{
- struct extent_entry *entry, *best = NULL, *prev = NULL;
-
- list_for_each_entry(entry, entries, list) {
- /*
- * If there are as many broken entries as entries then we know
- * not to trust this particular entry.
- */
- if (entry->broken == entry->count)
- continue;
-
- /*
- * Special case, when there are only two entries and 'best' is
- * the first one
- */
- if (!prev) {
- best = entry;
- prev = entry;
- continue;
- }
-
- /*
- * If our current entry == best then we can't be sure our best
- * is really the best, so we need to keep searching.
- */
- if (best && best->count == entry->count) {
- prev = entry;
- best = NULL;
- continue;
- }
-
- /* Prev == entry, not good enough, have to keep searching */
- if (!prev->broken && prev->count == entry->count)
- continue;
-
- if (!best)
- best = (prev->count > entry->count) ? prev : entry;
- else if (best->count < entry->count)
- best = entry;
- prev = entry;
- }
-
- return best;
-}
-
-static int repair_ref(struct btrfs_fs_info *info, struct btrfs_path *path,
- struct data_backref *dback, struct extent_entry *entry)
-{
- struct btrfs_trans_handle *trans;
- struct btrfs_root *root;
- struct btrfs_file_extent_item *fi;
- struct extent_buffer *leaf;
- struct btrfs_key key;
- u64 bytenr, bytes;
- int ret, err;
-
- key.objectid = dback->root;
- key.type = BTRFS_ROOT_ITEM_KEY;
- key.offset = (u64)-1;
- root = btrfs_read_fs_root(info, &key);
- if (IS_ERR(root)) {
- fprintf(stderr, "Couldn't find root for our ref\n");
- return -EINVAL;
- }
-
- /*
- * The backref points to the original offset of the extent if it was
- * split, so we need to search down to the offset we have and then walk
- * forward until we find the backref we're looking for.
- */
- key.objectid = dback->owner;
- key.type = BTRFS_EXTENT_DATA_KEY;
- key.offset = dback->offset;
- ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
- if (ret < 0) {
- fprintf(stderr, "Error looking up ref %d\n", ret);
- return ret;
- }
-
- while (1) {
- if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
- ret = btrfs_next_leaf(root, path);
- if (ret) {
- fprintf(stderr, "Couldn't find our ref, next\n");
- return -EINVAL;
- }
- }
- leaf = path->nodes[0];
- btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
- if (key.objectid != dback->owner ||
- key.type != BTRFS_EXTENT_DATA_KEY) {
- fprintf(stderr, "Couldn't find our ref, search\n");
- return -EINVAL;
- }
- fi = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_file_extent_item);
- bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
- bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
-
- if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
- break;
- path->slots[0]++;
- }
-
- btrfs_release_path(path);
-
- trans = btrfs_start_transaction(root, 1);
- if (IS_ERR(trans))
- return PTR_ERR(trans);
-
- /*
- * Ok we have the key of the file extent we want to fix, now we can cow
- * down to the thing and fix it.
- */
- ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
- if (ret < 0) {
- fprintf(stderr, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
- key.objectid, key.type, key.offset, ret);
- goto out;
- }
- if (ret > 0) {
- fprintf(stderr, "Well that's odd, we just found this key "
- "[%Lu, %u, %Lu]\n", key.objectid, key.type,
- key.offset);
- ret = -EINVAL;
- goto out;
- }
- leaf = path->nodes[0];
- fi = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_file_extent_item);
-
- if (btrfs_file_extent_compression(leaf, fi) &&
- dback->disk_bytenr != entry->bytenr) {
- fprintf(stderr, "Ref doesn't match the record start and is "
- "compressed, please take a btrfs-image of this file "
- "system and send it to a btrfs developer so they can "
- "complete this functionality for bytenr %Lu\n",
- dback->disk_bytenr);
- ret = -EINVAL;
- goto out;
- }
-
- if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
- btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
- } else if (dback->disk_bytenr > entry->bytenr) {
- u64 off_diff, offset;
-
- off_diff = dback->disk_bytenr - entry->bytenr;
- offset = btrfs_file_extent_offset(leaf, fi);
- if (dback->disk_bytenr + offset +
- btrfs_file_extent_num_bytes(leaf, fi) >
- entry->bytenr + entry->bytes) {
- fprintf(stderr, "Ref is past the entry end, please "
- "take a btrfs-image of this file system and "
- "send it to a btrfs developer, ref %Lu\n",
- dback->disk_bytenr);
- ret = -EINVAL;
- goto out;
- }
- offset += off_diff;
- btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
- btrfs_set_file_extent_offset(leaf, fi, offset);
- } else if (dback->disk_bytenr < entry->bytenr) {
- u64 offset;
-
- offset = btrfs_file_extent_offset(leaf, fi);
- if (dback->disk_bytenr + offset < entry->bytenr) {
- fprintf(stderr, "Ref is before the entry start, please"
- " take a btrfs-image of this file system and "
- "send it to a btrfs developer, ref %Lu\n",
- dback->disk_bytenr);
- ret = -EINVAL;
- goto out;
- }
-
- offset += dback->disk_bytenr;
- offset -= entry->bytenr;
- btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
- btrfs_set_file_extent_offset(leaf, fi, offset);
- }
-
- btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
-
- /*
- * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
- * only do this if we aren't using compression, otherwise it's a
- * trickier case.
- */
- if (!btrfs_file_extent_compression(leaf, fi))
- btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
- else
- printf("ram bytes may be wrong?\n");
- btrfs_mark_buffer_dirty(leaf);
-out:
- err = btrfs_commit_transaction(trans, root);
- btrfs_release_path(path);
- return ret ? ret : err;
-}
-
-static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
- struct extent_record *rec)
-{
- struct extent_backref *back, *tmp;
- struct data_backref *dback;
- struct extent_entry *entry, *best = NULL;
- LIST_HEAD(entries);
- int nr_entries = 0;
- int broken_entries = 0;
- int ret = 0;
- short mismatch = 0;
-
- /*
- * Metadata is easy and the backrefs should always agree on bytenr and
- * size, if not we've got bigger issues.
- */
- if (rec->metadata)
- return 0;
-
- rbtree_postorder_for_each_entry_safe(back, tmp,
- &rec->backref_tree, node) {
- if (back->full_backref || !back->is_data)
- continue;
-
- dback = to_data_backref(back);
-
- /*
- * We only pay attention to backrefs that we found a real
- * backref for.
- */
- if (dback->found_ref == 0)
- continue;
-
- /*
- * For now we only catch when the bytes don't match, not the
- * bytenr. We can easily do this at the same time, but I want
- * to have a fs image to test on before we just add repair
- * functionality willy-nilly so we know we won't screw up the
- * repair.
- */
-
- entry = find_entry(&entries, dback->disk_bytenr,
- dback->bytes);
- if (!entry) {
- entry = malloc(sizeof(struct extent_entry));
- if (!entry) {
- ret = -ENOMEM;
- goto out;
- }
- memset(entry, 0, sizeof(*entry));
- entry->bytenr = dback->disk_bytenr;
- entry->bytes = dback->bytes;
- list_add_tail(&entry->list, &entries);
- nr_entries++;
- }
-
- /*
- * If we only have on entry we may think the entries agree when
- * in reality they don't so we have to do some extra checking.
- */
- if (dback->disk_bytenr != rec->start ||
- dback->bytes != rec->nr || back->broken)
- mismatch = 1;
-
- if (back->broken) {
- entry->broken++;
- broken_entries++;
- }
-
- entry->count++;
- }
-
- /* Yay all the backrefs agree, carry on good sir */
- if (nr_entries <= 1 && !mismatch)
- goto out;
-
- fprintf(stderr, "attempting to repair backref discrepency for bytenr "
- "%Lu\n", rec->start);
-
- /*
- * First we want to see if the backrefs can agree amongst themselves who
- * is right, so figure out which one of the entries has the highest
- * count.
- */
- best = find_most_right_entry(&entries);
-
- /*
- * Ok so we may have an even split between what the backrefs think, so
- * this is where we use the extent ref to see what it thinks.
- */
- if (!best) {
- entry = find_entry(&entries, rec->start, rec->nr);
- if (!entry && (!broken_entries || !rec->found_rec)) {
- fprintf(stderr, "Backrefs don't agree with each other "
- "and extent record doesn't agree with anybody,"
- " so we can't fix bytenr %Lu bytes %Lu\n",
- rec->start, rec->nr);
- ret = -EINVAL;
- goto out;
- } else if (!entry) {
- /*
- * Ok our backrefs were broken, we'll assume this is the
- * correct value and add an entry for this range.
- */
- entry = malloc(sizeof(struct extent_entry));
- if (!entry) {
- ret = -ENOMEM;
- goto out;
- }
- memset(entry, 0, sizeof(*entry));
- entry->bytenr = rec->start;
- entry->bytes = rec->nr;
- list_add_tail(&entry->list, &entries);
- nr_entries++;
- }
- entry->count++;
- best = find_most_right_entry(&entries);
- if (!best) {
- fprintf(stderr, "Backrefs and extent record evenly "
- "split on who is right, this is going to "
- "require user input to fix bytenr %Lu bytes "
- "%Lu\n", rec->start, rec->nr);
- ret = -EINVAL;
- goto out;
- }
- }
-
- /*
- * I don't think this can happen currently as we'll abort() if we catch
- * this case higher up, but in case somebody removes that we still can't
- * deal with it properly here yet, so just bail out of that's the case.
- */
- if (best->bytenr != rec->start) {
- fprintf(stderr, "Extent start and backref starts don't match, "
- "please use btrfs-image on this file system and send "
- "it to a btrfs developer so they can make fsck fix "
- "this particular case. bytenr is %Lu, bytes is %Lu\n",
- rec->start, rec->nr);
- ret = -EINVAL;
- goto out;
- }
-
- /*
- * Ok great we all agreed on an extent record, let's go find the real
- * references and fix up the ones that don't match.
- */
- rbtree_postorder_for_each_entry_safe(back, tmp,
- &rec->backref_tree, node) {
- if (back->full_backref || !back->is_data)
- continue;
-
- dback = to_data_backref(back);
-
- /*
- * Still ignoring backrefs that don't have a real ref attached
- * to them.
- */
- if (dback->found_ref == 0)
- continue;
-
- if (dback->bytes == best->bytes &&
- dback->disk_bytenr == best->bytenr)
- continue;
-
- ret = repair_ref(info, path, dback, best);
- if (ret)
- goto out;
- }
-
- /*
- * Ok we messed with the actual refs, which means we need to drop our
- * entire cache and go back and rescan. I know this is a huge pain and
- * adds a lot of extra work, but it's the only way to be safe. Once all
- * the backrefs agree we may not need to do anything to the extent
- * record itself.
- */
- ret = -EAGAIN;
-out:
- while (!list_empty(&entries)) {
- entry = list_entry(entries.next, struct extent_entry, list);
- list_del_init(&entry->list);
- free(entry);
- }
- return ret;
-}
-
-static int process_duplicates(struct cache_tree *extent_cache,
- struct extent_record *rec)
-{
- struct extent_record *good, *tmp;
- struct cache_extent *cache;
- int ret;
-
- /*
- * If we found a extent record for this extent then return, or if we
- * have more than one duplicate we are likely going to need to delete
- * something.
- */
- if (rec->found_rec || rec->num_duplicates > 1)
- return 0;
-
- /* Shouldn't happen but just in case */
- BUG_ON(!rec->num_duplicates);
-
- /*
- * So this happens if we end up with a backref that doesn't match the
- * actual extent entry. So either the backref is bad or the extent
- * entry is bad. Either way we want to have the extent_record actually
- * reflect what we found in the extent_tree, so we need to take the
- * duplicate out and use that as the extent_record since the only way we
- * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
- */
- remove_cache_extent(extent_cache, &rec->cache);
-
- good = to_extent_record(rec->dups.next);
- list_del_init(&good->list);
- INIT_LIST_HEAD(&good->backrefs);
- INIT_LIST_HEAD(&good->dups);
- good->cache.start = good->start;
- good->cache.size = good->nr;
- good->content_checked = 0;
- good->owner_ref_checked = 0;
- good->num_duplicates = 0;
- good->refs = rec->refs;
- list_splice_init(&rec->backrefs, &good->backrefs);
- while (1) {
- cache = lookup_cache_extent(extent_cache, good->start,
- good->nr);
- if (!cache)
- break;
- tmp = container_of(cache, struct extent_record, cache);
-
- /*
- * If we find another overlapping extent and it's found_rec is
- * set then it's a duplicate and we need to try and delete
- * something.
- */
- if (tmp->found_rec || tmp->num_duplicates > 0) {
- if (list_empty(&good->list))
- list_add_tail(&good->list,
- &duplicate_extents);
- good->num_duplicates += tmp->num_duplicates + 1;
- list_splice_init(&tmp->dups, &good->dups);
- list_del_init(&tmp->list);
- list_add_tail(&tmp->list, &good->dups);
- remove_cache_extent(extent_cache, &tmp->cache);
- continue;
- }
-
- /*
- * Ok we have another non extent item backed extent rec, so lets
- * just add it to this extent and carry on like we did above.
- */
- good->refs += tmp->refs;
- list_splice_init(&tmp->backrefs, &good->backrefs);
- remove_cache_extent(extent_cache, &tmp->cache);
- free(tmp);
- }
- ret = insert_cache_extent(extent_cache, &good->cache);
- BUG_ON(ret);
- free(rec);
- return good->num_duplicates ? 0 : 1;
-}
-
-static int delete_duplicate_records(struct btrfs_root *root,
- struct extent_record *rec)
-{
- struct btrfs_trans_handle *trans;
- LIST_HEAD(delete_list);
- struct btrfs_path path;
- struct extent_record *tmp, *good, *n;
- int nr_del = 0;
- int ret = 0, err;
- struct btrfs_key key;
-
- btrfs_init_path(&path);
-
- good = rec;
- /* Find the record that covers all of the duplicates. */
- list_for_each_entry(tmp, &rec->dups, list) {
- if (good->start < tmp->start)
- continue;
- if (good->nr > tmp->nr)
- continue;
-
- if (tmp->start + tmp->nr < good->start + good->nr) {
- fprintf(stderr, "Ok we have overlapping extents that "
- "aren't completely covered by each other, this "
- "is going to require more careful thought. "
- "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
- tmp->start, tmp->nr, good->start, good->nr);
- abort();
- }
- good = tmp;
- }
-
- if (good != rec)
- list_add_tail(&rec->list, &delete_list);
-
- list_for_each_entry_safe(tmp, n, &rec->dups, list) {
- if (tmp == good)
- continue;
- list_move_tail(&tmp->list, &delete_list);
- }
-
- root = root->fs_info->extent_root;
- trans = btrfs_start_transaction(root, 1);
- if (IS_ERR(trans)) {
- ret = PTR_ERR(trans);
- goto out;
- }
-
- list_for_each_entry(tmp, &delete_list, list) {
- if (tmp->found_rec == 0)
- continue;
- key.objectid = tmp->start;
- key.type = BTRFS_EXTENT_ITEM_KEY;
- key.offset = tmp->nr;
-
- /* Shouldn't happen but just in case */
- if (tmp->metadata) {
- fprintf(stderr, "Well this shouldn't happen, extent "
- "record overlaps but is metadata? "
- "[%Lu, %Lu]\n", tmp->start, tmp->nr);
- abort();
- }
-
- ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
- if (ret) {
- if (ret > 0)
- ret = -EINVAL;
- break;
- }
- ret = btrfs_del_item(trans, root, &path);
- if (ret)
- break;
- btrfs_release_path(&path);
- nr_del++;
- }
- err = btrfs_commit_transaction(trans, root);
- if (err && !ret)
- ret = err;
-out:
- while (!list_empty(&delete_list)) {
- tmp = to_extent_record(delete_list.next);
- list_del_init(&tmp->list);
- if (tmp == rec)
- continue;
- free(tmp);
- }
-
- while (!list_empty(&rec->dups)) {
- tmp = to_extent_record(rec->dups.next);
- list_del_init(&tmp->list);
- free(tmp);
- }
-
- btrfs_release_path(&path);
-
- if (!ret && !nr_del)
- rec->num_duplicates = 0;
-
- return ret ? ret : nr_del;
-}
-
-static int find_possible_backrefs(struct btrfs_fs_info *info,
- struct btrfs_path *path,
- struct cache_tree *extent_cache,
- struct extent_record *rec)
-{
- struct btrfs_root *root;
- struct extent_backref *back, *tmp;
- struct data_backref *dback;
- struct cache_extent *cache;
- struct btrfs_file_extent_item *fi;
- struct btrfs_key key;
- u64 bytenr, bytes;
- int ret;
-
- rbtree_postorder_for_each_entry_safe(back, tmp,
- &rec->backref_tree, node) {
- /* Don't care about full backrefs (poor unloved backrefs) */
- if (back->full_backref || !back->is_data)
- continue;
-
- dback = to_data_backref(back);
-
- /* We found this one, we don't need to do a lookup */
- if (dback->found_ref)
- continue;
-
- key.objectid = dback->root;
- key.type = BTRFS_ROOT_ITEM_KEY;
- key.offset = (u64)-1;
-
- root = btrfs_read_fs_root(info, &key);
-
- /* No root, definitely a bad ref, skip */
- if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
- continue;
- /* Other err, exit */
- if (IS_ERR(root))
- return PTR_ERR(root);
-
- key.objectid = dback->owner;
- key.type = BTRFS_EXTENT_DATA_KEY;
- key.offset = dback->offset;
- ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
- if (ret) {
- btrfs_release_path(path);
- if (ret < 0)
- return ret;
- /* Didn't find it, we can carry on */
- ret = 0;
- continue;
- }
-
- fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
- struct btrfs_file_extent_item);
- bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
- bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
- btrfs_release_path(path);
- cache = lookup_cache_extent(extent_cache, bytenr, 1);
- if (cache) {
- struct extent_record *tmp;
- tmp = container_of(cache, struct extent_record, cache);
-
- /*
- * If we found an extent record for the bytenr for this
- * particular backref then we can't add it to our
- * current extent record. We only want to add backrefs
- * that don't have a corresponding extent item in the
- * extent tree since they likely belong to this record
- * and we need to fix it if it doesn't match bytenrs.
- */
- if (tmp->found_rec)
- continue;
- }
-
- dback->found_ref += 1;
- dback->disk_bytenr = bytenr;
- dback->bytes = bytes;
-
- /*
- * Set this so the verify backref code knows not to trust the
- * values in this backref.
- */
- back->broken = 1;
- }
-
- return 0;
-}
-
-/*
- * Record orphan data ref into corresponding root.
- *
- * Return 0 if the extent item contains data ref and recorded.
- * Return 1 if the extent item contains no useful data ref
- * On that case, it may contains only shared_dataref or metadata backref
- * or the file extent exists(this should be handled by the extent bytenr
- * recovery routine)
- * Return <0 if something goes wrong.
- */
-static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
- struct extent_record *rec)
-{
- struct btrfs_key key;
- struct btrfs_root *dest_root;
- struct extent_backref *back, *tmp;
- struct data_backref *dback;
- struct orphan_data_extent *orphan;
- struct btrfs_path path;
- int recorded_data_ref = 0;
- int ret = 0;
-
- if (rec->metadata)
- return 1;
- btrfs_init_path(&path);
- rbtree_postorder_for_each_entry_safe(back, tmp,
- &rec->backref_tree, node) {
- if (back->full_backref || !back->is_data ||
- !back->found_extent_tree)
- continue;
- dback = to_data_backref(back);
- if (dback->found_ref)
- continue;
- key.objectid = dback->root;
- key.type = BTRFS_ROOT_ITEM_KEY;
- key.offset = (u64)-1;
-
- dest_root = btrfs_read_fs_root(fs_info, &key);
-
- /* For non-exist root we just skip it */
- if (IS_ERR(dest_root) || !dest_root)
- continue;
-
- key.objectid = dback->owner;
- key.type = BTRFS_EXTENT_DATA_KEY;
- key.offset = dback->offset;
-
- ret = btrfs_search_slot(NULL, dest_root, &key, &path, 0, 0);
- btrfs_release_path(&path);
- /*
- * For ret < 0, it's OK since the fs-tree may be corrupted,
- * we need to record it for inode/file extent rebuild.
- * For ret > 0, we record it only for file extent rebuild.
- * For ret == 0, the file extent exists but only bytenr
- * mismatch, let the original bytenr fix routine to handle,
- * don't record it.
- */
- if (ret == 0)
- continue;
- ret = 0;
- orphan = malloc(sizeof(*orphan));
- if (!orphan) {
- ret = -ENOMEM;
- goto out;
- }
- INIT_LIST_HEAD(&orphan->list);
- orphan->root = dback->root;
- orphan->objectid = dback->owner;
- orphan->offset = dback->offset;
- orphan->disk_bytenr = rec->cache.start;
- orphan->disk_len = rec->cache.size;
- list_add(&dest_root->orphan_data_extents, &orphan->list);
- recorded_data_ref = 1;
- }
-out:
- btrfs_release_path(&path);
- if (!ret)
- return !recorded_data_ref;
- else
- return ret;
-}
-
-/*
- * when an incorrect extent item is found, this will delete
- * all of the existing entries for it and recreate them
- * based on what the tree scan found.
- */
-static int fixup_extent_refs(struct btrfs_fs_info *info,
- struct cache_tree *extent_cache,
- struct extent_record *rec)
-{
- struct btrfs_trans_handle *trans = NULL;
- int ret;
- struct btrfs_path path;
- struct cache_extent *cache;
- struct extent_backref *back, *tmp;
- int allocated = 0;
- u64 flags = 0;
-
- if (rec->flag_block_full_backref)
- flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
-
- btrfs_init_path(&path);
- if (rec->refs != rec->extent_item_refs && !rec->metadata) {
- /*
- * Sometimes the backrefs themselves are so broken they don't
- * get attached to any meaningful rec, so first go back and
- * check any of our backrefs that we couldn't find and throw
- * them into the list if we find the backref so that
- * verify_backrefs can figure out what to do.
- */
- ret = find_possible_backrefs(info, &path, extent_cache, rec);
- if (ret < 0)
- goto out;
- }
-
- /* step one, make sure all of the backrefs agree */
- ret = verify_backrefs(info, &path, rec);
- if (ret < 0)
- goto out;
-
- trans = btrfs_start_transaction(info->extent_root, 1);
- if (IS_ERR(trans)) {
- ret = PTR_ERR(trans);
- goto out;
- }
-
- /* step two, delete all the existing records */
- ret = delete_extent_records(trans, info->extent_root, &path,
- rec->start);
-
- if (ret < 0)
- goto out;
-
- /* was this block corrupt? If so, don't add references to it */
- cache = lookup_cache_extent(info->corrupt_blocks,
- rec->start, rec->max_size);
- if (cache) {
- ret = 0;
- goto out;
- }
-
- /* step three, recreate all the refs we did find */
- rbtree_postorder_for_each_entry_safe(back, tmp,
- &rec->backref_tree, node) {
- /*
- * if we didn't find any references, don't create a
- * new extent record
- */
- if (!back->found_ref)
- continue;
-
- rec->bad_full_backref = 0;
- ret = record_extent(trans, info, &path, rec, back, allocated, flags);
- allocated = 1;
-
- if (ret)
- goto out;
- }
-out:
- if (trans) {
- int err = btrfs_commit_transaction(trans, info->extent_root);
- if (!ret)
- ret = err;
- }
-
- if (!ret)
- fprintf(stderr, "Repaired extent references for %llu\n",
- (unsigned long long)rec->start);
-
- btrfs_release_path(&path);
- return ret;
-}
-
-static int fixup_extent_flags(struct btrfs_fs_info *fs_info,
- struct extent_record *rec)
-{
- struct btrfs_trans_handle *trans;
- struct btrfs_root *root = fs_info->extent_root;
- struct btrfs_path path;
- struct btrfs_extent_item *ei;
- struct btrfs_key key;
- u64 flags;
- int ret = 0;
-
- key.objectid = rec->start;
- if (rec->metadata) {
- key.type = BTRFS_METADATA_ITEM_KEY;
- key.offset = rec->info_level;
- } else {
- key.type = BTRFS_EXTENT_ITEM_KEY;
- key.offset = rec->max_size;
- }
-
- trans = btrfs_start_transaction(root, 0);
- if (IS_ERR(trans))
- return PTR_ERR(trans);
-
- btrfs_init_path(&path);
- ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
- if (ret < 0) {
- btrfs_release_path(&path);
- btrfs_commit_transaction(trans, root);
- return ret;
- } else if (ret) {
- fprintf(stderr, "Didn't find extent for %llu\n",
- (unsigned long long)rec->start);
- btrfs_release_path(&path);
- btrfs_commit_transaction(trans, root);
- return -ENOENT;
- }
-
- ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
- struct btrfs_extent_item);
- flags = btrfs_extent_flags(path.nodes[0], ei);
- if (rec->flag_block_full_backref) {
- fprintf(stderr, "setting full backref on %llu\n",
- (unsigned long long)key.objectid);
- flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- } else {
- fprintf(stderr, "clearing full backref on %llu\n",
- (unsigned long long)key.objectid);
- flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
- }
- btrfs_set_extent_flags(path.nodes[0], ei, flags);
- btrfs_mark_buffer_dirty(path.nodes[0]);
- btrfs_release_path(&path);
- ret = btrfs_commit_transaction(trans, root);
- if (!ret)
- fprintf(stderr, "Repaired extent flags for %llu\n",
- (unsigned long long)rec->start);
-
- return ret;
-}
-
-/* right now we only prune from the extent allocation tree */
-static int prune_one_block(struct btrfs_trans_handle *trans,
- struct btrfs_fs_info *info,
- struct btrfs_corrupt_block *corrupt)
-{
- int ret;
- struct btrfs_path path;
- struct extent_buffer *eb;
- u64 found;
- int slot;
- int nritems;
- int level = corrupt->level + 1;
-
- btrfs_init_path(&path);
-again:
- /* we want to stop at the parent to our busted block */
- path.lowest_level = level;
-
- ret = btrfs_search_slot(trans, info->extent_root,
- &corrupt->key, &path, -1, 1);
-
- if (ret < 0)
- goto out;
-
- eb = path.nodes[level];
- if (!eb) {
- ret = -ENOENT;
- goto out;
- }
-
- /*
- * hopefully the search gave us the block we want to prune,
- * lets try that first
- */
- slot = path.slots[level];
- found = btrfs_node_blockptr(eb, slot);
- if (found == corrupt->cache.start)
- goto del_ptr;
-
- nritems = btrfs_header_nritems(eb);
-
- /* the search failed, lets scan this node and hope we find it */
- for (slot = 0; slot < nritems; slot++) {
- found = btrfs_node_blockptr(eb, slot);
- if (found == corrupt->cache.start)
- goto del_ptr;
- }
- /*
- * we couldn't find the bad block. TODO, search all the nodes for pointers
- * to this block
- */
- if (eb == info->extent_root->node) {
- ret = -ENOENT;
- goto out;
- } else {
- level++;
- btrfs_release_path(&path);
- goto again;
- }
-
-del_ptr:
- printk("deleting pointer to block %Lu\n", corrupt->cache.start);
- ret = btrfs_del_ptr(info->extent_root, &path, level, slot);
-
-out:
- btrfs_release_path(&path);
- return ret;
-}
-
-static int prune_corrupt_blocks(struct btrfs_fs_info *info)
-{
- struct btrfs_trans_handle *trans = NULL;
- struct cache_extent *cache;
- struct btrfs_corrupt_block *corrupt;
-
- while (1) {
- cache = search_cache_extent(info->corrupt_blocks, 0);
- if (!cache)
- break;
- if (!trans) {
- trans = btrfs_start_transaction(info->extent_root, 1);
- if (IS_ERR(trans))
- return PTR_ERR(trans);
- }
- corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
- prune_one_block(trans, info, corrupt);
- remove_cache_extent(info->corrupt_blocks, cache);
- }
- if (trans)
- return btrfs_commit_transaction(trans, info->extent_root);
- return 0;
-}
-
-static void reset_cached_block_groups(struct btrfs_fs_info *fs_info)
-{
- struct btrfs_block_group_cache *cache;
- u64 start, end;
- int ret;
-
- while (1) {
- ret = find_first_extent_bit(&fs_info->free_space_cache, 0,
- &start, &end, EXTENT_DIRTY);
- if (ret)
- break;
- clear_extent_dirty(&fs_info->free_space_cache, start, end);
- }
-
- start = 0;
- while (1) {
- cache = btrfs_lookup_first_block_group(fs_info, start);
- if (!cache)
- break;
- if (cache->cached)
- cache->cached = 0;
- start = cache->key.objectid + cache->key.offset;
- }
-}
-
-static int check_extent_refs(struct btrfs_root *root,
- struct cache_tree *extent_cache)
-{
- struct extent_record *rec;
- struct cache_extent *cache;
- int ret = 0;
- int had_dups = 0;
- int err = 0;
-
- if (repair) {
- /*
- * if we're doing a repair, we have to make sure
- * we don't allocate from the problem extents.
- * In the worst case, this will be all the
- * extents in the FS
- */
- cache = search_cache_extent(extent_cache, 0);
- while(cache) {
- rec = container_of(cache, struct extent_record, cache);
- set_extent_dirty(root->fs_info->excluded_extents,
- rec->start,
- rec->start + rec->max_size - 1);
- cache = next_cache_extent(cache);
- }
-
- /* pin down all the corrupted blocks too */
- cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
- while(cache) {
- set_extent_dirty(root->fs_info->excluded_extents,
- cache->start,
- cache->start + cache->size - 1);
- cache = next_cache_extent(cache);
- }
- prune_corrupt_blocks(root->fs_info);
- reset_cached_block_groups(root->fs_info);
- }
-
- reset_cached_block_groups(root->fs_info);
-
- /*
- * We need to delete any duplicate entries we find first otherwise we
- * could mess up the extent tree when we have backrefs that actually
- * belong to a different extent item and not the weird duplicate one.
- */
- while (repair && !list_empty(&duplicate_extents)) {
- rec = to_extent_record(duplicate_extents.next);
- list_del_init(&rec->list);
-
- /* Sometimes we can find a backref before we find an actual
- * extent, so we need to process it a little bit to see if there
- * truly are multiple EXTENT_ITEM_KEY's for the same range, or
- * if this is a backref screwup. If we need to delete stuff
- * process_duplicates() will return 0, otherwise it will return
- * 1 and we
- */
- if (process_duplicates(extent_cache, rec))
- continue;
- ret = delete_duplicate_records(root, rec);
- if (ret < 0)
- return ret;
- /*
- * delete_duplicate_records will return the number of entries
- * deleted, so if it's greater than 0 then we know we actually
- * did something and we need to remove.
- */
- if (ret)
- had_dups = 1;
- }
-
- if (had_dups)
- return -EAGAIN;
-
- while(1) {
- int cur_err = 0;
- int fix = 0;
-
- cache = search_cache_extent(extent_cache, 0);
- if (!cache)
- break;
- rec = container_of(cache, struct extent_record, cache);
- if (rec->num_duplicates) {
- fprintf(stderr, "extent item %llu has multiple extent "
- "items\n", (unsigned long long)rec->start);
- cur_err = 1;
- }
-
- if (rec->refs != rec->extent_item_refs) {
- fprintf(stderr, "ref mismatch on [%llu %llu] ",
- (unsigned long long)rec->start,
- (unsigned long long)rec->nr);
- fprintf(stderr, "extent item %llu, found %llu\n",
- (unsigned long long)rec->extent_item_refs,
- (unsigned long long)rec->refs);
- ret = record_orphan_data_extents(root->fs_info, rec);
- if (ret < 0)
- goto repair_abort;
- fix = ret;
- cur_err = 1;
- }
- if (all_backpointers_checked(rec, 1)) {
- fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
- (unsigned long long)rec->start,
- (unsigned long long)rec->nr);
- fix = 1;
- cur_err = 1;
- }
- if (!rec->owner_ref_checked) {
- fprintf(stderr, "owner ref check failed [%llu %llu]\n",
- (unsigned long long)rec->start,
- (unsigned long long)rec->nr);
- fix = 1;
- cur_err = 1;
- }
-
- if (repair && fix) {
- ret = fixup_extent_refs(root->fs_info, extent_cache, rec);
- if (ret)
- goto repair_abort;
- }
-
-
- if (rec->bad_full_backref) {
- fprintf(stderr, "bad full backref, on [%llu]\n",
- (unsigned long long)rec->start);
- if (repair) {
- ret = fixup_extent_flags(root->fs_info, rec);
- if (ret)
- goto repair_abort;
- fix = 1;