btree.c (05335cff9f01555b769ac97b7bacc472b7ed047a) btree.c (2a285686c109816ba71a00b9278262cf02648258)
1/*
2 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
3 *
4 * Uses a block device as cache for other block devices; optimized for SSDs.
5 * All allocation is done in buckets, which should match the erase block size
6 * of the device.
7 *
8 * Buckets containing cached data are kept on a heap sorted by priority;

--- 153 unchanged lines hidden (view full) ---

162 _r; \
163})
164
165static inline struct bset *write_block(struct btree *b)
166{
167 return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
168}
169
1/*
2 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
3 *
4 * Uses a block device as cache for other block devices; optimized for SSDs.
5 * All allocation is done in buckets, which should match the erase block size
6 * of the device.
7 *
8 * Buckets containing cached data are kept on a heap sorted by priority;

--- 153 unchanged lines hidden (view full) ---

162 _r; \
163})
164
165static inline struct bset *write_block(struct btree *b)
166{
167 return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
168}
169
170static void bch_btree_init_next(struct btree *b)
171{
172 /* If not a leaf node, always sort */
173 if (b->level && b->keys.nsets)
174 bch_btree_sort(&b->keys, &b->c->sort);
175 else
176 bch_btree_sort_lazy(&b->keys, &b->c->sort);
177
178 if (b->written < btree_blocks(b))
179 bch_bset_init_next(&b->keys, write_block(b),
180 bset_magic(&b->c->sb));
181
182}
183
170/* Btree key manipulation */
171
172void bkey_put(struct cache_set *c, struct bkey *k)
173{
174 unsigned i;
175
176 for (i = 0; i < KEY_PTRS(k); i++)
177 if (ptr_available(c, k, i))

--- 255 unchanged lines hidden (view full) ---

433
434 bch_submit_bbio(b->bio, b->c, &k.key, 0);
435
436 closure_sync(cl);
437 continue_at_nobarrier(cl, __btree_node_write_done, NULL);
438 }
439}
440
184/* Btree key manipulation */
185
186void bkey_put(struct cache_set *c, struct bkey *k)
187{
188 unsigned i;
189
190 for (i = 0; i < KEY_PTRS(k); i++)
191 if (ptr_available(c, k, i))

--- 255 unchanged lines hidden (view full) ---

447
448 bch_submit_bbio(b->bio, b->c, &k.key, 0);
449
450 closure_sync(cl);
451 continue_at_nobarrier(cl, __btree_node_write_done, NULL);
452 }
453}
454
441void bch_btree_node_write(struct btree *b, struct closure *parent)
455void __bch_btree_node_write(struct btree *b, struct closure *parent)
442{
443 struct bset *i = btree_bset_last(b);
444
456{
457 struct bset *i = btree_bset_last(b);
458
459 lockdep_assert_held(&b->write_lock);
460
445 trace_bcache_btree_write(b);
446
447 BUG_ON(current->bio_list);
448 BUG_ON(b->written >= btree_blocks(b));
449 BUG_ON(b->written && !i->keys);
450 BUG_ON(btree_bset_first(b)->seq != i->seq);
451 bch_check_keys(&b->keys, "writing");
452

--- 7 unchanged lines hidden (view full) ---

460 change_bit(BTREE_NODE_write_idx, &b->flags);
461
462 do_btree_node_write(b);
463
464 atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size,
465 &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written);
466
467 b->written += set_blocks(i, block_bytes(b->c));
461 trace_bcache_btree_write(b);
462
463 BUG_ON(current->bio_list);
464 BUG_ON(b->written >= btree_blocks(b));
465 BUG_ON(b->written && !i->keys);
466 BUG_ON(btree_bset_first(b)->seq != i->seq);
467 bch_check_keys(&b->keys, "writing");
468

--- 7 unchanged lines hidden (view full) ---

476 change_bit(BTREE_NODE_write_idx, &b->flags);
477
478 do_btree_node_write(b);
479
480 atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size,
481 &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written);
482
483 b->written += set_blocks(i, block_bytes(b->c));
484}
468
485
469 /* If not a leaf node, always sort */
470 if (b->level && b->keys.nsets)
471 bch_btree_sort(&b->keys, &b->c->sort);
472 else
473 bch_btree_sort_lazy(&b->keys, &b->c->sort);
486void bch_btree_node_write(struct btree *b, struct closure *parent)
487{
488 unsigned nsets = b->keys.nsets;
474
489
490 lockdep_assert_held(&b->lock);
491
492 __bch_btree_node_write(b, parent);
493
475 /*
476 * do verify if there was more than one set initially (i.e. we did a
477 * sort) and we sorted down to a single set:
478 */
494 /*
495 * do verify if there was more than one set initially (i.e. we did a
496 * sort) and we sorted down to a single set:
497 */
479 if (i != b->keys.set->data && !b->keys.nsets)
498 if (nsets && !b->keys.nsets)
480 bch_btree_verify(b);
481
499 bch_btree_verify(b);
500
482 if (b->written < btree_blocks(b))
483 bch_bset_init_next(&b->keys, write_block(b),
484 bset_magic(&b->c->sb));
501 bch_btree_init_next(b);
485}
486
487static void bch_btree_node_write_sync(struct btree *b)
488{
489 struct closure cl;
490
491 closure_init_stack(&cl);
502}
503
504static void bch_btree_node_write_sync(struct btree *b)
505{
506 struct closure cl;
507
508 closure_init_stack(&cl);
509
510 mutex_lock(&b->write_lock);
492 bch_btree_node_write(b, &cl);
511 bch_btree_node_write(b, &cl);
512 mutex_unlock(&b->write_lock);
513
493 closure_sync(&cl);
494}
495
496static void btree_node_write_work(struct work_struct *w)
497{
498 struct btree *b = container_of(to_delayed_work(w), struct btree, work);
499
514 closure_sync(&cl);
515}
516
517static void btree_node_write_work(struct work_struct *w)
518{
519 struct btree *b = container_of(to_delayed_work(w), struct btree, work);
520
500 rw_lock(true, b, b->level);
501
521 mutex_lock(&b->write_lock);
502 if (btree_node_dirty(b))
522 if (btree_node_dirty(b))
503 bch_btree_node_write(b, NULL);
504 rw_unlock(true, b);
523 __bch_btree_node_write(b, NULL);
524 mutex_unlock(&b->write_lock);
505}
506
507static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
508{
509 struct bset *i = btree_bset_last(b);
510 struct btree_write *w = btree_current_write(b);
511
525}
526
527static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
528{
529 struct bset *i = btree_bset_last(b);
530 struct btree_write *w = btree_current_write(b);
531
532 lockdep_assert_held(&b->write_lock);
533
512 BUG_ON(!b->written);
513 BUG_ON(!i->keys);
514
515 if (!btree_node_dirty(b))
516 queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);
517
518 set_btree_node_dirty(b);
519

