Bcache v. whatever

Bcache: a block layer SSD cache

Does writethrough and writeback, handles unclean shutdown, and has various other nifty features. See the wiki and the documentation for more:

http://bcache.evilpiepirate.org

Over the Christmas break I finally got the tree into a self contained state that ought to be suitable for merging; this tree is fairly close to the previous stable tree that people have been running on production servers for awhile (and that I've been running on this workstation),

So, I think this is ready for mainline and I'd like to get it in. I should've tried to push it ages ago, but I was hoping to get in various block layer cleanups first; I finally deided to work around them in the meantime since I haven't had time to finish the block layer stuff.

Not everything has been addressed since I last posted for review feedback - notably the closure code was controversial and for now I've just moved that into drivers/block/bcache (though I've been refactoring stuff to make it less asynchronous lately; most of that work is in the testing/dev branches). The bigger issue IMO is the userspace interface - I'd like to finish the md integration so it doesn't need userspace stuff for probing/bootup. So, I'd be fine with it going into staging if that's the consensus, but it's stable tested code.

The code is available at
http://evilpiepirate.org/git/linux-bcache.git bcache-for-upstream

This latest branch is on top of v3.8-rc3:

----------------------------------------------------------------
Kent Overstreet (5):
Revert "rw_semaphore: remove up/down_read_non_owner" Export get_random_int()
Export blk_fill_rwbs()
Export __lockdep_no_validate__
bcache: A block layer cache

 Documentation/ABI/testing/sysfs-block-bcache |  156 ++
 Documentation/bcache.txt                     |  343 ++++
 drivers/char/random.c                        |    1 +
 drivers/md/Kconfig                           |    2 +
 drivers/md/Makefile                          |    1 +
 drivers/md/bcache/Kconfig                    |   41 +
 drivers/md/bcache/Makefile                   |   14 +
 drivers/md/bcache/alloc.c                    |  612 +++++++
 drivers/md/bcache/bcache.h                   | 1207 +++++++++++++
 drivers/md/bcache/bset.c                     | 1175 ++++++++++++
 drivers/md/bcache/bset.h                     |  378 ++++
 drivers/md/bcache/btree.c                    | 2497 ++++++++++++++++++++++++++
 drivers/md/bcache/btree.h                    |  412 +++++
 drivers/md/bcache/closure.c                  |  347 ++++
 drivers/md/bcache/closure.h                  |  670 +++++++
 drivers/md/bcache/debug.c                    |  550 ++++++
 drivers/md/bcache/debug.h                    |   54 +
 drivers/md/bcache/io.c                       |  383 ++++
 drivers/md/bcache/journal.c                  |  703 ++++++++
 drivers/md/bcache/journal.h                  |  159 ++
 drivers/md/bcache/movinggc.c                 |  245 +++
 drivers/md/bcache/request.c                  | 1370 ++++++++++++++
 drivers/md/bcache/request.h                  |   61 +
 drivers/md/bcache/stats.c                    |  239 +++
 drivers/md/bcache/stats.h                    |   58 +
 drivers/md/bcache/super.c                    | 1952 ++++++++++++++++++++
 drivers/md/bcache/sysfs.c                    |  807 +++++++++
 drivers/md/bcache/sysfs.h                    |   98 +
 drivers/md/bcache/trace.c                    |   26 +
 drivers/md/bcache/util.c                     |  382 ++++
 drivers/md/bcache/util.h                     |  587 ++++++
 drivers/md/bcache/writeback.c                |  406 +++++
 include/linux/cgroup_subsys.h                |    6 +
 include/linux/rwsem.h                        |   10 +
 include/linux/sched.h                        |    4 +
 include/trace/events/bcache.h                |  271 +++
 kernel/fork.c                                |    4 +
 kernel/lockdep.c                             |    1 +
 kernel/rwsem.c                               |   16 +
 kernel/trace/blktrace.c                      |    1 +
 40 files changed, 16249 insertions(+)
 create mode 100644 Documentation/ABI/testing/sysfs-block-bcache
 create mode 100644 Documentation/bcache.txt
 create mode 100644 drivers/md/bcache/Kconfig
 create mode 100644 drivers/md/bcache/Makefile
 create mode 100644 drivers/md/bcache/alloc.c
 create mode 100644 drivers/md/bcache/bcache.h
 create mode 100644 drivers/md/bcache/bset.c
 create mode 100644 drivers/md/bcache/bset.h
 create mode 100644 drivers/md/bcache/btree.c
 create mode 100644 drivers/md/bcache/btree.h
 create mode 100644 drivers/md/bcache/closure.c
 create mode 100644 drivers/md/bcache/closure.h
 create mode 100644 drivers/md/bcache/debug.c
 create mode 100644 drivers/md/bcache/debug.h
 create mode 100644 drivers/md/bcache/io.c
 create mode 100644 drivers/md/bcache/journal.c
 create mode 100644 drivers/md/bcache/journal.h
 create mode 100644 drivers/md/bcache/movinggc.c
 create mode 100644 drivers/md/bcache/request.c
 create mode 100644 drivers/md/bcache/request.h
 create mode 100644 drivers/md/bcache/stats.c
 create mode 100644 drivers/md/bcache/stats.h
 create mode 100644 drivers/md/bcache/super.c
 create mode 100644 drivers/md/bcache/sysfs.c
 create mode 100644 drivers/md/bcache/sysfs.h
 create mode 100644 drivers/md/bcache/trace.c
 create mode 100644 drivers/md/bcache/util.c
 create mode 100644 drivers/md/bcache/util.h
 create mode 100644 drivers/md/bcache/writeback.c
 create mode 100644 include/trace/events/bcache.h

