Lines Matching +full:data +full:- +full:path
1 // SPDX-License-Identifier: GPL-2.0
25 #include "sb-members.h"
26 #include "super-io.h"
47 struct bch_fs *c = trans->c; in bch2_btree_node_check_topology()
48 struct bpos node_min = b->key.k.type == KEY_TYPE_btree_ptr_v2 in bch2_btree_node_check_topology()
49 ? bkey_i_to_btree_ptr_v2(&b->key)->v.min_key in bch2_btree_node_check_topology()
50 : b->data->min_key; in bch2_btree_node_check_topology()
57 BUG_ON(b->key.k.type == KEY_TYPE_btree_ptr_v2 && in bch2_btree_node_check_topology()
58 !bpos_eq(bkey_i_to_btree_ptr_v2(&b->key)->v.min_key, in bch2_btree_node_check_topology()
59 b->data->min_key)); in bch2_btree_node_check_topology()
62 bkey_init(&prev.k->k); in bch2_btree_node_check_topology()
66 if (!bpos_eq(b->data->min_key, POS_MIN)) { in bch2_btree_node_check_topology()
68 bch2_bpos_to_text(&buf, b->data->min_key); in bch2_btree_node_check_topology()
74 if (!bpos_eq(b->data->max_key, SPOS_MAX)) { in bch2_btree_node_check_topology()
76 bch2_bpos_to_text(&buf, b->data->max_key); in bch2_btree_node_check_topology()
83 if (!b->c.level) in bch2_btree_node_check_topology()
87 if (k.k->type != KEY_TYPE_btree_ptr_v2) in bch2_btree_node_check_topology()
92 struct bpos expected_min = bkey_deleted(&prev.k->k) in bch2_btree_node_check_topology()
94 : bpos_successor(prev.k->k.p); in bch2_btree_node_check_topology()
96 if (!bpos_eq(expected_min, bp.v->min_key)) { in bch2_btree_node_check_topology()
101 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
103 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
117 if (bkey_deleted(&prev.k->k)) { in bch2_btree_node_check_topology()
122 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
124 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
128 } else if (!bpos_eq(prev.k->k.p, b->key.k.p)) { in bch2_btree_node_check_topology()
133 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
135 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
173 bch2_bkey_format_add_pos(&s, b->data->min_key); in bch2_btree_calc_format()
174 bch2_bkey_format_add_pos(&s, b->data->max_key); in bch2_btree_calc_format()
186 (((int) new_f->key_u64s - old_f->key_u64s) * in btree_node_u64s_with_format()
188 (((int) new_f->key_u64s - BKEY_U64s) * in btree_node_u64s_with_format()
197 * bch2_btree_node_format_fits - check if we could rewrite node with a new format
201 * @nr: number of keys for new node (i.e. b->nr)
204 * Returns: true if all re-packed keys will be able to fit in a new node.
212 size_t u64s = btree_node_u64s_with_format(nr, &b->format, new_f); in bch2_btree_node_format_fits()
221 struct bch_fs *c = trans->c; in __btree_node_free()
229 BUG_ON(b->ob.nr); in __btree_node_free()
230 BUG_ON(!list_empty(&b->write_blocked)); in __btree_node_free()
231 BUG_ON(b->will_make_reachable); in __btree_node_free()
237 struct btree_path *path, in bch2_btree_node_free_inmem() argument
240 struct bch_fs *c = trans->c; in bch2_btree_node_free_inmem()
242 bch2_btree_node_lock_write_nofail(trans, path, &b->c); in bch2_btree_node_free_inmem()
246 mutex_lock(&c->btree_cache.lock); in bch2_btree_node_free_inmem()
247 bch2_btree_node_hash_remove(&c->btree_cache, b); in bch2_btree_node_free_inmem()
248 mutex_unlock(&c->btree_cache.lock); in bch2_btree_node_free_inmem()
250 six_unlock_write(&b->c.lock); in bch2_btree_node_free_inmem()
251 mark_btree_node_locked_noreset(path, b->c.level, BTREE_NODE_INTENT_LOCKED); in bch2_btree_node_free_inmem()
260 struct bch_fs *c = as->c; in bch2_btree_node_free_never_used()
261 struct prealloc_nodes *p = &as->prealloc_nodes[b->c.lock.readers != NULL]; in bch2_btree_node_free_never_used()
263 BUG_ON(!list_empty(&b->write_blocked)); in bch2_btree_node_free_never_used()
264 BUG_ON(b->will_make_reachable != (1UL|(unsigned long) as)); in bch2_btree_node_free_never_used()
266 b->will_make_reachable = 0; in bch2_btree_node_free_never_used()
267 closure_put(&as->cl); in bch2_btree_node_free_never_used()
274 mutex_lock(&c->btree_cache.lock); in bch2_btree_node_free_never_used()
275 __bch2_btree_node_hash_remove(&c->btree_cache, b); in bch2_btree_node_free_never_used()
276 mutex_unlock(&c->btree_cache.lock); in bch2_btree_node_free_never_used()
278 BUG_ON(p->nr >= ARRAY_SIZE(p->b)); in bch2_btree_node_free_never_used()
279 p->b[p->nr++] = b; in bch2_btree_node_free_never_used()
281 six_unlock_intent(&b->c.lock); in bch2_btree_node_free_never_used()
292 struct bch_fs *c = trans->c; in __bch2_btree_node_alloc()
308 BUG_ON(b->ob.nr); in __bch2_btree_node_alloc()
310 mutex_lock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
311 if (c->btree_reserve_cache_nr > nr_reserve) { in __bch2_btree_node_alloc()
313 &c->btree_reserve_cache[--c->btree_reserve_cache_nr]; in __bch2_btree_node_alloc()
315 obs = a->ob; in __bch2_btree_node_alloc()
316 bkey_copy(&tmp.k, &a->k); in __bch2_btree_node_alloc()
317 mutex_unlock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
320 mutex_unlock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
323 c->opts.metadata_target ?: in __bch2_btree_node_alloc()
324 c->opts.foreground_target, in __bch2_btree_node_alloc()
326 writepoint_ptr(&c->btree_write_point), in __bch2_btree_node_alloc()
328 res->nr_replicas, in __bch2_btree_node_alloc()
329 min(res->nr_replicas, in __bch2_btree_node_alloc()
330 c->opts.metadata_replicas_required), in __bch2_btree_node_alloc()
335 if (wp->sectors_free < btree_sectors(c)) { in __bch2_btree_node_alloc()
339 open_bucket_for_each(c, &wp->ptrs, ob, i) in __bch2_btree_node_alloc()
340 if (ob->sectors_free < btree_sectors(c)) in __bch2_btree_node_alloc()
341 ob->sectors_free = 0; in __bch2_btree_node_alloc()
353 bkey_copy(&b->key, &tmp.k); in __bch2_btree_node_alloc()
354 b->ob = obs; in __bch2_btree_node_alloc()
355 six_unlock_write(&b->c.lock); in __bch2_btree_node_alloc()
356 six_unlock_intent(&b->c.lock); in __bch2_btree_node_alloc()
368 struct bch_fs *c = as->c; in bch2_btree_node_alloc()
370 struct prealloc_nodes *p = &as->prealloc_nodes[!!level]; in bch2_btree_node_alloc()
374 BUG_ON(!p->nr); in bch2_btree_node_alloc()
376 b = p->b[--p->nr]; in bch2_btree_node_alloc()
378 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in bch2_btree_node_alloc()
379 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_write); in bch2_btree_node_alloc()
385 bch2_bset_init_first(b, &b->data->keys); in bch2_btree_node_alloc()
386 b->c.level = level; in bch2_btree_node_alloc()
387 b->c.btree_id = as->btree_id; in bch2_btree_node_alloc()
388 b->version_ondisk = c->sb.version; in bch2_btree_node_alloc()
390 memset(&b->nr, 0, sizeof(b->nr)); in bch2_btree_node_alloc()
391 b->data->magic = cpu_to_le64(bset_magic(c)); in bch2_btree_node_alloc()
392 memset(&b->data->_ptr, 0, sizeof(b->data->_ptr)); in bch2_btree_node_alloc()
393 b->data->flags = 0; in bch2_btree_node_alloc()
394 SET_BTREE_NODE_ID(b->data, as->btree_id); in bch2_btree_node_alloc()
395 SET_BTREE_NODE_LEVEL(b->data, level); in bch2_btree_node_alloc()
397 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) { in bch2_btree_node_alloc()
398 struct bkey_i_btree_ptr_v2 *bp = bkey_i_to_btree_ptr_v2(&b->key); in bch2_btree_node_alloc()
400 bp->v.mem_ptr = 0; in bch2_btree_node_alloc()
401 bp->v.seq = b->data->keys.seq; in bch2_btree_node_alloc()
402 bp->v.sectors_written = 0; in bch2_btree_node_alloc()
405 SET_BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data, true); in bch2_btree_node_alloc()
409 ret = bch2_btree_node_hash_insert(&c->btree_cache, b, level, as->btree_id); in bch2_btree_node_alloc()
419 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) in btree_set_min()
420 bkey_i_to_btree_ptr_v2(&b->key)->v.min_key = pos; in btree_set_min()
421 b->data->min_key = pos; in btree_set_min()
426 b->key.k.p = pos; in btree_set_max()
427 b->data->max_key = pos; in btree_set_max()
434 struct btree *n = bch2_btree_node_alloc(as, trans, b->c.level); in bch2_btree_node_alloc_replacement()
438 * The keys might expand with the new format - if they wouldn't fit in in bch2_btree_node_alloc_replacement()
441 if (!bch2_btree_node_format_fits(as->c, b, b->nr, &format)) in bch2_btree_node_alloc_replacement()
442 format = b->format; in bch2_btree_node_alloc_replacement()
444 SET_BTREE_NODE_SEQ(n->data, BTREE_NODE_SEQ(b->data) + 1); in bch2_btree_node_alloc_replacement()
446 btree_set_min(n, b->data->min_key); in bch2_btree_node_alloc_replacement()
447 btree_set_max(n, b->data->max_key); in bch2_btree_node_alloc_replacement()
449 n->data->format = format; in bch2_btree_node_alloc_replacement()
452 bch2_btree_sort_into(as->c, n, b); in bch2_btree_node_alloc_replacement()
465 b->data->format = bch2_btree_calc_format(b); in __btree_root_alloc()
467 btree_node_set_format(b, b->data->format); in __btree_root_alloc()
475 struct bch_fs *c = as->c; in bch2_btree_reserve_put()
478 for (p = as->prealloc_nodes; in bch2_btree_reserve_put()
479 p < as->prealloc_nodes + ARRAY_SIZE(as->prealloc_nodes); in bch2_btree_reserve_put()
481 while (p->nr) { in bch2_btree_reserve_put()
482 struct btree *b = p->b[--p->nr]; in bch2_btree_reserve_put()
484 mutex_lock(&c->btree_reserve_cache_lock); in bch2_btree_reserve_put()
486 if (c->btree_reserve_cache_nr < in bch2_btree_reserve_put()
487 ARRAY_SIZE(c->btree_reserve_cache)) { in bch2_btree_reserve_put()
489 &c->btree_reserve_cache[c->btree_reserve_cache_nr++]; in bch2_btree_reserve_put()
491 a->ob = b->ob; in bch2_btree_reserve_put()
492 b->ob.nr = 0; in bch2_btree_reserve_put()
493 bkey_copy(&a->k, &b->key); in bch2_btree_reserve_put()
495 bch2_open_buckets_put(c, &b->ob); in bch2_btree_reserve_put()
498 mutex_unlock(&c->btree_reserve_cache_lock); in bch2_btree_reserve_put()
500 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in bch2_btree_reserve_put()
501 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_write); in bch2_btree_reserve_put()
529 struct prealloc_nodes *p = as->prealloc_nodes + interior; in bch2_btree_reserve_get()
531 while (p->nr < nr_nodes[interior]) { in bch2_btree_reserve_get()
532 b = __bch2_btree_node_alloc(trans, &as->disk_res, cl, in bch2_btree_reserve_get()
539 p->b[p->nr++] = b; in bch2_btree_reserve_get()
551 struct bch_fs *c = as->c; in bch2_btree_update_free()
553 if (as->took_gc_lock) in bch2_btree_update_free()
554 up_read(&c->gc_lock); in bch2_btree_update_free()
555 as->took_gc_lock = false; in bch2_btree_update_free()
557 bch2_journal_pin_drop(&c->journal, &as->journal); in bch2_btree_update_free()
558 bch2_journal_pin_flush(&c->journal, &as->journal); in bch2_btree_update_free()
559 bch2_disk_reservation_put(c, &as->disk_res); in bch2_btree_update_free()
562 bch2_time_stats_update(&c->times[BCH_TIME_btree_interior_update_total], in bch2_btree_update_free()
563 as->start_time); in bch2_btree_update_free()
565 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_free()
566 list_del(&as->unwritten_list); in bch2_btree_update_free()
567 list_del(&as->list); in bch2_btree_update_free()
569 closure_debug_destroy(&as->cl); in bch2_btree_update_free()
570 mempool_free(as, &c->btree_interior_update_pool); in bch2_btree_update_free()
576 closure_wake_up(&c->btree_interior_update_wait); in bch2_btree_update_free()
578 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_free()
584 struct bkey_i *k = &b->key; in btree_update_add_key()
586 BUG_ON(bch2_keylist_u64s(keys) + k->k.u64s > in btree_update_add_key()
587 ARRAY_SIZE(as->_old_keys)); in btree_update_add_key()
589 bkey_copy(keys->top, k); in btree_update_add_key()
590 bkey_i_to_btree_ptr_v2(keys->top)->v.mem_ptr = b->c.level + 1; in btree_update_add_key()
597 for_each_keylist_key(&as->new_keys, k) in btree_update_new_nodes_marked_sb()
598 if (!bch2_dev_btree_bitmap_marked(as->c, bkey_i_to_s_c(k))) in btree_update_new_nodes_marked_sb()
605 struct bch_fs *c = as->c; in btree_update_new_nodes_mark_sb()
607 mutex_lock(&c->sb_lock); in btree_update_new_nodes_mark_sb()
608 for_each_keylist_key(&as->new_keys, k) in btree_update_new_nodes_mark_sb()
612 mutex_unlock(&c->sb_lock); in btree_update_new_nodes_mark_sb()
622 struct jset_entry *e = bch2_trans_jset_entry_alloc(trans, as->journal_u64s); in btree_update_nodes_written_trans()
627 memcpy(e, as->journal_entries, as->journal_u64s * sizeof(u64)); in btree_update_nodes_written_trans()
629 trans->journal_pin = &as->journal; in btree_update_nodes_written_trans()
631 for_each_keylist_key(&as->old_keys, k) { in btree_update_nodes_written_trans()
632 unsigned level = bkey_i_to_btree_ptr_v2(k)->v.mem_ptr; in btree_update_nodes_written_trans()
634 ret = bch2_key_trigger_old(trans, as->btree_id, level, bkey_i_to_s_c(k), in btree_update_nodes_written_trans()
640 for_each_keylist_key(&as->new_keys, k) { in btree_update_nodes_written_trans()
641 unsigned level = bkey_i_to_btree_ptr_v2(k)->v.mem_ptr; in btree_update_nodes_written_trans()
643 ret = bch2_key_trigger_new(trans, as->btree_id, level, bkey_i_to_s(k), in btree_update_nodes_written_trans()
654 struct bch_fs *c = as->c; in btree_update_nodes_written()
668 ret = bch2_journal_error(&c->journal); in btree_update_nodes_written()
679 for (i = 0; i < as->nr_old_nodes; i++) { in btree_update_nodes_written()
682 b = as->old_nodes[i]; in btree_update_nodes_written()
685 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_read); in btree_update_nodes_written()
686 seq = b->data ? b->data->keys.seq : 0; in btree_update_nodes_written()
687 six_unlock_read(&b->c.lock); in btree_update_nodes_written()
690 if (seq == as->old_nodes_seq[i]) in btree_update_nodes_written()
691 wait_on_bit_io(&b->flags, BTREE_NODE_write_in_flight_inner, in btree_update_nodes_written()
708 ret = commit_do(trans, &as->disk_res, &journal_seq, in btree_update_nodes_written()
716 bch2_fs_fatal_err_on(ret && !bch2_journal_error(&c->journal), c, in btree_update_nodes_written()
724 * It should be, but bch2_path_get_unlocked_mut() -> bch2_path_get() in btree_update_nodes_written()
726 * rarely end up with a locked path besides the one we have here: in btree_update_nodes_written()
733 * to free as->b and calling btree_update_reparent() on us - we'll in btree_update_nodes_written()
736 b = READ_ONCE(as->b); in btree_update_nodes_written()
742 * unblock the write and allow most of the write path to happen in btree_update_nodes_written()
743 * so that shutdown works, but the i->journal_seq mechanism in btree_update_nodes_written()
745 * didn't get a journal sequence number) - instead in btree_update_nodes_written()
751 as->btree_id, b->c.level, b->key.k.p); in btree_update_nodes_written()
752 struct btree_path *path = trans->paths + path_idx; in btree_update_nodes_written() local
753 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in btree_update_nodes_written()
754 mark_btree_node_locked(trans, path, b->c.level, BTREE_NODE_INTENT_LOCKED); in btree_update_nodes_written()
755 path->l[b->c.level].lock_seq = six_lock_seq(&b->c.lock); in btree_update_nodes_written()
756 path->l[b->c.level].b = b; in btree_update_nodes_written()
758 bch2_btree_node_lock_write_nofail(trans, path, &b->c); in btree_update_nodes_written()
760 mutex_lock(&c->btree_interior_update_lock); in btree_update_nodes_written()
762 list_del(&as->write_blocked_list); in btree_update_nodes_written()
763 if (list_empty(&b->write_blocked)) in btree_update_nodes_written()
770 if (as->b == b) { in btree_update_nodes_written()
771 BUG_ON(!b->c.level); in btree_update_nodes_written()
777 last->journal_seq = cpu_to_le64( in btree_update_nodes_written()
779 le64_to_cpu(last->journal_seq))); in btree_update_nodes_written()
792 mutex_unlock(&c->btree_interior_update_lock); in btree_update_nodes_written()
794 mark_btree_node_locked_noreset(path, b->c.level, BTREE_NODE_INTENT_LOCKED); in btree_update_nodes_written()
795 six_unlock_write(&b->c.lock); in btree_update_nodes_written()
798 btree_node_unlock(trans, path, b->c.level); in btree_update_nodes_written()
802 bch2_journal_pin_drop(&c->journal, &as->journal); in btree_update_nodes_written()
804 mutex_lock(&c->btree_interior_update_lock); in btree_update_nodes_written()
805 for (i = 0; i < as->nr_new_nodes; i++) { in btree_update_nodes_written()
806 b = as->new_nodes[i]; in btree_update_nodes_written()
808 BUG_ON(b->will_make_reachable != (unsigned long) as); in btree_update_nodes_written()
809 b->will_make_reachable = 0; in btree_update_nodes_written()
812 mutex_unlock(&c->btree_interior_update_lock); in btree_update_nodes_written()
814 for (i = 0; i < as->nr_new_nodes; i++) { in btree_update_nodes_written()
815 b = as->new_nodes[i]; in btree_update_nodes_written()
817 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_read); in btree_update_nodes_written()
819 six_unlock_read(&b->c.lock); in btree_update_nodes_written()
822 for (i = 0; i < as->nr_open_buckets; i++) in btree_update_nodes_written()
823 bch2_open_bucket_put(c, c->open_buckets + as->open_buckets[i]); in btree_update_nodes_written()
836 mutex_lock(&c->btree_interior_update_lock); in btree_interior_update_work()
837 as = list_first_entry_or_null(&c->btree_interior_updates_unwritten, in btree_interior_update_work()
839 if (as && !as->nodes_written) in btree_interior_update_work()
841 mutex_unlock(&c->btree_interior_update_lock); in btree_interior_update_work()
853 struct bch_fs *c = as->c; in CLOSURE_CALLBACK()
855 mutex_lock(&c->btree_interior_update_lock); in CLOSURE_CALLBACK()
856 as->nodes_written = true; in CLOSURE_CALLBACK()
857 mutex_unlock(&c->btree_interior_update_lock); in CLOSURE_CALLBACK()
859 queue_work(c->btree_interior_update_worker, &c->btree_interior_update_work); in CLOSURE_CALLBACK()
868 struct bch_fs *c = as->c; in btree_update_updated_node()
870 BUG_ON(as->mode != BTREE_UPDATE_none); in btree_update_updated_node()
871 BUG_ON(as->update_level_end < b->c.level); in btree_update_updated_node()
873 BUG_ON(!b->c.level); in btree_update_updated_node()
875 mutex_lock(&c->btree_interior_update_lock); in btree_update_updated_node()
876 list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten); in btree_update_updated_node()
878 as->mode = BTREE_UPDATE_node; in btree_update_updated_node()
879 as->b = b; in btree_update_updated_node()
880 as->update_level_end = b->c.level; in btree_update_updated_node()
883 list_add(&as->write_blocked_list, &b->write_blocked); in btree_update_updated_node()
885 mutex_unlock(&c->btree_interior_update_lock); in btree_update_updated_node()
897 struct bch_fs *c = as->c; in btree_update_reparent()
899 lockdep_assert_held(&c->btree_interior_update_lock); in btree_update_reparent()
901 child->b = NULL; in btree_update_reparent()
902 child->mode = BTREE_UPDATE_update; in btree_update_reparent()
904 bch2_journal_pin_copy(&c->journal, &as->journal, &child->journal, in btree_update_reparent()
910 struct bkey_i *insert = &b->key; in btree_update_updated_root()
911 struct bch_fs *c = as->c; in btree_update_updated_root()
913 BUG_ON(as->mode != BTREE_UPDATE_none); in btree_update_updated_root()
915 BUG_ON(as->journal_u64s + jset_u64s(insert->k.u64s) > in btree_update_updated_root()
916 ARRAY_SIZE(as->journal_entries)); in btree_update_updated_root()
918 as->journal_u64s += in btree_update_updated_root()
919 journal_entry_set((void *) &as->journal_entries[as->journal_u64s], in btree_update_updated_root()
921 b->c.btree_id, b->c.level, in btree_update_updated_root()
922 insert, insert->k.u64s); in btree_update_updated_root()
924 mutex_lock(&c->btree_interior_update_lock); in btree_update_updated_root()
925 list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten); in btree_update_updated_root()
927 as->mode = BTREE_UPDATE_root; in btree_update_updated_root()
928 mutex_unlock(&c->btree_interior_update_lock); in btree_update_updated_root()
937 * Additionally, it sets b->will_make_reachable to prevent any additional writes
945 struct bch_fs *c = as->c; in bch2_btree_update_add_new_node()
947 closure_get(&as->cl); in bch2_btree_update_add_new_node()
949 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_add_new_node()
950 BUG_ON(as->nr_new_nodes >= ARRAY_SIZE(as->new_nodes)); in bch2_btree_update_add_new_node()
951 BUG_ON(b->will_make_reachable); in bch2_btree_update_add_new_node()
953 as->new_nodes[as->nr_new_nodes++] = b; in bch2_btree_update_add_new_node()
954 b->will_make_reachable = 1UL|(unsigned long) as; in bch2_btree_update_add_new_node()
957 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_add_new_node()
959 btree_update_add_key(as, &as->new_keys, b); in bch2_btree_update_add_new_node()
961 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) { in bch2_btree_update_add_new_node()
962 unsigned bytes = vstruct_end(&b->data->keys) - (void *) b->data; in bch2_btree_update_add_new_node()
965 bkey_i_to_btree_ptr_v2(&b->key)->v.sectors_written = in bch2_btree_update_add_new_node()
979 mutex_lock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
981 * When b->will_make_reachable != 0, it owns a ref on as->cl that's in btree_update_drop_new_node()
982 * dropped when it gets written by bch2_btree_complete_write - the in btree_update_drop_new_node()
985 v = xchg(&b->will_make_reachable, 0); in btree_update_drop_new_node()
990 mutex_unlock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
994 for (i = 0; i < as->nr_new_nodes; i++) in btree_update_drop_new_node()
995 if (as->new_nodes[i] == b) in btree_update_drop_new_node()
1000 array_remove_item(as->new_nodes, as->nr_new_nodes, i); in btree_update_drop_new_node()
1001 mutex_unlock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
1004 closure_put(&as->cl); in btree_update_drop_new_node()
1009 while (b->ob.nr) in bch2_btree_update_get_open_buckets()
1010 as->open_buckets[as->nr_open_buckets++] = in bch2_btree_update_get_open_buckets()
1011 b->ob.v[--b->ob.nr]; in bch2_btree_update_get_open_buckets()
1021 * @b is being split/rewritten: it may have pointers to not-yet-written btree
1022 * nodes and thus outstanding btree_updates - redirect @b's
1028 struct bch_fs *c = as->c; in bch2_btree_interior_update_will_free_node()
1037 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_interior_update_will_free_node()
1047 list_for_each_entry_safe(p, n, &b->write_blocked, write_blocked_list) { in bch2_btree_interior_update_will_free_node()
1048 list_del_init(&p->write_blocked_list); in bch2_btree_interior_update_will_free_node()
1055 closure_wake_up(&c->btree_interior_update_wait); in bch2_btree_interior_update_will_free_node()
1063 * Does this node have unwritten data that has a pin on the journal? in bch2_btree_interior_update_will_free_node()
1065 * If so, transfer that pin to the btree_update operation - in bch2_btree_interior_update_will_free_node()
1071 bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, in bch2_btree_interior_update_will_free_node()
1073 bch2_journal_pin_drop(&c->journal, &w->journal); in bch2_btree_interior_update_will_free_node()
1076 bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, in bch2_btree_interior_update_will_free_node()
1078 bch2_journal_pin_drop(&c->journal, &w->journal); in bch2_btree_interior_update_will_free_node()
1080 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_interior_update_will_free_node()
1086 * reachable - now that we've cancelled any pending writes and moved in bch2_btree_interior_update_will_free_node()
1093 btree_update_add_key(as, &as->old_keys, b); in bch2_btree_interior_update_will_free_node()
1095 as->old_nodes[as->nr_old_nodes] = b; in bch2_btree_interior_update_will_free_node()
1096 as->old_nodes_seq[as->nr_old_nodes] = b->data->keys.seq; in bch2_btree_interior_update_will_free_node()
1097 as->nr_old_nodes++; in bch2_btree_interior_update_will_free_node()
1102 struct bch_fs *c = as->c; in bch2_btree_update_done()
1103 u64 start_time = as->start_time; in bch2_btree_update_done()
1105 BUG_ON(as->mode == BTREE_UPDATE_none); in bch2_btree_update_done()
1107 if (as->took_gc_lock) in bch2_btree_update_done()
1108 up_read(&as->c->gc_lock); in bch2_btree_update_done()
1109 as->took_gc_lock = false; in bch2_btree_update_done()
1113 continue_at(&as->cl, btree_update_set_nodes_written, in bch2_btree_update_done()
1114 as->c->btree_interior_update_worker); in bch2_btree_update_done()
1116 bch2_time_stats_update(&c->times[BCH_TIME_btree_interior_update_foreground], in bch2_btree_update_done()
1121 bch2_btree_update_start(struct btree_trans *trans, struct btree_path *path, in bch2_btree_update_start() argument
1124 struct bch_fs *c = trans->c; in bch2_btree_update_start()
1133 u32 restart_count = trans->restart_count; in bch2_btree_update_start()
1135 BUG_ON(!path->should_be_locked); in bch2_btree_update_start()
1146 test_bit(JOURNAL_space_low, &c->journal.flags)) { in bch2_btree_update_start()
1148 return ERR_PTR(-BCH_ERR_journal_reclaim_would_deadlock); in bch2_btree_update_start()
1151 ({ wait_event(c->journal.wait, !test_bit(JOURNAL_space_low, &c->journal.flags)); 0; })); in bch2_btree_update_start()
1160 ret = bch2_btree_path_upgrade(trans, path, level_end + 1); in bch2_btree_update_start()
1164 if (!btree_path_node(path, level_end)) { in bch2_btree_update_start()
1173 * split at prior level - it might have been a merge instead: in bch2_btree_update_start()
1175 if (bch2_btree_node_insert_fits(path->l[level_end].b, in bch2_btree_update_start()
1179 split = path->l[level_end].b->nr.live_u64s > BTREE_SPLIT_THRESHOLD(c); in bch2_btree_update_start()
1182 if (!down_read_trylock(&c->gc_lock)) { in bch2_btree_update_start()
1183 ret = drop_locks_do(trans, (down_read(&c->gc_lock), 0)); in bch2_btree_update_start()
1185 up_read(&c->gc_lock); in bch2_btree_update_start()
1190 as = mempool_alloc(&c->btree_interior_update_pool, GFP_NOFS); in bch2_btree_update_start()
1192 closure_init(&as->cl, NULL); in bch2_btree_update_start()
1193 as->c = c; in bch2_btree_update_start()
1194 as->start_time = start_time; in bch2_btree_update_start()
1195 as->ip_started = _RET_IP_; in bch2_btree_update_start()
1196 as->mode = BTREE_UPDATE_none; in bch2_btree_update_start()
1197 as->flags = flags; in bch2_btree_update_start()
1198 as->took_gc_lock = true; in bch2_btree_update_start()
1199 as->btree_id = path->btree_id; in bch2_btree_update_start()
1200 as->update_level_start = level_start; in bch2_btree_update_start()
1201 as->update_level_end = level_end; in bch2_btree_update_start()
1202 INIT_LIST_HEAD(&as->list); in bch2_btree_update_start()
1203 INIT_LIST_HEAD(&as->unwritten_list); in bch2_btree_update_start()
1204 INIT_LIST_HEAD(&as->write_blocked_list); in bch2_btree_update_start()
1205 bch2_keylist_init(&as->old_keys, as->_old_keys); in bch2_btree_update_start()
1206 bch2_keylist_init(&as->new_keys, as->_new_keys); in bch2_btree_update_start()
1207 bch2_keylist_init(&as->parent_keys, as->inline_keys); in bch2_btree_update_start()
1209 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_start()
1210 list_add_tail(&as->list, &c->btree_interior_update_list); in bch2_btree_update_start()
1211 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_start()
1221 ret = bch2_journal_error(&c->journal); in bch2_btree_update_start()
1225 ret = bch2_disk_reservation_get(c, &as->disk_res, in bch2_btree_update_start()
1227 c->opts.metadata_replicas, in bch2_btree_update_start()
1244 ret = -BCH_ERR_journal_reclaim_would_deadlock; in bch2_btree_update_start()
1259 trace_and_count(c, btree_reserve_get_fail, trans->fn, in bch2_btree_update_start()
1274 ret != -BCH_ERR_journal_reclaim_would_deadlock) in bch2_btree_update_start()
1284 mutex_lock(&c->btree_cache.lock); in bch2_btree_set_root_inmem()
1285 list_del_init(&b->list); in bch2_btree_set_root_inmem()
1286 mutex_unlock(&c->btree_cache.lock); in bch2_btree_set_root_inmem()
1288 mutex_lock(&c->btree_root_lock); in bch2_btree_set_root_inmem()
1289 bch2_btree_id_root(c, b->c.btree_id)->b = b; in bch2_btree_set_root_inmem()
1290 mutex_unlock(&c->btree_root_lock); in bch2_btree_set_root_inmem()
1297 struct btree_path *path, in bch2_btree_set_root() argument
1301 struct bch_fs *c = as->c; in bch2_btree_set_root()
1312 bch2_btree_node_lock_write_nofail(trans, path, &old->c); in bch2_btree_set_root()
1314 int ret = bch2_btree_node_lock_write(trans, path, &old->c); in bch2_btree_set_root()
1330 bch2_btree_node_unlock_write(trans, path, old); in bch2_btree_set_root()
1338 struct btree_path *path, in bch2_insert_fixup_btree_ptr() argument
1343 struct bch_fs *c = as->c; in bch2_insert_fixup_btree_ptr()
1348 BUG_ON(insert->k.type == KEY_TYPE_btree_ptr_v2 && in bch2_insert_fixup_btree_ptr()
1351 if (unlikely(!test_bit(JOURNAL_replay_done, &c->journal.flags))) in bch2_insert_fixup_btree_ptr()
1352 bch2_journal_key_overwritten(c, b->c.btree_id, b->c.level, insert->k.p); in bch2_insert_fixup_btree_ptr()
1356 .level = b->c.level, in bch2_insert_fixup_btree_ptr()
1357 .btree = b->c.btree_id, in bch2_insert_fixup_btree_ptr()
1366 BUG_ON(as->journal_u64s + jset_u64s(insert->k.u64s) > in bch2_insert_fixup_btree_ptr()
1367 ARRAY_SIZE(as->journal_entries)); in bch2_insert_fixup_btree_ptr()
1369 as->journal_u64s += in bch2_insert_fixup_btree_ptr()
1370 journal_entry_set((void *) &as->journal_entries[as->journal_u64s], in bch2_insert_fixup_btree_ptr()
1372 b->c.btree_id, b->c.level, in bch2_insert_fixup_btree_ptr()
1373 insert, insert->k.u64s); in bch2_insert_fixup_btree_ptr()
1376 bkey_iter_pos_cmp(b, k, &insert->k.p) < 0) in bch2_insert_fixup_btree_ptr()
1379 bch2_btree_bset_insert_key(trans, path, b, node_iter, insert); in bch2_insert_fixup_btree_ptr()
1382 old = READ_ONCE(b->flags); in bch2_insert_fixup_btree_ptr()
1389 } while (!try_cmpxchg(&b->flags, &old, new)); in bch2_insert_fixup_btree_ptr()
1397 struct btree_path *path, in bch2_btree_insert_keys_interior() argument
1408 (bkey_cmp_left_packed(b, k, &insert->k.p) >= 0)) in bch2_btree_insert_keys_interior()
1412 insert != keys->top && bpos_le(insert->k.p, b->key.k.p); in bch2_btree_insert_keys_interior()
1414 bch2_insert_fixup_btree_ptr(as, trans, path, b, &node_iter, insert); in bch2_btree_insert_keys_interior()
1419 for (struct bkey_i *k = keys->keys; in bch2_btree_insert_keys_interior()
1422 bch2_bkey_val_to_text(&buf, trans->c, bkey_i_to_s_c(k)); in bch2_btree_insert_keys_interior()
1429 memmove_u64s_down(keys->keys, insert, keys->top_p - insert->_data); in bch2_btree_insert_keys_interior()
1430 keys->top_p -= insert->_data - keys->keys_p; in bch2_btree_insert_keys_interior()
1437 if (bkey_deleted(&k->k) && bpos_eq(k->k.p, pos)) in key_deleted_in_insert()
1459 unsigned u64s, n1_u64s = (b->nr.live_u64s * 3) / 5; in __btree_split_node()
1466 BUG_ON(n[i]->nsets != 1); in __btree_split_node()
1469 out[i] = bsets[i]->start; in __btree_split_node()
1471 SET_BTREE_NODE_SEQ(n[i]->data, BTREE_NODE_SEQ(b->data) + 1); in __btree_split_node()
1482 if (b->c.level && in __btree_split_node()
1484 u64s + k->u64s >= n1_u64s && in __btree_split_node()
1485 (bch2_key_deleted_in_journal(trans, b->c.btree_id, b->c.level, uk.p) || in __btree_split_node()
1487 n1_u64s += k->u64s; in __btree_split_node()
1490 u64s += k->u64s; in __btree_split_node()
1496 nr_keys[i].val_u64s += bkeyp_val_u64s(&b->format, k); in __btree_split_node()
1499 btree_set_min(n[0], b->data->min_key); in __btree_split_node()
1502 btree_set_max(n[1], b->data->max_key); in __btree_split_node()
1505 bch2_bkey_format_add_pos(&format[i], n[i]->data->min_key); in __btree_split_node()
1506 bch2_bkey_format_add_pos(&format[i], n[i]->data->max_key); in __btree_split_node()
1508 n[i]->data->format = bch2_bkey_format_done(&format[i]); in __btree_split_node()
1510 unsigned u64s = nr_keys[i].nr_keys * n[i]->data->format.key_u64s + in __btree_split_node()
1513 n[i]->data->format = b->format; in __btree_split_node()
1515 btree_node_set_format(n[i], n[i]->data->format); in __btree_split_node()
1524 u64s += k->u64s; in __btree_split_node()
1526 if (bch2_bkey_transform(&n[i]->format, out[i], bkey_packed(k) in __btree_split_node()
1527 ? &b->format: &bch2_bkey_format_current, k)) in __btree_split_node()
1528 out[i]->format = KEY_FORMAT_LOCAL_BTREE; in __btree_split_node()
1532 out[i]->needs_whiteout = false; in __btree_split_node()
1534 btree_keys_account_key_add(&n[i]->nr, 0, out[i]); in __btree_split_node()
1539 bsets[i]->u64s = cpu_to_le16((u64 *) out[i] - bsets[i]->_data); in __btree_split_node()
1541 BUG_ON(!bsets[i]->u64s); in __btree_split_node()
1543 set_btree_bset_end(n[i], n[i]->set); in __btree_split_node()
1560 * we do the split (and pick the pivot) - the pivot we pick might be between
1570 struct btree_path *path = trans->paths + path_idx; in btree_split_insert_keys() local
1573 bpos_le(bch2_keylist_front(keys)->k.p, b->data->max_key)) { in btree_split_insert_keys()
1576 bch2_btree_node_iter_init(&node_iter, b, &bch2_keylist_front(keys)->k.p); in btree_split_insert_keys()
1578 bch2_btree_insert_keys_interior(as, trans, path, b, node_iter, keys); in btree_split_insert_keys()
1583 btree_path_idx_t path, struct btree *b, in btree_split() argument
1586 struct bch_fs *c = as->c; in btree_split()
1587 struct btree *parent = btree_node_parent(trans->paths + path, b); in btree_split()
1595 BUG_ON(parent && !btree_node_intent_locked(trans->paths + path, b->c.level + 1)); in btree_split()
1601 if (b->nr.live_u64s > BTREE_SPLIT_THRESHOLD(c)) { in btree_split()
1606 n[0] = n1 = bch2_btree_node_alloc(as, trans, b->c.level); in btree_split()
1607 n[1] = n2 = bch2_btree_node_alloc(as, trans, b->c.level); in btree_split()
1612 btree_split_insert_keys(as, trans, path, n1, keys); in btree_split()
1613 btree_split_insert_keys(as, trans, path, n2, keys); in btree_split()
1622 six_unlock_write(&n2->c.lock); in btree_split()
1623 six_unlock_write(&n1->c.lock); in btree_split()
1625 path1 = bch2_path_get_unlocked_mut(trans, as->btree_id, n1->c.level, n1->key.k.p); in btree_split()
1626 six_lock_increment(&n1->c.lock, SIX_LOCK_intent); in btree_split()
1627 mark_btree_node_locked(trans, trans->paths + path1, n1->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1628 bch2_btree_path_level_init(trans, trans->paths + path1, n1); in btree_split()
1630 path2 = bch2_path_get_unlocked_mut(trans, as->btree_id, n2->c.level, n2->key.k.p); in btree_split()
1631 six_lock_increment(&n2->c.lock, SIX_LOCK_intent); in btree_split()
1632 mark_btree_node_locked(trans, trans->paths + path2, n2->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1633 bch2_btree_path_level_init(trans, trans->paths + path2, n2); in btree_split()
1640 bch2_keylist_add(&as->parent_keys, &n1->key); in btree_split()
1641 bch2_keylist_add(&as->parent_keys, &n2->key); in btree_split()
1645 n3 = __btree_root_alloc(as, trans, b->c.level + 1); in btree_split()
1648 six_unlock_write(&n3->c.lock); in btree_split()
1650 trans->paths[path2].locks_want++; in btree_split()
1651 BUG_ON(btree_node_locked(trans->paths + path2, n3->c.level)); in btree_split()
1652 six_lock_increment(&n3->c.lock, SIX_LOCK_intent); in btree_split()
1653 mark_btree_node_locked(trans, trans->paths + path2, n3->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1654 bch2_btree_path_level_init(trans, trans->paths + path2, n3); in btree_split()
1656 n3->sib_u64s[0] = U16_MAX; in btree_split()
1657 n3->sib_u64s[1] = U16_MAX; in btree_split()
1659 btree_split_insert_keys(as, trans, path, n3, &as->parent_keys); in btree_split()
1667 btree_split_insert_keys(as, trans, path, n1, keys); in btree_split()
1673 six_unlock_write(&n1->c.lock); in btree_split()
1675 path1 = bch2_path_get_unlocked_mut(trans, as->btree_id, n1->c.level, n1->key.k.p); in btree_split()
1676 six_lock_increment(&n1->c.lock, SIX_LOCK_intent); in btree_split()
1677 mark_btree_node_locked(trans, trans->paths + path1, n1->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1678 bch2_btree_path_level_init(trans, trans->paths + path1, n1); in btree_split()
1681 bch2_keylist_add(&as->parent_keys, &n1->key); in btree_split()
1688 ret = bch2_btree_insert_node(as, trans, path, parent, &as->parent_keys); in btree_split()
1690 ret = bch2_btree_set_root(as, trans, trans->paths + path, n3, false); in btree_split()
1693 ret = bch2_btree_set_root(as, trans, trans->paths + path, n1, false); in btree_split()
1714 * nodes - else another thread could re-acquire a read lock on the old in btree_split()
1716 * seeing stale data: in btree_split()
1718 bch2_btree_node_free_inmem(trans, trans->paths + path, b); in btree_split()
1721 bch2_trans_node_add(trans, trans->paths + path, n3); in btree_split()
1723 bch2_trans_node_add(trans, trans->paths + path2, n2); in btree_split()
1724 bch2_trans_node_add(trans, trans->paths + path1, n1); in btree_split()
1727 six_unlock_intent(&n3->c.lock); in btree_split()
1729 six_unlock_intent(&n2->c.lock); in btree_split()
1730 six_unlock_intent(&n1->c.lock); in btree_split()
1733 __bch2_btree_path_unlock(trans, trans->paths + path2); in btree_split()
1737 __bch2_btree_path_unlock(trans, trans->paths + path1); in btree_split()
1743 bch2_time_stats_update(&c->times[n2 in btree_split()
1758 * bch2_btree_insert_node - insert bkeys into a given btree node
1762 * @path_idx: path that points to current node
1770 * for leaf nodes -- inserts into interior nodes have to be atomic.
1776 struct bch_fs *c = as->c; in bch2_btree_insert_node()
1777 struct btree_path *path = trans->paths + path_idx, *linked; in bch2_btree_insert_node() local
1779 int old_u64s = le16_to_cpu(btree_bset_last(b)->u64s); in bch2_btree_insert_node()
1780 int old_live_u64s = b->nr.live_u64s; in bch2_btree_insert_node()
1784 lockdep_assert_held(&c->gc_lock); in bch2_btree_insert_node()
1785 BUG_ON(!btree_node_intent_locked(path, b->c.level)); in bch2_btree_insert_node()
1786 BUG_ON(!b->c.level); in bch2_btree_insert_node()
1787 BUG_ON(!as || as->b); in bch2_btree_insert_node()
1790 ret = bch2_btree_node_lock_write(trans, path, &b->c); in bch2_btree_insert_node()
1794 bch2_btree_node_prep_for_write(trans, path, b); in bch2_btree_insert_node()
1797 bch2_btree_node_unlock_write(trans, path, b); in bch2_btree_insert_node()
1803 bch2_btree_node_unlock_write(trans, path, b); in bch2_btree_insert_node()
1807 bch2_btree_insert_keys_interior(as, trans, path, b, in bch2_btree_insert_node()
1808 path->l[b->c.level].iter, keys); in bch2_btree_insert_node()
1811 bch2_btree_node_iter_peek(&linked->l[b->c.level].iter, b); in bch2_btree_insert_node()
1815 live_u64s_added = (int) b->nr.live_u64s - old_live_u64s; in bch2_btree_insert_node()
1816 u64s_added = (int) le16_to_cpu(btree_bset_last(b)->u64s) - old_u64s; in bch2_btree_insert_node()
1818 if (b->sib_u64s[0] != U16_MAX && live_u64s_added < 0) in bch2_btree_insert_node()
1819 b->sib_u64s[0] = max(0, (int) b->sib_u64s[0] + live_u64s_added); in bch2_btree_insert_node()
1820 if (b->sib_u64s[1] != U16_MAX && live_u64s_added < 0) in bch2_btree_insert_node()
1821 b->sib_u64s[1] = max(0, (int) b->sib_u64s[1] + live_u64s_added); in bch2_btree_insert_node()
1828 bch2_btree_node_unlock_write(trans, path, b); in bch2_btree_insert_node()
1835 if (b->c.level >= as->update_level_end) { in bch2_btree_insert_node()
1844 btree_path_idx_t path, in bch2_btree_split_leaf() argument
1848 struct btree *b = path_l(trans->paths + path)->b; in bch2_btree_split_leaf()
1853 as = bch2_btree_update_start(trans, trans->paths + path, in bch2_btree_split_leaf()
1854 trans->paths[path].level, in bch2_btree_split_leaf()
1859 ret = btree_split(as, trans, path, b, NULL); in bch2_btree_split_leaf()
1867 for (l = trans->paths[path].level + 1; in bch2_btree_split_leaf()
1868 btree_node_intent_locked(&trans->paths[path], l) && !ret; in bch2_btree_split_leaf()
1870 ret = bch2_foreground_maybe_merge(trans, path, l, flags); in bch2_btree_split_leaf()
1878 struct bch_fs *c = as->c; in __btree_increase_depth()
1879 struct btree_path *path = trans->paths + path_idx; in __btree_increase_depth() local
1880 struct btree *n, *b = bch2_btree_id_root(c, path->btree_id)->b; in __btree_increase_depth()
1882 BUG_ON(!btree_node_locked(path, b->c.level)); in __btree_increase_depth()
1884 n = __btree_root_alloc(as, trans, b->c.level + 1); in __btree_increase_depth()
1887 six_unlock_write(&n->c.lock); in __btree_increase_depth()
1889 path->locks_want++; in __btree_increase_depth()
1890 BUG_ON(btree_node_locked(path, n->c.level)); in __btree_increase_depth()
1891 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in __btree_increase_depth()
1892 mark_btree_node_locked(trans, path, n->c.level, BTREE_NODE_INTENT_LOCKED); in __btree_increase_depth()
1893 bch2_btree_path_level_init(trans, path, n); in __btree_increase_depth()
1895 n->sib_u64s[0] = U16_MAX; in __btree_increase_depth()
1896 n->sib_u64s[1] = U16_MAX; in __btree_increase_depth()
1898 bch2_keylist_add(&as->parent_keys, &b->key); in __btree_increase_depth()
1899 btree_split_insert_keys(as, trans, path_idx, n, &as->parent_keys); in __btree_increase_depth()
1901 int ret = bch2_btree_set_root(as, trans, path, n, true); in __btree_increase_depth()
1906 bch2_trans_node_add(trans, path, n); in __btree_increase_depth()
1907 six_unlock_intent(&n->c.lock); in __btree_increase_depth()
1909 mutex_lock(&c->btree_cache.lock); in __btree_increase_depth()
1910 list_add_tail(&b->list, &c->btree_cache.live[btree_node_pinned(b)].list); in __btree_increase_depth()
1911 mutex_unlock(&c->btree_cache.lock); in __btree_increase_depth()
1916 int bch2_btree_increase_depth(struct btree_trans *trans, btree_path_idx_t path, unsigned flags) in bch2_btree_increase_depth() argument
1918 struct bch_fs *c = trans->c; in bch2_btree_increase_depth()
1919 struct btree *b = bch2_btree_id_root(c, trans->paths[path].btree_id)->b; in bch2_btree_increase_depth()
1922 return bch2_btree_split_leaf(trans, path, flags); in bch2_btree_increase_depth()
1925 bch2_btree_update_start(trans, trans->paths + path, b->c.level, true, flags); in bch2_btree_increase_depth()
1929 __btree_increase_depth(as, trans, path); in bch2_btree_increase_depth()
1935 btree_path_idx_t path, in __bch2_foreground_maybe_merge() argument
1940 struct bch_fs *c = trans->c; in __bch2_foreground_maybe_merge()
1948 enum btree_id btree = trans->paths[path].btree_id; in __bch2_foreground_maybe_merge()
1954 BUG_ON(!trans->paths[path].should_be_locked); in __bch2_foreground_maybe_merge()
1955 BUG_ON(!btree_node_locked(&trans->paths[path], level)); in __bch2_foreground_maybe_merge()
1959 * merges and leaving tons of merges for us to do - we really don't need in __bch2_foreground_maybe_merge()
1960 * to be doing merges at all from the interior update path, and if the in __bch2_foreground_maybe_merge()
1961 * interior update path is generating too many new interior updates we in __bch2_foreground_maybe_merge()
1973 b = trans->paths[path].l[level].b; in __bch2_foreground_maybe_merge()
1975 if ((sib == btree_prev_sib && bpos_eq(b->data->min_key, POS_MIN)) || in __bch2_foreground_maybe_merge()
1976 (sib == btree_next_sib && bpos_eq(b->data->max_key, SPOS_MAX))) { in __bch2_foreground_maybe_merge()
1977 b->sib_u64s[sib] = U16_MAX; in __bch2_foreground_maybe_merge()
1982 ? bpos_predecessor(b->data->min_key) in __bch2_foreground_maybe_merge()
1983 : bpos_successor(b->data->max_key); in __bch2_foreground_maybe_merge()
1991 btree_path_set_should_be_locked(trans, trans->paths + sib_path); in __bch2_foreground_maybe_merge()
1993 m = trans->paths[sib_path].l[level].b; in __bch2_foreground_maybe_merge()
1995 if (btree_node_parent(trans->paths + path, b) != in __bch2_foreground_maybe_merge()
1996 btree_node_parent(trans->paths + sib_path, m)) { in __bch2_foreground_maybe_merge()
1997 b->sib_u64s[sib] = U16_MAX; in __bch2_foreground_maybe_merge()
2009 if (!bpos_eq(bpos_successor(prev->data->max_key), next->data->min_key)) { in __bch2_foreground_maybe_merge()
2012 bch2_bpos_to_text(&buf1, prev->data->max_key); in __bch2_foreground_maybe_merge()
2013 bch2_bpos_to_text(&buf2, next->data->min_key); in __bch2_foreground_maybe_merge()
2026 bch2_bkey_format_add_pos(&new_s, prev->data->min_key); in __bch2_foreground_maybe_merge()
2029 bch2_bkey_format_add_pos(&new_s, next->data->max_key); in __bch2_foreground_maybe_merge()
2032 sib_u64s = btree_node_u64s_with_format(b->nr, &b->format, &new_f) + in __bch2_foreground_maybe_merge()
2033 btree_node_u64s_with_format(m->nr, &m->format, &new_f); in __bch2_foreground_maybe_merge()
2036 sib_u64s -= BTREE_FOREGROUND_MERGE_HYSTERESIS(c); in __bch2_foreground_maybe_merge()
2042 sib_u64s = min(sib_u64s, (size_t) U16_MAX - 1); in __bch2_foreground_maybe_merge()
2043 b->sib_u64s[sib] = sib_u64s; in __bch2_foreground_maybe_merge()
2045 if (b->sib_u64s[sib] > c->btree_foreground_merge_threshold) in __bch2_foreground_maybe_merge()
2048 parent = btree_node_parent(trans->paths + path, b); in __bch2_foreground_maybe_merge()
2049 as = bch2_btree_update_start(trans, trans->paths + path, level, false, in __bch2_foreground_maybe_merge()
2057 n = bch2_btree_node_alloc(as, trans, b->c.level); in __bch2_foreground_maybe_merge()
2059 SET_BTREE_NODE_SEQ(n->data, in __bch2_foreground_maybe_merge()
2060 max(BTREE_NODE_SEQ(b->data), in __bch2_foreground_maybe_merge()
2061 BTREE_NODE_SEQ(m->data)) + 1); in __bch2_foreground_maybe_merge()
2063 btree_set_min(n, prev->data->min_key); in __bch2_foreground_maybe_merge()
2064 btree_set_max(n, next->data->max_key); in __bch2_foreground_maybe_merge()
2066 n->data->format = new_f; in __bch2_foreground_maybe_merge()
2074 six_unlock_write(&n->c.lock); in __bch2_foreground_maybe_merge()
2076 new_path = bch2_path_get_unlocked_mut(trans, btree, n->c.level, n->key.k.p); in __bch2_foreground_maybe_merge()
2077 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in __bch2_foreground_maybe_merge()
2078 mark_btree_node_locked(trans, trans->paths + new_path, n->c.level, BTREE_NODE_INTENT_LOCKED); in __bch2_foreground_maybe_merge()
2079 bch2_btree_path_level_init(trans, trans->paths + new_path, n); in __bch2_foreground_maybe_merge()
2082 delete.k.p = prev->key.k.p; in __bch2_foreground_maybe_merge()
2083 bch2_keylist_add(&as->parent_keys, &delete); in __bch2_foreground_maybe_merge()
2084 bch2_keylist_add(&as->parent_keys, &n->key); in __bch2_foreground_maybe_merge()
2088 ret = bch2_btree_insert_node(as, trans, path, parent, &as->parent_keys); in __bch2_foreground_maybe_merge()
2100 bch2_btree_node_free_inmem(trans, trans->paths + path, b); in __bch2_foreground_maybe_merge()
2101 bch2_btree_node_free_inmem(trans, trans->paths + sib_path, m); in __bch2_foreground_maybe_merge()
2103 bch2_trans_node_add(trans, trans->paths + path, n); in __bch2_foreground_maybe_merge()
2107 six_unlock_intent(&n->c.lock); in __bch2_foreground_maybe_merge()
2111 bch2_time_stats_update(&c->times[BCH_TIME_btree_node_merge], start_time); in __bch2_foreground_maybe_merge()
2118 if (ret == -BCH_ERR_journal_reclaim_would_deadlock) in __bch2_foreground_maybe_merge()
2134 struct bch_fs *c = trans->c; in bch2_btree_node_rewrite()
2142 struct btree_path *path = btree_iter_path(trans, iter); in bch2_btree_node_rewrite() local
2143 parent = btree_node_parent(path, b); in bch2_btree_node_rewrite()
2144 as = bch2_btree_update_start(trans, path, b->c.level, false, flags); in bch2_btree_node_rewrite()
2153 six_unlock_write(&n->c.lock); in bch2_btree_node_rewrite()
2155 new_path = bch2_path_get_unlocked_mut(trans, iter->btree_id, n->c.level, n->key.k.p); in bch2_btree_node_rewrite()
2156 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in bch2_btree_node_rewrite()
2157 mark_btree_node_locked(trans, trans->paths + new_path, n->c.level, BTREE_NODE_INTENT_LOCKED); in bch2_btree_node_rewrite()
2158 bch2_btree_path_level_init(trans, trans->paths + new_path, n); in bch2_btree_node_rewrite()
2163 bch2_keylist_add(&as->parent_keys, &n->key); in bch2_btree_node_rewrite()
2164 ret = bch2_btree_insert_node(as, trans, iter->path, parent, &as->parent_keys); in bch2_btree_node_rewrite()
2179 bch2_trans_node_add(trans, trans->paths + iter->path, n); in bch2_btree_node_rewrite()
2180 six_unlock_intent(&n->c.lock); in bch2_btree_node_rewrite()
2208 a->btree_id, a->key.k->k.p, in async_btree_node_rewrite_trans()
2209 BTREE_MAX_DEPTH, a->level, 0); in async_btree_node_rewrite_trans()
2215 bool found = b && btree_ptr_hash_val(&b->key) == btree_ptr_hash_val(a->key.k); in async_btree_node_rewrite_trans()
2218 : -ENOENT; in async_btree_node_rewrite_trans()
2222 if (!ret || ret == -ENOENT) { in async_btree_node_rewrite_trans()
2223 struct bch_fs *c = trans->c; in async_btree_node_rewrite_trans()
2228 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(a->key.k)); in async_btree_node_rewrite_trans()
2231 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(a->key.k)); in async_btree_node_rewrite_trans()
2234 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in async_btree_node_rewrite_trans()
2251 struct bch_fs *c = a->c; in async_btree_node_rewrite_work()
2254 if (ret != -ENOENT) in async_btree_node_rewrite_work()
2257 spin_lock(&c->btree_node_rewrites_lock); in async_btree_node_rewrite_work()
2258 list_del(&a->list); in async_btree_node_rewrite_work()
2259 spin_unlock(&c->btree_node_rewrites_lock); in async_btree_node_rewrite_work()
2261 closure_wake_up(&c->btree_node_rewrites_wait); in async_btree_node_rewrite_work()
2263 bch2_bkey_buf_exit(&a->key, c); in async_btree_node_rewrite_work()
2274 a->c = c; in bch2_btree_node_rewrite_async()
2275 a->btree_id = b->c.btree_id; in bch2_btree_node_rewrite_async()
2276 a->level = b->c.level; in bch2_btree_node_rewrite_async()
2277 INIT_WORK(&a->work, async_btree_node_rewrite_work); in bch2_btree_node_rewrite_async()
2279 bch2_bkey_buf_init(&a->key); in bch2_btree_node_rewrite_async()
2280 bch2_bkey_buf_copy(&a->key, c, &b->key); in bch2_btree_node_rewrite_async()
2284 spin_lock(&c->btree_node_rewrites_lock); in bch2_btree_node_rewrite_async()
2285 if (c->curr_recovery_pass > BCH_RECOVERY_PASS_journal_replay && in bch2_btree_node_rewrite_async()
2287 list_add(&a->list, &c->btree_node_rewrites); in bch2_btree_node_rewrite_async()
2289 } else if (!test_bit(BCH_FS_may_go_rw, &c->flags)) { in bch2_btree_node_rewrite_async()
2290 list_add(&a->list, &c->btree_node_rewrites_pending); in bch2_btree_node_rewrite_async()
2293 spin_unlock(&c->btree_node_rewrites_lock); in bch2_btree_node_rewrite_async()
2296 queue_work(c->btree_node_rewrite_worker, &a->work); in bch2_btree_node_rewrite_async()
2300 bch2_bkey_buf_exit(&a->key, c); in bch2_btree_node_rewrite_async()
2307 closure_wait_event(&c->btree_node_rewrites_wait, in bch2_async_btree_node_rewrites_flush()
2308 list_empty(&c->btree_node_rewrites)); in bch2_async_btree_node_rewrites_flush()
2314 spin_lock(&c->btree_node_rewrites_lock); in bch2_do_pending_node_rewrites()
2316 list_pop_entry(&c->btree_node_rewrites_pending, in bch2_do_pending_node_rewrites()
2319 list_add(&a->list, &c->btree_node_rewrites); in bch2_do_pending_node_rewrites()
2320 spin_unlock(&c->btree_node_rewrites_lock); in bch2_do_pending_node_rewrites()
2326 queue_work(c->btree_node_rewrite_worker, &a->work); in bch2_do_pending_node_rewrites()
2333 spin_lock(&c->btree_node_rewrites_lock); in bch2_free_pending_node_rewrites()
2335 list_pop_entry(&c->btree_node_rewrites_pending, in bch2_free_pending_node_rewrites()
2337 spin_unlock(&c->btree_node_rewrites_lock); in bch2_free_pending_node_rewrites()
2342 bch2_bkey_buf_exit(&a->key, c); in bch2_free_pending_node_rewrites()
2354 struct bch_fs *c = trans->c; in __bch2_btree_node_update_key()
2360 ret = bch2_key_trigger_old(trans, b->c.btree_id, b->c.level + 1, in __bch2_btree_node_update_key()
2361 bkey_i_to_s_c(&b->key), in __bch2_btree_node_update_key()
2363 bch2_key_trigger_new(trans, b->c.btree_id, b->c.level + 1, in __bch2_btree_node_update_key()
2371 bkey_copy(&new_hash->key, new_key); in __bch2_btree_node_update_key()
2372 ret = bch2_btree_node_hash_insert(&c->btree_cache, in __bch2_btree_node_update_key()
2373 new_hash, b->c.level, b->c.btree_id); in __bch2_btree_node_update_key()
2381 iter2.path = bch2_btree_path_make_mut(trans, iter2.path, in __bch2_btree_node_update_key()
2386 BUG_ON(path2->level != b->c.level); in __bch2_btree_node_update_key()
2387 BUG_ON(!bpos_eq(path2->pos, new_key->k.p)); in __bch2_btree_node_update_key()
2391 trans->paths_sorted = false; in __bch2_btree_node_update_key()
2401 jset_u64s(new_key->k.u64s)); in __bch2_btree_node_update_key()
2408 b->c.btree_id, b->c.level, in __bch2_btree_node_update_key()
2409 new_key, new_key->k.u64s); in __bch2_btree_node_update_key()
2416 bch2_btree_node_lock_write_nofail(trans, btree_iter_path(trans, iter), &b->c); in __bch2_btree_node_update_key()
2419 mutex_lock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2420 bch2_btree_node_hash_remove(&c->btree_cache, new_hash); in __bch2_btree_node_update_key()
2422 __bch2_btree_node_hash_remove(&c->btree_cache, b); in __bch2_btree_node_update_key()
2424 bkey_copy(&b->key, new_key); in __bch2_btree_node_update_key()
2425 ret = __bch2_btree_node_hash_insert(&c->btree_cache, b); in __bch2_btree_node_update_key()
2427 mutex_unlock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2429 bkey_copy(&b->key, new_key); in __bch2_btree_node_update_key()
2438 mutex_lock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2439 bch2_btree_node_hash_remove(&c->btree_cache, b); in __bch2_btree_node_update_key()
2440 mutex_unlock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2449 struct bch_fs *c = trans->c; in bch2_btree_node_update_key()
2451 struct btree_path *path = btree_iter_path(trans, iter); in bch2_btree_node_update_key() local
2455 ret = bch2_btree_path_upgrade(trans, path, b->c.level + 1); in bch2_btree_node_update_key()
2465 if (btree_ptr_hash_val(new_key) != b->hash_val) { in bch2_btree_node_update_key()
2479 path->intent_ref++; in bch2_btree_node_update_key()
2482 --path->intent_ref; in bch2_btree_node_update_key()
2499 bch2_trans_node_iter_init(trans, &iter, b->c.btree_id, b->key.k.p, in bch2_btree_node_update_key_get_iter()
2500 BTREE_MAX_DEPTH, b->c.level, in bch2_btree_node_update_key_get_iter()
2507 if (btree_iter_path(trans, &iter)->l[b->c.level].b != b) { in bch2_btree_node_update_key_get_iter()
2516 !bch2_bkey_has_device(bkey_i_to_s(&b->key), ptr->dev)); in bch2_btree_node_update_key_get_iter()
2540 struct bch_fs *c = trans->c; in bch2_btree_root_alloc_fake_trans()
2561 b->c.level = level; in bch2_btree_root_alloc_fake_trans()
2562 b->c.btree_id = id; in bch2_btree_root_alloc_fake_trans()
2564 bkey_btree_ptr_init(&b->key); in bch2_btree_root_alloc_fake_trans()
2565 b->key.k.p = SPOS_MAX; in bch2_btree_root_alloc_fake_trans()
2566 *((u64 *) bkey_i_to_btree_ptr(&b->key)->v.start) = U64_MAX - id; in bch2_btree_root_alloc_fake_trans()
2568 bch2_bset_init_first(b, &b->data->keys); in bch2_btree_root_alloc_fake_trans()
2571 b->data->flags = 0; in bch2_btree_root_alloc_fake_trans()
2574 b->data->format = bch2_btree_calc_format(b); in bch2_btree_root_alloc_fake_trans()
2575 btree_node_set_format(b, b->data->format); in bch2_btree_root_alloc_fake_trans()
2577 ret = bch2_btree_node_hash_insert(&c->btree_cache, b, in bch2_btree_root_alloc_fake_trans()
2578 b->c.level, b->c.btree_id); in bch2_btree_root_alloc_fake_trans()
2583 six_unlock_write(&b->c.lock); in bch2_btree_root_alloc_fake_trans()
2584 six_unlock_intent(&b->c.lock); in bch2_btree_root_alloc_fake_trans()
2595 prt_printf(out, "%ps: ", (void *) as->ip_started); in bch2_btree_update_to_text()
2596 bch2_trans_commit_flags_to_text(out, as->flags); in bch2_btree_update_to_text()
2599 bch2_btree_id_to_text(out, as->btree_id); in bch2_btree_update_to_text()
2600 prt_printf(out, " l=%u-%u mode=%s nodes_written=%u cl.remaining=%u journal_seq=%llu\n", in bch2_btree_update_to_text()
2601 as->update_level_start, in bch2_btree_update_to_text()
2602 as->update_level_end, in bch2_btree_update_to_text()
2603 bch2_btree_update_modes[as->mode], in bch2_btree_update_to_text()
2604 as->nodes_written, in bch2_btree_update_to_text()
2605 closure_nr_remaining(&as->cl), in bch2_btree_update_to_text()
2606 as->journal.seq); in bch2_btree_update_to_text()
2613 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_updates_to_text()
2614 list_for_each_entry(as, &c->btree_interior_update_list, list) in bch2_btree_updates_to_text()
2616 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_updates_to_text()
2623 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_interior_updates_pending()
2624 ret = !list_empty(&c->btree_interior_update_list); in bch2_btree_interior_updates_pending()
2625 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_interior_updates_pending()
2635 closure_wait_event(&c->btree_interior_update_wait, in bch2_btree_interior_updates_flush()
2642 struct btree_root *r = bch2_btree_id_root(c, entry->btree_id); in bch2_journal_entry_to_btree_root()
2644 mutex_lock(&c->btree_root_lock); in bch2_journal_entry_to_btree_root()
2646 r->level = entry->level; in bch2_journal_entry_to_btree_root()
2647 r->alive = true; in bch2_journal_entry_to_btree_root()
2648 bkey_copy(&r->key, (struct bkey_i *) entry->start); in bch2_journal_entry_to_btree_root()
2650 mutex_unlock(&c->btree_root_lock); in bch2_journal_entry_to_btree_root()
2660 mutex_lock(&c->btree_root_lock); in bch2_btree_roots_to_journal_entries()
2665 if (r->alive && !test_bit(i, &skip)) { in bch2_btree_roots_to_journal_entries()
2667 i, r->level, &r->key, r->key.k.u64s); in bch2_btree_roots_to_journal_entries()
2672 mutex_unlock(&c->btree_root_lock); in bch2_btree_roots_to_journal_entries()
2682 bch2_bkey_val_to_text(out, c, bkey_i_to_s_c(&a->k)); in bch2_btree_alloc_to_text()
2687 open_bucket_for_each(c, &a->ob, ob, i) in bch2_btree_alloc_to_text()
2695 for (unsigned i = 0; i < c->btree_reserve_cache_nr; i++) in bch2_btree_reserve_cache_to_text()
2696 bch2_btree_alloc_to_text(out, c, &c->btree_reserve_cache[i]); in bch2_btree_reserve_cache_to_text()
2701 WARN_ON(!list_empty(&c->btree_node_rewrites)); in bch2_fs_btree_interior_update_exit()
2702 WARN_ON(!list_empty(&c->btree_node_rewrites_pending)); in bch2_fs_btree_interior_update_exit()
2704 if (c->btree_node_rewrite_worker) in bch2_fs_btree_interior_update_exit()
2705 destroy_workqueue(c->btree_node_rewrite_worker); in bch2_fs_btree_interior_update_exit()
2706 if (c->btree_interior_update_worker) in bch2_fs_btree_interior_update_exit()
2707 destroy_workqueue(c->btree_interior_update_worker); in bch2_fs_btree_interior_update_exit()
2708 mempool_exit(&c->btree_interior_update_pool); in bch2_fs_btree_interior_update_exit()
2713 mutex_init(&c->btree_reserve_cache_lock); in bch2_fs_btree_interior_update_init_early()
2714 INIT_LIST_HEAD(&c->btree_interior_update_list); in bch2_fs_btree_interior_update_init_early()
2715 INIT_LIST_HEAD(&c->btree_interior_updates_unwritten); in bch2_fs_btree_interior_update_init_early()
2716 mutex_init(&c->btree_interior_update_lock); in bch2_fs_btree_interior_update_init_early()
2717 INIT_WORK(&c->btree_interior_update_work, btree_interior_update_work); in bch2_fs_btree_interior_update_init_early()
2719 INIT_LIST_HEAD(&c->btree_node_rewrites); in bch2_fs_btree_interior_update_init_early()
2720 INIT_LIST_HEAD(&c->btree_node_rewrites_pending); in bch2_fs_btree_interior_update_init_early()
2721 spin_lock_init(&c->btree_node_rewrites_lock); in bch2_fs_btree_interior_update_init_early()
2726 c->btree_interior_update_worker = in bch2_fs_btree_interior_update_init()
2728 if (!c->btree_interior_update_worker) in bch2_fs_btree_interior_update_init()
2729 return -BCH_ERR_ENOMEM_btree_interior_update_worker_init; in bch2_fs_btree_interior_update_init()
2731 c->btree_node_rewrite_worker = in bch2_fs_btree_interior_update_init()
2733 if (!c->btree_node_rewrite_worker) in bch2_fs_btree_interior_update_init()
2734 return -BCH_ERR_ENOMEM_btree_interior_update_worker_init; in bch2_fs_btree_interior_update_init()
2736 if (mempool_init_kmalloc_pool(&c->btree_interior_update_pool, 1, in bch2_fs_btree_interior_update_init()
2738 return -BCH_ERR_ENOMEM_btree_interior_update_pool_init; in bch2_fs_btree_interior_update_init()