#define PTR_HASH(c, k) \
(((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
-static struct workqueue_struct *btree_io_wq;
-
#define insert_lock(s, b) ((b)->level <= (s)->lock)
/*
({ \
int _r, l = (b)->level - 1; \
bool _w = l <= (op)->lock; \
- struct btree *_child = bch_btree_node_get((b)->c, key, l, _w); \
+ struct btree *_child = bch_btree_node_get((b)->c, op, key, l, _w);\
if (!IS_ERR(_child)) { \
_child->parent = (b); \
_r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
_r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
} \
rw_unlock(_w, _b); \
+ bch_cannibalize_unlock(c); \
if (_r == -EINTR) \
schedule(); \
- bch_cannibalize_unlock(c); \
- if (_r == -ENOSPC) { \
- wait_event((c)->try_wait, \
- !(c)->try_harder); \
- _r = -EINTR; \
- } \
} while (_r == -EINTR); \
\
- finish_wait(&(c)->bucket_wait, &(op)->wait); \
+ finish_wait(&(c)->btree_cache_wait, &(op)->wait); \
_r; \
})
btree_complete_write(b, w);
if (btree_node_dirty(b))
- queue_delayed_work(btree_io_wq, &b->work,
- msecs_to_jiffies(30000));
+ schedule_delayed_work(&b->work, 30 * HZ);
closure_return_with_destructor(cl, btree_node_write_unlock);
}
BUG_ON(!i->keys);
if (!btree_node_dirty(b))
- queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);
+ schedule_delayed_work(&b->work, 30 * HZ);
set_btree_node_dirty(b);
#define mca_reserve(c) (((c->root && c->root->level) \
? c->root->level : 1) * 8 + 16)
#define mca_can_free(c) \
- max_t(int, 0, c->bucket_cache_used - mca_reserve(c))
+ max_t(int, 0, c->btree_cache_used - mca_reserve(c))
static void mca_data_free(struct btree *b)
{
bch_btree_keys_free(&b->keys);
- b->c->bucket_cache_used--;
+ b->c->btree_cache_used--;
list_move(&b->list, &b->c->btree_cache_freed);
}
ilog2(b->c->btree_pages),
btree_order(k)),
gfp)) {
- b->c->bucket_cache_used++;
+ b->c->btree_cache_used++;
list_move(&b->list, &b->c->btree_cache);
} else {
list_move(&b->list, &b->c->btree_cache_freed);
if (c->shrinker_disabled)
return SHRINK_STOP;
- if (c->try_harder)
+ if (c->btree_cache_alloc_lock)
return SHRINK_STOP;
/* Return -1 if we can't do anything right now */
}
}
- for (i = 0; (nr--) && i < c->bucket_cache_used; i++) {
+ for (i = 0; (nr--) && i < c->btree_cache_used; i++) {
if (list_empty(&c->btree_cache))
goto out;
if (c->shrinker_disabled)
return 0;
- if (c->try_harder)
+ if (c->btree_cache_alloc_lock)
return 0;
return mca_can_free(c) * c->btree_pages;
return b;
}
-static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k)
+static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op)
+{
+ struct task_struct *old;
+
+ old = cmpxchg(&c->btree_cache_alloc_lock, NULL, current);
+ if (old && old != current) {
+ if (op)
+ prepare_to_wait(&c->btree_cache_wait, &op->wait,
+ TASK_UNINTERRUPTIBLE);
+ return -EINTR;
+ }
+
+ return 0;
+}
+
+static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op,
+ struct bkey *k)
{
struct btree *b;
trace_bcache_btree_cache_cannibalize(c);
- if (!c->try_harder) {
- c->try_harder = current;
- c->try_harder_start = local_clock();
- } else if (c->try_harder != current)
- return ERR_PTR(-ENOSPC);
+ if (mca_cannibalize_lock(c, op))
+ return ERR_PTR(-EINTR);
list_for_each_entry_reverse(b, &c->btree_cache, list)
if (!mca_reap(b, btree_order(k), false))
if (!mca_reap(b, btree_order(k), true))
return b;
+ WARN(1, "btree cache cannibalize failed\n");
return ERR_PTR(-ENOMEM);
}
*/
static void bch_cannibalize_unlock(struct cache_set *c)
{
- if (c->try_harder == current) {
- bch_time_stats_update(&c->try_harder_time, c->try_harder_start);
- c->try_harder = NULL;
- wake_up(&c->try_wait);
+ if (c->btree_cache_alloc_lock == current) {
+ c->btree_cache_alloc_lock = NULL;
+ wake_up(&c->btree_cache_wait);
}
}
-static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, int level)
+static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op,
+ struct bkey *k, int level)
{
struct btree *b;
if (b)
rw_unlock(true, b);
- b = mca_cannibalize(c, k);
+ b = mca_cannibalize(c, op, k);
if (!IS_ERR(b))
goto out;
* The btree node will have either a read or a write lock held, depending on
* level and op->lock.
*/
-struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k,
- int level, bool write)
+struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op,
+ struct bkey *k, int level, bool write)
{
int i = 0;
struct btree *b;
return ERR_PTR(-EAGAIN);
mutex_lock(&c->bucket_lock);
- b = mca_alloc(c, k, level);
+ b = mca_alloc(c, op, k, level);
mutex_unlock(&c->bucket_lock);
if (!b)
struct btree *b;
mutex_lock(&c->bucket_lock);
- b = mca_alloc(c, k, level);
+ b = mca_alloc(c, NULL, k, level);
mutex_unlock(&c->bucket_lock);
if (!IS_ERR_OR_NULL(b)) {
mutex_unlock(&b->c->bucket_lock);
}
-struct btree *bch_btree_node_alloc(struct cache_set *c, int level, bool wait)
+struct btree *bch_btree_node_alloc(struct cache_set *c, struct btree_op *op,
+ int level)
{
BKEY_PADDED(key) k;
struct btree *b = ERR_PTR(-EAGAIN);
mutex_lock(&c->bucket_lock);
retry:
- if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait))
+ if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, op != NULL))
goto err;
bkey_put(c, &k.key);
SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);
- b = mca_alloc(c, &k.key, level);
+ b = mca_alloc(c, op, &k.key, level);
if (IS_ERR(b))
goto err_free;
return b;
}
-static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait)
+static struct btree *btree_node_alloc_replacement(struct btree *b,
+ struct btree_op *op)
{
- struct btree *n = bch_btree_node_alloc(b->c, b->level, wait);
+ struct btree *n = bch_btree_node_alloc(b->c, op, b->level);
if (!IS_ERR_OR_NULL(n)) {
mutex_lock(&n->write_lock);
bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
{
struct cache_set *c = b->c;
struct cache *ca;
- unsigned i, reserve = c->root->level * 2 + 1;
- int ret = 0;
+ unsigned i, reserve = (c->root->level - b->level) * 2 + 1;
mutex_lock(&c->bucket_lock);
for_each_cache(ca, c, i)
if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {
if (op)
- prepare_to_wait(&c->bucket_wait, &op->wait,
+ prepare_to_wait(&c->btree_cache_wait, &op->wait,
TASK_UNINTERRUPTIBLE);
- ret = -EINTR;
- break;
+ mutex_unlock(&c->bucket_lock);
+ return -EINTR;
}
mutex_unlock(&c->bucket_lock);
- return ret;
+
+ return mca_cannibalize_lock(b->c, op);
}
/* Garbage collection */
struct keylist *, atomic_t *, struct bkey *);
static int btree_gc_coalesce(struct btree *b, struct btree_op *op,
- struct keylist *keylist, struct gc_stat *gc,
- struct gc_merge_info *r)
+ struct gc_stat *gc, struct gc_merge_info *r)
{
unsigned i, nodes = 0, keys = 0, blocks;
struct btree *new_nodes[GC_MERGE_NODES];
+ struct keylist keylist;
struct closure cl;
struct bkey *k;
+ bch_keylist_init(&keylist);
+
+ if (btree_check_reserve(b, NULL))
+ return 0;
+
memset(new_nodes, 0, sizeof(new_nodes));
closure_init_stack(&cl);
return 0;
for (i = 0; i < nodes; i++) {
- new_nodes[i] = btree_node_alloc_replacement(r[i].b, false);
+ new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL);
if (IS_ERR_OR_NULL(new_nodes[i]))
goto out_nocoalesce;
}
+ /*
+ * We have to check the reserve here, after we've allocated our new
+ * nodes, to make sure the insert below will succeed - we also check
+ * before as an optimization to potentially avoid a bunch of expensive
+ * allocs/sorts
+ */
+ if (btree_check_reserve(b, NULL))
+ goto out_nocoalesce;
+
for (i = 0; i < nodes; i++)
mutex_lock(&new_nodes[i]->write_lock);
n2->keys -= keys;
- if (__bch_keylist_realloc(keylist,
+ if (__bch_keylist_realloc(&keylist,
bkey_u64s(&new_nodes[i]->key)))
goto out_nocoalesce;
bch_btree_node_write(new_nodes[i], &cl);
- bch_keylist_add(keylist, &new_nodes[i]->key);
+ bch_keylist_add(&keylist, &new_nodes[i]->key);
}
for (i = 0; i < nodes; i++)
rw_unlock(true, new_nodes[0]);
for (i = 0; i < nodes; i++) {
- if (__bch_keylist_realloc(keylist, bkey_u64s(&r[i].b->key)))
+ if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key)))
goto out_nocoalesce;
- make_btree_freeing_key(r[i].b, keylist->top);
- bch_keylist_push(keylist);
+ make_btree_freeing_key(r[i].b, keylist.top);
+ bch_keylist_push(&keylist);
}
- bch_btree_insert_node(b, op, keylist, NULL, NULL);
- BUG_ON(!bch_keylist_empty(keylist));
+ bch_btree_insert_node(b, op, &keylist, NULL, NULL);
+ BUG_ON(!bch_keylist_empty(&keylist));
for (i = 0; i < nodes; i++) {
btree_node_free(r[i].b);
trace_bcache_btree_gc_coalesce(nodes);
gc->nodes--;
+ bch_keylist_free(&keylist);
+
/* Invalidated our iterator */
return -EINTR;
out_nocoalesce:
closure_sync(&cl);
+ bch_keylist_free(&keylist);
- while ((k = bch_keylist_pop(keylist)))
+ while ((k = bch_keylist_pop(&keylist)))
if (!bkey_cmp(k, &ZERO_KEY))
atomic_dec(&b->c->prio_blocked);
return 0;
}
+static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op,
+ struct btree *replace)
+{
+ struct keylist keys;
+ struct btree *n;
+
+ if (btree_check_reserve(b, NULL))
+ return 0;
+
+ n = btree_node_alloc_replacement(replace, NULL);
+
+ /* recheck reserve after allocating replacement node */
+ if (btree_check_reserve(b, NULL)) {
+ btree_node_free(n);
+ rw_unlock(true, n);
+ return 0;
+ }
+
+ bch_btree_node_write_sync(n);
+
+ bch_keylist_init(&keys);
+ bch_keylist_add(&keys, &n->key);
+
+ make_btree_freeing_key(replace, keys.top);
+ bch_keylist_push(&keys);
+
+ bch_btree_insert_node(b, op, &keys, NULL, NULL);
+ BUG_ON(!bch_keylist_empty(&keys));
+
+ btree_node_free(replace);
+ rw_unlock(true, n);
+
+ /* Invalidated our iterator */
+ return -EINTR;
+}
+
static unsigned btree_gc_count_keys(struct btree *b)
{
struct bkey *k;
{
int ret = 0;
bool should_rewrite;
- struct btree *n;
struct bkey *k;
- struct keylist keys;
struct btree_iter iter;
struct gc_merge_info r[GC_MERGE_NODES];
struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
- bch_keylist_init(&keys);
bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
for (i = r; i < r + ARRAY_SIZE(r); i++)
while (1) {
k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
if (k) {
- r->b = bch_btree_node_get(b->c, k, b->level - 1, true);
+ r->b = bch_btree_node_get(b->c, op, k, b->level - 1,
+ true);
if (IS_ERR(r->b)) {
ret = PTR_ERR(r->b);
break;
r->keys = btree_gc_count_keys(r->b);
- ret = btree_gc_coalesce(b, op, &keys, gc, r);
+ ret = btree_gc_coalesce(b, op, gc, r);
if (ret)
break;
}
if (!IS_ERR(last->b)) {
should_rewrite = btree_gc_mark_node(last->b, gc);
- if (should_rewrite &&
- !btree_check_reserve(b, NULL)) {
- n = btree_node_alloc_replacement(last->b,
- false);
-
- if (!IS_ERR_OR_NULL(n)) {
- bch_btree_node_write_sync(n);
-
- bch_keylist_add(&keys, &n->key);
-
- make_btree_freeing_key(last->b,
- keys.top);
- bch_keylist_push(&keys);
-
- bch_btree_insert_node(b, op, &keys,
- NULL, NULL);
- BUG_ON(!bch_keylist_empty(&keys));
-
- btree_node_free(last->b);
- rw_unlock(true, last->b);
- last->b = n;
-
- /* Invalidated our iterator */
- ret = -EINTR;
+ if (should_rewrite) {
+ ret = btree_gc_rewrite_node(b, op, last->b);
+ if (ret)
break;
- }
}
if (last->b->level) {
rw_unlock(true, i->b);
}
- bch_keylist_free(&keys);
-
return ret;
}
should_rewrite = btree_gc_mark_node(b, gc);
if (should_rewrite) {
- n = btree_node_alloc_replacement(b, false);
+ n = btree_node_alloc_replacement(b, NULL);
if (!IS_ERR_OR_NULL(n)) {
bch_btree_node_write_sync(n);
closure_init_stack(&cl);
bch_keylist_init(&parent_keys);
- if (!b->level &&
- btree_check_reserve(b, op))
- return -EINTR;
+ if (btree_check_reserve(b, op)) {
+ if (!b->level)
+ return -EINTR;
+ else
+ WARN(1, "insufficient reserve for split\n");
+ }
- n1 = btree_node_alloc_replacement(b, true);
+ n1 = btree_node_alloc_replacement(b, op);
if (IS_ERR(n1))
goto err;
trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys);
- n2 = bch_btree_node_alloc(b->c, b->level, true);
+ n2 = bch_btree_node_alloc(b->c, op, b->level);
if (IS_ERR(n2))
goto err_free1;
if (!b->parent) {
- n3 = bch_btree_node_alloc(b->c, b->level + 1, true);
+ n3 = bch_btree_node_alloc(b->c, op, b->level + 1);
if (IS_ERR(n3))
goto err_free2;
}
btree_node_free(n1);
rw_unlock(true, n1);
err:
- WARN(1, "bcache: btree split failed");
+ WARN(1, "bcache: btree split failed (level %u)", b->level);
if (n3 == ERR_PTR(-EAGAIN) ||
n2 == ERR_PTR(-EAGAIN) ||
spin_lock_init(&buf->lock);
array_allocator_init(&buf->freelist);
}
-
-void bch_btree_exit(void)
-{
- if (btree_io_wq)
- destroy_workqueue(btree_io_wq);
-}
-
-int __init bch_btree_init(void)
-{
- btree_io_wq = create_singlethread_workqueue("bch_btree_io");
- if (!btree_io_wq)
- return -ENOMEM;
-
- return 0;
-}
projects / cascardo / linux.git / blobdiff