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