flexible array implementation

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

Quoted 9 lines · Dave Hansen

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

I need to update this description, but the kerneldoc comments are up to date.

That reminds me... People will get somewhat weird behavior if they mix flex_array_append() and flex_array_put(). Is that OK? Should flex_array_put() modify ->nr_elements to point to the element past the one that was just put()? Should we perhaps drop the append() function and the ->nr_elements variable completely?

Quoted 9 lines · Dave Hansen

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

I need to update this description, but the kerneldoc comments are up to date.

That reminds me... People will get somewhat weird behavior if they mix flex_array_append() and flex_array_put(). Is that OK? Should flex_array_put() modify ->nr_elements to point to the element past the one that was just put()? Should we perhaps drop the append() function and the ->nr_elements variable completely?

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c new file +5 -0

+	dst = &part->elements[offset_inside_part(fa, element_nr)];
+	memcpy(dst, src, fa->element_size);
+	return 0;
+}
+

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c new file +5 -0

+	dst = &part->elements[offset_inside_part(fa, element_nr)];
+	memcpy(dst, src, fa->element_size);
+	return 0;
+}
+

Quoted 5 lines

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

@fa and @flags are not documented.

Quoted 7 lines

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c line 178

Quoted 9 lines

lib/flex_array.c new file +9 -0

+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;

So this may allocate memory, and has disavantages:

- If flex_array_put() is called in atomic context, flags has to be GFP_ATOMIC.
- and thus it may fail.

Since we pass the total_elem to flex_array_alloc(), how about add a flag, and if the flag is set, the alloc() will also allocate all fa_parts?

And add __flex_array_put(), which assumes fa_parts has been allocated.

Quoted 5 lines

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

@fa and @flags are not documented.

Quoted 7 lines

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c line 178

Quoted 9 lines

lib/flex_array.c new file +9 -0

+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;

So this may allocate memory, and has disavantages:

- If flex_array_put() is called in atomic context, flags has to be GFP_ATOMIC.
- and thus it may fail.

Since we pass the total_elem to flex_array_alloc(), how about add a flag, and if the flag is set, the alloc() will also allocate all fa_parts?

And add __flex_array_put(), which assumes fa_parts has been allocated.

Quoted 6 lines · Li Zefan

Quoted 5 lines

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

@fa and @flags are not documented.

True... But one of my pet peeves are kerneldocs like this:

@fa: the flex array
@flags: GFP flags

It's so trivially obvious from looking at the types and the variable names that I'm not sure it's worth the cost of the lines.

Quoted 21 lines

Quoted 7 lines

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c line 178

Quoted 9 lines

lib/flex_array.c new file +9 -0

+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;

So this may allocate memory, and has disavantages:

- If flex_array_put() is called in atomic context, flags has to be GFP_ATOMIC.
- and thus it may fail.

Quoted 4 lines

Since we pass the total_elem to flex_array_alloc(), how about add a flag, and if the flag is set, the alloc() will also allocate all fa_parts?

And add __flex_array_put(), which assumes fa_parts has been allocated.

How about flex_array_prealloc()? It seems to work for all the radix tree users.

Quoted 6 lines · Li Zefan

Quoted 5 lines

+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src: address of data to copy into the array
+ * @element_nr: index of the position in which to insert
+ * the new element.

@fa and @flags are not documented.

True... But one of my pet peeves are kerneldocs like this:

@fa: the flex array
@flags: GFP flags

It's so trivially obvious from looking at the types and the variable names that I'm not sure it's worth the cost of the lines.

Quoted 21 lines

Quoted 7 lines

+ *
+ * Note that this *copies* the contents of @src into
+ * the array. If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */

lib/flex_array.c line 178

Quoted 9 lines

lib/flex_array.c new file +9 -0

+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;

So this may allocate memory, and has disavantages:

- If flex_array_put() is called in atomic context, flags has to be GFP_ATOMIC.
- and thus it may fail.

Quoted 4 lines

Since we pass the total_elem to flex_array_alloc(), how about add a flag, and if the flag is set, the alloc() will also allocate all fa_parts?

And add __flex_array_put(), which assumes fa_parts has been allocated.

How about flex_array_prealloc()? It seems to work for all the radix tree users.

Changes from v1:
- to vs too typo
- added __check_part_and_nr() and gave it a warning
- fixed off-by-one check on __nr_part_ptrs()
- addedFLEX_ARRAY_INIT() macro
- some kerneldoc comments about the capacity with various sized objects
- comments to note lack of locking semantice

--

Once a structure goes over PAGE_SIZE*2, we see occasional allocation failures. Some people have chosen to switch over to things like vmalloc() that will let them keep array-like access to such a large structures. But, vmalloc() has plenty of downsides.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

One thought is that we should perhaps make the base structure half the size on 32-bit arches. That will ensure that someone testing on 32-bit will not get bitten by the size shrinking by half when moving to 64-bit.

We could also potentially just pass the "element_size" into each of the API functions instead of storing it internally. That would get us one more base pointer on 32-bit.

The last improvement that I thought about was letting the individual array members span pages. In this implementation, if you have a 2049-byte object, it will only pack one of them into each "part" with no attempt to pack them. At this point, I don't think the added complexity would be worth it.

Signed-off-by Dave Hansen <[email protected]>

---

linux-2.6.git-dave/include/linux/flex_array.h |   45 +++++
linux-2.6.git-dave/lib/Makefile               |    2 
linux-2.6.git-dave/lib/flex_array.c           |  230 ++++++++++++++++++++++++++
3 files changed, 276 insertions(+), 1 deletion(-)

