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                         !bch2_extent_is_atomic(i->k, i->iter));
 404
 405                 EBUG_ON((i->iter->flags & BTREE_ITER_IS_EXTENTS) &&
 406                         !(trans->flags & BTREE_INSERT_ATOMIC));
 407         }
 408
 409         BUG_ON(debug_check_bkeys(c) &&
 410                !bkey_deleted(&i->k->k) &&
 411                bch2_bkey_invalid(c, bkey_i_to_s_c(i->k), btree_id));
 412 }
 413
 414 static int bch2_trans_journal_preres_get(struct btree_trans *trans)
 415 {
 416         struct bch_fs *c = trans->c;
 417         struct btree_insert_entry *i;
 418         unsigned u64s = 0;
 419         int ret;
 420
 421         trans_for_each_update(trans, i)
 422                 if (i->deferred)
 423                         u64s += jset_u64s(i->k->k.u64s);
 424
 425         if (!u64s)
 426                 return 0;
 427
 428         ret = bch2_journal_preres_get(&c->journal,
 429                         &trans->journal_preres, u64s,
 430                         JOURNAL_RES_GET_NONBLOCK);
 431         if (ret != -EAGAIN)
 432                 return ret;
 433
 434         bch2_trans_unlock(trans);
 435
 436         ret = bch2_journal_preres_get(&c->journal,
 437                         &trans->journal_preres, u64s, 0);
 438         if (ret)
 439                 return ret;
 440
 441         if (!bch2_trans_relock(trans)) {
 442                 trace_trans_restart_journal_preres_get(trans->ip);
 443                 return -EINTR;
 444         }
 445
 446         return 0;
 447 }
 448
 449 static int bch2_trans_journal_res_get(struct btree_trans *trans,
 450                                       unsigned flags)
 451 {
 452         struct bch_fs *c = trans->c;
 453         int ret;
 454
 455         if (trans->flags & BTREE_INSERT_JOURNAL_RESERVED)
 456                 flags |= JOURNAL_RES_GET_RESERVED;
 457
 458         ret = bch2_journal_res_get(&c->journal, &trans->journal_res,
 459                                    trans->journal_u64s, flags);
 460
 461         return ret == -EAGAIN ? BTREE_INSERT_NEED_JOURNAL_RES : ret;
 462 }
 463
 464 static enum btree_insert_ret
 465 btree_key_can_insert(struct btree_trans *trans,
 466                      struct btree_insert_entry *insert,
 467                      unsigned *u64s)
 468 {
 469         struct bch_fs *c = trans->c;
 470         struct btree *b = insert->iter->l[0].b;
 471         static enum btree_insert_ret ret;
 472
 473         if (unlikely(btree_node_fake(b)))
 474                 return BTREE_INSERT_BTREE_NODE_FULL;
 475
 476         ret = !btree_node_is_extents(b)
 477                 ? BTREE_INSERT_OK
 478                 : bch2_extent_can_insert(trans, insert, u64s);
 479         if (ret)
 480                 return ret;
 481
 482         if (*u64s > bch_btree_keys_u64s_remaining(c, b))
 483                 return BTREE_INSERT_BTREE_NODE_FULL;
 484
 485         return BTREE_INSERT_OK;
 486 }
 487
 488 static int btree_trans_check_can_insert(struct btree_trans *trans,
 489                                         struct btree_insert_entry **stopped_at)
 490 {
 491         struct btree_insert_entry *i;
 492         unsigned u64s = 0;
 493         int ret;
 494
 495         trans_for_each_update_iter(trans, i) {
 496                 /* Multiple inserts might go to same leaf: */
 497                 if (!same_leaf_as_prev(trans, i))
 498                         u64s = 0;
 499
 500                 u64s += i->k->k.u64s;
 501                 ret = btree_key_can_insert(trans, i, &u64s);
 502                 if (ret) {
 503                         *stopped_at = i;
 504                         return ret;
 505                 }
 506         }
 507
 508         return 0;
 509 }
 510
 511 static inline void do_btree_insert_one(struct btree_trans *trans,
 512                                        struct btree_insert_entry *insert)
 513 {
 514         if (likely(!insert->deferred))
 515                 btree_insert_key_leaf(trans, insert);
 516         else
 517                 btree_insert_key_deferred(trans, insert);
 518 }
 519
 520 static inline bool update_triggers_transactional(struct btree_trans *trans,
 521                                                  struct btree_insert_entry *i)
 522 {
 523         return likely(!(trans->flags & BTREE_INSERT_MARK_INMEM)) &&
 524                 (i->iter->btree_id == BTREE_ID_EXTENTS ||
 525                  i->iter->btree_id == BTREE_ID_INODES);
 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         btree_trans_lock_write(c, trans);
 579
 580         if (race_fault()) {
 581                 ret = -EINTR;
 582                 trace_trans_restart_fault_inject(trans->ip);
 583                 goto out;
 584         }
 585
 586         /*
 587          * Check if the insert will fit in the leaf node with the write lock
 588          * held, otherwise another thread could write the node changing the
 589          * amount of space available:
 590          */
 591         ret = btree_trans_check_can_insert(trans, stopped_at);
 592         if (ret)
 593                 goto out;
 594
 595         trans_for_each_update_iter(trans, i) {
 596                 if (i->deferred ||
 597                     !btree_node_type_needs_gc(i->iter->btree_id))
 598                         continue;
 599
 600                 if (!fs_usage) {
 601                         percpu_down_read(&c->mark_lock);
 602                         fs_usage = bch2_fs_usage_scratch_get(c);
 603                 }
 604
 605                 if (!bch2_bkey_replicas_marked_locked(c,
 606                         bkey_i_to_s_c(i->k), true)) {
 607                         ret = BTREE_INSERT_NEED_MARK_REPLICAS;
 608                         goto out;
 609                 }
 610         }
 611
 612         /*
 613          * Don't get journal reservation until after we know insert will
 614          * succeed:
 615          */
 616         if (likely(!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY))) {
 617                 trans->journal_u64s = 0;
 618
 619                 trans_for_each_update(trans, i)
 620                         trans->journal_u64s += jset_u64s(i->k->k.u64s);
 621
 622                 ret = bch2_trans_journal_res_get(trans, JOURNAL_RES_GET_NONBLOCK);
 623                 if (ret)
 624                         goto out;
 625         }
 626
 627         if (!(trans->flags & BTREE_INSERT_JOURNAL_REPLAY)) {
 628                 if (journal_seq_verify(c))
 629                         trans_for_each_update(trans, i)
 630                                 i->k->k.version.lo = trans->journal_res.seq;
 631                 else if (inject_invalid_keys(c))
 632                         trans_for_each_update(trans, i)
 633                                 i->k->k.version = MAX_VERSION;
 634         }
 635
 636         trans_for_each_update_iter(trans, i)
 637                 if (update_has_triggers(trans, i) &&
 638                     !update_triggers_transactional(trans, i))
 639                         bch2_mark_update(trans, i, fs_usage, mark_flags);
 640
 641         if (fs_usage && trans->fs_usage_deltas)
 642                 bch2_replicas_delta_list_apply(c, fs_usage,
 643                                                trans->fs_usage_deltas);
 644
 645         if (fs_usage)
 646                 bch2_trans_fs_usage_apply(trans, fs_usage);
 647
 648         if (likely(!(trans->flags & BTREE_INSERT_NOMARK)) &&
 649             unlikely(c->gc_pos.phase))
 650                 trans_for_each_update_iter(trans, i)
 651                         if (gc_visited(c, gc_pos_btree_node(i->iter->l[0].b)))
 652                                 bch2_mark_update(trans, i, NULL,
 653                                                  mark_flags|
 654                                                  BCH_BUCKET_MARK_GC);
 655
 656         trans_for_each_update(trans, i)
 657                 do_btree_insert_one(trans, i);
 658 out:
 659         BUG_ON(ret &&
 660                (trans->flags & BTREE_INSERT_JOURNAL_RESERVED) &&
 661                trans->journal_res.ref);
 662
 663         btree_trans_unlock_write(trans);
 664
 665         if (fs_usage) {
 666                 bch2_fs_usage_scratch_put(c, fs_usage);
 667                 percpu_up_read(&c->mark_lock);
 668         }
 669
 670         bch2_journal_res_put(&c->journal, &trans->journal_res);
 671 out_clear_replicas:
 672         if (trans->fs_usage_deltas) {
 673                 memset(&trans->fs_usage_deltas->fs_usage, 0,
 674                        sizeof(trans->fs_usage_deltas->fs_usage));
 675                 trans->fs_usage_deltas->used = 0;
 676         }
 677
 678         return ret;
 679 }
 680
 681 static noinline
 682 int bch2_trans_commit_error(struct btree_trans *trans,
 683                             struct btree_insert_entry *i,
 684                             int ret)
 685 {
 686         struct bch_fs *c = trans->c;
 687         unsigned flags = trans->flags;
 688         struct btree_insert_entry *src, *dst;
 689
 690         src = dst = trans->updates;
 691
 692         while (src < trans->updates + trans->nr_updates) {
 693                 if (!src->triggered) {
 694                         *dst = *src;
 695                         dst++;
 696                 }
 697                 src++;
 698         }
 699
 700         trans->nr_updates = dst - trans->updates;
 701
 702         /*
 703          * BTREE_INSERT_NOUNLOCK means don't unlock _after_ successful btree
 704          * update; if we haven't done anything yet it doesn't apply
 705          */
 706         flags &= ~BTREE_INSERT_NOUNLOCK;
 707
 708         switch (ret) {
 709         case BTREE_INSERT_BTREE_NODE_FULL:
 710                 ret = bch2_btree_split_leaf(c, i->iter, flags);
 711
 712                 /*
 713                  * if the split succeeded without dropping locks the insert will
 714                  * still be atomic (in the BTREE_INSERT_ATOMIC sense, what the
 715                  * caller peeked() and is overwriting won't have changed)
 716                  */
 717 #if 0
 718                 /*
 719                  * XXX:
 720                  * split -> btree node merging (of parent node) might still drop
 721                  * locks when we're not passing it BTREE_INSERT_NOUNLOCK
 722                  *
 723                  * we don't want to pass BTREE_INSERT_NOUNLOCK to split as that
 724                  * will inhibit merging - but we don't have a reliable way yet
 725                  * (do we?) of checking if we dropped locks in this path
 726                  */
 727                 if (!ret)
 728                         goto retry;
 729 #endif
 730
 731                 /*
 732                  * don't care if we got ENOSPC because we told split it
 733                  * couldn't block:
 734                  */
 735                 if (!ret ||
 736                     ret == -EINTR ||
 737                     (flags & BTREE_INSERT_NOUNLOCK)) {
 738                         trace_trans_restart_btree_node_split(trans->ip);
 739                         ret = -EINTR;
 740                 }
 741                 break;
 742         case BTREE_INSERT_ENOSPC:
 743                 ret = -ENOSPC;
 744                 break;
 745         case BTREE_INSERT_NEED_MARK_REPLICAS:
 746                 bch2_trans_unlock(trans);
 747
 748                 trans_for_each_update_iter(trans, i) {
 749                         ret = bch2_mark_bkey_replicas(c, bkey_i_to_s_c(i->k));
 750                         if (ret)
 751                                 return ret;
 752                 }
 753
 754                 if (bch2_trans_relock(trans))
 755                         return 0;
 756
 757                 trace_trans_restart_mark_replicas(trans->ip);
 758                 ret = -EINTR;
 759                 break;
 760         case BTREE_INSERT_NEED_JOURNAL_RES:
 761                 bch2_trans_unlock(trans);
 762
 763                 ret = bch2_trans_journal_res_get(trans, JOURNAL_RES_GET_CHECK);
 764                 if (ret)
 765                         return ret;
 766
 767                 if (bch2_trans_relock(trans))
 768                         return 0;
 769
 770                 trace_trans_restart_journal_res_get(trans->ip);
 771                 ret = -EINTR;
 772                 break;
 773         default:
 774                 BUG_ON(ret >= 0);
 775                 break;
 776         }
 777
 778         if (ret == -EINTR) {
 779                 int ret2 = bch2_btree_iter_traverse_all(trans);
 780
 781                 if (ret2) {
 782                         trace_trans_restart_traverse(trans->ip);
 783                         return ret2;
 784                 }
 785
 786                 /*
 787                  * BTREE_ITER_ATOMIC means we have to return -EINTR if we
 788                  * dropped locks:
 789                  */
 790                 if (!(flags & BTREE_INSERT_ATOMIC))
 791                         return 0;
 792
 793                 trace_trans_restart_atomic(trans->ip);
 794         }
 795
 796         return ret;
 797 }
 798
 799 /**
 800  * __bch_btree_insert_at - insert keys at given iterator positions
 801  *
 802  * This is main entry point for btree updates.
 803  *
 804  * Return values:
 805  * -EINTR: locking changed, this function should be called again. Only returned
 806  *  if passed BTREE_INSERT_ATOMIC.
 807  * -EROFS: filesystem read only
 808  * -EIO: journal or btree node IO error
 809  */
 810 static int __bch2_trans_commit(struct btree_trans *trans,
 811                                struct btree_insert_entry **stopped_at)
 812 {
 813         struct bch_fs *c = trans->c;
 814         struct btree_insert_entry *i;
 815         int ret;
 816
 817         trans_for_each_update_iter(trans, i) {
 818                 if (!bch2_btree_iter_upgrade(i->iter, 1)) {
 819                         trace_trans_restart_upgrade(trans->ip);
 820                         ret = -EINTR;
 821                         goto err;
 822                 }
 823
 824                 ret = btree_iter_err(i->iter);
 825                 if (ret)
 826                         goto err;
 827         }
 828
 829         ret = do_btree_insert_at(trans, stopped_at);
 830         if (unlikely(ret))
 831                 goto err;
 832
 833         if (trans->flags & BTREE_INSERT_NOUNLOCK)
 834                 trans->nounlock = true;
 835
 836         trans_for_each_update_leaf(trans, i)
 837                 bch2_foreground_maybe_merge(c, i->iter, 0, trans->flags);
 838
 839         trans->nounlock = false;
 840
 841         trans_for_each_update_iter(trans, i)
 842                 bch2_btree_iter_downgrade(i->iter);
 843 err:
 844         /* make sure we didn't drop or screw up locks: */
 845         bch2_btree_trans_verify_locks(trans);
 846
 847         return ret;
 848 }
 849
 850 int bch2_trans_commit(struct btree_trans *trans,
 851                       struct disk_reservation *disk_res,
 852                       u64 *journal_seq,
 853                       unsigned flags)
 854 {
 855         struct bch_fs *c = trans->c;
 856         struct btree_insert_entry *i;
 857         unsigned orig_mem_top = trans->mem_top;
 858         int ret = 0;
 859
 860         if (!trans->nr_updates)
 861                 goto out_noupdates;
 862
 863         /* for the sake of sanity: */
 864         BUG_ON(trans->nr_updates > 1 && !(flags & BTREE_INSERT_ATOMIC));
 865
 866         if (flags & BTREE_INSERT_GC_LOCK_HELD)
 867                 lockdep_assert_held(&c->gc_lock);
 868
 869         if (!trans->commit_start)
 870                 trans->commit_start = local_clock();
 871
 872         memset(&trans->journal_res, 0, sizeof(trans->journal_res));
 873         memset(&trans->journal_preres, 0, sizeof(trans->journal_preres));
 874         trans->disk_res         = disk_res;
 875         trans->journal_seq      = journal_seq;
 876         trans->flags            = flags;
 877
 878         trans_for_each_update(trans, i)
 879                 btree_insert_entry_checks(trans, i);
 880         bch2_btree_trans_verify_locks(trans);
 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         } else {
 927                 bch2_trans_unlink_iters(trans, trans->iters_unlink_on_commit);
 928         }
 929         trans->nr_updates       = 0;
 930         trans->mem_top          = 0;
 931
 932         return ret;
 933 err:
 934         ret = bch2_trans_commit_error(trans, i, ret);
 935
 936         /* can't loop if it was passed in and we changed it: */
 937         if (unlikely(trans->flags & BTREE_INSERT_NO_CLEAR_REPLICAS) && !ret)
 938                 ret = -EINTR;
 939
 940         if (!ret) {
 941                 /* free memory used by triggers, they'll be reexecuted: */
 942                 trans->mem_top = orig_mem_top;
 943                 goto retry;
 944         }
 945
 946         goto out;
 947 }
 948
 949 struct btree_insert_entry *bch2_trans_update(struct btree_trans *trans,
 950                                              struct btree_insert_entry entry)
 951 {
 952         struct btree_insert_entry *i;
 953
 954         BUG_ON(trans->nr_updates >= trans->nr_iters + 4);
 955
 956         for (i = trans->updates;
 957              i < trans->updates + trans->nr_updates;
 958              i++)
 959                 if (btree_trans_cmp(entry, *i) < 0)
 960                         break;
 961
 962         memmove(&i[1], &i[0],
 963                 (void *) &trans->updates[trans->nr_updates] - (void *) i);
 964         trans->nr_updates++;
 965         *i = entry;
 966         return i;
 967 }
 968
 969 /**
 970  * bch2_btree_insert - insert keys into the extent btree
 971  * @c:                  pointer to struct bch_fs
 972  * @id:                 btree to insert into
 973  * @insert_keys:        list of keys to insert
 974  * @hook:               insert callback
 975  */
 976 int bch2_btree_insert(struct bch_fs *c, enum btree_id id,
 977                      struct bkey_i *k,
 978                      struct disk_reservation *disk_res,
 979                      u64 *journal_seq, int flags)
 980 {
 981         struct btree_trans trans;
 982         struct btree_iter *iter;
 983         int ret;
 984
 985         bch2_trans_init(&trans, c, 0, 0);
 986 retry:
 987         bch2_trans_begin(&trans);
 988
 989         iter = bch2_trans_get_iter(&trans, id, bkey_start_pos(&k->k),
 990                                    BTREE_ITER_INTENT);
 991
 992         bch2_trans_update(&trans, BTREE_INSERT_ENTRY(iter, k));
 993
 994         ret = bch2_trans_commit(&trans, disk_res, journal_seq, flags);
 995         if (ret == -EINTR)
 996                 goto retry;
 997         bch2_trans_exit(&trans);
 998
 999         return ret;
1000 }
1001
1002 int bch2_btree_delete_at_range(struct btree_trans *trans,
1003                                struct btree_iter *iter,
1004                                struct bpos end,
1005                                u64 *journal_seq)
1006 {
1007         struct bkey_s_c k;
1008         int ret = 0;
1009 retry:
1010         while ((k = bch2_btree_iter_peek(iter)).k &&
1011                !(ret = bkey_err(k)) &&
1012                bkey_cmp(iter->pos, end) < 0) {
1013                 struct bkey_i delete;
1014
1015                 bkey_init(&delete.k);
1016
1017                 /*
1018                  * For extents, iter.pos won't necessarily be the same as
1019                  * bkey_start_pos(k.k) (for non extents they always will be the
1020                  * same). It's important that we delete starting from iter.pos
1021                  * because the range we want to delete could start in the middle
1022                  * of k.
1023                  *
1024                  * (bch2_btree_iter_peek() does guarantee that iter.pos >=
1025                  * bkey_start_pos(k.k)).
1026                  */
1027                 delete.k.p = iter->pos;
1028
1029                 if (iter->flags & BTREE_ITER_IS_EXTENTS) {
1030                         unsigned max_sectors =
1031                                 KEY_SIZE_MAX & (~0 << trans->c->block_bits);
1032
1033                         /* create the biggest key we can */
1034                         bch2_key_resize(&delete.k, max_sectors);
1035                         bch2_cut_back(end, &delete.k);
1036                         bch2_extent_trim_atomic(&delete, iter);
1037                 }
1038
1039                 bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &delete));
1040                 ret = bch2_trans_commit(trans, NULL, journal_seq,
1041                                         BTREE_INSERT_ATOMIC|
1042                                         BTREE_INSERT_NOFAIL);
1043                 if (ret)
1044                         break;
1045
1046                 bch2_trans_cond_resched(trans);
1047         }
1048
1049         if (ret == -EINTR) {
1050                 ret = 0;
1051                 goto retry;
1052         }
1053
1054         return ret;
1055
1056 }
1057
1058 int bch2_btree_delete_at(struct btree_trans *trans,
1059                          struct btree_iter *iter, unsigned flags)
1060 {
1061         struct bkey_i k;
1062
1063         bkey_init(&k.k);
1064         k.k.p = iter->pos;
1065
1066         bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &k));
1067         return bch2_trans_commit(trans, NULL, NULL,
1068                                  BTREE_INSERT_NOFAIL|
1069                                  BTREE_INSERT_USE_RESERVE|flags);
1070 }
1071
1072 /*
1073  * bch_btree_delete_range - delete everything within a given range
1074  *
1075  * Range is a half open interval - [start, end)
1076  */
1077 int bch2_btree_delete_range(struct bch_fs *c, enum btree_id id,
1078                             struct bpos start, struct bpos end,
1079                             u64 *journal_seq)
1080 {
1081         struct btree_trans trans;
1082         struct btree_iter *iter;
1083         int ret = 0;
1084
1085         /*
1086          * XXX: whether we need mem/more iters depends on whether this btree id
1087          * has triggers
1088          */
1089         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 512);
1090
1091         iter = bch2_trans_get_iter(&trans, id, start, BTREE_ITER_INTENT);
1092
1093         ret = bch2_btree_delete_at_range(&trans, iter, end, journal_seq);
1094         ret = bch2_trans_exit(&trans) ?: ret;
1095
1096         BUG_ON(ret == -EINTR);
1097         return ret;
1098 }