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