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> | |
26 | ||
27 | struct flex_array_part { | |
28 | char elements[FLEX_ARRAY_PART_SIZE]; | |
29 | }; | |
30 | ||
534acc05 DH |
31 | /* |
32 | * If a user requests an allocation which is small | |
33 | * enough, we may simply use the space in the | |
34 | * flex_array->parts[] array to store the user | |
35 | * data. | |
36 | */ | |
37 | static inline int elements_fit_in_base(struct flex_array *fa) | |
38 | { | |
39 | int data_size = fa->element_size * fa->total_nr_elements; | |
45b588d6 | 40 | if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT) |
534acc05 DH |
41 | return 1; |
42 | return 0; | |
43 | } | |
44 | ||
45 | /** | |
46 | * flex_array_alloc - allocate a new flexible array | |
47 | * @element_size: the size of individual elements in the array | |
48 | * @total: total number of elements that this should hold | |
49 | * | |
50 | * Note: all locking must be provided by the caller. | |
51 | * | |
52 | * @total is used to size internal structures. If the user ever | |
53 | * accesses any array indexes >=@total, it will produce errors. | |
54 | * | |
55 | * The maximum number of elements is defined as: the number of | |
56 | * elements that can be stored in a page times the number of | |
57 | * page pointers that we can fit in the base structure or (using | |
58 | * integer math): | |
59 | * | |
60 | * (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *) | |
61 | * | |
62 | * Here's a table showing example capacities. Note that the maximum | |
63 | * index that the get/put() functions is just nr_objects-1. This | |
64 | * basically means that you get 4MB of storage on 32-bit and 2MB on | |
65 | * 64-bit. | |
66 | * | |
67 | * | |
68 | * Element size | Objects | Objects | | |
69 | * PAGE_SIZE=4k | 32-bit | 64-bit | | |
70 | * ---------------------------------| | |
71 | * 1 bytes | 4186112 | 2093056 | | |
72 | * 2 bytes | 2093056 | 1046528 | | |
73 | * 3 bytes | 1395030 | 697515 | | |
74 | * 4 bytes | 1046528 | 523264 | | |
75 | * 32 bytes | 130816 | 65408 | | |
76 | * 33 bytes | 126728 | 63364 | | |
77 | * 2048 bytes | 2044 | 1022 | | |
78 | * 2049 bytes | 1022 | 511 | | |
79 | * void * | 1046528 | 261632 | | |
80 | * | |
81 | * Since 64-bit pointers are twice the size, we lose half the | |
82 | * capacity in the base structure. Also note that no effort is made | |
83 | * to efficiently pack objects across page boundaries. | |
84 | */ | |
b62e408c DR |
85 | struct flex_array *flex_array_alloc(int element_size, unsigned int total, |
86 | gfp_t flags) | |
534acc05 DH |
87 | { |
88 | struct flex_array *ret; | |
45b588d6 DR |
89 | int max_size = FLEX_ARRAY_NR_BASE_PTRS * |
90 | FLEX_ARRAY_ELEMENTS_PER_PART(element_size); | |
534acc05 DH |
91 | |
92 | /* max_size will end up 0 if element_size > PAGE_SIZE */ | |
93 | if (total > max_size) | |
94 | return NULL; | |
95 | ret = kzalloc(sizeof(struct flex_array), flags); | |
96 | if (!ret) | |
97 | return NULL; | |
98 | ret->element_size = element_size; | |
99 | ret->total_nr_elements = total; | |
19da3dd1 | 100 | if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) |
45b588d6 DR |
101 | memset(ret->parts[0], FLEX_ARRAY_FREE, |
102 | FLEX_ARRAY_BASE_BYTES_LEFT); | |
534acc05 DH |
103 | return ret; |
104 | } | |
105 | ||
b62e408c DR |
106 | static int fa_element_to_part_nr(struct flex_array *fa, |
107 | unsigned int element_nr) | |
534acc05 | 108 | { |
45b588d6 | 109 | return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); |
534acc05 DH |
110 | } |
111 | ||
112 | /** | |
113 | * flex_array_free_parts - just free the second-level pages | |
534acc05 DH |
114 | * |
115 | * This is to be used in cases where the base 'struct flex_array' | |
116 | * has been statically allocated and should not be free. | |
117 | */ | |
118 | void flex_array_free_parts(struct flex_array *fa) | |
119 | { | |
120 | int part_nr; | |
534acc05 DH |
121 | |
122 | if (elements_fit_in_base(fa)) | |
123 | return; | |
45b588d6 | 124 | for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) |
534acc05 DH |
125 | kfree(fa->parts[part_nr]); |
126 | } | |
127 | ||
128 | void flex_array_free(struct flex_array *fa) | |
129 | { | |
130 | flex_array_free_parts(fa); | |
131 | kfree(fa); | |
132 | } | |
133 | ||
b62e408c DR |
134 | static unsigned int index_inside_part(struct flex_array *fa, |
135 | unsigned int element_nr) | |
534acc05 | 136 | { |
b62e408c | 137 | unsigned int part_offset; |
534acc05 | 138 | |
45b588d6 DR |
139 | part_offset = element_nr % |
140 | FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); | |
534acc05 DH |
141 | return part_offset * fa->element_size; |
142 | } | |
143 | ||
144 | static struct flex_array_part * | |
145 | __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) | |
146 | { | |
147 | struct flex_array_part *part = fa->parts[part_nr]; | |
148 | if (!part) { | |
19da3dd1 | 149 | part = kmalloc(sizeof(struct flex_array_part), flags); |
534acc05 DH |
150 | if (!part) |
151 | return NULL; | |
19da3dd1 DR |
152 | if (!(flags & __GFP_ZERO)) |
153 | memset(part, FLEX_ARRAY_FREE, | |
154 | sizeof(struct flex_array_part)); | |
534acc05 DH |
155 | fa->parts[part_nr] = part; |
156 | } | |
157 | return part; | |
158 | } | |
159 | ||
160 | /** | |
161 | * flex_array_put - copy data into the array at @element_nr | |
162 | * @src: address of data to copy into the array | |
163 | * @element_nr: index of the position in which to insert | |
164 | * the new element. | |
165 | * | |
166 | * Note that this *copies* the contents of @src into | |
167 | * the array. If you are trying to store an array of | |
168 | * pointers, make sure to pass in &ptr instead of ptr. | |
169 | * | |
170 | * Locking must be provided by the caller. | |
171 | */ | |
b62e408c DR |
172 | int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, |
173 | gfp_t flags) | |
534acc05 DH |
174 | { |
175 | int part_nr = fa_element_to_part_nr(fa, element_nr); | |
176 | struct flex_array_part *part; | |
177 | void *dst; | |
178 | ||
179 | if (element_nr >= fa->total_nr_elements) | |
180 | return -ENOSPC; | |
181 | if (elements_fit_in_base(fa)) | |
182 | part = (struct flex_array_part *)&fa->parts[0]; | |
a30b595d | 183 | else { |
534acc05 | 184 | part = __fa_get_part(fa, part_nr, flags); |
a30b595d DR |
185 | if (!part) |
186 | return -ENOMEM; | |
187 | } | |
534acc05 DH |
188 | dst = &part->elements[index_inside_part(fa, element_nr)]; |
189 | memcpy(dst, src, fa->element_size); | |
190 | return 0; | |
191 | } | |
192 | ||
e6de3988 DR |
193 | /** |
194 | * flex_array_clear - clear element in array at @element_nr | |
195 | * @element_nr: index of the position to clear. | |
196 | * | |
197 | * Locking must be provided by the caller. | |
198 | */ | |
199 | int flex_array_clear(struct flex_array *fa, unsigned int element_nr) | |
200 | { | |
201 | int part_nr = fa_element_to_part_nr(fa, element_nr); | |
202 | struct flex_array_part *part; | |
203 | void *dst; | |
204 | ||
205 | if (element_nr >= fa->total_nr_elements) | |
206 | return -ENOSPC; | |
207 | if (elements_fit_in_base(fa)) | |
208 | part = (struct flex_array_part *)&fa->parts[0]; | |
209 | else { | |
210 | part = fa->parts[part_nr]; | |
211 | if (!part) | |
212 | return -EINVAL; | |
213 | } | |
214 | dst = &part->elements[index_inside_part(fa, element_nr)]; | |
19da3dd1 | 215 | memset(dst, FLEX_ARRAY_FREE, fa->element_size); |
e6de3988 DR |
216 | return 0; |
217 | } | |
218 | ||
534acc05 DH |
219 | /** |
220 | * flex_array_prealloc - guarantee that array space exists | |
221 | * @start: index of first array element for which space is allocated | |
222 | * @end: index of last (inclusive) element for which space is allocated | |
223 | * | |
224 | * This will guarantee that no future calls to flex_array_put() | |
225 | * will allocate memory. It can be used if you are expecting to | |
226 | * be holding a lock or in some atomic context while writing | |
227 | * data into the array. | |
228 | * | |
229 | * Locking must be provided by the caller. | |
230 | */ | |
b62e408c DR |
231 | int flex_array_prealloc(struct flex_array *fa, unsigned int start, |
232 | unsigned int end, gfp_t flags) | |
534acc05 DH |
233 | { |
234 | int start_part; | |
235 | int end_part; | |
236 | int part_nr; | |
237 | struct flex_array_part *part; | |
238 | ||
239 | if (start >= fa->total_nr_elements || end >= fa->total_nr_elements) | |
240 | return -ENOSPC; | |
241 | if (elements_fit_in_base(fa)) | |
242 | return 0; | |
243 | start_part = fa_element_to_part_nr(fa, start); | |
244 | end_part = fa_element_to_part_nr(fa, end); | |
245 | for (part_nr = start_part; part_nr <= end_part; part_nr++) { | |
246 | part = __fa_get_part(fa, part_nr, flags); | |
247 | if (!part) | |
248 | return -ENOMEM; | |
249 | } | |
250 | return 0; | |
251 | } | |
252 | ||
253 | /** | |
254 | * flex_array_get - pull data back out of the array | |
255 | * @element_nr: index of the element to fetch from the array | |
256 | * | |
257 | * Returns a pointer to the data at index @element_nr. Note | |
258 | * that this is a copy of the data that was passed in. If you | |
259 | * are using this to store pointers, you'll get back &ptr. | |
260 | * | |
261 | * Locking must be provided by the caller. | |
262 | */ | |
b62e408c | 263 | void *flex_array_get(struct flex_array *fa, unsigned int element_nr) |
534acc05 DH |
264 | { |
265 | int part_nr = fa_element_to_part_nr(fa, element_nr); | |
266 | struct flex_array_part *part; | |
534acc05 DH |
267 | |
268 | if (element_nr >= fa->total_nr_elements) | |
269 | return NULL; | |
534acc05 DH |
270 | if (elements_fit_in_base(fa)) |
271 | part = (struct flex_array_part *)&fa->parts[0]; | |
a30b595d | 272 | else { |
534acc05 | 273 | part = fa->parts[part_nr]; |
a30b595d DR |
274 | if (!part) |
275 | return NULL; | |
276 | } | |
534acc05 DH |
277 | return &part->elements[index_inside_part(fa, element_nr)]; |
278 | } | |
4af5a2f7 DR |
279 | |
280 | static int part_is_free(struct flex_array_part *part) | |
281 | { | |
282 | int i; | |
283 | ||
284 | for (i = 0; i < sizeof(struct flex_array_part); i++) | |
285 | if (part->elements[i] != FLEX_ARRAY_FREE) | |
286 | return 0; | |
287 | return 1; | |
288 | } | |
289 | ||
290 | /** | |
291 | * flex_array_shrink - free unused second-level pages | |
292 | * | |
293 | * Frees all second-level pages that consist solely of unused | |
294 | * elements. Returns the number of pages freed. | |
295 | * | |
296 | * Locking must be provided by the caller. | |
297 | */ | |
298 | int flex_array_shrink(struct flex_array *fa) | |
299 | { | |
300 | struct flex_array_part *part; | |
4af5a2f7 DR |
301 | int part_nr; |
302 | int ret = 0; | |
303 | ||
304 | if (elements_fit_in_base(fa)) | |
305 | return ret; | |
45b588d6 | 306 | for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) { |
4af5a2f7 DR |
307 | part = fa->parts[part_nr]; |
308 | if (!part) | |
309 | continue; | |
310 | if (part_is_free(part)) { | |
311 | fa->parts[part_nr] = NULL; | |
312 | kfree(part); | |
313 | ret++; | |
314 | } | |
315 | } | |
316 | return ret; | |
317 | } |