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

   1
   2 #include "bcachefs.h"
   3 #include "bkey_methods.h"
   4 #include "btree_cache.h"
   5 #include "btree_io.h"
   6 #include "btree_iter.h"
   7 #include "btree_locking.h"
   8 #include "btree_update.h"
   9 #include "btree_update_interior.h"
  10 #include "buckets.h"
  11 #include "checksum.h"
  12 #include "debug.h"
  13 #include "error.h"
  14 #include "extents.h"
  15 #include "io.h"
  16 #include "journal.h"
  17 #include "super-io.h"
  18
  19 #include <trace/events/bcachefs.h>
  20
  21 static void verify_no_dups(struct btree *b,
  22                            struct bkey_packed *start,
  23                            struct bkey_packed *end)
  24 {
  25 #ifdef CONFIG_BCACHEFS_DEBUG
  26         struct bkey_packed *k;
  27
  28         for (k = start; k != end && bkey_next(k) != end; k = bkey_next(k)) {
  29                 struct bkey l = bkey_unpack_key(b, k);
  30                 struct bkey r = bkey_unpack_key(b, bkey_next(k));
  31
  32                 BUG_ON(btree_node_is_extents(b)
  33                        ? bkey_cmp(l.p, bkey_start_pos(&r)) > 0
  34                        : bkey_cmp(l.p, bkey_start_pos(&r)) >= 0);
  35                 //BUG_ON(bkey_cmp_packed(&b->format, k, bkey_next(k)) >= 0);
  36         }
  37 #endif
  38 }
  39
  40 static void clear_needs_whiteout(struct bset *i)
  41 {
  42         struct bkey_packed *k;
  43
  44         for (k = i->start; k != vstruct_last(i); k = bkey_next(k))
  45                 k->needs_whiteout = false;
  46 }
  47
  48 static void set_needs_whiteout(struct bset *i)
  49 {
  50         struct bkey_packed *k;
  51
  52         for (k = i->start; k != vstruct_last(i); k = bkey_next(k))
  53                 k->needs_whiteout = true;
  54 }
  55
  56 static void btree_bounce_free(struct bch_fs *c, unsigned order,
  57                               bool used_mempool, void *p)
  58 {
  59         if (used_mempool)
  60                 mempool_free(p, &c->btree_bounce_pool);
  61         else
  62                 vpfree(p, PAGE_SIZE << order);
  63 }
  64
  65 static void *btree_bounce_alloc(struct bch_fs *c, unsigned order,
  66                                 bool *used_mempool)
  67 {
  68         void *p;
  69
  70         BUG_ON(order > btree_page_order(c));
  71
  72         *used_mempool = false;
  73         p = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT, order);
  74         if (p)
  75                 return p;
  76
  77         *used_mempool = true;
  78         return mempool_alloc(&c->btree_bounce_pool, GFP_NOIO);
  79 }
  80
  81 typedef int (*sort_cmp_fn)(struct btree *,
  82                            struct bkey_packed *,
  83                            struct bkey_packed *);
  84
  85 struct sort_iter {
  86         struct btree    *b;
  87         unsigned                used;
  88
  89         struct sort_iter_set {
  90                 struct bkey_packed *k, *end;
  91         } data[MAX_BSETS + 1];
  92 };
  93
  94 static void sort_iter_init(struct sort_iter *iter, struct btree *b)
  95 {
  96         memset(iter, 0, sizeof(*iter));
  97         iter->b = b;
  98 }
  99
 100 static inline void __sort_iter_sift(struct sort_iter *iter,
 101                                     unsigned from,
 102                                     sort_cmp_fn cmp)
 103 {
 104         unsigned i;
 105
 106         for (i = from;
 107              i + 1 < iter->used &&
 108              cmp(iter->b, iter->data[i].k, iter->data[i + 1].k) > 0;
 109              i++)
 110                 swap(iter->data[i], iter->data[i + 1]);
 111 }
 112
 113 static inline void sort_iter_sift(struct sort_iter *iter, sort_cmp_fn cmp)
 114 {
 115
 116         __sort_iter_sift(iter, 0, cmp);
 117 }
 118
 119 static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp)
 120 {
 121         unsigned i = iter->used;
 122
 123         while (i--)
 124                 __sort_iter_sift(iter, i, cmp);
 125 }
 126
 127 static void sort_iter_add(struct sort_iter *iter,
 128                           struct bkey_packed *k,
 129                           struct bkey_packed *end)
 130 {
 131         BUG_ON(iter->used >= ARRAY_SIZE(iter->data));
 132
 133         if (k != end)
 134                 iter->data[iter->used++] = (struct sort_iter_set) { k, end };
 135 }
 136
 137 static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter)
 138 {
 139         return iter->used ? iter->data->k : NULL;
 140 }
 141
 142 static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp)
 143 {
 144         iter->data->k = bkey_next(iter->data->k);
 145
 146         BUG_ON(iter->data->k > iter->data->end);
 147
 148         if (iter->data->k == iter->data->end)
 149                 array_remove_item(iter->data, iter->used, 0);
 150         else
 151                 sort_iter_sift(iter, cmp);
 152 }
 153
 154 static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter,
 155                                                  sort_cmp_fn cmp)
 156 {
 157         struct bkey_packed *ret = sort_iter_peek(iter);
 158
 159         if (ret)
 160                 sort_iter_advance(iter, cmp);
 161
 162         return ret;
 163 }
 164
 165 static inline int sort_key_whiteouts_cmp(struct btree *b,
 166                                          struct bkey_packed *l,
 167                                          struct bkey_packed *r)
 168 {
 169         return bkey_cmp_packed(b, l, r);
 170 }
 171
 172 static unsigned sort_key_whiteouts(struct bkey_packed *dst,
 173                                    struct sort_iter *iter)
 174 {
 175         struct bkey_packed *in, *out = dst;
 176
 177         sort_iter_sort(iter, sort_key_whiteouts_cmp);
 178
 179         while ((in = sort_iter_next(iter, sort_key_whiteouts_cmp))) {
 180                 bkey_copy(out, in);
 181                 out = bkey_next(out);
 182         }
 183
 184         return (u64 *) out - (u64 *) dst;
 185 }
 186
 187 static inline int sort_extent_whiteouts_cmp(struct btree *b,
 188                                             struct bkey_packed *l,
 189                                             struct bkey_packed *r)
 190 {
 191         struct bkey ul = bkey_unpack_key(b, l);
 192         struct bkey ur = bkey_unpack_key(b, r);
 193
 194         return bkey_cmp(bkey_start_pos(&ul), bkey_start_pos(&ur));
 195 }
 196
 197 static unsigned sort_extent_whiteouts(struct bkey_packed *dst,
 198                                       struct sort_iter *iter)
 199 {
 200         const struct bkey_format *f = &iter->b->format;
 201         struct bkey_packed *in, *out = dst;
 202         struct bkey_i l, r;
 203         bool prev = false, l_packed = false;
 204         u64 max_packed_size     = bkey_field_max(f, BKEY_FIELD_SIZE);
 205         u64 max_packed_offset   = bkey_field_max(f, BKEY_FIELD_OFFSET);
 206         u64 new_size;
 207
 208         max_packed_size = min_t(u64, max_packed_size, KEY_SIZE_MAX);
 209
 210         sort_iter_sort(iter, sort_extent_whiteouts_cmp);
 211
 212         while ((in = sort_iter_next(iter, sort_extent_whiteouts_cmp))) {
 213                 EBUG_ON(bkeyp_val_u64s(f, in));
 214                 EBUG_ON(in->type != KEY_TYPE_DISCARD);
 215
 216                 r.k = bkey_unpack_key(iter->b, in);
 217
 218                 if (prev &&
 219                     bkey_cmp(l.k.p, bkey_start_pos(&r.k)) >= 0) {
 220                         if (bkey_cmp(l.k.p, r.k.p) >= 0)
 221                                 continue;
 222
 223                         new_size = l_packed
 224                                 ? min(max_packed_size, max_packed_offset -
 225                                       bkey_start_offset(&l.k))
 226                                 : KEY_SIZE_MAX;
 227
 228                         new_size = min(new_size, r.k.p.offset -
 229                                        bkey_start_offset(&l.k));
 230
 231                         BUG_ON(new_size < l.k.size);
 232
 233                         bch2_key_resize(&l.k, new_size);
 234
 235                         if (bkey_cmp(l.k.p, r.k.p) >= 0)
 236                                 continue;
 237
 238                         bch2_cut_front(l.k.p, &r);
 239                 }
 240
 241                 if (prev) {
 242                         if (!bch2_bkey_pack(out, &l, f)) {
 243                                 BUG_ON(l_packed);
 244                                 bkey_copy(out, &l);
 245                         }
 246                         out = bkey_next(out);
 247                 }
 248
 249                 l = r;
 250                 prev = true;
 251                 l_packed = bkey_packed(in);
 252         }
 253
 254         if (prev) {
 255                 if (!bch2_bkey_pack(out, &l, f)) {
 256                         BUG_ON(l_packed);
 257                         bkey_copy(out, &l);
 258                 }
 259                 out = bkey_next(out);
 260         }
 261
 262         return (u64 *) out - (u64 *) dst;
 263 }
 264
 265 static unsigned should_compact_bset(struct btree *b, struct bset_tree *t,
 266                                     bool compacting,
 267                                     enum compact_mode mode)
 268 {
 269         unsigned bset_u64s = le16_to_cpu(bset(b, t)->u64s);
 270         unsigned dead_u64s = bset_u64s - b->nr.bset_u64s[t - b->set];
 271
 272         if (mode == COMPACT_LAZY) {
 273                 if (should_compact_bset_lazy(b, t) ||
 274                     (compacting && bset_unwritten(b, bset(b, t))))
 275                         return dead_u64s;
 276         } else {
 277                 if (bset_written(b, bset(b, t)))
 278                         return dead_u64s;
 279         }
 280
 281         return 0;
 282 }
 283
 284 bool __bch2_compact_whiteouts(struct bch_fs *c, struct btree *b,
 285                              enum compact_mode mode)
 286 {
 287         const struct bkey_format *f = &b->format;
 288         struct bset_tree *t;
 289         struct bkey_packed *whiteouts = NULL;
 290         struct bkey_packed *u_start, *u_pos;
 291         struct sort_iter sort_iter;
 292         unsigned order, whiteout_u64s = 0, u64s;
 293         bool used_mempool, compacting = false;
 294
 295         for_each_bset(b, t)
 296                 whiteout_u64s += should_compact_bset(b, t,
 297                                         whiteout_u64s != 0, mode);
 298
 299         if (!whiteout_u64s)
 300                 return false;
 301
 302         sort_iter_init(&sort_iter, b);
 303
 304         whiteout_u64s += b->whiteout_u64s;
 305         order = get_order(whiteout_u64s * sizeof(u64));
 306
 307         whiteouts = btree_bounce_alloc(c, order, &used_mempool);
 308         u_start = u_pos = whiteouts;
 309
 310         memcpy_u64s(u_pos, unwritten_whiteouts_start(c, b),
 311                     b->whiteout_u64s);
 312         u_pos = (void *) u_pos + b->whiteout_u64s * sizeof(u64);
 313
 314         sort_iter_add(&sort_iter, u_start, u_pos);
 315
 316         for_each_bset(b, t) {
 317                 struct bset *i = bset(b, t);
 318                 struct bkey_packed *k, *n, *out, *start, *end;
 319                 struct btree_node_entry *src = NULL, *dst = NULL;
 320
 321                 if (t != b->set && bset_unwritten(b, i)) {
 322                         src = container_of(i, struct btree_node_entry, keys);
 323                         dst = max(write_block(b),
 324                                   (void *) btree_bkey_last(b, t -1));
 325                 }
 326
 327                 if (!should_compact_bset(b, t, compacting, mode)) {
 328                         if (src != dst) {
 329                                 memmove(dst, src, sizeof(*src) +
 330                                         le16_to_cpu(src->keys.u64s) *
 331                                         sizeof(u64));
 332                                 i = &dst->keys;
 333                                 set_btree_bset(b, t, i);
 334                         }
 335                         continue;
 336                 }
 337
 338                 compacting = true;
 339                 u_start = u_pos;
 340                 start = i->start;
 341                 end = vstruct_last(i);
 342
 343                 if (src != dst) {
 344                         memmove(dst, src, sizeof(*src));
 345                         i = &dst->keys;
 346                         set_btree_bset(b, t, i);
 347                 }
 348
 349                 out = i->start;
 350
 351                 for (k = start; k != end; k = n) {
 352                         n = bkey_next(k);
 353
 354                         if (bkey_deleted(k) && btree_node_is_extents(b))
 355                                 continue;
 356
 357                         if (bkey_whiteout(k) && !k->needs_whiteout)
 358                                 continue;
 359
 360                         if (bkey_whiteout(k)) {
 361                                 unreserve_whiteout(b, t, k);
 362                                 memcpy_u64s(u_pos, k, bkeyp_key_u64s(f, k));
 363                                 set_bkeyp_val_u64s(f, u_pos, 0);
 364                                 u_pos = bkey_next(u_pos);
 365                         } else if (mode != COMPACT_WRITTEN_NO_WRITE_LOCK) {
 366                                 bkey_copy(out, k);
 367                                 out = bkey_next(out);
 368                         }
 369                 }
 370
 371                 sort_iter_add(&sort_iter, u_start, u_pos);
 372
 373                 if (mode != COMPACT_WRITTEN_NO_WRITE_LOCK) {
 374                         i->u64s = cpu_to_le16((u64 *) out - i->_data);
 375                         set_btree_bset_end(b, t);
 376                         bch2_bset_set_no_aux_tree(b, t);
 377                 }
 378         }
 379
 380         b->whiteout_u64s = (u64 *) u_pos - (u64 *) whiteouts;
 381
 382         BUG_ON((void *) unwritten_whiteouts_start(c, b) <
 383                (void *) btree_bkey_last(b, bset_tree_last(b)));
 384
 385         u64s = btree_node_is_extents(b)
 386                 ? sort_extent_whiteouts(unwritten_whiteouts_start(c, b),
 387                                         &sort_iter)
 388                 : sort_key_whiteouts(unwritten_whiteouts_start(c, b),
 389                                      &sort_iter);
 390
 391         BUG_ON(u64s > b->whiteout_u64s);
 392         BUG_ON(u64s != b->whiteout_u64s && !btree_node_is_extents(b));
 393         BUG_ON(u_pos != whiteouts && !u64s);
 394
 395         if (u64s != b->whiteout_u64s) {
 396                 void *src = unwritten_whiteouts_start(c, b);
 397
 398                 b->whiteout_u64s = u64s;
 399                 memmove_u64s_up(unwritten_whiteouts_start(c, b), src, u64s);
 400         }
 401
 402         verify_no_dups(b,
 403                        unwritten_whiteouts_start(c, b),
 404                        unwritten_whiteouts_end(c, b));
 405
 406         btree_bounce_free(c, order, used_mempool, whiteouts);
 407
 408         if (mode != COMPACT_WRITTEN_NO_WRITE_LOCK)
 409                 bch2_btree_build_aux_trees(b);
 410
 411         bch_btree_keys_u64s_remaining(c, b);
 412         bch2_verify_btree_nr_keys(b);
 413
 414         return true;
 415 }
 416
 417 static bool bch2_drop_whiteouts(struct btree *b)
 418 {
 419         struct bset_tree *t;
 420         bool ret = false;
 421
 422         for_each_bset(b, t) {
 423                 struct bset *i = bset(b, t);
 424                 struct bkey_packed *k, *n, *out, *start, *end;
 425
 426                 if (!should_compact_bset(b, t, true, COMPACT_WRITTEN))
 427                         continue;
 428
 429                 start   = btree_bkey_first(b, t);
 430                 end     = btree_bkey_last(b, t);
 431
 432                 if (bset_unwritten(b, i) &&
 433                     t != b->set) {
 434                         struct bset *dst =
 435                                max_t(struct bset *, write_block(b),
 436                                      (void *) btree_bkey_last(b, t -1));
 437
 438                         memmove(dst, i, sizeof(struct bset));
 439                         i = dst;
 440                         set_btree_bset(b, t, i);
 441                 }
 442
 443                 out = i->start;
 444
 445                 for (k = start; k != end; k = n) {
 446                         n = bkey_next(k);
 447
 448                         if (!bkey_whiteout(k)) {
 449                                 bkey_copy(out, k);
 450                                 out = bkey_next(out);
 451                         }
 452                 }
 453
 454                 i->u64s = cpu_to_le16((u64 *) out - i->_data);
 455                 bch2_bset_set_no_aux_tree(b, t);
 456                 ret = true;
 457         }
 458
 459         bch2_verify_btree_nr_keys(b);
 460
 461         return ret;
 462 }
 463
 464 static inline int sort_keys_cmp(struct btree *b,
 465                                 struct bkey_packed *l,
 466                                 struct bkey_packed *r)
 467 {
 468         return bkey_cmp_packed(b, l, r) ?:
 469                 (int) bkey_whiteout(r) - (int) bkey_whiteout(l) ?:
 470                 (int) l->needs_whiteout - (int) r->needs_whiteout;
 471 }
 472
 473 static unsigned sort_keys(struct bkey_packed *dst,
 474                           struct sort_iter *iter,
 475                           bool filter_whiteouts)
 476 {
 477         const struct bkey_format *f = &iter->b->format;
 478         struct bkey_packed *in, *next, *out = dst;
 479
 480         sort_iter_sort(iter, sort_keys_cmp);
 481
 482         while ((in = sort_iter_next(iter, sort_keys_cmp))) {
 483                 if (bkey_whiteout(in) &&
 484                     (filter_whiteouts || !in->needs_whiteout))
 485                         continue;
 486
 487                 if (bkey_whiteout(in) &&
 488                     (next = sort_iter_peek(iter)) &&
 489                     !bkey_cmp_packed(iter->b, in, next)) {
 490                         BUG_ON(in->needs_whiteout &&
 491                                next->needs_whiteout);
 492                         /*
 493                          * XXX racy, called with read lock from write path
 494                          *
 495                          * leads to spurious BUG_ON() in bkey_unpack_key() in
 496                          * debug mode
 497                          */
 498                         next->needs_whiteout |= in->needs_whiteout;
 499                         continue;
 500                 }
 501
 502                 if (bkey_whiteout(in)) {
 503                         memcpy_u64s(out, in, bkeyp_key_u64s(f, in));
 504                         set_bkeyp_val_u64s(f, out, 0);
 505                 } else {
 506                         bkey_copy(out, in);
 507                 }
 508                 out = bkey_next(out);
 509         }
 510
 511         return (u64 *) out - (u64 *) dst;
 512 }
 513
 514 static inline int sort_extents_cmp(struct btree *b,
 515                                    struct bkey_packed *l,
 516                                    struct bkey_packed *r)
 517 {
 518         return bkey_cmp_packed(b, l, r) ?:
 519                 (int) bkey_deleted(l) - (int) bkey_deleted(r);
 520 }
 521
 522 static unsigned sort_extents(struct bkey_packed *dst,
 523                              struct sort_iter *iter,
 524                              bool filter_whiteouts)
 525 {
 526         struct bkey_packed *in, *out = dst;
 527
 528         sort_iter_sort(iter, sort_extents_cmp);
 529
 530         while ((in = sort_iter_next(iter, sort_extents_cmp))) {
 531                 if (bkey_deleted(in))
 532                         continue;
 533
 534                 if (bkey_whiteout(in) &&
 535                     (filter_whiteouts || !in->needs_whiteout))
 536                         continue;
 537
 538                 bkey_copy(out, in);
 539                 out = bkey_next(out);
 540         }
 541
 542         return (u64 *) out - (u64 *) dst;
 543 }
 544
 545 static void btree_node_sort(struct bch_fs *c, struct btree *b,
 546                             struct btree_iter *iter,
 547                             unsigned start_idx,
 548                             unsigned end_idx,
 549                             bool filter_whiteouts)
 550 {
 551         struct btree_node *out;
 552         struct sort_iter sort_iter;
 553         struct bset_tree *t;
 554         struct bset *start_bset = bset(b, &b->set[start_idx]);
 555         bool used_mempool = false;
 556         u64 start_time, seq = 0;
 557         unsigned i, u64s = 0, order, shift = end_idx - start_idx - 1;
 558         bool sorting_entire_node = start_idx == 0 &&
 559                 end_idx == b->nsets;
 560
 561         sort_iter_init(&sort_iter, b);
 562
 563         for (t = b->set + start_idx;
 564              t < b->set + end_idx;
 565              t++) {
 566                 u64s += le16_to_cpu(bset(b, t)->u64s);
 567                 sort_iter_add(&sort_iter,
 568                               btree_bkey_first(b, t),
 569                               btree_bkey_last(b, t));
 570         }
 571
 572         order = sorting_entire_node
 573                 ? btree_page_order(c)
 574                 : get_order(__vstruct_bytes(struct btree_node, u64s));
 575
 576         out = btree_bounce_alloc(c, order, &used_mempool);
 577
 578         start_time = local_clock();
 579
 580         if (btree_node_is_extents(b))
 581                 filter_whiteouts = bset_written(b, start_bset);
 582
 583         u64s = btree_node_is_extents(b)
 584                 ? sort_extents(out->keys.start, &sort_iter, filter_whiteouts)
 585                 : sort_keys(out->keys.start, &sort_iter, filter_whiteouts);
 586
 587         out->keys.u64s = cpu_to_le16(u64s);
 588
 589         BUG_ON(vstruct_end(&out->keys) > (void *) out + (PAGE_SIZE << order));
 590
 591         if (sorting_entire_node)
 592                 bch2_time_stats_update(&c->btree_sort_time, start_time);
 593
 594         /* Make sure we preserve bset journal_seq: */
 595         for (t = b->set + start_idx; t < b->set + end_idx; t++)
 596                 seq = max(seq, le64_to_cpu(bset(b, t)->journal_seq));
 597         start_bset->journal_seq = cpu_to_le64(seq);
 598
 599         if (sorting_entire_node) {
 600                 unsigned u64s = le16_to_cpu(out->keys.u64s);
 601
 602                 BUG_ON(order != btree_page_order(c));
 603
 604                 /*
 605                  * Our temporary buffer is the same size as the btree node's
 606                  * buffer, we can just swap buffers instead of doing a big
 607                  * memcpy()
 608                  */
 609                 *out = *b->data;
 610                 out->keys.u64s = cpu_to_le16(u64s);
 611                 swap(out, b->data);
 612                 set_btree_bset(b, b->set, &b->data->keys);
 613         } else {
 614                 start_bset->u64s = out->keys.u64s;
 615                 memcpy_u64s(start_bset->start,
 616                             out->keys.start,
 617                             le16_to_cpu(out->keys.u64s));
 618         }
 619
 620         for (i = start_idx + 1; i < end_idx; i++)
 621                 b->nr.bset_u64s[start_idx] +=
 622                         b->nr.bset_u64s[i];
 623
 624         b->nsets -= shift;
 625
 626         for (i = start_idx + 1; i < b->nsets; i++) {
 627                 b->nr.bset_u64s[i]      = b->nr.bset_u64s[i + shift];
 628                 b->set[i]               = b->set[i + shift];
 629         }
 630
 631         for (i = b->nsets; i < MAX_BSETS; i++)
 632                 b->nr.bset_u64s[i] = 0;
 633
 634         set_btree_bset_end(b, &b->set[start_idx]);
 635         bch2_bset_set_no_aux_tree(b, &b->set[start_idx]);
 636
 637         btree_bounce_free(c, order, used_mempool, out);
 638
 639         bch2_verify_btree_nr_keys(b);
 640 }
 641
 642 /* Sort + repack in a new format: */
 643 static struct btree_nr_keys sort_repack(struct bset *dst,
 644                                         struct btree *src,
 645                                         struct btree_node_iter *src_iter,
 646                                         struct bkey_format *out_f,
 647                                         bool filter_whiteouts)
 648 {
 649         struct bkey_format *in_f = &src->format;
 650         struct bkey_packed *in, *out = vstruct_last(dst);
 651         struct btree_nr_keys nr;
 652
 653         memset(&nr, 0, sizeof(nr));
 654
 655         while ((in = bch2_btree_node_iter_next_all(src_iter, src))) {
 656                 if (filter_whiteouts && bkey_whiteout(in))
 657                         continue;
 658
 659                 if (bch2_bkey_transform(out_f, out, bkey_packed(in)
 660                                        ? in_f : &bch2_bkey_format_current, in))
 661                         out->format = KEY_FORMAT_LOCAL_BTREE;
 662                 else
 663                         bch2_bkey_unpack(src, (void *) out, in);
 664
 665                 btree_keys_account_key_add(&nr, 0, out);
 666                 out = bkey_next(out);
 667         }
 668
 669         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
 670         return nr;
 671 }
 672
 673 /* Sort, repack, and merge: */
 674 static struct btree_nr_keys sort_repack_merge(struct bch_fs *c,
 675                                               struct bset *dst,
 676                                               struct btree *src,
 677                                               struct btree_node_iter *iter,
 678                                               struct bkey_format *out_f,
 679                                               bool filter_whiteouts,
 680                                               key_filter_fn filter,
 681                                               key_merge_fn merge)
 682 {
 683         struct bkey_packed *k, *prev = NULL, *out;
 684         struct btree_nr_keys nr;
 685         BKEY_PADDED(k) tmp;
 686
 687         memset(&nr, 0, sizeof(nr));
 688
 689         while ((k = bch2_btree_node_iter_next_all(iter, src))) {
 690                 if (filter_whiteouts && bkey_whiteout(k))
 691                         continue;
 692
 693                 /*
 694                  * The filter might modify pointers, so we have to unpack the
 695                  * key and values to &tmp.k:
 696                  */
 697                 bch2_bkey_unpack(src, &tmp.k, k);
 698
 699                 if (filter && filter(c, src, bkey_i_to_s(&tmp.k)))
 700                         continue;
 701
 702                 /* prev is always unpacked, for key merging: */
 703
 704                 if (prev &&
 705                     merge &&
 706                     merge(c, src, (void *) prev, &tmp.k) == BCH_MERGE_MERGE)
 707                         continue;
 708
 709                 /*
 710                  * the current key becomes the new prev: advance prev, then
 711                  * copy the current key - but first pack prev (in place):
 712                  */
 713                 if (prev) {
 714                         bch2_bkey_pack(prev, (void *) prev, out_f);
 715
 716                         btree_keys_account_key_add(&nr, 0, prev);
 717                         prev = bkey_next(prev);
 718                 } else {
 719                         prev = vstruct_last(dst);
 720                 }
 721
 722                 bkey_copy(prev, &tmp.k);
 723         }
 724
 725         if (prev) {
 726                 bch2_bkey_pack(prev, (void *) prev, out_f);
 727                 btree_keys_account_key_add(&nr, 0, prev);
 728                 out = bkey_next(prev);
 729         } else {
 730                 out = vstruct_last(dst);
 731         }
 732
 733         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
 734         return nr;
 735 }
 736
 737 void bch2_btree_sort_into(struct bch_fs *c,
 738                          struct btree *dst,
 739                          struct btree *src)
 740 {
 741         struct btree_nr_keys nr;
 742         struct btree_node_iter src_iter;
 743         u64 start_time = local_clock();
 744
 745         BUG_ON(dst->nsets != 1);
 746
 747         bch2_bset_set_no_aux_tree(dst, dst->set);
 748
 749         bch2_btree_node_iter_init_from_start(&src_iter, src,
 750                                             btree_node_is_extents(src));
 751
 752         if (btree_node_ops(src)->key_normalize ||
 753             btree_node_ops(src)->key_merge)
 754                 nr = sort_repack_merge(c, btree_bset_first(dst),
 755                                 src, &src_iter,
 756                                 &dst->format,
 757                                 true,
 758                                 btree_node_ops(src)->key_normalize,
 759                                 btree_node_ops(src)->key_merge);
 760         else
 761                 nr = sort_repack(btree_bset_first(dst),
 762                                 src, &src_iter,
 763                                 &dst->format,
 764                                 true);
 765
 766         bch2_time_stats_update(&c->btree_sort_time, start_time);
 767
 768         set_btree_bset_end(dst, dst->set);
 769
 770         dst->nr.live_u64s       += nr.live_u64s;
 771         dst->nr.bset_u64s[0]    += nr.bset_u64s[0];
 772         dst->nr.packed_keys     += nr.packed_keys;
 773         dst->nr.unpacked_keys   += nr.unpacked_keys;
 774
 775         bch2_verify_btree_nr_keys(dst);
 776 }
 777
 778 #define SORT_CRIT       (4096 / sizeof(u64))
 779
 780 /*
 781  * We're about to add another bset to the btree node, so if there's currently
 782  * too many bsets - sort some of them together:
 783  */
 784 static bool btree_node_compact(struct bch_fs *c, struct btree *b,
 785                                struct btree_iter *iter)
 786 {
 787         unsigned unwritten_idx;
 788         bool ret = false;
 789
 790         for (unwritten_idx = 0;
 791              unwritten_idx < b->nsets;
 792              unwritten_idx++)
 793                 if (bset_unwritten(b, bset(b, &b->set[unwritten_idx])))
 794                         break;
 795
 796         if (b->nsets - unwritten_idx > 1) {
 797                 btree_node_sort(c, b, iter, unwritten_idx,
 798                                 b->nsets, false);
 799                 ret = true;
 800         }
 801
 802         if (unwritten_idx > 1) {
 803                 btree_node_sort(c, b, iter, 0, unwritten_idx, false);
 804                 ret = true;
 805         }
 806
 807         return ret;
 808 }
 809
 810 void bch2_btree_build_aux_trees(struct btree *b)
 811 {
 812         struct bset_tree *t;
 813
 814         for_each_bset(b, t)
 815                 bch2_bset_build_aux_tree(b, t,
 816                                 bset_unwritten(b, bset(b, t)) &&
 817                                 t == bset_tree_last(b));
 818 }
 819
 820 /*
 821  * @bch_btree_init_next - initialize a new (unwritten) bset that can then be
 822  * inserted into
 823  *
 824  * Safe to call if there already is an unwritten bset - will only add a new bset
 825  * if @b doesn't already have one.
 826  *
 827  * Returns true if we sorted (i.e. invalidated iterators
 828  */
 829 void bch2_btree_init_next(struct bch_fs *c, struct btree *b,
 830                           struct btree_iter *iter)
 831 {
 832         struct btree_node_entry *bne;
 833         bool did_sort;
 834
 835         EBUG_ON(!(b->lock.state.seq & 1));
 836         EBUG_ON(iter && iter->l[b->level].b != b);
 837
 838         did_sort = btree_node_compact(c, b, iter);
 839
 840         bne = want_new_bset(c, b);
 841         if (bne)
 842                 bch2_bset_init_next(b, &bne->keys);
 843
 844         bch2_btree_build_aux_trees(b);
 845
 846         if (iter && did_sort)
 847                 bch2_btree_iter_reinit_node(iter, b);
 848 }
 849
 850 static struct nonce btree_nonce(struct bset *i, unsigned offset)
 851 {
 852         return (struct nonce) {{
 853                 [0] = cpu_to_le32(offset),
 854                 [1] = ((__le32 *) &i->seq)[0],
 855                 [2] = ((__le32 *) &i->seq)[1],
 856                 [3] = ((__le32 *) &i->journal_seq)[0]^BCH_NONCE_BTREE,
 857         }};
 858 }
 859
 860 static void bset_encrypt(struct bch_fs *c, struct bset *i, unsigned offset)
 861 {
 862         struct nonce nonce = btree_nonce(i, offset);
 863
 864         if (!offset) {
 865                 struct btree_node *bn = container_of(i, struct btree_node, keys);
 866                 unsigned bytes = (void *) &bn->keys - (void *) &bn->flags;
 867
 868                 bch2_encrypt(c, BSET_CSUM_TYPE(i), nonce, &bn->flags,
 869                              bytes);
 870
 871                 nonce = nonce_add(nonce, round_up(bytes, CHACHA20_BLOCK_SIZE));
 872         }
 873
 874         bch2_encrypt(c, BSET_CSUM_TYPE(i), nonce, i->_data,
 875                      vstruct_end(i) - (void *) i->_data);
 876 }
 877
 878 static int btree_err_msg(struct bch_fs *c, struct btree *b, struct bset *i,
 879                          unsigned offset, int write, char *buf, size_t len)
 880 {
 881         char *out = buf, *end = buf + len;
 882
 883         out += scnprintf(out, end - out,
 884                          "error validating btree node %s "
 885                          "at btree %u level %u/%u\n"
 886                          "pos %llu:%llu node offset %u",
 887                          write ? "before write " : "",
 888                          b->btree_id, b->level,
 889                          c->btree_roots[b->btree_id].level,
 890                          b->key.k.p.inode, b->key.k.p.offset,
 891                          b->written);
 892         if (i)
 893                 out += scnprintf(out, end - out,
 894                                  " bset u64s %u",
 895                                  le16_to_cpu(i->u64s));
 896
 897         return out - buf;
 898 }
 899
 900 enum btree_err_type {
 901         BTREE_ERR_FIXABLE,
 902         BTREE_ERR_WANT_RETRY,
 903         BTREE_ERR_MUST_RETRY,
 904         BTREE_ERR_FATAL,
 905 };
 906
 907 enum btree_validate_ret {
 908         BTREE_RETRY_READ = 64,
 909 };
 910
 911 #define btree_err(type, c, b, i, msg, ...)                              \
 912 ({                                                                      \
 913         char buf[200], *out = buf, *end = out + sizeof(buf);            \
 914                                                                         \
 915         out += btree_err_msg(c, b, i, b->written, write, out, end - out);\
 916         out += scnprintf(out, end - out, ": " msg, ##__VA_ARGS__);      \
 917                                                                         \
 918         if (type == BTREE_ERR_FIXABLE &&                                \
 919             write == READ &&                                            \
 920             !test_bit(BCH_FS_INITIAL_GC_DONE, &c->flags)) {             \
 921                 mustfix_fsck_err(c, "%s", buf);                         \
 922         } else {                                                        \
 923                 bch_err(c, "%s", buf);                                  \
 924                                                                         \
 925                 switch (type) {                                         \
 926                 case BTREE_ERR_FIXABLE:                                 \
 927                         ret = BCH_FSCK_ERRORS_NOT_FIXED;                \
 928                         goto fsck_err;                                  \
 929                 case BTREE_ERR_WANT_RETRY:                              \
 930                         if (have_retry) {                               \
 931                                 ret = BTREE_RETRY_READ;                 \
 932                                 goto fsck_err;                          \
 933                         }                                               \
 934                         break;                                          \
 935                 case BTREE_ERR_MUST_RETRY:                              \
 936                         ret = BTREE_RETRY_READ;                         \
 937                         goto fsck_err;                                  \
 938                 case BTREE_ERR_FATAL:                                   \
 939                         ret = BCH_FSCK_ERRORS_NOT_FIXED;                \
 940                         goto fsck_err;                                  \
 941                 }                                                       \
 942         }                                                               \
 943         true;                                                           \
 944 })
 945
 946 #define btree_err_on(cond, ...) ((cond) ? btree_err(__VA_ARGS__) : false)
 947
 948 static int validate_bset(struct bch_fs *c, struct btree *b,
 949                          struct bset *i, unsigned sectors,
 950                          unsigned *whiteout_u64s, int write,
 951                          bool have_retry)
 952 {
 953         struct bkey_packed *k, *prev = NULL;
 954         struct bpos prev_pos = POS_MIN;
 955         enum bkey_type type = btree_node_type(b);
 956         bool seen_non_whiteout = false;
 957         const char *err;
 958         int ret = 0;
 959
 960         if (i == &b->data->keys) {
 961                 /* These indicate that we read the wrong btree node: */
 962                 btree_err_on(BTREE_NODE_ID(b->data) != b->btree_id,
 963                              BTREE_ERR_MUST_RETRY, c, b, i,
 964                              "incorrect btree id");
 965
 966                 btree_err_on(BTREE_NODE_LEVEL(b->data) != b->level,
 967                              BTREE_ERR_MUST_RETRY, c, b, i,
 968                              "incorrect level");
 969
 970                 if (BSET_BIG_ENDIAN(i) != CPU_BIG_ENDIAN) {
 971                         u64 *p = (u64 *) &b->data->ptr;
 972
 973                         *p = swab64(*p);
 974                         bch2_bpos_swab(&b->data->min_key);
 975                         bch2_bpos_swab(&b->data->max_key);
 976                 }
 977
 978                 btree_err_on(bkey_cmp(b->data->max_key, b->key.k.p),
 979                              BTREE_ERR_MUST_RETRY, c, b, i,
 980                              "incorrect max key");
 981
 982                 /* XXX: ideally we would be validating min_key too */
 983 #if 0
 984                 /*
 985                  * not correct anymore, due to btree node write error
 986                  * handling
 987                  *
 988                  * need to add b->data->seq to btree keys and verify
 989                  * against that
 990                  */
 991                 btree_err_on(!extent_contains_ptr(bkey_i_to_s_c_extent(&b->key),
 992                                                   b->data->ptr),
 993                              BTREE_ERR_FATAL, c, b, i,
 994                              "incorrect backpointer");
 995 #endif
 996                 err = bch2_bkey_format_validate(&b->data->format);
 997                 btree_err_on(err,
 998                              BTREE_ERR_FATAL, c, b, i,
 999                              "invalid bkey format: %s", err);
1000         }
1001
1002         if (btree_err_on(le16_to_cpu(i->version) != BCACHE_BSET_VERSION,
1003                          BTREE_ERR_FIXABLE, c, b, i,
1004                          "unsupported bset version")) {
1005                 i->version = cpu_to_le16(BCACHE_BSET_VERSION);
1006                 i->u64s = 0;
1007                 return 0;
1008         }
1009
1010         if (btree_err_on(b->written + sectors > c->opts.btree_node_size,
1011                          BTREE_ERR_FIXABLE, c, b, i,
1012                          "bset past end of btree node")) {
1013                 i->u64s = 0;
1014                 return 0;
1015         }
1016
1017         btree_err_on(b->written && !i->u64s,
1018                      BTREE_ERR_FIXABLE, c, b, i,
1019                      "empty bset");
1020
1021         if (!BSET_SEPARATE_WHITEOUTS(i)) {
1022                 seen_non_whiteout = true;
1023                 *whiteout_u64s = 0;
1024         }
1025
1026         for (k = i->start;
1027              k != vstruct_last(i);) {
1028                 struct bkey_s_c u;
1029                 struct bkey tmp;
1030                 const char *invalid;
1031
1032                 if (btree_err_on(!k->u64s,
1033                                  BTREE_ERR_FIXABLE, c, b, i,
1034                                  "KEY_U64s 0: %zu bytes of metadata lost",
1035                                  vstruct_end(i) - (void *) k)) {
1036                         i->u64s = cpu_to_le16((u64 *) k - i->_data);
1037                         break;
1038                 }
1039
1040                 if (btree_err_on(bkey_next(k) > vstruct_last(i),
1041                                  BTREE_ERR_FIXABLE, c, b, i,
1042                                  "key extends past end of bset")) {
1043                         i->u64s = cpu_to_le16((u64 *) k - i->_data);
1044                         break;
1045                 }
1046
1047                 if (btree_err_on(k->format > KEY_FORMAT_CURRENT,
1048                                  BTREE_ERR_FIXABLE, c, b, i,
1049                                  "invalid bkey format %u", k->format)) {
1050                         i->u64s = cpu_to_le16(le16_to_cpu(i->u64s) - k->u64s);
1051                         memmove_u64s_down(k, bkey_next(k),
1052                                           (u64 *) vstruct_end(i) - (u64 *) k);
1053                         continue;
1054                 }
1055
1056                 if (BSET_BIG_ENDIAN(i) != CPU_BIG_ENDIAN)
1057                         bch2_bkey_swab(type, &b->format, k);
1058
1059                 u = bkey_disassemble(b, k, &tmp);
1060
1061                 invalid = __bch2_bkey_invalid(c, type, u) ?:
1062                         bch2_bkey_in_btree_node(b, u) ?:
1063                         (write ? bch2_bkey_val_invalid(c, type, u) : NULL);
1064                 if (invalid) {
1065                         char buf[160];
1066
1067                         bch2_bkey_val_to_text(c, type, buf, sizeof(buf), u);
1068                         btree_err(BTREE_ERR_FIXABLE, c, b, i,
1069                                   "invalid bkey %s: %s", buf, invalid);
1070
1071                         i->u64s = cpu_to_le16(le16_to_cpu(i->u64s) - k->u64s);
1072                         memmove_u64s_down(k, bkey_next(k),
1073                                           (u64 *) vstruct_end(i) - (u64 *) k);
1074                         continue;
1075                 }
1076
1077                 /*
1078                  * with the separate whiteouts thing (used for extents), the
1079                  * second set of keys actually can have whiteouts too, so we
1080                  * can't solely go off bkey_whiteout()...
1081                  */
1082
1083                 if (!seen_non_whiteout &&
1084                     (!bkey_whiteout(k) ||
1085                      (bkey_cmp(prev_pos, bkey_start_pos(u.k)) > 0))) {
1086                         *whiteout_u64s = k->_data - i->_data;
1087                         seen_non_whiteout = true;
1088                 } else if (bkey_cmp(prev_pos, bkey_start_pos(u.k)) > 0) {
1089                         btree_err(BTREE_ERR_FATAL, c, b, i,
1090                                   "keys out of order: %llu:%llu > %llu:%llu",
1091                                   prev_pos.inode,
1092                                   prev_pos.offset,
1093                                   u.k->p.inode,
1094                                   bkey_start_offset(u.k));
1095                         /* XXX: repair this */
1096                 }
1097
1098                 prev_pos = u.k->p;
1099                 prev = k;
1100                 k = bkey_next(k);
1101         }
1102
1103         SET_BSET_BIG_ENDIAN(i, CPU_BIG_ENDIAN);
1104 fsck_err:
1105         return ret;
1106 }
1107
1108 int bch2_btree_node_read_done(struct bch_fs *c, struct btree *b, bool have_retry)
1109 {
1110         struct btree_node_entry *bne;
1111         struct btree_node_iter *iter;
1112         struct btree_node *sorted;
1113         struct bkey_packed *k;
1114         struct bset *i;
1115         bool used_mempool;
1116         unsigned u64s;
1117         int ret, retry_read = 0, write = READ;
1118
1119         iter = mempool_alloc(&c->fill_iter, GFP_NOIO);
1120         __bch2_btree_node_iter_init(iter, btree_node_is_extents(b));
1121
1122         if (bch2_meta_read_fault("btree"))
1123                 btree_err(BTREE_ERR_MUST_RETRY, c, b, NULL,
1124                           "dynamic fault");
1125
1126         btree_err_on(le64_to_cpu(b->data->magic) != bset_magic(c),
1127                      BTREE_ERR_MUST_RETRY, c, b, NULL,
1128                      "bad magic");
1129
1130         btree_err_on(!b->data->keys.seq,
1131                      BTREE_ERR_MUST_RETRY, c, b, NULL,
1132                      "bad btree header");
1133
1134         while (b->written < c->opts.btree_node_size) {
1135                 unsigned sectors, whiteout_u64s = 0;
1136                 struct nonce nonce;
1137                 struct bch_csum csum;
1138                 bool first = !b->written;
1139
1140                 if (!b->written) {
1141                         i = &b->data->keys;
1142
1143                         btree_err_on(!bch2_checksum_type_valid(c, BSET_CSUM_TYPE(i)),
1144                                      BTREE_ERR_WANT_RETRY, c, b, i,
1145                                      "unknown checksum type");
1146
1147                         nonce = btree_nonce(i, b->written << 9);
1148                         csum = csum_vstruct(c, BSET_CSUM_TYPE(i), nonce, b->data);
1149
1150                         btree_err_on(bch2_crc_cmp(csum, b->data->csum),
1151                                      BTREE_ERR_WANT_RETRY, c, b, i,
1152                                      "invalid checksum");
1153
1154                         bset_encrypt(c, i, b->written << 9);
1155
1156                         sectors = vstruct_sectors(b->data, c->block_bits);
1157
1158                         set_btree_bset(b, b->set, &b->data->keys);
1159                         btree_node_set_format(b, b->data->format);
1160                 } else {
1161                         bne = write_block(b);
1162                         i = &bne->keys;
1163
1164                         if (i->seq != b->data->keys.seq)
1165                                 break;
1166
1167                         btree_err_on(!bch2_checksum_type_valid(c, BSET_CSUM_TYPE(i)),
1168                                      BTREE_ERR_WANT_RETRY, c, b, i,
1169                                      "unknown checksum type");
1170
1171                         nonce = btree_nonce(i, b->written << 9);
1172                         csum = csum_vstruct(c, BSET_CSUM_TYPE(i), nonce, bne);
1173
1174                         btree_err_on(bch2_crc_cmp(csum, bne->csum),
1175                                      BTREE_ERR_WANT_RETRY, c, b, i,
1176                                      "invalid checksum");
1177
1178                         bset_encrypt(c, i, b->written << 9);
1179
1180                         sectors = vstruct_sectors(bne, c->block_bits);
1181                 }
1182
1183                 ret = validate_bset(c, b, i, sectors, &whiteout_u64s,
1184                                     READ, have_retry);
1185                 if (ret)
1186                         goto fsck_err;
1187
1188                 b->written += sectors;
1189
1190                 ret = bch2_journal_seq_should_ignore(c, le64_to_cpu(i->journal_seq), b);
1191                 if (ret < 0) {
1192                         btree_err(BTREE_ERR_FATAL, c, b, i,
1193                                   "insufficient memory");
1194                         goto err;
1195                 }
1196
1197                 if (ret) {
1198                         btree_err_on(first,
1199                                      BTREE_ERR_FIXABLE, c, b, i,
1200                                      "first btree node bset has blacklisted journal seq");
1201                         if (!first)
1202                                 continue;
1203                 }
1204
1205                 __bch2_btree_node_iter_push(iter, b,
1206                                            i->start,
1207                                            vstruct_idx(i, whiteout_u64s));
1208
1209                 __bch2_btree_node_iter_push(iter, b,
1210                                            vstruct_idx(i, whiteout_u64s),
1211                                            vstruct_last(i));
1212         }
1213
1214         for (bne = write_block(b);
1215              bset_byte_offset(b, bne) < btree_bytes(c);
1216              bne = (void *) bne + block_bytes(c))
1217                 btree_err_on(bne->keys.seq == b->data->keys.seq,
1218                              BTREE_ERR_WANT_RETRY, c, b, NULL,
1219                              "found bset signature after last bset");
1220
1221         sorted = btree_bounce_alloc(c, btree_page_order(c), &used_mempool);
1222         sorted->keys.u64s = 0;
1223
1224         b->nr = btree_node_is_extents(b)
1225                 ? bch2_extent_sort_fix_overlapping(c, &sorted->keys, b, iter)
1226                 : bch2_key_sort_fix_overlapping(&sorted->keys, b, iter);
1227
1228         u64s = le16_to_cpu(sorted->keys.u64s);
1229         *sorted = *b->data;
1230         sorted->keys.u64s = cpu_to_le16(u64s);
1231         swap(sorted, b->data);
1232         set_btree_bset(b, b->set, &b->data->keys);
1233         b->nsets = 1;
1234
1235         BUG_ON(b->nr.live_u64s != u64s);
1236
1237         btree_bounce_free(c, btree_page_order(c), used_mempool, sorted);
1238
1239         i = &b->data->keys;
1240         for (k = i->start; k != vstruct_last(i);) {
1241                 enum bkey_type type = btree_node_type(b);
1242                 struct bkey tmp;
1243                 struct bkey_s_c u = bkey_disassemble(b, k, &tmp);
1244                 const char *invalid = bch2_bkey_val_invalid(c, type, u);
1245
1246                 if (invalid) {
1247                         char buf[160];
1248
1249                         bch2_bkey_val_to_text(c, type, buf, sizeof(buf), u);
1250                         btree_err(BTREE_ERR_FIXABLE, c, b, i,
1251                                   "invalid bkey %s: %s", buf, invalid);
1252
1253                         btree_keys_account_key_drop(&b->nr, 0, k);
1254
1255                         i->u64s = cpu_to_le16(le16_to_cpu(i->u64s) - k->u64s);
1256                         memmove_u64s_down(k, bkey_next(k),
1257                                           (u64 *) vstruct_end(i) - (u64 *) k);
1258                         continue;
1259                 }
1260
1261                 k = bkey_next(k);
1262         }
1263
1264         bch2_bset_build_aux_tree(b, b->set, false);
1265
1266         set_needs_whiteout(btree_bset_first(b));
1267
1268         btree_node_reset_sib_u64s(b);
1269 out:
1270         mempool_free(iter, &c->fill_iter);
1271         return retry_read;
1272 err:
1273 fsck_err:
1274         if (ret == BTREE_RETRY_READ) {
1275                 retry_read = 1;
1276         } else {
1277                 bch2_inconsistent_error(c);
1278                 set_btree_node_read_error(b);
1279         }
1280         goto out;
1281 }
1282
1283 static void btree_node_read_work(struct work_struct *work)
1284 {
1285         struct btree_read_bio *rb =
1286                 container_of(work, struct btree_read_bio, work);
1287         struct bch_fs *c        = rb->c;
1288         struct btree *b         = rb->bio.bi_private;
1289         struct bio *bio         = &rb->bio;
1290         struct bch_devs_mask avoid;
1291
1292         memset(&avoid, 0, sizeof(avoid));
1293
1294         goto start;
1295         do {
1296                 bch_info(c, "retrying read");
1297                 bio_reset(bio);
1298                 bio_set_dev(bio, rb->pick.ca->disk_sb.bdev);
1299                 bio->bi_opf             = REQ_OP_READ|REQ_SYNC|REQ_META;
1300                 bio->bi_iter.bi_sector  = rb->pick.ptr.offset;
1301                 bio->bi_iter.bi_size    = btree_bytes(c);
1302                 submit_bio_wait(bio);
1303 start:
1304                 bch2_dev_io_err_on(bio->bi_status, rb->pick.ca, "btree read");
1305                 percpu_ref_put(&rb->pick.ca->io_ref);
1306
1307                 __set_bit(rb->pick.ca->dev_idx, avoid.d);
1308                 rb->pick = bch2_btree_pick_ptr(c, b, &avoid);
1309
1310                 if (!bio->bi_status &&
1311                     !bch2_btree_node_read_done(c, b, !IS_ERR_OR_NULL(rb->pick.ca)))
1312                         goto out;
1313         } while (!IS_ERR_OR_NULL(rb->pick.ca));
1314
1315         set_btree_node_read_error(b);
1316 out:
1317         if (!IS_ERR_OR_NULL(rb->pick.ca))
1318                 percpu_ref_put(&rb->pick.ca->io_ref);
1319
1320         bch2_time_stats_update(&c->btree_read_time, rb->start_time);
1321         bio_put(&rb->bio);
1322         clear_btree_node_read_in_flight(b);
1323         wake_up_bit(&b->flags, BTREE_NODE_read_in_flight);
1324 }
1325
1326 static void btree_node_read_endio(struct bio *bio)
1327 {
1328         struct btree_read_bio *rb =
1329                 container_of(bio, struct btree_read_bio, bio);
1330
1331         bch2_latency_acct(rb->pick.ca, rb->start_time >> 10, READ);
1332
1333         INIT_WORK(&rb->work, btree_node_read_work);
1334         queue_work(system_unbound_wq, &rb->work);
1335 }
1336
1337 void bch2_btree_node_read(struct bch_fs *c, struct btree *b,
1338                           bool sync)
1339 {
1340         struct extent_pick_ptr pick;
1341         struct btree_read_bio *rb;
1342         struct bio *bio;
1343
1344         trace_btree_read(c, b);
1345
1346         pick = bch2_btree_pick_ptr(c, b, NULL);
1347         if (bch2_fs_fatal_err_on(!pick.ca, c,
1348                         "btree node read error: no device to read from")) {
1349                 set_btree_node_read_error(b);
1350                 return;
1351         }
1352
1353         bio = bio_alloc_bioset(GFP_NOIO, btree_pages(c), &c->btree_bio);
1354         rb = container_of(bio, struct btree_read_bio, bio);
1355         rb->c                   = c;
1356         rb->start_time          = local_clock();
1357         rb->pick                = pick;
1358         bio_set_dev(bio, pick.ca->disk_sb.bdev);
1359         bio->bi_opf             = REQ_OP_READ|REQ_SYNC|REQ_META;
1360         bio->bi_iter.bi_sector  = pick.ptr.offset;
1361         bio->bi_iter.bi_size    = btree_bytes(c);
1362         bch2_bio_map(bio, b->data);
1363
1364         this_cpu_add(pick.ca->io_done->sectors[READ][BCH_DATA_BTREE],
1365                      bio_sectors(bio));
1366
1367         set_btree_node_read_in_flight(b);
1368
1369         if (sync) {
1370                 submit_bio_wait(bio);
1371                 bio->bi_private = b;
1372                 btree_node_read_work(&rb->work);
1373         } else {
1374                 bio->bi_end_io  = btree_node_read_endio;
1375                 bio->bi_private = b;
1376                 submit_bio(bio);
1377         }
1378 }
1379
1380 int bch2_btree_root_read(struct bch_fs *c, enum btree_id id,
1381                         const struct bkey_i *k, unsigned level)
1382 {
1383         struct closure cl;
1384         struct btree *b;
1385         int ret;
1386
1387         closure_init_stack(&cl);
1388
1389         do {
1390                 ret = bch2_btree_cache_cannibalize_lock(c, &cl);
1391                 closure_sync(&cl);
1392         } while (ret);
1393
1394         b = bch2_btree_node_mem_alloc(c);
1395         bch2_btree_cache_cannibalize_unlock(c);
1396
1397         BUG_ON(IS_ERR(b));
1398
1399         bkey_copy(&b->key, k);
1400         BUG_ON(bch2_btree_node_hash_insert(&c->btree_cache, b, level, id));
1401
1402         bch2_btree_node_read(c, b, true);
1403
1404         if (btree_node_read_error(b)) {
1405                 bch2_btree_node_hash_remove(&c->btree_cache, b);
1406
1407                 mutex_lock(&c->btree_cache.lock);
1408                 list_move(&b->list, &c->btree_cache.freeable);
1409                 mutex_unlock(&c->btree_cache.lock);
1410
1411                 ret = -EIO;
1412                 goto err;
1413         }
1414
1415         bch2_btree_set_root_for_read(c, b);
1416 err:
1417         six_unlock_write(&b->lock);
1418         six_unlock_intent(&b->lock);
1419
1420         return ret;
1421 }
1422
1423 void bch2_btree_complete_write(struct bch_fs *c, struct btree *b,
1424                               struct btree_write *w)
1425 {
1426         unsigned long old, new, v = READ_ONCE(b->will_make_reachable);
1427
1428         do {
1429                 old = new = v;
1430                 if (!(old & 1))
1431                         break;
1432
1433                 new &= ~1UL;
1434         } while ((v = cmpxchg(&b->will_make_reachable, old, new)) != old);
1435
1436         if (old & 1)
1437                 closure_put(&((struct btree_update *) new)->cl);
1438
1439         bch2_journal_pin_drop(&c->journal, &w->journal);
1440         closure_wake_up(&w->wait);
1441 }
1442
1443 static void btree_node_write_done(struct bch_fs *c, struct btree *b)
1444 {
1445         struct btree_write *w = btree_prev_write(b);
1446
1447         bch2_btree_complete_write(c, b, w);
1448         btree_node_io_unlock(b);
1449 }
1450
1451 static void bch2_btree_node_write_error(struct bch_fs *c,
1452                                         struct btree_write_bio *wbio)
1453 {
1454         struct btree *b         = wbio->wbio.bio.bi_private;
1455         __BKEY_PADDED(k, BKEY_BTREE_PTR_VAL_U64s_MAX) tmp;
1456         struct bkey_i_extent *new_key;
1457         struct bkey_s_extent e;
1458         struct bch_extent_ptr *ptr;
1459         struct btree_iter iter;
1460         int ret;
1461
1462         __bch2_btree_iter_init(&iter, c, b->btree_id, b->key.k.p,
1463                                BTREE_MAX_DEPTH,
1464                                b->level, 0);
1465 retry:
1466         ret = bch2_btree_iter_traverse(&iter);
1467         if (ret)
1468                 goto err;
1469
1470         /* has node been freed? */
1471         if (iter.l[b->level].b != b) {
1472                 /* node has been freed: */
1473                 BUG_ON(!btree_node_dying(b));
1474                 goto out;
1475         }
1476
1477         BUG_ON(!btree_node_hashed(b));
1478
1479         bkey_copy(&tmp.k, &b->key);
1480
1481         new_key = bkey_i_to_extent(&tmp.k);
1482         e = extent_i_to_s(new_key);
1483         extent_for_each_ptr_backwards(e, ptr)
1484                 if (bch2_dev_list_has_dev(wbio->wbio.failed, ptr->dev))
1485                         bch2_extent_drop_ptr(e, ptr);
1486
1487         if (!bch2_extent_nr_ptrs(e.c))
1488                 goto err;
1489
1490         ret = bch2_btree_node_update_key(c, &iter, b, new_key);
1491         if (ret == -EINTR)
1492                 goto retry;
1493         if (ret)
1494                 goto err;
1495 out:
1496         bch2_btree_iter_unlock(&iter);
1497         bio_put(&wbio->wbio.bio);
1498         btree_node_write_done(c, b);
1499         return;
1500 err:
1501         set_btree_node_noevict(b);
1502         bch2_fs_fatal_error(c, "fatal error writing btree node");
1503         goto out;
1504 }
1505
1506 void bch2_btree_write_error_work(struct work_struct *work)
1507 {
1508         struct bch_fs *c = container_of(work, struct bch_fs,
1509                                         btree_write_error_work);
1510         struct bio *bio;
1511
1512         while (1) {
1513                 spin_lock_irq(&c->btree_write_error_lock);
1514                 bio = bio_list_pop(&c->btree_write_error_list);
1515                 spin_unlock_irq(&c->btree_write_error_lock);
1516
1517                 if (!bio)
1518                         break;
1519
1520                 bch2_btree_node_write_error(c,
1521                         container_of(bio, struct btree_write_bio, wbio.bio));
1522         }
1523 }
1524
1525 static void btree_node_write_work(struct work_struct *work)
1526 {
1527         struct btree_write_bio *wbio =
1528                 container_of(work, struct btree_write_bio, work);
1529         struct bch_fs *c        = wbio->wbio.c;
1530         struct btree *b         = wbio->wbio.bio.bi_private;
1531
1532         btree_bounce_free(c,
1533                 wbio->wbio.order,
1534                 wbio->wbio.used_mempool,
1535                 wbio->data);
1536
1537         if (wbio->wbio.failed.nr) {
1538                 unsigned long flags;
1539
1540                 spin_lock_irqsave(&c->btree_write_error_lock, flags);
1541                 bio_list_add(&c->btree_write_error_list, &wbio->wbio.bio);
1542                 spin_unlock_irqrestore(&c->btree_write_error_lock, flags);
1543
1544                 queue_work(c->wq, &c->btree_write_error_work);
1545                 return;
1546         }
1547
1548         bio_put(&wbio->wbio.bio);
1549         btree_node_write_done(c, b);
1550 }
1551
1552 static void btree_node_write_endio(struct bio *bio)
1553 {
1554         struct bch_write_bio *wbio      = to_wbio(bio);
1555         struct bch_write_bio *parent    = wbio->split ? wbio->parent : NULL;
1556         struct bch_write_bio *orig      = parent ?: wbio;
1557         struct bch_fs *c                = wbio->c;
1558         struct bch_dev *ca              = wbio->ca;
1559         unsigned long flags;
1560
1561         bch2_latency_acct(ca, wbio->submit_time_us, WRITE);
1562
1563         if (bio->bi_status == BLK_STS_REMOVED ||
1564             bch2_dev_io_err_on(bio->bi_status, ca, "btree write") ||
1565             bch2_meta_write_fault("btree")) {
1566                 spin_lock_irqsave(&c->btree_write_error_lock, flags);
1567                 bch2_dev_list_add_dev(&orig->failed, ca->dev_idx);
1568                 spin_unlock_irqrestore(&c->btree_write_error_lock, flags);
1569         }
1570
1571         if (wbio->have_io_ref)
1572                 percpu_ref_put(&ca->io_ref);
1573
1574         if (parent) {
1575                 bio_put(bio);
1576                 bio_endio(&parent->bio);
1577         } else {
1578                 struct btree_write_bio *wb =
1579                         container_of(orig, struct btree_write_bio, wbio);
1580
1581                 INIT_WORK(&wb->work, btree_node_write_work);
1582                 queue_work(system_unbound_wq, &wb->work);
1583         }
1584 }
1585
1586 static int validate_bset_for_write(struct bch_fs *c, struct btree *b,
1587                                    struct bset *i, unsigned sectors)
1588 {
1589         const struct bch_extent_ptr *ptr;
1590         unsigned whiteout_u64s = 0;
1591         int ret;
1592
1593         extent_for_each_ptr(bkey_i_to_s_c_extent(&b->key), ptr)
1594                 break;
1595
1596         ret = validate_bset(c, b, i, sectors, &whiteout_u64s, WRITE, false);
1597         if (ret)
1598                 bch2_inconsistent_error(c);
1599
1600         return ret;
1601 }
1602
1603 void __bch2_btree_node_write(struct bch_fs *c, struct btree *b,
1604                             enum six_lock_type lock_type_held)
1605 {
1606         struct btree_write_bio *wbio;
1607         struct bset_tree *t;
1608         struct bset *i;
1609         struct btree_node *bn = NULL;
1610         struct btree_node_entry *bne = NULL;
1611         BKEY_PADDED(key) k;
1612         struct bkey_s_extent e;
1613         struct bch_extent_ptr *ptr;
1614         struct sort_iter sort_iter;
1615         struct nonce nonce;
1616         unsigned bytes_to_write, sectors_to_write, order, bytes, u64s;
1617         u64 seq = 0;
1618         bool used_mempool;
1619         unsigned long old, new;
1620         void *data;
1621
1622         if (test_bit(BCH_FS_HOLD_BTREE_WRITES, &c->flags))
1623                 return;
1624
1625         /*
1626          * We may only have a read lock on the btree node - the dirty bit is our
1627          * "lock" against racing with other threads that may be trying to start
1628          * a write, we do a write iff we clear the dirty bit. Since setting the
1629          * dirty bit requires a write lock, we can't race with other threads
1630          * redirtying it:
1631          */
1632         do {
1633                 old = new = READ_ONCE(b->flags);
1634
1635                 if (!(old & (1 << BTREE_NODE_dirty)))
1636                         return;
1637
1638                 if (b->written &&
1639                     !btree_node_may_write(b))
1640                         return;
1641
1642                 if (old & (1 << BTREE_NODE_write_in_flight)) {
1643                         btree_node_wait_on_io(b);
1644                         continue;
1645                 }
1646
1647                 new &= ~(1 << BTREE_NODE_dirty);
1648                 new &= ~(1 << BTREE_NODE_need_write);
1649                 new |=  (1 << BTREE_NODE_write_in_flight);
1650                 new |=  (1 << BTREE_NODE_just_written);
1651                 new ^=  (1 << BTREE_NODE_write_idx);
1652         } while (cmpxchg_acquire(&b->flags, old, new) != old);
1653
1654         BUG_ON(btree_node_fake(b));
1655         BUG_ON(!list_empty(&b->write_blocked));
1656         BUG_ON((b->will_make_reachable != 0) != !b->written);
1657
1658         BUG_ON(b->written >= c->opts.btree_node_size);
1659         BUG_ON(bset_written(b, btree_bset_last(b)));
1660         BUG_ON(le64_to_cpu(b->data->magic) != bset_magic(c));
1661         BUG_ON(memcmp(&b->data->format, &b->format, sizeof(b->format)));
1662
1663         /*
1664          * We can't block on six_lock_write() here; another thread might be
1665          * trying to get a journal reservation with read locks held, and getting
1666          * a journal reservation might be blocked on flushing the journal and
1667          * doing btree writes:
1668          */
1669         if (lock_type_held == SIX_LOCK_intent &&
1670             six_trylock_write(&b->lock)) {
1671                 __bch2_compact_whiteouts(c, b, COMPACT_WRITTEN);
1672                 six_unlock_write(&b->lock);
1673         } else {
1674                 __bch2_compact_whiteouts(c, b, COMPACT_WRITTEN_NO_WRITE_LOCK);
1675         }
1676
1677         BUG_ON(b->uncompacted_whiteout_u64s);
1678
1679         sort_iter_init(&sort_iter, b);
1680
1681         bytes = !b->written
1682                 ? sizeof(struct btree_node)
1683                 : sizeof(struct btree_node_entry);
1684
1685         bytes += b->whiteout_u64s * sizeof(u64);
1686
1687         for_each_bset(b, t) {
1688                 i = bset(b, t);
1689
1690                 if (bset_written(b, i))
1691                         continue;
1692
1693                 bytes += le16_to_cpu(i->u64s) * sizeof(u64);
1694                 sort_iter_add(&sort_iter,
1695                               btree_bkey_first(b, t),
1696                               btree_bkey_last(b, t));
1697                 seq = max(seq, le64_to_cpu(i->journal_seq));
1698         }
1699
1700         order = get_order(bytes);
1701         data = btree_bounce_alloc(c, order, &used_mempool);
1702
1703         if (!b->written) {
1704                 bn = data;
1705                 *bn = *b->data;
1706                 i = &bn->keys;
1707         } else {
1708                 bne = data;
1709                 bne->keys = b->data->keys;
1710                 i = &bne->keys;
1711         }
1712
1713         i->journal_seq  = cpu_to_le64(seq);
1714         i->u64s         = 0;
1715
1716         if (!btree_node_is_extents(b)) {
1717                 sort_iter_add(&sort_iter,
1718                               unwritten_whiteouts_start(c, b),
1719                               unwritten_whiteouts_end(c, b));
1720                 SET_BSET_SEPARATE_WHITEOUTS(i, false);
1721         } else {
1722                 memcpy_u64s(i->start,
1723                             unwritten_whiteouts_start(c, b),
1724                             b->whiteout_u64s);
1725                 i->u64s = cpu_to_le16(b->whiteout_u64s);
1726                 SET_BSET_SEPARATE_WHITEOUTS(i, true);
1727         }
1728
1729         b->whiteout_u64s = 0;
1730
1731         u64s = btree_node_is_extents(b)
1732                 ? sort_extents(vstruct_last(i), &sort_iter, false)
1733                 : sort_keys(i->start, &sort_iter, false);
1734         le16_add_cpu(&i->u64s, u64s);
1735
1736         clear_needs_whiteout(i);
1737
1738         /* do we have data to write? */
1739         if (b->written && !i->u64s)
1740                 goto nowrite;
1741
1742         bytes_to_write = vstruct_end(i) - data;
1743         sectors_to_write = round_up(bytes_to_write, block_bytes(c)) >> 9;
1744
1745         memset(data + bytes_to_write, 0,
1746                (sectors_to_write << 9) - bytes_to_write);
1747
1748         BUG_ON(b->written + sectors_to_write > c->opts.btree_node_size);
1749         BUG_ON(BSET_BIG_ENDIAN(i) != CPU_BIG_ENDIAN);
1750         BUG_ON(i->seq != b->data->keys.seq);
1751
1752         i->version = cpu_to_le16(BCACHE_BSET_VERSION);
1753         SET_BSET_CSUM_TYPE(i, bch2_meta_checksum_type(c));
1754
1755         /* if we're going to be encrypting, check metadata validity first: */
1756         if (bch2_csum_type_is_encryption(BSET_CSUM_TYPE(i)) &&
1757             validate_bset_for_write(c, b, i, sectors_to_write))
1758                 goto err;
1759
1760         bset_encrypt(c, i, b->written << 9);
1761
1762         nonce = btree_nonce(i, b->written << 9);
1763
1764         if (bn)
1765                 bn->csum = csum_vstruct(c, BSET_CSUM_TYPE(i), nonce, bn);
1766         else
1767                 bne->csum = csum_vstruct(c, BSET_CSUM_TYPE(i), nonce, bne);
1768
1769         /* if we're not encrypting, check metadata after checksumming: */
1770         if (!bch2_csum_type_is_encryption(BSET_CSUM_TYPE(i)) &&
1771             validate_bset_for_write(c, b, i, sectors_to_write))
1772                 goto err;
1773
1774         /*
1775          * We handle btree write errors by immediately halting the journal -
1776          * after we've done that, we can't issue any subsequent btree writes
1777          * because they might have pointers to new nodes that failed to write.
1778          *
1779          * Furthermore, there's no point in doing any more btree writes because
1780          * with the journal stopped, we're never going to update the journal to
1781          * reflect that those writes were done and the data flushed from the
1782          * journal:
1783          *
1784          * Make sure to update b->written so bch2_btree_init_next() doesn't
1785          * break:
1786          */
1787         if (bch2_journal_error(&c->journal) ||
1788             c->opts.nochanges)
1789                 goto err;
1790
1791         trace_btree_write(b, bytes_to_write, sectors_to_write);
1792
1793         wbio = container_of(bio_alloc_bioset(GFP_NOIO, 1 << order, &c->btree_bio),
1794                             struct btree_write_bio, wbio.bio);
1795         wbio_init(&wbio->wbio.bio);
1796         wbio->data                      = data;
1797         wbio->wbio.order                = order;
1798         wbio->wbio.used_mempool         = used_mempool;
1799         wbio->wbio.bio.bi_opf           = REQ_OP_WRITE|REQ_META|REQ_FUA;
1800         wbio->wbio.bio.bi_iter.bi_size  = sectors_to_write << 9;
1801         wbio->wbio.bio.bi_end_io        = btree_node_write_endio;
1802         wbio->wbio.bio.bi_private       = b;
1803
1804         bch2_bio_map(&wbio->wbio.bio, data);
1805
1806         /*
1807          * If we're appending to a leaf node, we don't technically need FUA -
1808          * this write just needs to be persisted before the next journal write,
1809          * which will be marked FLUSH|FUA.
1810          *
1811          * Similarly if we're writing a new btree root - the pointer is going to
1812          * be in the next journal entry.
1813          *
1814          * But if we're writing a new btree node (that isn't a root) or
1815          * appending to a non leaf btree node, we need either FUA or a flush
1816          * when we write the parent with the new pointer. FUA is cheaper than a
1817          * flush, and writes appending to leaf nodes aren't blocking anything so
1818          * just make all btree node writes FUA to keep things sane.
1819          */
1820
1821         bkey_copy(&k.key, &b->key);
1822         e = bkey_i_to_s_extent(&k.key);
1823
1824         extent_for_each_ptr(e, ptr)
1825                 ptr->offset += b->written;
1826
1827         b->written += sectors_to_write;
1828
1829         bch2_submit_wbio_replicas(&wbio->wbio, c, BCH_DATA_BTREE, &k.key);
1830         return;
1831 err:
1832         set_btree_node_noevict(b);
1833         b->written += sectors_to_write;
1834 nowrite:
1835         btree_bounce_free(c, order, used_mempool, data);
1836         btree_node_write_done(c, b);
1837 }
1838
1839 /*
1840  * Work that must be done with write lock held:
1841  */
1842 bool bch2_btree_post_write_cleanup(struct bch_fs *c, struct btree *b)
1843 {
1844         bool invalidated_iter = false;
1845         struct btree_node_entry *bne;
1846         struct bset_tree *t;
1847
1848         if (!btree_node_just_written(b))
1849                 return false;
1850
1851         BUG_ON(b->whiteout_u64s);
1852         BUG_ON(b->uncompacted_whiteout_u64s);
1853
1854         clear_btree_node_just_written(b);
1855
1856         /*
1857          * Note: immediately after write, bset_unwritten()/bset_written() don't
1858          * work - the amount of data we had to write after compaction might have
1859          * been smaller than the offset of the last bset.
1860          *
1861          * However, we know that all bsets have been written here, as long as
1862          * we're still holding the write lock:
1863          */
1864
1865         /*
1866          * XXX: decide if we really want to unconditionally sort down to a
1867          * single bset:
1868          */
1869         if (b->nsets > 1) {
1870                 btree_node_sort(c, b, NULL, 0, b->nsets, true);
1871                 invalidated_iter = true;
1872         } else {
1873                 invalidated_iter = bch2_drop_whiteouts(b);
1874         }
1875
1876         for_each_bset(b, t)
1877                 set_needs_whiteout(bset(b, t));
1878
1879         bch2_btree_verify(c, b);
1880
1881         /*
1882          * If later we don't unconditionally sort down to a single bset, we have
1883          * to ensure this is still true:
1884          */
1885         BUG_ON((void *) btree_bkey_last(b, bset_tree_last(b)) > write_block(b));
1886
1887         bne = want_new_bset(c, b);
1888         if (bne)
1889                 bch2_bset_init_next(b, &bne->keys);
1890
1891         bch2_btree_build_aux_trees(b);
1892
1893         return invalidated_iter;
1894 }
1895
1896 /*
1897  * Use this one if the node is intent locked:
1898  */
1899 void bch2_btree_node_write(struct bch_fs *c, struct btree *b,
1900                           enum six_lock_type lock_type_held)
1901 {
1902         BUG_ON(lock_type_held == SIX_LOCK_write);
1903
1904         if (lock_type_held == SIX_LOCK_intent ||
1905             six_lock_tryupgrade(&b->lock)) {
1906                 __bch2_btree_node_write(c, b, SIX_LOCK_intent);
1907
1908                 /* don't cycle lock unnecessarily: */
1909                 if (btree_node_just_written(b) &&
1910                     six_trylock_write(&b->lock)) {
1911                         bch2_btree_post_write_cleanup(c, b);
1912                         six_unlock_write(&b->lock);
1913                 }
1914
1915                 if (lock_type_held == SIX_LOCK_read)
1916                         six_lock_downgrade(&b->lock);
1917         } else {
1918                 __bch2_btree_node_write(c, b, SIX_LOCK_read);
1919         }
1920 }
1921
1922 static void __bch2_btree_flush_all(struct bch_fs *c, unsigned flag)
1923 {
1924         struct bucket_table *tbl;
1925         struct rhash_head *pos;
1926         struct btree *b;
1927         unsigned i;
1928 restart:
1929         rcu_read_lock();
1930         for_each_cached_btree(b, c, tbl, i, pos)
1931                 if (test_bit(flag, &b->flags)) {
1932                         rcu_read_unlock();
1933                         wait_on_bit_io(&b->flags, flag, TASK_UNINTERRUPTIBLE);
1934                         goto restart;
1935
1936                 }
1937         rcu_read_unlock();
1938 }
1939
1940 void bch2_btree_flush_all_reads(struct bch_fs *c)
1941 {
1942         __bch2_btree_flush_all(c, BTREE_NODE_read_in_flight);
1943 }
1944
1945 void bch2_btree_flush_all_writes(struct bch_fs *c)
1946 {
1947         __bch2_btree_flush_all(c, BTREE_NODE_write_in_flight);
1948 }
1949
1950 void bch2_btree_verify_flushed(struct bch_fs *c)
1951 {
1952         struct bucket_table *tbl;
1953         struct rhash_head *pos;
1954         struct btree *b;
1955         unsigned i;
1956
1957         rcu_read_lock();
1958         for_each_cached_btree(b, c, tbl, i, pos) {
1959                 unsigned long flags = READ_ONCE(b->flags);
1960
1961                 BUG_ON((flags & (1 << BTREE_NODE_dirty)) ||
1962                        (flags & (1 << BTREE_NODE_write_in_flight)));
1963         }
1964         rcu_read_unlock();
1965 }
1966
1967 ssize_t bch2_dirty_btree_nodes_print(struct bch_fs *c, char *buf)
1968 {
1969         char *out = buf, *end = buf + PAGE_SIZE;
1970         struct bucket_table *tbl;
1971         struct rhash_head *pos;
1972         struct btree *b;
1973         unsigned i;
1974
1975         rcu_read_lock();
1976         for_each_cached_btree(b, c, tbl, i, pos) {
1977                 unsigned long flags = READ_ONCE(b->flags);
1978                 unsigned idx = (flags & (1 << BTREE_NODE_write_idx)) != 0;
1979
1980                 if (//!(flags & (1 << BTREE_NODE_dirty)) &&
1981                     !b->writes[0].wait.list.first &&
1982                     !b->writes[1].wait.list.first &&
1983                     !(b->will_make_reachable & 1))
1984                         continue;
1985
1986                 out += scnprintf(out, end - out, "%p d %u l %u w %u b %u r %u:%lu c %u p %u\n",
1987                                  b,
1988                                  (flags & (1 << BTREE_NODE_dirty)) != 0,
1989                                  b->level,
1990                                  b->written,
1991                                  !list_empty_careful(&b->write_blocked),
1992                                  b->will_make_reachable != 0,
1993                                  b->will_make_reachable & 1,
1994                                  b->writes[ idx].wait.list.first != NULL,
1995                                  b->writes[!idx].wait.list.first != NULL);
1996         }
1997         rcu_read_unlock();
1998
1999         return out - buf;
2000 }