If it goes into staging, I need a reason why it can't be merged into the "real" part of the kernel, and what will be done to get it there.

Oh, and you will need to get acks from the people who's symbols you are wanting to export, usually staging patches are self-contained.

thanks,

greg k-h

I don't personally see why it can't, but maybe other people will chime in. There's certainly still stuff to do (something this size is never finished) but I'm not abandoning the code.

Yeah, good point. I'll mail out those patches now.

Ok, then it should be accepted, care to make it up into a format that can be applied to someone's tree? We can't do anything in the current git-tree format it is in today.

thanks,

greg k-h

The guy to merge this is the maintainer in that layer, which is Alasdair Kergon. I know you've been sending patches to the dm-devel list, what's the reason you didn't include him in the cc list? Is there some type of political problem in dm? From reading the list, it looks like your patches are being tested and progressing, so what am I missing?

James

That was merely an oversight - but, bcache is currently just another block device, it doesn't plug into dm or md. There was some md integration work started, and that's the one I'm more inclined to work on personally (if and when I find the time).

So I'm not sure why it'd go in via dm, it seems to me it'd make just as much sense for it to go in via Neil Brown's tree. Unless there's something I'm missing?

I think md integration would be a bit of a mistake, since md is pretty much only a raid engine at this point in time. There are also a couple of other dm cache targets, so it would be nice to have one rather than three. This all, however, seems to be under discussion on the dm list.

Um, well there's no caching patches in the md tree; it's RAID only. The basic caching stuff is all in the dm tree, which is why it's the natural one.

It seems to me that your stuff is progressing on the dm list, so I don't really see a need to circumvent the process in the dm tree ... unless there's some problem I'm not seeing?

James

The raid vs. caching bit is a bit beside the point IMO; they both aggregate block devices and expose virtual block devices, and the mechanism for doing so isn't part of the generic framework.

I'm not morally opposed to dm integration, I'm just more comfortable with the md code and find it easier to understand and work with.

And the goal I care about is just commonality of userspace interfaces and tooling, which integration with either would accomplish.

I haven't been active on dm-devel, besides the occasional cross posting... not sure what activity you're referring to on the dm list,

But if Alasdair wants to pick it up I'm not complaining, I don't particularly care who merges it.

A caching framework based on dm has been proposed by Joe Thornber (the original author of dm).

