-/* Btree node locking: */
-
-void bch2_btree_node_unlock_write(struct btree_trans *trans,
- struct btree_path *path, struct btree *b)
-{
- bch2_btree_node_unlock_write_inlined(trans, path, b);
-}
-
-void __bch2_btree_node_lock_write(struct btree_trans *trans, struct btree *b)
-{
- struct btree_path *linked;
- unsigned readers = 0;
-
- trans_for_each_path(trans, linked)
- if (linked->l[b->c.level].b == b &&
- btree_node_read_locked(linked, b->c.level))
- readers++;
-
- /*
- * Must drop our read locks before calling six_lock_write() -
- * six_unlock() won't do wakeups until the reader count
- * goes to 0, and it's safe because we have the node intent
- * locked:
- */
- if (!b->c.lock.readers)
- atomic64_sub(__SIX_VAL(read_lock, readers),
- &b->c.lock.state.counter);
- else
- this_cpu_sub(*b->c.lock.readers, readers);
-
- six_lock_write(&b->c.lock, NULL, NULL);
-
- if (!b->c.lock.readers)
- atomic64_add(__SIX_VAL(read_lock, readers),
- &b->c.lock.state.counter);
- else
- this_cpu_add(*b->c.lock.readers, readers);
-}
-
-bool __bch2_btree_node_relock(struct btree_trans *trans,
- struct btree_path *path, unsigned level)
-{
- struct btree *b = btree_path_node(path, level);
- int want = __btree_lock_want(path, level);
-
- if (!is_btree_node(path, level))
- goto fail;
-
- if (race_fault())
- goto fail;
-
- if (six_relock_type(&b->c.lock, want, path->l[level].lock_seq) ||
- (btree_node_lock_seq_matches(path, b, level) &&
- btree_node_lock_increment(trans, b, level, want))) {
- mark_btree_node_locked(trans, path, level, want);
- return true;
- }
-fail:
- trace_btree_node_relock_fail(trans->fn, _RET_IP_,
- path->btree_id,
- &path->pos,
- (unsigned long) b,
- path->l[level].lock_seq,
- is_btree_node(path, level) ? b->c.lock.state.seq : 0);
- return false;
-}
-
-bool bch2_btree_node_upgrade(struct btree_trans *trans,
- struct btree_path *path, unsigned level)
-{
- struct btree *b = path->l[level].b;
-
- if (!is_btree_node(path, level))
- return false;
-
- switch (btree_lock_want(path, level)) {
- case BTREE_NODE_UNLOCKED:
- BUG_ON(btree_node_locked(path, level));
- return true;
- case BTREE_NODE_READ_LOCKED:
- BUG_ON(btree_node_intent_locked(path, level));
- return bch2_btree_node_relock(trans, path, level);
- case BTREE_NODE_INTENT_LOCKED:
- break;
- }
-
- if (btree_node_intent_locked(path, level))
- return true;
-
- if (race_fault())
- return false;
-
- if (btree_node_locked(path, level)
- ? six_lock_tryupgrade(&b->c.lock)
- : six_relock_type(&b->c.lock, SIX_LOCK_intent, path->l[level].lock_seq))
- goto success;
-
- if (btree_node_lock_seq_matches(path, b, level) &&
- btree_node_lock_increment(trans, b, level, BTREE_NODE_INTENT_LOCKED)) {
- btree_node_unlock(path, level);
- goto success;
- }
-
- return false;
-success:
- mark_btree_node_intent_locked(trans, path, level);
- return true;
-}
-
-static inline bool btree_path_get_locks(struct btree_trans *trans,
- struct btree_path *path,
- bool upgrade)
-{
- unsigned l = path->level;
- int fail_idx = -1;
-
- do {
- if (!btree_path_node(path, l))
- break;
-
- if (!(upgrade
- ? bch2_btree_node_upgrade(trans, path, l)
- : bch2_btree_node_relock(trans, path, l)))
- fail_idx = l;
-
- l++;
- } while (l < path->locks_want);
-
- /*
- * When we fail to get a lock, we have to ensure that any child nodes
- * can't be relocked so bch2_btree_path_traverse has to walk back up to
- * the node that we failed to relock:
- */
- if (fail_idx >= 0) {
- __bch2_btree_path_unlock(path);
- btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
-
- do {
- path->l[fail_idx].b = BTREE_ITER_NO_NODE_GET_LOCKS;
- --fail_idx;
- } while (fail_idx >= 0);
- }
-
- if (path->uptodate == BTREE_ITER_NEED_RELOCK)
- path->uptodate = BTREE_ITER_UPTODATE;
-
- bch2_trans_verify_locks(trans);
-
- return path->uptodate < BTREE_ITER_NEED_RELOCK;
-}
-
-static struct bpos btree_node_pos(struct btree_bkey_cached_common *_b,
- bool cached)
-{
- return !cached
- ? container_of(_b, struct btree, c)->key.k.p
- : container_of(_b, struct bkey_cached, c)->key.pos;
-}
-
-/* Slowpath: */
-bool __bch2_btree_node_lock(struct btree_trans *trans,
- struct btree_path *path,
- struct btree *b,
- struct bpos pos, unsigned level,
- enum six_lock_type type,
- six_lock_should_sleep_fn should_sleep_fn, void *p,
- unsigned long ip)
-{
- struct btree_path *linked;
- unsigned reason;
-
- /* Check if it's safe to block: */
- trans_for_each_path(trans, linked) {
- if (!linked->nodes_locked)
- continue;
-
- /*
- * Can't block taking an intent lock if we have _any_ nodes read
- * locked:
- *
- * - Our read lock blocks another thread with an intent lock on
- * the same node from getting a write lock, and thus from
- * dropping its intent lock
- *
- * - And the other thread may have multiple nodes intent locked:
- * both the node we want to intent lock, and the node we
- * already have read locked - deadlock:
- */
- if (type == SIX_LOCK_intent &&
- linked->nodes_locked != linked->nodes_intent_locked) {
- reason = 1;
- goto deadlock;
- }
-
- if (linked->btree_id != path->btree_id) {
- if (linked->btree_id < path->btree_id)
- continue;
-
- reason = 3;
- goto deadlock;
- }
-
- /*
- * Within the same btree, non-cached paths come before cached
- * paths:
- */
- if (linked->cached != path->cached) {
- if (!linked->cached)
- continue;
-
- reason = 4;
- goto deadlock;
- }
-
- /*
- * Interior nodes must be locked before their descendants: if
- * another path has possible descendants locked of the node
- * we're about to lock, it must have the ancestors locked too:
- */
- if (level > __fls(linked->nodes_locked)) {
- reason = 5;
- goto deadlock;
- }
-
- /* Must lock btree nodes in key order: */
- if (btree_node_locked(linked, level) &&
- bpos_cmp(pos, btree_node_pos((void *) linked->l[level].b,
- linked->cached)) <= 0) {
- BUG_ON(trans->in_traverse_all);
- reason = 7;
- goto deadlock;
- }
- }
-
- return btree_node_lock_type(trans, path, b, pos, level,
- type, should_sleep_fn, p);
-deadlock:
- trace_trans_restart_would_deadlock(trans->fn, ip,
- trans->in_traverse_all, reason,
- linked->btree_id,
- linked->cached,
- &linked->pos,
- path->btree_id,
- path->cached,
- &pos);
- btree_trans_restart(trans);
- return false;
-}
-
-/* Btree iterator locking: */
-
-#ifdef CONFIG_BCACHEFS_DEBUG
-
-static void bch2_btree_path_verify_locks(struct btree_path *path)
-{
- unsigned l;
-
- if (!path->nodes_locked) {
- BUG_ON(path->uptodate == BTREE_ITER_UPTODATE &&
- btree_path_node(path, path->level));
- return;
- }
-
- for (l = 0; btree_path_node(path, l); l++)
- BUG_ON(btree_lock_want(path, l) !=
- btree_node_locked_type(path, l));
-}
-
-void bch2_trans_verify_locks(struct btree_trans *trans)
-{
- struct btree_path *path;
-
- trans_for_each_path(trans, path)
- bch2_btree_path_verify_locks(path);
-}
-#else
-static inline void bch2_btree_path_verify_locks(struct btree_path *path) {}
-#endif
-
-/* Btree path locking: */
-
-/*
- * Only for btree_cache.c - only relocks intent locks
- */
-bool bch2_btree_path_relock_intent(struct btree_trans *trans,
- struct btree_path *path)
-{
- unsigned l;
-
- for (l = path->level;
- l < path->locks_want && btree_path_node(path, l);
- l++) {
- if (!bch2_btree_node_relock(trans, path, l)) {
- __bch2_btree_path_unlock(path);
- btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
- trace_trans_restart_relock_path_intent(trans->fn, _RET_IP_,
- path->btree_id, &path->pos);
- btree_trans_restart(trans);
- return false;
- }
- }
-
- return true;
-}
-
-__flatten
-static bool bch2_btree_path_relock(struct btree_trans *trans,
- struct btree_path *path, unsigned long trace_ip)
-{
- bool ret = btree_path_get_locks(trans, path, false);
-
- if (!ret) {
- trace_trans_restart_relock_path(trans->fn, trace_ip,
- path->btree_id, &path->pos);
- btree_trans_restart(trans);
- }
- return ret;
-}
-
-bool __bch2_btree_path_upgrade(struct btree_trans *trans,
- struct btree_path *path,
- unsigned new_locks_want)
-{
- struct btree_path *linked;
-
- EBUG_ON(path->locks_want >= new_locks_want);
-
- path->locks_want = new_locks_want;
-
- if (btree_path_get_locks(trans, path, true))
- return true;
-
- /*
- * XXX: this is ugly - we'd prefer to not be mucking with other
- * iterators in the btree_trans here.
- *
- * On failure to upgrade the iterator, setting iter->locks_want and
- * calling get_locks() is sufficient to make bch2_btree_path_traverse()
- * get the locks we want on transaction restart.
- *
- * But if this iterator was a clone, on transaction restart what we did
- * to this iterator isn't going to be preserved.
- *
- * Possibly we could add an iterator field for the parent iterator when
- * an iterator is a copy - for now, we'll just upgrade any other
- * iterators with the same btree id.
- *
- * The code below used to be needed to ensure ancestor nodes get locked
- * before interior nodes - now that's handled by
- * bch2_btree_path_traverse_all().
- */
- if (!path->cached && !trans->in_traverse_all)
- trans_for_each_path(trans, linked)
- if (linked != path &&
- linked->cached == path->cached &&
- linked->btree_id == path->btree_id &&
- linked->locks_want < new_locks_want) {
- linked->locks_want = new_locks_want;
- btree_path_get_locks(trans, linked, true);
- }
-
- return false;
-}
-
-void __bch2_btree_path_downgrade(struct btree_path *path,
- unsigned new_locks_want)
-{
- unsigned l;
-
- EBUG_ON(path->locks_want < new_locks_want);
-
- path->locks_want = new_locks_want;
-
- while (path->nodes_locked &&
- (l = __fls(path->nodes_locked)) >= path->locks_want) {
- if (l > path->level) {
- btree_node_unlock(path, l);
- } else {
- if (btree_node_intent_locked(path, l)) {
- six_lock_downgrade(&path->l[l].b->c.lock);
- path->nodes_intent_locked ^= 1 << l;
- }
- break;
- }
- }
-
- bch2_btree_path_verify_locks(path);
-}
-
-void bch2_trans_downgrade(struct btree_trans *trans)
-{
- struct btree_path *path;
-
- trans_for_each_path(trans, path)
- bch2_btree_path_downgrade(path);
-}
-
-/* Btree transaction locking: */
-
-bool bch2_trans_relock(struct btree_trans *trans)
-{
- struct btree_path *path;
-
- if (unlikely(trans->restarted))
- return false;
-
- trans_for_each_path(trans, path)
- if (path->should_be_locked &&
- !bch2_btree_path_relock(trans, path, _RET_IP_)) {
- trace_trans_restart_relock(trans->fn, _RET_IP_,
- path->btree_id, &path->pos);
- BUG_ON(!trans->restarted);
- return false;
- }
- return true;
-}
-
-void bch2_trans_unlock(struct btree_trans *trans)
-{
- struct btree_path *path;
-
- trans_for_each_path(trans, path)
- __bch2_btree_path_unlock(path);
-
- /*
- * bch2_gc_btree_init_recurse() doesn't use btree iterators for walking
- * btree nodes, it implements its own walking:
- */
- BUG_ON(!trans->is_initial_gc &&
- lock_class_is_held(&bch2_btree_node_lock_key));
-}
-