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

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "btree_update.h"
   5 #include "btree_update_interior.h"
   6 #include "btree_gc.h"
   7 #include "btree_io.h"
   8 #include "btree_iter.h"
   9 #include "btree_locking.h"
  10 #include "buckets.h"
  11 #include "debug.h"
  12 #include "error.h"
  13 #include "extents.h"
  14 #include "journal.h"
  15 #include "journal_reclaim.h"
  16 #include "keylist.h"
  17 #include "replicas.h"
  18
  19 #include <linux/sort.h>
  20 #include <trace/events/bcachefs.h>
  21
  22 inline void bch2_btree_node_lock_for_insert(struct bch_fs *c, struct btree *b,
  23                                             struct btree_iter *iter)
  24 {
  25         bch2_btree_node_lock_write(b, iter);
  26
  27         if (btree_node_just_written(b) &&
  28             bch2_btree_post_write_cleanup(c, b))
  29                 bch2_btree_iter_reinit_node(iter, b);
  30
  31         /*
  32          * If the last bset has been written, or if it's gotten too big - start
  33          * a new bset to insert into:
  34          */
  35         if (want_new_bset(c, b))
  36                 bch2_btree_init_next(c, b, iter);
  37 }
  38
  39 static void btree_trans_lock_write(struct bch_fs *c, struct btree_trans *trans)
  40 {
  41         struct btree_insert_entry *i;
  42
  43         trans_for_each_update_leaf(trans, i)
  44                 bch2_btree_node_lock_for_insert(c, i->iter->l[0].b, i->iter);
  45 }
  46
  47 static void btree_trans_unlock_write(struct btree_trans *trans)
  48 {
  49         struct btree_insert_entry *i;
  50
  51         trans_for_each_update_leaf(trans, i)
  52                 bch2_btree_node_unlock_write(i->iter->l[0].b, i->iter);
  53 }
  54
  55 static inline int btree_trans_cmp(struct btree_insert_entry l,
  56                                   struct btree_insert_entry r)
  57 {
  58         return cmp_int(l.deferred, r.deferred) ?:
  59                 btree_iter_cmp(l.iter, r.iter);
  60 }
  61
  62 /* Inserting into a given leaf node (last stage of insert): */
  63
  64 /* Handle overwrites and do insert, for non extents: */
  65 bool bch2_btree_bset_insert_key(struct btree_iter *iter,
  66                                 struct btree *b,
  67                                 struct btree_node_iter *node_iter,
  68                                 struct bkey_i *insert)
  69 {
  70         const struct bkey_format *f = &b->format;
  71         struct bkey_packed *k;
  72         unsigned clobber_u64s;
  73
  74         EBUG_ON(btree_node_just_written(b));
  75         EBUG_ON(bset_written(b, btree_bset_last(b)));
  76         EBUG_ON(bkey_deleted(&insert->k) && bkey_val_u64s(&insert->k));
  77         EBUG_ON(bkey_cmp(bkey_start_pos(&insert->k), b->data->min_key) < 0 ||
  78                 bkey_cmp(insert->k.p, b->data->max_key) > 0);
  79
  80         k = bch2_btree_node_iter_peek_all(node_iter, b);
  81         if (k && !bkey_cmp_packed(b, k, &insert->k)) {
  82                 BUG_ON(bkey_whiteout(k));
  83
  84                 if (!bkey_written(b, k) &&
  85                     bkey_val_u64s(&insert->k) == bkeyp_val_u64s(f, k) &&
  86                     !bkey_whiteout(&insert->k)) {
  87                         k->type = insert->k.type;
  88                         memcpy_u64s(bkeyp_val(f, k), &insert->v,
  89                                     bkey_val_u64s(&insert->k));
  90                         return true;
  91                 }
  92
  93                 insert->k.needs_whiteout = k->needs_whiteout;
  94
  95                 btree_account_key_drop(b, k);
  96
  97                 if (k >= btree_bset_last(b)->start) {
  98                         clobber_u64s = k->u64s;
  99
 100                         /*
 101                          * If we're deleting, and the key we're deleting doesn't
 102                          * need a whiteout (it wasn't overwriting a key that had
 103                          * been written to disk) - just delete it:
 104                          */
 105                         if (bkey_whiteout(&insert->k) && !k->needs_whiteout) {
 106                                 bch2_bset_delete(b, k, clobber_u64s);
 107                                 bch2_btree_node_iter_fix(iter, b, node_iter,
 108                                                          k, clobber_u64s, 0);
 109                                 bch2_btree_iter_verify(iter, b);
 110                                 return true;
 111                         }
 112
 113                         goto overwrite;
 114                 }
 115
 116                 k->type = KEY_TYPE_deleted;
 117                 bch2_btree_node_iter_fix(iter, b, node_iter, k,
 118                                          k->u64s, k->u64s);
 119                 bch2_btree_iter_verify(iter, b);
 120
 121                 if (bkey_whiteout(&insert->k)) {
 122                         reserve_whiteout(b, k);
 123                         return true;
 124                 } else {
 125                         k->needs_whiteout = false;
 126                 }
 127         } else {
 128                 /*
 129                  * Deleting, but the key to delete wasn't found - nothing to do:
 130                  */
 131                 if (bkey_whiteout(&insert->k))
 132                         return false;
 133
 134                 insert->k.needs_whiteout = false;
 135         }
 136
 137         k = bch2_btree_node_iter_bset_pos(node_iter, b, bset_tree_last(b));
 138         clobber_u64s = 0;
 139 overwrite:
 140         bch2_bset_insert(b, node_iter, k, insert, clobber_u64s);
 141         if (k->u64s != clobber_u64s || bkey_whiteout(&insert->k))
 142                 bch2_btree_node_iter_fix(iter, b, node_iter, k,
 143                                          clobber_u64s, k->u64s);
 144         bch2_btree_iter_verify(iter, b);
 145         return true;
 146 }
 147
 148 static void __btree_node_flush(struct journal *j, struct journal_entry_pin *pin,
 149                                unsigned i, u64 seq)
 150 {
 151         struct bch_fs *c = container_of(j, struct bch_fs, journal);
 152         struct btree_write *w = container_of(pin, struct btree_write, journal);
 153         struct btree *b = container_of(w, struct btree, writes[i]);
 154
 155         btree_node_lock_type(c, b, SIX_LOCK_read);
 156         bch2_btree_node_write_cond(c, b,
 157                 (btree_current_write(b) == w && w->journal.seq == seq));
 158         six_unlock_read(&b->lock);
 159 }
 160
 161 static void btree_node_flush0(struct journal *j, struct journal_entry_pin *pin, u64 seq)
 162 {
 163         return __btree_node_flush(j, pin, 0, seq);
 164 }
 165
 166 static void btree_node_flush1(struct journal *j, struct journal_entry_pin *pin, u64 seq)
 167 {
 168         return __btree_node_flush(j, pin, 1, seq);
 169 }
 170
 171 static inline void __btree_journal_key(struct btree_trans *trans,
 172                                        enum btree_id btree_id,
 173                                        struct bkey_i *insert)
 174 {
 175         struct journal *j = &trans->c->journal;
 176         u64 seq = trans->journal_res.seq;
 177         bool needs_whiteout = insert->k.needs_whiteout;
 178
 179         /* ick */
 180         insert->k.needs_whiteout = false;
 181         bch2_journal_add_keys(j, &trans->journal_res,
 182                               btree_id, insert);
 183         insert->k.needs_whiteout = needs_whiteout;
 184
 185         bch2_journal_set_has_inode(j, &trans->journal_res,
 186                                    insert->k.p.inode);
 187
 188         if (trans->journal_seq)
 189                 *trans->journal_seq = seq;
 190 }
 191
 192 void bch2_btree_journal_key(struct btree_trans *trans,
 193                            struct btree_iter *iter,
 194                            struct bkey_i *insert)
 195 {
 196         struct bch_fs *c = trans->c;
 197         struct journal *j = &c->journal;
 198         struct btree *b = iter->l[0].b;
 199         struct btree_write *w = btree_current_write(b);
 200
 201         EBUG_ON(iter->level || b->level);
 202         EBUG_ON(trans->journal_res.ref !=
 203                 !(trans->flags & BTREE_INSERT_JOURNAL_REPLAY));
 204
 205         if (likely(!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))) {
 206                 __btree_journal_key(trans, iter->btree_id, insert);
 207                 btree_bset_last(b)->journal_seq =
 208                         cpu_to_le64(trans->journal_res.seq);
 209         }
 210
 211         if (unlikely(!journal_pin_active(&w->journal))) {
 212                 u64 seq = likely(!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))
 213                         ? trans->journal_res.seq
 214                         : j->replay_journal_seq;
 215
 216                 bch2_journal_pin_add(j, seq, &w->journal,
 217                                      btree_node_write_idx(b) == 0
 218                                      ? btree_node_flush0
 219                                      : btree_node_flush1);
 220         }
 221
 222         if (unlikely(!btree_node_dirty(b)))
 223                 set_btree_node_dirty(b);
 224 }
 225
 226 static void bch2_insert_fixup_key(struct btree_trans *trans,
 227                                   struct btree_insert_entry *insert)
 228 {
 229         struct btree_iter *iter = insert->iter;
 230         struct btree_iter_level *l = &iter->l[0];
 231
 232         EBUG_ON(iter->level);
 233         EBUG_ON(insert->k->k.u64s >
 234                 bch_btree_keys_u64s_remaining(trans->c, l->b));
 235
 236         if (bch2_btree_bset_insert_key(iter, l->b, &l->iter,
 237                                        insert->k))
 238                 bch2_btree_journal_key(trans, iter, insert->k);
 239 }
 240
 241 /**
 242  * btree_insert_key - insert a key one key into a leaf node
 243  */
 244 static void btree_insert_key_leaf(struct btree_trans *trans,
 245                                   struct btree_insert_entry *insert)
 246 {
 247         struct bch_fs *c = trans->c;
 248         struct btree_iter *iter = insert->iter;
 249         struct btree *b = iter->l[0].b;
 250         int old_u64s = le16_to_cpu(btree_bset_last(b)->u64s);
 251         int old_live_u64s = b->nr.live_u64s;
 252         int live_u64s_added, u64s_added;
 253
 254         if (!btree_node_is_extents(b))
 255                 bch2_insert_fixup_key(trans, insert);
 256         else
 257                 bch2_insert_fixup_extent(trans, insert);
 258
 259         live_u64s_added = (int) b->nr.live_u64s - old_live_u64s;
 260         u64s_added = (int) le16_to_cpu(btree_bset_last(b)->u64s) - old_u64s;
 261
 262         if (b->sib_u64s[0] != U16_MAX && live_u64s_added < 0)
 263                 b->sib_u64s[0] = max(0, (int) b->sib_u64s[0] + live_u64s_added);
 264         if (b->sib_u64s[1] != U16_MAX && live_u64s_added < 0)
 265                 b->sib_u64s[1] = max(0, (int) b->sib_u64s[1] + live_u64s_added);
 266
 267         if (u64s_added > live_u64s_added &&
 268             bch2_maybe_compact_whiteouts(c, b))
 269                 bch2_btree_iter_reinit_node(iter, b);
 270
 271         trace_btree_insert_key(c, b, insert->k);
 272 }
 273
 274 /* Deferred btree updates: */
 275
 276 static void deferred_update_flush(struct journal *j,
 277                                   struct journal_entry_pin *pin,
 278                                   u64 seq)
 279 {
 280         struct bch_fs *c = container_of(j, struct bch_fs, journal);
 281         struct deferred_update *d =
 282                 container_of(pin, struct deferred_update, journal);
 283         struct journal_preres res = { 0 };
 284         u64 tmp[32];
 285         struct bkey_i *k = (void *) tmp;
 286         int ret;
 287
 288         if (d->allocated_u64s > ARRAY_SIZE(tmp)) {
 289                 k = kmalloc(d->allocated_u64s * sizeof(u64), GFP_NOFS);
 290
 291                 BUG_ON(!k); /* XXX */
 292         }
 293
 294         spin_lock(&d->lock);
 295         if (d->dirty) {
 296                 BUG_ON(jset_u64s(d->k.k.u64s) > d->res.u64s);
 297
 298                 swap(res, d->res);
 299
 300                 BUG_ON(d->k.k.u64s > d->allocated_u64s);
 301
 302                 bkey_copy(k, &d->k);
 303                 d->dirty = false;
 304                 spin_unlock(&d->lock);
 305
 306                 ret = bch2_btree_insert(c, d->btree_id, k, NULL, NULL,
 307                                         BTREE_INSERT_NOFAIL|
 308                                         BTREE_INSERT_USE_RESERVE|
 309                                         BTREE_INSERT_JOURNAL_RESERVED);
 310                 bch2_fs_fatal_err_on(ret && !bch2_journal_error(j),
 311                                      c, "error flushing deferred btree update: %i", ret);
 312
 313                 spin_lock(&d->lock);
 314         }
 315
 316         if (!d->dirty)
 317                 bch2_journal_pin_drop(j, &d->journal);
 318         spin_unlock(&d->lock);
 319
 320         bch2_journal_preres_put(j, &res);
 321         if (k != (void *) tmp)
 322                 kfree(k);
 323 }
 324
 325 static void btree_insert_key_deferred(struct btree_trans *trans,
 326                                       struct btree_insert_entry *insert)
 327 {
 328         struct bch_fs *c = trans->c;
 329         struct journal *j = &c->journal;
 330         struct deferred_update *d = insert->d;
 331         int difference;
 332
 333         BUG_ON(trans->flags & BTREE_INSERT_JOURNAL_REPLAY);
 334         BUG_ON(insert->k->u64s > d->allocated_u64s);
 335
 336         __btree_journal_key(trans, d->btree_id, insert->k);
 337
 338         spin_lock(&d->lock);
 339         BUG_ON(jset_u64s(insert->k->u64s) >
 340                trans->journal_preres.u64s);
 341
 342         difference = jset_u64s(insert->k->u64s) - d->res.u64s;
 343         if (difference > 0) {
 344                 trans->journal_preres.u64s      -= difference;
 345                 d->res.u64s                     += difference;
 346         }
 347
 348         bkey_copy(&d->k, insert->k);
 349         d->dirty = true;
 350
 351         bch2_journal_pin_update(j, trans->journal_res.seq, &d->journal,
 352                                 deferred_update_flush);
 353         spin_unlock(&d->lock);
 354 }
 355
 356 void bch2_deferred_update_free(struct bch_fs *c,
 357                                struct deferred_update *d)
 358 {
 359         deferred_update_flush(&c->journal, &d->journal, 0);
 360
 361         BUG_ON(journal_pin_active(&d->journal));
 362
 363         bch2_journal_pin_flush(&c->journal, &d->journal);
 364         kfree(d);
 365 }
 366
 367 struct deferred_update *
 368 bch2_deferred_update_alloc(struct bch_fs *c,
 369                            enum btree_id btree_id,
 370                            unsigned u64s)
 371 {
 372         struct deferred_update *d;
 373
 374         BUG_ON(u64s > U8_MAX);
 375
 376         d = kmalloc(offsetof(struct deferred_update, k) +
 377                     u64s * sizeof(u64), GFP_NOFS);
 378         BUG_ON(!d);
 379
 380         memset(d, 0, offsetof(struct deferred_update, k));
 381
 382         spin_lock_init(&d->lock);
 383         d->allocated_u64s       = u64s;
 384         d->btree_id             = btree_id;
 385
 386         return d;
 387 }
 388
 389 /* Normal update interface: */
 390
 391 static inline void btree_insert_entry_checks(struct btree_trans *trans,
 392                                              struct btree_insert_entry *i)
 393 {
 394         struct bch_fs *c = trans->c;
 395         enum btree_id btree_id = !i->deferred
 396                 ? i->iter->btree_id
 397                 : i->d->btree_id;
 398
 399         if (!i->deferred) {
 400                 BUG_ON(i->iter->level);
 401                 BUG_ON(bkey_cmp(bkey_start_pos(&i->k->k), i->iter->pos));
 402                 EBUG_ON((i->iter->flags & BTREE_ITER_IS_EXTENTS) &&
 403                         bkey_cmp(i->k->k.p, i->iter->l[0].b->key.k.p) > 0);
 404                 EBUG_ON((i->iter->flags & BTREE_ITER_IS_EXTENTS) &&
 405                         !(trans->flags & BTREE_INSERT_ATOMIC));
 406         }
 407
 408         BUG_ON(debug_check_bkeys(c) &&
 409                !bkey_deleted(&i->k->k) &&
 410                bch2_bkey_invalid(c, bkey_i_to_s_c(i->k), btree_id));
 411 }
 412
 413 static int bch2_trans_journal_preres_get(struct btree_trans *trans)
 414 {
 415         struct bch_fs *c = trans->c;
 416         struct btree_insert_entry *i;
 417         unsigned u64s = 0;
 418         int ret;
 419
 420         trans_for_each_update(trans, i)
 421                 if (i->deferred)
 422                         u64s += jset_u64s(i->k->k.u64s);
 423
 424         if (!u64s)
 425                 return 0;
 426
 427         ret = bch2_journal_preres_get(&c->journal,
 428                         &trans->journal_preres, u64s,
 429                         JOURNAL_RES_GET_NONBLOCK);
 430         if (ret != -EAGAIN)
 431                 return ret;
 432
 433         bch2_trans_unlock(trans);
 434
 435         ret = bch2_journal_preres_get(&c->journal,
 436                         &trans->journal_preres, u64s, 0);
 437         if (ret)
 438                 return ret;
 439
 440         if (!bch2_trans_relock(trans)) {
 441                 trace_trans_restart_journal_preres_get(trans->ip);
 442                 return -EINTR;
 443         }
 444
 445         return 0;
 446 }
 447
 448 static int bch2_trans_journal_res_get(struct btree_trans *trans,
 449                                       unsigned flags)
 450 {
 451         struct bch_fs *c = trans->c;
 452         int ret;
 453
 454         if (trans->flags & BTREE_INSERT_JOURNAL_RESERVED)
 455                 flags |= JOURNAL_RES_GET_RESERVED;
 456
 457         ret = bch2_journal_res_get(&c->journal, &trans->journal_res,
 458                                    trans->journal_u64s, flags);
 459
 460         return ret == -EAGAIN ? BTREE_INSERT_NEED_JOURNAL_RES : ret;
 461 }
 462
 463 static enum btree_insert_ret
 464 btree_key_can_insert(struct btree_trans *trans,
 465                      struct btree_insert_entry *insert,
 466                      unsigned *u64s)
 467 {
 468         struct bch_fs *c = trans->c;
 469         struct btree *b = insert->iter->l[0].b;
 470         static enum btree_insert_ret ret;
 471
 472         if (unlikely(btree_node_fake(b)))
 473                 return BTREE_INSERT_BTREE_NODE_FULL;
 474
 475         ret = !btree_node_is_extents(b)
 476                 ? BTREE_INSERT_OK
 477                 : bch2_extent_can_insert(trans, insert, u64s);
 478         if (ret)
 479                 return ret;
 480
 481         if (*u64s > bch_btree_keys_u64s_remaining(c, b))
 482                 return BTREE_INSERT_BTREE_NODE_FULL;
 483
 484         return BTREE_INSERT_OK;
 485 }
 486
 487 static int btree_trans_check_can_insert(struct btree_trans *trans,
 488                                         struct btree_insert_entry **stopped_at)
 489 {
 490         struct btree_insert_entry *i;
 491         unsigned u64s = 0;
 492         int ret;
 493
 494         trans_for_each_update_iter(trans, i) {
 495                 /* Multiple inserts might go to same leaf: */
 496                 if (!same_leaf_as_prev(trans, i))
 497                         u64s = 0;
 498
 499                 u64s += i->k->k.u64s;
 500                 ret = btree_key_can_insert(trans, i, &u64s);
 501                 if (ret) {
 502                         *stopped_at = i;
 503                         return ret;
 504                 }
 505         }
 506
 507         return 0;
 508 }
 509
 510 static inline void do_btree_insert_one(struct btree_trans *trans,
 511                                        struct btree_insert_entry *insert)
 512 {
 513         if (likely(!insert->deferred))
 514                 btree_insert_key_leaf(trans, insert);
 515         else
 516                 btree_insert_key_deferred(trans, insert);
 517 }
 518
 519 static inline bool update_triggers_transactional(struct btree_trans *trans,
 520                                                  struct btree_insert_entry *i)
 521 {
 522         return likely(!(trans->flags & BTREE_INSERT_MARK_INMEM)) &&
 523                 (i->iter->btree_id == BTREE_ID_EXTENTS ||
 524                  i->iter->btree_id == BTREE_ID_INODES ||
 525                  i->iter->btree_id == BTREE_ID_REFLINK);
 526 }
 527
 528 static inline bool update_has_triggers(struct btree_trans *trans,
 529                                        struct btree_insert_entry *i)
 530 {
 531         return likely(!(trans->flags & BTREE_INSERT_NOMARK)) &&
 532                 !i->deferred &&
 533                 btree_node_type_needs_gc(i->iter->btree_id);
 534 }
 535
 536 /*
 537  * Get journal reservation, take write locks, and attempt to do btree update(s):
 538  */
 539 static inline int do_btree_insert_at(struct btree_trans *trans,
 540                                      struct btree_insert_entry **stopped_at)
 541 {
 542         struct bch_fs *c = trans->c;
 543         struct bch_fs_usage *fs_usage = NULL;
 544         struct btree_insert_entry *i;
 545         bool saw_non_marked;
 546         unsigned mark_flags = trans->flags & BTREE_INSERT_BUCKET_INVALIDATE
 547                 ? BCH_BUCKET_MARK_BUCKET_INVALIDATE
 548                 : 0;
 549         int ret;
 550
 551         trans_for_each_update_iter(trans, i)
 552                 BUG_ON(i->iter->uptodate >= BTREE_ITER_NEED_RELOCK);
 553
 554         trans_for_each_update_iter(trans, i)
 555                 i->marked = false;
 556
 557         do {
 558                 saw_non_marked = false;
 559
 560                 trans_for_each_update_iter(trans, i) {
 561                         if (i->marked)
 562                                 continue;
 563
 564                         saw_non_marked = true;
 565                         i->marked = true;
 566
 567                         if (update_has_triggers(trans, i) &&
 568                             update_triggers_transactional(trans, i)) {
 569                                 ret = bch2_trans_mark_update(trans, i->iter, i->k);
 570                                 if (ret == -EINTR)
 571                                         trace_trans_restart_mark(trans->ip);
 572                                 if (ret)
 573                                         goto out_clear_replicas;
 574                         }
 575                 }
 576         } while (saw_non_marked);
 577
 578         trans_for_each_update(trans, i)
 579                 btree_insert_entry_checks(trans, i);
 580         bch2_btree_trans_verify_locks(trans);
 581
 582         btree_trans_lock_write(c, trans);
 583
 584         if (race_fault()) {
 585                 ret = -EINTR;
 586                 trace_trans_restart_fault_inject(trans->ip);
 587                 goto out;
 588         }
 589
 590         /*
 591          * Check if the insert will fit in the leaf node with the write lock
 592          * held, otherwise another thread could write the node changing the
 593          * amount of space available:
 594          */
 595         ret = btree_trans_check_can_insert(trans, stopped_at);
 596         if (ret)
 597                 goto out;
 598
 599         trans_for_each_update_iter(trans, i) {
 600                 if (i->deferred ||
 601                     !btree_node_type_needs_gc(i->iter->btree_id))
 602                         continue;
 603
 604                 if (!fs_usage) {
 605                         percpu_down_read(&c->mark_lock);
 606                         fs_usage = bch2_fs_usage_scratch_get(c);
 607                 }
 608
 609                 if (!bch2_bkey_replicas_marked_locked(c,
 610                         bkey_i_to_s_c(i->k), true)) {
 611                         ret = BTREE_INSERT_NEED_MARK_REPLICAS;
 612                         goto out;
 613                 }
 614         }
 615
 616         /*
 617          * Don't get journal reservation until after we know insert will
 618          * succeed:
 619          */
 620         if (likely(!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))) {
 621                 trans->journal_u64s = 0;
 622
 623                 trans_for_each_update(trans, i)
 624                         trans->journal_u64s += jset_u64s(i->k->k.u64s);
 625
 626                 ret = bch2_trans_journal_res_get(trans, JOURNAL_RES_GET_NONBLOCK);
 627                 if (ret)
 628                         goto out;
 629         }
 630
 631         if (!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY)) {
 632                 if (journal_seq_verify(c))
 633                         trans_for_each_update(trans, i)
 634                                 i->k->k.version.lo = trans->journal_res.seq;
 635                 else if (inject_invalid_keys(c))
 636                         trans_for_each_update(trans, i)
 637                                 i->k->k.version = MAX_VERSION;
 638         }
 639
 640         trans_for_each_update_iter(trans, i)
 641                 if (update_has_triggers(trans, i) &&
 642                     !update_triggers_transactional(trans, i))
 643                         bch2_mark_update(trans, i, fs_usage, mark_flags);
 644
 645         if (fs_usage && trans->fs_usage_deltas)
 646                 bch2_replicas_delta_list_apply(c, fs_usage,
 647                                                trans->fs_usage_deltas);
 648
 649         if (fs_usage)
 650                 bch2_trans_fs_usage_apply(trans, fs_usage);
 651
 652         if (likely(!(trans->flags & BTREE_INSERT_NOMARK)) &&
 653             unlikely(c->gc_pos.phase))
 654                 trans_for_each_update_iter(trans, i)
 655                         if (gc_visited(c, gc_pos_btree_node(i->iter->l[0].b)))
 656                                 bch2_mark_update(trans, i, NULL,
 657                                                  mark_flags|
 658                                                  BCH_BUCKET_MARK_GC);
 659
 660         trans_for_each_update(trans, i)
 661                 do_btree_insert_one(trans, i);
 662 out:
 663         BUG_ON(ret &&
 664                (trans->flags & BTREE_INSERT_JOURNAL_RESERVED) &&
 665                trans->journal_res.ref);
 666
 667         btree_trans_unlock_write(trans);
 668
 669         if (fs_usage) {
 670                 bch2_fs_usage_scratch_put(c, fs_usage);
 671                 percpu_up_read(&c->mark_lock);
 672         }
 673
 674         bch2_journal_res_put(&c->journal, &trans->journal_res);
 675 out_clear_replicas:
 676         if (trans->fs_usage_deltas) {
 677                 memset(&trans->fs_usage_deltas->fs_usage, 0,
 678                        sizeof(trans->fs_usage_deltas->fs_usage));
 679                 trans->fs_usage_deltas->used = 0;
 680         }
 681
 682         return ret;
 683 }
 684
 685 static noinline
 686 int bch2_trans_commit_error(struct btree_trans *trans,
 687                             struct btree_insert_entry *i,
 688                             int ret)
 689 {
 690         struct bch_fs *c = trans->c;
 691         unsigned flags = trans->flags;
 692         struct btree_insert_entry *src, *dst;
 693
 694         src = dst = trans->updates;
 695
 696         while (src < trans->updates + trans->nr_updates) {
 697                 if (!src->triggered) {
 698                         *dst = *src;
 699                         dst++;
 700                 }
 701                 src++;
 702         }
 703
 704         trans->nr_updates = dst - trans->updates;
 705
 706         /*
 707          * BTREE_INSERT_NOUNLOCK means don't unlock _after_ successful btree
 708          * update; if we haven't done anything yet it doesn't apply
 709          */
 710         flags &= ~BTREE_INSERT_NOUNLOCK;
 711
 712         switch (ret) {
 713         case BTREE_INSERT_BTREE_NODE_FULL:
 714                 ret = bch2_btree_split_leaf(c, i->iter, flags);
 715
 716                 /*
 717                  * if the split succeeded without dropping locks the insert will
 718                  * still be atomic (in the BTREE_INSERT_ATOMIC sense, what the
 719                  * caller peeked() and is overwriting won't have changed)
 720                  */
 721 #if 0
 722                 /*
 723                  * XXX:
 724                  * split -> btree node merging (of parent node) might still drop
 725                  * locks when we're not passing it BTREE_INSERT_NOUNLOCK
 726                  *
 727                  * we don't want to pass BTREE_INSERT_NOUNLOCK to split as that
 728                  * will inhibit merging - but we don't have a reliable way yet
 729                  * (do we?) of checking if we dropped locks in this path
 730                  */
 731                 if (!ret)
 732                         goto retry;
 733 #endif
 734
 735                 /*
 736                  * don't care if we got ENOSPC because we told split it
 737                  * couldn't block:
 738                  */
 739                 if (!ret ||
 740                     ret == -EINTR ||
 741                     (flags & BTREE_INSERT_NOUNLOCK)) {
 742                         trace_trans_restart_btree_node_split(trans->ip);
 743                         ret = -EINTR;
 744                 }
 745                 break;
 746         case BTREE_INSERT_ENOSPC:
 747                 ret = -ENOSPC;
 748                 break;
 749         case BTREE_INSERT_NEED_MARK_REPLICAS:
 750                 bch2_trans_unlock(trans);
 751
 752                 trans_for_each_update_iter(trans, i) {
 753                         ret = bch2_mark_bkey_replicas(c, bkey_i_to_s_c(i->k));
 754                         if (ret)
 755                                 return ret;
 756                 }
 757
 758                 if (bch2_trans_relock(trans))
 759                         return 0;
 760
 761                 trace_trans_restart_mark_replicas(trans->ip);
 762                 ret = -EINTR;
 763                 break;
 764         case BTREE_INSERT_NEED_JOURNAL_RES:
 765                 bch2_trans_unlock(trans);
 766
 767                 ret = bch2_trans_journal_res_get(trans, JOURNAL_RES_GET_CHECK);
 768                 if (ret)
 769                         return ret;
 770
 771                 if (bch2_trans_relock(trans))
 772                         return 0;
 773
 774                 trace_trans_restart_journal_res_get(trans->ip);
 775                 ret = -EINTR;
 776                 break;
 777         default:
 778                 BUG_ON(ret >= 0);
 779                 break;
 780         }
 781
 782         if (ret == -EINTR) {
 783                 int ret2 = bch2_btree_iter_traverse_all(trans);
 784
 785                 if (ret2) {
 786                         trace_trans_restart_traverse(trans->ip);
 787                         return ret2;
 788                 }
 789
 790                 /*
 791                  * BTREE_ITER_ATOMIC means we have to return -EINTR if we
 792                  * dropped locks:
 793                  */
 794                 if (!(flags & BTREE_INSERT_ATOMIC))
 795                         return 0;
 796
 797                 trace_trans_restart_atomic(trans->ip);
 798         }
 799
 800         return ret;
 801 }
 802
 803 /**
 804  * __bch_btree_insert_at - insert keys at given iterator positions
 805  *
 806  * This is main entry point for btree updates.
 807  *
 808  * Return values:
 809  * -EINTR: locking changed, this function should be called again. Only returned
 810  *  if passed BTREE_INSERT_ATOMIC.
 811  * -EROFS: filesystem read only
 812  * -EIO: journal or btree node IO error
 813  */
 814 static int __bch2_trans_commit(struct btree_trans *trans,
 815                                struct btree_insert_entry **stopped_at)
 816 {
 817         struct bch_fs *c = trans->c;
 818         struct btree_insert_entry *i;
 819         int ret;
 820
 821         trans_for_each_update_iter(trans, i) {
 822                 if (!bch2_btree_iter_upgrade(i->iter, 1)) {
 823                         trace_trans_restart_upgrade(trans->ip);
 824                         ret = -EINTR;
 825                         goto err;
 826                 }
 827
 828                 ret = btree_iter_err(i->iter);
 829                 if (ret)
 830                         goto err;
 831         }
 832
 833         ret = do_btree_insert_at(trans, stopped_at);
 834         if (unlikely(ret))
 835                 goto err;
 836
 837         if (trans->flags & BTREE_INSERT_NOUNLOCK)
 838                 trans->nounlock = true;
 839
 840         trans_for_each_update_leaf(trans, i)
 841                 bch2_foreground_maybe_merge(c, i->iter, 0, trans->flags);
 842
 843         trans->nounlock = false;
 844
 845         trans_for_each_update_iter(trans, i)
 846                 bch2_btree_iter_downgrade(i->iter);
 847 err:
 848         /* make sure we didn't drop or screw up locks: */
 849         bch2_btree_trans_verify_locks(trans);
 850
 851         return ret;
 852 }
 853
 854 int bch2_trans_commit(struct btree_trans *trans,
 855                       struct disk_reservation *disk_res,
 856                       u64 *journal_seq,
 857                       unsigned flags)
 858 {
 859         struct bch_fs *c = trans->c;
 860         struct btree_insert_entry *i = NULL;
 861         unsigned orig_mem_top = trans->mem_top;
 862         int ret = 0;
 863
 864         if (!trans->nr_updates)
 865                 goto out_noupdates;
 866
 867         /* for the sake of sanity: */
 868         BUG_ON(trans->nr_updates > 1 && !(flags & BTREE_INSERT_ATOMIC));
 869
 870         if (flags & BTREE_INSERT_GC_LOCK_HELD)
 871                 lockdep_assert_held(&c->gc_lock);
 872
 873         if (!trans->commit_start)
 874                 trans->commit_start = local_clock();
 875
 876         memset(&trans->journal_res, 0, sizeof(trans->journal_res));
 877         memset(&trans->journal_preres, 0, sizeof(trans->journal_preres));
 878         trans->disk_res         = disk_res;
 879         trans->journal_seq      = journal_seq;
 880         trans->flags            = flags;
 881
 882         if (unlikely(!(trans->flags & BTREE_INSERT_NOCHECK_RW) &&
 883                      !percpu_ref_tryget(&c->writes))) {
 884                 if (likely(!(trans->flags & BTREE_INSERT_LAZY_RW)))
 885                         return -EROFS;
 886
 887                 bch2_trans_unlock(trans);
 888
 889                 ret = bch2_fs_read_write_early(c);
 890                 if (ret)
 891                         return ret;
 892
 893                 percpu_ref_get(&c->writes);
 894
 895                 if (!bch2_trans_relock(trans)) {
 896                         ret = -EINTR;
 897                         goto err;
 898                 }
 899         }
 900 retry:
 901         ret = bch2_trans_journal_preres_get(trans);
 902         if (ret)
 903                 goto err;
 904
 905         ret = __bch2_trans_commit(trans, &i);
 906         if (ret)
 907                 goto err;
 908 out:
 909         bch2_journal_preres_put(&c->journal, &trans->journal_preres);
 910
 911         if (unlikely(!(trans->flags & BTREE_INSERT_NOCHECK_RW)))
 912                 percpu_ref_put(&c->writes);
 913 out_noupdates:
 914         if (!ret && trans->commit_start) {
 915                 bch2_time_stats_update(&c->times[BCH_TIME_btree_update],
 916                                        trans->commit_start);
 917                 trans->commit_start = 0;
 918         }
 919
 920         BUG_ON(!(trans->flags & BTREE_INSERT_ATOMIC) && ret == -EINTR);
 921
 922         if (!ret) {
 923                 bch2_trans_unlink_iters(trans, ~trans->iters_touched|
 924                                         trans->iters_unlink_on_commit);
 925                 trans->iters_touched = 0;
 926         }
 927         trans->nr_updates       = 0;
 928         trans->mem_top          = 0;
 929
 930         return ret;
 931 err:
 932         ret = bch2_trans_commit_error(trans, i, ret);
 933
 934         /* can't loop if it was passed in and we changed it: */
 935         if (unlikely(trans->flags & BTREE_INSERT_NO_CLEAR_REPLICAS) && !ret)
 936                 ret = -EINTR;
 937
 938         if (!ret) {
 939                 /* free memory used by triggers, they'll be reexecuted: */
 940                 trans->mem_top = orig_mem_top;
 941                 goto retry;
 942         }
 943
 944         goto out;
 945 }
 946
 947 struct btree_insert_entry *bch2_trans_update(struct btree_trans *trans,
 948                                              struct btree_insert_entry entry)
 949 {
 950         struct btree_insert_entry *i;
 951
 952         BUG_ON(trans->nr_updates >= trans->nr_iters + 4);
 953
 954         for (i = trans->updates;
 955              i < trans->updates + trans->nr_updates;
 956              i++)
 957                 if (btree_trans_cmp(entry, *i) < 0)
 958                         break;
 959
 960         memmove(&i[1], &i[0],
 961                 (void *) &trans->updates[trans->nr_updates] - (void *) i);
 962         trans->nr_updates++;
 963         *i = entry;
 964         return i;
 965 }
 966
 967 /**
 968  * bch2_btree_insert - insert keys into the extent btree
 969  * @c:                  pointer to struct bch_fs
 970  * @id:                 btree to insert into
 971  * @insert_keys:        list of keys to insert
 972  * @hook:               insert callback
 973  */
 974 int bch2_btree_insert(struct bch_fs *c, enum btree_id id,
 975                      struct bkey_i *k,
 976                      struct disk_reservation *disk_res,
 977                      u64 *journal_seq, int flags)
 978 {
 979         struct btree_trans trans;
 980         struct btree_iter *iter;
 981         int ret;
 982
 983         bch2_trans_init(&trans, c, 0, 0);
 984 retry:
 985         bch2_trans_begin(&trans);
 986
 987         iter = bch2_trans_get_iter(&trans, id, bkey_start_pos(&k->k),
 988                                    BTREE_ITER_INTENT);
 989
 990         bch2_trans_update(&trans, BTREE_INSERT_ENTRY(iter, k));
 991
 992         ret = bch2_trans_commit(&trans, disk_res, journal_seq, flags);
 993         if (ret == -EINTR)
 994                 goto retry;
 995         bch2_trans_exit(&trans);
 996
 997         return ret;
 998 }
 999
