git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/journal_seq_blacklist.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "btree_iter.h"
   5 #include "eytzinger.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 a
  13  * btree node entry (bset) is newer than the newest journal entry that was
  14  * successfully written, and ignore it - effectively ignoring any btree updates
  15  * 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 with
  18  * 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 updates
  20  * 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 must
  24  * still be present in the journal on disk until a journal entry has been
  25  * written _after_ that bset was written.
  26  *
  27  * To accomplish this, bsets record the newest journal sequence number they
  28  * contain updates for; then, on startup, the btree code queries the journal
  29  * code to ask "Is this sequence number newer than the newest journal entry? If
  30  * so, ignore it."
  31  *
  32  * When this happens, we must blacklist that journal sequence number: the
  33  * journal must not write any entries with that sequence number, and it must
  34  * record that it was blacklisted so that a) on recovery we don't think we have
  35  * missing journal entries and b) so that the btree code continues to ignore
  36  * that bset, until that btree node is rewritten.
  37  */
  38
  39 static 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
  46 static struct bch_sb_field_journal_seq_blacklist *
  47 blacklist_entry_try_merge(struct bch_fs *c,
  48                           struct bch_sb_field_journal_seq_blacklist *bl,
  49                           unsigned i)
  50 {
  51         unsigned nr = blacklist_nr_entries(bl);
  52
  53         if (le64_to_cpu(bl->start[i].end) >=
  54             le64_to_cpu(bl->start[i + 1].start)) {
  55                 bl->start[i].end = bl->start[i + 1].end;
  56                 --nr;
  57                 memmove(&bl->start[i],
  58                         &bl->start[i + 1],
  59                         sizeof(bl->start[0]) * (nr - i));
  60
  61                 bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,
  62                                           sb_blacklist_u64s(nr));
  63                 BUG_ON(!bl);
  64         }
  65
  66         return bl;
  67 }
  68
  69 static bool bl_entry_contig_or_overlaps(struct journal_seq_blacklist_entry *e,
  70                                         u64 start, u64 end)
  71 {
  72         return !(end < le64_to_cpu(e->start) || le64_to_cpu(e->end) < start);
  73 }
  74
  75 int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end)
  76 {
  77         struct bch_sb_field_journal_seq_blacklist *bl;
  78         unsigned i, nr;
  79         int ret = 0;
  80
  81         mutex_lock(&c->sb_lock);
  82         bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
  83         nr = blacklist_nr_entries(bl);
  84
  85         for (i = 0; i < nr; i++) {
  86                 struct journal_seq_blacklist_entry *e =
  87                         bl->start + i;
  88
  89                 if (bl_entry_contig_or_overlaps(e, start, end)) {
  90                         e->start = cpu_to_le64(min(start, le64_to_cpu(e->start)));
  91                         e->end  = cpu_to_le64(max(end, le64_to_cpu(e->end)));
  92
  93                         if (i + 1 < nr)
  94                                 bl = blacklist_entry_try_merge(c,
  95                                                         bl, i);
  96                         if (i)
  97                                 bl = blacklist_entry_try_merge(c,
  98                                                         bl, i - 1);
  99                         goto out_write_sb;
 100                 }
 101         }
 102
 103         bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,
 104                                   sb_blacklist_u64s(nr + 1));
 105         if (!bl) {
 106                 ret = -BCH_ERR_ENOSPC_sb_journal_seq_blacklist;
 107                 goto out;
 108         }
 109
 110         bl->start[nr].start     = cpu_to_le64(start);
 111         bl->start[nr].end       = cpu_to_le64(end);
 112 out_write_sb:
 113         c->disk_sb.sb->features[0] |= cpu_to_le64(1ULL << BCH_FEATURE_journal_seq_blacklist_v3);
 114
 115         ret = bch2_write_super(c);
 116 out:
 117         mutex_unlock(&c->sb_lock);
 118
 119         return ret ?: bch2_blacklist_table_initialize(c);
 120 }
 121
 122 static int journal_seq_blacklist_table_cmp(const void *_l,
 123                                            const void *_r, size_t size)
 124 {
 125         const struct journal_seq_blacklist_table_entry *l = _l;
 126         const struct journal_seq_blacklist_table_entry *r = _r;
 127
 128         return cmp_int(l->start, r->start);
 129 }
 130
 131 bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq,
 132                                      bool dirty)
 133 {
 134         struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;
 135         struct journal_seq_blacklist_table_entry search = { .start = seq };
 136         int idx;
 137
 138         if (!t)
 139                 return false;
 140
 141         idx = eytzinger0_find_le(t->entries, t->nr,
 142                                  sizeof(t->entries[0]),
 143                                  journal_seq_blacklist_table_cmp,
 144                                  &search);
 145         if (idx < 0)
 146                 return false;
 147
 148         BUG_ON(t->entries[idx].start > seq);
 149
 150         if (seq >= t->entries[idx].end)
 151                 return false;
 152
 153         if (dirty)
 154                 t->entries[idx].dirty = true;
 155         return true;
 156 }
 157
 158 int bch2_blacklist_table_initialize(struct bch_fs *c)
 159 {
 160         struct bch_sb_field_journal_seq_blacklist *bl =
 161                 bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
 162         struct journal_seq_blacklist_table *t;
 163         unsigned i, nr = blacklist_nr_entries(bl);
 164
 165         if (!bl)
 166                 return 0;
 167
 168         t = kzalloc(sizeof(*t) + sizeof(t->entries[0]) * nr,
 169                     GFP_KERNEL);
 170         if (!t)
 171                 return -BCH_ERR_ENOMEM_blacklist_table_init;
 172
 173         t->nr = nr;
 174
 175         for (i = 0; i < nr; i++) {
 176                 t->entries[i].start     = le64_to_cpu(bl->start[i].start);
 177                 t->entries[i].end       = le64_to_cpu(bl->start[i].end);
 178         }
 179
 180         eytzinger0_sort(t->entries,
 181                         t->nr,
 182                         sizeof(t->entries[0]),
 183                         journal_seq_blacklist_table_cmp,
 184                         NULL);
 185
 186         kfree(c->journal_seq_blacklist_table);
 187         c->journal_seq_blacklist_table = t;
 188         return 0;
 189 }
 190
 191 static int bch2_sb_journal_seq_blacklist_validate(struct bch_sb *sb,
 192                                                   struct bch_sb_field *f,
 193                                                   struct printbuf *err)
 194 {
 195         struct bch_sb_field_journal_seq_blacklist *bl =
 196                 field_to_type(f, journal_seq_blacklist);
 197         unsigned i, nr = blacklist_nr_entries(bl);
 198
 199         for (i = 0; i < nr; i++) {
 200                 struct journal_seq_blacklist_entry *e = bl->start + i;
 201
 202                 if (le64_to_cpu(e->start) >=
 203                     le64_to_cpu(e->end)) {
 204                         prt_printf(err, "entry %u start >= end (%llu >= %llu)",
 205                                i, le64_to_cpu(e->start), le64_to_cpu(e->end));
 206                         return -BCH_ERR_invalid_sb_journal_seq_blacklist;
 207                 }
 208
 209                 if (i + 1 < nr &&
 210                     le64_to_cpu(e[0].end) >
 211                     le64_to_cpu(e[1].start)) {
 212                         prt_printf(err, "entry %u out of order with next entry (%llu > %llu)",
 213                                i + 1, le64_to_cpu(e[0].end), le64_to_cpu(e[1].start));
 214                         return -BCH_ERR_invalid_sb_journal_seq_blacklist;
 215                 }
 216         }
 217
 218         return 0;
 219 }
 220
 221 static void bch2_sb_journal_seq_blacklist_to_text(struct printbuf *out,
 222                                                   struct bch_sb *sb,
 223                                                   struct bch_sb_field *f)
 224 {
 225         struct bch_sb_field_journal_seq_blacklist *bl =
 226                 field_to_type(f, journal_seq_blacklist);
 227         struct journal_seq_blacklist_entry *i;
 228         unsigned nr = blacklist_nr_entries(bl);
 229
 230         for (i = bl->start; i < bl->start + nr; i++) {
 231                 if (i != bl->start)
 232                         prt_printf(out, " ");
 233
 234                 prt_printf(out, "%llu-%llu",
 235                        le64_to_cpu(i->start),
 236                        le64_to_cpu(i->end));
 237         }
 238         prt_newline(out);
 239 }
 240
 241 const struct bch_sb_field_ops bch_sb_field_ops_journal_seq_blacklist = {
 242         .validate       = bch2_sb_journal_seq_blacklist_validate,
 243         .to_text        = bch2_sb_journal_seq_blacklist_to_text
 244 };
 245
 246 void bch2_blacklist_entries_gc(struct work_struct *work)
 247 {
 248         struct bch_fs *c = container_of(work, struct bch_fs,
 249                                         journal_seq_blacklist_gc_work);
 250         struct journal_seq_blacklist_table *t;
 251         struct bch_sb_field_journal_seq_blacklist *bl;
 252         struct journal_seq_blacklist_entry *src, *dst;
 253         struct btree_trans *trans = bch2_trans_get(c);
 254         unsigned i, nr, new_nr;
 255         int ret;
 256
 257         for (i = 0; i < BTREE_ID_NR; i++) {
 258                 struct btree_iter iter;
 259                 struct btree *b;
 260
 261                 bch2_trans_node_iter_init(trans, &iter, i, POS_MIN,
 262                                           0, 0, BTREE_ITER_PREFETCH);
 263 retry:
 264                 bch2_trans_begin(trans);
 265
 266                 b = bch2_btree_iter_peek_node(&iter);
 267
 268                 while (!(ret = PTR_ERR_OR_ZERO(b)) &&
 269                        b &&
 270                        !test_bit(BCH_FS_stopping, &c->flags))
 271                         b = bch2_btree_iter_next_node(&iter);
 272
 273                 if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 274                         goto retry;
 275
 276                 bch2_trans_iter_exit(trans, &iter);
 277         }
 278
 279         bch2_trans_put(trans);
 280         if (ret)
 281                 return;
 282
 283         mutex_lock(&c->sb_lock);
 284         bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
 285         if (!bl)
 286                 goto out;
 287
 288         nr = blacklist_nr_entries(bl);
 289         dst = bl->start;
 290
 291         t = c->journal_seq_blacklist_table;
 292         BUG_ON(nr != t->nr);
 293
 294         for (src = bl->start, i = eytzinger0_first(t->nr);
 295              src < bl->start + nr;
 296              src++, i = eytzinger0_next(i, nr)) {
 297                 BUG_ON(t->entries[i].start      != le64_to_cpu(src->start));
 298                 BUG_ON(t->entries[i].end        != le64_to_cpu(src->end));
 299
 300                 if (t->entries[i].dirty)
 301                         *dst++ = *src;
 302         }
 303
 304         new_nr = dst - bl->start;
 305
 306         bch_info(c, "nr blacklist entries was %u, now %u", nr, new_nr);
 307
 308         if (new_nr != nr) {
 309                 bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,
 310                                 new_nr ? sb_blacklist_u64s(new_nr) : 0);
 311                 BUG_ON(new_nr && !bl);
 312
 313                 if (!new_nr)
 314                         c->disk_sb.sb->features[0] &= cpu_to_le64(~(1ULL << BCH_FEATURE_journal_seq_blacklist_v3));
 315
 316                 bch2_write_super(c);
 317         }
 318 out:
 319         mutex_unlock(&c->sb_lock);
 320 }