lkml.org 
[lkml]   [2009]   [Jul]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH] flexible array implementation v3


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.




\
 
 \ /
  Last update: 2009-07-23 17:49    [W:0.151 / U:0.080 seconds]
©2003-2014 Jasper Spaans. Advertise on this site