diff -puN /dev/null include/linux/flex_array.h

include/linux/flex_array.h new file +3 -0

@@ -0,0 +1,45 @@
+#ifndef _FLEX_ARRAY_H
+#define _FLEX_ARRAY_H
+

include/linux/flex_array.h new file +31 -0

+ * and the developer is getting tempted to use
+ * vmalloc().
+ */
+
+struct flex_array {
+	union {
+		struct {
+			int nr_elements;
+			int element_size;
+			struct flex_array_part *parts[0];
+		};
+		/*
+		 * This little trick makes sure that
+		 * sizeof(flex_array) == PAGE_SIZE
+		 */
+		char padding[FLEX_ARRAY_BASE_SIZE];
+	};
+};
+
+#define FLEX_ARRAY_INIT(size, total) {{{\
+	.element_size = (size),		\
+	.nr_elements = 0,		\
+}}}
+
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags);
+void flex_array_free(struct flex_array *fa);
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags);
+int flex_array_append(struct flex_array *fa, void *src, gfp_t flags);
+void *flex_array_get(struct flex_array *fa, int element_nr);
+
+#endif /* _FLEX_ARRAY_H */

diff -puN /dev/null lib/flex_array.c

lib/flex_array.c new file +26 -0

@@ -0,0 +1,230 @@
+/*
+ * Flexible array managed in PAGE_SIZE parts
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2009
+ *
+ * Author: Dave Hansen <[email protected]>
+ */
+
+#include <linux/flex_array.h>
+#include <linux/slab.h>
+#include <linux/stddef.h>
+

lib/flex_array.c new file +78 -0

+{
+	int element_offset = offsetof(struct flex_array, parts);
+	int bytes_left = FLEX_ARRAY_BASE_SIZE - element_offset;
+	return bytes_left / sizeof(struct flex_array_part *);
+}
+
+/**
+ * flex_array_alloc - allocate a new flexible array
+ * @element_size:	the size of individual elements in the array
+ * @total:		total number of elements that this should hold
+ *
+ * Note: all locking must be provided by the caller.
+ *
+ * We do not actually use @total to size the allocation at this
+ * point.  It is just used to ensure that the user does not try
+ * to use this structure for something larger than it can handle
+ * later on.
+ *
+ * The maximum number of elements is defined as: the number of
+ * elements that can be stored in a page times the number of
+ * page pointers that we can fit in the base structure or (using
+ * integer math):
+ *
+ * 	(PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
+ *
+ * Here's a table showing example capacities.  Note that the maximum
+ * index that the get/put() functions is just nr_objects-1.
+ *
+ * Element size | Objects  | Objects |
+ * PAGE_SIZE=4k |  32-bit  |  64-bit |
+ * ----------------------------------|
+ *      1 byte  |  4186112 | 2093056 |
+ *      2 bytes |  2093056 | 1046528 |
+ *      3 bytes |  1395030 |  697515 |
+ *      4 bytes |  1046528 |  523264 |
+ *     32 bytes |   130816 |   65408 |
+ *     33 bytes |   126728 |   63364 |
+ *   2048 bytes |     2044 |   10228 |
+ *   2049 bytes |     1022 |     511 |
+ *       void * |  1046528 |  261632 |
+ *
+ * Since 64-bit pointers are twice the size, we lose half the
+ * capacity in the base structure.  Also note that no effort is made
+ * to efficiently pack objects across page boundaries.
+ */
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags)
+{
+	struct flex_array *ret;
+	int max_size = __nr_part_ptrs() * __elements_per_part(element_size);
+
+	/* max_size will end up 0 if element_size > PAGE_SIZE */
+	if (total > max_size)
+		return NULL;
+	ret = kzalloc(sizeof(struct flex_array), flags);
+	if (!ret)
+		return NULL;
+	ret->element_size = element_size;
+	return ret;
+}
+
+static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
+{
+	return element_nr / __elements_per_part(fa->element_size);
+}
+
+void flex_array_free(struct flex_array *fa)
+{
+	int part_nr;
+	int max_part;
+
+	/* keeps us from getting the index of -1 below */
+	if (!fa->nr_elements)
+		goto free_base;
+
+	/* we really want the *index* of the last element, thus the -1 */
+	max_part = fa_element_to_part_nr(fa, fa->nr_elements-1);
+	for (part_nr = 0; part_nr <= max_part; part_nr++)
+		kfree(fa->parts[part_nr]);

lib/flex_array.c new file +67 -0

+{
+	int part_offset = fa_index_inside_part(fa, element_nr);
+	return part_offset * fa->element_size;
+}
+
+static int __check_part_and_nr(struct flex_array *fa,
+	   		       int part_nr, int element_nr)
+{
+	if (part_nr >= __nr_part_ptrs() ||
+	    element_nr > fa->nr_elements) {
+		WARN(1, "bad flexible array element number: %d > %d\n",
+			element_nr, fa->nr_elements);
+		return -EINVAL;
+	}
+	return 0;
+}
+
+static struct flex_array_part *
+__fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
+{
+	struct flex_array_part *part = NULL;
+	if (__check_part_and_nr(fa, part_nr, fa->nr_elements))
+		return NULL;
+	part = fa->parts[part_nr];
+	if (!part) {
+		part = kmalloc(FLEX_ARRAY_PART_SIZE, flags);
+		if (!part)
+			return NULL;
+		fa->parts[part_nr] = part;
+	}
+	return part;
+}
+
+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src:	address of data to copy into the array
+ * @element_nr:	index of the position in which to insert
+ * 		the new element.
+ *
+ * Note that this *copies* the contents of @src into
+ * the array.  If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;
+	dst = &part->elements[offset_inside_part(fa, element_nr)];
+	memcpy(dst, src, fa->element_size);
+	return 0;
+}
+
+/**
+ * flex_array_append - append a new member into the array
+ * @src:	address of data to copy into the array
+ *
+ * This will use the internally-remembered last position in
+ * the array to choose an insertion point.
+ *
+ * Note that this *copies* the contents of @src into

lib/flex_array.c new file +18 -0

+	return ret;
+}
+
+
+/**
+ * flex_array_get - pull data back out of the array
+ * @element_nr:	index of the element to fetch from the array
+ *
+ * Returns a pointer to the data at index @element_nr.  Note
+ * that this is a copy of the data that was passed in.  If you
+ * are using this to store pointers, you'll get back &ptr.
+ *
+ * Locking must be provided by the caller.
+ */
+void *flex_array_get(struct flex_array *fa, int element_nr)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;

