iter->l[l].b != BTREE_ITER_NOT_END;
}
+/* Returns < 0 if @k is before iter pos, > 0 if @k is after */
+static inline int __btree_iter_pos_cmp(struct btree_iter *iter,
+ const struct btree *b,
+ const struct bkey_packed *k,
+ bool interior_node)
+{
+ int cmp = bkey_cmp_left_packed(b, k, &iter->pos);
+
+ if (cmp)
+ return cmp;
+ if (bkey_deleted(k))
+ return -1;
+
+ /*
+ * Normally, for extents we want the first key strictly greater than
+ * the iterator position - with the exception that for interior nodes,
+ * we don't want to advance past the last key if the iterator position
+ * is POS_MAX:
+ */
+ if (iter->flags & BTREE_ITER_IS_EXTENTS &&
+ (!interior_node ||
+ bkey_cmp_left_packed_byval(b, k, POS_MAX)))
+ return -1;
+ return 1;
+}
+
+static inline int btree_iter_pos_cmp(struct btree_iter *iter,
+ const struct btree *b,
+ const struct bkey_packed *k)
+{
+ return __btree_iter_pos_cmp(iter, b, k, b->level != 0);
+}
+
/* Btree node locking: */
/*
/* Btree iterator locking: */
#ifdef CONFIG_BCACHEFS_DEBUG
-void bch2_btree_iter_verify_locks(struct btree_iter *iter)
+void __bch2_btree_iter_verify_locks(struct btree_iter *iter)
{
unsigned l;
+ BUG_ON((iter->flags & BTREE_ITER_NOUNLOCK) &&
+ !btree_node_locked(iter, 0));
+
for (l = 0; btree_iter_node(iter, l); l++) {
if (iter->uptodate >= BTREE_ITER_NEED_RELOCK &&
!btree_node_locked(iter, l))
btree_node_locked_type(iter, l));
}
}
+
+void bch2_btree_iter_verify_locks(struct btree_iter *iter)
+{
+ struct btree_iter *linked;
+
+ for_each_btree_iter(iter, linked)
+ __bch2_btree_iter_verify_locks(linked);
+
+}
#endif
__flatten
break;
}
}
-
- bch2_btree_iter_verify_locks(linked);
}
+
+ bch2_btree_iter_verify_locks(iter);
}
int bch2_btree_iter_unlock(struct btree_iter *iter)
* whiteouts)
*/
k = b->level || iter->flags & BTREE_ITER_IS_EXTENTS
- ? bch2_btree_node_iter_prev_filter(&tmp, b, KEY_TYPE_DISCARD)
+ ? bch2_btree_node_iter_prev_filter(&tmp, b, KEY_TYPE_discard)
: bch2_btree_node_iter_prev_all(&tmp, b);
- if (k && btree_iter_pos_cmp_packed(b, &iter->pos, k,
- iter->flags & BTREE_ITER_IS_EXTENTS)) {
+ if (k && btree_iter_pos_cmp(iter, b, k) > 0) {
char buf[100];
struct bkey uk = bkey_unpack_key(b, k);
- bch2_bkey_to_text(buf, sizeof(buf), &uk);
+ bch2_bkey_to_text(&PBUF(buf), &uk);
panic("prev key should be before iter pos:\n%s\n%llu:%llu\n",
buf, iter->pos.inode, iter->pos.offset);
}
k = bch2_btree_node_iter_peek_all(&l->iter, b);
- if (k && !btree_iter_pos_cmp_packed(b, &iter->pos, k,
- iter->flags & BTREE_ITER_IS_EXTENTS)) {
+ if (k && btree_iter_pos_cmp(iter, b, k) < 0) {
char buf[100];
struct bkey uk = bkey_unpack_key(b, k);
- bch2_bkey_to_text(buf, sizeof(buf), &uk);
+ bch2_bkey_to_text(&PBUF(buf), &uk);
panic("iter should be after current key:\n"
"iter pos %llu:%llu\n"
"cur key %s\n",
/* didn't find the bset in the iterator - might have to readd it: */
if (new_u64s &&
- btree_iter_pos_cmp_packed(b, &iter->pos, where,
- iter->flags & BTREE_ITER_IS_EXTENTS)) {
+ btree_iter_pos_cmp(iter, b, where) > 0) {
btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
bch2_btree_node_iter_push(node_iter, b, where, end);
return;
if (new_u64s &&
- btree_iter_pos_cmp_packed(b, &iter->pos, where,
- iter->flags & BTREE_ITER_IS_EXTENTS)) {
+ btree_iter_pos_cmp(iter, b, where) > 0) {
set->k = offset;
} else if (set->k < offset + clobber_u64s) {
set->k = offset + new_u64s;
btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
bch2_btree_node_iter_sort(node_iter, b);
- if (!b->level && node_iter == &iter->l[0].iter)
+ if (!b->level && node_iter == &iter->l[0].iter) {
+ /*
+ * not legal to call bkey_debugcheck() here, because we're
+ * called midway through the update path after update has been
+ * marked but before deletes have actually happened:
+ */
+#if 0
__btree_iter_peek_all(iter, &iter->l[0], &iter->k);
+#endif
+ struct btree_iter_level *l = &iter->l[0];
+ struct bkey_packed *k =
+ bch2_btree_node_iter_peek_all(&l->iter, l->b);
+
+ if (unlikely(!k))
+ iter->k.type = KEY_TYPE_deleted;
+ else
+ bkey_disassemble(l->b, k, &iter->k);
+ }
iter_current_key_not_modified:
/*
* always point to the key for the child node the btree iterator points
* to.
*/
- if (b->level && new_u64s && !bkey_deleted(where) &&
- btree_iter_pos_cmp_packed(b, &iter->pos, where,
- iter->flags & BTREE_ITER_IS_EXTENTS)) {
+ if (b->level && new_u64s &&
+ btree_iter_pos_cmp(iter, b, where) > 0) {
struct bset_tree *t;
struct bkey_packed *k;
k = bch2_bkey_prev_all(b, t,
bch2_btree_node_iter_bset_pos(node_iter, b, t));
if (k &&
- __btree_node_iter_cmp(b, k, where) > 0) {
+ bkey_iter_cmp(b, k, where) > 0) {
struct btree_node_iter_set *set;
unsigned offset =
__btree_node_key_to_offset(b, bkey_next(k));
* signal to bch2_btree_iter_peek_slot() that we're currently at
* a hole
*/
- u->type = KEY_TYPE_DELETED;
+ u->type = KEY_TYPE_deleted;
return bkey_s_c_null;
}
bch2_btree_node_iter_peek(&l->iter, l->b));
}
-static inline void __btree_iter_advance(struct btree_iter_level *l)
+static inline bool btree_iter_advance_to_pos(struct btree_iter *iter,
+ struct btree_iter_level *l,
+ int max_advance)
{
- bch2_btree_node_iter_advance(&l->iter, l->b);
+ struct bkey_packed *k;
+ int nr_advanced = 0;
+
+ while ((k = bch2_btree_node_iter_peek_all(&l->iter, l->b)) &&
+ btree_iter_pos_cmp(iter, l->b, k) < 0) {
+ if (max_advance > 0 && nr_advanced >= max_advance)
+ return false;
+
+ bch2_btree_node_iter_advance(&l->iter, l->b);
+ nr_advanced++;
+ }
+
+ return true;
}
/*
char buf[100];
struct bkey uk = bkey_unpack_key(b, k);
- bch2_bkey_to_text(buf, sizeof(buf), &uk);
+ bch2_bkey_to_text(&PBUF(buf), &uk);
panic("parent iter doesn't point to new node:\n%s\n%llu:%llu\n",
buf, b->key.k.p.inode, b->key.k.p.offset);
}
static inline bool btree_iter_pos_after_node(struct btree_iter *iter,
struct btree *b)
{
- return !btree_iter_pos_cmp(iter, &b->key.k) &&
- bkey_cmp(b->key.k.p, POS_MAX);
+ return __btree_iter_pos_cmp(iter, NULL,
+ bkey_to_packed(&b->key), true) < 0;
}
static inline bool btree_iter_pos_in_node(struct btree_iter *iter,
}
static inline void __btree_iter_init(struct btree_iter *iter,
- struct btree *b)
+ unsigned level)
{
- struct btree_iter_level *l = &iter->l[b->level];
+ struct btree_iter_level *l = &iter->l[level];
+
+ bch2_btree_node_iter_init(&l->iter, l->b, &iter->pos);
- bch2_btree_node_iter_init(&l->iter, b, iter->pos,
- iter->flags & BTREE_ITER_IS_EXTENTS);
+ if (iter->flags & BTREE_ITER_IS_EXTENTS)
+ btree_iter_advance_to_pos(iter, l, -1);
/* Skip to first non whiteout: */
- if (b->level)
- bch2_btree_node_iter_peek(&l->iter, b);
+ if (level)
+ bch2_btree_node_iter_peek(&l->iter, l->b);
btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
}
iter->l[b->level].lock_seq = b->lock.state.seq;
iter->l[b->level].b = b;
- __btree_iter_init(iter, b);
+ __btree_iter_init(iter, b->level);
}
/*
struct btree_iter *linked;
unsigned level = b->level;
+ /* caller now responsible for unlocking @b */
+
+ BUG_ON(iter->l[level].b != b);
+ BUG_ON(!btree_node_intent_locked(iter, level));
+
+ iter->l[level].b = BTREE_ITER_NOT_END;
+ mark_btree_node_unlocked(iter, level);
+
for_each_btree_iter(iter, linked)
if (linked->l[level].b == b) {
- btree_node_unlock(linked, level);
+ __btree_node_unlock(linked, level);
linked->l[level].b = BTREE_ITER_NOT_END;
}
}
struct btree_iter *linked;
for_each_btree_iter_with_node(iter, b, linked)
- __btree_iter_init(linked, b);
+ __btree_iter_init(linked, b->level);
}
static inline int btree_iter_lock_root(struct btree_iter *iter,
*/
iter->level = depth_want;
iter->l[iter->level].b = NULL;
- return 0;
+ return 1;
}
lock_type = __btree_lock_want(iter, iter->level);
*
* XXX correctly using BTREE_ITER_UPTODATE should make this unnecessary
*/
- if (btree_iter_node(iter, iter->level)) {
- struct btree_iter_level *l = &iter->l[iter->level];
- struct bkey_s_c k;
- struct bkey u;
-
- while ((k = __btree_iter_peek_all(iter, l, &u)).k &&
- !btree_iter_pos_cmp(iter, k.k))
- __btree_iter_advance(l);
- }
+ if (btree_iter_node(iter, iter->level))
+ btree_iter_advance_to_pos(iter, &iter->l[iter->level], -1);
/*
* Note: iter->nodes[iter->level] may be temporarily NULL here - that
? btree_iter_down(iter)
: btree_iter_lock_root(iter, depth_want);
if (unlikely(ret)) {
+ if (ret == 1)
+ return 0;
+
iter->level = depth_want;
iter->l[iter->level].b = BTREE_ITER_NOT_END;
return ret;
void bch2_btree_iter_set_pos_same_leaf(struct btree_iter *iter, struct bpos new_pos)
{
struct btree_iter_level *l = &iter->l[0];
- struct bkey_packed *k;
EBUG_ON(iter->level != 0);
EBUG_ON(bkey_cmp(new_pos, iter->pos) < 0);
iter->pos = new_pos;
btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
- while ((k = bch2_btree_node_iter_peek_all(&l->iter, l->b)) &&
- !btree_iter_pos_cmp_packed(l->b, &iter->pos, k,
- iter->flags & BTREE_ITER_IS_EXTENTS))
- __btree_iter_advance(l);
+ btree_iter_advance_to_pos(iter, l, -1);
- if (!k && btree_iter_pos_after_node(iter, l->b))
+ if (bch2_btree_node_iter_end(&l->iter) &&
+ btree_iter_pos_after_node(iter, l->b))
btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
}
level = btree_iter_up_until_locked(iter, true);
if (btree_iter_node(iter, level)) {
- unsigned nr_advanced = 0;
- struct btree_iter_level *l = &iter->l[level];
- struct bkey_s_c k;
- struct bkey u;
-
/*
* We might have to skip over many keys, or just a few: try
* advancing the node iterator, and if we have to skip over too
* many keys just reinit it (or if we're rewinding, since that
* is expensive).
*/
- if (cmp > 0) {
- while ((k = __btree_iter_peek_all(iter, l, &u)).k &&
- !btree_iter_pos_cmp(iter, k.k)) {
- if (nr_advanced > 8)
- goto reinit_node;
-
- __btree_iter_advance(l);
- nr_advanced++;
- }
- } else {
-reinit_node:
- __btree_iter_init(iter, iter->l[level].b);
- }
+ if (cmp < 0 ||
+ !btree_iter_advance_to_pos(iter, &iter->l[level], 8))
+ __btree_iter_init(iter, level);
/* Don't leave it locked if we're not supposed to: */
if (btree_lock_want(iter, level) == BTREE_NODE_UNLOCKED)
}
do {
- __btree_iter_advance(l);
+ bch2_btree_node_iter_advance(&l->iter, l->b);
p = bch2_btree_node_iter_peek_all(&l->iter, l->b);
if (unlikely(!p))
return bch2_btree_iter_peek_next_leaf(iter);
while ((k = __btree_iter_peek_all(iter, l, &iter->k)).k &&
bkey_deleted(k.k) &&
bkey_cmp(bkey_start_pos(k.k), iter->pos) == 0)
- __btree_iter_advance(l);
+ bch2_btree_node_iter_advance(&l->iter, l->b);
/*
* iterator is now at the correct position for inserting at iter->pos,
: KEY_OFFSET_MAX) -
n.p.offset));
- //EBUG_ON(!n.size);
- if (!n.size) {
- char buf[100];
- bch2_dump_btree_node(iter->l[0].b);
-
- bch2_bkey_to_text(buf, sizeof(buf), k.k);
- panic("iter at %llu:%llu\n"
- "next key %s\n",
- iter->pos.inode,
- iter->pos.offset,
- buf);
- }
+ EBUG_ON(!n.size);
iter->k = n;
iter->uptodate = BTREE_ITER_UPTODATE;
while ((k = __btree_iter_peek_all(iter, l, &iter->k)).k &&
bkey_deleted(k.k) &&
bkey_cmp(k.k->p, iter->pos) == 0)
- __btree_iter_advance(l);
+ bch2_btree_node_iter_advance(&l->iter, l->b);
/*
* If we got to the end of the node, check if we need to traverse to the
}
if (!bkey_deleted(&iter->k))
- __btree_iter_advance(&iter->l[0]);
+ bch2_btree_node_iter_advance(&iter->l[0].iter, iter->l[0].b);
btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
projects / bcachefs-tools-debian / blobdiff