• Dave Hansen's avatar
    lib: flexible array implementation · 534acc05
    Dave Hansen authored
    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.
    
    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.
    
    I've been testing this by running it in userspace.  The header and patch
    that I've been using are here, as well as the little script I'm using to
    generate the size table which goes in the kerneldocs.
    
    	http://sr71.net/~dave/linux/flexarray/
    
    [akpm@linux-foundation.org: coding-style fixes]
    Signed-off-by: default avatarDave Hansen <dave@linux.vnet.ibm.com>
    Reviewed-by: default avatarKAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    534acc05
Makefile 3.26 KB