summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2016-12-12 11:11:02 -0900
committerKent Overstreet <kent.overstreet@gmail.com>2016-12-12 12:53:59 -0900
commitcb1b62102ab3a6143d6297a02c18c491ff762deb (patch)
treebaa11295d5a3cf5ec46d4bc9584f02e654326fdd
parent2d258c7a723ce2ec9893a1717158cfebe96285ce (diff)
downloadlinux-bcache-treebitvec.tar.zst
bcache: treebitvec thingtreebitvec
-rw-r--r--drivers/md/bcache/bcache.h2
-rw-r--r--drivers/md/bcache/buckets.c4
-rw-r--r--drivers/md/bcache/treebitvec.h88
3 files changed, 94 insertions, 0 deletions
diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index 3540e05e40ef..c2993023146b 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -198,6 +198,7 @@
#include "util.h"
#include "closure.h"
#include "opts.h"
+#include "treebitvec.h"
#include <linux/dynamic_fault.h>
@@ -411,6 +412,7 @@ struct cache {
/* most out of date gen in the btree */
u8 *oldest_gens;
struct bucket *buckets;
+ struct treebitvec empty_buckets;
unsigned short bucket_bits; /* ilog2(bucket_size) */
/* last calculated minimum prio */
diff --git a/drivers/md/bcache/buckets.c b/drivers/md/bcache/buckets.c
index 90dfa03b0a7a..8e602e8ac4d9 100644
--- a/drivers/md/bcache/buckets.c
+++ b/drivers/md/bcache/buckets.c
@@ -67,6 +67,8 @@
#include "btree_gc.h"
#include "buckets.h"
+#include "treebitvec.h"
+
#include <trace/events/bcache.h>
#ifdef DEBUG_BUCKETS
@@ -494,6 +496,8 @@ static void bch_mark_pointer(struct cache_set *c,
if (journal_seq) {
new.wait_on_journal = true;
new.journal_seq = journal_seq;
+ //treebitvec_set(&ca->empty_buckets,
+ // PTR_BUCKET_NR(ca, ptr));
}
} else {
new.is_metadata = (type == S_META);
diff --git a/drivers/md/bcache/treebitvec.h b/drivers/md/bcache/treebitvec.h
new file mode 100644
index 000000000000..de3618a2e4d5
--- /dev/null
+++ b/drivers/md/bcache/treebitvec.h
@@ -0,0 +1,88 @@
+#ifndef _TREEBITVEC_H
+#define _TREEBITVEC_H
+
+#include <linux/kernel.h>
+
+/* d-ary tree laid out in an array */
+
+#define BITSHIFT ilog2(BITS_PER_LONG)
+
+struct treebitvec {
+ size_t size;
+ size_t leaf_offset;
+ unsigned depth;
+ unsigned long *bits;
+};
+
+static inline size_t treebitvec_up(size_t n)
+{
+ return n = (n - 1) >> BITSHIFT;
+}
+
+static inline size_t treebitvec_down(size_t n)
+{
+ return (n << BITSHIFT) + 1;
+}
+
+static inline void treebitvec_set(struct treebitvec *bv, size_t n)
+{
+ unsigned bit;
+
+ bit = n & (BITS_PER_LONG - 1);
+ n = (bit >> BITSHIFT) + bv->leaf_offset;
+
+ while (!(bv->bits[n] & (1UL << bit))) {
+ bv->bits[n] |= (1UL << bit);
+
+ if (!n)
+ break;
+
+ bit = n & (BITS_PER_LONG - 1);
+ n = treebitvec_up(n);
+ }
+}
+
+static inline size_t treebitvec_next_set_bit(struct treebitvec *bv, size_t n)
+{
+ unsigned bit;
+
+ n = (n >> BITSHIFT) + bv->leaf_offset;
+
+ while (1) {
+ if (!bv->bits[n]) {
+ if (!n)
+ return SIZE_MAX;
+
+ n = treebitvec_up(n);
+ continue;
+ }
+
+ bit = __ffs(bv->bits[n]);
+ bv->bits[n] &= ~(1UL << bit);
+
+ if (n >= bv->leaf_offset)
+ return ((n - bv->leaf_offset) << BITSHIFT) + bit;
+
+ n = treebitvec_down(n) + bit;
+ }
+}
+
+static inline int treebitvec_init(struct treebitvec *bv, size_t size)
+{
+ size_t buf_size;
+
+ bv->size = size;
+ bv->depth = ilog2(size - 1) / ilog2(BITS_PER_LONG);
+ bv->leaf_offset = ((1UL << ((bv->depth + 1) * BITSHIFT)) - 1) /
+ (BITS_PER_LONG - 1);
+
+ buf_size = DIV_ROUND_UP(size, BITS_PER_LONG) + bv->leaf_offset;
+
+ bv->bits = kcalloc(buf_size, sizeof(unsigned long), GFP_KERNEL);
+ if (!bv->bits)
+ return -ENOMEM;
+
+ return 0;
+}
+
+#endif