1000 int bch2_btree_delete_at_range(struct btree_trans *trans,
1001                                struct btree_iter *iter,
1002                                struct bpos end,
1003                                u64 *journal_seq)
1004 {
1005         struct bkey_s_c k;
1006         int ret = 0;
1007 retry:
1008         while ((k = bch2_btree_iter_peek(iter)).k &&
1009                !(ret = bkey_err(k)) &&
1010                bkey_cmp(iter->pos, end) < 0) {
1011                 struct bkey_i delete;
1012
1013                 bkey_init(&delete.k);
1014
1015                 /*
1016                  * For extents, iter.pos won't necessarily be the same as
1017                  * bkey_start_pos(k.k) (for non extents they always will be the
1018                  * same). It's important that we delete starting from iter.pos
1019                  * because the range we want to delete could start in the middle
1020                  * of k.
1021                  *
1022                  * (bch2_btree_iter_peek() does guarantee that iter.pos >=
1023                  * bkey_start_pos(k.k)).
1024                  */
1025                 delete.k.p = iter->pos;
1026
1027                 if (iter->flags & BTREE_ITER_IS_EXTENTS) {
1028                         unsigned max_sectors =
1029                                 KEY_SIZE_MAX & (~0 << trans->c->block_bits);
1030
1031                         /* create the biggest key we can */
1032                         bch2_key_resize(&delete.k, max_sectors);
1033                         bch2_cut_back(end, &delete.k);
1034
1035                         ret = bch2_extent_trim_atomic(&delete, iter);
1036                         if (ret)
1037                                 break;
1038                 }
1039
1040                 bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &delete));
1041                 ret = bch2_trans_commit(trans, NULL, journal_seq,
1042                                         BTREE_INSERT_ATOMIC|
1043                                         BTREE_INSERT_NOFAIL);
1044                 if (ret)
1045                         break;
1046
1047                 bch2_trans_cond_resched(trans);
1048         }
1049
1050         if (ret == -EINTR) {
1051                 ret = 0;
1052                 goto retry;
1053         }
1054
1055         return ret;
1056
1057 }
1058
1059 int bch2_btree_delete_at(struct btree_trans *trans,
1060                          struct btree_iter *iter, unsigned flags)
1061 {
1062         struct bkey_i k;
1063
1064         bkey_init(&k.k);
1065         k.k.p = iter->pos;
1066
1067         bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &k));
1068         return bch2_trans_commit(trans, NULL, NULL,
1069                                  BTREE_INSERT_NOFAIL|
1070                                  BTREE_INSERT_USE_RESERVE|flags);
1071 }
1072
1073 /*
1074  * bch_btree_delete_range - delete everything within a given range
1075  *
1076  * Range is a half open interval - [start, end)
1077  */
1078 int bch2_btree_delete_range(struct bch_fs *c, enum btree_id id,
1079                             struct bpos start, struct bpos end,
1080                             u64 *journal_seq)
1081 {
1082         struct btree_trans trans;
1083         struct btree_iter *iter;
1084         int ret = 0;
1085
1086         /*
1087          * XXX: whether we need mem/more iters depends on whether this btree id
1088          * has triggers
1089          */
1090         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 512);
1091
1092         iter = bch2_trans_get_iter(&trans, id, start, BTREE_ITER_INTENT);
1093
1094         ret = bch2_btree_delete_at_range(&trans, iter, end, journal_seq);
1095         ret = bch2_trans_exit(&trans) ?: ret;
1096
1097         BUG_ON(ret == -EINTR);
1098         return ret;
1099 }