--- 68 unchanged lines hidden (view full) ---

588 struct bkey *k, gfp_t gfp)
589{
590 struct btree *b = kzalloc(sizeof(struct btree), gfp);
591 if (!b)
592 return NULL;
593
594 init_rwsem(&b->lock);
595 lockdep_set_novalidate_class(&b->lock);
534 BUG_ON(!b->written);
535 BUG_ON(!i->keys);
536
537 if (!btree_node_dirty(b))
538 queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);
539
540 set_btree_node_dirty(b);
541

--- 68 unchanged lines hidden (view full) ---

610 struct bkey *k, gfp_t gfp)
611{
612 struct btree *b = kzalloc(sizeof(struct btree), gfp);
613 if (!b)
614 return NULL;
615
616 init_rwsem(&b->lock);
617 lockdep_set_novalidate_class(&b->lock);
618 mutex_init(&b->write_lock);
619 lockdep_set_novalidate_class(&b->write_lock);
596 INIT_LIST_HEAD(&b->list);
597 INIT_DELAYED_WORK(&b->work, btree_node_write_work);
598 b->c = c;
599 sema_init(&b->io_mutex, 1);
600
601 mca_data_alloc(b, k, gfp);
602 return b;
603}

--- 17 unchanged lines hidden (view full) ---

621 if (btree_node_dirty(b))
622 goto out_unlock;
623
624 if (down_trylock(&b->io_mutex))
625 goto out_unlock;
626 up(&b->io_mutex);
627 }
628
620 INIT_LIST_HEAD(&b->list);
621 INIT_DELAYED_WORK(&b->work, btree_node_write_work);
622 b->c = c;
623 sema_init(&b->io_mutex, 1);
624
625 mca_data_alloc(b, k, gfp);
626 return b;
627}

