First observations with bcache

First observations with bcache

[Mark Hills]

I took some time to try out bcache, on an x86 Dell PC with OCZ Agility 3 
SSD.

The good news is that once I had applied various workarounds, thing seems 
to work as expected, both with 2.6.34 and with an updated 3.1 branch.

I had to make a few modifications to get going, and then more to enable 
the various debug options.

The most awkward problems seem to be the result of 32-bit architecture, 
and I think are highlighted by building as a module.

I'll follow-up this email with the patches (based on bcache-3.1 branch), 
though I don't consider them to be long-term solutions; they show the 
changes I made.

I some cases I've proposed a better solution, but thought I'd raise them 
here for discussion first.

-- 
Mark

[PATCH 1/7] Use exported call to up/down read

[Mark Hills]

When building bcache as a module, the following errors are silenced
by this patch:

  ERROR: "call_rwsem_down_read_failed" [block/bcache.ko] undefined!
  ERROR: "call_rwsem_wake" [block/bcache.ko] undefined!

There may be implications of the extra code introduced by this, but
I am not familiar with these functions. Though I can confirm that
the resulting build seems to work.
---
 block/bcache.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/block/bcache.c b/block/bcache.c
index a2dbd1e..faaf75e 100644
--- a/block/bcache.c
+++ b/block/bcache.c
@@ -5561,7 +5561,7 @@ static void bio_complete(struct closure *cl)
 	keylist_free(&s->op.keys);
 
 	if (s->op.insert_type & INSERT_WRITE)