lib/flex_array.c new file +1 -0

+}

diff -puN lib/Makefile~fa lib/Makefile

lib/Makefile renamed from lib/Makefile~fa +1 -1

@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o flex_array.o
 

lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
diff -puN lib/radix-tree.c~fa lib/radix-tree.c
diff -puN ./include/linux/radix-tree.h~fa ./include/linux/radix-tree.h

Quoted 1 line · Dave Hansen

+static inline int __nr_part_ptrs(void)

How about __nr_ptrs_in_part()?

lib/flex_array.c line 124

Quoted 6 lines

lib/flex_array.c new file +6 -0

+static int fa_index_inside_part(struct flex_array *fa, int element_nr)
+{
+	return (element_nr % __elements_per_part(fa->element_size));
+}
+
+static int offset_inside_part(struct flex_array *fa, int element_nr)

How about index_in_part()?

Quoted 1 line · Dave Hansen

+static inline int __nr_part_ptrs(void)

How about __nr_ptrs_in_part()?

lib/flex_array.c line 124

Quoted 6 lines

lib/flex_array.c new file +6 -0

+static int fa_index_inside_part(struct flex_array *fa, int element_nr)
+{
+	return (element_nr % __elements_per_part(fa->element_size));
+}
+
+static int offset_inside_part(struct flex_array *fa, int element_nr)

How about index_in_part()?

Changes from v1:
- to vs too typo
- added __check_part_and_nr() and gave it a warning
- fixed off-by-one check on __nr_part_ptrs()
- addedFLEX_ARRAY_INIT() macro
- some kerneldoc comments about the capacity with various sized objects
- comments to note lack of locking semantice

--

Once a structure goes over PAGE_SIZE*2, we see occasional allocation failures. Some people have chosen to switch over to things like vmalloc() that will let them keep array-like access to such a large structures. But, vmalloc() has plenty of downsides.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

One thought is that we should perhaps make the base structure half the size on 32-bit arches. That will ensure that someone testing on 32-bit will not get bitten by the size shrinking by half when moving to 64-bit.

We could also potentially just pass the "element_size" into each of the API functions instead of storing it internally. That would get us one more base pointer on 32-bit.

The last improvement that I thought about was letting the individual array members span pages. In this implementation, if you have a 2049-byte object, it will only pack one of them into each "part" with no attempt to pack them. At this point, I don't think the added complexity would be worth it.

Signed-off-by Dave Hansen <[email protected]>

---

linux-2.6.git-dave/include/linux/flex_array.h |   45 +++++
linux-2.6.git-dave/lib/Makefile               |    2 
linux-2.6.git-dave/lib/flex_array.c           |  230 ++++++++++++++++++++++++++
3 files changed, 276 insertions(+), 1 deletion(-)

diff -puN /dev/null include/linux/flex_array.h

include/linux/flex_array.h new file +3 -0

@@ -0,0 +1,45 @@
+#ifndef _FLEX_ARRAY_H
+#define _FLEX_ARRAY_H
+

include/linux/flex_array.h new file +31 -0

+ * and the developer is getting tempted to use
+ * vmalloc().
+ */
+
+struct flex_array {
+	union {
+		struct {
+			int nr_elements;
+			int element_size;
+			struct flex_array_part *parts[0];
+		};
+		/*
+		 * This little trick makes sure that
+		 * sizeof(flex_array) == PAGE_SIZE
+		 */
+		char padding[FLEX_ARRAY_BASE_SIZE];
+	};
+};
+
+#define FLEX_ARRAY_INIT(size, total) {{{\
+	.element_size = (size),		\
+	.nr_elements = 0,		\
+}}}
+
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags);
+void flex_array_free(struct flex_array *fa);
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags);
+int flex_array_append(struct flex_array *fa, void *src, gfp_t flags);
+void *flex_array_get(struct flex_array *fa, int element_nr);
+
+#endif /* _FLEX_ARRAY_H */

diff -puN /dev/null lib/flex_array.c

lib/flex_array.c new file +26 -0

@@ -0,0 +1,230 @@
+/*
+ * Flexible array managed in PAGE_SIZE parts
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2009
+ *
+ * Author: Dave Hansen <[email protected]>
+ */
+
+#include <linux/flex_array.h>
+#include <linux/slab.h>
+#include <linux/stddef.h>
+