Mike Snitzer is trying to adapt the performance tests for this dm-based framework to include the latest bcache code that you just posted to start to give us an idea of the circumstances in which each of them work well (or badly).

1, Caching is a complicated feature: It's easy to get no benefit or even a negative benefit from a cache if you use an inappropriate policy or don't tune it to your I/O patterns.

2. We now have several independent/overlapping implementations of this type of caching. Comparing and contrasting them should help us to tease out the critical design elements and optimisations and decide which of them together or separately (or some hybrid) would enable the kernel to support the widest range of situations users require with the minimum of code and complexity.

3. We all want to move quickly now, perhaps even with something in the next merge window if we can or otherwise the one after that.

Alasdair

Unfortunately, the first automated test in the thinp-test-suite that I ported to work with Bcache fails, here is a shell script that reproduces the problem (having bcache use a small SSD is key to reproducing):

## /dev/spindle/data is a 16G linear LV on a SAS spindle
## /dev/stec/256m_lv is a 256M linear LV on a PCI-e SSD
## (larger SSD volume doesn't have this problem; because the working set fits better?) make-bcache -B /dev/spindle/data -C /dev/stec/256m_lv --cache_replacement_policy=fifo -w 4096 --writeback --discard echo /dev/spindle/data > /sys/fs/bcache/register
echo /dev/stec/256m_lv > /sys/fs/bcache/register
DM_DEV_NAME=$(basename readlink /dev/mapper/spindle-data)
BCACHE_DEV=$(basename readlink /sys/block/${DM_DEV_NAME}/bcache/dev)
mkfs.ext4 -E lazy_itable_init=1 /dev/${BCACHE_DEV}
mkdir ./kernel_builds
mount /dev/${BCACHE_DEV} ./kernel_builds -o discard
cd ./kernel_builds
## /root/linux-github is a local clone of linus' git repo
git clone /root/linux-github linux
cd linux
git checkout v2.6.12
sync
echo 3 > /proc/sys/vm/drop_caches

The drop_caches hangs (sh spins eating cpu), and ./kernel_builds cannot be unmounted:

# ps auwwx | grep spin_bcache
root     18148 98.4  0.0 106208  1320 pts/2    R+   17:42  49:39 /bin/sh /root/bin/spin_bcache

spin_bcache R running task 0 18148 4886 0x00000000
00000000154d154d 0000000000000000 ffff8802edc00d90 ffff88032d395e48 0000000000000001 ffffffffffffff10 0000000000000018 ffff8802f9802800 ffff88032d395d28 ffffffff8116b8d5 ffff88032de6f000 ffff880332682800

Call Trace:
 [<ffffffff814f67e2>] ? _raw_spin_lock+0x12/0x30
 [<ffffffff8116b8d5>] ? put_super+0x25/0x40
 [<ffffffff8116ba65>] ? grab_super_passive+0x25/0xa0
 [<ffffffff8116bb3f>] ? prune_super+0x5f/0x1a0
 [<ffffffff8111d131>] ? shrink_slab+0xa1/0x2c0
 [<ffffffff8111d096>] ? shrink_slab+0x6/0x2c0
 [<ffffffff81194b22>] ? drop_caches_sysctl_handler+0x62/0x90
 [<ffffffff811d7f56>] ? proc_sys_call_handler+0x96/0xd0
 [<ffffffff811d7fa4>] ? proc_sys_write+0x14/0x20
 [<ffffffff81169194>] ? vfs_write+0xb4/0x130
 [<ffffffff8116993f>] ? sys_write+0x5f/0xa0
 [<ffffffff814ff119>] ? system_call_fastpath+0x16/0x1b

This reverts commit 11b80f459adaf91a712f95e7734a17655a36bf30.

Bcache needs rw semaphores for cache coherency in writeback mode - writes have to take a read lock on a per cache device rw sem, and release it when the bio completes.

But since this is for bios it's naturally not in the context of the process that originally took the lock.

