bcache: cache a block device with an ssd (now with fewer bugs!)

For those who missed the first version, I outlined the general
architecture: http://lkml.indiana.edu/hypermail//linux/kernel/1004.0/01051.html

For those who did read it, my apologies, this version is slightly less likely to make your eyes bleed. I've put a lot of effort into getting the code cleaned up and debugged; it's definitely taking shape. I'd really welcome any and all comments on the design and such at this point, including pointing out all the things I've done horribly wrong.

In this version the only real bug I know of (vs. stuff that's broken because it's unimplemented) is a deadlock caused by waiting on pages to be unlocked - in certain circumstances, it's possible to wait before the io has been submitted, and since the btree code is usually called from __generic_make_request it'll never get issued. The ideal way for me to handle this would be to get a callback when a page is unlocked, but I don't see a good way of doing this. The alternate solution would be not relying on page locking at all - having a per btree bucket struct that holds references to all its pages. It seems to me that this may be the way to go anyways to avoid the overhead of find_get_pages() on every bio, but I'm hoping to get some input before I go off and code that.

Locking is currently mostly unimplemented, waiting on the solution to the previous problem to be determined.

I'm also still missing some error handling, but it should now tolerate any on disk corruption and I think I may have the btrees just about worked out; splitting and such works reliably now, vs. the last one where it was horribly broken.

My other main unresolved issue is, given a bio how to determine which device it goes to. Originally I was using bio->bi_bdev, strictly as a hack to get it working, then I found it changing back and forth between the original value and a different one for no apparant reason. It looks like struct gendisk or something inside it might be what I want, except that previous to the device being opened bdev->block_device is null. Presumably it could be frobbed somehow to make it non null, but I have yet to discover how this is accomplished. Any pointers would be much appreciated.

As always, any review/input greatly appreciated. The make a cache device program is again at the bottom:

index f9e89f4..85adf8d 100644
@@ -100,6 +100,11 @@ config DEBUG_BLK_CGROUP
 	in the blk group which can be used by cfq for tracing various
 	group related activity.
 
+config BLK_CACHE
+	tristate "Block device as cache"
+	select SLOW_WORK
+	default m
+
 endif # BLOCK
 
 config BLOCK_COMPAT

index cb2d515..e9b5fc0 100644
@@ -15,3 +15,5 @@ obj-$(CONFIG_IOSCHED_CFQ)	+= cfq-iosched.o
 
 obj-$(CONFIG_BLOCK_COMPAT)	+= compat_ioctl.o
 obj-$(CONFIG_BLK_DEV_INTEGRITY)	+= blk-integrity.o
+
+obj-$(CONFIG_BLK_CACHE)		+= bcache.o

index 9fe174d..41b4d21 100644
@@ -1405,7 +1405,7 @@ static inline void __generic_make_request(struct bio *bio)
 {
 	struct request_queue *q;
 	sector_t old_sector;
-	int ret, nr_sectors = bio_sectors(bio);
+	int ret = 1, nr_sectors = bio_sectors(bio);
 	dev_t old_dev;
 	int err = -EIO;
 

@@ -1478,7 +1478,10 @@ static inline void __generic_make_request(struct bio *bio)
 
 		trace_block_bio_queue(q, bio);
 
-		ret = q->make_request_fn(q, bio);
+		if (bio->bi_bdev->bd_cache_fn)
+			ret = bio->bi_bdev->bd_cache_fn(q, bio);
+		if (ret)
+			ret = q->make_request_fn(q, bio);
 	} while (ret);
 
 	return;