lib/flex_array.c new file +78 -0

+{
+	int element_offset = offsetof(struct flex_array, parts);
+	int bytes_left = FLEX_ARRAY_BASE_SIZE - element_offset;
+	return bytes_left / sizeof(struct flex_array_part *);
+}
+
+/**
+ * flex_array_alloc - allocate a new flexible array
+ * @element_size:	the size of individual elements in the array
+ * @total:		total number of elements that this should hold
+ *
+ * Note: all locking must be provided by the caller.
+ *
+ * We do not actually use @total to size the allocation at this
+ * point.  It is just used to ensure that the user does not try
+ * to use this structure for something larger than it can handle
+ * later on.
+ *
+ * The maximum number of elements is defined as: the number of
+ * elements that can be stored in a page times the number of
+ * page pointers that we can fit in the base structure or (using
+ * integer math):
+ *
+ * 	(PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
+ *
+ * Here's a table showing example capacities.  Note that the maximum
+ * index that the get/put() functions is just nr_objects-1.
+ *
+ * Element size | Objects  | Objects |
+ * PAGE_SIZE=4k |  32-bit  |  64-bit |
+ * ----------------------------------|
+ *      1 byte  |  4186112 | 2093056 |
+ *      2 bytes |  2093056 | 1046528 |
+ *      3 bytes |  1395030 |  697515 |
+ *      4 bytes |  1046528 |  523264 |
+ *     32 bytes |   130816 |   65408 |
+ *     33 bytes |   126728 |   63364 |
+ *   2048 bytes |     2044 |   10228 |
+ *   2049 bytes |     1022 |     511 |
+ *       void * |  1046528 |  261632 |
+ *
+ * Since 64-bit pointers are twice the size, we lose half the
+ * capacity in the base structure.  Also note that no effort is made
+ * to efficiently pack objects across page boundaries.
+ */
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags)
+{
+	struct flex_array *ret;
+	int max_size = __nr_part_ptrs() * __elements_per_part(element_size);
+
+	/* max_size will end up 0 if element_size > PAGE_SIZE */
+	if (total > max_size)
+		return NULL;
+	ret = kzalloc(sizeof(struct flex_array), flags);
+	if (!ret)
+		return NULL;
+	ret->element_size = element_size;
+	return ret;
+}
+
+static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
+{
+	return element_nr / __elements_per_part(fa->element_size);
+}
+
+void flex_array_free(struct flex_array *fa)
+{
+	int part_nr;
+	int max_part;
+
+	/* keeps us from getting the index of -1 below */
+	if (!fa->nr_elements)
+		goto free_base;
+
+	/* we really want the *index* of the last element, thus the -1 */
+	max_part = fa_element_to_part_nr(fa, fa->nr_elements-1);
+	for (part_nr = 0; part_nr <= max_part; part_nr++)
+		kfree(fa->parts[part_nr]);

lib/flex_array.c new file +67 -0

+{
+	int part_offset = fa_index_inside_part(fa, element_nr);
+	return part_offset * fa->element_size;
+}
+
+static int __check_part_and_nr(struct flex_array *fa,
+	   		       int part_nr, int element_nr)
+{
+	if (part_nr >= __nr_part_ptrs() ||
+	    element_nr > fa->nr_elements) {
+		WARN(1, "bad flexible array element number: %d > %d\n",
+			element_nr, fa->nr_elements);
+		return -EINVAL;
+	}
+	return 0;
+}
+
+static struct flex_array_part *
+__fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
+{
+	struct flex_array_part *part = NULL;
+	if (__check_part_and_nr(fa, part_nr, fa->nr_elements))
+		return NULL;
+	part = fa->parts[part_nr];
+	if (!part) {
+		part = kmalloc(FLEX_ARRAY_PART_SIZE, flags);
+		if (!part)
+			return NULL;
+		fa->parts[part_nr] = part;
+	}
+	return part;
+}
+
+/**
+ * flex_array_put - copy data into the array at @element_nr
+ * @src:	address of data to copy into the array
+ * @element_nr:	index of the position in which to insert
+ * 		the new element.
+ *
+ * Note that this *copies* the contents of @src into
+ * the array.  If you are trying to store an array of
+ * pointers, make sure to pass in &ptr instead of ptr.
+ *
+ * Locking must be provided by the caller.
+ */
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;
+	void *dst;
+
+	part = __fa_get_part(fa, part_nr, flags);
+	if (!part)
+		return -ENOMEM;
+	dst = &part->elements[offset_inside_part(fa, element_nr)];
+	memcpy(dst, src, fa->element_size);
+	return 0;
+}
+
+/**
+ * flex_array_append - append a new member into the array
+ * @src:	address of data to copy into the array
+ *
+ * This will use the internally-remembered last position in
+ * the array to choose an insertion point.
+ *
+ * Note that this *copies* the contents of @src into

lib/flex_array.c new file +18 -0

+	return ret;
+}
+
+
+/**
+ * flex_array_get - pull data back out of the array
+ * @element_nr:	index of the element to fetch from the array
+ *
+ * Returns a pointer to the data at index @element_nr.  Note
+ * that this is a copy of the data that was passed in.  If you
+ * are using this to store pointers, you'll get back &ptr.
+ *
+ * Locking must be provided by the caller.
+ */
+void *flex_array_get(struct flex_array *fa, int element_nr)
+{
+	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	struct flex_array_part *part;

lib/flex_array.c new file +1 -0

+}