-		__up_read(&d->writeback_lock);
+		up_read(&d->writeback_lock);
 
 	if (s->cache_bio) {
 		int i;
@@ -5911,7 +5911,7 @@ static void request_write(struct search *s)
 	s->cl.fn		= bio_complete;
 	s->op.insert_type	= INSERT_WRITE;
 	check_should_skip(s);
-	__down_read(&s->op.d->writeback_lock);
+	down_read(&s->op.d->writeback_lock);
 
 	if (in_writeback(s->op.d, bio->bi_sector, bio_sectors(bio))) {
 		s->skip = false;
-- 
1.7.4.4

[PATCH 2/7] Provide 64-bit arithmetic functions

[Mark Hills]

Building on x86 (32-bit) gives linkage errors against __udivdi3 and
__umoddi3, which gcc uses to modulo and divide operations on 64-bit
numbers. eg. sector_t when divided by block_size, bucket_size

  ERROR: "__udivdi3" [block/bcache.ko] undefined!
  ERROR: "__umoddi3" [block/bcache.ko] undefined!

The recommended way to handle this in the kernel seems to be the do_div()
function. But since block_size, bucket_size etc. are restricted to powers
of 2 anyway, should we really be storing block size as a shift and a mask?

To get things running I just provided the following implementation in the
code, borrowed from a old patch by David Howells [1]

[1] http://lkml.org/lkml/2006/8/14/305
---
 block/bcache_util.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 95 insertions(+), 0 deletions(-)

diff --git a/block/bcache_util.c b/block/bcache_util.c
index ea707c9..8e147de 100644
--- a/block/bcache_util.c
+++ b/block/bcache_util.c
@@ -1,6 +1,7 @@
 #include <linux/bio.h>
 #include <linux/blkdev.h>
 #include <linux/debugfs.h>
+#include <linux/log2.h>
 #include <linux/module.h>
 #include <linux/seq_file.h>
 #include <linux/types.h>
@@ -659,3 +660,97 @@ uint64_t crc64(const void *data, size_t len)
 	return crc ^ 0xffffffffffffffff;
 }
 EXPORT_SYMBOL(crc64);
+
+/*
+ * calculate:
+ *	Q = a / b
+ *	R = a % b
+ * by long division (repeated shift and conditional subtract)
+ * - base2 long division does not require any usage of actual division or
+ *   multiplication instructions
+ */
+u64 __udivmoddi4(u64 a, u64 b, u64 *_r)
+{
+	u64 acc, Q;
+	u32 A;
+	int M;
+
+	/* dispose of trivialities first */
+	if (b >= a) {
+		if (b == a) {
+			if (_r)
+				*_r = 0;
+			return 1;
+		}
+		if (_r)
+			*_r = a;
+		return 0;
+	}
+
+	/* divide by two until at least one argument is odd */
+	while (!((a | b) & 1)) {
+		a >>= 1;
+		b >>= 1;
+	}
+
+	/* handle it as 64-bit divide by 32-bit if we can */
+	if (b <= 0xffffffffULL) {
+		acc = do_div(a, b);
+		if (_r)
+			*_r = acc;
+		return a;
+	}
+
+	/* skip any steps that don't need to be done given the magnitude of the
+	 * divisor:
+	 * - the divisor is at least 33 bits in size (log2(b) >= 32)
+	 * - load the accumulator with as many bits of the dividend as we can
+	 * - decant the remainder into a 32-bit variable since we will have
+	 *   fewer than 32-bits remaining
+	 */
+	M = ilog2(b >> 32) + 32;
+	acc = a >> (63 - M);
+	A = a;
+	A <<= M - 31;
+
+	Q = 0;
+
+	for (;;) {
+		if (acc >= b) {
+			/* reduce the accumulator if we can */
+			acc -= b;
+			Q |= 1ULL;
+		}
+
+		if (M >= 63)
+			break;
+
+		/* shift next-MSB from dividend into LSB of accumulator */
+		acc = acc << 1;
+		if (A & 0x80000000U)
+			acc |= 1ULL;
+		A <<= 1;
+		Q <<= 1;
+		M++;
+	}
+
+	/* the accumulator is left holding the remainder */
+	if (_r)
+		*_r = acc;
+
+	return Q;
+}
+
+u64 __udivdi3(u64 a, u64 b)
+{
+	return __udivmoddi4(a, b, NULL);
+}
+EXPORT_SYMBOL(__udivdi3);
+
+u64 __umoddi3(u64 a, u64 b)
+{
+	u64 r;
+	__udivmoddi4(a, b, &r);
+	return r;
+}
+EXPORT_SYMBOL(__umoddi3);
-- 
1.7.4.4

[PATCH 3/7] Break fuzz test to allow building as module

[Mark Hills]

get_random_int() is not available, and is required when
CONFIG_BCACHE_DEBUG is used.
---
 block/bcache.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/block/bcache.c b/block/bcache.c
index faaf75e..9a1ab79 100644
--- a/block/bcache.c
+++ b/block/bcache.c
@@ -6255,7 +6255,7 @@ static ssize_t btree_fuzz(struct kobject *k, struct kobj_attribute *a,
 			struct bset *i = write_block(b);
 			struct bkey *k = op.keys.top;
 
-			k->key = get_random_int();
+			k->key = 0; /* FIXME */
 
 			op.insert_type = k->key & 1
 				? INSERT_WRITE
-- 
1.7.4.4

[PATCH 4/7] Don't require linkage against closure_lock

[Mark Hills]

Allow building as a module with CONFIG_BCACHE_CLOSURE_DEBUG.
Previously bcache.o required access to closure_lock. Instead
of exposing this symbol move the affected function.
---
 block/bcache_util.c |   11 +++++++++++
 block/bcache_util.h |   17 +----------------
 2 files changed, 12 insertions(+), 16 deletions(-)

diff --git a/block/bcache_util.c b/block/bcache_util.c
index 8e147de..19846fb 100644
--- a/block/bcache_util.c
+++ b/block/bcache_util.c
@@ -476,6 +476,17 @@ void closure_sync(struct closure *c)
 }
 EXPORT_SYMBOL_GPL(closure_sync);
 
+void closure_del(struct closure *c)
+{
+#ifdef CONFIG_BCACHE_CLOSURE_DEBUG
+	unsigned long flags;
+	spin_lock_irqsave(&closure_lock, flags);
+	list_del(&c->all);
+	spin_unlock_irqrestore(&closure_lock, flags);
+#endif
+}
+EXPORT_SYMBOL_GPL(closure_del);
+
 #ifdef CONFIG_BCACHE_CLOSURE_DEBUG
 
 #ifdef CONFIG_DEBUG_FS
diff --git a/block/bcache_util.h b/block/bcache_util.h
index d208131..872ca56 100644
--- a/block/bcache_util.h
+++ b/block/bcache_util.h
@@ -474,22 +474,7 @@ void closure_run_wait(closure_list_t *list, struct workqueue_struct *wq);
 bool closure_wait(closure_list_t *list, struct closure *c);
 void closure_sync(struct closure *c);
 void __closure_sleep(struct closure *c);
-
-#ifdef CONFIG_BCACHE_CLOSURE_DEBUG
-extern struct list_head closures;
-extern spinlock_t closure_lock;
-
-static inline void closure_del(struct closure *c)
-{
-	unsigned long flags;
-	spin_lock_irqsave(&closure_lock, flags);
-	list_del(&c->all);
-	spin_unlock_irqrestore(&closure_lock, flags);
-}
-
-#else
-static inline void closure_del(struct closure *c) {}
-#endif
+void closure_del(struct closure *c);
 
 static inline void closure_init(struct closure *c, struct closure *parent)
 {
-- 
1.7.4.4

[PATCH 5/7] Allow closure debugging without CONFIG_DEBUG_FS

[Mark Hills]

Fixes the build, although closure debugging is not much use without
it.
---
 block/bcache_util.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/block/bcache_util.c b/block/bcache_util.c
index 19846fb..b014e8c 100644
--- a/block/bcache_util.c
+++ b/block/bcache_util.c
@@ -531,7 +531,9 @@ module_exit(closure_debug_exit);
 static int __init closure_debug_init(void)
 {
 	spin_lock_init(&closure_lock);
+#ifdef CONFIG_DEBUG_FS
 	debug = debugfs_create_file("closures", 0400, NULL, NULL, &debug_ops);
+#endif
 	return 0;
 }
 
-- 
1.7.4.4

[PATCH 6/7] Temporary fix to pr_latency()

[Mark Hills]

The following compile errors are caused by pr_latency (gcc 4.5.2):

  block/bcache.c: In function 'fill_bucket_work':
  block/bcache.c:2510:2: error: initializer element is not constant
  block/bcache.c:2510:2: error: (near initialization for '_rs.lock')
  [...]

This is caused by printk_ratelimited() when compiled with --std=gnu99.
Although it is not clear why; the pre-processed code seems to be
constant. Perhaps this is even a bug in GCC.

This patch fixes the build in this case, by using regular printk
instead.

But the correct fix is to remove the specialised compile flag on bcache
code. It is mainly required by variables initialised in for loops.
---
 block/bcache_util.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/block/bcache_util.h b/block/bcache_util.h
index 872ca56..c7e72d0 100644
--- a/block/bcache_util.h
+++ b/block/bcache_util.h
@@ -414,7 +414,7 @@ extern unsigned latency_warn_ms;
 do {									\
 	int _ms = jiffies_to_msecs(jiffies - (j));			\
 	if (j && latency_warn_ms && (_ms) > (int) latency_warn_ms)	\
-		printk_ratelimited(KERN_DEBUG "bcache: %i ms latency "	\
+		printk(KERN_DEBUG "bcache: %i ms latency "		\
 			"called from %pf for " fmt "\n", _ms,		\
 		       __builtin_return_address(0), ##__VA_ARGS__);	\
 } while (0)
-- 
1.7.4.4

[PATCH 7/7] Don't require latency_warn_ms from bcache_util.o

[Mark Hills]

When building as a module, we can't see this variable. This removes
useful debugging; probably some restructuring would be better here.

I'm not clear on the responsibilities of bcache.c, vs. bcache_util.c,
there seem to be references in both directions.
---
 block/bcache_util.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/block/bcache_util.c b/block/bcache_util.c
index b014e8c..11a81c0 100644
--- a/block/bcache_util.c
+++ b/block/bcache_util.c
@@ -378,8 +378,6 @@ void closure_put(struct closure *c, struct workqueue_struct *wq)
 	bool sleeping;
 	int r;
 again:
-	pr_latency(c->wait_time, "%pf", c->fn);
-
 	sleeping = test_bit(__CLOSURE_SLEEPING, &c->flags);
 	r = atomic_dec_return(&c->remaining);
 	smp_mb__after_atomic_dec();
-- 
1.7.4.4

Re: [PATCH 1/7] Use exported call to up/down read

[Kent Overstreet]

On Sat, Sep 10, 2011 at 02:45:33PM +0100, Mark Hills wrote:
> When building bcache as a module, the following errors are silenced
> by this patch:
> 
>   ERROR: "call_rwsem_down_read_failed" [block/bcache.ko] undefined!
>   ERROR: "call_rwsem_wake" [block/bcache.ko] undefined!
> 
> There may be implications of the extra code introduced by this, but
> I am not familiar with these functions. Though I can confirm that
> the resulting build seems to work.

Yeah, lockdep is going to complain loudly about that. The reason for the
__ versions is we release the lock in a different thread than we acquire
it in. There used to be down_read_non_owner() and up_read_non_owner(),
but those went away... I'll have to investigate further.

> ---
>  block/bcache.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/block/bcache.c b/block/bcache.c
> index a2dbd1e..faaf75e 100644
> --- a/block/bcache.c
> +++ b/block/bcache.c
> @@ -5561,7 +5561,7 @@ static void bio_complete(struct closure *cl)
>  	keylist_free(&s->op.keys);
>  
>  	if (s->op.insert_type & INSERT_WRITE)
> -		__up_read(&d->writeback_lock);
> +		up_read(&d->writeback_lock);
>  
>  	if (s->cache_bio) {
>  		int i;
> @@ -5911,7 +5911,7 @@ static void request_write(struct search *s)
>  	s->cl.fn		= bio_complete;
>  	s->op.insert_type	= INSERT_WRITE;
>  	check_should_skip(s);
> -	__down_read(&s->op.d->writeback_lock);
> +	down_read(&s->op.d->writeback_lock);
>  
>  	if (in_writeback(s->op.d, bio->bi_sector, bio_sectors(bio))) {
>  		s->skip = false;
> -- 
> 1.7.4.4
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: First observations with bcache

[Kent Overstreet]

Ok, I should have all the issues you found fixed. They're only compile
tested but they should be correct - tomorrow I'll pull them into the dev
branch and test them.

But I got that and the most recent stable code pushed to the public
repository. I got rid of the 2.6.34 branch, the bcache branch is now
based off 3.1.

You got it up and running? How's it working?

On Sat, Sep 10, 2011 at 02:44:56PM +0100, Mark Hills wrote:
> I took some time to try out bcache, on an x86 Dell PC with OCZ Agility 3 
> SSD.
> 
> The good news is that once I had applied various workarounds, thing seems 
> to work as expected, both with 2.6.34 and with an updated 3.1 branch.
> 
> I had to make a few modifications to get going, and then more to enable 
> the various debug options.
> 
> The most awkward problems seem to be the result of 32-bit architecture, 
> and I think are highlighted by building as a module.
> 
> I'll follow-up this email with the patches (based on bcache-3.1 branch), 
> though I don't consider them to be long-term solutions; they show the 
> changes I made.
> 
> I some cases I've proposed a better solution, but thought I'd raise them 
> here for discussion first.
> 
> -- 
> Mark
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: First observations with bcache

[Mark Hills]

On Wed, 21 Sep 2011, Kent Overstreet wrote:

> Ok, I should have all the issues you found fixed. They're only compile
> tested but they should be correct - tomorrow I'll pull them into the dev
> branch and test them.

You mean commit a1f7b3d? I checked this out quickly now, but on install 
got:

  DEPMOD  3.1.0-rc7-bcache+
  WARNING: Loop detected: /lib/modules/3.1.0-rc7-bcache+/kernel/block/bcache.ko needs bcache_util.ko which needs bcache.ko again!
  WARNING: Module /lib/modules/3.1.0-rc7-bcache+/kernel/block/bcache.ko ignored, due to loop
  WARNING: Module /lib/modules/3.1.0-rc7-bcache+/kernel/block/bcache_util.ko ignored, due to loop

Perhaps I will look in more detail tomorrow.

Did you make any steps in removing -std=gnu99? I think this is a must; I 
could not see this trend elsewhere in the existing kernel code.

> But I got that and the most recent stable code pushed to the public 
> repository. I got rid of the 2.6.34 branch, the bcache branch is now 
> based off 3.1.
> 
> You got it up and running? How's it working?

Hi, yes I did get it running before. The effect of the caching in tests 
was as I'd hoped; it felt like it was working well.

Something I found particularly interesting is the pass-through for 
sequential operations. With an SSD an order of magnitude faster than HDD, 
it seems like an interesting part of the project could be in the 
heuristics for this.

But I haven't been using it as I'd hoped, because of re-formatting the 
source device. IMO this is an unnecessary barrier to adoption. Flashcache, 
dm-cache etc. show a simple design that doesn't require this.

Whilst the aims of auto-configuration, thin provisioning, tiering etc. are 
admirable, it feels rather ambitious.

I mentioned on IRC the other week: I'd like to see bcache focus on the 
cache. From a user perspective, it already has a major contribution in 
this area, and could slot in neatly to provide this -- such as within 
device-mapper.

It would also have a clear position in the existing structure, which would 
ease the review process and leave the focus on the code quality and docs.

Thanks

-- 
Mark