[PATCH 02/17] xfs: create a big array data structure

["Darrick J. Wong" <darrick.wong@oracle.com>]

From: Darrick J. Wong <darrick.wong@oracle.com>

Create a simple 'big array' data structure for storage of fixed-size
metadata records that will be used to reconstruct a btree index.  For
repair operations, the most important operations are append, iterate,
and sort; while supported, get and put are not for frequent use.

For the initial implementation we will use linked-list containers,
though a subsequent patch will restructure the backend to avoid using
pinned kernel memory.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
 fs/xfs/Makefile      |    1 
 fs/xfs/scrub/array.c |  283 ++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/array.h |   53 +++++++++
 3 files changed, 337 insertions(+)
 create mode 100644 fs/xfs/scrub/array.c
 create mode 100644 fs/xfs/scrub/array.h


diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile
index 9c5542ef0495..bd781606719f 100644
--- a/fs/xfs/Makefile
+++ b/fs/xfs/Makefile
@@ -165,6 +165,7 @@ xfs-$(CONFIG_XFS_QUOTA)		+= scrub/quota.o
 ifeq ($(CONFIG_XFS_ONLINE_REPAIR),y)
 xfs-y				+= $(addprefix scrub/, \
 				   agheader_repair.o \
+				   array.o \
 				   bitmap.o \
 				   repair.o \
 				   )