diff -puN lib/Makefile~fa lib/Makefile

lib/Makefile renamed from lib/Makefile~fa +1 -1

@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o flex_array.o
 

lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
diff -puN lib/radix-tree.c~fa lib/radix-tree.c
diff -puN ./include/linux/radix-tree.h~fa ./include/linux/radix-tree.h

Changes from v1:
- to vs too typo
- added __check_part_and_nr() and gave it a warning
- fixed off-by-one check on __nr_part_ptrs()
- addedFLEX_ARRAY_INIT() macro
- some kerneldoc comments about the capacity with various sized objects
- comments to note lack of locking semantice

--

Once a structure goes over PAGE_SIZE*2, we see occasional allocation failures. Some people have chosen to switch over to things like vmalloc() that will let them keep array-like access to such a large structures. But, vmalloc() has plenty of downsides.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

One thought is that we should perhaps make the base structure half the size on 32-bit arches. That will ensure that someone testing on 32-bit will not get bitten by the size shrinking by half when moving to 64-bit.

We could also potentially just pass the "element_size" into each of the API functions instead of storing it internally. That would get us one more base pointer on 32-bit.

The last improvement that I thought about was letting the individual array members span pages. In this implementation, if you have a 2049-byte object, it will only pack one of them into each "part" with no attempt to pack them. At this point, I don't think the added complexity would be worth it.

Signed-off-by Dave Hansen <[email protected]>

---

 linux-2.6.git-dave/include/linux/flex_array.h |   45 +++++
 linux-2.6.git-dave/lib/Makefile               |    2 
 linux-2.6.git-dave/lib/flex_array.c           |  230 ++++++++++++++++++++++++++
 3 files changed, 276 insertions(+), 1 deletion(-)

diff -puN /dev/null include/linux/flex_array.h

include/linux/flex_array.h new file +45 -0

@@ -0,0 +1,45 @@
+#ifndef _FLEX_ARRAY_H
+#define _FLEX_ARRAY_H
+
+#include <linux/types.h>
+#include <asm/page.h>
+
+#define FLEX_ARRAY_PART_SIZE PAGE_SIZE
+#define FLEX_ARRAY_BASE_SIZE PAGE_SIZE
+
+struct flex_array_part;
+
+/*
+ * This is meant too replace cases where an array-like
+ * structure has gotten to big to fit into kmalloc()
+ * and the developer is getting tempted to use
+ * vmalloc().
+ */
+
+struct flex_array {
+	union {
+		struct {
+			int nr_elements;
+			int element_size;
+			struct flex_array_part *parts[0];
+		};
+		/*
+		 * This little trick makes sure that
+		 * sizeof(flex_array) == PAGE_SIZE
+		 */
+		char padding[FLEX_ARRAY_BASE_SIZE];
+	};
+};
+
+#define FLEX_ARRAY_INIT(size, total) {{{\
+	.element_size = (size),		\
+	.nr_elements = 0,		\
+}}}
+
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags);
+void flex_array_free(struct flex_array *fa);
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags);
+int flex_array_append(struct flex_array *fa, void *src, gfp_t flags);
+void *flex_array_get(struct flex_array *fa, int element_nr);
+
+#endif /* _FLEX_ARRAY_H */

diff -puN /dev/null lib/flex_array.c

lib/flex_array.c new file +130 -0

