Branch data Line data Source code
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>
26 : : #include <linux/export.h>
27 : : #include <linux/reciprocal_div.h>
28 : :
29 : : struct flex_array_part {
30 : : char elements[FLEX_ARRAY_PART_SIZE];
31 : : };
32 : :
33 : : /*
34 : : * If a user requests an allocation which is small
35 : : * enough, we may simply use the space in the
36 : : * flex_array->parts[] array to store the user
37 : : * data.
38 : : */
39 : : static inline int elements_fit_in_base(struct flex_array *fa)
40 : : {
41 : 0 : int data_size = fa->element_size * fa->total_nr_elements;
42 [ # # ][ # # ]: 0 : if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
43 : : return 1;
44 : : return 0;
45 : : }
46 : :
47 : : /**
48 : : * flex_array_alloc - allocate a new flexible array
49 : : * @element_size: the size of individual elements in the array
50 : : * @total: total number of elements that this should hold
51 : : * @flags: page allocation flags to use for base array
52 : : *
53 : : * Note: all locking must be provided by the caller.
54 : : *
55 : : * @total is used to size internal structures. If the user ever
56 : : * accesses any array indexes >=@total, it will produce errors.
57 : : *
58 : : * The maximum number of elements is defined as: the number of
59 : : * elements that can be stored in a page times the number of
60 : : * page pointers that we can fit in the base structure or (using
61 : : * integer math):
62 : : *
63 : : * (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
64 : : *
65 : : * Here's a table showing example capacities. Note that the maximum
66 : : * index that the get/put() functions is just nr_objects-1. This
67 : : * basically means that you get 4MB of storage on 32-bit and 2MB on
68 : : * 64-bit.
69 : : *
70 : : *
71 : : * Element size | Objects | Objects |
72 : : * PAGE_SIZE=4k | 32-bit | 64-bit |
73 : : * ---------------------------------|
74 : : * 1 bytes | 4177920 | 2088960 |
75 : : * 2 bytes | 2088960 | 1044480 |
76 : : * 3 bytes | 1392300 | 696150 |
77 : : * 4 bytes | 1044480 | 522240 |
78 : : * 32 bytes | 130560 | 65408 |
79 : : * 33 bytes | 126480 | 63240 |
80 : : * 2048 bytes | 2040 | 1020 |
81 : : * 2049 bytes | 1020 | 510 |
82 : : * void * | 1044480 | 261120 |
83 : : *
84 : : * Since 64-bit pointers are twice the size, we lose half the
85 : : * capacity in the base structure. Also note that no effort is made
86 : : * to efficiently pack objects across page boundaries.
87 : : */
88 : 0 : struct flex_array *flex_array_alloc(int element_size, unsigned int total,
89 : : gfp_t flags)
90 : : {
91 : : struct flex_array *ret;
92 : : int elems_per_part = 0;
93 : : int max_size = 0;
94 : 0 : struct reciprocal_value reciprocal_elems = { 0 };
95 : :
96 [ # # ]: 0 : if (element_size) {
97 : 0 : elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
98 : 0 : reciprocal_elems = reciprocal_value(elems_per_part);
99 : 0 : max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
100 : : }
101 : :
102 : : /* max_size will end up 0 if element_size > PAGE_SIZE */
103 [ # # ]: 0 : if (total > max_size)
104 : : return NULL;
105 : : ret = kzalloc(sizeof(struct flex_array), flags);
106 [ # # ]: 0 : if (!ret)
107 : : return NULL;
108 : 0 : ret->element_size = element_size;
109 : 0 : ret->total_nr_elements = total;
110 : 0 : ret->elems_per_part = elems_per_part;
111 : 0 : ret->reciprocal_elems = reciprocal_elems;
112 [ # # ][ # # ]: 0 : if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
113 : 0 : memset(&ret->parts[0], FLEX_ARRAY_FREE,
114 : : FLEX_ARRAY_BASE_BYTES_LEFT);
115 : 0 : return ret;
116 : : }
117 : : EXPORT_SYMBOL(flex_array_alloc);
118 : :
119 : : static int fa_element_to_part_nr(struct flex_array *fa,
120 : : unsigned int element_nr)
121 : : {
122 : : /*
123 : : * if element_size == 0 we don't get here, so we never touch
124 : : * the zeroed fa->reciprocal_elems, which would yield invalid
125 : : * results
126 : : */
127 : 0 : return reciprocal_divide(element_nr, fa->reciprocal_elems);
128 : : }
129 : :
130 : : /**
131 : : * flex_array_free_parts - just free the second-level pages
132 : : * @fa: the flex array from which to free parts
133 : : *
134 : : * This is to be used in cases where the base 'struct flex_array'
135 : : * has been statically allocated and should not be free.
136 : : */
137 : 0 : void flex_array_free_parts(struct flex_array *fa)
138 : : {
139 : : int part_nr;
140 : :
141 [ # # ]: 0 : if (elements_fit_in_base(fa))
142 : 0 : return;
143 [ # # ]: 0 : for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
144 : 0 : kfree(fa->parts[part_nr]);
145 : : }
146 : : EXPORT_SYMBOL(flex_array_free_parts);
147 : :
148 : 0 : void flex_array_free(struct flex_array *fa)
149 : : {
150 : 0 : flex_array_free_parts(fa);
151 : 0 : kfree(fa);
152 : 0 : }
153 : : EXPORT_SYMBOL(flex_array_free);
154 : :
155 : : static unsigned int index_inside_part(struct flex_array *fa,
156 : : unsigned int element_nr,
157 : : unsigned int part_nr)
158 : : {
159 : : unsigned int part_offset;
160 : :
161 : 0 : part_offset = element_nr - part_nr * fa->elems_per_part;
162 : 0 : return part_offset * fa->element_size;
163 : : }
164 : :
165 : : static struct flex_array_part *
166 : 0 : __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
167 : : {
168 : 0 : struct flex_array_part *part = fa->parts[part_nr];
169 [ # # ]: 0 : if (!part) {
170 : : part = kmalloc(sizeof(struct flex_array_part), flags);
171 [ # # ]: 0 : if (!part)
172 : : return NULL;
173 [ # # ]: 0 : if (!(flags & __GFP_ZERO))
174 : 0 : memset(part, FLEX_ARRAY_FREE,
175 : : sizeof(struct flex_array_part));
176 : 0 : fa->parts[part_nr] = part;
177 : : }
178 : 0 : return part;
179 : : }
180 : :
181 : : /**
182 : : * flex_array_put - copy data into the array at @element_nr
183 : : * @fa: the flex array to copy data into
184 : : * @element_nr: index of the position in which to insert
185 : : * the new element.
186 : : * @src: address of data to copy into the array
187 : : * @flags: page allocation flags to use for array expansion
188 : : *
189 : : *
190 : : * Note that this *copies* the contents of @src into
191 : : * the array. If you are trying to store an array of
192 : : * pointers, make sure to pass in &ptr instead of ptr.
193 : : * You may instead wish to use the flex_array_put_ptr()
194 : : * helper function.
195 : : *
196 : : * Locking must be provided by the caller.
197 : : */
198 : 0 : int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
199 : : gfp_t flags)
200 : : {
201 : : int part_nr = 0;
202 : : struct flex_array_part *part;
203 : : void *dst;
204 : :
205 [ # # ]: 0 : if (element_nr >= fa->total_nr_elements)
206 : : return -ENOSPC;
207 [ # # ]: 0 : if (!fa->element_size)
208 : : return 0;
209 [ # # ]: 0 : if (elements_fit_in_base(fa))
210 : 0 : part = (struct flex_array_part *)&fa->parts[0];
211 : : else {
212 : : part_nr = fa_element_to_part_nr(fa, element_nr);
213 : 0 : part = __fa_get_part(fa, part_nr, flags);
214 [ # # ]: 0 : if (!part)
215 : : return -ENOMEM;
216 : : }
217 : 0 : dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
218 : 0 : memcpy(dst, src, fa->element_size);
219 : 0 : return 0;
220 : : }
221 : : EXPORT_SYMBOL(flex_array_put);
222 : :
223 : : /**
224 : : * flex_array_clear - clear element in array at @element_nr
225 : : * @fa: the flex array of the element.
226 : : * @element_nr: index of the position to clear.
227 : : *
228 : : * Locking must be provided by the caller.
229 : : */
230 : 0 : int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
231 : : {
232 : : int part_nr = 0;
233 : : struct flex_array_part *part;
234 : : void *dst;
235 : :
236 [ # # ]: 0 : if (element_nr >= fa->total_nr_elements)
237 : : return -ENOSPC;
238 [ # # ]: 0 : if (!fa->element_size)
239 : : return 0;
240 [ # # ]: 0 : if (elements_fit_in_base(fa))
241 : 0 : part = (struct flex_array_part *)&fa->parts[0];
242 : : else {
243 : : part_nr = fa_element_to_part_nr(fa, element_nr);
244 : 0 : part = fa->parts[part_nr];
245 [ # # ]: 0 : if (!part)
246 : : return -EINVAL;
247 : : }
248 : 0 : dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
249 [ # # ]: 0 : memset(dst, FLEX_ARRAY_FREE, fa->element_size);
250 : : return 0;
251 : : }
252 : : EXPORT_SYMBOL(flex_array_clear);
253 : :
254 : : /**
255 : : * flex_array_prealloc - guarantee that array space exists
256 : : * @fa: the flex array for which to preallocate parts
257 : : * @start: index of first array element for which space is allocated
258 : : * @nr_elements: number of elements for which space is allocated
259 : : * @flags: page allocation flags
260 : : *
261 : : * This will guarantee that no future calls to flex_array_put()
262 : : * will allocate memory. It can be used if you are expecting to
263 : : * be holding a lock or in some atomic context while writing
264 : : * data into the array.
265 : : *
266 : : * Locking must be provided by the caller.
267 : : */
268 : 0 : int flex_array_prealloc(struct flex_array *fa, unsigned int start,
269 : : unsigned int nr_elements, gfp_t flags)
270 : : {
271 : : int start_part;
272 : : int end_part;
273 : : int part_nr;
274 : : unsigned int end;
275 : : struct flex_array_part *part;
276 : :
277 [ # # ]: 0 : if (!start && !nr_elements)
278 : : return 0;
279 [ # # ]: 0 : if (start >= fa->total_nr_elements)
280 : : return -ENOSPC;
281 [ # # ]: 0 : if (!nr_elements)
282 : : return 0;
283 : :
284 : 0 : end = start + nr_elements - 1;
285 : :
286 [ # # ]: 0 : if (end >= fa->total_nr_elements)
287 : : return -ENOSPC;
288 [ # # ]: 0 : if (!fa->element_size)
289 : : return 0;
290 [ # # ]: 0 : if (elements_fit_in_base(fa))
291 : : return 0;
292 : : start_part = fa_element_to_part_nr(fa, start);
293 : : end_part = fa_element_to_part_nr(fa, end);
294 [ # # ]: 0 : for (part_nr = start_part; part_nr <= end_part; part_nr++) {
295 : 0 : part = __fa_get_part(fa, part_nr, flags);
296 [ # # ]: 0 : if (!part)
297 : : return -ENOMEM;
298 : : }
299 : : return 0;
300 : : }
301 : : EXPORT_SYMBOL(flex_array_prealloc);
302 : :
303 : : /**
304 : : * flex_array_get - pull data back out of the array
305 : : * @fa: the flex array from which to extract data
306 : : * @element_nr: index of the element to fetch from the array
307 : : *
308 : : * Returns a pointer to the data at index @element_nr. Note
309 : : * that this is a copy of the data that was passed in. If you
310 : : * are using this to store pointers, you'll get back &ptr. You
311 : : * may instead wish to use the flex_array_get_ptr helper.
312 : : *
313 : : * Locking must be provided by the caller.
314 : : */
315 : 0 : void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
316 : : {
317 : : int part_nr = 0;
318 : : struct flex_array_part *part;
319 : :
320 [ # # ]: 0 : if (!fa->element_size)
321 : : return NULL;
322 [ # # ]: 0 : if (element_nr >= fa->total_nr_elements)
323 : : return NULL;
324 [ # # ]: 0 : if (elements_fit_in_base(fa))
325 : 0 : part = (struct flex_array_part *)&fa->parts[0];
326 : : else {
327 : : part_nr = fa_element_to_part_nr(fa, element_nr);
328 : 0 : part = fa->parts[part_nr];
329 [ # # ]: 0 : if (!part)
330 : : return NULL;
331 : : }
332 : 0 : return &part->elements[index_inside_part(fa, element_nr, part_nr)];
333 : : }
334 : : EXPORT_SYMBOL(flex_array_get);
335 : :
336 : : /**
337 : : * flex_array_get_ptr - pull a ptr back out of the array
338 : : * @fa: the flex array from which to extract data
339 : : * @element_nr: index of the element to fetch from the array
340 : : *
341 : : * Returns the pointer placed in the flex array at element_nr using
342 : : * flex_array_put_ptr(). This function should not be called if the
343 : : * element in question was not set using the _put_ptr() helper.
344 : : */
345 : 0 : void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr)
346 : : {
347 : : void **tmp;
348 : :
349 : 0 : tmp = flex_array_get(fa, element_nr);
350 [ # # ]: 0 : if (!tmp)
351 : : return NULL;
352 : :
353 : 0 : return *tmp;
354 : : }
355 : : EXPORT_SYMBOL(flex_array_get_ptr);
356 : :
357 : : static int part_is_free(struct flex_array_part *part)
358 : : {
359 : : int i;
360 : :
361 [ # # ]: 0 : for (i = 0; i < sizeof(struct flex_array_part); i++)
362 [ # # ]: 0 : if (part->elements[i] != FLEX_ARRAY_FREE)
363 : : return 0;
364 : : return 1;
365 : : }
366 : :
367 : : /**
368 : : * flex_array_shrink - free unused second-level pages
369 : : * @fa: the flex array to shrink
370 : : *
371 : : * Frees all second-level pages that consist solely of unused
372 : : * elements. Returns the number of pages freed.
373 : : *
374 : : * Locking must be provided by the caller.
375 : : */
376 : 0 : int flex_array_shrink(struct flex_array *fa)
377 : : {
378 : : struct flex_array_part *part;
379 : : int part_nr;
380 : : int ret = 0;
381 : :
382 [ # # ][ # # ]: 0 : if (!fa->total_nr_elements || !fa->element_size)
383 : : return 0;
384 [ # # ]: 0 : if (elements_fit_in_base(fa))
385 : : return ret;
386 [ # # ]: 0 : for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
387 : 0 : part = fa->parts[part_nr];
388 [ # # ]: 0 : if (!part)
389 : 0 : continue;
390 [ # # ]: 0 : if (part_is_free(part)) {
391 : 0 : fa->parts[part_nr] = NULL;
392 : 0 : kfree(part);
393 : 0 : ret++;
394 : : }
395 : : }
396 : : return ret;
397 : : }
398 : : EXPORT_SYMBOL(flex_array_shrink);
|