index a7c540f..75f4933 100644
@@ -412,7 +412,7 @@ struct os_cookie {
 #define PRINT_MAC(addr)	\
 	addr[0], addr[1], addr[2], addr[3], addr[4], addr[5]
 
-#ifdef DBG
+#if 0
 extern unsigned long RTDebugLevel;
 
 #define DBGPRINT_RAW(Level, Fmt)    \

index 39d57bc..8aba38c 100644
@@ -514,6 +514,8 @@ enum positive_aop_returns {
 struct page;
 struct address_space;
 struct writeback_control;
+struct bio;
+struct request_queue;
 
 struct iov_iter {
 	const struct iovec *iov;

@@ -664,6 +666,9 @@ struct block_device {
 	int			bd_invalidated;
 	struct gendisk *	bd_disk;
 	struct list_head	bd_list;
+
+	int (*bd_cache_fn)(struct request_queue *q, struct bio *bio);
+	char			bd_cache_identifier;
 	/*
 	 * Private data.  You must have bd_claim'ed the block_device
 	 * to use this.  NOTE:  bd_claim allows an owner to claim

/*
* make-bcache.c - set up a file/block device as a cache device */
#define _XOPEN_SOURCE 500

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>

const char bcache_magic[] = { 0xc6, 0x85, 0x73, 0xf6, 0x4e, 0x1a, 0x45, 0xca, 0x82, 0x65, 0xf5, 0x7f, 0x48, 0xba, 0x6d, 0x81 };

struct cache_sb {
	uint8_t  magic[16];
	uint32_t version;
	uint16_t block_size;		/* sectors */
	uint16_t bucket_size;		/* sectors */
	uint32_t journal_start;		/* buckets */
	uint32_t first_bucket;		/* start of data */
	uint64_t nbuckets;		/* device size */
	uint64_t first_free_bucket;	/* buckets that have never been used, only increments */
	uint64_t btree_root;
	uint16_t btree_level;
	uint16_t btree_bucket_size;
};

struct bucket_disk {
	uint16_t	priority;
	uint8_t		generation;
} __attribute((packed));

struct btree_node_header {
	uint32_t	csum;
	uint32_t	nkeys;
	uint64_t	random;
};

char zero[4096];

int main(int argc, char **argv)

{
	int ret;
	if (argc < 2) {
		printf("Please supply a device\n");
		return 0;
	}

	int fd = open(argv[1], O_RDWR);
	if (!fd) {
		perror("Can't open dev\n");
		return 0;
	}

	int random = open("/dev/urandom", O_RDONLY);
	if (!random) {
		perror("Can't open urandom\n");
		return 0;
	}

	struct stat statbuf;
	if (fstat(fd, &statbuf)) {
		perror("stat error\n");
		return 0;
	}

	struct cache_sb sb;
	memcpy(sb.magic, bcache_magic, 16);
	sb.version = 0;
	sb.block_size = 8;
	sb.bucket_size = 32;
	sb.nbuckets = statbuf.st_size / (sb.bucket_size * 512);

	do {
		sb.first_bucket = ((--sb.nbuckets * sizeof(struct bucket_disk)) + 4096 * 3)
			/ (sb.bucket_size * 512) + 1;

	} while ((sb.nbuckets + sb.first_bucket) * sb.bucket_size * 512 > statbuf.st_size);

	sb.journal_start = sb.first_bucket;
	sb.first_free_bucket = 1;

	sb.btree_root = sb.first_bucket * sb.bucket_size;
	sb.btree_level = 0;
	sb.btree_bucket_size = 32;

	printf("block_size:		%u\n"
	       "bucket_size:		%u\n"
	       "journal_start:		%u\n"
	       "first_bucket:		%u\n"
	       "nbuckets:		%ju\n"
	       "first_free_bucket:	%ju\n"
	       "btree_bucket_size:	%u\n",
	       sb.block_size,
	       sb.bucket_size,
	       sb.journal_start,
	       sb.first_bucket,
	       sb.nbuckets,
	       sb.first_free_bucket,
	       sb.btree_bucket_size);

	lseek(fd, 4096, SEEK_SET);
	for (int i = 0; i < sb.first_bucket * sb.bucket_size - 8; i++)
		for (int j = 0; j < 512; j += ret)
			if ((ret = write(fd, &zero[0], 512 - j)) < 0)
				goto err;

	if (pwrite(fd, &sb, sizeof(sb), 4096) != sizeof(sb))
		goto err;

	struct bucket_disk b;
	b.priority = ~0;
	b.generation = 1;
	if (pwrite(fd, &b, sizeof(b), 4096 * 3) != sizeof(b))
		goto err;

	struct btree_node_header n = { .nkeys = 0, };
	if (read(random, &n.random, 8) != 8)
		goto err;

	if (pwrite(fd, &n, sizeof(n), sb.btree_root * 512) != sizeof(n))
		goto err;

	return 0;
err:
	perror("write error\n");
}