---
 include/linux/rwsem.h | 10 ++++++++++
 kernel/rwsem.c        | 16 ++++++++++++++++
 2 files changed, 26 insertions(+)

index 54bd7cd..ddfe46d 100644
@@ -125,9 +125,19 @@ extern void downgrade_write(struct rw_semaphore *sem);
  */
 extern void down_read_nested(struct rw_semaphore *sem, int subclass);
 extern void down_write_nested(struct rw_semaphore *sem, int subclass);
+/*
+ * Take/release a lock when not the owner will release it.
+ *
+ * [ This API should be avoided as much as possible - the
+ *   proper abstraction for this case is completions. ]
+ */
+extern void down_read_non_owner(struct rw_semaphore *sem);
+extern void up_read_non_owner(struct rw_semaphore *sem);
 #else
 # define down_read_nested(sem, subclass)		down_read(sem)
 # define down_write_nested(sem, subclass)	down_write(sem)
+# define down_read_non_owner(sem)		down_read(sem)
+# define up_read_non_owner(sem)			up_read(sem)
 #endif
 
 #endif /* _LINUX_RWSEM_H */

index 6850f53..78b7915 100644
@@ -116,6 +116,15 @@ void down_read_nested(struct rw_semaphore *sem, int subclass)
 
 EXPORT_SYMBOL(down_read_nested);
 
+void down_read_non_owner(struct rw_semaphore *sem)
+{
+	might_sleep();
+
+	__down_read(sem);
+}
+
+EXPORT_SYMBOL(down_read_non_owner);
+
 void down_write_nested(struct rw_semaphore *sem, int subclass)
 {
 	might_sleep();

@@ -126,6 +135,13 @@ void down_write_nested(struct rw_semaphore *sem, int subclass)
 
 EXPORT_SYMBOL(down_write_nested);
 
+void up_read_non_owner(struct rw_semaphore *sem)
+{
+	__up_read(sem);
+}
+
+EXPORT_SYMBOL(up_read_non_owner);
+
 #endif
 
 

1.7.12

Needed for bcache - need a cheap source of random numbers for perturbing IO sizes, for rate limiting IO to the SSD.

---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

index 85e81ec..d6f673e 100644
@@ -1481,6 +1481,7 @@ unsigned int get_random_int(void)
 
 	return ret;
 }
+EXPORT_SYMBOL(get_random_int);
 
 /*
  * randomize_range() returns a start address such that

1.7.12

Exported so it can be used by bcache's tracepoints

---
 kernel/trace/blktrace.c | 1 +
 1 file changed, 1 insertion(+)

index c0bd030..dbe1667 100644
@@ -1806,6 +1806,7 @@ void blk_fill_rwbs(char *rwbs, u32 rw, int bytes)
 
 	rwbs[i] = '\0';
 }
+EXPORT_SYMBOL_GPL(blk_fill_rwbs);
 
 #endif /* CONFIG_EVENT_TRACING */
 

1.7.12

Li,

Can you give an Ack or Nack for this.

Thanks,

-- Steve

I think this patch shouldn't go into upstream without bcache code. We don't export symbols for out of tree code.

Even for GPL code? I have no problem either way, as we never guarantee a module ABI. Hence, if it is exported, there's no guarantee that it will exist or even act the same in later versions.

Kernel modules (internal, external, GPL or not) don't have the luxury of a stable ABI as user space does.

But I'll take this as a Nack.

Thanks,

-- Steve

Hack, but bcache needs a way around lockdep for locking during garbage collection - we need to keep multiple btree nodes locked for coalescing and rw_lock_nested() isn't really sufficient or appropriate here.

---
 kernel/lockdep.c | 1 +
 1 file changed, 1 insertion(+)

index 7981e5b..861fbeb 100644
@@ -2997,6 +2997,7 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
 struct lock_class_key __lockdep_no_validate__;
+EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
 
 static int
 print_lock_nested_lock_not_held(struct task_struct *curr,

1.7.12

sparc64 gcc-3.4.5:

drivers/md/bcache/btree.c: In function `bch_btree_read':
drivers/md/bcache/btree.c:266: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `__btree_write':
drivers/md/bcache/btree.c:379: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `btree_node_free':
drivers/md/bcache/btree.c:980: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `btree_insert_key':
drivers/md/bcache/btree.c:1857: error: invalid operands to binary + drivers/md/bcache/btree.c:1857: error: invalid operands to binary + drivers/md/bcache/btree.c:1859: error: invalid operands to binary + drivers/md/bcache/btree.c:1859: error: invalid operands to binary + drivers/md/bcache/btree.c:1864: error: invalid operands to binary + drivers/md/bcache/btree.c:1864: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `btree_split':
drivers/md/bcache/btree.c:1934: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `bch_btree_set_root':
drivers/md/bcache/btree.c:2159: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `bch_btree_search_recurse':
drivers/md/bcache/btree.c:2262: error: invalid operands to binary + drivers/md/bcache/btree.c: In function `bch_btree_refill_keybuf':
drivers/md/bcache/btree.c:2330: error: invalid operands to binary +

due to

#define pbtree(b) (&bch_pbtree(b).s[0])

I don't know why this is happening (presumably a gcc glitch), but returning an 80-byte struct by value from bch_pkey() and bch_pbtree() is just gruesome. The compiler has to allocate the space on the caller stack, pass a hidden pointer into the callee and the callee copies its return value into that caller stack slot. It's slow and consumes stack.

Something different, please.

Well, it is kind of... perverse but really the compiler's doing exactly what I would've had to do otherwise - stick a char buf[80] on the caller's stack and pass it to bch_pbtree(). With the caveat that I haven't looked at the generated code.

As far as I can tell the only real improvement would be to add a %p format string to vsnprintf, but adding a global extension would obviously be inappropriate for this. It'd be really nice to have a mechanism for adding file/module private format strings to vsnprintf, but I haven't cared enough yet to implement it myself.

Of course if you know a better solution I'm all ears.

Uhm, as for the actual bug - that is a fairly ancient gcc, I wasn't aware we were supporting compilers that old but I'm sure you wouldn't be bugging me about it if we weren't...

If you _really_ want me to rip out the macro/struct return hack I will... but this is just debug code and I hate making it more verbose if I don't have to.

Otherwise, I'll set up gcc-3.4.5 (hopefully it doesn't have to be a sparc compiler :P) and see if I can get gcc to stop complaining.

That's the more idiomatic way of doing things and yes, the code generation will be similarly awful.

Documentation/Changes is the official status. It says gcc-3.2+. We're very slow in updating those version numbers because it's hard. gcc-3.4.5 for mips fails in the same way.

Why are those things macros anyway? urgh, it's because we want to jam a string into the caller's stack frame without declaring any of it.

Really I do think it would be better to do away with the C party tricks and have callers do

	char btree_buf[BTREE_BUF_SIZE];

	btree_to_text(btree_buf, b);
	pr_debug("%s\n", btree_buf);

Nice, simple, explicit, direct and stupid. It might generate unused-var warnings if DEBUG is undefined but from my reading of pr_debug() things will be OK.

Then we can poke around at btree_to_text() until gcc-3.4.5 is happy with it.

Well, it also _used_ to be the case that if DEBUG and CONFIG_DYNAMIC_DEBUG weren't defined then pr_debug() was defined as an empty macro, so btree_to_text() wouldn't be called.

But, I just checked and it's been converted to an empty inline function, and some of this debug code is called from fast paths where the overhead really does matter :/ argh

Well, since pr_debug() isn't an empty macro anymore there goes my main reason for keeping these macros around.

seems like pr_debug() could still have the no_printk() call inside an if (0) though...

argh. If there was some way to tell gcc "this function only modifies this argument so you don't have to call it if the output is never used" then I'd just convert it to the explicit bufs now. But I really can't have btree_to_text()/bkey_to_text() getting called in non debug kernels...

I'm going to mull it over a bit for now, and try and decide what's least ugly.