256 lines · c
1// SPDX-License-Identifier: GPL-2.02 3#include "bcachefs.h"4#include "eytzinger.h"5#include "journal.h"6#include "journal_seq_blacklist.h"7#include "super-io.h"8 9/*10 * journal_seq_blacklist machinery:11 *12 * To guarantee order of btree updates after a crash, we need to detect when a13 * btree node entry (bset) is newer than the newest journal entry that was14 * successfully written, and ignore it - effectively ignoring any btree updates15 * that didn't make it into the journal.16 *17 * If we didn't do this, we might have two btree nodes, a and b, both with18 * updates that weren't written to the journal yet: if b was updated after a,19 * but b was flushed and not a - oops; on recovery we'll find that the updates20 * to b happened, but not the updates to a that happened before it.21 *22 * Ignoring bsets that are newer than the newest journal entry is always safe,23 * because everything they contain will also have been journalled - and must24 * still be present in the journal on disk until a journal entry has been25 * written _after_ that bset was written.26 *27 * To accomplish this, bsets record the newest journal sequence number they28 * contain updates for; then, on startup, the btree code queries the journal29 * code to ask "Is this sequence number newer than the newest journal entry? If30 * so, ignore it."31 *32 * When this happens, we must blacklist that journal sequence number: the33 * journal must not write any entries with that sequence number, and it must34 * record that it was blacklisted so that a) on recovery we don't think we have35 * missing journal entries and b) so that the btree code continues to ignore36 * that bset, until that btree node is rewritten.37 */38 39static unsigned sb_blacklist_u64s(unsigned nr)40{41 struct bch_sb_field_journal_seq_blacklist *bl;42 43 return (sizeof(*bl) + sizeof(bl->start[0]) * nr) / sizeof(u64);44}45 46int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end)47{48 struct bch_sb_field_journal_seq_blacklist *bl;49 unsigned i = 0, nr;50 int ret = 0;51 52 mutex_lock(&c->sb_lock);53 bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);54 nr = blacklist_nr_entries(bl);55 56 while (i < nr) {57 struct journal_seq_blacklist_entry *e =58 bl->start + i;59 60 if (end < le64_to_cpu(e->start))61 break;62 63 if (start > le64_to_cpu(e->end)) {64 i++;65 continue;66 }67 68 /*69 * Entry is contiguous or overlapping with new entry: merge it70 * with new entry, and delete:71 */72 73 start = min(start, le64_to_cpu(e->start));74 end = max(end, le64_to_cpu(e->end));75 array_remove_item(bl->start, nr, i);76 }77 78 bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,79 sb_blacklist_u64s(nr + 1));80 if (!bl) {81 ret = -BCH_ERR_ENOSPC_sb_journal_seq_blacklist;82 goto out;83 }84 85 array_insert_item(bl->start, nr, i, ((struct journal_seq_blacklist_entry) {86 .start = cpu_to_le64(start),87 .end = cpu_to_le64(end),88 }));89 c->disk_sb.sb->features[0] |= cpu_to_le64(1ULL << BCH_FEATURE_journal_seq_blacklist_v3);90 91 ret = bch2_write_super(c);92out:93 mutex_unlock(&c->sb_lock);94 95 return ret ?: bch2_blacklist_table_initialize(c);96}97 98static int journal_seq_blacklist_table_cmp(const void *_l, const void *_r)99{100 const struct journal_seq_blacklist_table_entry *l = _l;101 const struct journal_seq_blacklist_table_entry *r = _r;102 103 return cmp_int(l->start, r->start);104}105 106bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq,107 bool dirty)108{109 struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;110 struct journal_seq_blacklist_table_entry search = { .start = seq };111 int idx;112 113 if (!t)114 return false;115 116 idx = eytzinger0_find_le(t->entries, t->nr,117 sizeof(t->entries[0]),118 journal_seq_blacklist_table_cmp,119 &search);120 if (idx < 0)121 return false;122 123 BUG_ON(t->entries[idx].start > seq);124 125 if (seq >= t->entries[idx].end)126 return false;127 128 if (dirty)129 t->entries[idx].dirty = true;130 return true;131}132 133int bch2_blacklist_table_initialize(struct bch_fs *c)134{135 struct bch_sb_field_journal_seq_blacklist *bl =136 bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);137 struct journal_seq_blacklist_table *t;138 unsigned i, nr = blacklist_nr_entries(bl);139 140 if (!bl)141 return 0;142 143 t = kzalloc(struct_size(t, entries, nr), GFP_KERNEL);144 if (!t)145 return -BCH_ERR_ENOMEM_blacklist_table_init;146 147 t->nr = nr;148 149 for (i = 0; i < nr; i++) {150 t->entries[i].start = le64_to_cpu(bl->start[i].start);151 t->entries[i].end = le64_to_cpu(bl->start[i].end);152 }153 154 eytzinger0_sort(t->entries,155 t->nr,156 sizeof(t->entries[0]),157 journal_seq_blacklist_table_cmp,158 NULL);159 160 kfree(c->journal_seq_blacklist_table);161 c->journal_seq_blacklist_table = t;162 return 0;163}164 165static int bch2_sb_journal_seq_blacklist_validate(struct bch_sb *sb, struct bch_sb_field *f,166 enum bch_validate_flags flags, struct printbuf *err)167{168 struct bch_sb_field_journal_seq_blacklist *bl =169 field_to_type(f, journal_seq_blacklist);170 unsigned i, nr = blacklist_nr_entries(bl);171 172 for (i = 0; i < nr; i++) {173 struct journal_seq_blacklist_entry *e = bl->start + i;174 175 if (le64_to_cpu(e->start) >=176 le64_to_cpu(e->end)) {177 prt_printf(err, "entry %u start >= end (%llu >= %llu)",178 i, le64_to_cpu(e->start), le64_to_cpu(e->end));179 return -BCH_ERR_invalid_sb_journal_seq_blacklist;180 }181 182 if (i + 1 < nr &&183 le64_to_cpu(e[0].end) >184 le64_to_cpu(e[1].start)) {185 prt_printf(err, "entry %u out of order with next entry (%llu > %llu)",186 i + 1, le64_to_cpu(e[0].end), le64_to_cpu(e[1].start));187 return -BCH_ERR_invalid_sb_journal_seq_blacklist;188 }189 }190 191 return 0;192}193 194static void bch2_sb_journal_seq_blacklist_to_text(struct printbuf *out,195 struct bch_sb *sb,196 struct bch_sb_field *f)197{198 struct bch_sb_field_journal_seq_blacklist *bl =199 field_to_type(f, journal_seq_blacklist);200 struct journal_seq_blacklist_entry *i;201 unsigned nr = blacklist_nr_entries(bl);202 203 for (i = bl->start; i < bl->start + nr; i++) {204 if (i != bl->start)205 prt_printf(out, " ");206 207 prt_printf(out, "%llu-%llu",208 le64_to_cpu(i->start),209 le64_to_cpu(i->end));210 }211 prt_newline(out);212}213 214const struct bch_sb_field_ops bch_sb_field_ops_journal_seq_blacklist = {215 .validate = bch2_sb_journal_seq_blacklist_validate,216 .to_text = bch2_sb_journal_seq_blacklist_to_text217};218 219bool bch2_blacklist_entries_gc(struct bch_fs *c)220{221 struct journal_seq_blacklist_entry *src, *dst;222 223 struct bch_sb_field_journal_seq_blacklist *bl =224 bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);225 if (!bl)226 return false;227 228 unsigned nr = blacklist_nr_entries(bl);229 dst = bl->start;230 231 struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;232 BUG_ON(nr != t->nr);233 234 unsigned i;235 for (src = bl->start, i = t->nr == 0 ? 0 : eytzinger0_first(t->nr);236 src < bl->start + nr;237 src++, i = eytzinger0_next(i, nr)) {238 BUG_ON(t->entries[i].start != le64_to_cpu(src->start));239 BUG_ON(t->entries[i].end != le64_to_cpu(src->end));240 241 if (t->entries[i].dirty || t->entries[i].end >= c->journal.oldest_seq_found_ondisk)242 *dst++ = *src;243 }244 245 unsigned new_nr = dst - bl->start;246 if (new_nr == nr)247 return false;248 249 bch_verbose(c, "nr blacklist entries was %u, now %u", nr, new_nr);250 251 bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,252 new_nr ? sb_blacklist_u64s(new_nr) : 0);253 BUG_ON(new_nr && !bl);254 return true;255}256