dm: add persistent data library

The persistent-data library offers a re-usable framework for the storage
and management of on-disk metadata in device-mapper targets.

It's used by the thin-provisioning target in the next patch and in an
upcoming hierarchical storage target.

For further information, please read
Documentation/device-mapper/persistent-data.txt

Signed-off-by: Joe Thornber <thornber@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Signed-off-by: Alasdair G Kergon <agk@redhat.com>

21 files changed, 5625 insertions, 0 deletions

diff --git a/drivers/md/persistent-data/Kconfig b/drivers/md/persistent-data/Kconfig
new file mode 100644
index 000000000000..ceb359050a59
--- /dev/null
+++ b/drivers/md/persistent-data/Kconfig
@@ -0,0 +1,8 @@
+config DM_PERSISTENT_DATA
+       tristate
+       depends on BLK_DEV_DM && EXPERIMENTAL
+       select LIBCRC32C
+       select DM_BUFIO
+       ---help---
+         Library providing immutable on-disk data structure support for
+         device-mapper targets such as the thin provisioning target.
diff --git a/drivers/md/persistent-data/Makefile b/drivers/md/persistent-data/Makefile
new file mode 100644
index 000000000000..cfa95f662230
--- /dev/null
+++ b/drivers/md/persistent-data/Makefile
@@ -0,0 +1,11 @@
+obj-$(CONFIG_DM_PERSISTENT_DATA) += dm-persistent-data.o
+dm-persistent-data-objs := \
+        dm-block-manager.o \
+        dm-space-map-checker.o \
+        dm-space-map-common.o \
+        dm-space-map-disk.o \
+        dm-space-map-metadata.o \
+        dm-transaction-manager.o \
+        dm-btree.o \
+        dm-btree-remove.o \
+        dm-btree-spine.o
diff --git a/drivers/md/persistent-data/dm-block-manager.c b/drivers/md/persistent-data/dm-block-manager.c
new file mode 100644
index 000000000000..0317ecdc6e53
--- /dev/null
+++ b/drivers/md/persistent-data/dm-block-manager.c
@@ -0,0 +1,620 @@
+/*
+ * Copyright (C) 2011 Red Hat, Inc.
+ *
+ * This file is released under the GPL.
+ */
+#include "dm-block-manager.h"
+#include "dm-persistent-data-internal.h"
+#include "../dm-bufio.h"
+
+#include <linux/crc32c.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/rwsem.h>
+#include <linux/device-mapper.h>
+#include <linux/stacktrace.h>
+
+#define DM_MSG_PREFIX "block manager"
+
+/*----------------------------------------------------------------*/
+
+/*
+ * This is a read/write semaphore with a couple of differences.
+ *
+ * i) There is a restriction on the number of concurrent read locks that
+ * may be held at once.  This is just an implementation detail.
+ *
+ * ii) Recursive locking attempts are detected and return EINVAL.  A stack
+ * trace is also emitted for the previous lock aquisition.
+ *
+ * iii) Priority is given to write locks.
+ */
+#define MAX_HOLDERS 4
+#define MAX_STACK 10
+
+typedef unsigned long stack_entries[MAX_STACK];
+
+struct block_lock {
+        spinlock_t lock;
+        __s32 count;
+        struct list_head waiters;
+        struct task_struct *holders[MAX_HOLDERS];
+
+#ifdef CONFIG_DM_DEBUG_BLOCK_STACK_TRACING
+        struct stack_trace traces[MAX_HOLDERS];
+        stack_entries entries[MAX_HOLDERS];
+#endif
+};
+
+struct waiter {
+        struct list_head list;
+        struct task_struct *task;
+        int wants_write;
+};
+
+static unsigned __find_holder(struct block_lock *lock,
+                              struct task_struct *task)
+{
+        unsigned i;
+
+        for (i = 0; i < MAX_HOLDERS; i++)
+                if (lock->holders[i] == task)
+                        break;
+
+        BUG_ON(i == MAX_HOLDERS);
+        return i;
+}
+
+/* call this *after* you increment lock->count */
+static void __add_holder(struct block_lock *lock, struct task_struct *task)
+{
+        unsigned h = __find_holder(lock, NULL);
+#ifdef CONFIG_DM_DEBUG_BLOCK_STACK_TRACING
+        struct stack_trace *t;
+#endif
+
+        get_task_struct(task);
+        lock->holders[h] = task;
+
+#ifdef CONFIG_DM_DEBUG_BLOCK_STACK_TRACING
+        t = lock->traces + h;
+        t->nr_entries = 0;
+        t->max_entries = MAX_STACK;
+        t->entries = lock->entries[h];
+        t->skip = 2;
+        save_stack_trace(t);
+#endif
+}
+
+/* call this *before* you decrement lock->count */
+static void __del_holder(struct block_lock *lock, struct task_struct *task)
+{
+        unsigned h = __find_holder(lock, task);
+        lock->holders[h] = NULL;
+        put_task_struct(task);
+}
+
+static int __check_holder(struct block_lock *lock)
+{
+        unsigned i;
+#ifdef CONFIG_DM_DEBUG_BLOCK_STACK_TRACING
+        static struct stack_trace t;
+        static stack_entries entries;
+#endif
+
+        for (i = 0; i < MAX_HOLDERS; i++) {
+                if (lock->holders[i] == current) {
+                        DMERR("recursive lock detected in pool metadata");
+#ifdef CONFIG_DM_DEBUG_BLOCK_STACK_TRACING
+                        DMERR("previously held here:");
+                        print_stack_trace(lock->traces + i, 4);
+
+                        DMERR("subsequent aquisition attempted here:");
+                        t.nr_entries = 0;
+                        t.max_entries = MAX_STACK;
+                        t.entries = entries;
+                        t.skip = 3;
+                        save_stack_trace(&t);
+                        print_stack_trace(&t, 4);
+#endif
+                        return -EINVAL;
+                }
+        }
+
+        return 0;
+}
+
+static void __wait(struct waiter *w)
+{
+        for (;;) {
+                set_task_state(current, TASK_UNINTERRUPTIBLE);
+
+                if (!w->task)
+                        break;
+
+                schedule();
+        }
+
+        set_task_state(current, TASK_RUNNING);
+}
+
+static void __wake_waiter(struct waiter *w)
+{
+        struct task_struct *task;
+