@@ -0,0 +1,230 @@
+/*
+ * Flexible array managed in PAGE_SIZE parts
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2009
+ *
+ * Author: Dave Hansen <[email protected]>
+ */
+
+#include <linux/flex_array.h>
+#include <linux/slab.h>
+#include <linux/stddef.h>
+
+struct flex_array_part {
+	char elements[FLEX_ARRAY_PART_SIZE];
+};
+
+static inline int __elements_per_part(int element_size)
+{
+	return FLEX_ARRAY_PART_SIZE / element_size;
+}
+
+static inline int __nr_part_ptrs(void)
+{
+	int element_offset = offsetof(struct flex_array, parts);
+	int bytes_left = FLEX_ARRAY_BASE_SIZE - element_offset;
+	return bytes_left / sizeof(struct flex_array_part *);
+}
+
+/**
+ * flex_array_alloc - allocate a new flexible array
+ * @element_size:	the size of individual elements in the array
+ * @total:		total number of elements that this should hold
+ *
+ * Note: all locking must be provided by the caller.
+ *
+ * We do not actually use @total to size the allocation at this
+ * point.  It is just used to ensure that the user does not try
+ * to use this structure for something larger than it can handle
+ * later on.
+ *
+ * The maximum number of elements is defined as: the number of
+ * elements that can be stored in a page times the number of
+ * page pointers that we can fit in the base structure or (using
+ * integer math):
+ *
+ * 	(PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
+ *
+ * Here's a table showing example capacities.  Note that the maximum
+ * index that the get/put() functions is just nr_objects-1.
+ *
+ * Element size | Objects  | Objects |
+ * PAGE_SIZE=4k |  32-bit  |  64-bit |
+ * ----------------------------------|
+ *      1 byte  |  4186112 | 2093056 |
+ *      2 bytes |  2093056 | 1046528 |
+ *      3 bytes |  1395030 |  697515 |
+ *      4 bytes |  1046528 |  523264 |
+ *     32 bytes |   130816 |   65408 |
+ *     33 bytes |   126728 |   63364 |
+ *   2048 bytes |     2044 |   10228 |
+ *   2049 bytes |     1022 |     511 |
+ *       void * |  1046528 |  261632 |
+ *
+ * Since 64-bit pointers are twice the size, we lose half the
+ * capacity in the base structure.  Also note that no effort is made
+ * to efficiently pack objects across page boundaries.
+ */
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags)
+{
+	struct flex_array *ret;
+	int max_size = __nr_part_ptrs() * __elements_per_part(element_size);
+
+	/* max_size will end up 0 if element_size > PAGE_SIZE */
+	if (total > max_size)
+		return NULL;
+	ret = kzalloc(sizeof(struct flex_array), flags);
+	if (!ret)
+		return NULL;
+	ret->element_size = element_size;
+	return ret;
+}
+
+static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
+{
+	return element_nr / __elements_per_part(fa->element_size);
+}
+
+void flex_array_free(struct flex_array *fa)
+{
+	int part_nr;
+	int max_part;
+
+	/* keeps us from getting the index of -1 below */
+	if (!fa->nr_elements)
+		goto free_base;
+
+	/* we really want the *index* of the last element, thus the -1 */
+	max_part = fa_element_to_part_nr(fa, fa->nr_elements-1);
+	for (part_nr = 0; part_nr <= max_part; part_nr++)
+		kfree(fa->parts[part_nr]);
+free_base:
+	kfree(fa);
+}
+
+static int fa_index_inside_part(struct flex_array *fa, int element_nr)
+{
+	return (element_nr % __elements_per_part(fa->element_size));
+}
+
+static int offset_inside_part(struct flex_array *fa, int element_nr)
+{
+	int part_offset = fa_index_inside_part(fa, element_nr);
+	return part_offset * fa->element_size;
+}
+
+static int __check_part_and_nr(struct flex_array *fa,

Changes from v1:
- to vs too typo
- added __check_part_and_nr() and gave it a warning
- fixed off-by-one check on __nr_part_ptrs()
- addedFLEX_ARRAY_INIT() macro
- some kerneldoc comments about the capacity with various sized objects
- comments to note lack of locking semantice

--

Once a structure goes over PAGE_SIZE*2, we see occasional allocation failures. Some people have chosen to switch over to things like vmalloc() that will let them keep array-like access to such a large structures. But, vmalloc() has plenty of downsides.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

One thought is that we should perhaps make the base structure half the size on 32-bit arches. That will ensure that someone testing on 32-bit will not get bitten by the size shrinking by half when moving to 64-bit.

We could also potentially just pass the "element_size" into each of the API functions instead of storing it internally. That would get us one more base pointer on 32-bit.

The last improvement that I thought about was letting the individual array members span pages. In this implementation, if you have a 2049-byte object, it will only pack one of them into each "part" with no attempt to pack them. At this point, I don't think the added complexity would be worth it.

Signed-off-by Dave Hansen <[email protected]>

---

 linux-2.6.git-dave/include/linux/flex_array.h |   45 +++++
 linux-2.6.git-dave/lib/Makefile               |    2 
 linux-2.6.git-dave/lib/flex_array.c           |  230 ++++++++++++++++++++++++++
 3 files changed, 276 insertions(+), 1 deletion(-)

diff -puN /dev/null include/linux/flex_array.h

include/linux/flex_array.h new file +45 -0

@@ -0,0 +1,45 @@
+#ifndef _FLEX_ARRAY_H
+#define _FLEX_ARRAY_H
+
+#include <linux/types.h>
+#include <asm/page.h>
+
+#define FLEX_ARRAY_PART_SIZE PAGE_SIZE
+#define FLEX_ARRAY_BASE_SIZE PAGE_SIZE
+
+struct flex_array_part;
+
+/*
+ * This is meant too replace cases where an array-like
+ * structure has gotten to big to fit into kmalloc()
+ * and the developer is getting tempted to use
+ * vmalloc().
+ */
+
+struct flex_array {
+	union {
+		struct {
+			int nr_elements;
+			int element_size;
+			struct flex_array_part *parts[0];
+		};
+		/*
+		 * This little trick makes sure that
+		 * sizeof(flex_array) == PAGE_SIZE
+		 */
+		char padding[FLEX_ARRAY_BASE_SIZE];
+	};
+};
+
+#define FLEX_ARRAY_INIT(size, total) {{{\
+	.element_size = (size),		\
+	.nr_elements = 0,		\
+}}}
+
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags);
+void flex_array_free(struct flex_array *fa);
+int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags);
+int flex_array_append(struct flex_array *fa, void *src, gfp_t flags);
+void *flex_array_get(struct flex_array *fa, int element_nr);
+
+#endif /* _FLEX_ARRAY_H */

diff -puN /dev/null lib/flex_array.c

lib/flex_array.c new file +130 -0

