aboutsummaryrefslogtreecommitdiff
path: root/drivers/md/bcache
diff options
context:
space:
mode:
authorKent Overstreet <koverstreet@google.com>2013-05-11 15:59:37 -0700
committerKent Overstreet <koverstreet@google.com>2013-06-26 17:09:16 -0700
commit6ded34d1a54c046a45db071d3cb7b37bd0a4a31f (patch)
tree1f2b7703d1be78e0ab510df54a487b746a8e2312 /drivers/md/bcache
parent85b1492ee113486d871de7676a61f506a43ca475 (diff)
bcache: Improve lazy sorting
The old lazy sorting code was kind of hacky - rewrite in a way that mathematically makes more sense; the idea is that the size of the sets of keys in a btree node should increase by a more or less fixed ratio from smallest to biggest. Signed-off-by: Kent Overstreet <koverstreet@google.com>
Diffstat (limited to 'drivers/md/bcache')
-rw-r--r--drivers/md/bcache/bcache.h1
-rw-r--r--drivers/md/bcache/bset.c40
-rw-r--r--drivers/md/bcache/super.c2
3 files changed, 26 insertions, 17 deletions
diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index 59c15e09e4d..6fa5a1e33c4 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -828,6 +828,7 @@ struct cache_set {
*/
struct mutex sort_lock;
struct bset *sort;
+ unsigned sort_crit_factor;
/* List of buckets we're currently writing data to */
struct list_head data_buckets;
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index e9399ed7f68..a0f190ac17a 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -1092,33 +1092,39 @@ void bch_btree_sort_into(struct btree *b, struct btree *new)
new->sets->size = 0;
}
+#define SORT_CRIT (4096 / sizeof(uint64_t))
+
void bch_btree_sort_lazy(struct btree *b)
{
- if (b->nsets) {
- unsigned i, j, keys = 0, total;
-
- for (i = 0; i <= b->nsets; i++)
- keys += b->sets[i].data->keys;
+ unsigned crit = SORT_CRIT;
+ int i;
- total = keys;
+ /* Don't sort if nothing to do */
+ if (!b->nsets)
+ goto out;
- for (j = 0; j < b->nsets; j++) {
- if (keys * 2 < total ||
- keys < 1000) {
- bch_btree_sort_partial(b, j);
- return;
- }
+ /* If not a leaf node, always sort */
+ if (b->level) {
+ bch_btree_sort(b);
+ return;
+ }
- keys -= b->sets[j].data->keys;
- }
+ for (i = b->nsets - 1; i >= 0; --i) {
+ crit *= b->c->sort_crit_factor;
- /* Must sort if b->nsets == 3 or we'll overflow */
- if (b->nsets >= (MAX_BSETS - 1) - b->level) {
- bch_btree_sort(b);
+ if (b->sets[i].data->keys < crit) {
+ bch_btree_sort_partial(b, i);
return;
}
}
+ /* Sort if we'd overflow */
+ if (b->nsets + 1 == MAX_BSETS) {
+ bch_btree_sort(b);
+ return;
+ }
+
+out:
bset_build_written_tree(b);
}
diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
index f24c2e0cbb1..3c8474161e8 100644
--- a/drivers/md/bcache/super.c
+++ b/drivers/md/bcache/super.c
@@ -1375,6 +1375,8 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb *sb)
c->btree_pages = max_t(int, c->btree_pages / 4,
BTREE_MAX_PAGES);
+ c->sort_crit_factor = int_sqrt(c->btree_pages);
+
mutex_init(&c->bucket_lock);
mutex_init(&c->sort_lock);
spin_lock_init(&c->sort_time_lock);