[lkml]   [2009]   [Jul]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    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:
    > 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)


     \ /
      Last update: 2009-07-23 17:49    [W:0.023 / U:0.908 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site