sayli karnik | b2e3353 | 2017-03-30 02:01:16 +0530 | [diff] [blame] | 1 | |
| 2 | =================================== |
| 3 | Using flexible arrays in the kernel |
| 4 | =================================== |
| 5 | |
| 6 | Large contiguous memory allocations can be unreliable in the Linux kernel. |
| 7 | Kernel programmers will sometimes respond to this problem by allocating |
| 8 | pages with :c:func:`vmalloc()`. This solution not ideal, though. On 32-bit |
| 9 | systems, memory from vmalloc() must be mapped into a relatively small address |
| 10 | space; it's easy to run out. On SMP systems, the page table changes required |
| 11 | by vmalloc() allocations can require expensive cross-processor interrupts on |
| 12 | all CPUs. And, on all systems, use of space in the vmalloc() range increases |
| 13 | pressure on the translation lookaside buffer (TLB), reducing the performance |
| 14 | of the system. |
| 15 | |
| 16 | In many cases, the need for memory from vmalloc() can be eliminated by piecing |
| 17 | together an array from smaller parts; the flexible array library exists to make |
| 18 | this task easier. |
| 19 | |
| 20 | A flexible array holds an arbitrary (within limits) number of fixed-sized |
| 21 | objects, accessed via an integer index. Sparse arrays are handled |
| 22 | reasonably well. Only single-page allocations are made, so memory |
| 23 | allocation failures should be relatively rare. The down sides are that the |
| 24 | arrays cannot be indexed directly, individual object size cannot exceed the |
| 25 | system page size, and putting data into a flexible array requires a copy |
| 26 | operation. It's also worth noting that flexible arrays do no internal |
| 27 | locking at all; if concurrent access to an array is possible, then the |
| 28 | caller must arrange for appropriate mutual exclusion. |
| 29 | |
| 30 | The creation of a flexible array is done with :c:func:`flex_array_alloc()`:: |
| 31 | |
| 32 | #include <linux/flex_array.h> |
| 33 | |
| 34 | struct flex_array *flex_array_alloc(int element_size, |
| 35 | unsigned int total, |
| 36 | gfp_t flags); |
| 37 | |
| 38 | The individual object size is provided by ``element_size``, while total is the |
| 39 | maximum number of objects which can be stored in the array. The flags |
| 40 | argument is passed directly to the internal memory allocation calls. With |
| 41 | the current code, using flags to ask for high memory is likely to lead to |
| 42 | notably unpleasant side effects. |
| 43 | |
| 44 | It is also possible to define flexible arrays at compile time with:: |
| 45 | |
| 46 | DEFINE_FLEX_ARRAY(name, element_size, total); |
| 47 | |
| 48 | This macro will result in a definition of an array with the given name; the |
| 49 | element size and total will be checked for validity at compile time. |
| 50 | |
| 51 | Storing data into a flexible array is accomplished with a call to |
| 52 | :c:func:`flex_array_put()`:: |
| 53 | |
| 54 | int flex_array_put(struct flex_array *array, unsigned int element_nr, |
| 55 | void *src, gfp_t flags); |
| 56 | |
| 57 | This call will copy the data from src into the array, in the position |
| 58 | indicated by ``element_nr`` (which must be less than the maximum specified when |
| 59 | the array was created). If any memory allocations must be performed, flags |
| 60 | will be used. The return value is zero on success, a negative error code |
| 61 | otherwise. |
| 62 | |
| 63 | There might possibly be a need to store data into a flexible array while |
| 64 | running in some sort of atomic context; in this situation, sleeping in the |
| 65 | memory allocator would be a bad thing. That can be avoided by using |
| 66 | ``GFP_ATOMIC`` for the flags value, but, often, there is a better way. The |
| 67 | trick is to ensure that any needed memory allocations are done before |
| 68 | entering atomic context, using :c:func:`flex_array_prealloc()`:: |
| 69 | |
| 70 | int flex_array_prealloc(struct flex_array *array, unsigned int start, |
| 71 | unsigned int nr_elements, gfp_t flags); |
| 72 | |
| 73 | This function will ensure that memory for the elements indexed in the range |
| 74 | defined by ``start`` and ``nr_elements`` has been allocated. Thereafter, a |
| 75 | ``flex_array_put()`` call on an element in that range is guaranteed not to |
| 76 | block. |
| 77 | |
| 78 | Getting data back out of the array is done with :c:func:`flex_array_get()`:: |
| 79 | |
| 80 | void *flex_array_get(struct flex_array *fa, unsigned int element_nr); |
| 81 | |
| 82 | The return value is a pointer to the data element, or NULL if that |
| 83 | particular element has never been allocated. |
| 84 | |
| 85 | Note that it is possible to get back a valid pointer for an element which |
| 86 | has never been stored in the array. Memory for array elements is allocated |
| 87 | one page at a time; a single allocation could provide memory for several |
| 88 | adjacent elements. Flexible array elements are normally initialized to the |
| 89 | value ``FLEX_ARRAY_FREE`` (defined as 0x6c in <linux/poison.h>), so errors |
| 90 | involving that number probably result from use of unstored array entries. |
| 91 | Note that, if array elements are allocated with ``__GFP_ZERO``, they will be |
| 92 | initialized to zero and this poisoning will not happen. |
| 93 | |
| 94 | Individual elements in the array can be cleared with |
| 95 | :c:func:`flex_array_clear()`:: |
| 96 | |
| 97 | int flex_array_clear(struct flex_array *array, unsigned int element_nr); |
| 98 | |
| 99 | This function will set the given element to ``FLEX_ARRAY_FREE`` and return |
| 100 | zero. If storage for the indicated element is not allocated for the array, |
| 101 | ``flex_array_clear()`` will return ``-EINVAL`` instead. Note that clearing an |
| 102 | element does not release the storage associated with it; to reduce the |
| 103 | allocated size of an array, call :c:func:`flex_array_shrink()`:: |
| 104 | |
| 105 | int flex_array_shrink(struct flex_array *array); |
| 106 | |
| 107 | The return value will be the number of pages of memory actually freed. |
| 108 | This function works by scanning the array for pages containing nothing but |
| 109 | ``FLEX_ARRAY_FREE`` bytes, so (1) it can be expensive, and (2) it will not work |
| 110 | if the array's pages are allocated with ``__GFP_ZERO``. |
| 111 | |
| 112 | It is possible to remove all elements of an array with a call to |
| 113 | :c:func:`flex_array_free_parts()`:: |
| 114 | |
| 115 | void flex_array_free_parts(struct flex_array *array); |
| 116 | |
| 117 | This call frees all elements, but leaves the array itself in place. |
| 118 | Freeing the entire array is done with :c:func:`flex_array_free()`:: |
| 119 | |
| 120 | void flex_array_free(struct flex_array *array); |
| 121 | |
| 122 | As of this writing, there are no users of flexible arrays in the mainline |
| 123 | kernel. The functions described here are also not exported to modules; |
| 124 | that will probably be fixed when somebody comes up with a need for it. |
| 125 | |
| 126 | |
| 127 | Flexible array functions |
| 128 | ------------------------ |
| 129 | |
| 130 | .. kernel-doc:: include/linux/flex_array.h |