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

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Code for manipulating bucket marks for garbage collection.
   4  *
   5  * Copyright 2014 Datera, Inc.
   6  */
   7
   8 #include "bcachefs.h"
   9 #include "alloc_background.h"
  10 #include "bset.h"
  11 #include "btree_gc.h"
  12 #include "btree_update.h"
  13 #include "buckets.h"
  14 #include "ec.h"
  15 #include "error.h"
  16 #include "movinggc.h"
  17 #include "recovery.h"
  18 #include "reflink.h"
  19 #include "replicas.h"
  20 #include "subvolume.h"
  21
  22 #include <linux/preempt.h>
  23 #include <trace/events/bcachefs.h>
  24
  25 static inline void fs_usage_data_type_to_base(struct bch_fs_usage *fs_usage,
  26                                               enum bch_data_type data_type,
  27                                               s64 sectors)
  28 {
  29         switch (data_type) {
  30         case BCH_DATA_btree:
  31                 fs_usage->btree         += sectors;
  32                 break;
  33         case BCH_DATA_user:
  34         case BCH_DATA_parity:
  35                 fs_usage->data          += sectors;
  36                 break;
  37         case BCH_DATA_cached:
  38                 fs_usage->cached        += sectors;
  39                 break;
  40         default:
  41                 break;
  42         }
  43 }
  44
  45 /*
  46  * Clear journal_seq_valid for buckets for which it's not needed, to prevent
  47  * wraparound:
  48  */
  49 void bch2_bucket_seq_cleanup(struct bch_fs *c)
  50 {
  51         u64 journal_seq = atomic64_read(&c->journal.seq);
  52         u16 last_seq_ondisk = c->journal.last_seq_ondisk;
  53         struct bch_dev *ca;
  54         struct bucket_array *buckets;
  55         struct bucket *g;
  56         struct bucket_mark m;
  57         unsigned i;
  58
  59         if (journal_seq - c->last_bucket_seq_cleanup <
  60             (1U << (BUCKET_JOURNAL_SEQ_BITS - 2)))
  61                 return;
  62
  63         c->last_bucket_seq_cleanup = journal_seq;
  64
  65         for_each_member_device(ca, c, i) {
  66                 down_read(&ca->bucket_lock);
  67                 buckets = bucket_array(ca);
  68
  69                 for_each_bucket(g, buckets) {
  70                         bucket_cmpxchg(g, m, ({
  71                                 if (!m.journal_seq_valid ||
  72                                     bucket_needs_journal_commit(m, last_seq_ondisk))
  73                                         break;
  74
  75                                 m.journal_seq_valid = 0;
  76                         }));
  77                 }
  78                 up_read(&ca->bucket_lock);
  79         }
  80 }
  81
  82 void bch2_fs_usage_initialize(struct bch_fs *c)
  83 {
  84         struct bch_fs_usage *usage;
  85         struct bch_dev *ca;
  86         unsigned i;
  87
  88         percpu_down_write(&c->mark_lock);
  89         usage = c->usage_base;
  90
  91         for (i = 0; i < ARRAY_SIZE(c->usage); i++)
  92                 bch2_fs_usage_acc_to_base(c, i);
  93
  94         for (i = 0; i < BCH_REPLICAS_MAX; i++)
  95                 usage->reserved += usage->persistent_reserved[i];
  96
  97         for (i = 0; i < c->replicas.nr; i++) {
  98                 struct bch_replicas_entry *e =
  99                         cpu_replicas_entry(&c->replicas, i);
 100
 101                 fs_usage_data_type_to_base(usage, e->data_type, usage->replicas[i]);
 102         }
 103
 104         for_each_member_device(ca, c, i) {
 105                 struct bch_dev_usage dev = bch2_dev_usage_read(ca);
 106
 107                 usage->hidden += (dev.d[BCH_DATA_sb].buckets +
 108                                   dev.d[BCH_DATA_journal].buckets) *
 109                         ca->mi.bucket_size;
 110         }
 111
 112         percpu_up_write(&c->mark_lock);
 113 }
 114
 115 static inline struct bch_dev_usage *dev_usage_ptr(struct bch_dev *ca,
 116                                                   unsigned journal_seq,
 117                                                   bool gc)
 118 {
 119         return this_cpu_ptr(gc
 120                             ? ca->usage_gc
 121                             : ca->usage[journal_seq & JOURNAL_BUF_MASK]);
 122 }
 123
 124 struct bch_dev_usage bch2_dev_usage_read(struct bch_dev *ca)
 125 {
 126         struct bch_fs *c = ca->fs;
 127         struct bch_dev_usage ret;
 128         unsigned seq, i, u64s = dev_usage_u64s();
 129
 130         do {
 131                 seq = read_seqcount_begin(&c->usage_lock);
 132                 memcpy(&ret, ca->usage_base, u64s * sizeof(u64));
 133                 for (i = 0; i < ARRAY_SIZE(ca->usage); i++)
 134                         acc_u64s_percpu((u64 *) &ret, (u64 __percpu *) ca->usage[i], u64s);
 135         } while (read_seqcount_retry(&c->usage_lock, seq));
 136
 137         return ret;
 138 }
 139
 140 static inline struct bch_fs_usage *fs_usage_ptr(struct bch_fs *c,
 141                                                 unsigned journal_seq,
 142                                                 bool gc)
 143 {
 144         return this_cpu_ptr(gc
 145                             ? c->usage_gc
 146                             : c->usage[journal_seq & JOURNAL_BUF_MASK]);
 147 }
 148
 149 u64 bch2_fs_usage_read_one(struct bch_fs *c, u64 *v)
 150 {
 151         ssize_t offset = v - (u64 *) c->usage_base;
 152         unsigned i, seq;
 153         u64 ret;
 154
 155         BUG_ON(offset < 0 || offset >= fs_usage_u64s(c));
 156         percpu_rwsem_assert_held(&c->mark_lock);
 157
 158         do {
 159                 seq = read_seqcount_begin(&c->usage_lock);
 160                 ret = *v;
 161
 162                 for (i = 0; i < ARRAY_SIZE(c->usage); i++)
 163                         ret += percpu_u64_get((u64 __percpu *) c->usage[i] + offset);
 164         } while (read_seqcount_retry(&c->usage_lock, seq));
 165
 166         return ret;
 167 }
 168
 169 struct bch_fs_usage_online *bch2_fs_usage_read(struct bch_fs *c)
 170 {
 171         struct bch_fs_usage_online *ret;
 172         unsigned seq, i, u64s;
 173
 174         percpu_down_read(&c->mark_lock);
 175
 176         ret = kmalloc(sizeof(struct bch_fs_usage_online) +
 177                       sizeof(u64) * c->replicas.nr, GFP_NOFS);
 178         if (unlikely(!ret)) {
 179                 percpu_up_read(&c->mark_lock);
 180                 return NULL;
 181         }
 182
 183         ret->online_reserved = percpu_u64_get(c->online_reserved);
 184
 185         u64s = fs_usage_u64s(c);
 186         do {
 187                 seq = read_seqcount_begin(&c->usage_lock);
 188                 memcpy(&ret->u, c->usage_base, u64s * sizeof(u64));
 189                 for (i = 0; i < ARRAY_SIZE(c->usage); i++)
 190                         acc_u64s_percpu((u64 *) &ret->u, (u64 __percpu *) c->usage[i], u64s);
 191         } while (read_seqcount_retry(&c->usage_lock, seq));
 192
 193         return ret;
 194 }
 195
 196 void bch2_fs_usage_acc_to_base(struct bch_fs *c, unsigned idx)
 197 {
 198         struct bch_dev *ca;
 199         unsigned i, u64s = fs_usage_u64s(c);
 200
 201         BUG_ON(idx >= ARRAY_SIZE(c->usage));
 202
 203         preempt_disable();
 204         write_seqcount_begin(&c->usage_lock);
 205
 206         acc_u64s_percpu((u64 *) c->usage_base,
 207                         (u64 __percpu *) c->usage[idx], u64s);
 208         percpu_memset(c->usage[idx], 0, u64s * sizeof(u64));
 209
 210         rcu_read_lock();
 211         for_each_member_device_rcu(ca, c, i, NULL) {
 212                 u64s = dev_usage_u64s();
 213
 214                 acc_u64s_percpu((u64 *) ca->usage_base,
 215                                 (u64 __percpu *) ca->usage[idx], u64s);
 216                 percpu_memset(ca->usage[idx], 0, u64s * sizeof(u64));
 217         }
 218         rcu_read_unlock();
 219
 220         write_seqcount_end(&c->usage_lock);
 221         preempt_enable();
 222 }
 223
 224 void bch2_fs_usage_to_text(struct printbuf *out,
 225                            struct bch_fs *c,
 226                            struct bch_fs_usage_online *fs_usage)
 227 {
 228         unsigned i;
 229
 230         pr_buf(out, "capacity:\t\t\t%llu\n", c->capacity);
 231
 232         pr_buf(out, "hidden:\t\t\t\t%llu\n",
 233                fs_usage->u.hidden);
 234         pr_buf(out, "data:\t\t\t\t%llu\n",
 235                fs_usage->u.data);
 236         pr_buf(out, "cached:\t\t\t\t%llu\n",
 237                fs_usage->u.cached);
 238         pr_buf(out, "reserved:\t\t\t%llu\n",
 239                fs_usage->u.reserved);
 240         pr_buf(out, "nr_inodes:\t\t\t%llu\n",
 241                fs_usage->u.nr_inodes);
 242         pr_buf(out, "online reserved:\t\t%llu\n",
 243                fs_usage->online_reserved);
 244
 245         for (i = 0;
 246              i < ARRAY_SIZE(fs_usage->u.persistent_reserved);
 247              i++) {
 248                 pr_buf(out, "%u replicas:\n", i + 1);
 249                 pr_buf(out, "\treserved:\t\t%llu\n",
 250                        fs_usage->u.persistent_reserved[i]);
 251         }
 252
 253         for (i = 0; i < c->replicas.nr; i++) {
 254                 struct bch_replicas_entry *e =
 255                         cpu_replicas_entry(&c->replicas, i);
 256
 257                 pr_buf(out, "\t");
 258                 bch2_replicas_entry_to_text(out, e);
 259                 pr_buf(out, ":\t%llu\n", fs_usage->u.replicas[i]);
 260         }
 261 }
 262
 263 static u64 reserve_factor(u64 r)
 264 {
 265         return r + (round_up(r, (1 << RESERVE_FACTOR)) >> RESERVE_FACTOR);
 266 }
 267
 268 u64 bch2_fs_sectors_used(struct bch_fs *c, struct bch_fs_usage_online *fs_usage)
 269 {
 270         return min(fs_usage->u.hidden +
 271                    fs_usage->u.btree +
 272                    fs_usage->u.data +
 273                    reserve_factor(fs_usage->u.reserved +
 274                                   fs_usage->online_reserved),
 275                    c->capacity);
 276 }
 277
 278 static struct bch_fs_usage_short
 279 __bch2_fs_usage_read_short(struct bch_fs *c)
 280 {
 281         struct bch_fs_usage_short ret;
 282         u64 data, reserved;
 283
 284         ret.capacity = c->capacity -
 285                 bch2_fs_usage_read_one(c, &c->usage_base->hidden);
 286
 287         data            = bch2_fs_usage_read_one(c, &c->usage_base->data) +
 288                 bch2_fs_usage_read_one(c, &c->usage_base->btree);
 289         reserved        = bch2_fs_usage_read_one(c, &c->usage_base->reserved) +
 290                 percpu_u64_get(c->online_reserved);
 291
 292         ret.used        = min(ret.capacity, data + reserve_factor(reserved));
 293         ret.free        = ret.capacity - ret.used;
 294
 295         ret.nr_inodes   = bch2_fs_usage_read_one(c, &c->usage_base->nr_inodes);
 296
 297         return ret;
 298 }
 299
 300 struct bch_fs_usage_short
 301 bch2_fs_usage_read_short(struct bch_fs *c)
 302 {
 303         struct bch_fs_usage_short ret;
 304
 305         percpu_down_read(&c->mark_lock);
 306         ret = __bch2_fs_usage_read_short(c);
 307         percpu_up_read(&c->mark_lock);
 308
 309         return ret;
 310 }
 311
 312 static inline int is_unavailable_bucket(struct bucket_mark m)
 313 {
 314         return !is_available_bucket(m);
 315 }
 316
 317 static inline int bucket_sectors_fragmented(struct bch_dev *ca,
 318                                             struct bucket_mark m)
 319 {
 320         return bucket_sectors_used(m)
 321                 ? max(0, (int) ca->mi.bucket_size - (int) bucket_sectors_used(m))
 322                 : 0;
 323 }
 324
 325 static inline int is_stripe_data_bucket(struct bucket_mark m)
 326 {
 327         return m.stripe && m.data_type != BCH_DATA_parity;
 328 }
 329
 330 static inline enum bch_data_type bucket_type(struct bucket_mark m)
 331 {
 332         return m.cached_sectors && !m.dirty_sectors
 333                 ? BCH_DATA_cached
 334                 : m.data_type;
 335 }
 336
 337 static bool bucket_became_unavailable(struct bucket_mark old,
 338                                       struct bucket_mark new)
 339 {
 340         return is_available_bucket(old) &&
 341                !is_available_bucket(new);
 342 }
 343
 344 static inline void account_bucket(struct bch_fs_usage *fs_usage,
 345                                   struct bch_dev_usage *dev_usage,
 346                                   enum bch_data_type type,
 347                                   int nr, s64 size)
 348 {
 349         if (type == BCH_DATA_sb || type == BCH_DATA_journal)
 350                 fs_usage->hidden        += size;
 351
 352         dev_usage->d[type].buckets      += nr;
 353 }
 354
 355 static void bch2_dev_usage_update(struct bch_fs *c, struct bch_dev *ca,
 356                                   struct bucket_mark old, struct bucket_mark new,
 357                                   u64 journal_seq, bool gc)
 358 {
 359         struct bch_fs_usage *fs_usage;
 360         struct bch_dev_usage *u;
 361
 362         percpu_rwsem_assert_held(&c->mark_lock);
 363
 364         preempt_disable();
 365         fs_usage = fs_usage_ptr(c, journal_seq, gc);
 366         u = dev_usage_ptr(ca, journal_seq, gc);
 367
 368         if (bucket_type(old))
 369                 account_bucket(fs_usage, u, bucket_type(old),
 370                                -1, -ca->mi.bucket_size);
 371
 372         if (bucket_type(new))
 373                 account_bucket(fs_usage, u, bucket_type(new),
 374                                1, ca->mi.bucket_size);
 375
 376         u->buckets_ec += (int) new.stripe - (int) old.stripe;
 377         u->buckets_unavailable +=
 378                 is_unavailable_bucket(new) - is_unavailable_bucket(old);
 379
 380         u->d[old.data_type].sectors -= old.dirty_sectors;
 381         u->d[new.data_type].sectors += new.dirty_sectors;
 382         u->d[BCH_DATA_cached].sectors +=
 383                 (int) new.cached_sectors - (int) old.cached_sectors;
 384
 385         u->d[old.data_type].fragmented -= bucket_sectors_fragmented(ca, old);
 386         u->d[new.data_type].fragmented += bucket_sectors_fragmented(ca, new);
 387
 388         preempt_enable();
 389
 390         if (!is_available_bucket(old) && is_available_bucket(new))
 391                 bch2_wake_allocator(ca);
 392 }
 393
 394 static inline int __update_replicas(struct bch_fs *c,
 395                                     struct bch_fs_usage *fs_usage,
 396                                     struct bch_replicas_entry *r,
 397                                     s64 sectors)
 398 {
 399         int idx = bch2_replicas_entry_idx(c, r);
 400
 401         if (idx < 0)
 402                 return -1;
 403
 404         fs_usage_data_type_to_base(fs_usage, r->data_type, sectors);
 405         fs_usage->replicas[idx]         += sectors;
 406         return 0;
 407 }
 408
 409 static inline int update_replicas(struct bch_fs *c,
 410                         struct bch_replicas_entry *r, s64 sectors,
 411                         unsigned journal_seq, bool gc)
 412 {
 413         struct bch_fs_usage __percpu *fs_usage;
 414         int idx = bch2_replicas_entry_idx(c, r);
 415
 416         if (idx < 0)
 417                 return -1;
 418
 419         preempt_disable();
 420         fs_usage = fs_usage_ptr(c, journal_seq, gc);
 421         fs_usage_data_type_to_base(fs_usage, r->data_type, sectors);
 422         fs_usage->replicas[idx]         += sectors;
 423         preempt_enable();
 424         return 0;
 425 }
 426
 427 static inline int update_cached_sectors(struct bch_fs *c,
 428                         unsigned dev, s64 sectors,
 429                         unsigned journal_seq, bool gc)
 430 {
 431         struct bch_replicas_padded r;
 432
 433         bch2_replicas_entry_cached(&r.e, dev);
 434
 435         return update_replicas(c, &r.e, sectors, journal_seq, gc);
 436 }
 437
 438 static struct replicas_delta_list *
 439 replicas_deltas_realloc(struct btree_trans *trans, unsigned more)
 440 {
 441         struct replicas_delta_list *d = trans->fs_usage_deltas;
 442         unsigned new_size = d ? (d->size + more) * 2 : 128;
 443         unsigned alloc_size = sizeof(*d) + new_size;
 444
 445         WARN_ON_ONCE(alloc_size > REPLICAS_DELTA_LIST_MAX);
 446
 447         if (!d || d->used + more > d->size) {
 448                 d = krealloc(d, alloc_size, GFP_NOIO|__GFP_ZERO);
 449
 450                 BUG_ON(!d && alloc_size > REPLICAS_DELTA_LIST_MAX);
 451
 452                 if (!d) {
 453                         d = mempool_alloc(&trans->c->replicas_delta_pool, GFP_NOIO);
 454                         memset(d, 0, REPLICAS_DELTA_LIST_MAX);
 455
 456                         if (trans->fs_usage_deltas)
 457                                 memcpy(d, trans->fs_usage_deltas,
 458                                        trans->fs_usage_deltas->size + sizeof(*d));
 459
 460                         new_size = REPLICAS_DELTA_LIST_MAX - sizeof(*d);
 461                         kfree(trans->fs_usage_deltas);
 462                 }
 463
 464                 d->size = new_size;
 465                 trans->fs_usage_deltas = d;
 466         }
 467         return d;
 468 }
 469
 470 static inline void update_replicas_list(struct btree_trans *trans,
 471                                         struct bch_replicas_entry *r,
 472                                         s64 sectors)
 473 {
 474         struct replicas_delta_list *d;
 475         struct replicas_delta *n;
 476         unsigned b;
 477
 478         if (!sectors)
 479                 return;
 480
 481         b = replicas_entry_bytes(r) + 8;
 482         d = replicas_deltas_realloc(trans, b);
 483
 484         n = (void *) d->d + d->used;
 485         n->delta = sectors;
 486         memcpy(&n->r, r, replicas_entry_bytes(r));
 487         bch2_replicas_entry_sort(&n->r);
 488         d->used += b;
 489 }
 490
 491 static inline void update_cached_sectors_list(struct btree_trans *trans,
 492                                               unsigned dev, s64 sectors)
 493 {
 494         struct bch_replicas_padded r;
 495
 496         bch2_replicas_entry_cached(&r.e, dev);
 497
 498         update_replicas_list(trans, &r.e, sectors);
 499 }
 500
 501 #define do_mark_fn(fn, c, pos, flags, ...)                              \
 502 ({                                                                      \
 503         int gc, ret = 0;                                                \
 504                                                                         \
 505         percpu_rwsem_assert_held(&c->mark_lock);                        \
 506                                                                         \
 507         for (gc = 0; gc < 2 && !ret; gc++)                              \
 508                 if (!gc == !(flags & BTREE_TRIGGER_GC) ||               \
 509                     (gc && gc_visited(c, pos)))                         \
 510                         ret = fn(c, __VA_ARGS__, gc);                   \
 511         ret;                                                            \
 512 })
 513
 514 void bch2_mark_alloc_bucket(struct bch_fs *c, struct bch_dev *ca,
 515                             size_t b, bool owned_by_allocator)
 516 {
 517         struct bucket *g = bucket(ca, b);
 518         struct bucket_mark old, new;
 519
 520         old = bucket_cmpxchg(g, new, ({
 521                 new.owned_by_allocator  = owned_by_allocator;
 522         }));
 523
 524         BUG_ON(owned_by_allocator == old.owned_by_allocator);
 525 }
 526
 527 static int bch2_mark_alloc(struct bch_fs *c,
 528                            struct bkey_s_c old, struct bkey_s_c new,
 529                            u64 journal_seq, unsigned flags)
 530 {
 531         bool gc = flags & BTREE_TRIGGER_GC;
 532         struct bkey_alloc_unpacked u;
 533         struct bch_dev *ca;
 534         struct bucket *g;
 535         struct bucket_mark old_m, m;
 536
 537         /* We don't do anything for deletions - do we?: */
 538         if (new.k->type != KEY_TYPE_alloc &&
 539             new.k->type != KEY_TYPE_alloc_v2)
 540                 return 0;
 541
 542         /*
 543          * alloc btree is read in by bch2_alloc_read, not gc:
 544          */
 545         if ((flags & BTREE_TRIGGER_GC) &&
 546             !(flags & BTREE_TRIGGER_BUCKET_INVALIDATE))
 547                 return 0;
 548
 549         ca = bch_dev_bkey_exists(c, new.k->p.inode);
 550
 551         if (new.k->p.offset >= ca->mi.nbuckets)
 552                 return 0;
 553
 554         g = __bucket(ca, new.k->p.offset, gc);
 555         u = bch2_alloc_unpack(new);
 556
 557         old_m = bucket_cmpxchg(g, m, ({
 558                 m.gen                   = u.gen;
 559                 m.data_type             = u.data_type;
 560                 m.dirty_sectors         = u.dirty_sectors;
 561                 m.cached_sectors        = u.cached_sectors;
 562                 m.stripe                = u.stripe != 0;
 563
 564                 if (journal_seq) {
 565                         m.journal_seq_valid     = 1;
 566                         m.journal_seq           = journal_seq;
 567                 }
 568         }));
 569
 570         bch2_dev_usage_update(c, ca, old_m, m, journal_seq, gc);
 571
 572         g->io_time[READ]        = u.read_time;
 573         g->io_time[WRITE]       = u.write_time;
 574         g->oldest_gen           = u.oldest_gen;
 575         g->gen_valid            = 1;
 576         g->stripe               = u.stripe;
 577         g->stripe_redundancy    = u.stripe_redundancy;
 578
 579         /*
 580          * need to know if we're getting called from the invalidate path or
 581          * not:
 582          */
 583
 584         if ((flags & BTREE_TRIGGER_BUCKET_INVALIDATE) &&
 585             old_m.cached_sectors) {
 586                 if (update_cached_sectors(c, ca->dev_idx, -old_m.cached_sectors,
 587                                           journal_seq, gc)) {
 588                         bch2_fs_fatal_error(c, "bch2_mark_alloc(): no replicas entry while updating cached sectors");
 589                         return -1;
 590                 }
 591
 592                 trace_invalidate(ca, bucket_to_sector(ca, new.k->p.offset),
 593                                  old_m.cached_sectors);
 594         }
 595
 596         return 0;
 597 }
 598
 599 #define checked_add(a, b)                                       \
 600 ({                                                              \
 601         unsigned _res = (unsigned) (a) + (b);                   \
 602         bool overflow = _res > U16_MAX;                         \
 603         if (overflow)                                           \
 604                 _res = U16_MAX;                                 \
 605         (a) = _res;                                             \
 606         overflow;                                               \
 607 })
 608
 609 static int __bch2_mark_metadata_bucket(struct bch_fs *c, struct bch_dev *ca,
 610                                        size_t b, enum bch_data_type data_type,
 611                                        unsigned sectors, bool gc)
 612 {
 613         struct bucket *g = __bucket(ca, b, gc);
 614         struct bucket_mark old, new;
 615         bool overflow;
 616
 617         BUG_ON(data_type != BCH_DATA_sb &&
 618                data_type != BCH_DATA_journal);
 619
 620         old = bucket_cmpxchg(g, new, ({
 621                 new.data_type   = data_type;
 622                 overflow = checked_add(new.dirty_sectors, sectors);
 623         }));
 624
 625         bch2_fs_inconsistent_on(old.data_type &&
 626                                 old.data_type != data_type, c,
 627                 "different types of data in same bucket: %s, %s",
 628                 bch2_data_types[old.data_type],
 629                 bch2_data_types[data_type]);
 630
 631         bch2_fs_inconsistent_on(overflow, c,
 632                 "bucket %u:%zu gen %u data type %s sector count overflow: %u + %u > U16_MAX",
 633                 ca->dev_idx, b, new.gen,
 634                 bch2_data_types[old.data_type ?: data_type],
 635                 old.dirty_sectors, sectors);
 636
 637         if (c)
 638                 bch2_dev_usage_update(c, ca, old, new, 0, gc);
 639
 640         return 0;
 641 }
 642
 643 void bch2_mark_metadata_bucket(struct bch_fs *c, struct bch_dev *ca,
 644                                size_t b, enum bch_data_type type,
 645                                unsigned sectors, struct gc_pos pos,
 646                                unsigned flags)
 647 {
 648         BUG_ON(type != BCH_DATA_sb &&
 649                type != BCH_DATA_journal);
 650
 651         /*
 652          * Backup superblock might be past the end of our normal usable space:
 653          */
 654         if (b >= ca->mi.nbuckets)
 655                 return;
 656
 657         if (likely(c)) {
 658                 do_mark_fn(__bch2_mark_metadata_bucket, c, pos, flags,
 659                            ca, b, type, sectors);
 660         } else {
 661                 __bch2_mark_metadata_bucket(c, ca, b, type, sectors, 0);
 662         }
 663 }
 664
 665 static s64 ptr_disk_sectors(s64 sectors, struct extent_ptr_decoded p)
 666 {
 667         EBUG_ON(sectors < 0);
 668
 669         return p.crc.compression_type &&
 670                 p.crc.compression_type != BCH_COMPRESSION_TYPE_incompressible
 671                 ? DIV_ROUND_UP_ULL(sectors * p.crc.compressed_size,
 672                                p.crc.uncompressed_size)
 673                 : sectors;
 674 }
 675
 676 static int check_bucket_ref(struct bch_fs *c, struct bkey_s_c k,
 677                             const struct bch_extent_ptr *ptr,
 678                             s64 sectors, enum bch_data_type ptr_data_type,
 679                             u8 bucket_gen, u8 bucket_data_type,
 680                             u16 dirty_sectors, u16 cached_sectors)
 681 {
 682         size_t bucket_nr = PTR_BUCKET_NR(bch_dev_bkey_exists(c, ptr->dev), ptr);
 683         u16 bucket_sectors = !ptr->cached
 684                 ? dirty_sectors
 685                 : cached_sectors;
 686         char buf[200];
 687
 688         if (gen_after(ptr->gen, bucket_gen)) {
 689                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
 690                         "bucket %u:%zu gen %u data type %s: ptr gen %u newer than bucket gen\n"
 691                         "while marking %s",
 692                         ptr->dev, bucket_nr, bucket_gen,
 693                         bch2_data_types[bucket_data_type ?: ptr_data_type],
 694                         ptr->gen,
 695                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 696                 return -EIO;
 697         }
 698
 699         if (gen_cmp(bucket_gen, ptr->gen) > BUCKET_GC_GEN_MAX) {
 700                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
 701                         "bucket %u:%zu gen %u data type %s: ptr gen %u too stale\n"
 702                         "while marking %s",
 703                         ptr->dev, bucket_nr, bucket_gen,
 704                         bch2_data_types[bucket_data_type ?: ptr_data_type],
 705                         ptr->gen,
 706                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 707                 return -EIO;
 708         }
 709
 710         if (bucket_gen != ptr->gen && !ptr->cached) {
 711                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
 712                         "bucket %u:%zu gen %u data type %s: stale dirty ptr (gen %u)\n"
 713                         "while marking %s",
 714                         ptr->dev, bucket_nr, bucket_gen,
 715                         bch2_data_types[bucket_data_type ?: ptr_data_type],
 716                         ptr->gen,
 717                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 718                 return -EIO;
 719         }
 720
 721         if (bucket_gen != ptr->gen)
 722                 return 1;
 723
 724         if (bucket_data_type && ptr_data_type &&
 725             bucket_data_type != ptr_data_type) {
 726                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
 727                         "bucket %u:%zu gen %u different types of data in same bucket: %s, %s\n"
 728                         "while marking %s",
 729                         ptr->dev, bucket_nr, bucket_gen,
 730                         bch2_data_types[bucket_data_type],
 731                         bch2_data_types[ptr_data_type],
 732                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 733                 return -EIO;
 734         }
 735
 736         if ((unsigned) (bucket_sectors + sectors) > U16_MAX) {
 737                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
 738                         "bucket %u:%zu gen %u data type %s sector count overflow: %u + %lli > U16_MAX\n"
 739                         "while marking %s",
 740                         ptr->dev, bucket_nr, bucket_gen,
 741                         bch2_data_types[bucket_data_type ?: ptr_data_type],
 742                         bucket_sectors, sectors,
 743                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 744                 return -EIO;
 745         }
 746
 747         return 0;
 748 }
 749
 750 static int mark_stripe_bucket(struct bch_fs *c, struct bkey_s_c k,
 751                              unsigned ptr_idx,
 752                              u64 journal_seq, unsigned flags)
 753 {
 754         const struct bch_stripe *s = bkey_s_c_to_stripe(k).v;
 755         unsigned nr_data = s->nr_blocks - s->nr_redundant;
 756         bool parity = ptr_idx >= nr_data;
 757         const struct bch_extent_ptr *ptr = s->ptrs + ptr_idx;
 758         bool gc = flags & BTREE_TRIGGER_GC;
 759         struct bch_dev *ca = bch_dev_bkey_exists(c, ptr->dev);
 760         struct bucket *g = PTR_BUCKET(ca, ptr, gc);
 761         struct bucket_mark new, old;
 762         char buf[200];
 763         int ret;
 764
 765         if (g->stripe && g->stripe != k.k->p.offset) {
 766                 bch2_fs_inconsistent(c,
 767                               "bucket %u:%zu gen %u: multiple stripes using same bucket\n%s",
 768                               ptr->dev, PTR_BUCKET_NR(ca, ptr), g->mark.gen,
 769                               (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf));
 770                 return -EINVAL;
 771         }
 772
 773         old = bucket_cmpxchg(g, new, ({
 774                 ret = check_bucket_ref(c, k, ptr, 0, 0, new.gen, new.data_type,
 775                                        new.dirty_sectors, new.cached_sectors);
 776                 if (ret)
 777                         return ret;
 778
 779                 if (parity) {
 780                         new.data_type           = BCH_DATA_parity;
 781                         new.dirty_sectors       = le16_to_cpu(s->sectors);
 782                 }
 783
 784                 if (journal_seq) {
 785                         new.journal_seq_valid   = 1;
 786                         new.journal_seq         = journal_seq;
 787                 }
 788         }));
 789
 790         g->stripe               = k.k->p.offset;
 791         g->stripe_redundancy    = s->nr_redundant;
 792
 793         bch2_dev_usage_update(c, ca, old, new, journal_seq, gc);
 794         return 0;
 795 }
 796
 797 static int __mark_pointer(struct bch_fs *c, struct bkey_s_c k,
 798                           const struct bch_extent_ptr *ptr,
 799                           s64 sectors, enum bch_data_type ptr_data_type,
 800                           u8 bucket_gen, u8 *bucket_data_type,
 801                           u16 *dirty_sectors, u16 *cached_sectors)
 802 {
 803         u16 *dst_sectors = !ptr->cached
 804                 ? dirty_sectors
 805                 : cached_sectors;
 806         int ret = check_bucket_ref(c, k, ptr, sectors, ptr_data_type,
 807                                    bucket_gen, *bucket_data_type,
 808                                    *dirty_sectors, *cached_sectors);
 809
 810         if (ret)
 811                 return ret;
 812
 813         *dst_sectors += sectors;
 814         *bucket_data_type = *dirty_sectors || *cached_sectors
 815                 ? ptr_data_type : 0;
 816         return 0;
 817 }
 818
 819 static int bch2_mark_pointer(struct bch_fs *c, struct bkey_s_c k,
 820                              struct extent_ptr_decoded p,
 821                              s64 sectors, enum bch_data_type data_type,
 822                              u64 journal_seq, unsigned flags)
 823 {
 824         bool gc = flags & BTREE_TRIGGER_GC;
 825         struct bucket_mark old, new;
 826         struct bch_dev *ca = bch_dev_bkey_exists(c, p.ptr.dev);
 827         struct bucket *g = PTR_BUCKET(ca, &p.ptr, gc);
 828         u8 bucket_data_type;
 829         u64 v;
 830         int ret;
 831
 832         v = atomic64_read(&g->_mark.v);
 833         do {
 834                 new.v.counter = old.v.counter = v;
 835                 bucket_data_type = new.data_type;
 836
 837                 ret = __mark_pointer(c, k, &p.ptr, sectors, data_type, new.gen,
 838                                      &bucket_data_type,
 839                                      &new.dirty_sectors,
 840                                      &new.cached_sectors);
 841                 if (ret)
 842                         return ret;
 843
 844                 new.data_type = bucket_data_type;
 845
 846                 if (journal_seq) {
 847                         new.journal_seq_valid = 1;
 848                         new.journal_seq = journal_seq;
 849                 }
 850
 851                 if (flags & BTREE_TRIGGER_NOATOMIC) {
 852                         g->_mark = new;
 853                         break;
 854                 }
 855         } while ((v = atomic64_cmpxchg(&g->_mark.v,
 856                               old.v.counter,
 857                               new.v.counter)) != old.v.counter);
 858
 859         bch2_dev_usage_update(c, ca, old, new, journal_seq, gc);
 860
 861         BUG_ON(!gc && bucket_became_unavailable(old, new));
 862
 863         return 0;
 864 }
 865
 866 static int bch2_mark_stripe_ptr(struct bch_fs *c,
 867                                 struct bch_extent_stripe_ptr p,
 868                                 enum bch_data_type data_type,
 869                                 s64 sectors,
 870                                 unsigned journal_seq, unsigned flags)
 871 {
 872         bool gc = flags & BTREE_TRIGGER_GC;
 873         struct bch_replicas_padded r;
 874         struct stripe *m;
 875         unsigned i, blocks_nonempty = 0;
 876
 877         m = genradix_ptr(&c->stripes[gc], p.idx);
 878
 879         spin_lock(&c->ec_stripes_heap_lock);
 880
 881         if (!m || !m->alive) {
 882                 spin_unlock(&c->ec_stripes_heap_lock);
 883                 bch_err_ratelimited(c, "pointer to nonexistent stripe %llu",
 884                                     (u64) p.idx);
 885                 bch2_inconsistent_error(c);
 886                 return -EIO;
 887         }
 888
 889         m->block_sectors[p.block] += sectors;
 890
 891         r = m->r;
 892
 893         for (i = 0; i < m->nr_blocks; i++)
 894                 blocks_nonempty += m->block_sectors[i] != 0;
 895
 896         if (m->blocks_nonempty != blocks_nonempty) {
 897                 m->blocks_nonempty = blocks_nonempty;
 898                 if (!gc)
 899                         bch2_stripes_heap_update(c, m, p.idx);
 900         }
 901
 902         spin_unlock(&c->ec_stripes_heap_lock);
 903
 904         r.e.data_type = data_type;
 905         update_replicas(c, &r.e, sectors, journal_seq, gc);
 906
 907         return 0;
 908 }
 909
 910 static int bch2_mark_extent(struct bch_fs *c,
 911                             struct bkey_s_c old, struct bkey_s_c new,
 912                             unsigned journal_seq, unsigned flags)
 913 {
 914         bool gc = flags & BTREE_TRIGGER_GC;
 915         struct bkey_s_c k = flags & BTREE_TRIGGER_INSERT ? new : old;
 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         struct bch_replicas_padded r;
 920         enum bch_data_type data_type = bkey_is_btree_ptr(k.k)
 921                 ? BCH_DATA_btree
 922                 : BCH_DATA_user;
 923         s64 sectors = bkey_is_btree_ptr(k.k)
 924                 ? c->opts.btree_node_size
 925                 : k.k->size;
 926         s64 dirty_sectors = 0;
 927         bool stale;
 928         int ret;
 929
 930         BUG_ON((flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)) ==
 931                (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE));
 932
 933         r.e.data_type   = data_type;
 934         r.e.nr_devs     = 0;
 935         r.e.nr_required = 1;
 936
 937         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
 938                 s64 disk_sectors = ptr_disk_sectors(sectors, p);
 939
 940                 if (flags & BTREE_TRIGGER_OVERWRITE)
 941                         disk_sectors = -disk_sectors;
 942
 943                 ret = bch2_mark_pointer(c, k, p, disk_sectors, data_type,
 944                                         journal_seq, flags);
 945                 if (ret < 0)
 946                         return ret;
 947
 948                 stale = ret > 0;
 949
 950                 if (p.ptr.cached) {
 951                         if (!stale)
 952                                 if (update_cached_sectors(c, p.ptr.dev, disk_sectors,
 953                                                           journal_seq, gc)) {
 954                                         bch2_fs_fatal_error(c, "bch2_mark_extent(): no replicas entry while updating cached sectors");
 955                                         return -1;
 956
 957                                 }
 958                 } else if (!p.has_ec) {
 959                         dirty_sectors          += disk_sectors;
 960                         r.e.devs[r.e.nr_devs++] = p.ptr.dev;
 961                 } else {
 962                         ret = bch2_mark_stripe_ptr(c, p.ec, data_type,
 963                                         disk_sectors, journal_seq, flags);
 964                         if (ret)
 965                                 return ret;
 966
 967                         /*
 968                          * There may be other dirty pointers in this extent, but
 969                          * if so they're not required for mounting if we have an
 970                          * erasure coded pointer in this extent:
 971                          */
 972                         r.e.nr_required = 0;
 973                 }
 974         }
 975
 976         if (r.e.nr_devs) {
 977                 if (update_replicas(c, &r.e, dirty_sectors, journal_seq, gc)) {
 978                         char buf[200];
 979
 980                         bch2_bkey_val_to_text(&PBUF(buf), c, k);
 981                         bch2_fs_fatal_error(c, "no replicas entry for %s", buf);
 982                         return -1;
 983                 }
 984         }
 985
 986         return 0;
 987 }
 988
 989 static int bch2_mark_stripe(struct bch_fs *c,
 990                         struct bkey_s_c old, struct bkey_s_c new,
 991                         u64 journal_seq, unsigned flags)
 992 {
 993         bool gc = flags & BTREE_TRIGGER_GC;
 994         size_t idx = new.k->p.offset;
 995         const struct bch_stripe *old_s = old.k->type == KEY_TYPE_stripe
 996                 ? bkey_s_c_to_stripe(old).v : NULL;
 997         const struct bch_stripe *new_s = new.k->type == KEY_TYPE_stripe
 998                 ? bkey_s_c_to_stripe(new).v : NULL;
 999         struct stripe *m = genradix_ptr(&c->stripes[gc], idx);
1000         unsigned i;
1001         int ret;
1002
1003         BUG_ON(gc && old_s);
1004
1005         if (!m || (old_s && !m->alive)) {
1006                 bch_err_ratelimited(c, "error marking nonexistent stripe %zu",
1007                                     idx);
1008                 bch2_inconsistent_error(c);
1009                 return -1;
1010         }
1011
1012         if (!new_s) {
1013                 spin_lock(&c->ec_stripes_heap_lock);
1014                 bch2_stripes_heap_del(c, m, idx);
1015                 spin_unlock(&c->ec_stripes_heap_lock);
1016
1017                 memset(m, 0, sizeof(*m));
1018         } else {
1019                 m->alive        = true;
1020                 m->sectors      = le16_to_cpu(new_s->sectors);
1021                 m->algorithm    = new_s->algorithm;
1022                 m->nr_blocks    = new_s->nr_blocks;
1023                 m->nr_redundant = new_s->nr_redundant;
1024                 m->blocks_nonempty = 0;
1025
1026                 for (i = 0; i < new_s->nr_blocks; i++) {
1027                         m->block_sectors[i] =
1028                                 stripe_blockcount_get(new_s, i);
1029                         m->blocks_nonempty += !!m->block_sectors[i];
1030
1031                         m->ptrs[i] = new_s->ptrs[i];
1032                 }
1033
1034                 bch2_bkey_to_replicas(&m->r.e, new);
1035
1036                 if (!gc) {
1037                         spin_lock(&c->ec_stripes_heap_lock);
1038                         bch2_stripes_heap_update(c, m, idx);
1039                         spin_unlock(&c->ec_stripes_heap_lock);
1040                 }
1041         }
1042
1043         if (gc) {
1044                 /*
1045                  * gc recalculates this field from stripe ptr
1046                  * references:
1047                  */
1048                 memset(m->block_sectors, 0, sizeof(m->block_sectors));
1049                 m->blocks_nonempty = 0;
1050
1051                 for (i = 0; i < new_s->nr_blocks; i++) {
1052                         ret = mark_stripe_bucket(c, new, i, journal_seq, flags);
1053                         if (ret)
1054                                 return ret;
1055                 }
1056
1057                 if (update_replicas(c, &m->r.e,
1058                                     ((s64) m->sectors * m->nr_redundant),
1059                                     journal_seq, gc)) {
1060                         char buf[200];
1061
1062                         bch2_bkey_val_to_text(&PBUF(buf), c, new);
1063                         bch2_fs_fatal_error(c, "no replicas entry for %s", buf);
1064                         return -1;
1065                 }
1066         }
1067
1068         return 0;
1069 }
1070
1071 static int bch2_mark_inode(struct bch_fs *c,
1072                         struct bkey_s_c old, struct bkey_s_c new,
1073                         u64 journal_seq, unsigned flags)
1074 {
1075         struct bch_fs_usage __percpu *fs_usage;
1076
1077         preempt_disable();
1078         fs_usage = fs_usage_ptr(c, journal_seq, flags & BTREE_TRIGGER_GC);
1079         fs_usage->nr_inodes += new.k->type == KEY_TYPE_inode;
1080         fs_usage->nr_inodes -= old.k->type == KEY_TYPE_inode;
1081         preempt_enable();
1082         return 0;
1083 }
1084
1085 static int bch2_mark_reservation(struct bch_fs *c,
1086                         struct bkey_s_c old, struct bkey_s_c new,
1087                         u64 journal_seq, unsigned flags)
1088 {
1089         struct bkey_s_c k = flags & BTREE_TRIGGER_INSERT ? new : old;
1090         struct bch_fs_usage __percpu *fs_usage;
1091         unsigned replicas = bkey_s_c_to_reservation(k).v->nr_replicas;
1092         s64 sectors = (s64) k.k->size;
1093
1094         if (flags & BTREE_TRIGGER_OVERWRITE)
1095                 sectors = -sectors;
1096         sectors *= replicas;
1097
1098         preempt_disable();
1099         fs_usage = fs_usage_ptr(c, journal_seq, flags & BTREE_TRIGGER_GC);
1100         replicas = clamp_t(unsigned, replicas, 1,
1101                            ARRAY_SIZE(fs_usage->persistent_reserved));
1102
1103         fs_usage->reserved                              += sectors;
1104         fs_usage->persistent_reserved[replicas - 1]     += sectors;
1105         preempt_enable();
1106
1107         return 0;
1108 }
1109
1110 static s64 __bch2_mark_reflink_p(struct bch_fs *c, struct bkey_s_c_reflink_p p,
1111                                  u64 idx, unsigned flags, size_t *r_idx)
1112 {
1113         struct reflink_gc *r;
1114         int add = !(flags & BTREE_TRIGGER_OVERWRITE) ? 1 : -1;
1115         s64 ret = 0;
1116
1117         while (*r_idx < c->reflink_gc_nr) {
1118                 r = genradix_ptr(&c->reflink_gc_table, *r_idx);
1119                 BUG_ON(!r);
1120
1121                 if (idx < r->offset)
1122                         break;
1123                 (*r_idx)++;
1124         }
1125
1126         if (*r_idx >= c->reflink_gc_nr ||
1127             idx < r->offset - r->size) {
1128                 ret = p.k->size;
1129                 goto not_found;
1130         }
1131
1132         BUG_ON((s64) r->refcount + add < 0);
1133
1134         r->refcount += add;
1135         return r->offset - idx;
1136 not_found:
1137         if ((flags & BTREE_TRIGGER_GC) &&
1138             (flags & BTREE_TRIGGER_NOATOMIC)) {
1139                 /*
1140                  * XXX: we're replacing the entire reflink pointer with an error
1141                  * key, we should just be replacing the part that was missing:
1142                  */
1143                 if (fsck_err(c, "%llu:%llu len %u points to nonexistent indirect extent %llu",
1144                              p.k->p.inode, p.k->p.offset, p.k->size, idx)) {
1145                         struct bkey_i_error *new;
1146
1147                         new = kmalloc(sizeof(*new), GFP_KERNEL);
1148                         if (!new) {
1149                                 bch_err(c, "%s: error allocating new key", __func__);
1150                                 return -ENOMEM;
1151                         }
1152
1153                         bkey_init(&new->k);
1154                         new->k.type     = KEY_TYPE_error;
1155                         new->k.p        = p.k->p;
1156                         new->k.size     = p.k->size;
1157                         ret = bch2_journal_key_insert(c, BTREE_ID_extents, 0, &new->k_i);
1158
1159                 }
1160         } else {
1161                 bch2_fs_inconsistent(c,
1162                                      "%llu:%llu len %u points to nonexistent indirect extent %llu",
1163                                      p.k->p.inode, p.k->p.offset, p.k->size, idx);
1164                 bch2_inconsistent_error(c);
1165                 ret = -EIO;
1166         }
1167 fsck_err:
1168         return ret;
1169 }
1170
1171 static int bch2_mark_reflink_p(struct bch_fs *c,
1172                         struct bkey_s_c old, struct bkey_s_c new,
1173                         u64 journal_seq, unsigned flags)
1174 {
1175         struct bkey_s_c k = flags & BTREE_TRIGGER_INSERT ? new : old;
1176         struct bkey_s_c_reflink_p p = bkey_s_c_to_reflink_p(k);
1177         struct reflink_gc *ref;
1178         size_t l, r, m;
1179         u64 idx = le64_to_cpu(p.v->idx);
1180         unsigned sectors = p.k->size;
1181         s64 ret = 0;
1182
1183         BUG_ON((flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)) ==
1184                (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE));
1185
1186         l = 0;
1187         r = c->reflink_gc_nr;
1188         while (l < r) {
1189                 m = l + (r - l) / 2;
1190
1191                 ref = genradix_ptr(&c->reflink_gc_table, m);
1192                 if (ref->offset <= idx)
1193                         l = m + 1;
1194                 else
1195                         r = m;
1196         }
1197
1198         while (sectors) {
1199                 ret = __bch2_mark_reflink_p(c, p, idx, flags, &l);
1200                 if (ret <= 0)
1201                         return ret;
1202
1203                 ret = min_t(s64, ret, sectors);
1204                 idx     += ret;
1205                 sectors -= ret;
1206         }
1207
1208         return 0;
1209 }
1210
1211 static int bch2_mark_key_locked(struct bch_fs *c,
1212                    struct bkey_s_c old,
1213                    struct bkey_s_c new,
1214                    u64 journal_seq, unsigned flags)
1215 {
1216         struct bkey_s_c k = flags & BTREE_TRIGGER_INSERT ? new : old;
1217
1218         BUG_ON(!(flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)));
1219
1220         switch (k.k->type) {
1221         case KEY_TYPE_alloc:
1222         case KEY_TYPE_alloc_v2:
1223                 return bch2_mark_alloc(c, old, new, journal_seq, flags);
1224         case KEY_TYPE_btree_ptr:
1225         case KEY_TYPE_btree_ptr_v2:
1226         case KEY_TYPE_extent:
1227         case KEY_TYPE_reflink_v:
1228                 return bch2_mark_extent(c, old, new, journal_seq, flags);
1229         case KEY_TYPE_stripe:
1230                 return bch2_mark_stripe(c, old, new, journal_seq, flags);
1231         case KEY_TYPE_inode:
1232                 return bch2_mark_inode(c, old, new, journal_seq, flags);
1233         case KEY_TYPE_reservation:
1234                 return bch2_mark_reservation(c, old, new, journal_seq, flags);
1235         case KEY_TYPE_reflink_p:
1236                 return bch2_mark_reflink_p(c, old, new, journal_seq, flags);
1237         case KEY_TYPE_snapshot:
1238                 return bch2_mark_snapshot(c, old, new, journal_seq, flags);
1239         default:
1240                 return 0;
1241         }
1242 }
1243
1244 int bch2_mark_key(struct bch_fs *c, struct bkey_s_c new, unsigned flags)
1245 {
1246         struct bkey deleted = KEY(0, 0, 0);
1247         struct bkey_s_c old = (struct bkey_s_c) { &deleted, NULL };
1248         int ret;
1249
1250         percpu_down_read(&c->mark_lock);
1251         ret = bch2_mark_key_locked(c, old, new, 0, flags);
1252         percpu_up_read(&c->mark_lock);
1253
1254         return ret;
1255 }
1256
1257 int bch2_mark_update(struct btree_trans *trans, struct btree_path *path,
1258                      struct bkey_i *new, unsigned flags)
1259 {
1260         struct bch_fs           *c = trans->c;
1261         struct bkey             _deleted = KEY(0, 0, 0);
1262         struct bkey_s_c         deleted = (struct bkey_s_c) { &_deleted, NULL };
1263         struct bkey_s_c         old;
1264         struct bkey             unpacked;
1265         int ret;
1266
1267         if (unlikely(flags & BTREE_TRIGGER_NORUN))
1268                 return 0;
1269
1270         if (!btree_node_type_needs_gc(path->btree_id))
1271                 return 0;
1272
1273         old = bch2_btree_path_peek_slot(path, &unpacked);
1274
1275         if (old.k->type == new->k.type &&
1276             ((1U << old.k->type) & BTREE_TRIGGER_WANTS_OLD_AND_NEW)) {
1277                 ret   = bch2_mark_key_locked(c, old, bkey_i_to_s_c(new),
1278                                 trans->journal_res.seq,
1279                                 BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE|flags);
1280         } else {
1281                 ret   = bch2_mark_key_locked(c, deleted, bkey_i_to_s_c(new),
1282                                 trans->journal_res.seq,
1283                                 BTREE_TRIGGER_INSERT|flags) ?:
1284                         bch2_mark_key_locked(c, old, deleted,
1285                                 trans->journal_res.seq,
1286                                 BTREE_TRIGGER_OVERWRITE|flags);
1287         }
1288
1289         return ret;
1290 }
1291
1292 static noinline __cold
1293 void fs_usage_apply_warn(struct btree_trans *trans,
1294                          unsigned disk_res_sectors,
1295                          s64 should_not_have_added)
1296 {
1297         struct bch_fs *c = trans->c;
1298         struct btree_insert_entry *i;
1299         char buf[200];
1300
1301         bch_err(c, "disk usage increased %lli more than %u sectors reserved",
1302                 should_not_have_added, disk_res_sectors);
1303
1304         trans_for_each_update(trans, i) {
1305                 pr_err("while inserting");
1306                 bch2_bkey_val_to_text(&PBUF(buf), c, bkey_i_to_s_c(i->k));
1307                 pr_err("%s", buf);
1308                 pr_err("overlapping with");
1309
1310                 if (!i->cached) {
1311                         struct bkey u;
1312                         struct bkey_s_c k = bch2_btree_path_peek_slot(i->path, &u);
1313
1314                         bch2_bkey_val_to_text(&PBUF(buf), c, k);
1315                         pr_err("%s", buf);
1316                 } else {
1317                         struct bkey_cached *ck = (void *) i->path->l[0].b;
1318
1319                         if (ck->valid) {
1320                                 bch2_bkey_val_to_text(&PBUF(buf), c, bkey_i_to_s_c(ck->k));
1321                                 pr_err("%s", buf);
1322                         }
1323                 }
1324         }
1325         __WARN();
1326 }
1327
1328 void bch2_trans_fs_usage_apply(struct btree_trans *trans,
1329                                struct replicas_delta_list *deltas)
1330 {
1331         struct bch_fs *c = trans->c;
1332         static int warned_disk_usage = 0;
1333         bool warn = false;
1334         unsigned disk_res_sectors = trans->disk_res ? trans->disk_res->sectors : 0;
1335         struct replicas_delta *d = deltas->d;
1336         struct replicas_delta *top = (void *) deltas->d + deltas->used;
1337         struct bch_fs_usage *dst;
1338         s64 added = 0, should_not_have_added;
1339         unsigned i;
1340
1341         percpu_rwsem_assert_held(&c->mark_lock);
1342
1343         preempt_disable();
1344         dst = fs_usage_ptr(c, trans->journal_res.seq, false);
1345
1346         for (d = deltas->d; d != top; d = replicas_delta_next(d)) {
1347                 switch (d->r.data_type) {
1348                 case BCH_DATA_btree:
1349                 case BCH_DATA_user:
1350                 case BCH_DATA_parity:
1351                         added += d->delta;
1352                 }
1353
1354                 BUG_ON(__update_replicas(c, dst, &d->r, d->delta));
1355         }
1356
1357         dst->nr_inodes += deltas->nr_inodes;
1358
1359         for (i = 0; i < BCH_REPLICAS_MAX; i++) {
1360                 added                           += deltas->persistent_reserved[i];
1361                 dst->reserved                   += deltas->persistent_reserved[i];
1362                 dst->persistent_reserved[i]     += deltas->persistent_reserved[i];
1363         }
1364
1365         /*
1366          * Not allowed to reduce sectors_available except by getting a
1367          * reservation:
1368          */
1369         should_not_have_added = added - (s64) disk_res_sectors;
1370         if (unlikely(should_not_have_added > 0)) {
1371                 u64 old, new, v = atomic64_read(&c->sectors_available);
1372
1373                 do {
1374                         old = v;
1375                         new = max_t(s64, 0, old - should_not_have_added);
1376                 } while ((v = atomic64_cmpxchg(&c->sectors_available,
1377                                                old, new)) != old);
1378
1379                 added -= should_not_have_added;
1380                 warn = true;
1381         }
1382
1383         if (added > 0) {
1384                 trans->disk_res->sectors -= added;
1385                 this_cpu_sub(*c->online_reserved, added);
1386         }
1387
1388         preempt_enable();
1389
1390         if (unlikely(warn) && !xchg(&warned_disk_usage, 1))
1391                 fs_usage_apply_warn(trans, disk_res_sectors, should_not_have_added);
1392 }
1393
1394 /* trans_mark: */
1395
1396 static struct bkey_alloc_buf *
1397 bch2_trans_start_alloc_update(struct btree_trans *trans, struct btree_iter *iter,
1398                               const struct bch_extent_ptr *ptr,
1399                               struct bkey_alloc_unpacked *u)
1400 {
1401         struct bch_fs *c = trans->c;
1402         struct bch_dev *ca = bch_dev_bkey_exists(c, ptr->dev);
1403         struct bpos pos = POS(ptr->dev, PTR_BUCKET_NR(ca, ptr));
1404         struct bucket *g;
1405         struct bkey_alloc_buf *a;
1406         struct bkey_i *update = btree_trans_peek_updates(trans, BTREE_ID_alloc, pos);
1407         int ret;
1408
1409         a = bch2_trans_kmalloc(trans, sizeof(struct bkey_alloc_buf));
1410         if (IS_ERR(a))
1411                 return a;
1412
1413         bch2_trans_iter_init(trans, iter, BTREE_ID_alloc, pos,
1414                              BTREE_ITER_CACHED|
1415                              BTREE_ITER_CACHED_NOFILL|
1416                              BTREE_ITER_INTENT);
1417         ret = bch2_btree_iter_traverse(iter);
1418         if (ret) {
1419                 bch2_trans_iter_exit(trans, iter);
1420                 return ERR_PTR(ret);
1421         }
1422
1423         if (update && !bpos_cmp(update->k.p, pos)) {
1424                 *u = bch2_alloc_unpack(bkey_i_to_s_c(update));
1425         } else {
1426                 percpu_down_read(&c->mark_lock);
1427                 g = bucket(ca, pos.offset);
1428                 *u = alloc_mem_to_key(iter, g, READ_ONCE(g->mark));
1429                 percpu_up_read(&c->mark_lock);
1430         }
1431
1432         return a;
1433 }
1434
1435 static int bch2_trans_mark_pointer(struct btree_trans *trans,
1436                         struct bkey_s_c k, struct extent_ptr_decoded p,
1437                         s64 sectors, enum bch_data_type data_type)
1438 {
1439         struct bch_fs *c = trans->c;
1440         struct btree_iter iter;
1441         struct bkey_alloc_unpacked u;
1442         struct bkey_alloc_buf *a;
1443         int ret;
1444
1445         a = bch2_trans_start_alloc_update(trans, &iter, &p.ptr, &u);
1446         if (IS_ERR(a))
1447                 return PTR_ERR(a);
1448
1449         ret = __mark_pointer(c, k, &p.ptr, sectors, data_type, u.gen, &u.data_type,
1450                              &u.dirty_sectors, &u.cached_sectors);
1451         if (ret)
1452                 goto out;
1453
1454         bch2_alloc_pack(c, a, u);
1455         bch2_trans_update(trans, &iter, &a->k, 0);
1456 out:
1457         bch2_trans_iter_exit(trans, &iter);
1458         return ret;
1459 }
1460
1461 static int bch2_trans_mark_stripe_ptr(struct btree_trans *trans,
1462                         struct extent_ptr_decoded p,
1463                         s64 sectors, enum bch_data_type data_type)
1464 {
1465         struct bch_fs *c = trans->c;
1466         struct btree_iter iter;
1467         struct bkey_s_c k;
1468         struct bkey_i_stripe *s;
1469         struct bch_replicas_padded r;
1470         int ret = 0;
1471
1472         bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes, POS(0, p.ec.idx),
1473                              BTREE_ITER_INTENT|
1474                              BTREE_ITER_WITH_UPDATES);
1475         k = bch2_btree_iter_peek_slot(&iter);
1476         ret = bkey_err(k);
1477         if (ret)
1478                 goto err;
1479
1480         if (k.k->type != KEY_TYPE_stripe) {
1481                 bch2_fs_inconsistent(c,
1482                         "pointer to nonexistent stripe %llu",
1483                         (u64) p.ec.idx);
1484                 bch2_inconsistent_error(c);
1485                 ret = -EIO;
1486                 goto err;
1487         }
1488
1489         if (!bch2_ptr_matches_stripe(bkey_s_c_to_stripe(k).v, p)) {
1490                 bch2_fs_inconsistent(c,
1491                         "stripe pointer doesn't match stripe %llu",
1492                         (u64) p.ec.idx);
1493                 ret = -EIO;
1494                 goto err;
1495         }
1496
1497         s = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1498         ret = PTR_ERR_OR_ZERO(s);
1499         if (ret)
1500                 goto err;
1501
1502         bkey_reassemble(&s->k_i, k);
1503         stripe_blockcount_set(&s->v, p.ec.block,
1504                 stripe_blockcount_get(&s->v, p.ec.block) +
1505                 sectors);
1506         bch2_trans_update(trans, &iter, &s->k_i, 0);
1507
1508         bch2_bkey_to_replicas(&r.e, bkey_i_to_s_c(&s->k_i));
1509         r.e.data_type = data_type;
1510         update_replicas_list(trans, &r.e, sectors);
1511 err:
1512         bch2_trans_iter_exit(trans, &iter);
1513         return ret;
1514 }
1515
1516 static int bch2_trans_mark_extent(struct btree_trans *trans,
1517                         struct bkey_s_c k, unsigned flags)
1518 {
1519         struct bch_fs *c = trans->c;
1520         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
1521         const union bch_extent_entry *entry;
1522         struct extent_ptr_decoded p;
1523         struct bch_replicas_padded r;
1524         enum bch_data_type data_type = bkey_is_btree_ptr(k.k)
1525                 ? BCH_DATA_btree
1526                 : BCH_DATA_user;
1527         s64 sectors = bkey_is_btree_ptr(k.k)
1528                 ? c->opts.btree_node_size
1529                 : k.k->size;
1530         s64 dirty_sectors = 0;
1531         bool stale;
1532         int ret;
1533
1534         BUG_ON((flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)) ==
1535                (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE));
1536
1537         r.e.data_type   = data_type;
1538         r.e.nr_devs     = 0;
1539         r.e.nr_required = 1;
1540
1541         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
1542                 s64 disk_sectors = ptr_disk_sectors(sectors, p);
1543
1544                 if (flags & BTREE_TRIGGER_OVERWRITE)
1545                         disk_sectors = -disk_sectors;
1546
1547                 ret = bch2_trans_mark_pointer(trans, k, p,
1548                                         disk_sectors, data_type);
1549                 if (ret < 0)
1550                         return ret;
1551
1552                 stale = ret > 0;
1553
1554                 if (p.ptr.cached) {
1555                         if (!stale)
1556                                 update_cached_sectors_list(trans, p.ptr.dev,
1557                                                            disk_sectors);
1558                 } else if (!p.has_ec) {
1559                         dirty_sectors          += disk_sectors;
1560                         r.e.devs[r.e.nr_devs++] = p.ptr.dev;
1561                 } else {
1562                         ret = bch2_trans_mark_stripe_ptr(trans, p,
1563                                         disk_sectors, data_type);
1564                         if (ret)
1565                                 return ret;
1566
1567                         r.e.nr_required = 0;
1568                 }
1569         }
1570
1571         if (r.e.nr_devs)
1572                 update_replicas_list(trans, &r.e, dirty_sectors);
1573
1574         return 0;
1575 }
1576
1577 static int bch2_trans_mark_stripe_alloc_ref(struct btree_trans *trans,
1578                                             struct bkey_s_c_stripe s,
1579                                             unsigned idx, bool deleting)
1580 {
1581         struct bch_fs *c = trans->c;
1582         const struct bch_extent_ptr *ptr = &s.v->ptrs[idx];
1583         struct bkey_alloc_buf *a;
1584         struct btree_iter iter;
1585         struct bkey_alloc_unpacked u;
1586         bool parity = idx >= s.v->nr_blocks - s.v->nr_redundant;
1587         int ret = 0;
1588
1589         a = bch2_trans_start_alloc_update(trans, &iter, ptr, &u);
1590         if (IS_ERR(a))
1591                 return PTR_ERR(a);
1592
1593         if (parity) {
1594                 s64 sectors = le16_to_cpu(s.v->sectors);
1595
1596                 if (deleting)
1597                         sectors = -sectors;
1598
1599                 u.dirty_sectors += sectors;
1600                 u.data_type = u.dirty_sectors
1601                         ? BCH_DATA_parity
1602                         : 0;
1603         }
1604
1605         if (!deleting) {
1606                 if (bch2_fs_inconsistent_on(u.stripe && u.stripe != s.k->p.offset, c,
1607                                 "bucket %llu:%llu gen %u: multiple stripes using same bucket (%u, %llu)",
1608                                 iter.pos.inode, iter.pos.offset, u.gen,
1609                                 u.stripe, s.k->p.offset)) {
1610                         ret = -EIO;
1611                         goto err;
1612                 }
1613
1614                 u.stripe                = s.k->p.offset;
1615                 u.stripe_redundancy     = s.v->nr_redundant;
1616         } else {
1617                 u.stripe                = 0;
1618                 u.stripe_redundancy     = 0;
1619         }
1620
1621         bch2_alloc_pack(c, a, u);
1622         bch2_trans_update(trans, &iter, &a->k, 0);
1623 err:
1624         bch2_trans_iter_exit(trans, &iter);
1625         return ret;
1626 }
1627
1628 static int bch2_trans_mark_stripe(struct btree_trans *trans,
1629                                   struct bkey_s_c old, struct bkey_s_c new,
1630                                   unsigned flags)
1631 {
1632         struct bkey_s_c_stripe old_s = { .k = NULL };
1633         struct bkey_s_c_stripe new_s = { .k = NULL };
1634         struct bch_replicas_padded r;
1635         unsigned i;
1636         int ret = 0;
1637
1638         if (old.k->type == KEY_TYPE_stripe)
1639                 old_s = bkey_s_c_to_stripe(old);
1640         if (new.k->type == KEY_TYPE_stripe)
1641                 new_s = bkey_s_c_to_stripe(new);
1642
1643         /*
1644          * If the pointers aren't changing, we don't need to do anything:
1645          */
1646         if (new_s.k && old_s.k &&
1647             new_s.v->nr_blocks          == old_s.v->nr_blocks &&
1648             new_s.v->nr_redundant       == old_s.v->nr_redundant &&
1649             !memcmp(old_s.v->ptrs, new_s.v->ptrs,
1650                     new_s.v->nr_blocks * sizeof(struct bch_extent_ptr)))
1651                 return 0;
1652
1653         if (new_s.k) {
1654                 s64 sectors = le16_to_cpu(new_s.v->sectors);
1655
1656                 bch2_bkey_to_replicas(&r.e, new);
1657                 update_replicas_list(trans, &r.e, sectors * new_s.v->nr_redundant);
1658
1659                 for (i = 0; i < new_s.v->nr_blocks; i++) {
1660                         ret = bch2_trans_mark_stripe_alloc_ref(trans, new_s,
1661                                                                i, false);
1662                         if (ret)
1663                                 return ret;
1664                 }
1665         }
1666
1667         if (old_s.k) {
1668                 s64 sectors = -((s64) le16_to_cpu(old_s.v->sectors));
1669
1670                 bch2_bkey_to_replicas(&r.e, old);
1671                 update_replicas_list(trans, &r.e, sectors * old_s.v->nr_redundant);
1672
1673                 for (i = 0; i < old_s.v->nr_blocks; i++) {
1674                         ret = bch2_trans_mark_stripe_alloc_ref(trans, old_s,
1675                                                                i, true);
1676                         if (ret)
1677                                 return ret;
1678                 }
1679         }
1680
1681         return ret;
1682 }
1683
1684 static int bch2_trans_mark_inode(struct btree_trans *trans,
1685                                  struct bkey_s_c old,
1686                                  struct bkey_s_c new,
1687                                  unsigned flags)
1688 {
1689         int nr = (new.k->type == KEY_TYPE_inode) -
1690                 (old.k->type == KEY_TYPE_inode);
1691
1692         if (nr) {
1693                 struct replicas_delta_list *d =
1694                         replicas_deltas_realloc(trans, 0);
1695                 d->nr_inodes += nr;
1696         }
1697
1698         return 0;
1699 }
1700
1701 static int bch2_trans_mark_reservation(struct btree_trans *trans,
1702                                        struct bkey_s_c k, unsigned flags)
1703 {
1704         unsigned replicas = bkey_s_c_to_reservation(k).v->nr_replicas;
1705         s64 sectors = (s64) k.k->size;
1706         struct replicas_delta_list *d;
1707
1708         BUG_ON((flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)) ==
1709                (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE));
1710
1711         if (flags & BTREE_TRIGGER_OVERWRITE)
1712                 sectors = -sectors;
1713         sectors *= replicas;
1714
1715         d = replicas_deltas_realloc(trans, 0);
1716
1717         replicas = clamp_t(unsigned, replicas, 1,
1718                            ARRAY_SIZE(d->persistent_reserved));
1719
1720         d->persistent_reserved[replicas - 1] += sectors;
1721         return 0;
1722 }
1723
1724 static int __bch2_trans_mark_reflink_p(struct btree_trans *trans,
1725                         struct bkey_s_c_reflink_p p,
1726                         u64 idx, unsigned flags)
1727 {
1728         struct bch_fs *c = trans->c;
1729         struct btree_iter iter;
1730         struct bkey_s_c k;
1731         struct bkey_i *n;
1732         __le64 *refcount;
1733         int add = !(flags & BTREE_TRIGGER_OVERWRITE) ? 1 : -1;
1734         s64 ret;
1735
1736         bch2_trans_iter_init(trans, &iter, BTREE_ID_reflink, POS(0, idx),
1737                              BTREE_ITER_INTENT|
1738                              BTREE_ITER_WITH_UPDATES);
1739         k = bch2_btree_iter_peek_slot(&iter);
1740         ret = bkey_err(k);
1741         if (ret)
1742                 goto err;
1743
1744         n = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1745         ret = PTR_ERR_OR_ZERO(n);
1746         if (ret)
1747                 goto err;
1748
1749         bkey_reassemble(n, k);
1750
1751         refcount = bkey_refcount(n);
1752         if (!refcount) {
1753                 bch2_fs_inconsistent(c,
1754                         "%llu:%llu len %u points to nonexistent indirect extent %llu",
1755                         p.k->p.inode, p.k->p.offset, p.k->size, idx);
1756                 bch2_inconsistent_error(c);
1757                 ret = -EIO;
1758                 goto err;
1759         }
1760
1761         BUG_ON(!*refcount && (flags & BTREE_TRIGGER_OVERWRITE));
1762         le64_add_cpu(refcount, add);
1763
1764         if (!*refcount) {
1765                 n->k.type = KEY_TYPE_deleted;
1766                 set_bkey_val_u64s(&n->k, 0);
1767         }
1768
1769         bch2_btree_iter_set_pos_to_extent_start(&iter);
1770         ret = bch2_trans_update(trans, &iter, n, 0);
1771         if (ret)
1772                 goto err;
1773
1774         ret = k.k->p.offset - idx;
1775 err:
1776         bch2_trans_iter_exit(trans, &iter);
1777         return ret;
1778 }
1779
1780 static int bch2_trans_mark_reflink_p(struct btree_trans *trans,
1781                                      struct bkey_s_c k, unsigned flags)
1782 {
1783         struct bkey_s_c_reflink_p p = bkey_s_c_to_reflink_p(k);
1784         u64 idx = le64_to_cpu(p.v->idx);
1785         unsigned sectors = p.k->size;
1786         s64 ret = 0;
1787
1788         while (sectors) {
1789                 ret = __bch2_trans_mark_reflink_p(trans, p, idx, flags);
1790                 if (ret < 0)
1791                         return ret;
1792
1793                 ret = min_t(s64, ret, sectors);
1794                 idx     += ret;
1795                 sectors -= ret;
1796         }
1797
1798         return 0;
1799 }
1800
1801 int bch2_trans_mark_key(struct btree_trans *trans, struct bkey_s_c old,
1802                         struct bkey_s_c new, unsigned flags)
1803 {
1804         struct bkey_s_c k = flags & BTREE_TRIGGER_INSERT ? new : old;
1805
1806         BUG_ON(!(flags & (BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE)));
1807
1808         switch (k.k->type) {
1809         case KEY_TYPE_btree_ptr:
1810         case KEY_TYPE_btree_ptr_v2:
1811         case KEY_TYPE_extent:
1812         case KEY_TYPE_reflink_v:
1813                 return bch2_trans_mark_extent(trans, k, flags);
1814         case KEY_TYPE_stripe:
1815                 return bch2_trans_mark_stripe(trans, old, new, flags);
1816         case KEY_TYPE_inode:
1817                 return bch2_trans_mark_inode(trans, old, new, flags);
1818         case KEY_TYPE_reservation:
1819                 return bch2_trans_mark_reservation(trans, k, flags);
1820         case KEY_TYPE_reflink_p:
1821                 return bch2_trans_mark_reflink_p(trans, k, flags);
1822         default:
1823                 return 0;
1824         }
1825 }
1826
1827 int bch2_trans_mark_update(struct btree_trans *trans,
1828                            struct btree_path *path,
1829                            struct bkey_i *new,
1830                            unsigned flags)
1831 {
1832         struct bkey             _deleted = KEY(0, 0, 0);
1833         struct bkey_s_c         deleted = (struct bkey_s_c) { &_deleted, NULL };
1834         struct bkey_s_c         old;
1835         struct bkey             unpacked;
1836         int ret;
1837
1838         if (unlikely(flags & BTREE_TRIGGER_NORUN))
1839                 return 0;
1840
1841         if (!btree_node_type_needs_gc(path->btree_id))
1842                 return 0;
1843
1844         old = bch2_btree_path_peek_slot(path, &unpacked);
1845
1846         if (old.k->type == new->k.type &&
1847             ((1U << old.k->type) & BTREE_TRIGGER_WANTS_OLD_AND_NEW)) {
1848                 ret   = bch2_trans_mark_key(trans, old, bkey_i_to_s_c(new),
1849                                 BTREE_TRIGGER_INSERT|BTREE_TRIGGER_OVERWRITE|flags);
1850         } else {
1851                 ret   = bch2_trans_mark_key(trans, deleted, bkey_i_to_s_c(new),
1852                                 BTREE_TRIGGER_INSERT|flags) ?:
1853                         bch2_trans_mark_key(trans, old, deleted,
1854                                 BTREE_TRIGGER_OVERWRITE|flags);
1855         }
1856
1857         return ret;
1858 }
1859
1860 static int __bch2_trans_mark_metadata_bucket(struct btree_trans *trans,
1861                                     struct bch_dev *ca, size_t b,
1862                                     enum bch_data_type type,
1863                                     unsigned sectors)
1864 {
1865         struct bch_fs *c = trans->c;
1866         struct btree_iter iter;
1867         struct bkey_alloc_unpacked u;
1868         struct bkey_alloc_buf *a;
1869         struct bch_extent_ptr ptr = {
1870                 .dev = ca->dev_idx,
1871                 .offset = bucket_to_sector(ca, b),
1872         };
1873         int ret = 0;
1874
1875         /*
1876          * Backup superblock might be past the end of our normal usable space:
1877          */
1878         if (b >= ca->mi.nbuckets)
1879                 return 0;
1880
1881         a = bch2_trans_start_alloc_update(trans, &iter, &ptr, &u);
1882         if (IS_ERR(a))
1883                 return PTR_ERR(a);
1884
1885         if (u.data_type && u.data_type != type) {
1886                 bch2_fsck_err(c, FSCK_CAN_IGNORE|FSCK_NEED_FSCK,
1887                         "bucket %llu:%llu gen %u different types of data in same bucket: %s, %s\n"
1888                         "while marking %s",
1889                         iter.pos.inode, iter.pos.offset, u.gen,
1890                         bch2_data_types[u.data_type],
1891                         bch2_data_types[type],
1892                         bch2_data_types[type]);
1893                 ret = -EIO;
1894                 goto out;
1895         }
1896
1897         u.data_type     = type;
1898         u.dirty_sectors = sectors;
1899
1900         bch2_alloc_pack(c, a, u);
1901         bch2_trans_update(trans, &iter, &a->k, 0);
1902 out:
1903         bch2_trans_iter_exit(trans, &iter);
1904         return ret;
1905 }
1906
1907 int bch2_trans_mark_metadata_bucket(struct btree_trans *trans,
1908                                     struct bch_dev *ca, size_t b,
1909                                     enum bch_data_type type,
1910                                     unsigned sectors)
1911 {
1912         return __bch2_trans_do(trans, NULL, NULL, 0,
1913                         __bch2_trans_mark_metadata_bucket(trans, ca, b, type, sectors));
1914 }
1915
1916 static int bch2_trans_mark_metadata_sectors(struct btree_trans *trans,
1917                                             struct bch_dev *ca,
1918                                             u64 start, u64 end,
1919                                             enum bch_data_type type,
1920                                             u64 *bucket, unsigned *bucket_sectors)
1921 {
1922         do {
1923                 u64 b = sector_to_bucket(ca, start);
1924                 unsigned sectors =
1925                         min_t(u64, bucket_to_sector(ca, b + 1), end) - start;
1926
1927                 if (b != *bucket && *bucket_sectors) {
1928                         int ret = bch2_trans_mark_metadata_bucket(trans, ca, *bucket,
1929                                                                   type, *bucket_sectors);
1930                         if (ret)
1931                                 return ret;
1932
1933                         *bucket_sectors = 0;
1934                 }
1935
1936                 *bucket         = b;
1937                 *bucket_sectors += sectors;
1938                 start += sectors;
1939         } while (start < end);
1940
1941         return 0;
1942 }
1943
1944 static int __bch2_trans_mark_dev_sb(struct btree_trans *trans,
1945                                     struct bch_dev *ca)
1946 {
1947         struct bch_sb_layout *layout = &ca->disk_sb.sb->layout;
1948         u64 bucket = 0;
1949         unsigned i, bucket_sectors = 0;
1950         int ret;
1951
1952         for (i = 0; i < layout->nr_superblocks; i++) {
1953                 u64 offset = le64_to_cpu(layout->sb_offset[i]);
1954
1955                 if (offset == BCH_SB_SECTOR) {
1956                         ret = bch2_trans_mark_metadata_sectors(trans, ca,
1957                                                 0, BCH_SB_SECTOR,
1958                                                 BCH_DATA_sb, &bucket, &bucket_sectors);
1959                         if (ret)
1960                                 return ret;
1961                 }
1962
1963                 ret = bch2_trans_mark_metadata_sectors(trans, ca, offset,
1964                                       offset + (1 << layout->sb_max_size_bits),
1965                                       BCH_DATA_sb, &bucket, &bucket_sectors);
1966                 if (ret)
1967                         return ret;
1968         }
1969
1970         if (bucket_sectors) {
1971                 ret = bch2_trans_mark_metadata_bucket(trans, ca,
1972                                 bucket, BCH_DATA_sb, bucket_sectors);
1973                 if (ret)
1974                         return ret;
1975         }
1976
1977         for (i = 0; i < ca->journal.nr; i++) {
1978                 ret = bch2_trans_mark_metadata_bucket(trans, ca,
1979                                 ca->journal.buckets[i],
1980                                 BCH_DATA_journal, ca->mi.bucket_size);
1981                 if (ret)
1982                         return ret;
1983         }
1984
1985         return 0;
1986 }
1987
1988 int bch2_trans_mark_dev_sb(struct bch_fs *c, struct bch_dev *ca)
1989 {
1990         return bch2_trans_do(c, NULL, NULL, BTREE_INSERT_LAZY_RW,
1991                         __bch2_trans_mark_dev_sb(&trans, ca));
1992 }
1993
1994 /* Disk reservations: */
1995
1996 #define SECTORS_CACHE   1024
1997
1998 int bch2_disk_reservation_add(struct bch_fs *c, struct disk_reservation *res,
1999                               u64 sectors, int flags)
2000 {
2001         struct bch_fs_pcpu *pcpu;
2002         u64 old, v, get;
2003         s64 sectors_available;
2004         int ret;
2005
2006         percpu_down_read(&c->mark_lock);
2007         preempt_disable();
2008         pcpu = this_cpu_ptr(c->pcpu);
2009
2010         if (sectors <= pcpu->sectors_available)
2011                 goto out;
2012
2013         v = atomic64_read(&c->sectors_available);
2014         do {
2015                 old = v;
2016                 get = min((u64) sectors + SECTORS_CACHE, old);
2017
2018                 if (get < sectors) {
2019                         preempt_enable();
2020                         goto recalculate;
2021                 }
2022         } while ((v = atomic64_cmpxchg(&c->sectors_available,
2023                                        old, old - get)) != old);
2024
2025         pcpu->sectors_available         += get;
2026
2027 out:
2028         pcpu->sectors_available         -= sectors;
2029         this_cpu_add(*c->online_reserved, sectors);
2030         res->sectors                    += sectors;
2031
2032         preempt_enable();
2033         percpu_up_read(&c->mark_lock);
2034         return 0;
2035
2036 recalculate:
2037         mutex_lock(&c->sectors_available_lock);
2038
2039         percpu_u64_set(&c->pcpu->sectors_available, 0);
2040         sectors_available = avail_factor(__bch2_fs_usage_read_short(c).free);
2041
2042         if (sectors <= sectors_available ||
2043             (flags & BCH_DISK_RESERVATION_NOFAIL)) {
2044                 atomic64_set(&c->sectors_available,
2045                              max_t(s64, 0, sectors_available - sectors));
2046                 this_cpu_add(*c->online_reserved, sectors);
2047                 res->sectors                    += sectors;
2048                 ret = 0;
2049         } else {
2050                 atomic64_set(&c->sectors_available, sectors_available);
2051                 ret = -ENOSPC;
2052         }
2053
2054         mutex_unlock(&c->sectors_available_lock);
2055         percpu_up_read(&c->mark_lock);
2056
2057         return ret;
2058 }
2059
2060 /* Startup/shutdown: */
2061
2062 static void buckets_free_rcu(struct rcu_head *rcu)
2063 {
2064         struct bucket_array *buckets =
2065                 container_of(rcu, struct bucket_array, rcu);
2066
2067         kvpfree(buckets,
2068                 sizeof(struct bucket_array) +
2069                 buckets->nbuckets * sizeof(struct bucket));
2070 }
2071
2072 int bch2_dev_buckets_resize(struct bch_fs *c, struct bch_dev *ca, u64 nbuckets)
2073 {
2074         struct bucket_array *buckets = NULL, *old_buckets = NULL;
2075         unsigned long *buckets_nouse = NULL;
2076         alloc_fifo      free[RESERVE_NR];
2077         alloc_fifo      free_inc;
2078         alloc_heap      alloc_heap;
2079
2080         size_t btree_reserve    = DIV_ROUND_UP(BTREE_NODE_RESERVE,
2081                              ca->mi.bucket_size / c->opts.btree_node_size);
2082         /* XXX: these should be tunable */
2083         size_t reserve_none     = max_t(size_t, 1, nbuckets >> 9);
2084         size_t copygc_reserve   = max_t(size_t, 2, nbuckets >> 6);
2085         size_t free_inc_nr      = max(max_t(size_t, 1, nbuckets >> 12),
2086                                       btree_reserve * 2);
2087         bool resize = ca->buckets[0] != NULL;
2088         int ret = -ENOMEM;
2089         unsigned i;
2090
2091         memset(&free,           0, sizeof(free));
2092         memset(&free_inc,       0, sizeof(free_inc));
2093         memset(&alloc_heap,     0, sizeof(alloc_heap));
2094
2095         if (!(buckets           = kvpmalloc(sizeof(struct bucket_array) +
2096                                             nbuckets * sizeof(struct bucket),
2097                                             GFP_KERNEL|__GFP_ZERO)) ||
2098             !(buckets_nouse     = kvpmalloc(BITS_TO_LONGS(nbuckets) *
2099                                             sizeof(unsigned long),
2100                                             GFP_KERNEL|__GFP_ZERO)) ||
2101             !init_fifo(&free[RESERVE_MOVINGGC],
2102                        copygc_reserve, GFP_KERNEL) ||
2103             !init_fifo(&free[RESERVE_NONE], reserve_none, GFP_KERNEL) ||
2104             !init_fifo(&free_inc,       free_inc_nr, GFP_KERNEL) ||
2105             !init_heap(&alloc_heap,     ALLOC_SCAN_BATCH(ca) << 1, GFP_KERNEL))
2106                 goto err;
2107
2108         buckets->first_bucket   = ca->mi.first_bucket;
2109         buckets->nbuckets       = nbuckets;
2110
2111         bch2_copygc_stop(c);
2112
2113         if (resize) {
2114                 down_write(&c->gc_lock);
2115                 down_write(&ca->bucket_lock);
2116                 percpu_down_write(&c->mark_lock);
2117         }
2118
2119         old_buckets = bucket_array(ca);
2120
2121         if (resize) {
2122                 size_t n = min(buckets->nbuckets, old_buckets->nbuckets);
2123
2124                 memcpy(buckets->b,
2125                        old_buckets->b,
2126                        n * sizeof(struct bucket));
2127                 memcpy(buckets_nouse,
2128                        ca->buckets_nouse,
2129                        BITS_TO_LONGS(n) * sizeof(unsigned long));
2130         }
2131
2132         rcu_assign_pointer(ca->buckets[0], buckets);
2133         buckets = old_buckets;
2134
2135         swap(ca->buckets_nouse, buckets_nouse);
2136
2137         if (resize) {
2138                 percpu_up_write(&c->mark_lock);
2139                 up_write(&c->gc_lock);
2140         }
2141
2142         spin_lock(&c->freelist_lock);
2143         for (i = 0; i < RESERVE_NR; i++) {
2144                 fifo_move(&free[i], &ca->free[i]);
2145                 swap(ca->free[i], free[i]);
2146         }
2147         fifo_move(&free_inc, &ca->free_inc);
2148         swap(ca->free_inc, free_inc);
2149         spin_unlock(&c->freelist_lock);
2150
2151         /* with gc lock held, alloc_heap can't be in use: */
2152         swap(ca->alloc_heap, alloc_heap);
2153
2154         nbuckets = ca->mi.nbuckets;
2155
2156         if (resize)
2157                 up_write(&ca->bucket_lock);
2158
2159         ret = 0;
2160 err:
2161         free_heap(&alloc_heap);
2162         free_fifo(&free_inc);
2163         for (i = 0; i < RESERVE_NR; i++)
2164                 free_fifo(&free[i]);
2165         kvpfree(buckets_nouse,
2166                 BITS_TO_LONGS(nbuckets) * sizeof(unsigned long));
2167         if (buckets)
2168                 call_rcu(&old_buckets->rcu, buckets_free_rcu);
2169
2170         return ret;
2171 }
2172
2173 void bch2_dev_buckets_free(struct bch_dev *ca)
2174 {
2175         unsigned i;
2176
2177         free_heap(&ca->alloc_heap);
2178         free_fifo(&ca->free_inc);
2179         for (i = 0; i < RESERVE_NR; i++)
2180                 free_fifo(&ca->free[i]);
2181         kvpfree(ca->buckets_nouse,
2182                 BITS_TO_LONGS(ca->mi.nbuckets) * sizeof(unsigned long));
2183         kvpfree(rcu_dereference_protected(ca->buckets[0], 1),
2184                 sizeof(struct bucket_array) +
2185                 ca->mi.nbuckets * sizeof(struct bucket));
2186
2187         for (i = 0; i < ARRAY_SIZE(ca->usage); i++)
2188                 free_percpu(ca->usage[i]);
2189         kfree(ca->usage_base);
2190 }
2191
2192 int bch2_dev_buckets_alloc(struct bch_fs *c, struct bch_dev *ca)
2193 {
2194         unsigned i;
2195
2196         ca->usage_base = kzalloc(sizeof(struct bch_dev_usage), GFP_KERNEL);
2197         if (!ca->usage_base)
2198                 return -ENOMEM;
2199
2200         for (i = 0; i < ARRAY_SIZE(ca->usage); i++) {
2201                 ca->usage[i] = alloc_percpu(struct bch_dev_usage);
2202                 if (!ca->usage[i])
2203                         return -ENOMEM;
2204         }
2205
2206         return bch2_dev_buckets_resize(c, ca, ca->mi.nbuckets);;
2207 }