bcache: treebitvec thingtreebitvec

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