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

   1 /*
   2  * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
   3  *
   4  * Code for managing the extent btree and dynamically updating the writeback
   5  * dirty sector count.
   6  */
   7
   8 #include "bcachefs.h"
   9 #include "bkey_methods.h"
  10 #include "btree_gc.h"
  11 #include "btree_update.h"
  12 #include "btree_update_interior.h"
  13 #include "buckets.h"
  14 #include "checksum.h"
  15 #include "debug.h"
  16 #include "dirent.h"
  17 #include "error.h"
  18 #include "extents.h"
  19 #include "inode.h"
  20 #include "journal.h"
  21 #include "super.h"
  22 #include "super-io.h"
  23 #include "util.h"
  24 #include "xattr.h"
  25
  26 #include <trace/events/bcachefs.h>
  27
  28 static enum merge_result bch2_extent_merge(struct bch_fs *, struct btree *,
  29                                            struct bkey_i *, struct bkey_i *);
  30
  31 static void sort_key_next(struct btree_node_iter_large *iter,
  32                           struct btree *b,
  33                           struct btree_node_iter_set *i)
  34 {
  35         i->k += __btree_node_offset_to_key(b, i->k)->u64s;
  36
  37         if (i->k == i->end)
  38                 *i = iter->data[--iter->used];
  39 }
  40
  41 /*
  42  * Returns true if l > r - unless l == r, in which case returns true if l is
  43  * older than r.
  44  *
  45  * Necessary for btree_sort_fixup() - if there are multiple keys that compare
  46  * equal in different sets, we have to process them newest to oldest.
  47  */
  48 #define key_sort_cmp(h, l, r)                                           \
  49 ({                                                                      \
  50         bkey_cmp_packed(b,                                              \
  51                         __btree_node_offset_to_key(b, (l).k),           \
  52                         __btree_node_offset_to_key(b, (r).k))           \
  53                                                                         \
  54         ?: (l).k - (r).k;                                               \
  55 })
  56
  57 static inline bool should_drop_next_key(struct btree_node_iter_large *iter,
  58                                         struct btree *b)
  59 {
  60         struct btree_node_iter_set *l = iter->data, *r = iter->data + 1;
  61         struct bkey_packed *k = __btree_node_offset_to_key(b, l->k);
  62
  63         if (bkey_whiteout(k))
  64                 return true;
  65
  66         if (iter->used < 2)
  67                 return false;
  68
  69         if (iter->used > 2 &&
  70             key_sort_cmp(iter, r[0], r[1]) >= 0)
  71                 r++;
  72
  73         /*
  74          * key_sort_cmp() ensures that when keys compare equal the older key
  75          * comes first; so if l->k compares equal to r->k then l->k is older and
  76          * should be dropped.
  77          */
  78         return !bkey_cmp_packed(b,
  79                                 __btree_node_offset_to_key(b, l->k),
  80                                 __btree_node_offset_to_key(b, r->k));
  81 }
  82
  83 struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *dst,
  84                                         struct btree *b,
  85                                         struct btree_node_iter_large *iter)
  86 {
  87         struct bkey_packed *out = dst->start;
  88         struct btree_nr_keys nr;
  89
  90         memset(&nr, 0, sizeof(nr));
  91
  92         heap_resort(iter, key_sort_cmp);
  93
  94         while (!bch2_btree_node_iter_large_end(iter)) {
  95                 if (!should_drop_next_key(iter, b)) {
  96                         struct bkey_packed *k =
  97                                 __btree_node_offset_to_key(b, iter->data->k);
  98
  99                         bkey_copy(out, k);
 100                         btree_keys_account_key_add(&nr, 0, out);
 101                         out = bkey_next(out);
 102                 }
 103
 104                 sort_key_next(iter, b, iter->data);
 105                 heap_sift_down(iter, 0, key_sort_cmp);
 106         }
 107
 108         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
 109         return nr;
 110 }
 111
 112 /* Common among btree and extent ptrs */
 113
 114 const struct bch_extent_ptr *
 115 bch2_extent_has_device(struct bkey_s_c_extent e, unsigned dev)
 116 {
 117         const struct bch_extent_ptr *ptr;
 118
 119         extent_for_each_ptr(e, ptr)
 120                 if (ptr->dev == dev)
 121                         return ptr;
 122
 123         return NULL;
 124 }
 125
 126 bool bch2_extent_drop_device(struct bkey_s_extent e, unsigned dev)
 127 {
 128         struct bch_extent_ptr *ptr;
 129         bool dropped = false;
 130
 131         extent_for_each_ptr_backwards(e, ptr)
 132                 if (ptr->dev == dev) {
 133                         __bch2_extent_drop_ptr(e, ptr);
 134                         dropped = true;
 135                 }
 136
 137         if (dropped)
 138                 bch2_extent_drop_redundant_crcs(e);
 139         return dropped;
 140 }
 141
 142 const struct bch_extent_ptr *
 143 bch2_extent_has_group(struct bch_fs *c, struct bkey_s_c_extent e, unsigned group)
 144 {
 145         const struct bch_extent_ptr *ptr;
 146
 147         extent_for_each_ptr(e, ptr) {
 148                 struct bch_dev *ca = c->devs[ptr->dev];
 149
 150                 if (ca->mi.group &&
 151                     ca->mi.group - 1 == group)
 152                         return ptr;
 153         }
 154
 155         return NULL;
 156 }
 157
 158 const struct bch_extent_ptr *
 159 bch2_extent_has_target(struct bch_fs *c, struct bkey_s_c_extent e, unsigned target)
 160 {
 161         const struct bch_extent_ptr *ptr;
 162
 163         extent_for_each_ptr(e, ptr)
 164                 if (dev_in_target(c->devs[ptr->dev], target))
 165                         return ptr;
 166
 167         return NULL;
 168 }
 169
 170 unsigned bch2_extent_nr_ptrs(struct bkey_s_c_extent e)
 171 {
 172         const struct bch_extent_ptr *ptr;
 173         unsigned nr_ptrs = 0;
 174
 175         extent_for_each_ptr(e, ptr)
 176                 nr_ptrs++;
 177
 178         return nr_ptrs;
 179 }
 180
 181 unsigned bch2_extent_nr_dirty_ptrs(struct bkey_s_c k)
 182 {
 183         struct bkey_s_c_extent e;
 184         const struct bch_extent_ptr *ptr;
 185         unsigned nr_ptrs = 0;
 186
 187         switch (k.k->type) {
 188         case BCH_EXTENT:
 189         case BCH_EXTENT_CACHED:
 190                 e = bkey_s_c_to_extent(k);
 191
 192                 extent_for_each_ptr(e, ptr)
 193                         nr_ptrs += !ptr->cached;
 194                 break;
 195
 196         case BCH_RESERVATION:
 197                 nr_ptrs = bkey_s_c_to_reservation(k).v->nr_replicas;
 198                 break;
 199         }
 200
 201         return nr_ptrs;
 202 }
 203
 204 unsigned bch2_extent_ptr_durability(struct bch_fs *c,
 205                                     const struct bch_extent_ptr *ptr)
 206 {
 207         struct bch_dev *ca;
 208
 209         if (ptr->cached)
 210                 return 0;
 211
 212         ca = bch_dev_bkey_exists(c, ptr->dev);
 213
 214         if (ca->mi.state == BCH_MEMBER_STATE_FAILED)
 215                 return 0;
 216
 217         return ca->mi.durability;
 218 }
 219
 220 unsigned bch2_extent_durability(struct bch_fs *c, struct bkey_s_c_extent e)
 221 {
 222         const struct bch_extent_ptr *ptr;
 223         unsigned durability = 0;
 224
 225         extent_for_each_ptr(e, ptr)
 226                 durability += bch2_extent_ptr_durability(c, ptr);
 227
 228         return durability;
 229 }
 230
 231 unsigned bch2_extent_is_compressed(struct bkey_s_c k)
 232 {
 233         struct bkey_s_c_extent e;
 234         const struct bch_extent_ptr *ptr;
 235         struct bch_extent_crc_unpacked crc;
 236         unsigned ret = 0;
 237
 238         switch (k.k->type) {
 239         case BCH_EXTENT:
 240         case BCH_EXTENT_CACHED:
 241                 e = bkey_s_c_to_extent(k);
 242
 243                 extent_for_each_ptr_crc(e, ptr, crc)
 244                         if (!ptr->cached &&
 245                             crc.compression_type != BCH_COMPRESSION_NONE &&
 246                             crc.compressed_size < crc.live_size)
 247                                 ret = max_t(unsigned, ret, crc.compressed_size);
 248         }
 249
 250         return ret;
 251 }
 252
 253 bool bch2_extent_matches_ptr(struct bch_fs *c, struct bkey_s_c_extent e,
 254                              struct bch_extent_ptr m, u64 offset)
 255 {
 256         const struct bch_extent_ptr *ptr;
 257         struct bch_extent_crc_unpacked crc;
 258
 259         extent_for_each_ptr_crc(e, ptr, crc)
 260                 if (ptr->dev    == m.dev &&
 261                     ptr->gen    == m.gen &&
 262                     (s64) ptr->offset + crc.offset - bkey_start_offset(e.k) ==
 263                     (s64) m.offset  - offset)
 264                         return ptr;
 265
 266         return NULL;
 267 }
 268
 269 /* Doesn't cleanup redundant crcs */
 270 void __bch2_extent_drop_ptr(struct bkey_s_extent e, struct bch_extent_ptr *ptr)
 271 {
 272         EBUG_ON(ptr < &e.v->start->ptr ||
 273                 ptr >= &extent_entry_last(e)->ptr);
 274         EBUG_ON(ptr->type != 1 << BCH_EXTENT_ENTRY_ptr);
 275         memmove_u64s_down(ptr, ptr + 1,
 276                           (u64 *) extent_entry_last(e) - (u64 *) (ptr + 1));
 277         e.k->u64s -= sizeof(*ptr) / sizeof(u64);
 278 }
 279
 280 void bch2_extent_drop_ptr(struct bkey_s_extent e, struct bch_extent_ptr *ptr)
 281 {
 282         __bch2_extent_drop_ptr(e, ptr);
 283         bch2_extent_drop_redundant_crcs(e);
 284 }
 285
 286 static inline bool can_narrow_crc(struct bch_extent_crc_unpacked u,
 287                                   struct bch_extent_crc_unpacked n)
 288 {
 289         return !u.compression_type &&
 290                 u.csum_type &&
 291                 u.uncompressed_size > u.live_size &&
 292                 bch2_csum_type_is_encryption(u.csum_type) ==
 293                 bch2_csum_type_is_encryption(n.csum_type);
 294 }
 295
 296 bool bch2_can_narrow_extent_crcs(struct bkey_s_c_extent e,
 297                                  struct bch_extent_crc_unpacked n)
 298 {
 299         struct bch_extent_crc_unpacked crc;
 300         const union bch_extent_entry *i;
 301
 302         if (!n.csum_type)
 303                 return false;
 304
 305         extent_for_each_crc(e, crc, i)
 306                 if (can_narrow_crc(crc, n))
 307                         return true;
 308
 309         return false;
 310 }
 311
 312 /*
 313  * We're writing another replica for this extent, so while we've got the data in
 314  * memory we'll be computing a new checksum for the currently live data.
 315  *
 316  * If there are other replicas we aren't moving, and they are checksummed but
 317  * not compressed, we can modify them to point to only the data that is
 318  * currently live (so that readers won't have to bounce) while we've got the
 319  * checksum we need:
 320  */
 321 bool bch2_extent_narrow_crcs(struct bkey_i_extent *e,
 322                              struct bch_extent_crc_unpacked n)
 323 {
 324         struct bch_extent_crc_unpacked u;
 325         struct bch_extent_ptr *ptr;
 326         union bch_extent_entry *i;
 327
 328         /* Find a checksum entry that covers only live data: */
 329         if (!n.csum_type)
 330                 extent_for_each_crc(extent_i_to_s(e), u, i)
 331                         if (!u.compression_type &&
 332                             u.csum_type &&
 333                             u.live_size == u.uncompressed_size) {
 334                                 n = u;
 335                                 break;
 336                         }
 337
 338         if (!bch2_can_narrow_extent_crcs(extent_i_to_s_c(e), n))
 339                 return false;
 340
 341         BUG_ON(n.compression_type);
 342         BUG_ON(n.offset);
 343         BUG_ON(n.live_size != e->k.size);
 344
 345         bch2_extent_crc_append(e, n);
 346 restart_narrow_pointers:
 347         extent_for_each_ptr_crc(extent_i_to_s(e), ptr, u)
 348                 if (can_narrow_crc(u, n)) {
 349                         ptr->offset += u.offset;
 350                         extent_ptr_append(e, *ptr);
 351                         __bch2_extent_drop_ptr(extent_i_to_s(e), ptr);
 352                         goto restart_narrow_pointers;
 353                 }
 354
 355         bch2_extent_drop_redundant_crcs(extent_i_to_s(e));
 356         return true;
 357 }
 358
 359 void bch2_extent_drop_redundant_crcs(struct bkey_s_extent e)
 360 {
 361         union bch_extent_entry *entry = e.v->start;
 362         union bch_extent_crc *crc, *prev = NULL;
 363         struct bch_extent_crc_unpacked u, prev_u;
 364
 365         while (entry != extent_entry_last(e)) {
 366                 union bch_extent_entry *next = extent_entry_next(entry);
 367                 size_t crc_u64s = extent_entry_u64s(entry);
 368
 369                 if (!extent_entry_is_crc(entry))
 370                         goto next;
 371
 372                 crc = entry_to_crc(entry);
 373                 u = bch2_extent_crc_unpack(e.k, crc);
 374
 375                 if (next == extent_entry_last(e)) {
 376                         /* crc entry with no pointers after it: */
 377                         goto drop;
 378                 }
 379
 380                 if (extent_entry_is_crc(next)) {
 381                         /* no pointers before next crc entry: */
 382                         goto drop;
 383                 }
 384
 385                 if (prev && !memcmp(&u, &prev_u, sizeof(u))) {
 386                         /* identical to previous crc entry: */
 387                         goto drop;
 388                 }
 389
 390                 if (!prev &&
 391                     !u.csum_type &&
 392                     !u.compression_type) {
 393                         /* null crc entry: */
 394                         union bch_extent_entry *e2;
 395
 396                         extent_for_each_entry_from(e, e2, extent_entry_next(entry)) {
 397                                 if (!extent_entry_is_ptr(e2))
 398                                         break;
 399
 400                                 e2->ptr.offset += u.offset;
 401                         }
 402                         goto drop;
 403                 }
 404
 405                 prev = crc;
 406                 prev_u = u;
 407 next:
 408                 entry = next;
 409                 continue;
 410 drop:
 411                 memmove_u64s_down(crc, next,
 412                                   (u64 *) extent_entry_last(e) - (u64 *) next);
 413                 e.k->u64s -= crc_u64s;
 414         }
 415
 416         EBUG_ON(bkey_val_u64s(e.k) && !bch2_extent_nr_ptrs(e.c));
 417 }
 418
 419 static bool should_drop_ptr(const struct bch_fs *c,
 420                             struct bkey_s_c_extent e,
 421                             const struct bch_extent_ptr *ptr)
 422 {
 423         return ptr->cached && ptr_stale(bch_dev_bkey_exists(c, ptr->dev), ptr);
 424 }
 425
 426 static void bch2_extent_drop_stale(struct bch_fs *c, struct bkey_s_extent e)
 427 {
 428         struct bch_extent_ptr *ptr = &e.v->start->ptr;
 429         bool dropped = false;
 430
 431         while ((ptr = extent_ptr_next(e, ptr)))
 432                 if (should_drop_ptr(c, e.c, ptr)) {
 433                         __bch2_extent_drop_ptr(e, ptr);
 434                         dropped = true;
 435                 } else
 436                         ptr++;
 437
 438         if (dropped)
 439                 bch2_extent_drop_redundant_crcs(e);
 440 }
 441
 442 static bool bch2_ptr_normalize(struct bch_fs *c, struct btree *bk,
 443                               struct bkey_s k)
 444 {
 445         return bch2_extent_normalize(c, k);
 446 }
 447
 448 static void bch2_ptr_swab(const struct bkey_format *f, struct bkey_packed *k)
 449 {
 450         switch (k->type) {
 451         case BCH_EXTENT:
 452         case BCH_EXTENT_CACHED: {
 453                 union bch_extent_entry *entry;
 454                 u64 *d = (u64 *) bkeyp_val(f, k);
 455                 unsigned i;
 456
 457                 for (i = 0; i < bkeyp_val_u64s(f, k); i++)
 458                         d[i] = swab64(d[i]);
 459
 460                 for (entry = (union bch_extent_entry *) d;
 461                      entry < (union bch_extent_entry *) (d + bkeyp_val_u64s(f, k));
 462                      entry = extent_entry_next(entry)) {
 463                         switch (extent_entry_type(entry)) {
 464                         case BCH_EXTENT_ENTRY_crc32:
 465                                 entry->crc32.csum = swab32(entry->crc32.csum);
 466                                 break;
 467                         case BCH_EXTENT_ENTRY_crc64:
 468                                 entry->crc64.csum_hi = swab16(entry->crc64.csum_hi);
 469                                 entry->crc64.csum_lo = swab64(entry->crc64.csum_lo);
 470                                 break;
 471                         case BCH_EXTENT_ENTRY_crc128:
 472                                 entry->crc128.csum.hi = (__force __le64)
 473                                         swab64((__force u64) entry->crc128.csum.hi);
 474                                 entry->crc128.csum.lo = (__force __le64)
 475                                         swab64((__force u64) entry->crc128.csum.lo);
 476                                 break;
 477                         case BCH_EXTENT_ENTRY_ptr:
 478                                 break;
 479                         }
 480                 }
 481                 break;
 482         }
 483         }
 484 }
 485
 486 static const char *extent_ptr_invalid(const struct bch_fs *c,
 487                                       struct bkey_s_c_extent e,
 488                                       const struct bch_extent_ptr *ptr,
 489                                       unsigned size_ondisk,
 490                                       bool metadata)
 491 {
 492         const struct bch_extent_ptr *ptr2;
 493         struct bch_dev *ca;
 494
 495         if (ptr->dev >= c->sb.nr_devices ||
 496             !c->devs[ptr->dev])
 497                 return "pointer to invalid device";
 498
 499         ca = bch_dev_bkey_exists(c, ptr->dev);
 500         if (!ca)
 501                 return "pointer to invalid device";
 502
 503         extent_for_each_ptr(e, ptr2)
 504                 if (ptr != ptr2 && ptr->dev == ptr2->dev)
 505                         return "multiple pointers to same device";
 506
 507         if (ptr->offset + size_ondisk > bucket_to_sector(ca, ca->mi.nbuckets))
 508                 return "offset past end of device";
 509
 510         if (ptr->offset < bucket_to_sector(ca, ca->mi.first_bucket))
 511                 return "offset before first bucket";
 512
 513         if (bucket_remainder(ca, ptr->offset) +
 514             size_ondisk > ca->mi.bucket_size)
 515                 return "spans multiple buckets";
 516
 517         return NULL;
 518 }
 519
 520 static size_t extent_print_ptrs(struct bch_fs *c, char *buf,
 521                                 size_t size, struct bkey_s_c_extent e)
 522 {
 523         char *out = buf, *end = buf + size;
 524         const union bch_extent_entry *entry;
 525         struct bch_extent_crc_unpacked crc;
 526         const struct bch_extent_ptr *ptr;
 527         struct bch_dev *ca;
 528         bool first = true;
 529
 530 #define p(...)  (out += scnprintf(out, end - out, __VA_ARGS__))
 531
 532         extent_for_each_entry(e, entry) {
 533                 if (!first)
 534                         p(" ");
 535
 536                 switch (__extent_entry_type(entry)) {
 537                 case BCH_EXTENT_ENTRY_crc32:
 538                 case BCH_EXTENT_ENTRY_crc64:
 539                 case BCH_EXTENT_ENTRY_crc128:
 540                         crc = bch2_extent_crc_unpack(e.k, entry_to_crc(entry));
 541
 542                         p("crc: c_size %u size %u offset %u nonce %u csum %u compress %u",
 543                           crc.compressed_size,
 544                           crc.uncompressed_size,
 545                           crc.offset, crc.nonce,
 546                           crc.csum_type,
 547                           crc.compression_type);
 548                         break;
 549                 case BCH_EXTENT_ENTRY_ptr:
 550                         ptr = entry_to_ptr(entry);
 551                         ca = ptr->dev < c->sb.nr_devices && c->devs[ptr->dev]
 552                                 ? bch_dev_bkey_exists(c, ptr->dev)
 553                                 : NULL;
 554
 555                         p("ptr: %u:%llu gen %u%s%s", ptr->dev,
 556                           (u64) ptr->offset, ptr->gen,
 557                           ptr->cached ? " cached" : "",
 558                           ca && ptr_stale(ca, ptr)
 559                           ? " stale" : "");
 560                         break;
 561                 default:
 562                         p("(invalid extent entry %.16llx)", *((u64 *) entry));
 563                         goto out;
 564                 }
 565
 566                 first = false;
 567         }
 568 out:
 569         if (bkey_extent_is_cached(e.k))
 570                 p(" cached");
 571 #undef p
 572         return out - buf;
 573 }
 574
 575 static inline bool dev_latency_better(struct bch_dev *dev1,
 576                                       struct bch_dev *dev2)
 577 {
 578         unsigned l1 = atomic_read(&dev1->latency[READ]);
 579         unsigned l2 = atomic_read(&dev2->latency[READ]);
 580
 581         /* Pick at random, biased in favor of the faster device: */
 582
 583         return bch2_rand_range(l1 + l2) > l1;
 584 }
 585
 586 static void extent_pick_read_device(struct bch_fs *c,
 587                                     struct bkey_s_c_extent e,
 588                                     struct bch_devs_mask *avoid,
 589                                     struct extent_pick_ptr *pick)
 590 {
 591         const struct bch_extent_ptr *ptr;
 592         struct bch_extent_crc_unpacked crc;
 593
 594         extent_for_each_ptr_crc(e, ptr, crc) {
 595                 struct bch_dev *ca = bch_dev_bkey_exists(c, ptr->dev);
 596
 597                 if (ptr->cached && ptr_stale(ca, ptr))
 598                         continue;
 599
 600                 if (ca->mi.state == BCH_MEMBER_STATE_FAILED)
 601                         continue;
 602
 603                 if (avoid) {
 604                         if (test_bit(ca->dev_idx, avoid->d))
 605                                 continue;
 606
 607                         if (pick->ca &&
 608                             test_bit(pick->ca->dev_idx, avoid->d))
 609                                 goto use;
 610                 }
 611
 612                 if (pick->ca && !dev_latency_better(ca, pick->ca))
 613                         continue;
 614 use:
 615                 if (!percpu_ref_tryget(&ca->io_ref))
 616                         continue;
 617
 618                 if (pick->ca)
 619                         percpu_ref_put(&pick->ca->io_ref);
 620
 621                 *pick = (struct extent_pick_ptr) {
 622                         .ptr    = *ptr,
 623                         .crc    = crc,
 624                         .ca     = ca,
 625                 };
 626         }
 627 }
 628
 629 /* Btree ptrs */
 630
 631 static const char *bch2_btree_ptr_invalid(const struct bch_fs *c,
 632                                          struct bkey_s_c k)
 633 {
 634         if (bkey_extent_is_cached(k.k))
 635                 return "cached";
 636
 637         if (k.k->size)
 638                 return "nonzero key size";
 639
 640         if (bkey_val_u64s(k.k) > BKEY_BTREE_PTR_VAL_U64s_MAX)
 641                 return "value too big";
 642
 643         switch (k.k->type) {
 644         case BCH_EXTENT: {
 645                 struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
 646                 const union bch_extent_entry *entry;
 647                 const struct bch_extent_ptr *ptr;
 648                 const char *reason;
 649
 650                 extent_for_each_entry(e, entry) {
 651                         if (__extent_entry_type(entry) >= BCH_EXTENT_ENTRY_MAX)
 652                                 return "invalid extent entry type";
 653
 654                         if (extent_entry_is_crc(entry))
 655                                 return "has crc field";
 656                 }
 657
 658                 extent_for_each_ptr(e, ptr) {
 659                         reason = extent_ptr_invalid(c, e, ptr,
 660                                                     c->opts.btree_node_size,
 661                                                     true);
 662                         if (reason)
 663                                 return reason;
 664                 }
 665
 666                 return NULL;
 667         }
 668
 669         default:
 670                 return "invalid value type";
 671         }
 672 }
 673
 674 static void btree_ptr_debugcheck(struct bch_fs *c, struct btree *b,
 675                                  struct bkey_s_c k)
 676 {
 677         struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
 678         const struct bch_extent_ptr *ptr;
 679         unsigned seq;
 680         const char *err;
 681         char buf[160];
 682         struct bucket_mark mark;
 683         struct bch_dev *ca;
 684         unsigned replicas = 0;
 685         bool bad;
 686
 687         extent_for_each_ptr(e, ptr) {
 688                 ca = bch_dev_bkey_exists(c, ptr->dev);
 689                 replicas++;
 690
 691                 if (!test_bit(BCH_FS_ALLOC_READ_DONE, &c->flags))
 692                         continue;
 693
 694                 err = "stale";
 695                 if (ptr_stale(ca, ptr))
 696                         goto err;
 697
 698                 do {
 699                         seq = read_seqcount_begin(&c->gc_pos_lock);
 700                         mark = ptr_bucket_mark(ca, ptr);
 701
 702                         bad = gc_pos_cmp(c->gc_pos, gc_pos_btree_node(b)) > 0 &&
 703                                 (mark.data_type != BCH_DATA_BTREE ||
 704                                  mark.dirty_sectors < c->opts.btree_node_size);
 705                 } while (read_seqcount_retry(&c->gc_pos_lock, seq));
 706
 707                 err = "inconsistent";
 708                 if (bad)
 709                         goto err;
 710         }
 711
 712         if (!bch2_bkey_replicas_marked(c, BCH_DATA_BTREE, e.s_c)) {
 713                 bch2_bkey_val_to_text(c, btree_node_type(b),
 714                                      buf, sizeof(buf), k);
 715                 bch2_fs_bug(c,
 716                         "btree key bad (replicas not marked in superblock):\n%s",
 717                         buf);
 718                 return;
 719         }
 720
 721         return;
 722 err:
 723         bch2_bkey_val_to_text(c, btree_node_type(b), buf, sizeof(buf), k);
 724         bch2_fs_bug(c, "%s btree pointer %s: bucket %zi "
 725                       "gen %i mark %08x",
 726                       err, buf, PTR_BUCKET_NR(ca, ptr),
 727                       mark.gen, (unsigned) mark.counter);
 728 }
 729
 730 static void bch2_btree_ptr_to_text(struct bch_fs *c, char *buf,
 731                                   size_t size, struct bkey_s_c k)
 732 {
 733         char *out = buf, *end = buf + size;
 734         const char *invalid;
 735
 736 #define p(...)  (out += scnprintf(out, end - out, __VA_ARGS__))
 737
 738         if (bkey_extent_is_data(k.k))
 739                 out += extent_print_ptrs(c, buf, size, bkey_s_c_to_extent(k));
 740
 741         invalid = bch2_btree_ptr_invalid(c, k);
 742         if (invalid)
 743                 p(" invalid: %s", invalid);
 744 #undef p
 745 }
 746
 747 struct extent_pick_ptr
 748 bch2_btree_pick_ptr(struct bch_fs *c, const struct btree *b,
 749                     struct bch_devs_mask *avoid)
 750 {
 751         struct extent_pick_ptr pick = { .ca = NULL };
 752
 753         extent_pick_read_device(c, bkey_i_to_s_c_extent(&b->key),
 754                                 avoid, &pick);
 755
 756         return pick;
 757 }
 758
 759 const struct bkey_ops bch2_bkey_btree_ops = {
 760         .key_invalid    = bch2_btree_ptr_invalid,
 761         .key_debugcheck = btree_ptr_debugcheck,
 762         .val_to_text    = bch2_btree_ptr_to_text,
 763         .swab           = bch2_ptr_swab,
 764 };
 765
 766 /* Extents */
 767
 768 static bool __bch2_cut_front(struct bpos where, struct bkey_s k)
 769 {
 770         u64 len = 0;
 771
 772         if (bkey_cmp(where, bkey_start_pos(k.k)) <= 0)
 773                 return false;
 774
 775         EBUG_ON(bkey_cmp(where, k.k->p) > 0);
 776
 777         len = k.k->p.offset - where.offset;
 778
 779         BUG_ON(len > k.k->size);
 780
 781         /*
 782          * Don't readjust offset if the key size is now 0, because that could
 783          * cause offset to point to the next bucket:
 784          */
 785         if (!len)
 786                 __set_bkey_deleted(k.k);
 787         else if (bkey_extent_is_data(k.k)) {
 788                 struct bkey_s_extent e = bkey_s_to_extent(k);
 789                 union bch_extent_entry *entry;
 790                 bool seen_crc = false;
 791
 792                 extent_for_each_entry(e, entry) {
 793                         switch (extent_entry_type(entry)) {
 794                         case BCH_EXTENT_ENTRY_ptr:
 795                                 if (!seen_crc)
 796                                         entry->ptr.offset += e.k->size - len;
 797                                 break;
 798                         case BCH_EXTENT_ENTRY_crc32:
 799                                 entry->crc32.offset += e.k->size - len;
 800                                 break;
 801                         case BCH_EXTENT_ENTRY_crc64:
 802                                 entry->crc64.offset += e.k->size - len;
 803                                 break;
 804                         case BCH_EXTENT_ENTRY_crc128:
 805                                 entry->crc128.offset += e.k->size - len;
 806                                 break;
 807                         }
 808
 809                         if (extent_entry_is_crc(entry))
 810                                 seen_crc = true;
 811                 }
 812         }
 813
 814         k.k->size = len;
 815
 816         return true;
 817 }
 818
 819 bool bch2_cut_front(struct bpos where, struct bkey_i *k)
 820 {
 821         return __bch2_cut_front(where, bkey_i_to_s(k));
 822 }
 823
 824 bool bch2_cut_back(struct bpos where, struct bkey *k)
 825 {
 826         u64 len = 0;
 827
 828         if (bkey_cmp(where, k->p) >= 0)
 829                 return false;
 830
 831         EBUG_ON(bkey_cmp(where, bkey_start_pos(k)) < 0);
 832
 833         len = where.offset - bkey_start_offset(k);
 834
 835         BUG_ON(len > k->size);
 836
 837         k->p = where;
 838         k->size = len;
 839
 840         if (!len)
 841                 __set_bkey_deleted(k);
 842
 843         return true;
 844 }
 845
 846 /**
 847  * bch_key_resize - adjust size of @k
 848  *
 849  * bkey_start_offset(k) will be preserved, modifies where the extent ends
 850  */
 851 void bch2_key_resize(struct bkey *k,
 852                     unsigned new_size)
 853 {
 854         k->p.offset -= k->size;
 855         k->p.offset += new_size;
 856         k->size = new_size;
 857 }
 858
 859 /*
 860  * In extent_sort_fix_overlapping(), insert_fixup_extent(),
 861  * extent_merge_inline() - we're modifying keys in place that are packed. To do
 862  * that we have to unpack the key, modify the unpacked key - then this
 863  * copies/repacks the unpacked to the original as necessary.
 864  */
 865 static bool __extent_save(struct btree *b, struct btree_node_iter *iter,
 866                           struct bkey_packed *dst, struct bkey *src)
 867 {
 868         struct bkey_format *f = &b->format;
 869         struct bkey_i *dst_unpacked;
 870         bool ret;
 871
 872         if ((dst_unpacked = packed_to_bkey(dst))) {
 873                 dst_unpacked->k = *src;
 874                 ret = true;
 875         } else {
 876                 ret = bch2_bkey_pack_key(dst, src, f);
 877         }
 878
 879         if (ret && iter)
 880                 bch2_verify_key_order(b, iter, dst);
 881
 882         return ret;
 883 }
 884
 885 static void extent_save(struct btree *b, struct btree_node_iter *iter,
 886                         struct bkey_packed *dst, struct bkey *src)
 887 {
 888         BUG_ON(!__extent_save(b, iter, dst, src));
 889 }
 890
 891 /*
 892  * If keys compare equal, compare by pointer order:
 893  *
 894  * Necessary for sort_fix_overlapping() - if there are multiple keys that
 895  * compare equal in different sets, we have to process them newest to oldest.
 896  */
 897 #define extent_sort_cmp(h, l, r)                                        \
 898 ({                                                                      \
 899         struct bkey _ul = bkey_unpack_key(b,                            \
 900                                 __btree_node_offset_to_key(b, (l).k));  \
 901         struct bkey _ur = bkey_unpack_key(b,                            \
 902                                 __btree_node_offset_to_key(b, (r).k));  \
 903                                                                         \
 904         bkey_cmp(bkey_start_pos(&_ul),                                  \
 905                  bkey_start_pos(&_ur)) ?: (r).k - (l).k;                \
 906 })
 907
 908 static inline void extent_sort_sift(struct btree_node_iter_large *iter,
 909                                     struct btree *b, size_t i)
 910 {
 911         heap_sift_down(iter, i, extent_sort_cmp);
 912 }
 913
 914 static inline void extent_sort_next(struct btree_node_iter_large *iter,
 915                                     struct btree *b,
 916                                     struct btree_node_iter_set *i)
 917 {
 918         sort_key_next(iter, b, i);
 919         heap_sift_down(iter, i - iter->data, extent_sort_cmp);
 920 }
 921
 922 static void extent_sort_append(struct bch_fs *c,
 923                                struct btree *b,
 924                                struct btree_nr_keys *nr,
 925                                struct bkey_packed *start,
 926                                struct bkey_packed **prev,
 927                                struct bkey_packed *k)
 928 {
 929         struct bkey_format *f = &b->format;
 930         BKEY_PADDED(k) tmp;
 931
 932         if (bkey_whiteout(k))
 933                 return;
 934
 935         bch2_bkey_unpack(b, &tmp.k, k);
 936
 937         if (*prev &&
 938             bch2_extent_merge(c, b, (void *) *prev, &tmp.k))
 939                 return;
 940
 941         if (*prev) {
 942                 bch2_bkey_pack(*prev, (void *) *prev, f);
 943
 944                 btree_keys_account_key_add(nr, 0, *prev);
 945                 *prev = bkey_next(*prev);
 946         } else {
 947                 *prev = start;
 948         }
 949
 950         bkey_copy(*prev, &tmp.k);
 951 }
 952
 953 struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
 954                                         struct bset *dst,
 955                                         struct btree *b,
 956                                         struct btree_node_iter_large *iter)
 957 {
 958         struct bkey_format *f = &b->format;
 959         struct btree_node_iter_set *_l = iter->data, *_r;
 960         struct bkey_packed *prev = NULL, *out, *lk, *rk;
 961         struct bkey l_unpacked, r_unpacked;
 962         struct bkey_s l, r;
 963         struct btree_nr_keys nr;
 964
 965         memset(&nr, 0, sizeof(nr));
 966
 967         heap_resort(iter, extent_sort_cmp);
 968
 969         while (!bch2_btree_node_iter_large_end(iter)) {
 970                 lk = __btree_node_offset_to_key(b, _l->k);
 971
 972                 if (iter->used == 1) {
 973                         extent_sort_append(c, b, &nr, dst->start, &prev, lk);
 974                         extent_sort_next(iter, b, _l);
 975                         continue;
 976                 }
 977
 978                 _r = iter->data + 1;
 979                 if (iter->used > 2 &&
 980                     extent_sort_cmp(iter, _r[0], _r[1]) >= 0)
 981                         _r++;
 982
 983                 rk = __btree_node_offset_to_key(b, _r->k);
 984
 985                 l = __bkey_disassemble(b, lk, &l_unpacked);
 986                 r = __bkey_disassemble(b, rk, &r_unpacked);
 987
 988                 /* If current key and next key don't overlap, just append */
 989                 if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) {
 990                         extent_sort_append(c, b, &nr, dst->start, &prev, lk);
 991                         extent_sort_next(iter, b, _l);
 992                         continue;
 993                 }
 994
 995                 /* Skip 0 size keys */
 996                 if (!r.k->size) {
 997                         extent_sort_next(iter, b, _r);
 998                         continue;
 999                 }
1000
1001                 /*
1002                  * overlap: keep the newer key and trim the older key so they
1003                  * don't overlap. comparing pointers tells us which one is
1004                  * newer, since the bsets are appended one after the other.
1005                  */
1006
1007                 /* can't happen because of comparison func */
1008                 BUG_ON(_l->k < _r->k &&
1009                        !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k)));
1010
1011                 if (_l->k > _r->k) {
1012                         /* l wins, trim r */
1013                         if (bkey_cmp(l.k->p, r.k->p) >= 0) {
1014                                 sort_key_next(iter, b, _r);
1015                         } else {
1016                                 __bch2_cut_front(l.k->p, r);
1017                                 extent_save(b, NULL, rk, r.k);
1018                         }
1019
1020                         extent_sort_sift(iter, b, _r - iter->data);
1021                 } else if (bkey_cmp(l.k->p, r.k->p) > 0) {
1022                         BKEY_PADDED(k) tmp;
1023
1024                         /*
1025                          * r wins, but it overlaps in the middle of l - split l:
1026                          */
1027                         bkey_reassemble(&tmp.k, l.s_c);
1028                         bch2_cut_back(bkey_start_pos(r.k), &tmp.k.k);
1029
1030                         __bch2_cut_front(r.k->p, l);
1031                         extent_save(b, NULL, lk, l.k);
1032
1033                         extent_sort_sift(iter, b, 0);
1034
1035                         extent_sort_append(c, b, &nr, dst->start, &prev,
1036                                            bkey_to_packed(&tmp.k));
1037                 } else {
1038                         bch2_cut_back(bkey_start_pos(r.k), l.k);
1039                         extent_save(b, NULL, lk, l.k);
1040                 }
1041         }
1042
1043         if (prev) {
1044                 bch2_bkey_pack(prev, (void *) prev, f);
1045                 btree_keys_account_key_add(&nr, 0, prev);
1046                 out = bkey_next(prev);
1047         } else {
1048                 out = dst->start;
1049         }
1050
1051         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
1052         return nr;
1053 }
1054
1055 struct extent_insert_state {
1056         struct btree_insert             *trans;
1057         struct btree_insert_entry       *insert;
1058         struct bpos                     committed;
1059         struct bch_fs_usage             stats;
1060
1061         /* for deleting: */
1062         struct bkey_i                   whiteout;
1063         bool                            do_journal;
1064         bool                            deleting;
1065 };
1066
1067 static void bch2_add_sectors(struct extent_insert_state *s,
1068                              struct bkey_s_c k, u64 offset, s64 sectors)
1069 {
1070         struct bch_fs *c = s->trans->c;
1071         struct btree *b = s->insert->iter->l[0].b;
1072
1073         EBUG_ON(bkey_cmp(bkey_start_pos(k.k), b->data->min_key) < 0);
1074
1075         if (!sectors)
1076                 return;
1077
1078         bch2_mark_key(c, k, sectors, false, gc_pos_btree_node(b),
1079                       &s->stats, s->trans->journal_res.seq, 0);
1080 }
1081
1082 static void bch2_subtract_sectors(struct extent_insert_state *s,
1083                                  struct bkey_s_c k, u64 offset, s64 sectors)
1084 {
1085         bch2_add_sectors(s, k, offset, -sectors);
1086 }
1087
1088 /* These wrappers subtract exactly the sectors that we're removing from @k */
1089 static void bch2_cut_subtract_back(struct extent_insert_state *s,
1090                                   struct bpos where, struct bkey_s k)
1091 {
1092         bch2_subtract_sectors(s, k.s_c, where.offset,
1093                              k.k->p.offset - where.offset);
1094         bch2_cut_back(where, k.k);
1095 }
1096
1097 static void bch2_cut_subtract_front(struct extent_insert_state *s,
1098                                    struct bpos where, struct bkey_s k)
1099 {
1100         bch2_subtract_sectors(s, k.s_c, bkey_start_offset(k.k),
1101                              where.offset - bkey_start_offset(k.k));
1102         __bch2_cut_front(where, k);
1103 }
1104
1105 static void bch2_drop_subtract(struct extent_insert_state *s, struct bkey_s k)
1106 {
1107         if (k.k->size)
1108                 bch2_subtract_sectors(s, k.s_c,
1109                                      bkey_start_offset(k.k), k.k->size);
1110         k.k->size = 0;
1111         __set_bkey_deleted(k.k);
1112 }
1113
1114 static bool bch2_extent_merge_inline(struct bch_fs *,
1115                                      struct btree_iter *,
1116                                      struct bkey_packed *,
1117                                      struct bkey_packed *,
1118                                      bool);
1119
1120 #define MAX_LOCK_HOLD_TIME      (5 * NSEC_PER_MSEC)
1121
1122 static enum btree_insert_ret
1123 extent_insert_should_stop(struct extent_insert_state *s)
1124 {
1125         struct btree *b = s->insert->iter->l[0].b;
1126
1127         /*
1128          * Check if we have sufficient space in both the btree node and the
1129          * journal reservation:
1130          *
1131          * Each insert checks for room in the journal entry, but we check for
1132          * room in the btree node up-front. In the worst case, bkey_cmpxchg()
1133          * will insert two keys, and one iteration of this room will insert one
1134          * key, so we need room for three keys.
1135          */
1136         if (!bch2_btree_node_insert_fits(s->trans->c, b, s->insert->k->k.u64s))
1137                 return BTREE_INSERT_BTREE_NODE_FULL;
1138         else if (!journal_res_insert_fits(s->trans, s->insert))
1139                 return BTREE_INSERT_JOURNAL_RES_FULL; /* XXX worth tracing */
1140         else
1141                 return BTREE_INSERT_OK;
1142 }
1143
1144 static void extent_bset_insert(struct bch_fs *c, struct btree_iter *iter,
1145                                struct bkey_i *insert)
1146 {
1147         struct btree_iter_level *l = &iter->l[0];
1148         struct bset_tree *t = bset_tree_last(l->b);
1149         struct bkey_packed *where =
1150                 bch2_btree_node_iter_bset_pos(&l->iter, l->b, t);
1151         struct bkey_packed *prev = bch2_bkey_prev(l->b, t, where);
1152         struct bkey_packed *next_live_key = where;
1153         unsigned clobber_u64s;
1154
1155         if (prev)
1156                 where = bkey_next(prev);
1157
1158         while (next_live_key != btree_bkey_last(l->b, t) &&
1159                bkey_deleted(next_live_key))
1160                 next_live_key = bkey_next(next_live_key);
1161
1162         /*
1163          * Everything between where and next_live_key is now deleted keys, and
1164          * is overwritten:
1165          */
1166         clobber_u64s = (u64 *) next_live_key - (u64 *) where;
1167
1168         if (prev &&
1169             bch2_extent_merge_inline(c, iter, prev, bkey_to_packed(insert), true))
1170                 goto drop_deleted_keys;
1171
1172         if (next_live_key != btree_bkey_last(l->b, t) &&
1173             bch2_extent_merge_inline(c, iter, bkey_to_packed(insert),
1174                                     next_live_key, false))
1175                 goto drop_deleted_keys;
1176
1177         bch2_bset_insert(l->b, &l->iter, where, insert, clobber_u64s);
1178         bch2_btree_node_iter_fix(iter, l->b, &l->iter, t, where,
1179                                 clobber_u64s, where->u64s);
1180         return;
1181 drop_deleted_keys:
1182         bch2_bset_delete(l->b, where, clobber_u64s);
1183         bch2_btree_node_iter_fix(iter, l->b, &l->iter, t,
1184                                  where, clobber_u64s, 0);
1185 }
1186
1187 static void extent_insert_committed(struct extent_insert_state *s)
1188 {
1189         struct bch_fs *c = s->trans->c;
1190         struct btree_iter *iter = s->insert->iter;
1191         struct bkey_i *insert = !s->deleting
1192                 ? s->insert->k
1193                 : &s->whiteout;
1194         BKEY_PADDED(k) split;
1195
1196         EBUG_ON(bkey_cmp(insert->k.p, s->committed) < 0);
1197         EBUG_ON(bkey_cmp(s->committed, bkey_start_pos(&insert->k)) < 0);
1198
1199         if (!bkey_cmp(s->committed, bkey_start_pos(&insert->k)))
1200                 return;
1201
1202         if (s->deleting && !s->do_journal) {
1203                 bch2_cut_front(s->committed, insert);
1204                 goto done;
1205         }
1206
1207         EBUG_ON(bkey_deleted(&insert->k) || !insert->k.size);
1208
1209         bkey_copy(&split.k, insert);
1210
1211         if (!(s->trans->flags & BTREE_INSERT_JOURNAL_REPLAY) &&
1212             bkey_cmp(s->committed, insert->k.p) &&
1213             bch2_extent_is_compressed(bkey_i_to_s_c(insert))) {
1214                 /* XXX: possibly need to increase our reservation? */
1215                 bch2_cut_subtract_back(s, s->committed,
1216                                       bkey_i_to_s(&split.k));
1217                 bch2_cut_front(s->committed, insert);
1218                 bch2_add_sectors(s, bkey_i_to_s_c(insert),
1219                                 bkey_start_offset(&insert->k),
1220                                 insert->k.size);
1221         } else {
1222                 bch2_cut_back(s->committed, &split.k.k);
1223                 bch2_cut_front(s->committed, insert);
1224         }
1225
1226         if (debug_check_bkeys(c))
1227                 bch2_bkey_debugcheck(c, iter->l[0].b, bkey_i_to_s_c(&split.k));
1228
1229         bch2_btree_journal_key(s->trans, iter, &split.k);
1230
1231         if (!s->deleting)
1232                 extent_bset_insert(c, iter, &split.k);
1233 done:
1234         bch2_btree_iter_set_pos_same_leaf(iter, s->committed);
1235
1236         insert->k.needs_whiteout        = false;
1237         s->do_journal                   = false;
1238         s->trans->did_work              = true;
1239 }
1240
1241 static enum btree_insert_ret
1242 __extent_insert_advance_pos(struct extent_insert_state *s,
1243                             struct bpos next_pos,
1244                             struct bkey_s_c k)
1245 {
1246         struct extent_insert_hook *hook = s->trans->hook;
1247         enum btree_insert_ret ret;
1248
1249         if (hook)
1250                 ret = hook->fn(hook, s->committed, next_pos, k, s->insert->k);
1251         else
1252                 ret = BTREE_INSERT_OK;
1253
1254         EBUG_ON(bkey_deleted(&s->insert->k->k) || !s->insert->k->k.size);
1255
1256         if (ret == BTREE_INSERT_OK)
1257                 s->committed = next_pos;
1258
1259         return ret;
1260 }
1261
1262 /*
1263  * Update iter->pos, marking how much of @insert we've processed, and call hook
1264  * fn:
1265  */
1266 static enum btree_insert_ret
1267 extent_insert_advance_pos(struct extent_insert_state *s, struct bkey_s_c k)
1268 {
1269         struct btree *b = s->insert->iter->l[0].b;
1270         struct bpos next_pos = bpos_min(s->insert->k->k.p,
1271                                         k.k ? k.k->p : b->key.k.p);
1272         enum btree_insert_ret ret;
1273
1274         if (race_fault())
1275                 return BTREE_INSERT_NEED_TRAVERSE;
1276
1277         /* hole? */
1278         if (k.k && bkey_cmp(s->committed, bkey_start_pos(k.k)) < 0) {
1279                 ret = __extent_insert_advance_pos(s, bkey_start_pos(k.k),
1280                                                     bkey_s_c_null);
1281                 if (ret != BTREE_INSERT_OK)
1282                         return ret;
1283         }
1284
1285         /* avoid redundant calls to hook fn: */
1286         if (!bkey_cmp(s->committed, next_pos))
1287                 return BTREE_INSERT_OK;
1288
1289         return __extent_insert_advance_pos(s, next_pos, k);
1290 }
1291
1292 static enum btree_insert_ret
1293 extent_insert_check_split_compressed(struct extent_insert_state *s,
1294                                      struct bkey_s_c k,
1295                                      enum bch_extent_overlap overlap)
1296 {
1297         struct bch_fs *c = s->trans->c;
1298         unsigned sectors;
1299
1300         if (overlap == BCH_EXTENT_OVERLAP_MIDDLE &&
1301             (sectors = bch2_extent_is_compressed(k))) {
1302                 int flags = BCH_DISK_RESERVATION_BTREE_LOCKS_HELD;
1303
1304                 if (s->trans->flags & BTREE_INSERT_NOFAIL)
1305                         flags |= BCH_DISK_RESERVATION_NOFAIL;
1306
1307                 switch (bch2_disk_reservation_add(c,
1308                                 s->trans->disk_res,
1309                                 sectors * bch2_extent_nr_dirty_ptrs(k),
1310                                 flags)) {
1311                 case 0:
1312                         break;
1313                 case -ENOSPC:
1314                         return BTREE_INSERT_ENOSPC;
1315                 case -EINTR:
1316                         return BTREE_INSERT_NEED_GC_LOCK;
1317                 default:
1318                         BUG();
1319                 }
1320         }
1321
1322         return BTREE_INSERT_OK;
1323 }
1324
1325 static enum btree_insert_ret
1326 extent_squash(struct extent_insert_state *s, struct bkey_i *insert,
1327               struct bset_tree *t, struct bkey_packed *_k, struct bkey_s k,
1328               enum bch_extent_overlap overlap)
1329 {
1330         struct bch_fs *c = s->trans->c;
1331         struct btree_iter *iter = s->insert->iter;
1332         struct btree_iter_level *l = &iter->l[0];
1333         struct btree *b = l->b;
1334         struct btree_node_iter *node_iter = &l->iter;
1335         enum btree_insert_ret ret;
1336
1337         switch (overlap) {
1338         case BCH_EXTENT_OVERLAP_FRONT:
1339                 /* insert overlaps with start of k: */
1340                 bch2_cut_subtract_front(s, insert->k.p, k);
1341                 BUG_ON(bkey_deleted(k.k));
1342                 extent_save(b, node_iter, _k, k.k);
1343                 break;
1344
1345         case BCH_EXTENT_OVERLAP_BACK:
1346                 /* insert overlaps with end of k: */
1347                 bch2_cut_subtract_back(s, bkey_start_pos(&insert->k), k);
1348                 BUG_ON(bkey_deleted(k.k));
1349                 extent_save(b, node_iter, _k, k.k);
1350
1351                 /*
1352                  * As the auxiliary tree is indexed by the end of the
1353                  * key and we've just changed the end, update the
1354                  * auxiliary tree.
1355                  */
1356                 bch2_bset_fix_invalidated_key(b, t, _k);
1357                 bch2_btree_node_iter_fix(iter, b, node_iter, t,
1358                                         _k, _k->u64s, _k->u64s);
1359                 break;
1360
1361         case BCH_EXTENT_OVERLAP_ALL: {
1362                 struct bpos orig_pos = k.k->p;
1363
1364                 /* The insert key completely covers k, invalidate k */
1365                 if (!bkey_whiteout(k.k))
1366                         btree_keys_account_key_drop(&b->nr,
1367                                                 t - b->set, _k);
1368
1369                 bch2_drop_subtract(s, k);
1370                 k.k->p = bkey_start_pos(&insert->k);
1371                 if (!__extent_save(b, node_iter, _k, k.k)) {
1372                         /*
1373                          * Couldn't repack: we aren't necessarily able
1374                          * to repack if the new key is outside the range
1375                          * of the old extent, so we have to split
1376                          * @insert:
1377                          */
1378                         k.k->p = orig_pos;
1379                         extent_save(b, node_iter, _k, k.k);
1380
1381                         ret = extent_insert_advance_pos(s, k.s_c);
1382                         if (ret != BTREE_INSERT_OK)
1383                                 return ret;
1384
1385                         extent_insert_committed(s);
1386                         /*
1387                          * We split and inserted upto at k.k->p - that
1388                          * has to coincide with iter->pos, so that we
1389                          * don't have anything more we have to insert
1390                          * until we recheck our journal reservation:
1391                          */
1392                         EBUG_ON(bkey_cmp(s->committed, k.k->p));
1393                 } else {
1394                         bch2_bset_fix_invalidated_key(b, t, _k);
1395                         bch2_btree_node_iter_fix(iter, b, node_iter, t,
1396                                                 _k, _k->u64s, _k->u64s);
1397                 }
1398
1399                 break;
1400         }
1401         case BCH_EXTENT_OVERLAP_MIDDLE: {
1402                 BKEY_PADDED(k) split;
1403                 /*
1404                  * The insert key falls 'in the middle' of k
1405                  * The insert key splits k in 3:
1406                  * - start only in k, preserve
1407                  * - middle common section, invalidate in k
1408                  * - end only in k, preserve
1409                  *
1410                  * We update the old key to preserve the start,
1411                  * insert will be the new common section,
1412                  * we manually insert the end that we are preserving.
1413                  *
1414                  * modify k _before_ doing the insert (which will move
1415                  * what k points to)
1416                  */
1417                 bkey_reassemble(&split.k, k.s_c);
1418                 split.k.k.needs_whiteout |= bset_written(b, bset(b, t));
1419
1420                 bch2_cut_back(bkey_start_pos(&insert->k), &split.k.k);
1421                 BUG_ON(bkey_deleted(&split.k.k));
1422
1423                 bch2_cut_subtract_front(s, insert->k.p, k);
1424                 BUG_ON(bkey_deleted(k.k));
1425                 extent_save(b, node_iter, _k, k.k);
1426
1427                 bch2_add_sectors(s, bkey_i_to_s_c(&split.k),
1428                                 bkey_start_offset(&split.k.k),
1429                                 split.k.k.size);
1430                 extent_bset_insert(c, iter, &split.k);
1431                 break;
1432         }
1433         }
1434
1435         return BTREE_INSERT_OK;
1436 }
1437
1438 static enum btree_insert_ret
1439 bch2_delete_fixup_extent(struct extent_insert_state *s)
1440 {
1441         struct bch_fs *c = s->trans->c;
1442         struct btree_iter *iter = s->insert->iter;
1443         struct btree_iter_level *l = &iter->l[0];
1444         struct btree *b = l->b;
1445         struct btree_node_iter *node_iter = &l->iter;
1446         struct bkey_packed *_k;
1447         struct bkey unpacked;
1448         struct bkey_i *insert = s->insert->k;
1449         enum btree_insert_ret ret = BTREE_INSERT_OK;
1450
1451         EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k)));
1452
1453         s->whiteout     = *insert;
1454         s->do_journal   = false;
1455
1456         while (bkey_cmp(s->committed, insert->k.p) < 0 &&
1457                (ret = extent_insert_should_stop(s)) == BTREE_INSERT_OK &&
1458                (_k = bch2_btree_node_iter_peek_all(node_iter, b))) {
1459                 struct bset_tree *t = bch2_bkey_to_bset(b, _k);
1460                 struct bkey_s k = __bkey_disassemble(b, _k, &unpacked);
1461                 enum bch_extent_overlap overlap;
1462
1463                 EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k)));
1464                 EBUG_ON(bkey_cmp(iter->pos, k.k->p) >= 0);
1465
1466                 if (bkey_cmp(bkey_start_pos(k.k), insert->k.p) >= 0)
1467                         break;
1468
1469                 if (bkey_whiteout(k.k)) {
1470                         s->committed = bpos_min(insert->k.p, k.k->p);
1471                         goto next;
1472                 }
1473
1474                 overlap = bch2_extent_overlap(&insert->k, k.k);
1475
1476                 ret = extent_insert_check_split_compressed(s, k.s_c, overlap);
1477                 if (ret != BTREE_INSERT_OK)
1478                         goto stop;
1479
1480                 ret = extent_insert_advance_pos(s, k.s_c);
1481                 if (ret)
1482                         goto stop;
1483
1484                 s->do_journal = true;
1485
1486                 if (overlap == BCH_EXTENT_OVERLAP_ALL) {
1487                         btree_keys_account_key_drop(&b->nr,
1488                                                 t - b->set, _k);
1489                         bch2_subtract_sectors(s, k.s_c,
1490                                              bkey_start_offset(k.k), k.k->size);
1491                         _k->type = KEY_TYPE_DISCARD;
1492                         reserve_whiteout(b, t, _k);
1493                 } else if (k.k->needs_whiteout ||
1494                            bset_written(b, bset(b, t))) {
1495                         struct bkey_i discard = *insert;
1496
1497                         switch (overlap) {
1498                         case BCH_EXTENT_OVERLAP_FRONT:
1499                                 bch2_cut_front(bkey_start_pos(k.k), &discard);
1500                                 break;
1501                         case BCH_EXTENT_OVERLAP_BACK:
1502                                 bch2_cut_back(k.k->p, &discard.k);
1503                                 break;
1504                         default:
1505                                 break;
1506                         }
1507
1508                         discard.k.needs_whiteout = true;
1509
1510                         ret = extent_squash(s, insert, t, _k, k, overlap);
1511                         BUG_ON(ret != BTREE_INSERT_OK);
1512
1513                         extent_bset_insert(c, iter, &discard);
1514                 } else {
1515                         ret = extent_squash(s, insert, t, _k, k, overlap);
1516                         BUG_ON(ret != BTREE_INSERT_OK);
1517                 }
1518 next:
1519                 bch2_cut_front(s->committed, insert);
1520                 bch2_btree_iter_set_pos_same_leaf(iter, s->committed);
1521         }
1522
1523         if (ret == BTREE_INSERT_OK &&
1524             bkey_cmp(s->committed, insert->k.p) < 0)
1525                 ret = extent_insert_advance_pos(s, bkey_s_c_null);
1526 stop:
1527         extent_insert_committed(s);
1528
1529         bch2_fs_usage_apply(c, &s->stats, s->trans->disk_res,
1530                            gc_pos_btree_node(b));
1531
1532         EBUG_ON(bkey_cmp(iter->pos, s->committed));
1533         EBUG_ON((bkey_cmp(iter->pos, b->key.k.p) == 0) !=
1534                 !!(iter->flags & BTREE_ITER_AT_END_OF_LEAF));
1535
1536         bch2_cut_front(iter->pos, insert);
1537
1538         if (insert->k.size && (iter->flags & BTREE_ITER_AT_END_OF_LEAF))
1539                 ret = BTREE_INSERT_NEED_TRAVERSE;
1540
1541         EBUG_ON(insert->k.size && ret == BTREE_INSERT_OK);
1542
1543         return ret;
1544 }
1545
1546 /**
1547  * bch_extent_insert_fixup - insert a new extent and deal with overlaps
1548  *
1549  * this may result in not actually doing the insert, or inserting some subset
1550  * of the insert key. For cmpxchg operations this is where that logic lives.
1551  *
1552  * All subsets of @insert that need to be inserted are inserted using
1553  * bch2_btree_insert_and_journal(). If @b or @res fills up, this function
1554  * returns false, setting @iter->pos for the prefix of @insert that actually got
1555  * inserted.
1556  *
1557  * BSET INVARIANTS: this function is responsible for maintaining all the
1558  * invariants for bsets of extents in memory. things get really hairy with 0
1559  * size extents
1560  *
1561  * within one bset:
1562  *
1563  * bkey_start_pos(bkey_next(k)) >= k
1564  * or bkey_start_offset(bkey_next(k)) >= k->offset
1565  *
1566  * i.e. strict ordering, no overlapping extents.
1567  *
1568  * multiple bsets (i.e. full btree node):
1569  *
1570  * ∀ k, j
1571  *   k.size != 0 ∧ j.size != 0 →
1572  *     ¬ (k > bkey_start_pos(j) ∧ k < j)
1573  *
1574  * i.e. no two overlapping keys _of nonzero size_
1575  *
1576  * We can't realistically maintain this invariant for zero size keys because of
1577  * the key merging done in bch2_btree_insert_key() - for two mergeable keys k, j
1578  * there may be another 0 size key between them in another bset, and it will
1579  * thus overlap with the merged key.
1580  *
1581  * In addition, the end of iter->pos indicates how much has been processed.
1582  * If the end of iter->pos is not the same as the end of insert, then
1583  * key insertion needs to continue/be retried.
1584  */
1585 enum btree_insert_ret
1586 bch2_insert_fixup_extent(struct btree_insert *trans,
1587                          struct btree_insert_entry *insert)
1588 {
1589         struct bch_fs *c = trans->c;
1590         struct btree_iter *iter = insert->iter;
1591         struct btree_iter_level *l = &iter->l[0];
1592         struct btree *b = l->b;
1593         struct btree_node_iter *node_iter = &l->iter;
1594         struct bkey_packed *_k;
1595         struct bkey unpacked;
1596         enum btree_insert_ret ret = BTREE_INSERT_OK;
1597
1598         struct extent_insert_state s = {
1599                 .trans          = trans,
1600                 .insert         = insert,
1601                 .committed      = insert->iter->pos,
1602                 .deleting       = bkey_whiteout(&insert->k->k),
1603         };
1604
1605         EBUG_ON(iter->level);
1606         EBUG_ON(bkey_deleted(&insert->k->k) || !insert->k->k.size);
1607
1608         if (s.deleting)
1609                 return bch2_delete_fixup_extent(&s);
1610
1611         /*
1612          * As we process overlapping extents, we advance @iter->pos both to
1613          * signal to our caller (btree_insert_key()) how much of @insert->k has
1614          * been inserted, and also to keep @iter->pos consistent with
1615          * @insert->k and the node iterator that we're advancing:
1616          */
1617         EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
1618
1619         if (!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))
1620                 bch2_add_sectors(&s, bkey_i_to_s_c(insert->k),
1621                                 bkey_start_offset(&insert->k->k),
1622                                 insert->k->k.size);
1623
1624         while (bkey_cmp(s.committed, insert->k->k.p) < 0 &&
1625                (ret = extent_insert_should_stop(&s)) == BTREE_INSERT_OK &&
1626                (_k = bch2_btree_node_iter_peek_all(node_iter, b))) {
1627                 struct bset_tree *t = bch2_bkey_to_bset(b, _k);
1628                 struct bkey_s k = __bkey_disassemble(b, _k, &unpacked);
1629                 enum bch_extent_overlap overlap;
1630
1631                 EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
1632                 EBUG_ON(bkey_cmp(iter->pos, k.k->p) >= 0);
1633
1634                 if (bkey_cmp(bkey_start_pos(k.k), insert->k->k.p) >= 0)
1635                         break;
1636
1637                 overlap = bch2_extent_overlap(&insert->k->k, k.k);
1638
1639                 ret = extent_insert_check_split_compressed(&s, k.s_c, overlap);
1640                 if (ret != BTREE_INSERT_OK)
1641                         goto stop;
1642
1643                 if (!k.k->size)
1644                         goto squash;
1645
1646                 /*
1647                  * Only call advance pos & call hook for nonzero size extents:
1648                  */
1649                 ret = extent_insert_advance_pos(&s, k.s_c);
1650                 if (ret != BTREE_INSERT_OK)
1651                         goto stop;
1652
1653                 if (k.k->size &&
1654                     (k.k->needs_whiteout || bset_written(b, bset(b, t))))
1655                         insert->k->k.needs_whiteout = true;
1656
1657                 if (overlap == BCH_EXTENT_OVERLAP_ALL &&
1658                     bkey_whiteout(k.k) &&
1659                     k.k->needs_whiteout) {
1660                         unreserve_whiteout(b, t, _k);
1661                         _k->needs_whiteout = false;
1662                 }
1663 squash:
1664                 ret = extent_squash(&s, insert->k, t, _k, k, overlap);
1665                 if (ret != BTREE_INSERT_OK)
1666                         goto stop;
1667         }
1668
1669         if (ret == BTREE_INSERT_OK &&
1670             bkey_cmp(s.committed, insert->k->k.p) < 0)
1671                 ret = extent_insert_advance_pos(&s, bkey_s_c_null);
1672 stop:
1673         extent_insert_committed(&s);
1674         /*
1675          * Subtract any remaining sectors from @insert, if we bailed out early
1676          * and didn't fully insert @insert:
1677          */
1678         if (insert->k->k.size &&
1679             !(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))
1680                 bch2_subtract_sectors(&s, bkey_i_to_s_c(insert->k),
1681                                      bkey_start_offset(&insert->k->k),
1682                                      insert->k->k.size);
1683
1684         bch2_fs_usage_apply(c, &s.stats, trans->disk_res,
1685                            gc_pos_btree_node(b));
1686
1687         EBUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&insert->k->k)));
1688         EBUG_ON(bkey_cmp(iter->pos, s.committed));
1689         EBUG_ON((bkey_cmp(iter->pos, b->key.k.p) == 0) !=
1690                 !!(iter->flags & BTREE_ITER_AT_END_OF_LEAF));
1691
1692         if (insert->k->k.size && (iter->flags & BTREE_ITER_AT_END_OF_LEAF))
1693                 ret = BTREE_INSERT_NEED_TRAVERSE;
1694
1695         EBUG_ON(insert->k->k.size && ret == BTREE_INSERT_OK);
1696
1697         return ret;
1698 }
1699
1700 static const char *bch2_extent_invalid(const struct bch_fs *c,
1701                                        struct bkey_s_c k)
1702 {
1703         if (bkey_val_u64s(k.k) > BKEY_EXTENT_VAL_U64s_MAX)
1704                 return "value too big";
1705
1706         if (!k.k->size)
1707                 return "zero key size";
1708
1709         switch (k.k->type) {
1710         case BCH_EXTENT:
1711         case BCH_EXTENT_CACHED: {
1712                 struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
1713                 const union bch_extent_entry *entry;
1714                 struct bch_extent_crc_unpacked crc;
1715                 const struct bch_extent_ptr *ptr;
1716                 unsigned size_ondisk = e.k->size;
1717                 const char *reason;
1718                 unsigned nonce = UINT_MAX;
1719
1720                 extent_for_each_entry(e, entry) {
1721                         if (__extent_entry_type(entry) >= BCH_EXTENT_ENTRY_MAX)
1722                                 return "invalid extent entry type";
1723
1724                         if (extent_entry_is_crc(entry)) {
1725                                 crc = bch2_extent_crc_unpack(e.k, entry_to_crc(entry));
1726
1727                                 if (crc.offset + e.k->size >
1728                                     crc.uncompressed_size)
1729                                         return "checksum offset + key size > uncompressed size";
1730
1731                                 size_ondisk = crc.compressed_size;
1732
1733                                 if (!bch2_checksum_type_valid(c, crc.csum_type))
1734                                         return "invalid checksum type";
1735
1736                                 if (crc.compression_type >= BCH_COMPRESSION_NR)
1737                                         return "invalid compression type";
1738
1739                                 if (bch2_csum_type_is_encryption(crc.csum_type)) {
1740                                         if (nonce == UINT_MAX)
1741                                                 nonce = crc.offset + crc.nonce;
1742                                         else if (nonce != crc.offset + crc.nonce)
1743                                                 return "incorrect nonce";
1744                                 }
1745                         } else {
1746                                 ptr = entry_to_ptr(entry);
1747
1748                                 reason = extent_ptr_invalid(c, e, &entry->ptr,
1749                                                             size_ondisk, false);
1750                                 if (reason)
1751                                         return reason;
1752                         }
1753                 }
1754
1755                 return NULL;
1756         }
1757
1758         case BCH_RESERVATION: {
1759                 struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k);
1760
1761                 if (bkey_val_bytes(k.k) != sizeof(struct bch_reservation))
1762                         return "incorrect value size";
1763
1764                 if (!r.v->nr_replicas || r.v->nr_replicas > BCH_REPLICAS_MAX)
1765                         return "invalid nr_replicas";
1766
1767                 return NULL;
1768         }
1769
1770         default:
1771                 return "invalid value type";
1772         }
1773 }
1774
1775 static void bch2_extent_debugcheck_extent(struct bch_fs *c, struct btree *b,
1776                                           struct bkey_s_c_extent e)
1777 {
1778         const struct bch_extent_ptr *ptr;
1779         struct bch_dev *ca;
1780         struct bucket_mark mark;
1781         unsigned seq, stale;
1782         char buf[160];
1783         bool bad;
1784         unsigned replicas = 0;
1785
1786         /*
1787          * XXX: we should be doing most/all of these checks at startup time,
1788          * where we check bch2_bkey_invalid() in btree_node_read_done()
1789          *
1790          * But note that we can't check for stale pointers or incorrect gc marks
1791          * until after journal replay is done (it might be an extent that's
1792          * going to get overwritten during replay)
1793          */
1794
1795         extent_for_each_ptr(e, ptr) {
1796                 ca = bch_dev_bkey_exists(c, ptr->dev);
1797                 replicas++;
1798
1799                 /*
1800                  * If journal replay hasn't finished, we might be seeing keys
1801                  * that will be overwritten by the time journal replay is done:
1802                  */
1803                 if (!test_bit(JOURNAL_REPLAY_DONE, &c->journal.flags))
1804                         continue;
1805
1806                 stale = 0;
1807
1808                 do {
1809                         seq = read_seqcount_begin(&c->gc_pos_lock);
1810                         mark = ptr_bucket_mark(ca, ptr);
1811
1812                         /* between mark and bucket gen */
1813                         smp_rmb();
1814
1815                         stale = ptr_stale(ca, ptr);
1816
1817                         bch2_fs_bug_on(stale && !ptr->cached, c,
1818                                          "stale dirty pointer");
1819
1820                         bch2_fs_bug_on(stale > 96, c,
1821                                          "key too stale: %i",
1822                                          stale);
1823
1824                         if (stale)
1825                                 break;
1826
1827                         bad = gc_pos_cmp(c->gc_pos, gc_pos_btree_node(b)) > 0 &&
1828                                 (mark.data_type != BCH_DATA_USER ||
1829                                  !(ptr->cached
1830                                    ? mark.cached_sectors
1831                                    : mark.dirty_sectors));
1832                 } while (read_seqcount_retry(&c->gc_pos_lock, seq));
1833
1834                 if (bad)
1835                         goto bad_ptr;
1836         }
1837
1838         if (replicas > BCH_REPLICAS_MAX) {
1839                 bch2_bkey_val_to_text(c, btree_node_type(b), buf,
1840                                      sizeof(buf), e.s_c);
1841                 bch2_fs_bug(c,
1842                         "extent key bad (too many replicas: %u): %s",
1843                         replicas, buf);
1844                 return;
1845         }
1846
1847         if (!bkey_extent_is_cached(e.k) &&
1848             !bch2_bkey_replicas_marked(c, BCH_DATA_USER, e.s_c)) {
1849                 bch2_bkey_val_to_text(c, btree_node_type(b),
1850                                      buf, sizeof(buf), e.s_c);
1851                 bch2_fs_bug(c,
1852                         "extent key bad (replicas not marked in superblock):\n%s",
1853                         buf);
1854                 return;
1855         }
1856
1857         return;
1858
1859 bad_ptr:
1860         bch2_bkey_val_to_text(c, btree_node_type(b), buf,
1861                              sizeof(buf), e.s_c);
1862         bch2_fs_bug(c, "extent pointer bad gc mark: %s:\nbucket %zu "
1863                    "gen %i type %u", buf,
1864                    PTR_BUCKET_NR(ca, ptr), mark.gen, mark.data_type);
1865         return;
1866 }
1867
1868 static void bch2_extent_debugcheck(struct bch_fs *c, struct btree *b,
1869                                    struct bkey_s_c k)
1870 {
1871         switch (k.k->type) {
1872         case BCH_EXTENT:
1873         case BCH_EXTENT_CACHED:
1874                 bch2_extent_debugcheck_extent(c, b, bkey_s_c_to_extent(k));
1875                 break;
1876         case BCH_RESERVATION:
1877                 break;
1878         default:
1879                 BUG();
1880         }
1881 }
1882
1883 static void bch2_extent_to_text(struct bch_fs *c, char *buf,
1884                                 size_t size, struct bkey_s_c k)
1885 {
1886         char *out = buf, *end = buf + size;
1887         const char *invalid;
1888
1889 #define p(...)  (out += scnprintf(out, end - out, __VA_ARGS__))
1890
1891         if (bkey_extent_is_data(k.k))
1892                 out += extent_print_ptrs(c, buf, size, bkey_s_c_to_extent(k));
1893
1894         invalid = bch2_extent_invalid(c, k);
1895         if (invalid)
1896                 p(" invalid: %s", invalid);
1897 #undef p
1898 }
1899
1900 static void bch2_extent_crc_init(union bch_extent_crc *crc,
1901                                  struct bch_extent_crc_unpacked new)
1902 {
1903 #define common_fields(_crc)                                             \
1904                 .csum_type              = _crc.csum_type,               \
1905                 .compression_type       = _crc.compression_type,        \
1906                 ._compressed_size       = _crc.compressed_size - 1,     \
1907                 ._uncompressed_size     = _crc.uncompressed_size - 1,   \
1908                 .offset                 = _crc.offset
1909
1910         if (bch_crc_bytes[new.csum_type]        <= 4 &&
1911             new.uncompressed_size               <= CRC32_SIZE_MAX &&
1912             new.nonce                           <= CRC32_NONCE_MAX) {
1913                 crc->crc32 = (struct bch_extent_crc32) {
1914                         .type = 1 << BCH_EXTENT_ENTRY_crc32,
1915                         common_fields(new),
1916                         .csum                   = *((__le32 *) &new.csum.lo),
1917                 };
1918                 return;
1919         }
1920
1921         if (bch_crc_bytes[new.csum_type]        <= 10 &&
1922             new.uncompressed_size               <= CRC64_SIZE_MAX &&
1923             new.nonce                           <= CRC64_NONCE_MAX) {
1924                 crc->crc64 = (struct bch_extent_crc64) {
1925                         .type = 1 << BCH_EXTENT_ENTRY_crc64,
1926                         common_fields(new),
1927                         .nonce                  = new.nonce,
1928                         .csum_lo                = new.csum.lo,
1929                         .csum_hi                = *((__le16 *) &new.csum.hi),
1930                 };
1931                 return;
1932         }
1933
1934         if (bch_crc_bytes[new.csum_type]        <= 16 &&
1935             new.uncompressed_size               <= CRC128_SIZE_MAX &&
1936             new.nonce                           <= CRC128_NONCE_MAX) {
1937                 crc->crc128 = (struct bch_extent_crc128) {
1938                         .type = 1 << BCH_EXTENT_ENTRY_crc128,
1939                         common_fields(new),
1940                         .nonce                  = new.nonce,
1941                         .csum                   = new.csum,
1942                 };
1943                 return;
1944         }
1945 #undef common_fields
1946         BUG();
1947 }
1948
1949 void bch2_extent_crc_append(struct bkey_i_extent *e,
1950                             struct bch_extent_crc_unpacked new)
1951 {
1952         struct bch_extent_crc_unpacked crc;
1953         const union bch_extent_entry *i;
1954
1955         BUG_ON(new.compressed_size > new.uncompressed_size);
1956         BUG_ON(new.live_size != e->k.size);
1957         BUG_ON(!new.compressed_size || !new.uncompressed_size);
1958
1959         /*
1960          * Look up the last crc entry, so we can check if we need to add
1961          * another:
1962          */
1963         extent_for_each_crc(extent_i_to_s(e), crc, i)
1964                 ;
1965
1966         if (!memcmp(&crc, &new, sizeof(crc)))
1967                 return;
1968
1969         bch2_extent_crc_init((void *) extent_entry_last(extent_i_to_s(e)), new);
1970         __extent_entry_push(e);
1971 }
1972
1973 /*
1974  * bch_extent_normalize - clean up an extent, dropping stale pointers etc.
1975  *
1976  * Returns true if @k should be dropped entirely
1977  *
1978  * For existing keys, only called when btree nodes are being rewritten, not when
1979  * they're merely being compacted/resorted in memory.
1980  */
1981 bool bch2_extent_normalize(struct bch_fs *c, struct bkey_s k)
1982 {
1983         struct bkey_s_extent e;
1984
1985         switch (k.k->type) {
1986         case KEY_TYPE_ERROR:
1987                 return false;
1988
1989         case KEY_TYPE_DELETED:
1990         case KEY_TYPE_COOKIE:
1991                 return true;
1992
1993         case KEY_TYPE_DISCARD:
1994                 return bversion_zero(k.k->version);
1995
1996         case BCH_EXTENT:
1997         case BCH_EXTENT_CACHED:
1998                 e = bkey_s_to_extent(k);
1999
2000                 bch2_extent_drop_stale(c, e);
2001
2002                 if (!bkey_val_u64s(e.k)) {
2003                         if (bkey_extent_is_cached(e.k)) {
2004                                 k.k->type = KEY_TYPE_DISCARD;
2005                                 if (bversion_zero(k.k->version))
2006                                         return true;
2007                         } else {
2008                                 k.k->type = KEY_TYPE_ERROR;
2009                         }
2010                 }
2011
2012                 return false;
2013         case BCH_RESERVATION:
2014                 return false;
2015         default:
2016                 BUG();
2017         }
2018 }
2019
2020 void bch2_extent_mark_replicas_cached(struct bch_fs *c,
2021                                       struct bkey_s_extent e,
2022                                       unsigned target,
2023                                       unsigned nr_desired_replicas)
2024 {
2025         struct bch_extent_ptr *ptr;
2026         int extra = bch2_extent_durability(c, e.c) - nr_desired_replicas;
2027
2028         if (target && extra > 0)
2029                 extent_for_each_ptr(e, ptr) {
2030                         int n = bch2_extent_ptr_durability(c, ptr);
2031
2032                         if (n && n <= extra &&
2033                             !dev_in_target(c->devs[ptr->dev], target)) {
2034                                 ptr->cached = true;
2035                                 extra -= n;
2036                         }
2037                 }
2038
2039         if (extra > 0)
2040                 extent_for_each_ptr(e, ptr) {
2041                         int n = bch2_extent_ptr_durability(c, ptr);
2042
2043                         if (n && n <= extra) {
2044                                 ptr->cached = true;
2045                                 extra -= n;
2046                         }
2047                 }
2048 }
2049
2050 /*
2051  * This picks a non-stale pointer, preferably from a device other than @avoid.
2052  * Avoid can be NULL, meaning pick any. If there are no non-stale pointers to
2053  * other devices, it will still pick a pointer from avoid.
2054  */
2055 void bch2_extent_pick_ptr(struct bch_fs *c, struct bkey_s_c k,
2056                           struct bch_devs_mask *avoid,
2057                           struct extent_pick_ptr *ret)
2058 {
2059         struct bkey_s_c_extent e;
2060
2061         switch (k.k->type) {
2062         case KEY_TYPE_DELETED:
2063         case KEY_TYPE_DISCARD:
2064         case KEY_TYPE_COOKIE:
2065                 ret->ca = NULL;
2066                 return;
2067
2068         case KEY_TYPE_ERROR:
2069                 ret->ca = ERR_PTR(-EIO);
2070                 return;
2071
2072         case BCH_EXTENT:
2073         case BCH_EXTENT_CACHED:
2074                 e = bkey_s_c_to_extent(k);
2075                 ret->ca = NULL;
2076
2077                 extent_pick_read_device(c, bkey_s_c_to_extent(k), avoid, ret);
2078
2079                 if (!ret->ca && !bkey_extent_is_cached(e.k))
2080                         ret->ca = ERR_PTR(-EIO);
2081                 return;
2082
2083         case BCH_RESERVATION:
2084                 ret->ca = NULL;
2085                 return;
2086
2087         default:
2088                 BUG();
2089         }
2090 }
2091
2092 static enum merge_result bch2_extent_merge(struct bch_fs *c,
2093                                            struct btree *bk,
2094                                            struct bkey_i *l, struct bkey_i *r)
2095 {
2096         struct bkey_s_extent el, er;
2097         union bch_extent_entry *en_l, *en_r;
2098
2099         if (key_merging_disabled(c))
2100                 return BCH_MERGE_NOMERGE;
2101
2102         /*
2103          * Generic header checks
2104          * Assumes left and right are in order
2105          * Left and right must be exactly aligned
2106          */
2107
2108         if (l->k.u64s           != r->k.u64s ||
2109             l->k.type           != r->k.type ||
2110             bversion_cmp(l->k.version, r->k.version) ||
2111             bkey_cmp(l->k.p, bkey_start_pos(&r->k)))
2112                 return BCH_MERGE_NOMERGE;
2113
2114         switch (l->k.type) {
2115         case KEY_TYPE_DELETED:
2116         case KEY_TYPE_DISCARD:
2117         case KEY_TYPE_ERROR:
2118                 /* These types are mergeable, and no val to check */
2119                 break;
2120
2121         case BCH_EXTENT:
2122         case BCH_EXTENT_CACHED:
2123                 el = bkey_i_to_s_extent(l);
2124                 er = bkey_i_to_s_extent(r);
2125
2126                 extent_for_each_entry(el, en_l) {
2127                         struct bch_extent_ptr *lp, *rp;
2128                         struct bch_dev *ca;
2129
2130                         en_r = vstruct_idx(er.v, (u64 *) en_l - el.v->_data);
2131
2132                         if ((extent_entry_type(en_l) !=
2133                              extent_entry_type(en_r)) ||
2134                             extent_entry_is_crc(en_l))
2135                                 return BCH_MERGE_NOMERGE;
2136
2137                         lp = &en_l->ptr;
2138                         rp = &en_r->ptr;
2139
2140                         if (lp->offset + el.k->size     != rp->offset ||
2141                             lp->dev                     != rp->dev ||
2142                             lp->gen                     != rp->gen)
2143                                 return BCH_MERGE_NOMERGE;
2144
2145                         /* We don't allow extents to straddle buckets: */
2146                         ca = bch_dev_bkey_exists(c, lp->dev);
2147
2148                         if (PTR_BUCKET_NR(ca, lp) != PTR_BUCKET_NR(ca, rp))
2149                                 return BCH_MERGE_NOMERGE;
2150                 }
2151
2152                 break;
2153         case BCH_RESERVATION: {
2154                 struct bkey_i_reservation *li = bkey_i_to_reservation(l);
2155                 struct bkey_i_reservation *ri = bkey_i_to_reservation(r);
2156
2157                 if (li->v.generation != ri->v.generation ||
2158                     li->v.nr_replicas != ri->v.nr_replicas)
2159                         return BCH_MERGE_NOMERGE;
2160                 break;
2161         }
2162         default:
2163                 return BCH_MERGE_NOMERGE;
2164         }
2165
2166         l->k.needs_whiteout |= r->k.needs_whiteout;
2167
2168         /* Keys with no pointers aren't restricted to one bucket and could
2169          * overflow KEY_SIZE
2170          */
2171         if ((u64) l->k.size + r->k.size > KEY_SIZE_MAX) {
2172                 bch2_key_resize(&l->k, KEY_SIZE_MAX);
2173                 bch2_cut_front(l->k.p, r);
2174                 return BCH_MERGE_PARTIAL;
2175         }
2176
2177         bch2_key_resize(&l->k, l->k.size + r->k.size);
2178
2179         return BCH_MERGE_MERGE;
2180 }
2181
2182 static void extent_i_save(struct btree *b, struct bkey_packed *dst,
2183                           struct bkey_i *src)
2184 {
2185         struct bkey_format *f = &b->format;
2186         struct bkey_i *dst_unpacked;
2187
2188         BUG_ON(bkeyp_val_u64s(f, dst) != bkey_val_u64s(&src->k));
2189
2190         /*
2191          * We don't want the bch2_verify_key_order() call in extent_save(),
2192          * because we may be out of order with deleted keys that are about to be
2193          * removed by extent_bset_insert()
2194          */
2195
2196         if ((dst_unpacked = packed_to_bkey(dst)))
2197                 bkey_copy(dst_unpacked, src);
2198         else
2199                 BUG_ON(!bch2_bkey_pack(dst, src, f));
2200 }
2201
2202 static bool extent_merge_one_overlapping(struct btree_iter *iter,
2203                                          struct bpos new_pos,
2204                                          struct bset_tree *t,
2205                                          struct bkey_packed *k, struct bkey uk,
2206                                          bool check, bool could_pack)
2207 {
2208         struct btree_iter_level *l = &iter->l[0];
2209
2210         BUG_ON(!bkey_deleted(k));
2211
2212         if (check) {
2213                 return !bkey_packed(k) || could_pack;
2214         } else {
2215                 uk.p = new_pos;
2216                 extent_save(l->b, &l->iter, k, &uk);
2217                 bch2_bset_fix_invalidated_key(l->b, t, k);
2218                 bch2_btree_node_iter_fix(iter, l->b, &l->iter, t,
2219                                          k, k->u64s, k->u64s);
2220                 return true;
2221         }
2222 }
2223
2224 static bool extent_merge_do_overlapping(struct btree_iter *iter,
2225                                         struct bkey *m, bool back_merge)
2226 {
2227         struct btree_iter_level *l = &iter->l[0];
2228         struct btree *b = l->b;
2229         struct btree_node_iter *node_iter = &l->iter;
2230         struct bset_tree *t;
2231         struct bkey_packed *k;
2232         struct bkey uk;
2233         struct bpos new_pos = back_merge ? m->p : bkey_start_pos(m);
2234         bool could_pack = bkey_pack_pos((void *) &uk, new_pos, b);
2235         bool check = true;
2236
2237         /*
2238          * @m is the new merged extent:
2239          *
2240          * The merge took place in the last bset; we know there can't be any 0
2241          * size extents overlapping with m there because if so they would have
2242          * been between the two extents we merged.
2243          *
2244          * But in the other bsets, we have to check for and fix such extents:
2245          */
2246 do_fixup:
2247         for_each_bset(b, t) {
2248                 if (t == bset_tree_last(b))
2249                         break;
2250
2251                 /*
2252                  * if we don't find this bset in the iterator we already got to
2253                  * the end of that bset, so start searching from the end.
2254                  */
2255                 k = bch2_btree_node_iter_bset_pos(node_iter, b, t);
2256
2257                 if (k == btree_bkey_last(b, t))
2258                         k = bch2_bkey_prev_all(b, t, k);
2259                 if (!k)
2260                         continue;
2261
2262                 if (back_merge) {
2263                         /*
2264                          * Back merge: 0 size extents will be before the key
2265                          * that was just inserted (and thus the iterator
2266                          * position) - walk backwards to find them
2267                          */
2268                         for (;
2269                              k &&
2270                              (uk = bkey_unpack_key(b, k),
2271                               bkey_cmp(uk.p, bkey_start_pos(m)) > 0);
2272                              k = bch2_bkey_prev_all(b, t, k)) {
2273                                 if (bkey_cmp(uk.p, m->p) >= 0)
2274                                         continue;
2275
2276                                 if (!extent_merge_one_overlapping(iter, new_pos,
2277                                                 t, k, uk, check, could_pack))
2278                                         return false;
2279                         }
2280                 } else {
2281                         /* Front merge - walk forwards */
2282                         for (;
2283                              k != btree_bkey_last(b, t) &&
2284                              (uk = bkey_unpack_key(b, k),
2285                               bkey_cmp(uk.p, m->p) < 0);
2286                              k = bkey_next(k)) {
2287                                 if (bkey_cmp(uk.p,
2288                                              bkey_start_pos(m)) <= 0)
2289                                         continue;
2290
2291                                 if (!extent_merge_one_overlapping(iter, new_pos,
2292                                                 t, k, uk, check, could_pack))
2293                                         return false;
2294                         }
2295                 }
2296         }
2297
2298         if (check) {
2299                 check = false;
2300                 goto do_fixup;
2301         }
2302
2303         return true;
2304 }
2305
2306 /*
2307  * When merging an extent that we're inserting into a btree node, the new merged
2308  * extent could overlap with an existing 0 size extent - if we don't fix that,
2309  * it'll break the btree node iterator so this code finds those 0 size extents
2310  * and shifts them out of the way.
2311  *
2312  * Also unpacks and repacks.
2313  */
2314 static bool bch2_extent_merge_inline(struct bch_fs *c,
2315                                      struct btree_iter *iter,
2316                                      struct bkey_packed *l,
2317                                      struct bkey_packed *r,
2318                                      bool back_merge)
2319 {
2320         struct btree *b = iter->l[0].b;
2321         struct btree_node_iter *node_iter = &iter->l[0].iter;
2322         const struct bkey_format *f = &b->format;
2323         struct bset_tree *t = bset_tree_last(b);
2324         struct bkey_packed *m;
2325         BKEY_PADDED(k) li;
2326         BKEY_PADDED(k) ri;
2327         struct bkey_i *mi;
2328         struct bkey tmp;
2329
2330         /*
2331          * We need to save copies of both l and r, because we might get a
2332          * partial merge (which modifies both) and then fails to repack
2333          */
2334         bch2_bkey_unpack(b, &li.k, l);
2335         bch2_bkey_unpack(b, &ri.k, r);
2336
2337         m = back_merge ? l : r;
2338         mi = back_merge ? &li.k : &ri.k;
2339
2340         /* l & r should be in last bset: */
2341         EBUG_ON(bch2_bkey_to_bset(b, m) != t);
2342
2343         switch (bch2_extent_merge(c, b, &li.k, &ri.k)) {
2344         case BCH_MERGE_NOMERGE:
2345                 return false;
2346         case BCH_MERGE_PARTIAL:
2347                 if (bkey_packed(m) && !bch2_bkey_pack_key((void *) &tmp, &mi->k, f))
2348                         return false;
2349
2350                 if (!extent_merge_do_overlapping(iter, &li.k.k, back_merge))
2351                         return false;
2352
2353                 extent_i_save(b, m, mi);
2354                 bch2_bset_fix_invalidated_key(b, t, m);
2355
2356                 /*
2357                  * Update iterator to reflect what we just inserted - otherwise,
2358                  * the iter_fix() call is going to put us _before_ the key we
2359                  * just partially merged with:
2360                  */
2361                 if (back_merge)
2362                         bch2_btree_iter_set_pos_same_leaf(iter, li.k.k.p);
2363
2364                 bch2_btree_node_iter_fix(iter, b, node_iter,
2365                                          t, m, m->u64s, m->u64s);
2366
2367                 if (!back_merge)
2368                         bkey_copy(packed_to_bkey(l), &li.k);
2369                 else
2370                         bkey_copy(packed_to_bkey(r), &ri.k);
2371                 return false;
2372         case BCH_MERGE_MERGE:
2373                 if (bkey_packed(m) && !bch2_bkey_pack_key((void *) &tmp, &li.k.k, f))
2374                         return false;
2375
2376                 if (!extent_merge_do_overlapping(iter, &li.k.k, back_merge))
2377                         return false;
2378
2379                 extent_i_save(b, m, &li.k);
2380                 bch2_bset_fix_invalidated_key(b, t, m);
2381
2382                 bch2_btree_node_iter_fix(iter, b, node_iter,
2383                                          t, m, m->u64s, m->u64s);
2384                 return true;
2385         default:
2386                 BUG();
2387         }
2388 }
2389
2390 int bch2_check_range_allocated(struct bch_fs *c, struct bpos pos, u64 size)
2391 {
2392         struct btree_iter iter;
2393         struct bpos end = pos;
2394         struct bkey_s_c k;
2395         int ret = 0;
2396
2397         end.offset += size;
2398
2399         for_each_btree_key(&iter, c, BTREE_ID_EXTENTS, pos,
2400                              BTREE_ITER_SLOTS, k) {
2401                 if (bkey_cmp(bkey_start_pos(k.k), end) >= 0)
2402                         break;
2403
2404                 if (!bch2_extent_is_fully_allocated(k)) {
2405                         ret = -ENOSPC;
2406                         break;
2407                 }
2408         }
2409         bch2_btree_iter_unlock(&iter);
2410
2411         return ret;
2412 }
2413
2414 const struct bkey_ops bch2_bkey_extent_ops = {
2415         .key_invalid    = bch2_extent_invalid,
2416         .key_debugcheck = bch2_extent_debugcheck,
2417         .val_to_text    = bch2_extent_to_text,
2418         .swab           = bch2_ptr_swab,
2419         .key_normalize  = bch2_ptr_normalize,
2420         .key_merge      = bch2_extent_merge,
2421         .is_extents     = true,
2422 };