diff --git a/fs/xfs/scrub/array.c b/fs/xfs/scrub/array.c
new file mode 100644
index 000000000000..7871e8dcad5c
--- /dev/null
+++ b/fs/xfs/scrub/array.c
@@ -0,0 +1,283 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Copyright (C) 2018 Oracle.  All Rights Reserved.
+ * Author: Darrick J. Wong <darrick.wong@oracle.com>
+ */
+#include "xfs.h"
+#include "xfs_fs.h"
+#include "xfs_shared.h"
+#include "scrub/array.h"
+
+/*
+ * XFS Fixed-Size Big Memory Array
+ * ===============================
+ * The big memory array uses a list to store large numbers of fixed-size
+ * records in memory.  Access to the array is performed via indexed get and put
+ * methods, and an append method is provided for convenience.  Array elements
+ * can be set to all zeroes, which means that the entry is NULL and will be
+ * skipped during iteration.
+ */
+
+struct xa_item {
+	struct list_head	list;
+	/* array item comes after here */
+};
+
+#define XA_ITEM_SIZE(sz)	(sizeof(struct xa_item) + (sz))
+
+/* Initialize a big memory array. */
+struct xfbma *
+xfbma_init(
+	size_t		obj_size)
+{
+	struct xfbma	*array;
+	int		error;
+
+	error = -ENOMEM;
+	array = kmem_alloc(sizeof(struct xfbma) + obj_size,
+			KM_NOFS | KM_MAYFAIL);
+	if (!array)
+		return ERR_PTR(error);
+
+	array->obj_size = obj_size;
+	array->nr = 0;
+	INIT_LIST_HEAD(&array->list);
+	memset(&array->cache, 0, sizeof(array->cache));
+
+	return array;
+}
+
+void
+xfbma_destroy(
+	struct xfbma	*array)
+{
+	struct xa_item	*item, *n;
+
+	list_for_each_entry_safe(item, n, &array->list, list) {
+		list_del(&item->list);
+		kmem_free(item);
+	}
+	kmem_free(array);
+}
+
+/* Find something in the cache. */
+static struct xa_item *
+xfbma_cache_lookup(
+	struct xfbma	*array,
+	uint64_t	nr)
+{
+	uint64_t	i;
+
+	for (i = 0; i < XMA_CACHE_SIZE; i++)
+		if (array->cache[i].nr == nr && array->cache[i].item)
+			return array->cache[i].item;
+	return NULL;
+}
+
+/* Invalidate the lookup cache. */
+static void
+xfbma_cache_invalidate(
+	struct xfbma	*array)
+{
+	memset(array->cache, 0, sizeof(array->cache));
+}
+
+/* Put something in the cache. */
+static void
+xfbma_cache_store(
+	struct xfbma	*array,
+	uint64_t	nr,
+	struct xa_item	*item)
+{
+	memmove(array->cache + 1, array->cache,
+			sizeof(struct xma_cache) * (XMA_CACHE_SIZE - 1));
+	array->cache[0].item = item;
+	array->cache[0].nr = nr;
+}
+
+/* Find a particular array item. */
+static struct xa_item *
+xfbma_lookup(
+	struct xfbma	*array,
+	uint64_t	nr)
+{
+	struct xa_item	*item;
+	uint64_t	i;
+
+	if (nr >= array->nr) {
+		ASSERT(0);
+		return NULL;
+	}
+
+	item = xfbma_cache_lookup(array, nr);
+	if (item)
+		return item;
+
+	i = 0;
+	list_for_each_entry(item, &array->list, list) {
+		if (i == nr) {
+			xfbma_cache_store(array, nr, item);
+			return item;
+		}
+		i++;
+	}
+	return NULL;
+}
+
+/* Get an element from the array. */
+int
+xfbma_get(
+	struct xfbma	*array,
+	uint64_t	nr,
+	void		*ptr)
+{
+	struct xa_item	*item;
+
+	item = xfbma_lookup(array, nr);
+	if (!item)
+		return -ENODATA;
+	memcpy(ptr, item + 1, array->obj_size);
+	return 0;
+}
+
+/* Put an element in the array. */
+int
+xfbma_set(
+	struct xfbma	*array,
+	uint64_t	nr,
+	void		*ptr)
+{
+	struct xa_item	*item;
+
+	item = xfbma_lookup(array, nr);
+	if (!item)
+		return -ENODATA;
+	memcpy(item + 1, ptr, array->obj_size);
+	return 0;
+}
+
+/* Is this array element NULL? */
+bool
+xfbma_is_null(
+	struct xfbma	*array,
+	void		*ptr)
+{
+	return !memchr_inv(ptr, 0, array->obj_size);
+}
+
+/* Put an element anywhere in the array that isn't NULL. */
+int
+xfbma_insert_anywhere(
+	struct xfbma	*array,
+	void		*ptr)
+{
+	struct xa_item	*item;
+
+	/* Find a null slot to put it in. */
+	list_for_each_entry(item, &array->list, list) {
+		if (!xfbma_is_null(array, item + 1))
+			continue;
+		memcpy(item + 1, ptr, array->obj_size);
+		return 0;
+	}
+
+	/* No null slots, just dump it on the end. */
+	return xfbma_append(array, ptr);
+}
+
+/* NULL an element in the array. */
+int
+xfbma_nullify(
+	struct xfbma	*array,
+	uint64_t	nr)
+{
+	struct xa_item	*item;
+
+	item = xfbma_lookup(array, nr);
+	if (!item)
+		return -ENODATA;
+	memset(item + 1, 0, array->obj_size);
+	return 0;
+}
+
+/* Append an element to the array. */
+int
+xfbma_append(
+	struct xfbma	*array,
+	void		*ptr)
+{
+	struct xa_item	*item;
+
+	item = kmem_alloc(XA_ITEM_SIZE(array->obj_size), KM_NOFS | KM_MAYFAIL);
+	if (!item)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD(&item->list);
+	memcpy(item + 1, ptr, array->obj_size);
+	list_add_tail(&item->list, &array->list);
+	array->nr++;
+	return 0;
+}
+
+/*
+ * Iterate every element in this array, freeing each element as we go.
+ * Array elements will be shifted down.
+ */
+int
+xfbma_iter_del(
+	struct xfbma	*array,
+	xfbma_iter_fn	iter_fn,
+	void		*priv)
+{
+	struct xa_item	*item, *n;
+	int		error = 0;
+
+	list_for_each_entry_safe(item, n, &array->list, list) {
+		if (xfbma_is_null(array, item + 1))
+			goto next;
+		memcpy(array + 1, item + 1, array->obj_size);
+		error = iter_fn(array + 1, priv);
+		if (error)
+			break;
+next:
+		list_del(&item->list);
+		kmem_free(item);
+		array->nr--;
+	}
+
+	xfbma_cache_invalidate(array);
+	return error;
+}
+
+/* Return length of array. */
+uint64_t
+xfbma_length(
+	struct xfbma	*array)
+{
+	return array->nr;
+}
+
+static int
+xfbma_item_cmp(
+	void			*priv,
+	struct list_head	*a,
+	struct list_head	*b)
+{
+	int			(*cmp_fn)(void *a, void *b) = priv;
+	struct xa_item		*ai, *bi;
+
+	ai = container_of(a, struct xa_item, list);
+	bi = container_of(b, struct xa_item, list);
+
+	return cmp_fn(ai + 1, bi + 1);
+}
+
+/* Sort everything in this array. */
+int
+xfbma_sort(
+	struct xfbma	*array,
+	xfbma_cmp_fn	cmp_fn)
+{
+	list_sort(cmp_fn, &array->list, xfbma_item_cmp);
+	return 0;
+}
diff --git a/fs/xfs/scrub/array.h b/fs/xfs/scrub/array.h
new file mode 100644
index 000000000000..a6a7b69dc138
--- /dev/null
+++ b/fs/xfs/scrub/array.h
@@ -0,0 +1,53 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Copyright (C) 2018 Oracle.  All Rights Reserved.
+ * Author: Darrick J. Wong <darrick.wong@oracle.com>
+ */
+#ifndef __XFS_SCRUB_ARRAY_H__
+#define __XFS_SCRUB_ARRAY_H__
+
+struct xma_item;
+
+struct xma_cache {
+	uint64_t	nr;
+	struct xa_item	*item;
+};
+
+#define XMA_CACHE_SIZE	(8)
+
+struct xfbma {
+	struct list_head	list;
+	size_t			obj_size;
+	uint64_t		nr;
+	struct xma_cache	cache[XMA_CACHE_SIZE];
+};
+
+struct xfbma *xfbma_init(size_t obj_size);
+void xfbma_destroy(struct xfbma *array);
+int xfbma_get(struct xfbma *array, uint64_t nr, void *ptr);
+int xfbma_set(struct xfbma *array, uint64_t nr, void *ptr);
+int xfbma_insert_anywhere(struct xfbma *array, void *ptr);
+bool xfbma_is_null(struct xfbma *array, void *ptr);
+int xfbma_nullify(struct xfbma *array, uint64_t nr);
+int xfbma_append(struct xfbma *array, void *ptr);
+uint64_t xfbma_length(struct xfbma *array);
+
+/*
+ * Iterator functions return zero for success, a negative error code to abort
+ * with an error, or XFBMA_ITERATE_ABORT to stop iterating.
+ */
+#define XFBMA_ITERATE_ABORT	(1)
+typedef int (*xfbma_iter_fn)(const void *item, void *priv);
+
+int xfbma_iter_del(struct xfbma *array, xfbma_iter_fn iter_fn, void *priv);
+
+typedef int (*xfbma_cmp_fn)(const void *a, const void *b);
+
+int xfbma_sort(struct xfbma *array, xfbma_cmp_fn cmp_fn);
+
+#define foreach_xfbma_item(array, i, rec) \
+	for ((i) = 0; (i) < xfbma_length(array); (i)++) \
+		if (xfbma_get((array), (i), &(rec)) == 0 && \
+		    !xfbma_is_null((array), &(rec)))
+
+#endif /* __XFS_SCRUB_ARRAY_H__ */