+ return ret;
+ add_cache_extent(pending, bytenr, size);
+ return 0;
+}
+
+static int pick_next_pending(struct cache_tree *pending,
+ struct cache_tree *reada,
+ struct cache_tree *nodes,
+ u64 last, struct block_info *bits, int bits_nr,
+ int *reada_bits)
+{
+ unsigned long node_start = last;
+ struct cache_extent *cache;
+ int ret;
+
+ 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;
+
+ 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) {
+ add_tree_backref(extent_cache, key.objectid, key.offset, 0, 0);
+ } else {
+ add_data_backref(extent_cache, key.objectid, key.offset, 0,
+ 0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
+ }
+ return 0;
+}
+#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 = malloc(btrfs_chunk_record_size(num_stripes));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ exit(-1);
+ }
+
+ memset(rec, 0, btrfs_chunk_record_size(num_stripes));
+
+ 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;
+ int ret = 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 = malloc(sizeof(*rec));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ exit(-1);
+ }
+ memset(rec, 0, sizeof(*rec));
+
+ 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 = malloc(sizeof(*rec));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ exit(-1);
+ }
+ memset(rec, 0, sizeof(*rec));
+
+ 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;
+ unsigned long end;
+ unsigned long ptr;
+ 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->leafsize;
+ } else {
+ num_bytes = key.offset;
+ }
+
+ if (item_size < sizeof(*ei)) {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ struct btrfs_extent_item_v0 *ei0;
+ BUG_ON(item_size != sizeof(*ei0));
+ ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
+ refs = btrfs_extent_refs_v0(eb, ei0);
+#else
+ BUG();
+#endif
+ return add_extent_rec(extent_cache, NULL, 0, key.objectid,
+ num_bytes, refs, 0, 0, 0, metadata, 1,
+ num_bytes);
+ }
+
+ ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
+ refs = btrfs_extent_refs(eb, ei);
+
+ add_extent_rec(extent_cache, NULL, 0, key.objectid, num_bytes,
+ refs, 0, 0, 0, metadata, 1, num_bytes);
+
+ 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:
+ add_tree_backref(extent_cache, key.objectid,
+ 0, offset, 0);
+ break;
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ add_tree_backref(extent_cache, key.objectid,
+ offset, 0, 0);
+ 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->mapping_tree,
+ 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) {
+ kfree(logical);
+ return 0;
+ }
+ bytes -= stripe_len;
+ offset += stripe_len;
+ } else if (logical[nr] < offset) {
+ if (logical[nr] + stripe_len >=
+ offset + bytes) {
+ kfree(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) {
+ kfree(logical);
+ return ret;
+ }
+
+ /* Now we continue with the right side */
+ bytes = (offset + bytes) -
+ (logical[nr] + stripe_len);
+ offset = logical[nr] + stripe_len;
+ }
+ }
+
+ kfree(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;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ root = root->fs_info->extent_root;
+
+ last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
+
+ 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->leafsize;
+ 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->leafsize;
+ 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_free_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;
+ }
+
+ 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->sectorsize)) {
+ ret = -ENOMEM;
+ break;
+ }
+ } else {
+ btrfs_remove_free_space_cache(cache);
+ }
+
+ 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 isnt %Lu\n",
+ cache->key.objectid);
+ error++;
+ }
+ }
+
+ 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) {
+
+ u64 offset = 0;
+ u16 csum_size = btrfs_super_csum_size(root->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 % root->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(root, 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(NULL, (char *)data + tmp,
+ csum, root->sectorsize);
+ btrfs_csum_final(csum, (char *)&csum);
+
+ csum_offset = leaf_offset +
+ tmp / root->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->mapping_tree,
+ bytenr, num_bytes);
+ if (mirror < num_copies - 1) {
+ mirror += 1;
+ goto again;
+ }
+ }
+ data_checked += root->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;
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ fprintf(stderr, "Error allocing path\n");
+ return -ENOMEM;
+ }
+
+ 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_free_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 traveler,
+ * 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_free_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_free_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;
+ }
+
+ key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
+ key.type = BTRFS_EXTENT_CSUM_KEY;
+ key.offset = 0;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+ if (ret < 0) {
+ fprintf(stderr, "Error searching csum tree %d\n", ret);
+ btrfs_free_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->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_free_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 cow'ed 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 btrfs_root *root,
+ 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 */
+ BUG_ON(!cache);
+ 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 != -1 &&
+ 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 != -1 &&
+ rec->flag_block_full_backref != 1)
+ rec->bad_full_backref = 1;
+ return 0;
+}
+
+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 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(root, bits[i].start,
+ bits[i].size, 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, bytenr, size, 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(root, 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(root, 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)) {