Commit | Line | Data |
---|---|---|
534acc05 DH |
1 | /* |
2 | * Flexible array managed in PAGE_SIZE parts | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or modify | |
5 | * it under the terms of the GNU General Public License as published by | |
6 | * the Free Software Foundation; either version 2 of the License, or | |
7 | * (at your option) any later version. | |
8 | * | |
9 | * This program is distributed in the hope that it will be useful, | |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | * GNU General Public License for more details. | |
13 | * | |
14 | * You should have received a copy of the GNU General Public License | |
15 | * along with this program; if not, write to the Free Software | |
16 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
17 | * | |
18 | * Copyright IBM Corporation, 2009 | |
19 | * | |
20 | * Author: Dave Hansen <dave@linux.vnet.ibm.com> | |
21 | */ | |
22 | ||
23 | #include <linux/flex_array.h> | |
24 | #include <linux/slab.h> | |
25 | #include <linux/stddef.h> | |
78c377d1 | 26 | #include <linux/module.h> |
534acc05 DH |
27 | |
28 | struct flex_array_part { | |
29 | char elements[FLEX_ARRAY_PART_SIZE]; | |
30 | }; | |
31 | ||
534acc05 DH |
32 | /* |
33 | * If a user requests an allocation which is small | |
34 | * enough, we may simply use the space in the | |
35 | * flex_array->parts[] array to store the user | |
36 | * data. | |
37 | */ | |
38 | static inline int elements_fit_in_base(struct flex_array *fa) | |
39 | { | |
40 | int data_size = fa->element_size * fa->total_nr_elements; | |
45b588d6 | 41 | if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT) |
534acc05 DH |
42 | return 1; |
43 | return 0; | |
44 | } | |
45 | ||
46 | /** | |
47 | * flex_array_alloc - allocate a new flexible array | |
48 | * @element_size: the size of individual elements in the array | |
49 | * @total: total number of elements that this should hold | |
fc0d8d94 | 50 | * @flags: page allocation flags to use for base array |
534acc05 DH |
51 | * |
52 | * Note: all locking must be provided by the caller. | |
53 | * | |
54 | * @total is used to size internal structures. If the user ever | |
55 | * accesses any array indexes >=@total, it will produce errors. | |
56 | * | |
57 | * The maximum number of elements is defined as: the number of | |
58 | * elements that can be stored in a page times the number of | |
59 | * page pointers that we can fit in the base structure or (using | |
60 | * integer math): | |
61 | * | |
62 | * (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *) | |
63 | * | |
64 | * Here's a table showing example capacities. Note that the maximum | |
65 | * index that the get/put() functions is just nr_objects-1. This | |
66 | * basically means that you get 4MB of storage on 32-bit and 2MB on | |
67 | * 64-bit. | |
68 | * | |
69 | * | |
70 | * Element size | Objects | Objects | | |
71 | * PAGE_SIZE=4k | 32-bit | 64-bit | | |
72 | * ---------------------------------| | |
73 | * 1 bytes | 4186112 | 2093056 | | |
74 | * 2 bytes | 2093056 | 1046528 | | |
75 | * 3 bytes | 1395030 | 697515 | | |
76 | * 4 bytes | 1046528 | 523264 | | |
77 | * 32 bytes | 130816 | 65408 | | |
78 | * 33 bytes | 126728 | 63364 | | |
79 | * 2048 bytes | 2044 | 1022 | | |
80 | * 2049 bytes | 1022 | 511 | | |
81 | * void * | 1046528 | 261632 | | |
82 | * | |
83 | * Since 64-bit pointers are twice the size, we lose half the | |
84 | * capacity in the base structure. Also note that no effort is made | |
85 | * to efficiently pack objects across page boundaries. | |
86 | */ | |
b62e408c DR |
87 | struct flex_array *flex_array_alloc(int element_size, unsigned int total, |
88 | gfp_t flags) | |
534acc05 DH |
89 | { |
90 | struct flex_array *ret; | |
a8d05c81 EP |
91 | int max_size = 0; |
92 | ||
93 | if (element_size) | |
94 | max_size = FLEX_ARRAY_NR_BASE_PTRS * | |
95 | FLEX_ARRAY_ELEMENTS_PER_PART(element_size); | |
534acc05 DH |
96 | |
97 | /* max_size will end up 0 if element_size > PAGE_SIZE */ | |
98 | if (total > max_size) | |
99 | return NULL; | |
100 | ret = kzalloc(sizeof(struct flex_array), flags); | |
101 | if (!ret) | |
102 | return NULL; | |
103 | ret->element_size = element_size; | |
104 | ret->total_nr_elements = total; | |
19da3dd1 | 105 | if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) |
e59464c7 | 106 | memset(&ret->parts[0], FLEX_ARRAY_FREE, |
45b588d6 | 107 | FLEX_ARRAY_BASE_BYTES_LEFT); |
534acc05 DH |
108 | return ret; |
109 | } | |
78c377d1 | 110 | EXPORT_SYMBOL(flex_array_alloc); |
534acc05 | 111 | |
b62e408c DR |
112 | static int fa_element_to_part_nr(struct flex_array *fa, |
113 | unsigned int element_nr) | |
534acc05 | 114 | { |
45b588d6 | 115 | return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); |
534acc05 DH |
116 | } |
117 | ||
118 | /** | |
119 | * flex_array_free_parts - just free the second-level pages | |
fc0d8d94 | 120 | * @fa: the flex array from which to free parts |
534acc05 DH |
121 | * |
122 | * This is to be used in cases where the base 'struct flex_array' | |
123 | * has been statically allocated and should not be free. | |
124 | */ | |
125 | void flex_array_free_parts(struct flex_array *fa) | |
126 | { | |
127 | int part_nr; | |
534acc05 DH |
128 | |
129 | if (elements_fit_in_base(fa)) | |
130 | return; | |
45b588d6 | 131 | for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) |
534acc05 DH |
132 | kfree(fa->parts[part_nr]); |
133 | } | |
78c377d1 | 134 | EXPORT_SYMBOL(flex_array_free_parts); |
534acc05 DH |
135 | |
136 | void flex_array_free(struct flex_array *fa) | |
137 | { | |
138 | flex_array_free_parts(fa); | |
139 | kfree(fa); | |
140 | } | |
78c377d1 | 141 | EXPORT_SYMBOL(flex_array_free); |
534acc05 | 142 | |
b62e408c DR |
143 | static unsigned int index_inside_part(struct flex_array *fa, |
144 | unsigned int element_nr) | |
534acc05 | 145 | { |
b62e408c | 146 | unsigned int part_offset; |
534acc05 | 147 | |
45b588d6 DR |
148 | part_offset = element_nr % |
149 | FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); | |
534acc05 DH |
150 | return part_offset * fa->element_size; |
151 | } | |
152 | ||
153 | static struct flex_array_part * | |
154 | __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) | |
155 | { | |
156 | struct flex_array_part *part = fa->parts[part_nr]; | |
157 | if (!part) { | |
19da3dd1 | 158 | part = kmalloc(sizeof(struct flex_array_part), flags); |
534acc05 DH |
159 | if (!part) |
160 | return NULL; | |
19da3dd1 DR |
161 | if (!(flags & __GFP_ZERO)) |
162 | memset(part, FLEX_ARRAY_FREE, | |
163 | sizeof(struct flex_array_part)); | |
534acc05 DH |
164 | fa->parts[part_nr] = part; |
165 | } | |
166 | return part; | |
167 | } | |
168 | ||
169 | /** | |
170 | * flex_array_put - copy data into the array at @element_nr | |
fc0d8d94 | 171 | * @fa: the flex array to copy data into |
534acc05 DH |
172 | * @element_nr: index of the position in which to insert |
173 | * the new element. | |
fc0d8d94 DR |
174 | * @src: address of data to copy into the array |
175 | * @flags: page allocation flags to use for array expansion | |
176 | * | |
534acc05 DH |
177 | * |
178 | * Note that this *copies* the contents of @src into | |
179 | * the array. If you are trying to store an array of | |
180 | * pointers, make sure to pass in &ptr instead of ptr. | |
ea98eed9 EP |
181 | * You may instead wish to use the flex_array_put_ptr() |
182 | * helper function. | |
534acc05 DH |
183 | * |
184 | * Locking must be provided by the caller. | |
185 | */ | |
b62e408c DR |
186 | int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, |
187 | gfp_t flags) | |
534acc05 | 188 | { |
a8d05c81 | 189 | int part_nr; |
534acc05 DH |
190 | struct flex_array_part *part; |
191 | void *dst; | |
192 | ||
193 | if (element_nr >= fa->total_nr_elements) | |
194 | return -ENOSPC; | |
a8d05c81 EP |
195 | if (!fa->element_size) |
196 | return 0; | |
534acc05 DH |
197 | if (elements_fit_in_base(fa)) |
198 | part = (struct flex_array_part *)&fa->parts[0]; | |
a30b595d | 199 | else { |
a8d05c81 | 200 | part_nr = fa_element_to_part_nr(fa, element_nr); |
534acc05 | 201 | part = __fa_get_part(fa, part_nr, flags); |
a30b595d DR |
202 | if (!part) |
203 | return -ENOMEM; | |
204 | } | |
534acc05 DH |
205 | dst = &part->elements[index_inside_part(fa, element_nr)]; |
206 | memcpy(dst, src, fa->element_size); | |
207 | return 0; | |
208 | } | |
78c377d1 | 209 | EXPORT_SYMBOL(flex_array_put); |
534acc05 | 210 | |
e6de3988 DR |
211 | /** |
212 | * flex_array_clear - clear element in array at @element_nr | |
fc0d8d94 | 213 | * @fa: the flex array of the element. |
e6de3988 DR |
214 | * @element_nr: index of the position to clear. |
215 | * | |
216 | * Locking must be provided by the caller. | |
217 | */ | |
218 | int flex_array_clear(struct flex_array *fa, unsigned int element_nr) | |
219 | { | |
a8d05c81 | 220 | int part_nr; |
e6de3988 DR |
221 | struct flex_array_part *part; |
222 | void *dst; | |
223 | ||
224 | if (element_nr >= fa->total_nr_elements) | |
225 | return -ENOSPC; | |
a8d05c81 EP |
226 | if (!fa->element_size) |
227 | return 0; | |
e6de3988 DR |
228 | if (elements_fit_in_base(fa)) |
229 | part = (struct flex_array_part *)&fa->parts[0]; | |
230 | else { | |
a8d05c81 | 231 | part_nr = fa_element_to_part_nr(fa, element_nr); |
e6de3988 DR |
232 | part = fa->parts[part_nr]; |
233 | if (!part) | |
234 | return -EINVAL; | |
235 | } | |
236 | dst = &part->elements[index_inside_part(fa, element_nr)]; | |
19da3dd1 | 237 | memset(dst, FLEX_ARRAY_FREE, fa->element_size); |
e6de3988 DR |
238 | return 0; |
239 | } | |
78c377d1 | 240 | EXPORT_SYMBOL(flex_array_clear); |
e6de3988 | 241 | |
534acc05 DH |
242 | /** |
243 | * flex_array_prealloc - guarantee that array space exists | |
5a3ea878 EP |
244 | * @fa: the flex array for which to preallocate parts |
245 | * @start: index of first array element for which space is allocated | |
246 | * @nr_elements: number of elements for which space is allocated | |
247 | * @flags: page allocation flags | |
534acc05 DH |
248 | * |
249 | * This will guarantee that no future calls to flex_array_put() | |
250 | * will allocate memory. It can be used if you are expecting to | |
251 | * be holding a lock or in some atomic context while writing | |
252 | * data into the array. | |
253 | * | |
254 | * Locking must be provided by the caller. | |
255 | */ | |
b62e408c | 256 | int flex_array_prealloc(struct flex_array *fa, unsigned int start, |
5a3ea878 | 257 | unsigned int nr_elements, gfp_t flags) |
534acc05 DH |
258 | { |
259 | int start_part; | |
260 | int end_part; | |
261 | int part_nr; | |
5a3ea878 | 262 | unsigned int end; |
534acc05 DH |
263 | struct flex_array_part *part; |
264 | ||
150cdf6e EP |
265 | if (!start && !nr_elements) |
266 | return 0; | |
267 | if (start >= fa->total_nr_elements) | |
268 | return -ENOSPC; | |
269 | if (!nr_elements) | |
270 | return 0; | |
271 | ||
5a3ea878 EP |
272 | end = start + nr_elements - 1; |
273 | ||
150cdf6e | 274 | if (end >= fa->total_nr_elements) |
534acc05 | 275 | return -ENOSPC; |
a8d05c81 EP |
276 | if (!fa->element_size) |
277 | return 0; | |
534acc05 DH |
278 | if (elements_fit_in_base(fa)) |
279 | return 0; | |
280 | start_part = fa_element_to_part_nr(fa, start); | |
281 | end_part = fa_element_to_part_nr(fa, end); | |
282 | for (part_nr = start_part; part_nr <= end_part; part_nr++) { | |
283 | part = __fa_get_part(fa, part_nr, flags); | |
284 | if (!part) | |
285 | return -ENOMEM; | |
286 | } | |
287 | return 0; | |
288 | } | |
78c377d1 | 289 | EXPORT_SYMBOL(flex_array_prealloc); |
534acc05 DH |
290 | |
291 | /** | |
292 | * flex_array_get - pull data back out of the array | |
fc0d8d94 | 293 | * @fa: the flex array from which to extract data |
534acc05 DH |
294 | * @element_nr: index of the element to fetch from the array |
295 | * | |
296 | * Returns a pointer to the data at index @element_nr. Note | |
297 | * that this is a copy of the data that was passed in. If you | |
ea98eed9 EP |
298 | * are using this to store pointers, you'll get back &ptr. You |
299 | * may instead wish to use the flex_array_get_ptr helper. | |
534acc05 DH |
300 | * |
301 | * Locking must be provided by the caller. | |
302 | */ | |
b62e408c | 303 | void *flex_array_get(struct flex_array *fa, unsigned int element_nr) |
534acc05 | 304 | { |
a8d05c81 | 305 | int part_nr; |
534acc05 | 306 | struct flex_array_part *part; |
534acc05 | 307 | |
a8d05c81 EP |
308 | if (!fa->element_size) |
309 | return NULL; | |
534acc05 DH |
310 | if (element_nr >= fa->total_nr_elements) |
311 | return NULL; | |
534acc05 DH |
312 | if (elements_fit_in_base(fa)) |
313 | part = (struct flex_array_part *)&fa->parts[0]; | |
a30b595d | 314 | else { |
a8d05c81 | 315 | part_nr = fa_element_to_part_nr(fa, element_nr); |
534acc05 | 316 | part = fa->parts[part_nr]; |
a30b595d DR |
317 | if (!part) |
318 | return NULL; | |
319 | } | |
534acc05 DH |
320 | return &part->elements[index_inside_part(fa, element_nr)]; |
321 | } | |
78c377d1 | 322 | EXPORT_SYMBOL(flex_array_get); |
4af5a2f7 | 323 | |
ea98eed9 EP |
324 | /** |
325 | * flex_array_get_ptr - pull a ptr back out of the array | |
326 | * @fa: the flex array from which to extract data | |
327 | * @element_nr: index of the element to fetch from the array | |
328 | * | |
329 | * Returns the pointer placed in the flex array at element_nr using | |
330 | * flex_array_put_ptr(). This function should not be called if the | |
331 | * element in question was not set using the _put_ptr() helper. | |
332 | */ | |
333 | void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr) | |
334 | { | |
335 | void **tmp; | |
336 | ||
337 | tmp = flex_array_get(fa, element_nr); | |
338 | if (!tmp) | |
339 | return NULL; | |
340 | ||
341 | return *tmp; | |
342 | } | |
78c377d1 | 343 | EXPORT_SYMBOL(flex_array_get_ptr); |
ea98eed9 | 344 | |
4af5a2f7 DR |
345 | static int part_is_free(struct flex_array_part *part) |
346 | { | |
347 | int i; | |
348 | ||
349 | for (i = 0; i < sizeof(struct flex_array_part); i++) | |
350 | if (part->elements[i] != FLEX_ARRAY_FREE) | |
351 | return 0; | |
352 | return 1; | |
353 | } | |
354 | ||
355 | /** | |
356 | * flex_array_shrink - free unused second-level pages | |
fc0d8d94 | 357 | * @fa: the flex array to shrink |
4af5a2f7 DR |
358 | * |
359 | * Frees all second-level pages that consist solely of unused | |
360 | * elements. Returns the number of pages freed. | |
361 | * | |
362 | * Locking must be provided by the caller. | |
363 | */ | |
364 | int flex_array_shrink(struct flex_array *fa) | |
365 | { | |
366 | struct flex_array_part *part; | |
4af5a2f7 DR |
367 | int part_nr; |
368 | int ret = 0; | |
369 | ||
a8d05c81 | 370 | if (!fa->total_nr_elements || !fa->element_size) |
150cdf6e | 371 | return 0; |
4af5a2f7 DR |
372 | if (elements_fit_in_base(fa)) |
373 | return ret; | |
45b588d6 | 374 | for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) { |
4af5a2f7 DR |
375 | part = fa->parts[part_nr]; |
376 | if (!part) | |
377 | continue; | |
378 | if (part_is_free(part)) { | |
379 | fa->parts[part_nr] = NULL; | |
380 | kfree(part); | |
381 | ret++; | |
382 | } | |
383 | } | |
384 | return ret; | |
385 | } | |
78c377d1 | 386 | EXPORT_SYMBOL(flex_array_shrink); |