11  * For managing keys we read from the journal: until journal replay works normal
12  * btree lookups need to be able to find and return keys from the journal where
32 static inline size_t idx_to_pos(struct journal_keys *keys, size_t idx)  in idx_to_pos()  argument
34 	size_t gap_size = keys->size - keys->nr;  in idx_to_pos()
36 	if (idx >= keys->gap)  in idx_to_pos()
41 static inline struct journal_key *idx_to_key(struct journal_keys *keys, size_t idx)  in idx_to_key()  argument
43 	return keys->d + idx_to_pos(keys, idx);  in idx_to_key()
46 static size_t __bch2_journal_key_search(struct journal_keys *keys,  in __bch2_journal_key_search()  argument
50 	size_t l = 0, r = keys->nr, m;  in __bch2_journal_key_search()
54 		if (__journal_key_cmp(id, level, pos, idx_to_key(keys, m)) > 0)  in __bch2_journal_key_search()
60 	BUG_ON(l < keys->nr &&  in __bch2_journal_key_search()
61 	       __journal_key_cmp(id, level, pos, idx_to_key(keys, l)) > 0);  in __bch2_journal_key_search()
64 	       __journal_key_cmp(id, level, pos, idx_to_key(keys, l - 1)) <= 0);  in __bch2_journal_key_search()
69 static size_t bch2_journal_key_search(struct journal_keys *keys,  in bch2_journal_key_search()  argument
73 	return idx_to_pos(keys, __bch2_journal_key_search(keys, id, level, pos));  in bch2_journal_key_search()
81 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_peek_upto()  local
85 	BUG_ON(*idx > keys->nr);  in bch2_journal_keys_peek_upto()
88 		*idx = __bch2_journal_key_search(keys, btree_id, level, pos);  in bch2_journal_keys_peek_upto()
91 	       __journal_key_cmp(btree_id, level, end_pos, idx_to_key(keys, *idx - 1)) <= 0) {  in bch2_journal_keys_peek_upto()
100 	while ((k = *idx < keys->nr ? idx_to_key(keys, *idx) : NULL)) {  in bch2_journal_keys_peek_upto()
133 	struct journal_keys *keys = &c->journal_keys;  in journal_iters_fix()  local
135 	size_t gap_end = keys->gap + (keys->size - keys->nr);  in journal_iters_fix()
146 			iter->journal.idx = keys->gap - 1;  in journal_iters_fix()
151 	struct journal_keys *keys = &c->journal_keys;  in journal_iters_move_gap()  local
153 	size_t gap_size = keys->size - keys->nr;  in journal_iters_move_gap()
172 		 * Ensure these keys are done last by journal replay, to unblock  in bch2_journal_key_insert_take()
177 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_key_insert_take()  local
178 	size_t idx = bch2_journal_key_search(keys, id, level, k->k.p);  in bch2_journal_key_insert_take()
182 	if (idx < keys->size &&  in bch2_journal_key_insert_take()
183 	    journal_key_cmp(&n, &keys->d[idx]) == 0) {  in bch2_journal_key_insert_take()
184 		if (keys->d[idx].allocated)  in bch2_journal_key_insert_take()
185 			kfree(keys->d[idx].k);  in bch2_journal_key_insert_take()
186 		keys->d[idx] = n;  in bch2_journal_key_insert_take()
190 	if (idx > keys->gap)  in bch2_journal_key_insert_take()
191 		idx -= keys->size - keys->nr;  in bch2_journal_key_insert_take()
193 	if (keys->nr == keys->size) {  in bch2_journal_key_insert_take()
195 			.nr			= keys->nr,  in bch2_journal_key_insert_take()
196 			.size			= max_t(size_t, keys->size, 8) * 2,  in bch2_journal_key_insert_take()
206 		/* Since @keys was full, there was no gap: */  in bch2_journal_key_insert_take()
207 		memcpy(new_keys.d, keys->d, sizeof(keys->d[0]) * keys->nr);  in bch2_journal_key_insert_take()
208 		kvfree(keys->d);  in bch2_journal_key_insert_take()
209 		keys->d		= new_keys.d;  in bch2_journal_key_insert_take()
210 		keys->nr	= new_keys.nr;  in bch2_journal_key_insert_take()
211 		keys->size	= new_keys.size;  in bch2_journal_key_insert_take()
214 		keys->gap	= keys->nr;  in bch2_journal_key_insert_take()
217 	journal_iters_move_gap(c, keys->gap, idx);  in bch2_journal_key_insert_take()
219 	move_gap(keys->d, keys->nr, keys->size, keys->gap, idx);  in bch2_journal_key_insert_take()
220 	keys->gap = idx;  in bch2_journal_key_insert_take()
222 	keys->nr++;  in bch2_journal_key_insert_take()
223 	keys->d[keys->gap++] = n;  in bch2_journal_key_insert_take()
266 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_key_overwritten()  local
267 	size_t idx = bch2_journal_key_search(keys, btree, level, pos);  in bch2_journal_key_overwritten()
269 	if (idx < keys->size &&  in bch2_journal_key_overwritten()
270 	    keys->d[idx].btree_id	== btree &&  in bch2_journal_key_overwritten()
271 	    keys->d[idx].level		== level &&  in bch2_journal_key_overwritten()
272 	    bpos_eq(keys->d[idx].k->k.p, pos))  in bch2_journal_key_overwritten()
273 		keys->d[idx].overwritten = true;  in bch2_journal_key_overwritten()
278 	if (iter->idx < iter->keys->size) {  in bch2_journal_iter_advance()
280 		if (iter->idx == iter->keys->gap)  in bch2_journal_iter_advance()
281 			iter->idx += iter->keys->size - iter->keys->nr;  in bch2_journal_iter_advance()
287 	struct journal_key *k = iter->keys->d + iter->idx;  in bch2_journal_iter_peek()
289 	while (k < iter->keys->d + iter->keys->size &&  in bch2_journal_iter_peek()
296 		k = iter->keys->d + iter->idx;  in bch2_journal_iter_peek()
314 	iter->keys	= &c->journal_keys;  in bch2_journal_iter_init()
410 /* sort and dedup all keys in the journal: */
425  * When keys compare equal, oldest compares first:
439 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_put()  local
442 	BUG_ON(atomic_read(&keys->ref) <= 0);  in bch2_journal_keys_put()
444 	if (!atomic_dec_and_test(&keys->ref))  in bch2_journal_keys_put()
447 	move_gap(keys->d, keys->nr, keys->size, keys->gap, keys->nr);  in bch2_journal_keys_put()
448 	keys->gap = keys->nr;  in bch2_journal_keys_put()
450 	for (i = keys->d; i < keys->d + keys->nr; i++)  in bch2_journal_keys_put()
454 	kvfree(keys->d);  in bch2_journal_keys_put()
455 	keys->d = NULL;  in bch2_journal_keys_put()
456 	keys->nr = keys->gap = keys->size = 0;  in bch2_journal_keys_put()
461 static void __journal_keys_sort(struct journal_keys *keys)  in __journal_keys_sort()  argument
465 	sort(keys->d, keys->nr, sizeof(keys->d[0]), journal_sort_key_cmp, NULL);  in __journal_keys_sort()
467 	src = dst = keys->d;  in __journal_keys_sort()
468 	while (src < keys->d + keys->nr) {  in __journal_keys_sort()
469 		while (src + 1 < keys->d + keys->nr &&  in __journal_keys_sort()
476 	keys->nr = dst - keys->d;  in __journal_keys_sort()
485 	struct journal_keys *keys = &c->journal_keys;  in bch2_journal_keys_sort()  local
501 	keys->size = roundup_pow_of_two(nr_keys);  in bch2_journal_keys_sort()
503 	keys->d = kvmalloc_array(keys->size, sizeof(keys->d[0]), GFP_KERNEL);  in bch2_journal_keys_sort()
504 	if (!keys->d) {  in bch2_journal_keys_sort()
505 		bch_err(c, "Failed to allocate buffer for sorted journal keys (%zu keys); trying slowpath",  in bch2_journal_keys_sort()
509 			keys->size >>= 1;  in bch2_journal_keys_sort()
510 			keys->d = kvmalloc_array(keys->size, sizeof(keys->d[0]), GFP_KERNEL);  in bch2_journal_keys_sort()
511 		} while (!keys->d && keys->size > nr_keys / 8);  in bch2_journal_keys_sort()
513 		if (!keys->d) {  in bch2_journal_keys_sort()
514 			bch_err(c, "Failed to allocate %zu size buffer for sorted journal keys; exiting",  in bch2_journal_keys_sort()
515 				keys->size);  in bch2_journal_keys_sort()
529 			if (keys->nr == keys->size) {  in bch2_journal_keys_sort()
530 				__journal_keys_sort(keys);  in bch2_journal_keys_sort()
532 				if (keys->nr > keys->size * 7 / 8) {  in bch2_journal_keys_sort()
533 …bch_err(c, "Too many journal keys for slowpath; have %zu compacted, buf size %zu, processed %zu/%z…  in bch2_journal_keys_sort()
534 						keys->nr, keys->size, nr_read, nr_keys);  in bch2_journal_keys_sort()
539 			keys->d[keys->nr++] = (struct journal_key) {  in bch2_journal_keys_sort()
551 	__journal_keys_sort(keys);  in bch2_journal_keys_sort()
552 	keys->gap = keys->nr;  in bch2_journal_keys_sort()
554 	bch_verbose(c, "Journal keys: %zu read, %zu after sorting and compacting", nr_keys, keys->nr);  in bch2_journal_keys_sort()