summaryrefslogtreecommitdiffstats
path: root/lib/flex_array.c (follow)
Commit message (Collapse)AuthorAgeFilesLines
* flex_array: convert element_nr formals to unsignedDavid Rientjes2009-08-271-11/+13
| | | | | | | | | | | | | | | | | | | | | It's problematic to allow signed element_nr's or total's to be passed as part of the flex array API. flex_array_alloc() allows total_nr_elements to be set to a negative quantity, which is obviously erroneous. flex_array_get() and flex_array_put() allows negative array indices in dereferencing an array part, which could address memory mapped before struct flex_array. The fix is to convert all existing element_nr formals to be qualified as unsigned. Existing checks to compare it to total_nr_elements or the max array size based on element_size need not be changed. Signed-off-by: David Rientjes <rientjes@google.com> Cc: Dave Hansen <dave@linux.vnet.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* flex_array: fix flex_array_free_parts commentDavid Rientjes2009-08-271-3/+0
| | | | | | | | | | flex_array_free_parts() does not take `src' or `element_nr' formals, so remove their respective comments. Signed-off-by: David Rientjes <rientjes@google.com> Acked-by: Dave Hansen <dave@linux.vnet.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* flex_array: fix get function for elements in base starting at non-zeroDavid Rientjes2009-08-271-6/+8
| | | | | | | | | | | | | | | | | | | | | | If all array elements fit into the base structure and data is copied using flex_array_put() starting at a non-zero index, flex_array_get() will fail to return the data. This fixes the bug by only checking for NULL parts when all elements do not fit in the base structure when flex_array_get() is used. Otherwise, fa_element_to_part_nr() will always be 0 since there are no parts structures needed and such element may never have been put. Thus, it will remain NULL due to the kzalloc() of the base. Additionally, flex_array_put() now only checks for a NULL part when all elements do not fit in the base structure. This is otherwise unnecessary since the base structure is guaranteed to exist (or we would have already hit a NULL pointer). Signed-off-by: David Rientjes <rientjes@google.com> Acked-by: Dave Hansen <dave@linux.vnet.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* flex_array: remove unneeded index calculationJonathan Corbet2009-08-051-2/+0
| | | | | | | | | flex_array_get() calculates an index value, then drops it on the floor; simply remove it. Signed-off-by: Jonathan Corbet <corbet@lwn.net> Acked-by: Dave Hansen <dave@linux.vnet.ibm.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: flexible array implementationDave Hansen2009-07-301-0/+269
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: Dave Hansen <dave@linux.vnet.ibm.com> Reviewed-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>