[RFC][PATCH] flexible array implementation v3

[Oren Laadan]

Dave Hansen wrote:
> 
> Changes from v2:
> - renamed some of the index functions
> - added preallocation function
> - added flex_array_free_parts() for use with
>   statically allocated bases
> - killed append() function
> 
> 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()
> - added FLEX_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.  There's a table detailing this in the code.
> 
> There are kerneldocs for the functions, but here's an
> overview:
> 
> flex_array_alloc() - dynamically allocate a base structure
> flex_array_free() - free the array and all of the
> 		    second-level pages
> flex_array_free_parts() - free the second-level pages, but
> 			  not the base (for static bases)
> flex_array_put() - copy into the array at the given index
> flex_array_get() - copy out of the array at the given index
> flex_array_prealloc() - preallocate the second-level pages
> 			between the given indexes to
> 			guarantee no allocs will occur at
> 			put() time.

Probably premature, but -- I wonder if it's worth adding interfaces to:

* copy a range of elements at once (perhaps to/from regular array ?
or userspace ? -- depending on potential users)

* (macro ?) iterate through elements (better have it ready for users
of flex_array before, than convert their code later on)

Oren.