diff options
| -rw-r--r-- | include/sys/btree.h | 21 | ||||
| -rw-r--r-- | module/zfs/btree.c | 8 | ||||
| -rw-r--r-- | module/zfs/dsl_scan.c | 19 | ||||
| -rw-r--r-- | module/zfs/range_tree.c | 8 |
4 files changed, 40 insertions, 16 deletions
diff --git a/include/sys/btree.h b/include/sys/btree.h index 1673b5217..9fe2534df 100644 --- a/include/sys/btree.h +++ b/include/sys/btree.h @@ -131,10 +131,10 @@ void zfs_btree_create(zfs_btree_t *, int (*) (const void *, const void *), /* * Find a node with a matching value in the tree. Returns the matching node * found. If not found, it returns NULL and then if "where" is not NULL it sets - * "where" for use with zfs_btree_insert() or zfs_btree_nearest(). + * "where" for use with zfs_btree_add_idx() or zfs_btree_nearest(). * * node - node that has the value being looked for - * where - position for use with zfs_btree_nearest() or zfs_btree_insert(), + * where - position for use with zfs_btree_nearest() or zfs_btree_add_idx(), * may be NULL */ void *zfs_btree_find(zfs_btree_t *, const void *, zfs_btree_index_t *); @@ -145,17 +145,20 @@ void *zfs_btree_find(zfs_btree_t *, const void *, zfs_btree_index_t *); * node - the node to insert * where - position as returned from zfs_btree_find() */ -void zfs_btree_insert(zfs_btree_t *, const void *, const zfs_btree_index_t *); +void zfs_btree_add_idx(zfs_btree_t *, const void *, const zfs_btree_index_t *); /* - * Return the first or last valued node in the tree. Will return NULL - * if the tree is empty. + * Return the first or last valued node in the tree. Will return NULL if the + * tree is empty. The index can be NULL if the location of the first or last + * element isn't required. */ void *zfs_btree_first(zfs_btree_t *, zfs_btree_index_t *); void *zfs_btree_last(zfs_btree_t *, zfs_btree_index_t *); /* - * Return the next or previous valued node in the tree. + * Return the next or previous valued node in the tree. The second index can + * safely be NULL, if the location of the next or previous value isn't + * required. */ void *zfs_btree_next(zfs_btree_t *, const zfs_btree_index_t *, zfs_btree_index_t *); @@ -169,7 +172,9 @@ void *zfs_btree_get(zfs_btree_t *, zfs_btree_index_t *); /* * Add a single value to the tree. The value must not compare equal to any - * other node already in the tree. + * other node already in the tree. Note that the value will be copied out, not + * inserted directly. It is safe to free or destroy the value once this + * function returns. */ void zfs_btree_add(zfs_btree_t *, const void *); @@ -183,7 +188,7 @@ void zfs_btree_remove(zfs_btree_t *, const void *); /* * Remove the value at the given location from the tree. */ -void zfs_btree_remove_from(zfs_btree_t *, zfs_btree_index_t *); +void zfs_btree_remove_idx(zfs_btree_t *, zfs_btree_index_t *); /* * Return the number of nodes in the tree diff --git a/module/zfs/btree.c b/module/zfs/btree.c index 8f514caab..f099eb67c 100644 --- a/module/zfs/btree.c +++ b/module/zfs/btree.c @@ -980,7 +980,7 @@ zfs_btree_bulk_finish(zfs_btree_t *tree) * Insert value into tree at the location specified by where. */ void -zfs_btree_insert(zfs_btree_t *tree, const void *value, +zfs_btree_add_idx(zfs_btree_t *tree, const void *value, const zfs_btree_index_t *where) { zfs_btree_index_t idx = {0}; @@ -1294,7 +1294,7 @@ zfs_btree_add(zfs_btree_t *tree, const void *node) { zfs_btree_index_t where = {0}; VERIFY3P(zfs_btree_find(tree, node, &where), ==, NULL); - zfs_btree_insert(tree, node, &where); + zfs_btree_add_idx(tree, node, &where); } /* Helper function to free a tree node. */ @@ -1542,7 +1542,7 @@ zfs_btree_remove_from_node(zfs_btree_t *tree, zfs_btree_core_t *node, /* Remove the element at the specific location. */ void -zfs_btree_remove_from(zfs_btree_t *tree, zfs_btree_index_t *where) +zfs_btree_remove_idx(zfs_btree_t *tree, zfs_btree_index_t *where) { size_t size = tree->bt_elem_size; zfs_btree_hdr_t *hdr = where->bti_node; @@ -1778,7 +1778,7 @@ zfs_btree_remove(zfs_btree_t *tree, const void *value) { zfs_btree_index_t where = {0}; VERIFY3P(zfs_btree_find(tree, value, &where), !=, NULL); - zfs_btree_remove_from(tree, &where); + zfs_btree_remove_idx(tree, &where); } /* Return the number of elements in the tree. */ diff --git a/module/zfs/dsl_scan.c b/module/zfs/dsl_scan.c index 3eacb42f1..b848f7ef3 100644 --- a/module/zfs/dsl_scan.c +++ b/module/zfs/dsl_scan.c @@ -2925,13 +2925,23 @@ scan_io_queue_fetch_ext(dsl_scan_io_queue_t *queue) if (zfs_scan_issue_strategy == 1) { return (range_tree_first(rt)); } else if (zfs_scan_issue_strategy == 2) { + /* + * We need to get the original entry in the by_addr + * tree so we can modify it. + */ range_seg_t *size_rs = zfs_btree_first(&queue->q_exts_by_size, NULL); + if (size_rs == NULL) + return (NULL); uint64_t start = rs_get_start(size_rs, rt); uint64_t size = rs_get_end(size_rs, rt) - start; range_seg_t *addr_rs = range_tree_find(rt, start, size); ASSERT3P(addr_rs, !=, NULL); + ASSERT3U(rs_get_start(size_rs, rt), ==, + rs_get_start(addr_rs, rt)); + ASSERT3U(rs_get_end(size_rs, rt), ==, + rs_get_end(addr_rs, rt)); return (addr_rs); } } @@ -2948,12 +2958,21 @@ scan_io_queue_fetch_ext(dsl_scan_io_queue_t *queue) if (scn->scn_checkpointing) { return (range_tree_first(rt)); } else if (scn->scn_clearing) { + /* + * We need to get the original entry in the by_addr + * tree so we can modify it. + */ range_seg_t *size_rs = zfs_btree_first(&queue->q_exts_by_size, NULL); + if (size_rs == NULL) + return (NULL); uint64_t start = rs_get_start(size_rs, rt); uint64_t size = rs_get_end(size_rs, rt) - start; range_seg_t *addr_rs = range_tree_find(rt, start, size); ASSERT3P(addr_rs, !=, NULL); + ASSERT3U(rs_get_start(size_rs, rt), ==, rs_get_start(addr_rs, + rt)); + ASSERT3U(rs_get_end(size_rs, rt), ==, rs_get_end(addr_rs, rt)); return (addr_rs); } else { return (NULL); diff --git a/module/zfs/range_tree.c b/module/zfs/range_tree.c index 0b369a438..1559605c2 100644 --- a/module/zfs/range_tree.c +++ b/module/zfs/range_tree.c @@ -349,7 +349,7 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill) uint64_t before_start = rs_get_start_raw(rs_before, rt); uint64_t before_fill = rs_get_fill(rs_before, rt); uint64_t after_fill = rs_get_fill(rs_after, rt); - zfs_btree_remove_from(&rt->rt_root, &where_before); + zfs_btree_remove_idx(&rt->rt_root, &where_before); /* * We have to re-find the node because our old reference is @@ -385,7 +385,7 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill) rs_set_start(rs, rt, start); rs_set_end(rs, rt, end); rs_set_fill(rs, rt, fill); - zfs_btree_insert(&rt->rt_root, rs, &where); + zfs_btree_add_idx(&rt->rt_root, rs, &where); } if (gap != 0) { @@ -488,7 +488,7 @@ range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size, rs_copy(rs, &rs_tmp, rt); if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL) - zfs_btree_insert(&rt->rt_root, &newseg, &where); + zfs_btree_add_idx(&rt->rt_root, &newseg, &where); else zfs_btree_add(&rt->rt_root, &newseg); @@ -503,7 +503,7 @@ range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size, rs_set_start(rs, rt, end); rs_copy(rs, &rs_tmp, rt); } else { - zfs_btree_remove_from(&rt->rt_root, &where); + zfs_btree_remove_idx(&rt->rt_root, &where); rs = NULL; } |