aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/flexible-arrays.txt
diff options
context:
space:
mode:
authorJonathan Corbet <corbet@lwn.net>2009-09-08 19:49:37 -0400
committerJonathan Corbet <corbet@lwn.net>2009-09-10 16:33:36 -0400
commit6c19efb46aacf2c5043ad210b888ee58ffb848c0 (patch)
tree2d6ed1de6c8f3ed2df44a5d008ee2316284527bf /Documentation/flexible-arrays.txt
parente8188807b7cd14e0a001946005f0c58f9dd9dfe6 (diff)
Document the flex_array library.
A brief document on how to use flexible arrays, derived from an article first published on LWN. Signed-off-by: Jonathan Corbet <corbet@lwn.net>
Diffstat (limited to 'Documentation/flexible-arrays.txt')
-rw-r--r--Documentation/flexible-arrays.txt99
1 files changed, 99 insertions, 0 deletions
diff --git a/Documentation/flexible-arrays.txt b/Documentation/flexible-arrays.txt
new file mode 100644
index 000000000000..84eb26808dee
--- /dev/null
+++ b/Documentation/flexible-arrays.txt
@@ -0,0 +1,99 @@
1Using flexible arrays in the kernel
2Last updated for 2.6.31
3Jonathan Corbet <corbet@lwn.net>
4
5Large contiguous memory allocations can be unreliable in the Linux kernel.
6Kernel programmers will sometimes respond to this problem by allocating
7pages with vmalloc(). This solution not ideal, though. On 32-bit systems,
8memory from vmalloc() must be mapped into a relatively small address space;
9it's easy to run out. On SMP systems, the page table changes required by
10vmalloc() allocations can require expensive cross-processor interrupts on
11all CPUs. And, on all systems, use of space in the vmalloc() range
12increases pressure on the translation lookaside buffer (TLB), reducing the
13performance of the system.
14
15In many cases, the need for memory from vmalloc() can be eliminated by
16piecing together an array from smaller parts; the flexible array library
17exists to make this task easier.
18
19A flexible array holds an arbitrary (within limits) number of fixed-sized
20objects, accessed via an integer index. Sparse arrays are handled
21reasonably well. Only single-page allocations are made, so memory
22allocation failures should be relatively rare. The down sides are that the
23arrays cannot be indexed directly, individual object size cannot exceed the
24system page size, and putting data into a flexible array requires a copy
25operation. It's also worth noting that flexible arrays do no internal
26locking at all; if concurrent access to an array is possible, then the
27caller must arrange for appropriate mutual exclusion.
28
29The creation of a flexible array is done with:
30
31 #include <linux/flex_array.h>
32
33 struct flex_array *flex_array_alloc(int element_size,
34 unsigned int total,
35 gfp_t flags);
36
37The individual object size is provided by element_size, while total is the
38maximum number of objects which can be stored in the array. The flags
39argument is passed directly to the internal memory allocation calls. With
40the current code, using flags to ask for high memory is likely to lead to
41notably unpleasant side effects.
42
43Storing data into a flexible array is accomplished with a call to:
44
45 int flex_array_put(struct flex_array *array, unsigned int element_nr,
46 void *src, gfp_t flags);
47
48This call will copy the data from src into the array, in the position
49indicated by element_nr (which must be less than the maximum specified when
50the array was created). If any memory allocations must be performed, flags
51will be used. The return value is zero on success, a negative error code
52otherwise.
53
54There might possibly be a need to store data into a flexible array while
55running in some sort of atomic context; in this situation, sleeping in the
56memory allocator would be a bad thing. That can be avoided by using
57GFP_ATOMIC for the flags value, but, often, there is a better way. The
58trick is to ensure that any needed memory allocations are done before
59entering atomic context, using:
60
61 int flex_array_prealloc(struct flex_array *array, unsigned int start,
62 unsigned int end, gfp_t flags);
63
64This function will ensure that memory for the elements indexed in the range
65defined by start and end has been allocated. Thereafter, a
66flex_array_put() call on an element in that range is guaranteed not to
67block.
68
69Getting data back out of the array is done with:
70
71 void *flex_array_get(struct flex_array *fa, unsigned int element_nr);
72
73The return value is a pointer to the data element, or NULL if that
74particular element has never been allocated.
75
76Note that it is possible to get back a valid pointer for an element which
77has never been stored in the array. Memory for array elements is allocated
78one page at a time; a single allocation could provide memory for several
79adjacent elements. The flexible array code does not know if a specific
80element has been written; it only knows if the associated memory is
81present. So a flex_array_get() call on an element which was never stored
82in the array has the potential to return a pointer to random data. If the
83caller does not have a separate way to know which elements were actually
84stored, it might be wise, at least, to add GFP_ZERO to the flags argument
85to ensure that all elements are zeroed.
86
87There is no way to remove a single element from the array. It is possible,
88though, to remove all elements with a call to:
89
90 void flex_array_free_parts(struct flex_array *array);
91
92This call frees all elements, but leaves the array itself in place.
93Freeing the entire array is done with:
94
95 void flex_array_free(struct flex_array *array);
96
97As of this writing, there are no users of flexible arrays in the mainline
98kernel. The functions described here are also not exported to modules;
99that will probably be fixed when somebody comes up with a need for it.