--- 17 unchanged lines hidden (view full) ---

645 if (btree_node_dirty(b))
646 goto out_unlock;
647
648 if (down_trylock(&b->io_mutex))
649 goto out_unlock;
650 up(&b->io_mutex);
651 }
652
653 mutex_lock(&b->write_lock);
629 if (btree_node_dirty(b))
654 if (btree_node_dirty(b))
630 bch_btree_node_write_sync(b);
655 __bch_btree_node_write(b, &cl);
656 mutex_unlock(&b->write_lock);
631
657
658 closure_sync(&cl);
659
632 /* wait for any in flight btree write */
633 down(&b->io_mutex);
634 up(&b->io_mutex);
635
636 return 0;
637out_unlock:
638 rw_unlock(true, b);
639 return -ENOMEM;

--- 365 unchanged lines hidden (view full) ---

1005/* Btree alloc */
1006
1007static void btree_node_free(struct btree *b)
1008{
1009 trace_bcache_btree_node_free(b);
1010
1011 BUG_ON(b == b->c->root);
1012
660 /* wait for any in flight btree write */
661 down(&b->io_mutex);
662 up(&b->io_mutex);
663
664 return 0;
665out_unlock:
666 rw_unlock(true, b);
667 return -ENOMEM;

--- 365 unchanged lines hidden (view full) ---

1033/* Btree alloc */
1034
1035static void btree_node_free(struct btree *b)
1036{
1037 trace_bcache_btree_node_free(b);
1038
1039 BUG_ON(b == b->c->root);
1040
1041 mutex_lock(&b->write_lock);
1042
1013 if (btree_node_dirty(b))
1014 btree_complete_write(b, btree_current_write(b));
1015 clear_bit(BTREE_NODE_dirty, &b->flags);
1016
1043 if (btree_node_dirty(b))
1044 btree_complete_write(b, btree_current_write(b));
1045 clear_bit(BTREE_NODE_dirty, &b->flags);
1046
1047 mutex_unlock(&b->write_lock);
1048
1017 cancel_delayed_work(&b->work);
1018
1019 mutex_lock(&b->c->bucket_lock);
1020 bch_bucket_free(b->c, &b->key);
1021 mca_bucket_free(b);
1022 mutex_unlock(&b->c->bucket_lock);
1023}
1024

--- 35 unchanged lines hidden (view full) ---

1060 trace_bcache_btree_node_alloc_fail(b);
1061 return b;
1062}
1063
1064static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait)
1065{
1066 struct btree *n = bch_btree_node_alloc(b->c, b->level, wait);
1067 if (!IS_ERR_OR_NULL(n)) {
1049 cancel_delayed_work(&b->work);
1050
1051 mutex_lock(&b->c->bucket_lock);
1052 bch_bucket_free(b->c, &b->key);
1053 mca_bucket_free(b);
1054 mutex_unlock(&b->c->bucket_lock);
1055}
1056

--- 35 unchanged lines hidden (view full) ---

1092 trace_bcache_btree_node_alloc_fail(b);
1093 return b;
1094}
1095
1096static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait)
1097{
1098 struct btree *n = bch_btree_node_alloc(b->c, b->level, wait);
1099 if (!IS_ERR_OR_NULL(n)) {
1100 mutex_lock(&n->write_lock);
1068 bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
1069 bkey_copy_key(&n->key, &b->key);
1101 bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
1102 bkey_copy_key(&n->key, &b->key);
1103 mutex_unlock(&n->write_lock);
1070 }
1071
1072 return n;
1073}
1074
1075static void make_btree_freeing_key(struct btree *b, struct bkey *k)
1076{
1077 unsigned i;

--- 186 unchanged lines hidden (view full) ---

1264 return 0;
1265
1266 for (i = 0; i < nodes; i++) {
1267 new_nodes[i] = btree_node_alloc_replacement(r[i].b, false);
1268 if (IS_ERR_OR_NULL(new_nodes[i]))
1269 goto out_nocoalesce;
1270 }
1271
1104 }
1105
1106 return n;
1107}
1108
1109static void make_btree_freeing_key(struct btree *b, struct bkey *k)
1110{
1111 unsigned i;

--- 186 unchanged lines hidden (view full) ---

1298 return 0;
1299
1300 for (i = 0; i < nodes; i++) {
1301 new_nodes[i] = btree_node_alloc_replacement(r[i].b, false);
1302 if (IS_ERR_OR_NULL(new_nodes[i]))
1303 goto out_nocoalesce;
1304 }
1305
1306 for (i = 0; i < nodes; i++)
1307 mutex_lock(&new_nodes[i]->write_lock);
1308
1272 for (i = nodes - 1; i > 0; --i) {
1273 struct bset *n1 = btree_bset_first(new_nodes[i]);
1274 struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
1275 struct bkey *k, *last = NULL;
1276
1277 keys = 0;
1278
1279 if (i > 1) {

--- 50 unchanged lines hidden (view full) ---

1330 if (__bch_keylist_realloc(keylist,
1331 bkey_u64s(&new_nodes[i]->key)))
1332 goto out_nocoalesce;
1333
1334 bch_btree_node_write(new_nodes[i], &cl);
1335 bch_keylist_add(keylist, &new_nodes[i]->key);
1336 }
1337
1309 for (i = nodes - 1; i > 0; --i) {
1310 struct bset *n1 = btree_bset_first(new_nodes[i]);
1311 struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
1312 struct bkey *k, *last = NULL;
1313
1314 keys = 0;
1315
1316 if (i > 1) {

--- 50 unchanged lines hidden (view full) ---

1367 if (__bch_keylist_realloc(keylist,
1368 bkey_u64s(&new_nodes[i]->key)))
1369 goto out_nocoalesce;
1370
1371 bch_btree_node_write(new_nodes[i], &cl);
1372 bch_keylist_add(keylist, &new_nodes[i]->key);
1373 }
1374
1375 for (i = 0; i < nodes; i++)
1376 mutex_unlock(&new_nodes[i]->write_lock);
1377
1338 closure_sync(&cl);
1339
1340 /* We emptied out this node */
1341 BUG_ON(btree_bset_first(new_nodes[0])->keys);
1342 btree_node_free(new_nodes[0]);
1343 rw_unlock(true, new_nodes[0]);
1344
1345 for (i = 0; i < nodes; i++) {

--- 48 unchanged lines hidden (view full) ---

1394 ret += bkey_u64s(k);
1395
1396 return ret;
1397}
1398
1399static int btree_gc_recurse(struct btree *b, struct btree_op *op,
1400 struct closure *writes, struct gc_stat *gc)
1401{
1378 closure_sync(&cl);
1379
1380 /* We emptied out this node */
1381 BUG_ON(btree_bset_first(new_nodes[0])->keys);
1382 btree_node_free(new_nodes[0]);
1383 rw_unlock(true, new_nodes[0]);
1384
1385 for (i = 0; i < nodes; i++) {

--- 48 unchanged lines hidden (view full) ---

1434 ret += bkey_u64s(k);
1435
1436 return ret;
1437}
1438
1439static int btree_gc_recurse(struct btree *b, struct btree_op *op,
1440 struct closure *writes, struct gc_stat *gc)
1441{
1402 unsigned i;
1403 int ret = 0;
1404 bool should_rewrite;
1405 struct btree *n;
1406 struct bkey *k;
1407 struct keylist keys;
1408 struct btree_iter iter;
1409 struct gc_merge_info r[GC_MERGE_NODES];
1442 int ret = 0;
1443 bool should_rewrite;
1444 struct btree *n;
1445 struct bkey *k;
1446 struct keylist keys;
1447 struct btree_iter iter;
1448 struct gc_merge_info r[GC_MERGE_NODES];
1410 struct gc_merge_info *last = r + GC_MERGE_NODES - 1;
1449 struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
1411
1412 bch_keylist_init(&keys);
1413 bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
1414
1450
1451 bch_keylist_init(&keys);
1452 bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
1453
1415 for (i = 0; i < GC_MERGE_NODES; i++)
1416 r[i].b = ERR_PTR(-EINTR);
1454 for (i = r; i < r + ARRAY_SIZE(r); i++)
1455 i->b = ERR_PTR(-EINTR);
1417
1418 while (1) {
1419 k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
1420 if (k) {
1421 r->b = bch_btree_node_get(b->c, k, b->level - 1, true);
1422 if (IS_ERR(r->b)) {
1423 ret = PTR_ERR(r->b);
1424 break;

--- 13 unchanged lines hidden (view full) ---

1438 should_rewrite = btree_gc_mark_node(last->b, gc);
1439 if (should_rewrite &&
1440 !btree_check_reserve(b, NULL)) {
1441 n = btree_node_alloc_replacement(last->b,
1442 false);
1443
1444 if (!IS_ERR_OR_NULL(n)) {
1445 bch_btree_node_write_sync(n);
1456
1457 while (1) {
1458 k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
1459 if (k) {
1460 r->b = bch_btree_node_get(b->c, k, b->level - 1, true);
1461 if (IS_ERR(r->b)) {
1462 ret = PTR_ERR(r->b);
1463 break;

--- 13 unchanged lines hidden (view full) ---

1477 should_rewrite = btree_gc_mark_node(last->b, gc);
1478 if (should_rewrite &&
1479 !btree_check_reserve(b, NULL)) {
1480 n = btree_node_alloc_replacement(last->b,
1481 false);
1482
1483 if (!IS_ERR_OR_NULL(n)) {
1484 bch_btree_node_write_sync(n);
1485
1446 bch_keylist_add(&keys, &n->key);
1447
1448 make_btree_freeing_key(last->b,
1449 keys.top);
1450 bch_keylist_push(&keys);
1451
1452 bch_btree_insert_node(b, op, &keys,
1453 NULL, NULL);

--- 16 unchanged lines hidden (view full) ---

1470 }
1471
1472 bkey_copy_key(&b->c->gc_done, &last->b->key);
1473
1474 /*
1475 * Must flush leaf nodes before gc ends, since replace
1476 * operations aren't journalled
1477 */
1486 bch_keylist_add(&keys, &n->key);
1487
1488 make_btree_freeing_key(last->b,
1489 keys.top);
1490 bch_keylist_push(&keys);
1491
1492 bch_btree_insert_node(b, op, &keys,
1493 NULL, NULL);

--- 16 unchanged lines hidden (view full) ---

1510 }
1511
1512 bkey_copy_key(&b->c->gc_done, &last->b->key);
1513
1514 /*
1515 * Must flush leaf nodes before gc ends, since replace
1516 * operations aren't journalled
1517 */
1518 mutex_lock(&last->b->write_lock);
1478 if (btree_node_dirty(last->b))
1479 bch_btree_node_write(last->b, writes);
1519 if (btree_node_dirty(last->b))
1520 bch_btree_node_write(last->b, writes);
1521 mutex_unlock(&last->b->write_lock);
1480 rw_unlock(true, last->b);
1481 }
1482
1483 memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
1484 r->b = NULL;
1485
1486 if (need_resched()) {
1487 ret = -EAGAIN;
1488 break;
1489 }
1490 }
1491
1522 rw_unlock(true, last->b);
1523 }
1524
1525 memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
1526 r->b = NULL;
1527
1528 if (need_resched()) {
1529 ret = -EAGAIN;
1530 break;
1531 }
1532 }
1533
1492 for (i = 0; i < GC_MERGE_NODES; i++)
1493 if (!IS_ERR_OR_NULL(r[i].b)) {
1494 if (btree_node_dirty(r[i].b))
1495 bch_btree_node_write(r[i].b, writes);
1496 rw_unlock(true, r[i].b);
1534 for (i = r; i < r + ARRAY_SIZE(r); i++)
1535 if (!IS_ERR_OR_NULL(i->b)) {
1536 mutex_lock(&i->b->write_lock);
1537 if (btree_node_dirty(i->b))
1538 bch_btree_node_write(i->b, writes);
1539 mutex_unlock(&i->b->write_lock);
1540 rw_unlock(true, i->b);
1497 }
1498
1499 bch_keylist_free(&keys);
1500
1501 return ret;
1502}
1503
1504static int bch_btree_gc_root(struct btree *b, struct btree_op *op,

--- 4 unchanged lines hidden (view full) ---

1509 bool should_rewrite;
1510
1511 should_rewrite = btree_gc_mark_node(b, gc);
1512 if (should_rewrite) {
1513 n = btree_node_alloc_replacement(b, false);
1514
1515 if (!IS_ERR_OR_NULL(n)) {
1516 bch_btree_node_write_sync(n);
1541 }
1542
1543 bch_keylist_free(&keys);
1544
1545 return ret;
1546}
1547
1548static int bch_btree_gc_root(struct btree *b, struct btree_op *op,

--- 4 unchanged lines hidden (view full) ---

1553 bool should_rewrite;
1554
1555 should_rewrite = btree_gc_mark_node(b, gc);
1556 if (should_rewrite) {
1557 n = btree_node_alloc_replacement(b, false);
1558
1559 if (!IS_ERR_OR_NULL(n)) {
1560 bch_btree_node_write_sync(n);
1561
1517 bch_btree_set_root(n);
1518 btree_node_free(b);
1519 rw_unlock(true, n);
1520
1521 return -EINTR;
1522 }
1523 }
1524

--- 341 unchanged lines hidden (view full) ---

1866 goto err_free1;
1867
1868 if (!b->parent) {
1869 n3 = bch_btree_node_alloc(b->c, b->level + 1, true);
1870 if (IS_ERR(n3))
1871 goto err_free2;
1872 }
1873
1562 bch_btree_set_root(n);
1563 btree_node_free(b);
1564 rw_unlock(true, n);
1565
1566 return -EINTR;
1567 }
1568 }
1569

--- 341 unchanged lines hidden (view full) ---

1911 goto err_free1;
1912
1913 if (!b->parent) {
1914 n3 = bch_btree_node_alloc(b->c, b->level + 1, true);
1915 if (IS_ERR(n3))
1916 goto err_free2;
1917 }
1918
1919 mutex_lock(&n1->write_lock);
1920 mutex_lock(&n2->write_lock);
1921
1874 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
1875
1876 /*
1877 * Has to be a linear search because we don't have an auxiliary
1878 * search tree yet
1879 */
1880
1881 while (keys < (btree_bset_first(n1)->keys * 3) / 5)

--- 10 unchanged lines hidden (view full) ---

1892 memcpy(btree_bset_first(n2)->start,
1893 bset_bkey_last(btree_bset_first(n1)),
1894 btree_bset_first(n2)->keys * sizeof(uint64_t));
1895
1896 bkey_copy_key(&n2->key, &b->key);
1897
1898 bch_keylist_add(&parent_keys, &n2->key);
1899 bch_btree_node_write(n2, &cl);
1922 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
1923
1924 /*
1925 * Has to be a linear search because we don't have an auxiliary
1926 * search tree yet
1927 */
1928
1929 while (keys < (btree_bset_first(n1)->keys * 3) / 5)

--- 10 unchanged lines hidden (view full) ---

1940 memcpy(btree_bset_first(n2)->start,
1941 bset_bkey_last(btree_bset_first(n1)),
1942 btree_bset_first(n2)->keys * sizeof(uint64_t));
1943
1944 bkey_copy_key(&n2->key, &b->key);
1945
1946 bch_keylist_add(&parent_keys, &n2->key);
1947 bch_btree_node_write(n2, &cl);
1948 mutex_unlock(&n2->write_lock);
1900 rw_unlock(true, n2);
1901 } else {
1902 trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
1903
1949 rw_unlock(true, n2);
1950 } else {
1951 trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
1952
1953 mutex_lock(&n1->write_lock);
1904 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
1905 }
1906
1907 bch_keylist_add(&parent_keys, &n1->key);
1908 bch_btree_node_write(n1, &cl);
1954 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
1955 }
1956
1957 bch_keylist_add(&parent_keys, &n1->key);
1958 bch_btree_node_write(n1, &cl);
1959 mutex_unlock(&n1->write_lock);
1909
1910 if (n3) {
1911 /* Depth increases, make a new root */
1960
1961 if (n3) {
1962 /* Depth increases, make a new root */
1963 mutex_lock(&n3->write_lock);
1912 bkey_copy_key(&n3->key, &MAX_KEY);
1913 bch_btree_insert_keys(n3, op, &parent_keys, NULL);
1914 bch_btree_node_write(n3, &cl);
1964 bkey_copy_key(&n3->key, &MAX_KEY);
1965 bch_btree_insert_keys(n3, op, &parent_keys, NULL);
1966 bch_btree_node_write(n3, &cl);
1967 mutex_unlock(&n3->write_lock);
1915
1916 closure_sync(&cl);
1917 bch_btree_set_root(n3);
1918 rw_unlock(true, n3);
1919 } else if (!b->parent) {
1920 /* Root filled up but didn't need to be split */
1921 closure_sync(&cl);
1922 bch_btree_set_root(n1);

--- 32 unchanged lines hidden (view full) ---

1955 return -ENOMEM;
1956}
1957
1958static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
1959 struct keylist *insert_keys,
1960 atomic_t *journal_ref,
1961 struct bkey *replace_key)
1962{
1968
1969 closure_sync(&cl);
1970 bch_btree_set_root(n3);
1971 rw_unlock(true, n3);
1972 } else if (!b->parent) {
1973 /* Root filled up but didn't need to be split */
1974 closure_sync(&cl);
1975 bch_btree_set_root(n1);

--- 32 unchanged lines hidden (view full) ---

2008 return -ENOMEM;
2009}
2010
2011static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
2012 struct keylist *insert_keys,
2013 atomic_t *journal_ref,
2014 struct bkey *replace_key)
2015{
2016 struct closure cl;
2017
1963 BUG_ON(b->level && replace_key);
1964
2018 BUG_ON(b->level && replace_key);
2019
2020 closure_init_stack(&cl);
2021
2022 mutex_lock(&b->write_lock);
2023
2024 if (write_block(b) != btree_bset_last(b) &&
2025 b->keys.last_set_unwritten)
2026 bch_btree_init_next(b); /* just wrote a set */
2027
1965 if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
2028 if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
1966 if (current->bio_list) {
1967 op->lock = b->c->root->level + 1;
1968 return -EAGAIN;
1969 } else if (op->lock <= b->c->root->level) {
1970 op->lock = b->c->root->level + 1;
1971 return -EINTR;
1972 } else {
1973 /* Invalidated all iterators */
1974 int ret = btree_split(b, op, insert_keys, replace_key);
2029 mutex_unlock(&b->write_lock);
2030 goto split;
2031 }
1975
2032
1976 return bch_keylist_empty(insert_keys) ?
1977 0 : ret ?: -EINTR;
1978 }
1979 } else {
1980 BUG_ON(write_block(b) != btree_bset_last(b));
2033 BUG_ON(write_block(b) != btree_bset_last(b));
1981
2034
1982 if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {
1983 if (!b->level)
1984 bch_btree_leaf_dirty(b, journal_ref);
1985 else
1986 bch_btree_node_write_sync(b);
1987 }
2035 if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {
2036 if (!b->level)
2037 bch_btree_leaf_dirty(b, journal_ref);
2038 else
2039 bch_btree_node_write(b, &cl);
2040 }
1988
2041
1989 return 0;
2042 mutex_unlock(&b->write_lock);
2043
2044 /* wait for btree node write if necessary, after unlock */
2045 closure_sync(&cl);
2046
2047 return 0;
2048split:
2049 if (current->bio_list) {
2050 op->lock = b->c->root->level + 1;
2051 return -EAGAIN;
2052 } else if (op->lock <= b->c->root->level) {
2053 op->lock = b->c->root->level + 1;
2054 return -EINTR;
2055 } else {
2056 /* Invalidated all iterators */
2057 int ret = btree_split(b, op, insert_keys, replace_key);
2058
2059 if (bch_keylist_empty(insert_keys))
2060 return 0;
2061 else if (!ret)
2062 return -EINTR;
2063 return ret;
1990 }
1991}
1992
1993int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
1994 struct bkey *check_key)
1995{
1996 int ret = -EINTR;
1997 uint64_t btree_ptr = b->key.ptr[0];

--- 392 unchanged lines hidden --- 		2064 }
2065}
2066
2067int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
2068 struct bkey *check_key)
2069{
2070 int ret = -EINTR;
2071 uint64_t btree_ptr = b->key.ptr[0];

--- 392 unchanged lines hidden ---