Lines Matching +full:never +full:- +full:post +full:- +full:merge +full:- +full:rules
1 // SPDX-License-Identifier: GPL-2.0
25 #include "sb-members.h"
26 #include "super-io.h"
49 struct bch_fs *c = trans->c; in bch2_btree_node_check_topology()
50 struct bpos node_min = b->key.k.type == KEY_TYPE_btree_ptr_v2 in bch2_btree_node_check_topology()
51 ? bkey_i_to_btree_ptr_v2(&b->key)->v.min_key in bch2_btree_node_check_topology()
52 : b->data->min_key; in bch2_btree_node_check_topology()
61 BUG_ON(b->key.k.type == KEY_TYPE_btree_ptr_v2 && in bch2_btree_node_check_topology()
62 !bpos_eq(bkey_i_to_btree_ptr_v2(&b->key)->v.min_key, in bch2_btree_node_check_topology()
63 b->data->min_key)); in bch2_btree_node_check_topology()
66 bkey_init(&prev.k->k); in bch2_btree_node_check_topology()
70 if (!bpos_eq(b->data->min_key, POS_MIN)) { in bch2_btree_node_check_topology()
73 bch2_bpos_to_text(&buf, b->data->min_key); in bch2_btree_node_check_topology()
79 if (!bpos_eq(b->data->max_key, SPOS_MAX)) { in bch2_btree_node_check_topology()
81 bch2_bpos_to_text(&buf, b->data->max_key); in bch2_btree_node_check_topology()
88 if (!b->c.level) in bch2_btree_node_check_topology()
92 if (k.k->type != KEY_TYPE_btree_ptr_v2) in bch2_btree_node_check_topology()
97 struct bpos expected_min = bkey_deleted(&prev.k->k) in bch2_btree_node_check_topology()
99 : bpos_successor(prev.k->k.p); in bch2_btree_node_check_topology()
101 if (!bpos_eq(expected_min, bp.v->min_key)) { in bch2_btree_node_check_topology()
105 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
107 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
121 if (bkey_deleted(&prev.k->k)) { in bch2_btree_node_check_topology()
125 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
127 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
130 } else if (!bpos_eq(prev.k->k.p, b->key.k.p)) { in bch2_btree_node_check_topology()
134 bch2_btree_id_level_to_text(&buf, b->c.btree_id, b->c.level); in bch2_btree_node_check_topology()
136 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&b->key)); in bch2_btree_node_check_topology()
170 bch2_bkey_format_add_pos(&s, b->data->min_key); in bch2_btree_calc_format()
171 bch2_bkey_format_add_pos(&s, b->data->max_key); in bch2_btree_calc_format()
181 /* stupid integer promotion rules */ in btree_node_u64s_with_format()
183 (((int) new_f->key_u64s - old_f->key_u64s) * in btree_node_u64s_with_format()
185 (((int) new_f->key_u64s - BKEY_U64s) * in btree_node_u64s_with_format()
194 * bch2_btree_node_format_fits - check if we could rewrite node with a new format
198 * @nr: number of keys for new node (i.e. b->nr)
201 * Returns: true if all re-packed keys will be able to fit in a new node.
209 size_t u64s = btree_node_u64s_with_format(nr, &b->format, new_f); in bch2_btree_node_format_fits()
218 struct bch_fs *c = trans->c; in __btree_node_free()
226 BUG_ON(b->ob.nr); in __btree_node_free()
227 BUG_ON(!list_empty(&b->write_blocked)); in __btree_node_free()
228 BUG_ON(b->will_make_reachable); in __btree_node_free()
237 struct bch_fs *c = trans->c; in bch2_btree_node_free_inmem()
239 bch2_btree_node_lock_write_nofail(trans, path, &b->c); in bch2_btree_node_free_inmem()
243 mutex_lock(&c->btree_cache.lock); in bch2_btree_node_free_inmem()
244 bch2_btree_node_hash_remove(&c->btree_cache, b); in bch2_btree_node_free_inmem()
245 mutex_unlock(&c->btree_cache.lock); in bch2_btree_node_free_inmem()
247 six_unlock_write(&b->c.lock); in bch2_btree_node_free_inmem()
248 mark_btree_node_locked_noreset(path, b->c.level, BTREE_NODE_INTENT_LOCKED); in bch2_btree_node_free_inmem()
257 struct bch_fs *c = as->c; in bch2_btree_node_free_never_used()
258 struct prealloc_nodes *p = &as->prealloc_nodes[b->c.lock.readers != NULL]; in bch2_btree_node_free_never_used()
260 BUG_ON(!list_empty(&b->write_blocked)); in bch2_btree_node_free_never_used()
261 BUG_ON(b->will_make_reachable != (1UL|(unsigned long) as)); in bch2_btree_node_free_never_used()
263 b->will_make_reachable = 0; in bch2_btree_node_free_never_used()
264 closure_put(&as->cl); in bch2_btree_node_free_never_used()
271 mutex_lock(&c->btree_cache.lock); in bch2_btree_node_free_never_used()
272 __bch2_btree_node_hash_remove(&c->btree_cache, b); in bch2_btree_node_free_never_used()
273 mutex_unlock(&c->btree_cache.lock); in bch2_btree_node_free_never_used()
275 BUG_ON(p->nr >= ARRAY_SIZE(p->b)); in bch2_btree_node_free_never_used()
276 p->b[p->nr++] = b; in bch2_btree_node_free_never_used()
278 six_unlock_intent(&b->c.lock); in bch2_btree_node_free_never_used()
289 struct bch_fs *c = trans->c; in __bch2_btree_node_alloc()
305 BUG_ON(b->ob.nr); in __bch2_btree_node_alloc()
307 mutex_lock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
308 if (c->btree_reserve_cache_nr > nr_reserve) { in __bch2_btree_node_alloc()
310 &c->btree_reserve_cache[--c->btree_reserve_cache_nr]; in __bch2_btree_node_alloc()
312 obs = a->ob; in __bch2_btree_node_alloc()
313 bkey_copy(&tmp.k, &a->k); in __bch2_btree_node_alloc()
314 mutex_unlock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
317 mutex_unlock(&c->btree_reserve_cache_lock); in __bch2_btree_node_alloc()
320 c->opts.metadata_target ?: in __bch2_btree_node_alloc()
321 c->opts.foreground_target, in __bch2_btree_node_alloc()
323 writepoint_ptr(&c->btree_write_point), in __bch2_btree_node_alloc()
325 res->nr_replicas, in __bch2_btree_node_alloc()
326 min(res->nr_replicas, in __bch2_btree_node_alloc()
327 c->opts.metadata_replicas_required), in __bch2_btree_node_alloc()
332 if (wp->sectors_free < btree_sectors(c)) { in __bch2_btree_node_alloc()
336 open_bucket_for_each(c, &wp->ptrs, ob, i) in __bch2_btree_node_alloc()
337 if (ob->sectors_free < btree_sectors(c)) in __bch2_btree_node_alloc()
338 ob->sectors_free = 0; in __bch2_btree_node_alloc()
350 bkey_copy(&b->key, &tmp.k); in __bch2_btree_node_alloc()
351 b->ob = obs; in __bch2_btree_node_alloc()
352 six_unlock_write(&b->c.lock); in __bch2_btree_node_alloc()
353 six_unlock_intent(&b->c.lock); in __bch2_btree_node_alloc()
365 struct bch_fs *c = as->c; in bch2_btree_node_alloc()
367 struct prealloc_nodes *p = &as->prealloc_nodes[!!level]; in bch2_btree_node_alloc()
371 BUG_ON(!p->nr); in bch2_btree_node_alloc()
373 b = p->b[--p->nr]; in bch2_btree_node_alloc()
375 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in bch2_btree_node_alloc()
376 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_write); in bch2_btree_node_alloc()
382 bch2_bset_init_first(b, &b->data->keys); in bch2_btree_node_alloc()
383 b->c.level = level; in bch2_btree_node_alloc()
384 b->c.btree_id = as->btree_id; in bch2_btree_node_alloc()
385 b->version_ondisk = c->sb.version; in bch2_btree_node_alloc()
387 memset(&b->nr, 0, sizeof(b->nr)); in bch2_btree_node_alloc()
388 b->data->magic = cpu_to_le64(bset_magic(c)); in bch2_btree_node_alloc()
389 memset(&b->data->_ptr, 0, sizeof(b->data->_ptr)); in bch2_btree_node_alloc()
390 b->data->flags = 0; in bch2_btree_node_alloc()
391 SET_BTREE_NODE_ID(b->data, as->btree_id); in bch2_btree_node_alloc()
392 SET_BTREE_NODE_LEVEL(b->data, level); in bch2_btree_node_alloc()
394 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) { in bch2_btree_node_alloc()
395 struct bkey_i_btree_ptr_v2 *bp = bkey_i_to_btree_ptr_v2(&b->key); in bch2_btree_node_alloc()
397 bp->v.mem_ptr = 0; in bch2_btree_node_alloc()
398 bp->v.seq = b->data->keys.seq; in bch2_btree_node_alloc()
399 bp->v.sectors_written = 0; in bch2_btree_node_alloc()
402 SET_BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data, true); in bch2_btree_node_alloc()
406 ret = bch2_btree_node_hash_insert(&c->btree_cache, b, level, as->btree_id); in bch2_btree_node_alloc()
416 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) in btree_set_min()
417 bkey_i_to_btree_ptr_v2(&b->key)->v.min_key = pos; in btree_set_min()
418 b->data->min_key = pos; in btree_set_min()
423 b->key.k.p = pos; in btree_set_max()
424 b->data->max_key = pos; in btree_set_max()
431 struct btree *n = bch2_btree_node_alloc(as, trans, b->c.level); in bch2_btree_node_alloc_replacement()
435 * The keys might expand with the new format - if they wouldn't fit in in bch2_btree_node_alloc_replacement()
438 if (!bch2_btree_node_format_fits(as->c, b, b->nr, &format)) in bch2_btree_node_alloc_replacement()
439 format = b->format; in bch2_btree_node_alloc_replacement()
441 SET_BTREE_NODE_SEQ(n->data, BTREE_NODE_SEQ(b->data) + 1); in bch2_btree_node_alloc_replacement()
443 btree_set_min(n, b->data->min_key); in bch2_btree_node_alloc_replacement()
444 btree_set_max(n, b->data->max_key); in bch2_btree_node_alloc_replacement()
446 n->data->format = format; in bch2_btree_node_alloc_replacement()
449 bch2_btree_sort_into(as->c, n, b); in bch2_btree_node_alloc_replacement()
462 b->data->format = bch2_btree_calc_format(b); in __btree_root_alloc()
464 btree_node_set_format(b, b->data->format); in __btree_root_alloc()
472 struct bch_fs *c = as->c; in bch2_btree_reserve_put()
475 for (p = as->prealloc_nodes; in bch2_btree_reserve_put()
476 p < as->prealloc_nodes + ARRAY_SIZE(as->prealloc_nodes); in bch2_btree_reserve_put()
478 while (p->nr) { in bch2_btree_reserve_put()
479 struct btree *b = p->b[--p->nr]; in bch2_btree_reserve_put()
481 mutex_lock(&c->btree_reserve_cache_lock); in bch2_btree_reserve_put()
483 if (c->btree_reserve_cache_nr < in bch2_btree_reserve_put()
484 ARRAY_SIZE(c->btree_reserve_cache)) { in bch2_btree_reserve_put()
486 &c->btree_reserve_cache[c->btree_reserve_cache_nr++]; in bch2_btree_reserve_put()
488 a->ob = b->ob; in bch2_btree_reserve_put()
489 b->ob.nr = 0; in bch2_btree_reserve_put()
490 bkey_copy(&a->k, &b->key); in bch2_btree_reserve_put()
492 bch2_open_buckets_put(c, &b->ob); in bch2_btree_reserve_put()
495 mutex_unlock(&c->btree_reserve_cache_lock); in bch2_btree_reserve_put()
497 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in bch2_btree_reserve_put()
498 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_write); in bch2_btree_reserve_put()
526 struct prealloc_nodes *p = as->prealloc_nodes + interior; in bch2_btree_reserve_get()
528 while (p->nr < nr_nodes[interior]) { in bch2_btree_reserve_get()
529 b = __bch2_btree_node_alloc(trans, &as->disk_res, cl, in bch2_btree_reserve_get()
536 p->b[p->nr++] = b; in bch2_btree_reserve_get()
548 struct bch_fs *c = as->c; in bch2_btree_update_free()
550 if (as->took_gc_lock) in bch2_btree_update_free()
551 up_read(&c->gc_lock); in bch2_btree_update_free()
552 as->took_gc_lock = false; in bch2_btree_update_free()
554 bch2_journal_pin_drop(&c->journal, &as->journal); in bch2_btree_update_free()
555 bch2_journal_pin_flush(&c->journal, &as->journal); in bch2_btree_update_free()
556 bch2_disk_reservation_put(c, &as->disk_res); in bch2_btree_update_free()
559 bch2_time_stats_update(&c->times[BCH_TIME_btree_interior_update_total], in bch2_btree_update_free()
560 as->start_time); in bch2_btree_update_free()
562 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_free()
563 list_del(&as->unwritten_list); in bch2_btree_update_free()
564 list_del(&as->list); in bch2_btree_update_free()
566 closure_debug_destroy(&as->cl); in bch2_btree_update_free()
567 mempool_free(as, &c->btree_interior_update_pool); in bch2_btree_update_free()
573 closure_wake_up(&c->btree_interior_update_wait); in bch2_btree_update_free()
575 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_free()
581 struct bkey_i *k = &b->key; in btree_update_add_key()
583 BUG_ON(bch2_keylist_u64s(keys) + k->k.u64s > in btree_update_add_key()
584 ARRAY_SIZE(as->_old_keys)); in btree_update_add_key()
586 bkey_copy(keys->top, k); in btree_update_add_key()
587 bkey_i_to_btree_ptr_v2(keys->top)->v.mem_ptr = b->c.level + 1; in btree_update_add_key()
594 for_each_keylist_key(&as->new_keys, k) in btree_update_new_nodes_marked_sb()
595 if (!bch2_dev_btree_bitmap_marked(as->c, bkey_i_to_s_c(k))) in btree_update_new_nodes_marked_sb()
602 struct bch_fs *c = as->c; in btree_update_new_nodes_mark_sb()
604 mutex_lock(&c->sb_lock); in btree_update_new_nodes_mark_sb()
605 for_each_keylist_key(&as->new_keys, k) in btree_update_new_nodes_mark_sb()
609 mutex_unlock(&c->sb_lock); in btree_update_new_nodes_mark_sb()
619 struct jset_entry *e = bch2_trans_jset_entry_alloc(trans, as->journal_u64s); in btree_update_nodes_written_trans()
624 memcpy(e, as->journal_entries, as->journal_u64s * sizeof(u64)); in btree_update_nodes_written_trans()
626 trans->journal_pin = &as->journal; in btree_update_nodes_written_trans()
628 for_each_keylist_key(&as->old_keys, k) { in btree_update_nodes_written_trans()
629 unsigned level = bkey_i_to_btree_ptr_v2(k)->v.mem_ptr; in btree_update_nodes_written_trans()
631 ret = bch2_key_trigger_old(trans, as->btree_id, level, bkey_i_to_s_c(k), in btree_update_nodes_written_trans()
637 for_each_keylist_key(&as->new_keys, k) { in btree_update_nodes_written_trans()
638 unsigned level = bkey_i_to_btree_ptr_v2(k)->v.mem_ptr; in btree_update_nodes_written_trans()
640 ret = bch2_key_trigger_new(trans, as->btree_id, level, bkey_i_to_s(k), in btree_update_nodes_written_trans()
649 /* If the node has been reused, we might be reading uninitialized memory - that's fine: */
652 struct btree_node *b_data = READ_ONCE(b->data); in btree_node_seq_matches()
654 return (b_data ? b_data->keys.seq : 0) == seq; in btree_node_seq_matches()
659 struct bch_fs *c = as->c; in btree_update_nodes_written()
668 * was never written, and we might be trying to free that same btree in btree_update_nodes_written()
673 ret = bch2_journal_error(&c->journal); in btree_update_nodes_written()
684 for (i = 0; i < as->nr_old_nodes; i++) { in btree_update_nodes_written()
685 b = as->old_nodes[i]; in btree_update_nodes_written()
687 if (btree_node_seq_matches(b, as->old_nodes_seq[i])) in btree_update_nodes_written()
688 wait_on_bit_io(&b->flags, BTREE_NODE_write_in_flight_inner, in btree_update_nodes_written()
705 ret = commit_do(trans, &as->disk_res, &journal_seq, in btree_update_nodes_written()
713 bch2_fs_fatal_err_on(ret && !bch2_journal_error(&c->journal), c, in btree_update_nodes_written()
721 * It should be, but bch2_path_get_unlocked_mut() -> bch2_path_get() in btree_update_nodes_written()
730 * to free as->b and calling btree_update_reparent() on us - we'll in btree_update_nodes_written()
733 b = READ_ONCE(as->b); in btree_update_nodes_written()
740 * so that shutdown works, but the i->journal_seq mechanism in btree_update_nodes_written()
742 * didn't get a journal sequence number) - instead in btree_update_nodes_written()
748 as->btree_id, b->c.level, b->key.k.p); in btree_update_nodes_written()
749 struct btree_path *path = trans->paths + path_idx; in btree_update_nodes_written()
750 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_intent); in btree_update_nodes_written()
751 mark_btree_node_locked(trans, path, b->c.level, BTREE_NODE_INTENT_LOCKED); in btree_update_nodes_written()
752 path->l[b->c.level].lock_seq = six_lock_seq(&b->c.lock); in btree_update_nodes_written()
753 path->l[b->c.level].b = b; in btree_update_nodes_written()
755 bch2_btree_node_lock_write_nofail(trans, path, &b->c); in btree_update_nodes_written()
757 mutex_lock(&c->btree_interior_update_lock); in btree_update_nodes_written()
759 list_del(&as->write_blocked_list); in btree_update_nodes_written()
760 if (list_empty(&b->write_blocked)) in btree_update_nodes_written()
767 if (as->b == b) { in btree_update_nodes_written()
768 BUG_ON(!b->c.level); in btree_update_nodes_written()
774 last->journal_seq = cpu_to_le64( in btree_update_nodes_written()
776 le64_to_cpu(last->journal_seq))); in btree_update_nodes_written()
789 mutex_unlock(&c->btree_interior_update_lock); in btree_update_nodes_written()
791 mark_btree_node_locked_noreset(path, b->c.level, BTREE_NODE_INTENT_LOCKED); in btree_update_nodes_written()
792 six_unlock_write(&b->c.lock); in btree_update_nodes_written()
795 btree_node_unlock(trans, path, b->c.level); in btree_update_nodes_written()
799 bch2_journal_pin_drop(&c->journal, &as->journal); in btree_update_nodes_written()
801 mutex_lock(&c->btree_interior_update_lock); in btree_update_nodes_written()
802 for (i = 0; i < as->nr_new_nodes; i++) { in btree_update_nodes_written()
803 b = as->new_nodes[i]; in btree_update_nodes_written()
805 BUG_ON(b->will_make_reachable != (unsigned long) as); in btree_update_nodes_written()
806 b->will_make_reachable = 0; in btree_update_nodes_written()
809 mutex_unlock(&c->btree_interior_update_lock); in btree_update_nodes_written()
811 for (i = 0; i < as->nr_new_nodes; i++) { in btree_update_nodes_written()
812 b = as->new_nodes[i]; in btree_update_nodes_written()
814 btree_node_lock_nopath_nofail(trans, &b->c, SIX_LOCK_read); in btree_update_nodes_written()
816 six_unlock_read(&b->c.lock); in btree_update_nodes_written()
819 for (i = 0; i < as->nr_open_buckets; i++) in btree_update_nodes_written()
820 bch2_open_bucket_put(c, c->open_buckets + as->open_buckets[i]); in btree_update_nodes_written()
833 mutex_lock(&c->btree_interior_update_lock); in btree_interior_update_work()
834 as = list_first_entry_or_null(&c->btree_interior_updates_unwritten, in btree_interior_update_work()
836 if (as && !as->nodes_written) in btree_interior_update_work()
838 mutex_unlock(&c->btree_interior_update_lock); in btree_interior_update_work()
850 struct bch_fs *c = as->c; in CLOSURE_CALLBACK()
852 mutex_lock(&c->btree_interior_update_lock); in CLOSURE_CALLBACK()
853 as->nodes_written = true; in CLOSURE_CALLBACK()
854 mutex_unlock(&c->btree_interior_update_lock); in CLOSURE_CALLBACK()
856 queue_work(c->btree_interior_update_worker, &c->btree_interior_update_work); in CLOSURE_CALLBACK()
865 struct bch_fs *c = as->c; in btree_update_updated_node()
867 BUG_ON(as->mode != BTREE_UPDATE_none); in btree_update_updated_node()
868 BUG_ON(as->update_level_end < b->c.level); in btree_update_updated_node()
870 BUG_ON(!b->c.level); in btree_update_updated_node()
872 mutex_lock(&c->btree_interior_update_lock); in btree_update_updated_node()
873 list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten); in btree_update_updated_node()
875 as->mode = BTREE_UPDATE_node; in btree_update_updated_node()
876 as->b = b; in btree_update_updated_node()
877 as->update_level_end = b->c.level; in btree_update_updated_node()
880 list_add(&as->write_blocked_list, &b->write_blocked); in btree_update_updated_node()
882 mutex_unlock(&c->btree_interior_update_lock); in btree_update_updated_node()
894 struct bch_fs *c = as->c; in btree_update_reparent()
896 lockdep_assert_held(&c->btree_interior_update_lock); in btree_update_reparent()
898 child->b = NULL; in btree_update_reparent()
899 child->mode = BTREE_UPDATE_update; in btree_update_reparent()
901 bch2_journal_pin_copy(&c->journal, &as->journal, &child->journal, in btree_update_reparent()
907 struct bkey_i *insert = &b->key; in btree_update_updated_root()
908 struct bch_fs *c = as->c; in btree_update_updated_root()
910 BUG_ON(as->mode != BTREE_UPDATE_none); in btree_update_updated_root()
912 BUG_ON(as->journal_u64s + jset_u64s(insert->k.u64s) > in btree_update_updated_root()
913 ARRAY_SIZE(as->journal_entries)); in btree_update_updated_root()
915 as->journal_u64s += in btree_update_updated_root()
916 journal_entry_set((void *) &as->journal_entries[as->journal_u64s], in btree_update_updated_root()
918 b->c.btree_id, b->c.level, in btree_update_updated_root()
919 insert, insert->k.u64s); in btree_update_updated_root()
921 mutex_lock(&c->btree_interior_update_lock); in btree_update_updated_root()
922 list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten); in btree_update_updated_root()
924 as->mode = BTREE_UPDATE_root; in btree_update_updated_root()
925 mutex_unlock(&c->btree_interior_update_lock); in btree_update_updated_root()
934 * Additionally, it sets b->will_make_reachable to prevent any additional writes
942 struct bch_fs *c = as->c; in bch2_btree_update_add_new_node()
944 closure_get(&as->cl); in bch2_btree_update_add_new_node()
946 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_add_new_node()
947 BUG_ON(as->nr_new_nodes >= ARRAY_SIZE(as->new_nodes)); in bch2_btree_update_add_new_node()
948 BUG_ON(b->will_make_reachable); in bch2_btree_update_add_new_node()
950 as->new_nodes[as->nr_new_nodes++] = b; in bch2_btree_update_add_new_node()
951 b->will_make_reachable = 1UL|(unsigned long) as; in bch2_btree_update_add_new_node()
954 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_add_new_node()
956 btree_update_add_key(as, &as->new_keys, b); in bch2_btree_update_add_new_node()
958 if (b->key.k.type == KEY_TYPE_btree_ptr_v2) { in bch2_btree_update_add_new_node()
959 unsigned bytes = vstruct_end(&b->data->keys) - (void *) b->data; in bch2_btree_update_add_new_node()
962 bkey_i_to_btree_ptr_v2(&b->key)->v.sectors_written = in bch2_btree_update_add_new_node()
976 mutex_lock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
978 * When b->will_make_reachable != 0, it owns a ref on as->cl that's in btree_update_drop_new_node()
979 * dropped when it gets written by bch2_btree_complete_write - the in btree_update_drop_new_node()
982 v = xchg(&b->will_make_reachable, 0); in btree_update_drop_new_node()
987 mutex_unlock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
991 for (i = 0; i < as->nr_new_nodes; i++) in btree_update_drop_new_node()
992 if (as->new_nodes[i] == b) in btree_update_drop_new_node()
997 array_remove_item(as->new_nodes, as->nr_new_nodes, i); in btree_update_drop_new_node()
998 mutex_unlock(&c->btree_interior_update_lock); in btree_update_drop_new_node()
1001 closure_put(&as->cl); in btree_update_drop_new_node()
1006 while (b->ob.nr) in bch2_btree_update_get_open_buckets()
1007 as->open_buckets[as->nr_open_buckets++] = in bch2_btree_update_get_open_buckets()
1008 b->ob.v[--b->ob.nr]; in bch2_btree_update_get_open_buckets()
1018 * @b is being split/rewritten: it may have pointers to not-yet-written btree
1019 * nodes and thus outstanding btree_updates - redirect @b's
1025 struct bch_fs *c = as->c; in bch2_btree_interior_update_will_free_node()
1034 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_interior_update_will_free_node()
1044 list_for_each_entry_safe(p, n, &b->write_blocked, write_blocked_list) { in bch2_btree_interior_update_will_free_node()
1045 list_del_init(&p->write_blocked_list); in bch2_btree_interior_update_will_free_node()
1052 closure_wake_up(&c->btree_interior_update_wait); in bch2_btree_interior_update_will_free_node()
1062 * If so, transfer that pin to the btree_update operation - in bch2_btree_interior_update_will_free_node()
1068 bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, in bch2_btree_interior_update_will_free_node()
1070 bch2_journal_pin_drop(&c->journal, &w->journal); in bch2_btree_interior_update_will_free_node()
1073 bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, in bch2_btree_interior_update_will_free_node()
1075 bch2_journal_pin_drop(&c->journal, &w->journal); in bch2_btree_interior_update_will_free_node()
1077 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_interior_update_will_free_node()
1083 * reachable - now that we've cancelled any pending writes and moved in bch2_btree_interior_update_will_free_node()
1090 btree_update_add_key(as, &as->old_keys, b); in bch2_btree_interior_update_will_free_node()
1092 as->old_nodes[as->nr_old_nodes] = b; in bch2_btree_interior_update_will_free_node()
1093 as->old_nodes_seq[as->nr_old_nodes] = b->data->keys.seq; in bch2_btree_interior_update_will_free_node()
1094 as->nr_old_nodes++; in bch2_btree_interior_update_will_free_node()
1099 struct bch_fs *c = as->c; in bch2_btree_update_done()
1100 u64 start_time = as->start_time; in bch2_btree_update_done()
1102 BUG_ON(as->mode == BTREE_UPDATE_none); in bch2_btree_update_done()
1104 if (as->took_gc_lock) in bch2_btree_update_done()
1105 up_read(&as->c->gc_lock); in bch2_btree_update_done()
1106 as->took_gc_lock = false; in bch2_btree_update_done()
1110 continue_at(&as->cl, btree_update_set_nodes_written, in bch2_btree_update_done()
1111 as->c->btree_interior_update_worker); in bch2_btree_update_done()
1113 bch2_time_stats_update(&c->times[BCH_TIME_btree_interior_update_foreground], in bch2_btree_update_done()
1121 struct bch_fs *c = trans->c; in bch2_btree_update_start()
1130 u32 restart_count = trans->restart_count; in bch2_btree_update_start()
1132 BUG_ON(!path->should_be_locked); in bch2_btree_update_start()
1143 test_bit(JOURNAL_space_low, &c->journal.flags)) { in bch2_btree_update_start()
1145 return ERR_PTR(-BCH_ERR_journal_reclaim_would_deadlock); in bch2_btree_update_start()
1148 ({ wait_event(c->journal.wait, !test_bit(JOURNAL_space_low, &c->journal.flags)); 0; })); in bch2_btree_update_start()
1170 * split at prior level - it might have been a merge instead: in bch2_btree_update_start()
1172 if (bch2_btree_node_insert_fits(path->l[level_end].b, in bch2_btree_update_start()
1176 split = path->l[level_end].b->nr.live_u64s > BTREE_SPLIT_THRESHOLD(c); in bch2_btree_update_start()
1179 if (!down_read_trylock(&c->gc_lock)) { in bch2_btree_update_start()
1180 ret = drop_locks_do(trans, (down_read(&c->gc_lock), 0)); in bch2_btree_update_start()
1182 up_read(&c->gc_lock); in bch2_btree_update_start()
1187 as = mempool_alloc(&c->btree_interior_update_pool, GFP_NOFS); in bch2_btree_update_start()
1189 closure_init(&as->cl, NULL); in bch2_btree_update_start()
1190 as->c = c; in bch2_btree_update_start()
1191 as->start_time = start_time; in bch2_btree_update_start()
1192 as->ip_started = _RET_IP_; in bch2_btree_update_start()
1193 as->mode = BTREE_UPDATE_none; in bch2_btree_update_start()
1194 as->flags = flags; in bch2_btree_update_start()
1195 as->took_gc_lock = true; in bch2_btree_update_start()
1196 as->btree_id = path->btree_id; in bch2_btree_update_start()
1197 as->update_level_start = level_start; in bch2_btree_update_start()
1198 as->update_level_end = level_end; in bch2_btree_update_start()
1199 INIT_LIST_HEAD(&as->list); in bch2_btree_update_start()
1200 INIT_LIST_HEAD(&as->unwritten_list); in bch2_btree_update_start()
1201 INIT_LIST_HEAD(&as->write_blocked_list); in bch2_btree_update_start()
1202 bch2_keylist_init(&as->old_keys, as->_old_keys); in bch2_btree_update_start()
1203 bch2_keylist_init(&as->new_keys, as->_new_keys); in bch2_btree_update_start()
1204 bch2_keylist_init(&as->parent_keys, as->inline_keys); in bch2_btree_update_start()
1206 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_update_start()
1207 list_add_tail(&as->list, &c->btree_interior_update_list); in bch2_btree_update_start()
1208 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_update_start()
1218 ret = bch2_journal_error(&c->journal); in bch2_btree_update_start()
1222 ret = bch2_disk_reservation_get(c, &as->disk_res, in bch2_btree_update_start()
1224 READ_ONCE(c->opts.metadata_replicas), in bch2_btree_update_start()
1241 ret = -BCH_ERR_journal_reclaim_would_deadlock; in bch2_btree_update_start()
1256 trace_and_count(c, btree_reserve_get_fail, trans->fn, in bch2_btree_update_start()
1271 ret != -BCH_ERR_journal_reclaim_would_deadlock && in bch2_btree_update_start()
1272 ret != -BCH_ERR_journal_shutdown) in bch2_btree_update_start()
1282 mutex_lock(&c->btree_cache.lock); in bch2_btree_set_root_inmem()
1283 list_del_init(&b->list); in bch2_btree_set_root_inmem()
1284 mutex_unlock(&c->btree_cache.lock); in bch2_btree_set_root_inmem()
1286 mutex_lock(&c->btree_root_lock); in bch2_btree_set_root_inmem()
1287 bch2_btree_id_root(c, b->c.btree_id)->b = b; in bch2_btree_set_root_inmem()
1288 mutex_unlock(&c->btree_root_lock); in bch2_btree_set_root_inmem()
1299 struct bch_fs *c = as->c; in bch2_btree_set_root()
1310 bch2_btree_node_lock_write_nofail(trans, path, &old->c); in bch2_btree_set_root()
1312 int ret = bch2_btree_node_lock_write(trans, path, &old->c); in bch2_btree_set_root()
1341 struct bch_fs *c = as->c; in bch2_insert_fixup_btree_ptr()
1346 BUG_ON(insert->k.type == KEY_TYPE_btree_ptr_v2 && in bch2_insert_fixup_btree_ptr()
1349 if (unlikely(!test_bit(JOURNAL_replay_done, &c->journal.flags))) in bch2_insert_fixup_btree_ptr()
1350 bch2_journal_key_overwritten(c, b->c.btree_id, b->c.level, insert->k.p); in bch2_insert_fixup_btree_ptr()
1354 .level = b->c.level, in bch2_insert_fixup_btree_ptr()
1355 .btree = b->c.btree_id, in bch2_insert_fixup_btree_ptr()
1364 BUG_ON(as->journal_u64s + jset_u64s(insert->k.u64s) > in bch2_insert_fixup_btree_ptr()
1365 ARRAY_SIZE(as->journal_entries)); in bch2_insert_fixup_btree_ptr()
1367 as->journal_u64s += in bch2_insert_fixup_btree_ptr()
1368 journal_entry_set((void *) &as->journal_entries[as->journal_u64s], in bch2_insert_fixup_btree_ptr()
1370 b->c.btree_id, b->c.level, in bch2_insert_fixup_btree_ptr()
1371 insert, insert->k.u64s); in bch2_insert_fixup_btree_ptr()
1374 bkey_iter_pos_cmp(b, k, &insert->k.p) < 0) in bch2_insert_fixup_btree_ptr()
1380 old = READ_ONCE(b->flags); in bch2_insert_fixup_btree_ptr()
1387 } while (!try_cmpxchg(&b->flags, &old, new)); in bch2_insert_fixup_btree_ptr()
1406 (bkey_cmp_left_packed(b, k, &insert->k.p) >= 0)) in bch2_btree_insert_keys_interior()
1410 insert != keys->top && bpos_le(insert->k.p, b->key.k.p); in bch2_btree_insert_keys_interior()
1418 for (struct bkey_i *k = keys->keys; in bch2_btree_insert_keys_interior()
1421 bch2_bkey_val_to_text(&buf, trans->c, bkey_i_to_s_c(k)); in bch2_btree_insert_keys_interior()
1425 bch2_fs_fatal_error(as->c, "%ps -> %s(): check_topology error %s: inserted keys\n%s", in bch2_btree_insert_keys_interior()
1431 memmove_u64s_down(keys->keys, insert, keys->top_p - insert->_data); in bch2_btree_insert_keys_interior()
1432 keys->top_p -= insert->_data - keys->keys_p; in bch2_btree_insert_keys_interior()
1440 if (bkey_deleted(&k->k) && bpos_eq(k->k.p, pos)) in key_deleted_in_insert()
1462 unsigned u64s, n1_u64s = (b->nr.live_u64s * 3) / 5; in __btree_split_node()
1469 BUG_ON(n[i]->nsets != 1); in __btree_split_node()
1472 out[i] = bsets[i]->start; in __btree_split_node()
1474 SET_BTREE_NODE_SEQ(n[i]->data, BTREE_NODE_SEQ(b->data) + 1); in __btree_split_node()
1485 if (b->c.level && in __btree_split_node()
1487 u64s + k->u64s >= n1_u64s && in __btree_split_node()
1488 (bch2_key_deleted_in_journal(trans, b->c.btree_id, b->c.level, uk.p) || in __btree_split_node()
1490 n1_u64s += k->u64s; in __btree_split_node()
1493 u64s += k->u64s; in __btree_split_node()
1499 nr_keys[i].val_u64s += bkeyp_val_u64s(&b->format, k); in __btree_split_node()
1502 btree_set_min(n[0], b->data->min_key); in __btree_split_node()
1505 btree_set_max(n[1], b->data->max_key); in __btree_split_node()
1508 bch2_bkey_format_add_pos(&format[i], n[i]->data->min_key); in __btree_split_node()
1509 bch2_bkey_format_add_pos(&format[i], n[i]->data->max_key); in __btree_split_node()
1511 n[i]->data->format = bch2_bkey_format_done(&format[i]); in __btree_split_node()
1513 unsigned u64s = nr_keys[i].nr_keys * n[i]->data->format.key_u64s + in __btree_split_node()
1516 n[i]->data->format = b->format; in __btree_split_node()
1518 btree_node_set_format(n[i], n[i]->data->format); in __btree_split_node()
1527 u64s += k->u64s; in __btree_split_node()
1529 if (bch2_bkey_transform(&n[i]->format, out[i], bkey_packed(k) in __btree_split_node()
1530 ? &b->format: &bch2_bkey_format_current, k)) in __btree_split_node()
1531 out[i]->format = KEY_FORMAT_LOCAL_BTREE; in __btree_split_node()
1535 out[i]->needs_whiteout = false; in __btree_split_node()
1537 btree_keys_account_key_add(&n[i]->nr, 0, out[i]); in __btree_split_node()
1542 bsets[i]->u64s = cpu_to_le16((u64 *) out[i] - bsets[i]->_data); in __btree_split_node()
1544 BUG_ON(!bsets[i]->u64s); in __btree_split_node()
1546 set_btree_bset_end(n[i], n[i]->set); in __btree_split_node()
1558 * because the stuff we're inserting has to be inserted atomically. Post split,
1563 * we do the split (and pick the pivot) - the pivot we pick might be between
1564 * nodes that were coalesced, and thus in the middle of a child node post
1573 struct btree_path *path = trans->paths + path_idx; in btree_split_insert_keys()
1576 bpos_le(bch2_keylist_front(keys)->k.p, b->data->max_key)) { in btree_split_insert_keys()
1579 bch2_btree_node_iter_init(&node_iter, b, &bch2_keylist_front(keys)->k.p); in btree_split_insert_keys()
1593 struct bch_fs *c = as->c; in btree_split()
1594 struct btree *parent = btree_node_parent(trans->paths + path, b); in btree_split()
1602 BUG_ON(parent && !btree_node_intent_locked(trans->paths + path, b->c.level + 1)); in btree_split()
1608 if (b->nr.live_u64s > BTREE_SPLIT_THRESHOLD(c)) { in btree_split()
1613 n[0] = n1 = bch2_btree_node_alloc(as, trans, b->c.level); in btree_split()
1614 n[1] = n2 = bch2_btree_node_alloc(as, trans, b->c.level); in btree_split()
1631 six_unlock_write(&n2->c.lock); in btree_split()
1632 six_unlock_write(&n1->c.lock); in btree_split()
1634 path1 = bch2_path_get_unlocked_mut(trans, as->btree_id, n1->c.level, n1->key.k.p); in btree_split()
1635 six_lock_increment(&n1->c.lock, SIX_LOCK_intent); in btree_split()
1636 mark_btree_node_locked(trans, trans->paths + path1, n1->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1637 bch2_btree_path_level_init(trans, trans->paths + path1, n1); in btree_split()
1639 path2 = bch2_path_get_unlocked_mut(trans, as->btree_id, n2->c.level, n2->key.k.p); in btree_split()
1640 six_lock_increment(&n2->c.lock, SIX_LOCK_intent); in btree_split()
1641 mark_btree_node_locked(trans, trans->paths + path2, n2->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1642 bch2_btree_path_level_init(trans, trans->paths + path2, n2); in btree_split()
1649 bch2_keylist_add(&as->parent_keys, &n1->key); in btree_split()
1650 bch2_keylist_add(&as->parent_keys, &n2->key); in btree_split()
1654 n3 = __btree_root_alloc(as, trans, b->c.level + 1); in btree_split()
1657 six_unlock_write(&n3->c.lock); in btree_split()
1659 trans->paths[path2].locks_want++; in btree_split()
1660 BUG_ON(btree_node_locked(trans->paths + path2, n3->c.level)); in btree_split()
1661 six_lock_increment(&n3->c.lock, SIX_LOCK_intent); in btree_split()
1662 mark_btree_node_locked(trans, trans->paths + path2, n3->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1663 bch2_btree_path_level_init(trans, trans->paths + path2, n3); in btree_split()
1665 n3->sib_u64s[0] = U16_MAX; in btree_split()
1666 n3->sib_u64s[1] = U16_MAX; in btree_split()
1668 ret = btree_split_insert_keys(as, trans, path, n3, &as->parent_keys); in btree_split()
1686 six_unlock_write(&n1->c.lock); in btree_split()
1688 path1 = bch2_path_get_unlocked_mut(trans, as->btree_id, n1->c.level, n1->key.k.p); in btree_split()
1689 six_lock_increment(&n1->c.lock, SIX_LOCK_intent); in btree_split()
1690 mark_btree_node_locked(trans, trans->paths + path1, n1->c.level, BTREE_NODE_INTENT_LOCKED); in btree_split()
1691 bch2_btree_path_level_init(trans, trans->paths + path1, n1); in btree_split()
1694 bch2_keylist_add(&as->parent_keys, &n1->key); in btree_split()
1701 ret = bch2_btree_insert_node(as, trans, path, parent, &as->parent_keys); in btree_split()
1703 ret = bch2_btree_set_root(as, trans, trans->paths + path, n3, false); in btree_split()
1706 ret = bch2_btree_set_root(as, trans, trans->paths + path, n1, false); in btree_split()
1727 * nodes - else another thread could re-acquire a read lock on the old in btree_split()
1731 bch2_btree_node_free_inmem(trans, trans->paths + path, b); in btree_split()
1734 bch2_trans_node_add(trans, trans->paths + path, n3); in btree_split()
1736 bch2_trans_node_add(trans, trans->paths + path2, n2); in btree_split()
1737 bch2_trans_node_add(trans, trans->paths + path1, n1); in btree_split()
1740 six_unlock_intent(&n3->c.lock); in btree_split()
1742 six_unlock_intent(&n2->c.lock); in btree_split()
1743 six_unlock_intent(&n1->c.lock); in btree_split()
1746 __bch2_btree_path_unlock(trans, trans->paths + path2); in btree_split()
1750 __bch2_btree_path_unlock(trans, trans->paths + path1); in btree_split()
1756 bch2_time_stats_update(&c->times[n2 in btree_split()
1771 * bch2_btree_insert_node - insert bkeys into a given btree node
1783 * for leaf nodes -- inserts into interior nodes have to be atomic.
1789 struct bch_fs *c = as->c; in bch2_btree_insert_node()
1790 struct btree_path *path = trans->paths + path_idx, *linked; in bch2_btree_insert_node()
1792 int old_u64s = le16_to_cpu(btree_bset_last(b)->u64s); in bch2_btree_insert_node()
1793 int old_live_u64s = b->nr.live_u64s; in bch2_btree_insert_node()
1797 lockdep_assert_held(&c->gc_lock); in bch2_btree_insert_node()
1798 BUG_ON(!b->c.level); in bch2_btree_insert_node()
1799 BUG_ON(!as || as->b); in bch2_btree_insert_node()
1802 if (!btree_node_intent_locked(path, b->c.level)) { in bch2_btree_insert_node()
1806 __func__, b->c.level); in bch2_btree_insert_node()
1813 return -EIO; in bch2_btree_insert_node()
1816 ret = bch2_btree_node_lock_write(trans, path, &b->c); in bch2_btree_insert_node()
1830 path->l[b->c.level].iter, keys); in bch2_btree_insert_node()
1837 bch2_btree_node_iter_peek(&linked->l[b->c.level].iter, b); in bch2_btree_insert_node()
1841 live_u64s_added = (int) b->nr.live_u64s - old_live_u64s; in bch2_btree_insert_node()
1842 u64s_added = (int) le16_to_cpu(btree_bset_last(b)->u64s) - old_u64s; in bch2_btree_insert_node()
1844 if (b->sib_u64s[0] != U16_MAX && live_u64s_added < 0) in bch2_btree_insert_node()
1845 b->sib_u64s[0] = max(0, (int) b->sib_u64s[0] + live_u64s_added); in bch2_btree_insert_node()
1846 if (b->sib_u64s[1] != U16_MAX && live_u64s_added < 0) in bch2_btree_insert_node()
1847 b->sib_u64s[1] = max(0, (int) b->sib_u64s[1] + live_u64s_added); in bch2_btree_insert_node()
1861 if (b->c.level >= as->update_level_end) { in bch2_btree_insert_node()
1873 /* btree_split & merge may both cause paths array to be reallocated */ in bch2_btree_split_leaf()
1874 struct btree *b = path_l(trans->paths + path)->b; in bch2_btree_split_leaf()
1879 as = bch2_btree_update_start(trans, trans->paths + path, in bch2_btree_split_leaf()
1880 trans->paths[path].level, in bch2_btree_split_leaf()
1893 for (l = trans->paths[path].level + 1; in bch2_btree_split_leaf()
1894 btree_node_intent_locked(&trans->paths[path], l) && !ret; in bch2_btree_split_leaf()
1904 struct bch_fs *c = as->c; in __btree_increase_depth()
1905 struct btree_path *path = trans->paths + path_idx; in __btree_increase_depth()
1906 struct btree *n, *b = bch2_btree_id_root(c, path->btree_id)->b; in __btree_increase_depth()
1908 BUG_ON(!btree_node_locked(path, b->c.level)); in __btree_increase_depth()
1910 n = __btree_root_alloc(as, trans, b->c.level + 1); in __btree_increase_depth()
1913 six_unlock_write(&n->c.lock); in __btree_increase_depth()
1915 path->locks_want++; in __btree_increase_depth()
1916 BUG_ON(btree_node_locked(path, n->c.level)); in __btree_increase_depth()
1917 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in __btree_increase_depth()
1918 mark_btree_node_locked(trans, path, n->c.level, BTREE_NODE_INTENT_LOCKED); in __btree_increase_depth()
1921 n->sib_u64s[0] = U16_MAX; in __btree_increase_depth()
1922 n->sib_u64s[1] = U16_MAX; in __btree_increase_depth()
1924 bch2_keylist_add(&as->parent_keys, &b->key); in __btree_increase_depth()
1925 btree_split_insert_keys(as, trans, path_idx, n, &as->parent_keys); in __btree_increase_depth()
1933 six_unlock_intent(&n->c.lock); in __btree_increase_depth()
1935 mutex_lock(&c->btree_cache.lock); in __btree_increase_depth()
1936 list_add_tail(&b->list, &c->btree_cache.live[btree_node_pinned(b)].list); in __btree_increase_depth()
1937 mutex_unlock(&c->btree_cache.lock); in __btree_increase_depth()
1944 struct bch_fs *c = trans->c; in bch2_btree_increase_depth()
1945 struct btree *b = bch2_btree_id_root(c, trans->paths[path].btree_id)->b; in bch2_btree_increase_depth()
1951 bch2_btree_update_start(trans, trans->paths + path, b->c.level, true, flags); in bch2_btree_increase_depth()
1966 struct bch_fs *c = trans->c; in __bch2_foreground_maybe_merge()
1974 enum btree_id btree = trans->paths[path].btree_id; in __bch2_foreground_maybe_merge()
1980 BUG_ON(!trans->paths[path].should_be_locked); in __bch2_foreground_maybe_merge()
1981 BUG_ON(!btree_node_locked(&trans->paths[path], level)); in __bch2_foreground_maybe_merge()
1985 * merges and leaving tons of merges for us to do - we really don't need in __bch2_foreground_maybe_merge()
1999 b = trans->paths[path].l[level].b; in __bch2_foreground_maybe_merge()
2001 if ((sib == btree_prev_sib && bpos_eq(b->data->min_key, POS_MIN)) || in __bch2_foreground_maybe_merge()
2002 (sib == btree_next_sib && bpos_eq(b->data->max_key, SPOS_MAX))) { in __bch2_foreground_maybe_merge()
2003 b->sib_u64s[sib] = U16_MAX; in __bch2_foreground_maybe_merge()
2008 ? bpos_predecessor(b->data->min_key) in __bch2_foreground_maybe_merge()
2009 : bpos_successor(b->data->max_key); in __bch2_foreground_maybe_merge()
2017 btree_path_set_should_be_locked(trans, trans->paths + sib_path); in __bch2_foreground_maybe_merge()
2019 m = trans->paths[sib_path].l[level].b; in __bch2_foreground_maybe_merge()
2021 if (btree_node_parent(trans->paths + path, b) != in __bch2_foreground_maybe_merge()
2022 btree_node_parent(trans->paths + sib_path, m)) { in __bch2_foreground_maybe_merge()
2023 b->sib_u64s[sib] = U16_MAX; in __bch2_foreground_maybe_merge()
2035 if (!bpos_eq(bpos_successor(prev->data->max_key), next->data->min_key)) { in __bch2_foreground_maybe_merge()
2044 bch2_bpos_to_text(&buf, prev->data->max_key); in __bch2_foreground_maybe_merge()
2048 bch2_bpos_to_text(&buf, next->data->min_key); in __bch2_foreground_maybe_merge()
2056 bch2_bkey_format_add_pos(&new_s, prev->data->min_key); in __bch2_foreground_maybe_merge()
2059 bch2_bkey_format_add_pos(&new_s, next->data->max_key); in __bch2_foreground_maybe_merge()
2062 sib_u64s = btree_node_u64s_with_format(b->nr, &b->format, &new_f) + in __bch2_foreground_maybe_merge()
2063 btree_node_u64s_with_format(m->nr, &m->format, &new_f); in __bch2_foreground_maybe_merge()
2066 sib_u64s -= BTREE_FOREGROUND_MERGE_HYSTERESIS(c); in __bch2_foreground_maybe_merge()
2072 sib_u64s = min(sib_u64s, (size_t) U16_MAX - 1); in __bch2_foreground_maybe_merge()
2073 b->sib_u64s[sib] = sib_u64s; in __bch2_foreground_maybe_merge()
2075 if (b->sib_u64s[sib] > c->btree_foreground_merge_threshold) in __bch2_foreground_maybe_merge()
2078 parent = btree_node_parent(trans->paths + path, b); in __bch2_foreground_maybe_merge()
2079 as = bch2_btree_update_start(trans, trans->paths + path, level, false, in __bch2_foreground_maybe_merge()
2087 n = bch2_btree_node_alloc(as, trans, b->c.level); in __bch2_foreground_maybe_merge()
2089 SET_BTREE_NODE_SEQ(n->data, in __bch2_foreground_maybe_merge()
2090 max(BTREE_NODE_SEQ(b->data), in __bch2_foreground_maybe_merge()
2091 BTREE_NODE_SEQ(m->data)) + 1); in __bch2_foreground_maybe_merge()
2093 btree_set_min(n, prev->data->min_key); in __bch2_foreground_maybe_merge()
2094 btree_set_max(n, next->data->max_key); in __bch2_foreground_maybe_merge()
2096 n->data->format = new_f; in __bch2_foreground_maybe_merge()
2104 six_unlock_write(&n->c.lock); in __bch2_foreground_maybe_merge()
2106 new_path = bch2_path_get_unlocked_mut(trans, btree, n->c.level, n->key.k.p); in __bch2_foreground_maybe_merge()
2107 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in __bch2_foreground_maybe_merge()
2108 mark_btree_node_locked(trans, trans->paths + new_path, n->c.level, BTREE_NODE_INTENT_LOCKED); in __bch2_foreground_maybe_merge()
2109 bch2_btree_path_level_init(trans, trans->paths + new_path, n); in __bch2_foreground_maybe_merge()
2112 delete.k.p = prev->key.k.p; in __bch2_foreground_maybe_merge()
2113 bch2_keylist_add(&as->parent_keys, &delete); in __bch2_foreground_maybe_merge()
2114 bch2_keylist_add(&as->parent_keys, &n->key); in __bch2_foreground_maybe_merge()
2118 ret = bch2_btree_insert_node(as, trans, path, parent, &as->parent_keys); in __bch2_foreground_maybe_merge()
2130 bch2_btree_node_free_inmem(trans, trans->paths + path, b); in __bch2_foreground_maybe_merge()
2131 bch2_btree_node_free_inmem(trans, trans->paths + sib_path, m); in __bch2_foreground_maybe_merge()
2133 bch2_trans_node_add(trans, trans->paths + path, n); in __bch2_foreground_maybe_merge()
2137 six_unlock_intent(&n->c.lock); in __bch2_foreground_maybe_merge()
2141 bch2_time_stats_update(&c->times[BCH_TIME_btree_node_merge], start_time); in __bch2_foreground_maybe_merge()
2148 if (ret == -BCH_ERR_journal_reclaim_would_deadlock) in __bch2_foreground_maybe_merge()
2162 bch2_trans_node_iter_init(trans, iter, b->c.btree_id, b->key.k.p, in get_iter_to_node()
2163 BTREE_MAX_DEPTH, b->c.level, in get_iter_to_node()
2170 if (btree_iter_path(trans, iter)->l[b->c.level].b != b) { in get_iter_to_node()
2173 ret = -BCH_ERR_btree_node_dying; in get_iter_to_node()
2189 struct bch_fs *c = trans->c; in bch2_btree_node_rewrite()
2199 as = bch2_btree_update_start(trans, path, b->c.level, false, flags); in bch2_btree_node_rewrite()
2208 six_unlock_write(&n->c.lock); in bch2_btree_node_rewrite()
2210 new_path = bch2_path_get_unlocked_mut(trans, iter->btree_id, n->c.level, n->key.k.p); in bch2_btree_node_rewrite()
2211 six_lock_increment(&n->c.lock, SIX_LOCK_intent); in bch2_btree_node_rewrite()
2212 mark_btree_node_locked(trans, trans->paths + new_path, n->c.level, BTREE_NODE_INTENT_LOCKED); in bch2_btree_node_rewrite()
2213 bch2_btree_path_level_init(trans, trans->paths + new_path, n); in bch2_btree_node_rewrite()
2218 bch2_keylist_add(&as->parent_keys, &n->key); in bch2_btree_node_rewrite()
2219 ret = bch2_btree_insert_node(as, trans, iter->path, parent, &as->parent_keys); in bch2_btree_node_rewrite()
2234 bch2_trans_node_add(trans, trans->paths + iter->path, n); in bch2_btree_node_rewrite()
2235 six_unlock_intent(&n->c.lock); in bch2_btree_node_rewrite()
2255 btree, k->k.p, in bch2_btree_node_rewrite_key()
2262 bool found = b && btree_ptr_hash_val(&b->key) == btree_ptr_hash_val(k); in bch2_btree_node_rewrite_key()
2265 : -ENOENT; in bch2_btree_node_rewrite_key()
2279 bch2_trans_node_iter_init(trans, &iter, btree, pos, 0, level - 1, 0); in bch2_btree_node_rewrite_pos()
2297 return ret == -BCH_ERR_btree_node_dying ? 0 : ret; in bch2_btree_node_rewrite_key_get_iter()
2317 struct bch_fs *c = a->c; in async_btree_node_rewrite_work()
2320 a->btree_id, a->level, a->key.k, 0)); in async_btree_node_rewrite_work()
2321 if (ret != -ENOENT && in async_btree_node_rewrite_work()
2323 ret != -BCH_ERR_journal_shutdown) in async_btree_node_rewrite_work()
2326 spin_lock(&c->btree_node_rewrites_lock); in async_btree_node_rewrite_work()
2327 list_del(&a->list); in async_btree_node_rewrite_work()
2328 spin_unlock(&c->btree_node_rewrites_lock); in async_btree_node_rewrite_work()
2330 closure_wake_up(&c->btree_node_rewrites_wait); in async_btree_node_rewrite_work()
2332 bch2_bkey_buf_exit(&a->key, c); in async_btree_node_rewrite_work()
2343 a->c = c; in bch2_btree_node_rewrite_async()
2344 a->btree_id = b->c.btree_id; in bch2_btree_node_rewrite_async()
2345 a->level = b->c.level; in bch2_btree_node_rewrite_async()
2346 INIT_WORK(&a->work, async_btree_node_rewrite_work); in bch2_btree_node_rewrite_async()
2348 bch2_bkey_buf_init(&a->key); in bch2_btree_node_rewrite_async()
2349 bch2_bkey_buf_copy(&a->key, c, &b->key); in bch2_btree_node_rewrite_async()
2353 spin_lock(&c->btree_node_rewrites_lock); in bch2_btree_node_rewrite_async()
2354 if (c->curr_recovery_pass > BCH_RECOVERY_PASS_journal_replay && in bch2_btree_node_rewrite_async()
2356 list_add(&a->list, &c->btree_node_rewrites); in bch2_btree_node_rewrite_async()
2358 } else if (!test_bit(BCH_FS_may_go_rw, &c->flags)) { in bch2_btree_node_rewrite_async()
2359 list_add(&a->list, &c->btree_node_rewrites_pending); in bch2_btree_node_rewrite_async()
2362 spin_unlock(&c->btree_node_rewrites_lock); in bch2_btree_node_rewrite_async()
2365 queue_work(c->btree_node_rewrite_worker, &a->work); in bch2_btree_node_rewrite_async()
2369 bch2_bkey_buf_exit(&a->key, c); in bch2_btree_node_rewrite_async()
2376 closure_wait_event(&c->btree_node_rewrites_wait, in bch2_async_btree_node_rewrites_flush()
2377 list_empty(&c->btree_node_rewrites)); in bch2_async_btree_node_rewrites_flush()
2383 spin_lock(&c->btree_node_rewrites_lock); in bch2_do_pending_node_rewrites()
2385 list_pop_entry(&c->btree_node_rewrites_pending, in bch2_do_pending_node_rewrites()
2388 list_add(&a->list, &c->btree_node_rewrites); in bch2_do_pending_node_rewrites()
2389 spin_unlock(&c->btree_node_rewrites_lock); in bch2_do_pending_node_rewrites()
2395 queue_work(c->btree_node_rewrite_worker, &a->work); in bch2_do_pending_node_rewrites()
2402 spin_lock(&c->btree_node_rewrites_lock); in bch2_free_pending_node_rewrites()
2404 list_pop_entry(&c->btree_node_rewrites_pending, in bch2_free_pending_node_rewrites()
2406 spin_unlock(&c->btree_node_rewrites_lock); in bch2_free_pending_node_rewrites()
2411 bch2_bkey_buf_exit(&a->key, c); in bch2_free_pending_node_rewrites()
2423 struct bch_fs *c = trans->c; in __bch2_btree_node_update_key()
2429 ret = bch2_key_trigger_old(trans, b->c.btree_id, b->c.level + 1, in __bch2_btree_node_update_key()
2430 bkey_i_to_s_c(&b->key), in __bch2_btree_node_update_key()
2432 bch2_key_trigger_new(trans, b->c.btree_id, b->c.level + 1, in __bch2_btree_node_update_key()
2440 bkey_copy(&new_hash->key, new_key); in __bch2_btree_node_update_key()
2441 ret = bch2_btree_node_hash_insert(&c->btree_cache, in __bch2_btree_node_update_key()
2442 new_hash, b->c.level, b->c.btree_id); in __bch2_btree_node_update_key()
2455 BUG_ON(path2->level != b->c.level); in __bch2_btree_node_update_key()
2456 BUG_ON(!bpos_eq(path2->pos, new_key->k.p)); in __bch2_btree_node_update_key()
2460 trans->paths_sorted = false; in __bch2_btree_node_update_key()
2470 jset_u64s(new_key->k.u64s)); in __bch2_btree_node_update_key()
2477 b->c.btree_id, b->c.level, in __bch2_btree_node_update_key()
2478 new_key, new_key->k.u64s); in __bch2_btree_node_update_key()
2485 bch2_btree_node_lock_write_nofail(trans, btree_iter_path(trans, iter), &b->c); in __bch2_btree_node_update_key()
2488 mutex_lock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2489 bch2_btree_node_hash_remove(&c->btree_cache, new_hash); in __bch2_btree_node_update_key()
2491 __bch2_btree_node_hash_remove(&c->btree_cache, b); in __bch2_btree_node_update_key()
2493 bkey_copy(&b->key, new_key); in __bch2_btree_node_update_key()
2494 ret = __bch2_btree_node_hash_insert(&c->btree_cache, b); in __bch2_btree_node_update_key()
2496 mutex_unlock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2498 bkey_copy(&b->key, new_key); in __bch2_btree_node_update_key()
2507 mutex_lock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2508 bch2_btree_node_hash_remove(&c->btree_cache, b); in __bch2_btree_node_update_key()
2509 mutex_unlock(&c->btree_cache.lock); in __bch2_btree_node_update_key()
2518 struct bch_fs *c = trans->c; in bch2_btree_node_update_key()
2524 ret = bch2_btree_path_upgrade(trans, path, b->c.level + 1); in bch2_btree_node_update_key()
2534 if (btree_ptr_hash_val(new_key) != b->hash_val) { in bch2_btree_node_update_key()
2548 path->intent_ref++; in bch2_btree_node_update_key()
2551 --path->intent_ref; in bch2_btree_node_update_key()
2568 return ret == -BCH_ERR_btree_node_dying ? 0 : ret; in bch2_btree_node_update_key_get_iter()
2571 !bch2_bkey_has_device(bkey_i_to_s(&b->key), ptr->dev)); in bch2_btree_node_update_key_get_iter()
2594 struct bch_fs *c = trans->c; in bch2_btree_root_alloc_fake_trans()
2615 b->c.level = level; in bch2_btree_root_alloc_fake_trans()
2616 b->c.btree_id = id; in bch2_btree_root_alloc_fake_trans()
2618 bkey_btree_ptr_init(&b->key); in bch2_btree_root_alloc_fake_trans()
2619 b->key.k.p = SPOS_MAX; in bch2_btree_root_alloc_fake_trans()
2620 *((u64 *) bkey_i_to_btree_ptr(&b->key)->v.start) = U64_MAX - id; in bch2_btree_root_alloc_fake_trans()
2622 bch2_bset_init_first(b, &b->data->keys); in bch2_btree_root_alloc_fake_trans()
2625 b->data->flags = 0; in bch2_btree_root_alloc_fake_trans()
2628 b->data->format = bch2_btree_calc_format(b); in bch2_btree_root_alloc_fake_trans()
2629 btree_node_set_format(b, b->data->format); in bch2_btree_root_alloc_fake_trans()
2631 ret = bch2_btree_node_hash_insert(&c->btree_cache, b, in bch2_btree_root_alloc_fake_trans()
2632 b->c.level, b->c.btree_id); in bch2_btree_root_alloc_fake_trans()
2637 six_unlock_write(&b->c.lock); in bch2_btree_root_alloc_fake_trans()
2638 six_unlock_intent(&b->c.lock); in bch2_btree_root_alloc_fake_trans()
2649 prt_printf(out, "%ps: ", (void *) as->ip_started); in bch2_btree_update_to_text()
2650 bch2_trans_commit_flags_to_text(out, as->flags); in bch2_btree_update_to_text()
2653 bch2_btree_id_to_text(out, as->btree_id); in bch2_btree_update_to_text()
2654 prt_printf(out, " l=%u-%u mode=%s nodes_written=%u cl.remaining=%u journal_seq=%llu\n", in bch2_btree_update_to_text()
2655 as->update_level_start, in bch2_btree_update_to_text()
2656 as->update_level_end, in bch2_btree_update_to_text()
2657 bch2_btree_update_modes[as->mode], in bch2_btree_update_to_text()
2658 as->nodes_written, in bch2_btree_update_to_text()
2659 closure_nr_remaining(&as->cl), in bch2_btree_update_to_text()
2660 as->journal.seq); in bch2_btree_update_to_text()
2667 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_updates_to_text()
2668 list_for_each_entry(as, &c->btree_interior_update_list, list) in bch2_btree_updates_to_text()
2670 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_updates_to_text()
2677 mutex_lock(&c->btree_interior_update_lock); in bch2_btree_interior_updates_pending()
2678 ret = !list_empty(&c->btree_interior_update_list); in bch2_btree_interior_updates_pending()
2679 mutex_unlock(&c->btree_interior_update_lock); in bch2_btree_interior_updates_pending()
2689 closure_wait_event(&c->btree_interior_update_wait, in bch2_btree_interior_updates_flush()
2696 struct btree_root *r = bch2_btree_id_root(c, entry->btree_id); in bch2_journal_entry_to_btree_root()
2698 mutex_lock(&c->btree_root_lock); in bch2_journal_entry_to_btree_root()
2700 r->level = entry->level; in bch2_journal_entry_to_btree_root()
2701 r->alive = true; in bch2_journal_entry_to_btree_root()
2702 bkey_copy(&r->key, (struct bkey_i *) entry->start); in bch2_journal_entry_to_btree_root()
2704 mutex_unlock(&c->btree_root_lock); in bch2_journal_entry_to_btree_root()
2714 mutex_lock(&c->btree_root_lock); in bch2_btree_roots_to_journal_entries()
2719 if (r->alive && !test_bit(i, &skip)) { in bch2_btree_roots_to_journal_entries()
2721 i, r->level, &r->key, r->key.k.u64s); in bch2_btree_roots_to_journal_entries()
2726 mutex_unlock(&c->btree_root_lock); in bch2_btree_roots_to_journal_entries()
2736 bch2_bkey_val_to_text(out, c, bkey_i_to_s_c(&a->k)); in bch2_btree_alloc_to_text()
2741 open_bucket_for_each(c, &a->ob, ob, i) in bch2_btree_alloc_to_text()
2749 for (unsigned i = 0; i < c->btree_reserve_cache_nr; i++) in bch2_btree_reserve_cache_to_text()
2750 bch2_btree_alloc_to_text(out, c, &c->btree_reserve_cache[i]); in bch2_btree_reserve_cache_to_text()
2755 WARN_ON(!list_empty(&c->btree_node_rewrites)); in bch2_fs_btree_interior_update_exit()
2756 WARN_ON(!list_empty(&c->btree_node_rewrites_pending)); in bch2_fs_btree_interior_update_exit()
2758 if (c->btree_node_rewrite_worker) in bch2_fs_btree_interior_update_exit()
2759 destroy_workqueue(c->btree_node_rewrite_worker); in bch2_fs_btree_interior_update_exit()
2760 if (c->btree_interior_update_worker) in bch2_fs_btree_interior_update_exit()
2761 destroy_workqueue(c->btree_interior_update_worker); in bch2_fs_btree_interior_update_exit()
2762 mempool_exit(&c->btree_interior_update_pool); in bch2_fs_btree_interior_update_exit()
2767 mutex_init(&c->btree_reserve_cache_lock); in bch2_fs_btree_interior_update_init_early()
2768 INIT_LIST_HEAD(&c->btree_interior_update_list); in bch2_fs_btree_interior_update_init_early()
2769 INIT_LIST_HEAD(&c->btree_interior_updates_unwritten); in bch2_fs_btree_interior_update_init_early()
2770 mutex_init(&c->btree_interior_update_lock); in bch2_fs_btree_interior_update_init_early()
2771 INIT_WORK(&c->btree_interior_update_work, btree_interior_update_work); in bch2_fs_btree_interior_update_init_early()
2773 INIT_LIST_HEAD(&c->btree_node_rewrites); in bch2_fs_btree_interior_update_init_early()
2774 INIT_LIST_HEAD(&c->btree_node_rewrites_pending); in bch2_fs_btree_interior_update_init_early()
2775 spin_lock_init(&c->btree_node_rewrites_lock); in bch2_fs_btree_interior_update_init_early()
2780 c->btree_interior_update_worker = in bch2_fs_btree_interior_update_init()
2782 if (!c->btree_interior_update_worker) in bch2_fs_btree_interior_update_init()
2783 return -BCH_ERR_ENOMEM_btree_interior_update_worker_init; in bch2_fs_btree_interior_update_init()
2785 c->btree_node_rewrite_worker = in bch2_fs_btree_interior_update_init()
2787 if (!c->btree_node_rewrite_worker) in bch2_fs_btree_interior_update_init()
2788 return -BCH_ERR_ENOMEM_btree_interior_update_worker_init; in bch2_fs_btree_interior_update_init()
2790 if (mempool_init_kmalloc_pool(&c->btree_interior_update_pool, 1, in bch2_fs_btree_interior_update_init()
2792 return -BCH_ERR_ENOMEM_btree_interior_update_pool_init; in bch2_fs_btree_interior_update_init()