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

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
   4  *
   5  * Code for managing the extent btree and dynamically updating the writeback
   6  * dirty sector count.
   7  */
   8
   9 #include "bcachefs.h"
  10 #include "bkey_methods.h"
  11 #include "btree_gc.h"
  12 #include "btree_io.h"
  13 #include "btree_iter.h"
  14 #include "buckets.h"
  15 #include "checksum.h"
  16 #include "debug.h"
  17 #include "disk_groups.h"
  18 #include "error.h"
  19 #include "extents.h"
  20 #include "inode.h"
  21 #include "journal.h"
  22 #include "replicas.h"
  23 #include "super.h"
  24 #include "super-io.h"
  25 #include "util.h"
  26
  27 #include <trace/events/bcachefs.h>
  28
  29 static unsigned bch2_crc_field_size_max[] = {
  30         [BCH_EXTENT_ENTRY_crc32] = CRC32_SIZE_MAX,
  31         [BCH_EXTENT_ENTRY_crc64] = CRC64_SIZE_MAX,
  32         [BCH_EXTENT_ENTRY_crc128] = CRC128_SIZE_MAX,
  33 };
  34
  35 static void bch2_extent_crc_pack(union bch_extent_crc *,
  36                                  struct bch_extent_crc_unpacked,
  37                                  enum bch_extent_entry_type);
  38
  39 static struct bch_dev_io_failures *dev_io_failures(struct bch_io_failures *f,
  40                                                    unsigned dev)
  41 {
  42         struct bch_dev_io_failures *i;
  43
  44         for (i = f->devs; i < f->devs + f->nr; i++)
  45                 if (i->dev == dev)
  46                         return i;
  47
  48         return NULL;
  49 }
  50
  51 void bch2_mark_io_failure(struct bch_io_failures *failed,
  52                           struct extent_ptr_decoded *p)
  53 {
  54         struct bch_dev_io_failures *f = dev_io_failures(failed, p->ptr.dev);
  55
  56         if (!f) {
  57                 BUG_ON(failed->nr >= ARRAY_SIZE(failed->devs));
  58
  59                 f = &failed->devs[failed->nr++];
  60                 f->dev          = p->ptr.dev;
  61                 f->idx          = p->idx;
  62                 f->nr_failed    = 1;
  63                 f->nr_retries   = 0;
  64         } else if (p->idx != f->idx) {
  65                 f->idx          = p->idx;
  66                 f->nr_failed    = 1;
  67                 f->nr_retries   = 0;
  68         } else {
  69                 f->nr_failed++;
  70         }
  71 }
  72
  73 /*
  74  * returns true if p1 is better than p2:
  75  */
  76 static inline bool ptr_better(struct bch_fs *c,
  77                               const struct extent_ptr_decoded p1,
  78                               const struct extent_ptr_decoded p2)
  79 {
  80         if (likely(!p1.idx && !p2.idx)) {
  81                 struct bch_dev *dev1 = bch_dev_bkey_exists(c, p1.ptr.dev);
  82                 struct bch_dev *dev2 = bch_dev_bkey_exists(c, p2.ptr.dev);
  83
  84                 u64 l1 = atomic64_read(&dev1->cur_latency[READ]);
  85                 u64 l2 = atomic64_read(&dev2->cur_latency[READ]);
  86
  87                 /* Pick at random, biased in favor of the faster device: */
  88
  89                 return bch2_rand_range(l1 + l2) > l1;
  90         }
  91
  92         if (bch2_force_reconstruct_read)
  93                 return p1.idx > p2.idx;
  94
  95         return p1.idx < p2.idx;
  96 }
  97
  98 /*
  99  * This picks a non-stale pointer, preferably from a device other than @avoid.
 100  * Avoid can be NULL, meaning pick any. If there are no non-stale pointers to
 101  * other devices, it will still pick a pointer from avoid.
 102  */
 103 int bch2_bkey_pick_read_device(struct bch_fs *c, struct bkey_s_c k,
 104                                struct bch_io_failures *failed,
 105                                struct extent_ptr_decoded *pick)
 106 {
 107         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 108         const union bch_extent_entry *entry;
 109         struct extent_ptr_decoded p;
 110         struct bch_dev_io_failures *f;
 111         struct bch_dev *ca;
 112         int ret = 0;
 113
 114         if (k.k->type == KEY_TYPE_error)
 115                 return -EIO;
 116
 117         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
 118                 ca = bch_dev_bkey_exists(c, p.ptr.dev);
 119
 120                 /*
 121                  * If there are any dirty pointers it's an error if we can't
 122                  * read:
 123                  */
 124                 if (!ret && !p.ptr.cached)
 125                         ret = -EIO;
 126
 127                 if (p.ptr.cached && ptr_stale(ca, &p.ptr))
 128                         continue;
 129
 130                 f = failed ? dev_io_failures(failed, p.ptr.dev) : NULL;
 131                 if (f)
 132                         p.idx = f->nr_failed < f->nr_retries
 133                                 ? f->idx
 134                                 : f->idx + 1;
 135
 136                 if (!p.idx &&
 137                     !bch2_dev_is_readable(ca))
 138                         p.idx++;
 139
 140                 if (bch2_force_reconstruct_read &&
 141                     !p.idx && p.has_ec)
 142                         p.idx++;
 143
 144                 if (p.idx >= (unsigned) p.has_ec + 1)
 145                         continue;
 146
 147                 if (ret > 0 && !ptr_better(c, p, *pick))
 148                         continue;
 149
 150                 *pick = p;
 151                 ret = 1;
 152         }
 153
 154         return ret;
 155 }
 156
 157 /* KEY_TYPE_btree_ptr: */
 158
 159 int bch2_btree_ptr_invalid(const struct bch_fs *c, struct bkey_s_c k,
 160                            int rw, struct printbuf *err)
 161 {
 162         if (bkey_val_u64s(k.k) > BCH_REPLICAS_MAX) {
 163                 pr_buf(err, "value too big (%zu > %u)",
 164                        bkey_val_u64s(k.k), BCH_REPLICAS_MAX);
 165                 return -EINVAL;
 166         }
 167
 168         return bch2_bkey_ptrs_invalid(c, k, rw, err);
 169 }
 170
 171 void bch2_btree_ptr_to_text(struct printbuf *out, struct bch_fs *c,
 172                             struct bkey_s_c k)
 173 {
 174         bch2_bkey_ptrs_to_text(out, c, k);
 175 }
 176
 177 int bch2_btree_ptr_v2_invalid(const struct bch_fs *c, struct bkey_s_c k,
 178                               int rw, struct printbuf *err)
 179 {
 180         struct bkey_s_c_btree_ptr_v2 bp = bkey_s_c_to_btree_ptr_v2(k);
 181
 182         if (bkey_val_bytes(k.k) <= sizeof(*bp.v)) {
 183                 pr_buf(err, "value too small (%zu <= %zu)",
 184                        bkey_val_bytes(k.k), sizeof(*bp.v));
 185                 return -EINVAL;
 186         }
 187
 188         if (bkey_val_u64s(k.k) > BKEY_BTREE_PTR_VAL_U64s_MAX) {
 189                 pr_buf(err, "value too big (%zu > %zu)",
 190                        bkey_val_u64s(k.k), BKEY_BTREE_PTR_VAL_U64s_MAX);
 191                 return -EINVAL;
 192         }
 193
 194         if (c->sb.version < bcachefs_metadata_version_snapshot &&
 195             bp.v->min_key.snapshot) {
 196                 pr_buf(err, "invalid min_key.snapshot (%u != 0)",
 197                        bp.v->min_key.snapshot);
 198                 return -EINVAL;
 199         }
 200
 201         return bch2_bkey_ptrs_invalid(c, k, rw, err);
 202 }
 203
 204 void bch2_btree_ptr_v2_to_text(struct printbuf *out, struct bch_fs *c,
 205                                struct bkey_s_c k)
 206 {
 207         struct bkey_s_c_btree_ptr_v2 bp = bkey_s_c_to_btree_ptr_v2(k);
 208
 209         pr_buf(out, "seq %llx written %u min_key %s",
 210                le64_to_cpu(bp.v->seq),
 211                le16_to_cpu(bp.v->sectors_written),
 212                BTREE_PTR_RANGE_UPDATED(bp.v) ? "R " : "");
 213
 214         bch2_bpos_to_text(out, bp.v->min_key);
 215         pr_buf(out, " ");
 216         bch2_bkey_ptrs_to_text(out, c, k);
 217 }
 218
 219 void bch2_btree_ptr_v2_compat(enum btree_id btree_id, unsigned version,
 220                               unsigned big_endian, int write,
 221                               struct bkey_s k)
 222 {
 223         struct bkey_s_btree_ptr_v2 bp = bkey_s_to_btree_ptr_v2(k);
 224
 225         compat_bpos(0, btree_id, version, big_endian, write, &bp.v->min_key);
 226
 227         if (version < bcachefs_metadata_version_inode_btree_change &&
 228             btree_node_type_is_extents(btree_id) &&
 229             bkey_cmp(bp.v->min_key, POS_MIN))
 230                 bp.v->min_key = write
 231                         ? bpos_nosnap_predecessor(bp.v->min_key)
 232                         : bpos_nosnap_successor(bp.v->min_key);
 233 }
 234
 235 /* KEY_TYPE_extent: */
 236
 237 bool bch2_extent_merge(struct bch_fs *c, struct bkey_s l, struct bkey_s_c r)
 238 {
 239         struct bkey_ptrs   l_ptrs = bch2_bkey_ptrs(l);
 240         struct bkey_ptrs_c r_ptrs = bch2_bkey_ptrs_c(r);
 241         union bch_extent_entry *en_l;
 242         const union bch_extent_entry *en_r;
 243         struct extent_ptr_decoded lp, rp;
 244         bool use_right_ptr;
 245         struct bch_dev *ca;
 246
 247         en_l = l_ptrs.start;
 248         en_r = r_ptrs.start;
 249         while (en_l < l_ptrs.end && en_r < r_ptrs.end) {
 250                 if (extent_entry_type(en_l) != extent_entry_type(en_r))
 251                         return false;
 252
 253                 en_l = extent_entry_next(en_l);
 254                 en_r = extent_entry_next(en_r);
 255         }
 256
 257         if (en_l < l_ptrs.end || en_r < r_ptrs.end)
 258                 return false;
 259
 260         en_l = l_ptrs.start;
 261         en_r = r_ptrs.start;
 262         lp.crc = bch2_extent_crc_unpack(l.k, NULL);
 263         rp.crc = bch2_extent_crc_unpack(r.k, NULL);
 264
 265         while (__bkey_ptr_next_decode(l.k, l_ptrs.end, lp, en_l) &&
 266                __bkey_ptr_next_decode(r.k, r_ptrs.end, rp, en_r)) {
 267                 if (lp.ptr.offset + lp.crc.offset + lp.crc.live_size !=
 268                     rp.ptr.offset + rp.crc.offset ||
 269                     lp.ptr.dev                  != rp.ptr.dev ||
 270                     lp.ptr.gen                  != rp.ptr.gen ||
 271                     lp.has_ec                   != rp.has_ec)
 272                         return false;
 273
 274                 /* Extents may not straddle buckets: */
 275                 ca = bch_dev_bkey_exists(c, lp.ptr.dev);
 276                 if (PTR_BUCKET_NR(ca, &lp.ptr) != PTR_BUCKET_NR(ca, &rp.ptr))
 277                         return false;
 278
 279                 if (lp.has_ec                   != rp.has_ec ||
 280                     (lp.has_ec &&
 281                      (lp.ec.block               != rp.ec.block ||
 282                       lp.ec.redundancy          != rp.ec.redundancy ||
 283                       lp.ec.idx                 != rp.ec.idx)))
 284                         return false;
 285
 286                 if (lp.crc.compression_type     != rp.crc.compression_type ||
 287                     lp.crc.nonce                != rp.crc.nonce)
 288                         return false;
 289
 290                 if (lp.crc.offset + lp.crc.live_size + rp.crc.live_size <=
 291                     lp.crc.uncompressed_size) {
 292                         /* can use left extent's crc entry */
 293                 } else if (lp.crc.live_size <= rp.crc.offset ) {
 294                         /* can use right extent's crc entry */
 295                 } else {
 296                         /* check if checksums can be merged: */
 297                         if (lp.crc.csum_type            != rp.crc.csum_type ||
 298                             lp.crc.nonce                != rp.crc.nonce ||
 299                             crc_is_compressed(lp.crc) ||
 300                             !bch2_checksum_mergeable(lp.crc.csum_type))
 301                                 return false;
 302
 303                         if (lp.crc.offset + lp.crc.live_size != lp.crc.compressed_size ||
 304                             rp.crc.offset)
 305                                 return false;
 306
 307                         if (lp.crc.csum_type &&
 308                             lp.crc.uncompressed_size +
 309                             rp.crc.uncompressed_size > (c->opts.encoded_extent_max >> 9))
 310                                 return false;
 311
 312                         if (lp.crc.uncompressed_size + rp.crc.uncompressed_size >
 313                             bch2_crc_field_size_max[extent_entry_type(en_l)])
 314                                 return false;
 315                 }
 316
 317                 en_l = extent_entry_next(en_l);
 318                 en_r = extent_entry_next(en_r);
 319         }
 320
 321         use_right_ptr = false;
 322         en_l = l_ptrs.start;
 323         en_r = r_ptrs.start;
 324         while (en_l < l_ptrs.end) {
 325                 if (extent_entry_type(en_l) == BCH_EXTENT_ENTRY_ptr &&
 326                     use_right_ptr)
 327                         en_l->ptr = en_r->ptr;
 328
 329                 if (extent_entry_is_crc(en_l)) {
 330                         struct bch_extent_crc_unpacked crc_l =
 331                                 bch2_extent_crc_unpack(l.k, entry_to_crc(en_l));
 332                         struct bch_extent_crc_unpacked crc_r =
 333                                 bch2_extent_crc_unpack(r.k, entry_to_crc(en_r));
 334
 335                         use_right_ptr = false;
 336
 337                         if (crc_l.offset + crc_l.live_size + crc_r.live_size <=
 338                             crc_l.uncompressed_size) {
 339                                 /* can use left extent's crc entry */
 340                         } else if (crc_l.live_size <= crc_r.offset ) {
 341                                 /* can use right extent's crc entry */
 342                                 crc_r.offset -= crc_l.live_size;
 343                                 bch2_extent_crc_pack(entry_to_crc(en_l), crc_r,
 344                                                      extent_entry_type(en_l));
 345                                 use_right_ptr = true;
 346                         } else {
 347                                 crc_l.csum = bch2_checksum_merge(crc_l.csum_type,
 348                                                                  crc_l.csum,
 349                                                                  crc_r.csum,
 350                                                                  crc_r.uncompressed_size << 9);
 351
 352                                 crc_l.uncompressed_size += crc_r.uncompressed_size;
 353                                 crc_l.compressed_size   += crc_r.compressed_size;
 354                                 bch2_extent_crc_pack(entry_to_crc(en_l), crc_l,
 355                                                      extent_entry_type(en_l));
 356                         }
 357                 }
 358
 359                 en_l = extent_entry_next(en_l);
 360                 en_r = extent_entry_next(en_r);
 361         }
 362
 363         bch2_key_resize(l.k, l.k->size + r.k->size);
 364         return true;
 365 }
 366
 367 /* KEY_TYPE_reservation: */
 368
 369 int bch2_reservation_invalid(const struct bch_fs *c, struct bkey_s_c k,
 370                              int rw, struct printbuf *err)
 371 {
 372         struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k);
 373
 374         if (bkey_val_bytes(k.k) != sizeof(struct bch_reservation)) {
 375                 pr_buf(err, "incorrect value size (%zu != %zu)",
 376                        bkey_val_bytes(k.k), sizeof(*r.v));
 377                 return -EINVAL;
 378         }
 379
 380         if (!r.v->nr_replicas || r.v->nr_replicas > BCH_REPLICAS_MAX) {
 381                 pr_buf(err, "invalid nr_replicas (%u)",
 382                        r.v->nr_replicas);
 383                 return -EINVAL;
 384         }
 385
 386         return 0;
 387 }
 388
 389 void bch2_reservation_to_text(struct printbuf *out, struct bch_fs *c,
 390                               struct bkey_s_c k)
 391 {
 392         struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k);
 393
 394         pr_buf(out, "generation %u replicas %u",
 395                le32_to_cpu(r.v->generation),
 396                r.v->nr_replicas);
 397 }
 398
 399 bool bch2_reservation_merge(struct bch_fs *c, struct bkey_s _l, struct bkey_s_c _r)
 400 {
 401         struct bkey_s_reservation l = bkey_s_to_reservation(_l);
 402         struct bkey_s_c_reservation r = bkey_s_c_to_reservation(_r);
 403
 404         if (l.v->generation != r.v->generation ||
 405             l.v->nr_replicas != r.v->nr_replicas)
 406                 return false;
 407
 408         bch2_key_resize(l.k, l.k->size + r.k->size);
 409         return true;
 410 }
 411
 412 /* Extent checksum entries: */
 413
 414 /* returns true if not equal */
 415 static inline bool bch2_crc_unpacked_cmp(struct bch_extent_crc_unpacked l,
 416                                          struct bch_extent_crc_unpacked r)
 417 {
 418         return (l.csum_type             != r.csum_type ||
 419                 l.compression_type      != r.compression_type ||
 420                 l.compressed_size       != r.compressed_size ||
 421                 l.uncompressed_size     != r.uncompressed_size ||
 422                 l.offset                != r.offset ||
 423                 l.live_size             != r.live_size ||
 424                 l.nonce                 != r.nonce ||
 425                 bch2_crc_cmp(l.csum, r.csum));
 426 }
 427
 428 static inline bool can_narrow_crc(struct bch_extent_crc_unpacked u,
 429                                   struct bch_extent_crc_unpacked n)
 430 {
 431         return !crc_is_compressed(u) &&
 432                 u.csum_type &&
 433                 u.uncompressed_size > u.live_size &&
 434                 bch2_csum_type_is_encryption(u.csum_type) ==
 435                 bch2_csum_type_is_encryption(n.csum_type);
 436 }
 437
 438 bool bch2_can_narrow_extent_crcs(struct bkey_s_c k,
 439                                  struct bch_extent_crc_unpacked n)
 440 {
 441         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 442         struct bch_extent_crc_unpacked crc;
 443         const union bch_extent_entry *i;
 444
 445         if (!n.csum_type)
 446                 return false;
 447
 448         bkey_for_each_crc(k.k, ptrs, crc, i)
 449                 if (can_narrow_crc(crc, n))
 450                         return true;
 451
 452         return false;
 453 }
 454
 455 /*
 456  * We're writing another replica for this extent, so while we've got the data in
 457  * memory we'll be computing a new checksum for the currently live data.
 458  *
 459  * If there are other replicas we aren't moving, and they are checksummed but
 460  * not compressed, we can modify them to point to only the data that is
 461  * currently live (so that readers won't have to bounce) while we've got the
 462  * checksum we need:
 463  */
 464 bool bch2_bkey_narrow_crcs(struct bkey_i *k, struct bch_extent_crc_unpacked n)
 465 {
 466         struct bkey_ptrs ptrs = bch2_bkey_ptrs(bkey_i_to_s(k));
 467         struct bch_extent_crc_unpacked u;
 468         struct extent_ptr_decoded p;
 469         union bch_extent_entry *i;
 470         bool ret = false;
 471
 472         /* Find a checksum entry that covers only live data: */
 473         if (!n.csum_type) {
 474                 bkey_for_each_crc(&k->k, ptrs, u, i)
 475                         if (!crc_is_compressed(u) &&
 476                             u.csum_type &&
 477                             u.live_size == u.uncompressed_size) {
 478                                 n = u;
 479                                 goto found;
 480                         }
 481                 return false;
 482         }
 483 found:
 484         BUG_ON(crc_is_compressed(n));
 485         BUG_ON(n.offset);
 486         BUG_ON(n.live_size != k->k.size);
 487
 488 restart_narrow_pointers:
 489         ptrs = bch2_bkey_ptrs(bkey_i_to_s(k));
 490
 491         bkey_for_each_ptr_decode(&k->k, ptrs, p, i)
 492                 if (can_narrow_crc(p.crc, n)) {
 493                         __bch2_bkey_drop_ptr(bkey_i_to_s(k), &i->ptr);
 494                         p.ptr.offset += p.crc.offset;
 495                         p.crc = n;
 496                         bch2_extent_ptr_decoded_append(k, &p);
 497                         ret = true;
 498                         goto restart_narrow_pointers;
 499                 }
 500
 501         return ret;
 502 }
 503
 504 static void bch2_extent_crc_pack(union bch_extent_crc *dst,
 505                                  struct bch_extent_crc_unpacked src,
 506                                  enum bch_extent_entry_type type)
 507 {
 508 #define set_common_fields(_dst, _src)                                   \
 509                 _dst.type               = 1 << type;                    \
 510                 _dst.csum_type          = _src.csum_type,               \
 511                 _dst.compression_type   = _src.compression_type,        \
 512                 _dst._compressed_size   = _src.compressed_size - 1,     \
 513                 _dst._uncompressed_size = _src.uncompressed_size - 1,   \
 514                 _dst.offset             = _src.offset
 515
 516         switch (type) {
 517         case BCH_EXTENT_ENTRY_crc32:
 518                 set_common_fields(dst->crc32, src);
 519                 dst->crc32.csum  = *((__le32 *) &src.csum.lo);
 520                 break;
 521         case BCH_EXTENT_ENTRY_crc64:
 522                 set_common_fields(dst->crc64, src);
 523                 dst->crc64.nonce        = src.nonce;
 524                 dst->crc64.csum_lo      = src.csum.lo;
 525                 dst->crc64.csum_hi      = *((__le16 *) &src.csum.hi);
 526                 break;
 527         case BCH_EXTENT_ENTRY_crc128:
 528                 set_common_fields(dst->crc128, src);
 529                 dst->crc128.nonce       = src.nonce;
 530                 dst->crc128.csum        = src.csum;
 531                 break;
 532         default:
 533                 BUG();
 534         }
 535 #undef set_common_fields
 536 }
 537
 538 void bch2_extent_crc_append(struct bkey_i *k,
 539                             struct bch_extent_crc_unpacked new)
 540 {
 541         struct bkey_ptrs ptrs = bch2_bkey_ptrs(bkey_i_to_s(k));
 542         union bch_extent_crc *crc = (void *) ptrs.end;
 543         enum bch_extent_entry_type type;
 544
 545         if (bch_crc_bytes[new.csum_type]        <= 4 &&
 546             new.uncompressed_size               <= CRC32_SIZE_MAX &&
 547             new.nonce                           <= CRC32_NONCE_MAX)
 548                 type = BCH_EXTENT_ENTRY_crc32;
 549         else if (bch_crc_bytes[new.csum_type]   <= 10 &&
 550                    new.uncompressed_size        <= CRC64_SIZE_MAX &&
 551                    new.nonce                    <= CRC64_NONCE_MAX)
 552                 type = BCH_EXTENT_ENTRY_crc64;
 553         else if (bch_crc_bytes[new.csum_type]   <= 16 &&
 554                    new.uncompressed_size        <= CRC128_SIZE_MAX &&
 555                    new.nonce                    <= CRC128_NONCE_MAX)
 556                 type = BCH_EXTENT_ENTRY_crc128;
 557         else
 558                 BUG();
 559
 560         bch2_extent_crc_pack(crc, new, type);
 561
 562         k->k.u64s += extent_entry_u64s(ptrs.end);
 563
 564         EBUG_ON(bkey_val_u64s(&k->k) > BKEY_EXTENT_VAL_U64s_MAX);
 565 }
 566
 567 /* Generic code for keys with pointers: */
 568
 569 unsigned bch2_bkey_nr_ptrs(struct bkey_s_c k)
 570 {
 571         return bch2_bkey_devs(k).nr;
 572 }
 573
 574 unsigned bch2_bkey_nr_ptrs_allocated(struct bkey_s_c k)
 575 {
 576         return k.k->type == KEY_TYPE_reservation
 577                 ? bkey_s_c_to_reservation(k).v->nr_replicas
 578                 : bch2_bkey_dirty_devs(k).nr;
 579 }
 580
 581 unsigned bch2_bkey_nr_ptrs_fully_allocated(struct bkey_s_c k)
 582 {
 583         unsigned ret = 0;
 584
 585         if (k.k->type == KEY_TYPE_reservation) {
 586                 ret = bkey_s_c_to_reservation(k).v->nr_replicas;
 587         } else {
 588                 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 589                 const union bch_extent_entry *entry;
 590                 struct extent_ptr_decoded p;
 591
 592                 bkey_for_each_ptr_decode(k.k, ptrs, p, entry)
 593                         ret += !p.ptr.cached && !crc_is_compressed(p.crc);
 594         }
 595
 596         return ret;
 597 }
 598
 599 unsigned bch2_bkey_sectors_compressed(struct bkey_s_c k)
 600 {
 601         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 602         const union bch_extent_entry *entry;
 603         struct extent_ptr_decoded p;
 604         unsigned ret = 0;
 605
 606         bkey_for_each_ptr_decode(k.k, ptrs, p, entry)
 607                 if (!p.ptr.cached && crc_is_compressed(p.crc))
 608                         ret += p.crc.compressed_size;
 609
 610         return ret;
 611 }
 612
 613 bool bch2_bkey_is_incompressible(struct bkey_s_c k)
 614 {
 615         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 616         const union bch_extent_entry *entry;
 617         struct bch_extent_crc_unpacked crc;
 618
 619         bkey_for_each_crc(k.k, ptrs, crc, entry)
 620                 if (crc.compression_type == BCH_COMPRESSION_TYPE_incompressible)
 621                         return true;
 622         return false;
 623 }
 624
 625 unsigned bch2_bkey_replicas(struct bch_fs *c, struct bkey_s_c k)
 626 {
 627         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 628         const union bch_extent_entry *entry;
 629         struct extent_ptr_decoded p = { 0 };
 630         unsigned replicas = 0;
 631
 632         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
 633                 if (p.ptr.cached)
 634                         continue;
 635
 636                 if (p.has_ec)
 637                         replicas += p.ec.redundancy;
 638
 639                 replicas++;
 640
 641         }
 642
 643         return replicas;
 644 }
 645
 646 static unsigned bch2_extent_ptr_durability(struct bch_fs *c,
 647                                            struct extent_ptr_decoded p)
 648 {
 649         unsigned durability = 0;
 650         struct bch_dev *ca;
 651
 652         if (p.ptr.cached)
 653                 return 0;
 654
 655         ca = bch_dev_bkey_exists(c, p.ptr.dev);
 656
 657         if (ca->mi.state != BCH_MEMBER_STATE_failed)
 658                 durability = max_t(unsigned, durability, ca->mi.durability);
 659
 660         if (p.has_ec)
 661                 durability += p.ec.redundancy;
 662
 663         return durability;
 664 }
 665
 666 unsigned bch2_bkey_durability(struct bch_fs *c, struct bkey_s_c k)
 667 {
 668         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 669         const union bch_extent_entry *entry;
 670         struct extent_ptr_decoded p;
 671         unsigned durability = 0;
 672
 673         bkey_for_each_ptr_decode(k.k, ptrs, p, entry)
 674                 durability += bch2_extent_ptr_durability(c, p);
 675
 676         return durability;
 677 }
 678
 679 void bch2_bkey_mark_replicas_cached(struct bch_fs *c, struct bkey_s k,
 680                                     unsigned target,
 681                                     unsigned nr_desired_replicas)
 682 {
 683         struct bkey_ptrs ptrs = bch2_bkey_ptrs(k);
 684         union bch_extent_entry *entry;
 685         struct extent_ptr_decoded p;
 686         int extra = bch2_bkey_durability(c, k.s_c) - nr_desired_replicas;
 687
 688         if (target && extra > 0)
 689                 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
 690                         int n = bch2_extent_ptr_durability(c, p);
 691
 692                         if (n && n <= extra &&
 693                             !bch2_dev_in_target(c, p.ptr.dev, target)) {
 694                                 entry->ptr.cached = true;
 695                                 extra -= n;
 696                         }
 697                 }
 698
 699         if (extra > 0)
 700                 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
 701                         int n = bch2_extent_ptr_durability(c, p);
 702
 703                         if (n && n <= extra) {
 704                                 entry->ptr.cached = true;
 705                                 extra -= n;
 706                         }
 707                 }
 708 }
 709
 710 void bch2_bkey_extent_entry_drop(struct bkey_i *k, union bch_extent_entry *entry)
 711 {
 712         union bch_extent_entry *end = bkey_val_end(bkey_i_to_s(k));
 713         union bch_extent_entry *next = extent_entry_next(entry);
 714
 715         memmove_u64s(entry, next, (u64 *) end - (u64 *) next);
 716         k->k.u64s -= extent_entry_u64s(entry);
 717 }
 718
 719 void bch2_bkey_append_ptr(struct bkey_i *k,
 720                           struct bch_extent_ptr ptr)
 721 {
 722         EBUG_ON(bch2_bkey_has_device(bkey_i_to_s_c(k), ptr.dev));
 723
 724         switch (k->k.type) {
 725         case KEY_TYPE_btree_ptr:
 726         case KEY_TYPE_btree_ptr_v2:
 727         case KEY_TYPE_extent:
 728                 EBUG_ON(bkey_val_u64s(&k->k) >= BKEY_EXTENT_VAL_U64s_MAX);
 729
 730                 ptr.type = 1 << BCH_EXTENT_ENTRY_ptr;
 731
 732                 memcpy((void *) &k->v + bkey_val_bytes(&k->k),
 733                        &ptr,
 734                        sizeof(ptr));
 735                 k->u64s++;
 736                 break;
 737         default:
 738                 BUG();
 739         }
 740 }
 741
 742 static inline void __extent_entry_insert(struct bkey_i *k,
 743                                          union bch_extent_entry *dst,
 744                                          union bch_extent_entry *new)
 745 {
 746         union bch_extent_entry *end = bkey_val_end(bkey_i_to_s(k));
 747
 748         memmove_u64s_up_small((u64 *) dst + extent_entry_u64s(new),
 749                               dst, (u64 *) end - (u64 *) dst);
 750         k->k.u64s += extent_entry_u64s(new);
 751         memcpy(dst, new, extent_entry_bytes(new));
 752 }
 753
 754 void bch2_extent_ptr_decoded_append(struct bkey_i *k,
 755                                     struct extent_ptr_decoded *p)
 756 {
 757         struct bkey_ptrs ptrs = bch2_bkey_ptrs(bkey_i_to_s(k));
 758         struct bch_extent_crc_unpacked crc =
 759                 bch2_extent_crc_unpack(&k->k, NULL);
 760         union bch_extent_entry *pos;
 761
 762         if (!bch2_crc_unpacked_cmp(crc, p->crc)) {
 763                 pos = ptrs.start;
 764                 goto found;
 765         }
 766
 767         bkey_for_each_crc(&k->k, ptrs, crc, pos)
 768                 if (!bch2_crc_unpacked_cmp(crc, p->crc)) {
 769                         pos = extent_entry_next(pos);
 770                         goto found;
 771                 }
 772
 773         bch2_extent_crc_append(k, p->crc);
 774         pos = bkey_val_end(bkey_i_to_s(k));
 775 found:
 776         p->ptr.type = 1 << BCH_EXTENT_ENTRY_ptr;
 777         __extent_entry_insert(k, pos, to_entry(&p->ptr));
 778
 779         if (p->has_ec) {
 780                 p->ec.type = 1 << BCH_EXTENT_ENTRY_stripe_ptr;
 781                 __extent_entry_insert(k, pos, to_entry(&p->ec));
 782         }
 783 }
 784
 785 static union bch_extent_entry *extent_entry_prev(struct bkey_ptrs ptrs,
 786                                           union bch_extent_entry *entry)
 787 {
 788         union bch_extent_entry *i = ptrs.start;
 789
 790         if (i == entry)
 791                 return NULL;
 792
 793         while (extent_entry_next(i) != entry)
 794                 i = extent_entry_next(i);
 795         return i;
 796 }
 797
 798 static void extent_entry_drop(struct bkey_s k, union bch_extent_entry *entry)
 799 {
 800         union bch_extent_entry *next = extent_entry_next(entry);
 801
 802         /* stripes have ptrs, but their layout doesn't work with this code */
 803         BUG_ON(k.k->type == KEY_TYPE_stripe);
 804
 805         memmove_u64s_down(entry, next,
 806                           (u64 *) bkey_val_end(k) - (u64 *) next);
 807         k.k->u64s -= (u64 *) next - (u64 *) entry;
 808 }
 809
 810 /*
 811  * Returns pointer to the next entry after the one being dropped:
 812  */
 813 union bch_extent_entry *__bch2_bkey_drop_ptr(struct bkey_s k,
 814                                              struct bch_extent_ptr *ptr)
 815 {
 816         struct bkey_ptrs ptrs = bch2_bkey_ptrs(k);
 817         union bch_extent_entry *entry = to_entry(ptr), *next;
 818         union bch_extent_entry *ret = entry;
 819         bool drop_crc = true;
 820
 821         EBUG_ON(ptr < &ptrs.start->ptr ||
 822                 ptr >= &ptrs.end->ptr);
 823         EBUG_ON(ptr->type != 1 << BCH_EXTENT_ENTRY_ptr);
 824
 825         for (next = extent_entry_next(entry);
 826              next != ptrs.end;
 827              next = extent_entry_next(next)) {
 828                 if (extent_entry_is_crc(next)) {
 829                         break;
 830                 } else if (extent_entry_is_ptr(next)) {
 831                         drop_crc = false;
 832                         break;
 833                 }
 834         }
 835
 836         extent_entry_drop(k, entry);
 837
 838         while ((entry = extent_entry_prev(ptrs, entry))) {
 839                 if (extent_entry_is_ptr(entry))
 840                         break;
 841
 842                 if ((extent_entry_is_crc(entry) && drop_crc) ||
 843                     extent_entry_is_stripe_ptr(entry)) {
 844                         ret = (void *) ret - extent_entry_bytes(entry);
 845                         extent_entry_drop(k, entry);
 846                 }
 847         }
 848
 849         return ret;
 850 }
 851
 852 union bch_extent_entry *bch2_bkey_drop_ptr(struct bkey_s k,
 853                                            struct bch_extent_ptr *ptr)
 854 {
 855         bool have_dirty = bch2_bkey_dirty_devs(k.s_c).nr;
 856         union bch_extent_entry *ret =
 857                 __bch2_bkey_drop_ptr(k, ptr);
 858
 859         /*
 860          * If we deleted all the dirty pointers and there's still cached
 861          * pointers, we could set the cached pointers to dirty if they're not
 862          * stale - but to do that correctly we'd need to grab an open_bucket
 863          * reference so that we don't race with bucket reuse:
 864          */
 865         if (have_dirty &&
 866             !bch2_bkey_dirty_devs(k.s_c).nr) {
 867                 k.k->type = KEY_TYPE_error;
 868                 set_bkey_val_u64s(k.k, 0);
 869                 ret = NULL;
 870         } else if (!bch2_bkey_nr_ptrs(k.s_c)) {
 871                 k.k->type = KEY_TYPE_deleted;
 872                 set_bkey_val_u64s(k.k, 0);
 873                 ret = NULL;
 874         }
 875
 876         return ret;
 877 }
 878
 879 void bch2_bkey_drop_device(struct bkey_s k, unsigned dev)
 880 {
 881         struct bch_extent_ptr *ptr;
 882
 883         bch2_bkey_drop_ptrs(k, ptr, ptr->dev == dev);
 884 }
 885
 886 const struct bch_extent_ptr *
 887 bch2_bkey_has_device(struct bkey_s_c k, unsigned dev)
 888 {
 889         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 890         const struct bch_extent_ptr *ptr;
 891
 892         bkey_for_each_ptr(ptrs, ptr)
 893                 if (ptr->dev == dev)
 894                         return ptr;
 895
 896         return NULL;
 897 }
 898
 899 bool bch2_bkey_has_target(struct bch_fs *c, struct bkey_s_c k, unsigned target)
 900 {
 901         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 902         const struct bch_extent_ptr *ptr;
 903
 904         bkey_for_each_ptr(ptrs, ptr)
 905                 if (bch2_dev_in_target(c, ptr->dev, target) &&
 906                     (!ptr->cached ||
 907                      !ptr_stale(bch_dev_bkey_exists(c, ptr->dev), ptr)))
 908                         return true;
 909
 910         return false;
 911 }
 912
 913 bool bch2_bkey_matches_ptr(struct bch_fs *c, struct bkey_s_c k,
 914                            struct bch_extent_ptr m, u64 offset)
 915 {
 916         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 917         const union bch_extent_entry *entry;
 918         struct extent_ptr_decoded p;
 919
 920         bkey_for_each_ptr_decode(k.k, ptrs, p, entry)
 921                 if (p.ptr.dev   == m.dev &&
 922                     p.ptr.gen   == m.gen &&
 923                     (s64) p.ptr.offset + p.crc.offset - bkey_start_offset(k.k) ==
 924                     (s64) m.offset  - offset)
 925                         return true;
 926
 927         return false;
 928 }
 929
 930 /*
 931  * bch_extent_normalize - clean up an extent, dropping stale pointers etc.
 932  *
 933  * Returns true if @k should be dropped entirely
 934  *
 935  * For existing keys, only called when btree nodes are being rewritten, not when
 936  * they're merely being compacted/resorted in memory.
 937  */
 938 bool bch2_extent_normalize(struct bch_fs *c, struct bkey_s k)
 939 {
 940         struct bch_extent_ptr *ptr;
 941
 942         bch2_bkey_drop_ptrs(k, ptr,
 943                 ptr->cached &&
 944                 ptr_stale(bch_dev_bkey_exists(c, ptr->dev), ptr));
 945
 946         return bkey_deleted(k.k);
 947 }
 948
 949 void bch2_bkey_ptrs_to_text(struct printbuf *out, struct bch_fs *c,
 950                             struct bkey_s_c k)
 951 {
 952         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 953         const union bch_extent_entry *entry;
 954         struct bch_extent_crc_unpacked crc;
 955         const struct bch_extent_ptr *ptr;
 956         const struct bch_extent_stripe_ptr *ec;
 957         struct bch_dev *ca;
 958         bool first = true;
 959
 960         bkey_extent_entry_for_each(ptrs, entry) {
 961                 if (!first)
 962                         pr_buf(out, " ");
 963
 964                 switch (__extent_entry_type(entry)) {
 965                 case BCH_EXTENT_ENTRY_ptr:
 966                         ptr = entry_to_ptr(entry);
 967                         ca = c && ptr->dev < c->sb.nr_devices && c->devs[ptr->dev]
 968                                 ? bch_dev_bkey_exists(c, ptr->dev)
 969                                 : NULL;
 970
 971                         if (!ca) {
 972                                 pr_buf(out, "ptr: %u:%llu gen %u%s", ptr->dev,
 973                                        (u64) ptr->offset, ptr->gen,
 974                                        ptr->cached ? " cached" : "");
 975                         } else {
 976                                 u32 offset;
 977                                 u64 b = sector_to_bucket_and_offset(ca, ptr->offset, &offset);
 978
 979                                 pr_buf(out, "ptr: %u:%llu:%u gen %u%s", ptr->dev,
 980                                        b, offset, ptr->gen,
 981                                        ptr->cached ? " cached" : "");
 982
 983                                 if (ca && ptr_stale(ca, ptr))
 984                                         pr_buf(out, " stale");
 985                         }
 986                         break;
 987                 case BCH_EXTENT_ENTRY_crc32:
 988                 case BCH_EXTENT_ENTRY_crc64:
 989                 case BCH_EXTENT_ENTRY_crc128:
 990                         crc = bch2_extent_crc_unpack(k.k, entry_to_crc(entry));
 991
 992                         pr_buf(out, "crc: c_size %u size %u offset %u nonce %u csum %s compress %s",
 993                                crc.compressed_size,
 994                                crc.uncompressed_size,
 995                                crc.offset, crc.nonce,
 996                                bch2_csum_types[crc.csum_type],
 997                                bch2_compression_types[crc.compression_type]);
 998                         break;
 999                 case BCH_EXTENT_ENTRY_stripe_ptr:
1000                         ec = &entry->stripe_ptr;
1001
1002                         pr_buf(out, "ec: idx %llu block %u",
1003                                (u64) ec->idx, ec->block);
1004                         break;
1005                 default:
1006                         pr_buf(out, "(invalid extent entry %.16llx)", *((u64 *) entry));
1007                         return;
1008                 }
1009
1010                 first = false;
1011         }
1012 }
1013
1014 static int extent_ptr_invalid(const struct bch_fs *c,
1015                               struct bkey_s_c k,
1016                               const struct bch_extent_ptr *ptr,
1017                               unsigned size_ondisk,
1018                               bool metadata,
1019                               struct printbuf *err)
1020 {
1021         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
1022         const struct bch_extent_ptr *ptr2;
1023         u64 bucket;
1024         u32 bucket_offset;
1025         struct bch_dev *ca;
1026
1027         if (!bch2_dev_exists2(c, ptr->dev)) {
1028                 pr_buf(err, "pointer to invalid device (%u)", ptr->dev);
1029                 return -EINVAL;
1030         }
1031
1032         ca = bch_dev_bkey_exists(c, ptr->dev);
1033         bkey_for_each_ptr(ptrs, ptr2)
1034                 if (ptr != ptr2 && ptr->dev == ptr2->dev) {
1035                         pr_buf(err, "multiple pointers to same device (%u)", ptr->dev);
1036                         return -EINVAL;
1037                 }
1038
1039         bucket = sector_to_bucket_and_offset(ca, ptr->offset, &bucket_offset);
1040
1041         if (bucket >= ca->mi.nbuckets) {
1042                 pr_buf(err, "pointer past last bucket (%llu > %llu)",
1043                        bucket, ca->mi.nbuckets);
1044                 return -EINVAL;
1045         }
1046
1047         if (ptr->offset < bucket_to_sector(ca, ca->mi.first_bucket)) {
1048                 pr_buf(err, "pointer before first bucket (%llu < %u)",
1049                        bucket, ca->mi.first_bucket);
1050                 return -EINVAL;
1051         }
1052
1053         if (bucket_offset + size_ondisk > ca->mi.bucket_size) {
1054                 pr_buf(err, "pointer spans multiple buckets (%u + %u > %u)",
1055                        bucket_offset, size_ondisk, ca->mi.bucket_size);
1056                 return -EINVAL;
1057         }
1058
1059         return 0;
1060 }
1061
1062 int bch2_bkey_ptrs_invalid(const struct bch_fs *c, struct bkey_s_c k,
1063                            int rw, struct printbuf *err)
1064 {
1065         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
1066         const union bch_extent_entry *entry;
1067         struct bch_extent_crc_unpacked crc;
1068         unsigned size_ondisk = k.k->size;
1069         unsigned nonce = UINT_MAX;
1070         int ret;
1071
1072         if (bkey_is_btree_ptr(k.k))
1073                 size_ondisk = btree_sectors(c);
1074
1075         bkey_extent_entry_for_each(ptrs, entry) {
1076                 if (__extent_entry_type(entry) >= BCH_EXTENT_ENTRY_MAX) {
1077                         pr_buf(err, "invalid extent entry type (got %u, max %u)",
1078                                __extent_entry_type(entry), BCH_EXTENT_ENTRY_MAX);
1079                         return -EINVAL;
1080                 }
1081
1082                 if (bkey_is_btree_ptr(k.k) &&
1083                     !extent_entry_is_ptr(entry)) {
1084                         pr_buf(err, "has non ptr field");
1085                         return -EINVAL;
1086                 }
1087
1088                 switch (extent_entry_type(entry)) {
1089                 case BCH_EXTENT_ENTRY_ptr:
1090                         ret = extent_ptr_invalid(c, k, &entry->ptr, size_ondisk,
1091                                                  false, err);
1092                         if (ret)
1093                                 return ret;
1094                         break;
1095                 case BCH_EXTENT_ENTRY_crc32:
1096                 case BCH_EXTENT_ENTRY_crc64:
1097                 case BCH_EXTENT_ENTRY_crc128:
1098                         crc = bch2_extent_crc_unpack(k.k, entry_to_crc(entry));
1099
1100                         if (crc.offset + crc.live_size >
1101                             crc.uncompressed_size) {
1102                                 pr_buf(err, "checksum offset + key size > uncompressed size");
1103                                 return -EINVAL;
1104                         }
1105
1106                         size_ondisk = crc.compressed_size;
1107
1108                         if (!bch2_checksum_type_valid(c, crc.csum_type)) {
1109                                 pr_buf(err, "invalid checksum type");
1110                                 return -EINVAL;
1111                         }
1112
1113                         if (crc.compression_type >= BCH_COMPRESSION_TYPE_NR) {
1114                                 pr_buf(err, "invalid compression type");
1115                                 return -EINVAL;
1116                         }
1117
1118                         if (bch2_csum_type_is_encryption(crc.csum_type)) {
1119                                 if (nonce == UINT_MAX)
1120                                         nonce = crc.offset + crc.nonce;
1121                                 else if (nonce != crc.offset + crc.nonce) {
1122                                         pr_buf(err, "incorrect nonce");
1123                                         return -EINVAL;
1124                                 }
1125                         }
1126                         break;
1127                 case BCH_EXTENT_ENTRY_stripe_ptr:
1128                         break;
1129                 }
1130         }
1131
1132         return 0;
1133 }
1134
1135 void bch2_ptr_swab(struct bkey_s k)
1136 {
1137         struct bkey_ptrs ptrs = bch2_bkey_ptrs(k);
1138         union bch_extent_entry *entry;
1139         u64 *d;
1140
1141         for (d =  (u64 *) ptrs.start;
1142              d != (u64 *) ptrs.end;
1143              d++)
1144                 *d = swab64(*d);
1145
1146         for (entry = ptrs.start;
1147              entry < ptrs.end;
1148              entry = extent_entry_next(entry)) {
1149                 switch (extent_entry_type(entry)) {
1150                 case BCH_EXTENT_ENTRY_ptr:
1151                         break;
1152                 case BCH_EXTENT_ENTRY_crc32:
1153                         entry->crc32.csum = swab32(entry->crc32.csum);
1154                         break;
1155                 case BCH_EXTENT_ENTRY_crc64:
1156                         entry->crc64.csum_hi = swab16(entry->crc64.csum_hi);
1157                         entry->crc64.csum_lo = swab64(entry->crc64.csum_lo);
1158                         break;
1159                 case BCH_EXTENT_ENTRY_crc128:
1160                         entry->crc128.csum.hi = (__force __le64)
1161                                 swab64((__force u64) entry->crc128.csum.hi);
1162                         entry->crc128.csum.lo = (__force __le64)
1163                                 swab64((__force u64) entry->crc128.csum.lo);
1164                         break;
1165                 case BCH_EXTENT_ENTRY_stripe_ptr:
1166                         break;
1167                 }
1168         }
1169 }
1170
1171 /* Generic extent code: */
1172
1173 int bch2_cut_front_s(struct bpos where, struct bkey_s k)
1174 {
1175         unsigned new_val_u64s = bkey_val_u64s(k.k);
1176         int val_u64s_delta;
1177         u64 sub;
1178
1179         if (bkey_cmp(where, bkey_start_pos(k.k)) <= 0)
1180                 return 0;
1181
1182         EBUG_ON(bkey_cmp(where, k.k->p) > 0);
1183
1184         sub = where.offset - bkey_start_offset(k.k);
1185
1186         k.k->size -= sub;
1187
1188         if (!k.k->size) {
1189                 k.k->type = KEY_TYPE_deleted;
1190                 new_val_u64s = 0;
1191         }
1192
1193         switch (k.k->type) {
1194         case KEY_TYPE_extent:
1195         case KEY_TYPE_reflink_v: {
1196                 struct bkey_ptrs ptrs = bch2_bkey_ptrs(k);
1197                 union bch_extent_entry *entry;
1198                 bool seen_crc = false;
1199
1200                 bkey_extent_entry_for_each(ptrs, entry) {
1201                         switch (extent_entry_type(entry)) {
1202                         case BCH_EXTENT_ENTRY_ptr:
1203                                 if (!seen_crc)
1204                                         entry->ptr.offset += sub;
1205                                 break;
1206                         case BCH_EXTENT_ENTRY_crc32:
1207                                 entry->crc32.offset += sub;
1208                                 break;
1209                         case BCH_EXTENT_ENTRY_crc64:
1210                                 entry->crc64.offset += sub;
1211                                 break;
1212                         case BCH_EXTENT_ENTRY_crc128:
1213                                 entry->crc128.offset += sub;
1214                                 break;
1215                         case BCH_EXTENT_ENTRY_stripe_ptr:
1216                                 break;
1217                         }
1218
1219                         if (extent_entry_is_crc(entry))
1220                                 seen_crc = true;
1221                 }
1222
1223                 break;
1224         }
1225         case KEY_TYPE_reflink_p: {
1226                 struct bkey_s_reflink_p p = bkey_s_to_reflink_p(k);
1227
1228                 le64_add_cpu(&p.v->idx, sub);
1229                 break;
1230         }
1231         case KEY_TYPE_inline_data:
1232         case KEY_TYPE_indirect_inline_data: {
1233                 void *p = bkey_inline_data_p(k);
1234                 unsigned bytes = bkey_inline_data_bytes(k.k);
1235
1236                 sub = min_t(u64, sub << 9, bytes);
1237
1238                 memmove(p, p + sub, bytes - sub);
1239
1240                 new_val_u64s -= sub >> 3;
1241                 break;
1242         }
1243         }
1244
1245         val_u64s_delta = bkey_val_u64s(k.k) - new_val_u64s;
1246         BUG_ON(val_u64s_delta < 0);
1247
1248         set_bkey_val_u64s(k.k, new_val_u64s);
1249         memset(bkey_val_end(k), 0, val_u64s_delta * sizeof(u64));
1250         return -val_u64s_delta;
1251 }
1252
1253 int bch2_cut_back_s(struct bpos where, struct bkey_s k)
1254 {
1255         unsigned new_val_u64s = bkey_val_u64s(k.k);
1256         int val_u64s_delta;
1257         u64 len = 0;
1258
1259         if (bkey_cmp(where, k.k->p) >= 0)
1260                 return 0;
1261
1262         EBUG_ON(bkey_cmp(where, bkey_start_pos(k.k)) < 0);
1263
1264         len = where.offset - bkey_start_offset(k.k);
1265
1266         k.k->p.offset = where.offset;
1267         k.k->size = len;
1268
1269         if (!len) {
1270                 k.k->type = KEY_TYPE_deleted;
1271                 new_val_u64s = 0;
1272         }
1273
1274         switch (k.k->type) {
1275         case KEY_TYPE_inline_data:
1276         case KEY_TYPE_indirect_inline_data:
1277                 new_val_u64s = (bkey_inline_data_offset(k.k) +
1278                                 min(bkey_inline_data_bytes(k.k), k.k->size << 9)) >> 3;
1279                 break;
1280         }
1281
1282         val_u64s_delta = bkey_val_u64s(k.k) - new_val_u64s;
1283         BUG_ON(val_u64s_delta < 0);
1284
1285         set_bkey_val_u64s(k.k, new_val_u64s);
1286         memset(bkey_val_end(k), 0, val_u64s_delta * sizeof(u64));
1287         return -val_u64s_delta;
1288 }