diff options
| -rw-r--r-- | Documentation/core-api/flexible-arrays.rst | 130 | ||||
| -rw-r--r-- | Documentation/core-api/index.rst | 1 | ||||
| -rw-r--r-- | include/linux/flex_array.h | 67 |
3 files changed, 198 insertions, 0 deletions
diff --git a/Documentation/core-api/flexible-arrays.rst b/Documentation/core-api/flexible-arrays.rst new file mode 100644 index 000000000000..b6b85a1b518e --- /dev/null +++ b/Documentation/core-api/flexible-arrays.rst @@ -0,0 +1,130 @@ + +=================================== +Using flexible arrays in the kernel +=================================== + +Large contiguous memory allocations can be unreliable in the Linux kernel. +Kernel programmers will sometimes respond to this problem by allocating +pages with :c:func:`vmalloc()`. This solution not ideal, though. On 32-bit +systems, memory from vmalloc() must be mapped into a relatively small address +space; it's easy to run out. On SMP systems, the page table changes required +by vmalloc() allocations can require expensive cross-processor interrupts on +all CPUs. And, on all systems, use of space in the vmalloc() range increases +pressure on the translation lookaside buffer (TLB), reducing the performance +of the system. + +In many cases, the need for memory from vmalloc() can be eliminated by piecing +together an array from smaller parts; the flexible array library exists to make +this task easier. + +A flexible array holds an arbitrary (within limits) number of fixed-sized +objects, accessed via an integer index. Sparse arrays are handled +reasonably well. Only single-page allocations are made, so memory +allocation failures should be relatively rare. The down sides are that the +arrays cannot be indexed directly, individual object size cannot exceed the +system page size, and putting data into a flexible array requires a copy +operation. It's also worth noting that flexible arrays do no internal +locking at all; if concurrent access to an array is possible, then the +caller must arrange for appropriate mutual exclusion. + +The creation of a flexible array is done with :c:func:`flex_array_alloc()`:: + + #include <linux/flex_array.h> + + struct flex_array *flex_array_alloc(int element_size, + unsigned int total, + gfp_t flags); + +The individual object size is provided by ``element_size``, while total is the +maximum number of objects which can be stored in the array. The flags +argument is passed directly to the internal memory allocation calls. With +the current code, using flags to ask for high memory is likely to lead to +notably unpleasant side effects. + +It is also possible to define flexible arrays at compile time with:: + + DEFINE_FLEX_ARRAY(name, element_size, total); + +This macro will result in a definition of an array with the given name; the +element size and total will be checked for validity at compile time. + +Storing data into a flexible array is accomplished with a call to +:c:func:`flex_array_put()`:: + + int flex_array_put(struct flex_array *array, unsigned int element_nr, + void *src, gfp_t flags); + +This call will copy the data from src into the array, in the position +indicated by ``element_nr`` (which must be less than the maximum specified when +the array was created). If any memory allocations must be performed, flags +will be used. The return value is zero on success, a negative error code +otherwise. + +There might possibly be a need to store data into a flexible array while +running in some sort of atomic context; in this situation, sleeping in the +memory allocator would be a bad thing. That can be avoided by using +``GFP_ATOMIC`` for the flags value, but, often, there is a better way. The +trick is to ensure that any needed memory allocations are done before +entering atomic context, using :c:func:`flex_array_prealloc()`:: + + int flex_array_prealloc(struct flex_array *array, unsigned int start, + unsigned int nr_elements, gfp_t flags); + +This function will ensure that memory for the elements indexed in the range +defined by ``start`` and ``nr_elements`` has been allocated. Thereafter, a +``flex_array_put()`` call on an element in that range is guaranteed not to +block. + +Getting data back out of the array is done with :c:func:`flex_array_get()`:: + + void *flex_array_get(struct flex_array *fa, unsigned int element_nr); + +The return value is a pointer to the data element, or NULL if that +particular element has never been allocated. + +Note that it is possible to get back a valid pointer for an element which +has never been stored in the array. Memory for array elements is allocated +one page at a time; a single allocation could provide memory for several +adjacent elements. Flexible array elements are normally initialized to the +value ``FLEX_ARRAY_FREE`` (defined as 0x6c in <linux/poison.h>), so errors +involving that number probably result from use of unstored array entries. +Note that, if array elements are allocated with ``__GFP_ZERO``, they will be +initialized to zero and this poisoning will not happen. + +Individual elements in the array can be cleared with +:c:func:`flex_array_clear()`:: + + int flex_array_clear(struct flex_array *array, unsigned int element_nr); + +This function will set the given element to ``FLEX_ARRAY_FREE`` and return +zero. If storage for the indicated element is not allocated for the array, +``flex_array_clear()`` will return ``-EINVAL`` instead. Note that clearing an +element does not release the storage associated with it; to reduce the +allocated size of an array, call :c:func:`flex_array_shrink()`:: + + int flex_array_shrink(struct flex_array *array); + +The return value will be the number of pages of memory actually freed. +This function works by scanning the array for pages containing nothing but +``FLEX_ARRAY_FREE`` bytes, so (1) it can be expensive, and (2) it will not work +if the array's pages are allocated with ``__GFP_ZERO``. + +It is possible to remove all elements of an array with a call to +:c:func:`flex_array_free_parts()`:: + + void flex_array_free_parts(struct flex_array *array); + +This call frees all elements, but leaves the array itself in place. +Freeing the entire array is done with :c:func:`flex_array_free()`:: + + void flex_array_free(struct flex_array *array); + +As of this writing, there are no users of flexible arrays in the mainline +kernel. The functions described here are also not exported to modules; +that will probably be fixed when somebody comes up with a need for it. + + +Flexible array functions +------------------------ + +.. kernel-doc:: include/linux/flex_array.h diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index 0d93d8089136..2b908ac41021 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -16,6 +16,7 @@ Core utilities cpu_hotplug local_ops workqueue + flexible-arrays Interfaces for kernel debugging =============================== diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h index b6efb0c64408..11366b3ff0b4 100644 --- a/include/linux/flex_array.h +++ b/include/linux/flex_array.h @@ -61,16 +61,83 @@ struct flex_array { FLEX_ARRAY_ELEMENTS_PER_PART(__element_size)); \ } +/** + * flex_array_alloc() - Creates a flexible array. + * @element_size: individual object size. + * @total: maximum number of objects which can be stored. + * @flags: GFP flags + * + * Return: Returns an object of structure flex_array. + */ struct flex_array *flex_array_alloc(int element_size, unsigned int total, gfp_t flags); + +/** + * flex_array_prealloc() - Ensures that memory for the elements indexed in the + * range defined by start and nr_elements has been allocated. + * @fa: array to allocate memory to. + * @start: start address + * @nr_elements: number of elements to be allocated. + * @flags: GFP flags + * + */ int flex_array_prealloc(struct flex_array *fa, unsigned int start, unsigned int nr_elements, gfp_t flags); + +/** + * flex_array_free() - Removes all elements of a flexible array. + * @fa: array to be freed. + */ void flex_array_free(struct flex_array *fa); + +/** + * flex_array_free_parts() - Removes all elements of a flexible array, but + * leaves the array itself in place. + * @fa: array to be emptied. + */ void flex_array_free_parts(struct flex_array *fa); + +/** + * flex_array_put() - Stores data into a flexible array. + * @fa: array where element is to be stored. + * @element_nr: position to copy, must be less than the maximum specified when + * the array was created. + * @src: data source to be copied into the array. + * @flags: GFP flags + * + * Return: Returns zero on success, a negative error code otherwise. + */ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, gfp_t flags); + +/** + * flex_array_clear() - Clears an individual element in the array, sets the + * given element to FLEX_ARRAY_FREE. + * @element_nr: element position to clear. + * @fa: array to which element to be cleared belongs. + * + * Return: Returns zero on success, -EINVAL otherwise. + */ int flex_array_clear(struct flex_array *fa, unsigned int element_nr); + +/** + * flex_array_get() - Retrieves data into a flexible array. + * + * @element_nr: Element position to retrieve data from. + * @fa: array from which data is to be retrieved. + * + * Return: Returns a pointer to the data element, or NULL if that + * particular element has never been allocated. + */ void *flex_array_get(struct flex_array *fa, unsigned int element_nr); + +/** + * flex_array_shrink() - Reduces the allocated size of an array. + * @fa: array to shrink. + * + * Return: Returns number of pages of memory actually freed. + * + */ int flex_array_shrink(struct flex_array *fa); #define flex_array_put_ptr(fa, nr, src, gfp) \ |