13  * For managing keys we read from the journal: until journal replay works normal
14  * btree lookups need to be able to find and return keys from the journal where
19 static inline size_t pos_to_idx(struct journal_keys *keys, size_t pos)  in pos_to_idx()  argument
21 	size_t gap_size = keys->size - keys->nr;  in pos_to_idx()
23 	BUG_ON(pos >= keys->gap && pos < keys->gap + gap_size);  in pos_to_idx()
25 	if (pos >= keys->gap)  in pos_to_idx()
30 static inline size_t idx_to_pos(struct journal_keys *keys, size_t idx)  in idx_to_pos()  argument
32 	size_t gap_size = keys->size - keys->nr;  in idx_to_pos()
34 	if (idx >= keys->gap)  in idx_to_pos()
39 static inline struct journal_key *idx_to_key(struct journal_keys *keys, size_t idx)  in idx_to_key()  argument
41 	return keys->data + idx_to_pos(keys, idx);  in idx_to_key()
44 static size_t __bch2_journal_key_search(struct journal_keys *keys,  in __bch2_journal_key_search()  argument
48 	size_t l = 0, r = keys->nr, m;  in __bch2_journal_key_search()
52 		if (__journal_key_cmp(id, level, pos, idx_to_key(keys, m)) > 0)  in __bch2_journal_key_search()
58 	BUG_ON(l < keys->nr &&  in __bch2_journal_key_search()
59 	       __journal_key_cmp(id, level, pos, idx_to_key(keys, l)) > 0);  in __bch2_journal_key_search()
62 	       __journal_key_cmp(id, level, pos, idx_to_key(keys, l - 1)) <= 0);  in __bch2_journal_key_search()
67 static size_t bch2_journal_key_search(struct journal_keys *keys,  in bch2_journal_key_search()  argument
71 	return idx_to_pos(keys, __bch2_journal_key_search(keys, id, level, pos));  in bch2_journal_key_search()
79 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_peek_max()  local
83 	BUG_ON(*idx > keys->nr);  in bch2_journal_keys_peek_max()
86 		*idx = __bch2_journal_key_search(keys, btree_id, level, pos);  in bch2_journal_keys_peek_max()
89 	       __journal_key_cmp(btree_id, level, end_pos, idx_to_key(keys, *idx - 1)) <= 0) {  in bch2_journal_keys_peek_max()
101 	while ((k = *idx < keys->nr ? idx_to_key(keys, *idx) : NULL)) {  in bch2_journal_keys_peek_max()
135 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_peek_prev_min()  local
139 	BUG_ON(*idx > keys->nr);  in bch2_journal_keys_peek_prev_min()
141 	if (!keys->nr)  in bch2_journal_keys_peek_prev_min()
145 		*idx = __bch2_journal_key_search(keys, btree_id, level, pos);  in bch2_journal_keys_peek_prev_min()
147 	while (*idx < keys->nr &&  in bch2_journal_keys_peek_prev_min()
148 	       __journal_key_cmp(btree_id, level, end_pos, idx_to_key(keys, *idx)) >= 0) {  in bch2_journal_keys_peek_prev_min()
157 	if (*idx == keys->nr)  in bch2_journal_keys_peek_prev_min()
164 		k = idx_to_key(keys, *idx);  in bch2_journal_keys_peek_prev_min()
207 	struct journal_keys *keys = iter->keys;  in journal_iter_verify()  local
208 	size_t gap_size = keys->size - keys->nr;  in journal_iter_verify()
210 	BUG_ON(iter->idx >= keys->gap &&  in journal_iter_verify()
211 	       iter->idx <  keys->gap + gap_size);  in journal_iter_verify()
213 	if (iter->idx < keys->size) {  in journal_iter_verify()
214 		struct journal_key *k = keys->data + iter->idx;  in journal_iter_verify()
224 	struct journal_keys *keys = &c->journal_keys;  in journal_iters_fix()  local
226 	size_t gap_end = keys->gap + (keys->size - keys->nr);  in journal_iters_fix()
227 	struct journal_key *new_key = &keys->data[keys->gap - 1];  in journal_iters_fix()
241 			iter->idx = keys->gap - 1;  in journal_iters_fix()
248 	struct journal_keys *keys = &c->journal_keys;  in journal_iters_move_gap()  local
250 	size_t gap_size = keys->size - keys->nr;  in journal_iters_move_gap()
269 		 * Ensure these keys are done last by journal replay, to unblock  in bch2_journal_key_insert_take()
274 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_key_insert_take()  local
275 	size_t idx = bch2_journal_key_search(keys, id, level, k->k.p);  in bch2_journal_key_insert_take()
279 	if (idx < keys->size &&  in bch2_journal_key_insert_take()
280 	    journal_key_cmp(&n, &keys->data[idx]) == 0) {  in bch2_journal_key_insert_take()
281 		if (keys->data[idx].allocated)  in bch2_journal_key_insert_take()
282 			kfree(keys->data[idx].k);  in bch2_journal_key_insert_take()
283 		keys->data[idx] = n;  in bch2_journal_key_insert_take()
287 	if (idx > keys->gap)  in bch2_journal_key_insert_take()
288 		idx -= keys->size - keys->nr;  in bch2_journal_key_insert_take()
290 	size_t old_gap = keys->gap;  in bch2_journal_key_insert_take()
292 	if (keys->nr == keys->size) {  in bch2_journal_key_insert_take()
293 		journal_iters_move_gap(c, old_gap, keys->size);  in bch2_journal_key_insert_take()
294 		old_gap = keys->size;  in bch2_journal_key_insert_take()
297 			.nr			= keys->nr,  in bch2_journal_key_insert_take()
298 			.size			= max_t(size_t, keys->size, 8) * 2,  in bch2_journal_key_insert_take()
308 		/* Since @keys was full, there was no gap: */  in bch2_journal_key_insert_take()
309 		memcpy(new_keys.data, keys->data, sizeof(keys->data[0]) * keys->nr);  in bch2_journal_key_insert_take()
310 		kvfree(keys->data);  in bch2_journal_key_insert_take()
311 		keys->data	= new_keys.data;  in bch2_journal_key_insert_take()
312 		keys->nr	= new_keys.nr;  in bch2_journal_key_insert_take()
313 		keys->size	= new_keys.size;  in bch2_journal_key_insert_take()
316 		keys->gap	= keys->nr;  in bch2_journal_key_insert_take()
321 	move_gap(keys, idx);  in bch2_journal_key_insert_take()
323 	keys->nr++;  in bch2_journal_key_insert_take()
324 	keys->data[keys->gap++] = n;  in bch2_journal_key_insert_take()
367 	struct journal_keys *keys = &trans->c->journal_keys;  in bch2_key_deleted_in_journal()  local
368 	size_t idx = bch2_journal_key_search(keys, btree, level, pos);  in bch2_key_deleted_in_journal()
373 	return (idx < keys->size &&  in bch2_key_deleted_in_journal()
374 		keys->data[idx].btree_id	== btree &&  in bch2_key_deleted_in_journal()
375 		keys->data[idx].level		== level &&  in bch2_key_deleted_in_journal()
376 		bpos_eq(keys->data[idx].k->k.p, pos) &&  in bch2_key_deleted_in_journal()
377 		bkey_deleted(&keys->data[idx].k->k));  in bch2_key_deleted_in_journal()
380 static void __bch2_journal_key_overwritten(struct journal_keys *keys, size_t pos)  in __bch2_journal_key_overwritten()  argument
382 	struct journal_key *k = keys->data + pos;  in __bch2_journal_key_overwritten()
383 	size_t idx = pos_to_idx(keys, pos);  in __bch2_journal_key_overwritten()
387 	struct journal_key *prev = idx > 0 ? keys->data + idx_to_pos(keys, idx - 1) : NULL;  in __bch2_journal_key_overwritten()
388 	struct journal_key *next = idx + 1 < keys->nr ? keys->data + idx_to_pos(keys, idx + 1) : NULL;  in __bch2_journal_key_overwritten()
404 		keys->data[pos].overwritten_range = prev_range;  in __bch2_journal_key_overwritten()
406 			struct journal_key *ip = keys->data + idx_to_pos(keys, i);  in __bch2_journal_key_overwritten()
445 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_key_overwritten()  local
446 	size_t idx = bch2_journal_key_search(keys, btree, level, pos);  in bch2_journal_key_overwritten()
448 	if (idx < keys->size &&  in bch2_journal_key_overwritten()
449 	    keys->data[idx].btree_id	== btree &&  in bch2_journal_key_overwritten()
450 	    keys->data[idx].level	== level &&  in bch2_journal_key_overwritten()
451 	    bpos_eq(keys->data[idx].k->k.p, pos) &&  in bch2_journal_key_overwritten()
452 	    !keys->data[idx].overwritten) {  in bch2_journal_key_overwritten()
453 		mutex_lock(&keys->overwrite_lock);  in bch2_journal_key_overwritten()
454 		__bch2_journal_key_overwritten(keys, idx);  in bch2_journal_key_overwritten()
455 		mutex_unlock(&keys->overwrite_lock);  in bch2_journal_key_overwritten()
461 	if (iter->idx < iter->keys->size) {  in bch2_journal_iter_advance()
463 		if (iter->idx == iter->keys->gap)  in bch2_journal_iter_advance()
464 			iter->idx += iter->keys->size - iter->keys->nr;  in bch2_journal_iter_advance()
473 	while (iter->idx < iter->keys->size) {  in bch2_journal_iter_peek()
474 		struct journal_key *k = iter->keys->data + iter->idx;  in bch2_journal_iter_peek()
485 			iter->idx = idx_to_pos(iter->keys, rcu_dereference(k->overwritten_range)->end);  in bch2_journal_iter_peek()
505 	iter->keys	= &c->journal_keys;  in bch2_journal_iter_init()
645 /* sort and dedup all keys in the journal: */
648  * When keys compare equal, oldest compares first:
663 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_put()  local
665 	BUG_ON(atomic_read(&keys->ref) <= 0);  in bch2_journal_keys_put()
667 	if (!atomic_dec_and_test(&keys->ref))  in bch2_journal_keys_put()
670 	move_gap(keys, keys->nr);  in bch2_journal_keys_put()
672 	darray_for_each(*keys, i) {  in bch2_journal_keys_put()
674 		    (i == &darray_last(*keys) ||  in bch2_journal_keys_put()
682 	kvfree(keys->data);  in bch2_journal_keys_put()
683 	keys->data = NULL;  in bch2_journal_keys_put()
684 	keys->nr = keys->gap = keys->size = 0;  in bch2_journal_keys_put()
694 static void __journal_keys_sort(struct journal_keys *keys)  in __journal_keys_sort()  argument
696 	sort_nonatomic(keys->data, keys->nr, sizeof(keys->data[0]),  in __journal_keys_sort()
701 	struct journal_key *dst = keys->data;  in __journal_keys_sort()
703 	darray_for_each(*keys, src) {  in __journal_keys_sort()
705 		 * We don't accumulate accounting keys here because we have to  in __journal_keys_sort()
710 		    src + 1 < &darray_top(*keys) &&  in __journal_keys_sort()
717 	keys->nr = dst - keys->data;  in __journal_keys_sort()
724 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_sort()  local
760 				if (darray_push(keys, n)) {  in bch2_journal_keys_sort()
761 					__journal_keys_sort(keys);  in bch2_journal_keys_sort()
763 					if (keys->nr * 8 > keys->size * 7) {  in bch2_journal_keys_sort()
764 …bch_err(c, "Too many journal keys for slowpath; have %zu compacted, buf size %zu, processed %zu ke…  in bch2_journal_keys_sort()
765 							keys->nr, keys->size, nr_read, le64_to_cpu(i->j.seq));  in bch2_journal_keys_sort()
769 					BUG_ON(darray_push(keys, n));  in bch2_journal_keys_sort()
777 	__journal_keys_sort(keys);  in bch2_journal_keys_sort()
778 	keys->gap = keys->nr;  in bch2_journal_keys_sort()
780 	bch_verbose(c, "Journal keys: %zu read, %zu after sorting and compacting", nr_read, keys->nr);  in bch2_journal_keys_sort()
788 	struct journal_keys *keys = &c->journal_keys;  in bch2_shoot_down_journal_keys()  local
791 	move_gap(keys, keys->nr);  in bch2_shoot_down_journal_keys()
793 	darray_for_each(*keys, i)  in bch2_shoot_down_journal_keys()
799 			keys->data[dst++] = *i;  in bch2_shoot_down_journal_keys()
800 	keys->nr = keys->gap = dst;  in bch2_shoot_down_journal_keys()
805 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_dump()  local
808 	pr_info("%zu keys:", keys->nr);  in bch2_journal_keys_dump()
810 	move_gap(keys, keys->nr);  in bch2_journal_keys_dump()
812 	darray_for_each(*keys, i) {  in bch2_journal_keys_dump()
825 	struct journal_keys *keys = &c->journal_keys;  in bch2_fs_journal_keys_init()  local
827 	atomic_set(&keys->ref, 1);  in bch2_fs_journal_keys_init()
828 	keys->initial_ref_held = true;  in bch2_fs_journal_keys_init()
829 	mutex_init(&keys->overwrite_lock);  in bch2_fs_journal_keys_init()