1 files changed, 85 insertions, 58 deletions

diff --git a/fs/bcachefs/disk_accounting.c b/fs/bcachefs/disk_accounting.c
index 5944ad6d0f8d..809c76b68ba8 100644
--- a/fs/bcachefs/disk_accounting.c
+++ b/fs/bcachefs/disk_accounting.c
@@ -734,6 +734,37 @@ invalid_device:
 	goto fsck_err;
 }
 
+static struct journal_key *accumulate_newer_accounting_keys(struct bch_fs *c, struct journal_key *i)
+{
+	struct journal_keys *keys = &c->journal_keys;
+	struct bkey_i *k = journal_key_k(c, i);
+
+	darray_for_each_from(*keys, j, i + 1) {
+		if (journal_key_cmp(c, i, j))
+			return j;
+
+		struct bkey_i *n = journal_key_k(c, j);
+		if (n->k.type == KEY_TYPE_accounting) {
+			WARN_ON(bversion_cmp(k->k.bversion, n->k.bversion) >= 0);
+
+			bch2_accounting_accumulate(bkey_i_to_accounting(k),
+						   bkey_i_to_s_c_accounting(n));
+			j->overwritten = true;
+		}
+	}
+
+	return &darray_top(*keys);
+}
+
+static struct journal_key *accumulate_and_read_journal_accounting(struct btree_trans *trans, struct journal_key *i)
+{
+	struct bch_fs *c = trans->c;
+	struct journal_key *next = accumulate_newer_accounting_keys(c, i);
+
+	int ret = accounting_read_key(trans, bkey_i_to_s_c(journal_key_k(c, i)));
+	return ret ? ERR_PTR(ret) : next;
+}
+
 /*
  * At startup time, initialize the in memory accounting from the btree (and
  * journal)
@@ -759,80 +790,76 @@ int bch2_accounting_read(struct bch_fs *c)
 		percpu_memset(c->usage, 0, sizeof(*c->usage));
 	}
 
+	struct journal_keys *keys = &c->journal_keys;
+	struct journal_key *jk = keys->data;
+
+	while (jk < &darray_top(*keys) &&
+	       __journal_key_cmp(c, BTREE_ID_accounting, 0, POS_MIN, jk) > 0)
+		jk++;
+
+	struct journal_key *end = jk;
+	while (end < &darray_top(*keys) &&
+	       __journal_key_cmp(c, BTREE_ID_accounting, 0, SPOS_MAX, end) > 0)
+		end++;
+
 	struct btree_iter iter;
 	bch2_trans_iter_init(trans, &iter, BTREE_ID_accounting, POS_MIN,
 			     BTREE_ITER_prefetch|BTREE_ITER_all_snapshots);
 	iter.flags &= ~BTREE_ITER_with_journal;
 	int ret = for_each_btree_key_continue(trans, iter,
 				BTREE_ITER_prefetch|BTREE_ITER_all_snapshots, k, ({
-			struct bkey u;
-			struct bkey_s_c k = bch2_btree_path_peek_slot_exact(btree_iter_path(trans, &iter), &u);
-
-			if (k.k->type != KEY_TYPE_accounting)
-				continue;
-
-			struct disk_accounting_pos acc_k;
-			bpos_to_disk_accounting_pos(&acc_k, k.k->p);
-
-			if (acc_k.type >= BCH_DISK_ACCOUNTING_TYPE_NR)
-				break;
-
-			if (!bch2_accounting_is_mem(&acc_k)) {
-				struct disk_accounting_pos next;
-				memset(&next, 0, sizeof(next));
-				next.type = acc_k.type + 1;
-				bch2_btree_iter_set_pos(&iter, disk_accounting_pos_to_bpos(&next));
-				continue;
-			}
+		struct bkey u;
+		struct bkey_s_c k = bch2_btree_path_peek_slot_exact(btree_iter_path(trans, &iter), &u);
 
-			accounting_read_key(trans, k);
-		}));
-	bch2_trans_iter_exit(&iter);
-	if (ret)
-		return ret;
-
-	struct journal_keys *keys = &c->journal_keys;
-	struct journal_key *dst = keys->data;
-	move_gap(keys, keys->nr);
-
-	darray_for_each(*keys, i) {
-		if (i->k->k.type == KEY_TYPE_accounting) {
-			struct disk_accounting_pos acc_k;
-			bpos_to_disk_accounting_pos(&acc_k, i->k->k.p);
+		if (k.k->type != KEY_TYPE_accounting)
+			continue;
 
-			if (!bch2_accounting_is_mem(&acc_k))
-				continue;
+		while (jk < end &&
+		       __journal_key_cmp(c, BTREE_ID_accounting, 0, k.k->p, jk) > 0)
+			jk = accumulate_and_read_journal_accounting(trans, jk);
 
-			struct bkey_s_c k = bkey_i_to_s_c(i->k);
-			unsigned idx = eytzinger0_find(acc->k.data, acc->k.nr,
-						sizeof(acc->k.data[0]),
-						accounting_pos_cmp, &k.k->p);
+		while (jk < end &&
+		       __journal_key_cmp(c, BTREE_ID_accounting, 0, k.k->p, jk) == 0 &&
+		       bversion_cmp(journal_key_k(c, jk)->k.bversion, k.k->bversion) <= 0) {
+			jk->overwritten = true;
+			jk++;
+		}
 
-			bool applied = idx < acc->k.nr &&
-				bversion_cmp(acc->k.data[idx].bversion, k.k->bversion) >= 0;
+		if (jk < end &&
+		    __journal_key_cmp(c, BTREE_ID_accounting, 0, k.k->p, jk) == 0)
+			jk = accumulate_and_read_journal_accounting(trans, jk);
 
-			if (applied)
-				continue;
+		struct disk_accounting_pos acc_k;
+		bpos_to_disk_accounting_pos(&acc_k, k.k->p);
 
-			if (i + 1 < &darray_top(*keys) &&
-			    i[1].k->k.type == KEY_TYPE_accounting &&
-			    !journal_key_cmp(i, i + 1)) {
-				WARN_ON(bversion_cmp(i[0].k->k.bversion, i[1].k->k.bversion) >= 0);
+		if (acc_k.type >= BCH_DISK_ACCOUNTING_TYPE_NR)
+			break;
 
-				i[1].journal_seq = i[0].journal_seq;
+		if (!bch2_accounting_is_mem(&acc_k)) {
+			struct disk_accounting_pos next_acc;
+			memset(&next_acc, 0, sizeof(next_acc));
+			next_acc.type = acc_k.type + 1;
+			struct bpos next = disk_accounting_pos_to_bpos(&next_acc);
+			if (jk < end)
+				next = bpos_min(next, journal_key_k(c, jk)->k.p);
+
+			bch2_btree_iter_set_pos(&iter, next);
+			continue;
+		}
 
-				bch2_accounting_accumulate(bkey_i_to_accounting(i[1].k),
-							   bkey_s_c_to_accounting(k));
-				continue;
-			}
+		accounting_read_key(trans, k);
+	}));
+	bch2_trans_iter_exit(&iter);
+	if (ret)
+		return ret;
 
-			ret = accounting_read_key(trans, k);
-			if (ret)
-				return ret;
-		}
+	while (jk < end)
+		jk = accumulate_and_read_journal_accounting(trans, jk);
 
-		*dst++ = *i;
-	}
+	struct journal_key *dst = keys->data;
+	darray_for_each(*keys, i)
+		if (!i->overwritten)
+			*dst++ = *i;
 	keys->gap = keys->nr = dst - keys->data;
 
 	guard(percpu_write)(&c->mark_lock);