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

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