@@ -0,0 +1,230 @@
+/*
+ * Flexible array managed in PAGE_SIZE parts
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2009
+ *
+ * Author: Dave Hansen <[email protected]>
+ */
+
+#include <linux/flex_array.h>
+#include <linux/slab.h>
+#include <linux/stddef.h>
+
+struct flex_array_part {
+	char elements[FLEX_ARRAY_PART_SIZE];
+};
+
+static inline int __elements_per_part(int element_size)
+{
+	return FLEX_ARRAY_PART_SIZE / element_size;
+}
+
+static inline int __nr_part_ptrs(void)
+{
+	int element_offset = offsetof(struct flex_array, parts);
+	int bytes_left = FLEX_ARRAY_BASE_SIZE - element_offset;
+	return bytes_left / sizeof(struct flex_array_part *);
+}
+
+/**
+ * flex_array_alloc - allocate a new flexible array
+ * @element_size:	the size of individual elements in the array
+ * @total:		total number of elements that this should hold
+ *
+ * Note: all locking must be provided by the caller.
+ *
+ * We do not actually use @total to size the allocation at this
+ * point.  It is just used to ensure that the user does not try
+ * to use this structure for something larger than it can handle
+ * later on.
+ *
+ * The maximum number of elements is defined as: the number of
+ * elements that can be stored in a page times the number of
+ * page pointers that we can fit in the base structure or (using
+ * integer math):
+ *
+ * 	(PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
+ *
+ * Here's a table showing example capacities.  Note that the maximum
+ * index that the get/put() functions is just nr_objects-1.
+ *
+ * Element size | Objects  | Objects |
+ * PAGE_SIZE=4k |  32-bit  |  64-bit |
+ * ----------------------------------|
+ *      1 byte  |  4186112 | 2093056 |
+ *      2 bytes |  2093056 | 1046528 |
+ *      3 bytes |  1395030 |  697515 |
+ *      4 bytes |  1046528 |  523264 |
+ *     32 bytes |   130816 |   65408 |
+ *     33 bytes |   126728 |   63364 |
+ *   2048 bytes |     2044 |   10228 |
+ *   2049 bytes |     1022 |     511 |
+ *       void * |  1046528 |  261632 |
+ *
+ * Since 64-bit pointers are twice the size, we lose half the
+ * capacity in the base structure.  Also note that no effort is made
+ * to efficiently pack objects across page boundaries.
+ */
+struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags)
+{
+	struct flex_array *ret;
+	int max_size = __nr_part_ptrs() * __elements_per_part(element_size);
+
+	/* max_size will end up 0 if element_size > PAGE_SIZE */
+	if (total > max_size)
+		return NULL;
+	ret = kzalloc(sizeof(struct flex_array), flags);
+	if (!ret)
+		return NULL;
+	ret->element_size = element_size;
+	return ret;
+}
+
+static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
+{
+	return element_nr / __elements_per_part(fa->element_size);
+}
+
+void flex_array_free(struct flex_array *fa)
+{
+	int part_nr;
+	int max_part;
+
+	/* keeps us from getting the index of -1 below */
+	if (!fa->nr_elements)
+		goto free_base;
+
+	/* we really want the *index* of the last element, thus the -1 */
+	max_part = fa_element_to_part_nr(fa, fa->nr_elements-1);
+	for (part_nr = 0; part_nr <= max_part; part_nr++)
+		kfree(fa->parts[part_nr]);
+free_base:
+	kfree(fa);
+}
+
+static int fa_index_inside_part(struct flex_array *fa, int element_nr)
+{
+	return (element_nr % __elements_per_part(fa->element_size));
+}
+
+static int offset_inside_part(struct flex_array *fa, int element_nr)
+{
+	int part_offset = fa_index_inside_part(fa, element_nr);
+	return part_offset * fa->element_size;
+}
+
+static int __check_part_and_nr(struct flex_array *fa,

Quoted 7 lines

lib/flex_array.c new file +7 -0

+static int __check_part_and_nr(struct flex_array *fa,
+                            int part_nr, int element_nr)
+{
+     if (part_nr >= __nr_part_ptrs() ||
+         element_nr > fa->nr_elements) {
+             WARN(1, "bad flexible array element number: %d > %d\n",
+                     element_nr, fa->nr_elements);

lib/flex_array.c line 140

Quoted 4 lines

lib/flex_array.c new file +4 -0

+             return -EINVAL;
+     }
+     return 0;
+}

Should the above be inline? Does it make sense to optimize the "common" case and penalize inappropriate access by putting an unlikely() in there? Or is it too early for this stuff?

I wonder how the *, /, and % ops will affect things that otherwise would have been reduced to shifts and masks -- especially on the "smaller" embedded archs.

Quoted 7 lines

lib/flex_array.c new file +7 -0

+static int __check_part_and_nr(struct flex_array *fa,
+                            int part_nr, int element_nr)
+{
+     if (part_nr >= __nr_part_ptrs() ||
+         element_nr > fa->nr_elements) {
+             WARN(1, "bad flexible array element number: %d > %d\n",
+                     element_nr, fa->nr_elements);

lib/flex_array.c line 140

Quoted 4 lines

lib/flex_array.c new file +4 -0

+             return -EINVAL;
+     }
+     return 0;
+}

Should the above be inline? Does it make sense to optimize the "common" case and penalize inappropriate access by putting an unlikely() in there? Or is it too early for this stuff?

I wonder how the *, /, and % ops will affect things that otherwise would have been reduced to shifts and masks -- especially on the "smaller" embedded archs.

Changes from v1:
- to vs too typo
- added __check_part_and_nr() and gave it a warning
- fixed off-by-one check on __nr_part_ptrs()
- addedFLEX_ARRAY_INIT() macro
- some kerneldoc comments about the capacity with various sized objects
- comments to note lack of locking semantice

--

Once a structure goes over PAGE_SIZE*2, we see occasional allocation failures. Some people have chosen to switch over to things like vmalloc() that will let them keep array-like access to such a large structures. But, vmalloc() has plenty of downsides.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

The interface is dirt simple. 4 functions:
alloc_flex_array()
free_flex_array()
flex_array_put()
flex_array_get()

put() appends an item into the array while get() takes indexes and does array-style access.

One thought is that we should perhaps make the base structure half the size on 32-bit arches. That will ensure that someone testing on 32-bit will not get bitten by the size shrinking by half when moving to 64-bit.

We could also potentially just pass the "element_size" into each of the API functions instead of storing it internally. That would get us one more base pointer on 32-bit.

The last improvement that I thought about was letting the individual array members span pages. In this implementation, if you have a 2049-byte object, it will only pack one of them into each "part" with no attempt to pack them. At this point, I don't think the added complexity would be worth it.

Signed-off-by Dave Hansen <[email protected]>

---

 linux-2.6.git-dave/include/linux/flex_array.h |   45 +++++
 linux-2.6.git-dave/lib/Makefile               |    2 
 linux-2.6.git-dave/lib/flex_array.c           |  230 ++++++++++++++++++++++++++
 3 files changed, 276 insertions(+), 1 deletion(-)

diff -puN /dev/null include/linux/flex_array.h

include/linux/flex_array.h new file +28 -0

@@ -0,0 +1,45 @@
+#ifndef _FLEX_ARRAY_H
+#define _FLEX_ARRAY_H
+
+#include <linux/types.h>
+#include <asm/page.h>
+
+#define FLEX_ARRAY_PART_SIZE PAGE_SIZE
+#define FLEX_ARRAY_BASE_SIZE PAGE_SIZE
+
+struct flex_array_part;
+
+/*
+ * This is meant too replace cases where an array-like
+ * structure has gotten to big to fit into kmalloc()
+ * and the developer is getting tempted to use
+ * vmalloc().
+ */
+
+struct flex_array {
+	union {
+		struct {
+			int nr_elements;
+			int element_size;
+			struct flex_array_part *parts[0];
+		};
+		/*
+		 * This little trick makes sure that
+		 * sizeof(flex_array) == PAGE_SIZE

include/linux/flex_array.h line 38

Quoted 5 lines

include/linux/flex_array.h new file +5 -0

+#define FLEX_ARRAY_INIT(size, total) {{{\
+     .element_size = (size),         \
+     .nr_elements = 0,               \
+}}}
+

It's not clear how this guy is used. It will initialize a flex_array, but how is somebody expected to free the parts that get associated with it?

Is there a fancy way to make declaring a flex_array on stack a compile-time error?

include/linux/flex_array.h line 38

Quoted 5 lines

include/linux/flex_array.h new file +5 -0

+#define FLEX_ARRAY_INIT(size, total) {{{\
+     .element_size = (size),         \
+     .nr_elements = 0,               \
+}}}
+

It's not clear how this guy is used. It will initialize a flex_array, but how is somebody expected to free the parts that get associated with it?

Is there a fancy way to make declaring a flex_array on stack a compile-time error?

Does the array automatically grow if you give it more elements than you tell it it can have?

How about a resize() function that can be
used to either grow or shrink the array?

Quoted 2 lines · Benjamin Blum

Does the array automatically grow if you give it more elements than you tell it it can have?

The only limits it has or enforces are the structural and architectural ones dictated by the layout.

Quoted 2 lines

How about a resize() function that can be
used to either grow or shrink the array?

I think growing is out of the question.  It has a fixed maximum size already.  As for shrinking, there's probably a use case for when something is large, then shrinks back down.  But, I think I'd want to see a user for it, otherwise I'm just guessing at it too much.

-- Dave

Quoted 2 lines · Benjamin Blum

Does the array automatically grow if you give it more elements than you tell it it can have?

The only limits it has or enforces are the structural and architectural ones dictated by the layout.

Quoted 2 lines

How about a resize() function that can be
used to either grow or shrink the array?

I think growing is out of the question.  It has a fixed maximum size already.  As for shrinking, there's probably a use case for when something is large, then shrinks back down.  But, I think I'd want to see a user for it, otherwise I'm just guessing at it too much.

-- Dave

Quoted 8 lines

Quoted 3 lines

How about a resize() function that can be
used to either grow or shrink the array?

I think growing is out of the question. It has a fixed maximum size already. As for shrinking, there's probably a use case for when something is large, then shrinks back down. But, I think I'd want to see a user for it, otherwise I'm just guessing at it too much.

Check out the reallocate logic in pidlist_uniq from my patch (the series you linked).

Quoted 8 lines

Quoted 3 lines

How about a resize() function that can be
used to either grow or shrink the array?

I think growing is out of the question. It has a fixed maximum size already. As for shrinking, there's probably a use case for when something is large, then shrinks back down. But, I think I'd want to see a user for it, otherwise I'm just guessing at it too much.

Check out the reallocate logic in pidlist_uniq from my patch (the series you linked).

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

Here's an alternative. I think it's what Andrew was suggesting here:

	http://lkml.org/lkml/2009/7/2/518 

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

Quoted 8 lines

I call it a flexible array. It does all of its work in PAGE_SIZE bits, so never does an order>0 allocation. The base level has PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level. So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total storage when the objects pack nicely into a page. It is half that on 64-bit because the pointers are twice the size.

I'm wondering if there is any use case which would require scaling below the PAGE_SIZE level... in which case it would be nice for it to gracefully decay to a single kmalloc allocation + some metadata.