1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#include <linux/flex_array.h>
24#include <linux/slab.h>
25#include <linux/stddef.h>
26
27struct flex_array_part {
28 char elements[FLEX_ARRAY_PART_SIZE];
29};
30
31
32
33
34
35
36
37static inline int elements_fit_in_base(struct flex_array *fa)
38{
39 int data_size = fa->element_size * fa->total_nr_elements;
40 if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
41 return 1;
42 return 0;
43}
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86struct flex_array *flex_array_alloc(int element_size, unsigned int total,
87 gfp_t flags)
88{
89 struct flex_array *ret;
90 int max_size = FLEX_ARRAY_NR_BASE_PTRS *
91 FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
92
93
94 if (total > max_size)
95 return NULL;
96 ret = kzalloc(sizeof(struct flex_array), flags);
97 if (!ret)
98 return NULL;
99 ret->element_size = element_size;
100 ret->total_nr_elements = total;
101 if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
102 memset(ret->parts[0], FLEX_ARRAY_FREE,
103 FLEX_ARRAY_BASE_BYTES_LEFT);
104 return ret;
105}
106
107static int fa_element_to_part_nr(struct flex_array *fa,
108 unsigned int element_nr)
109{
110 return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
111}
112
113
114
115
116
117
118
119
120void flex_array_free_parts(struct flex_array *fa)
121{
122 int part_nr;
123
124 if (elements_fit_in_base(fa))
125 return;
126 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
127 kfree(fa->parts[part_nr]);
128}
129
130void flex_array_free(struct flex_array *fa)
131{
132 flex_array_free_parts(fa);
133 kfree(fa);
134}
135
136static unsigned int index_inside_part(struct flex_array *fa,
137 unsigned int element_nr)
138{
139 unsigned int part_offset;
140
141 part_offset = element_nr %
142 FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
143 return part_offset * fa->element_size;
144}
145
146static struct flex_array_part *
147__fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
148{
149 struct flex_array_part *part = fa->parts[part_nr];
150 if (!part) {
151 part = kmalloc(sizeof(struct flex_array_part), flags);
152 if (!part)
153 return NULL;
154 if (!(flags & __GFP_ZERO))
155 memset(part, FLEX_ARRAY_FREE,
156 sizeof(struct flex_array_part));
157 fa->parts[part_nr] = part;
158 }
159 return part;
160}
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
178 gfp_t flags)
179{
180 int part_nr = fa_element_to_part_nr(fa, element_nr);
181 struct flex_array_part *part;
182 void *dst;
183
184 if (element_nr >= fa->total_nr_elements)
185 return -ENOSPC;
186 if (elements_fit_in_base(fa))
187 part = (struct flex_array_part *)&fa->parts[0];
188 else {
189 part = __fa_get_part(fa, part_nr, flags);
190 if (!part)
191 return -ENOMEM;
192 }
193 dst = &part->elements[index_inside_part(fa, element_nr)];
194 memcpy(dst, src, fa->element_size);
195 return 0;
196}
197
198
199
200
201
202
203
204
205int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
206{
207 int part_nr = fa_element_to_part_nr(fa, element_nr);
208 struct flex_array_part *part;
209 void *dst;
210
211 if (element_nr >= fa->total_nr_elements)
212 return -ENOSPC;
213 if (elements_fit_in_base(fa))
214 part = (struct flex_array_part *)&fa->parts[0];
215 else {
216 part = fa->parts[part_nr];
217 if (!part)
218 return -EINVAL;
219 }
220 dst = &part->elements[index_inside_part(fa, element_nr)];
221 memset(dst, FLEX_ARRAY_FREE, fa->element_size);
222 return 0;
223}
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239int flex_array_prealloc(struct flex_array *fa, unsigned int start,
240 unsigned int end, gfp_t flags)
241{
242 int start_part;
243 int end_part;
244 int part_nr;
245 struct flex_array_part *part;
246
247 if (start >= fa->total_nr_elements || end >= fa->total_nr_elements)
248 return -ENOSPC;
249 if (elements_fit_in_base(fa))
250 return 0;
251 start_part = fa_element_to_part_nr(fa, start);
252 end_part = fa_element_to_part_nr(fa, end);
253 for (part_nr = start_part; part_nr <= end_part; part_nr++) {
254 part = __fa_get_part(fa, part_nr, flags);
255 if (!part)
256 return -ENOMEM;
257 }
258 return 0;
259}
260
261
262
263
264
265
266
267
268
269
270
271
272void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
273{
274 int part_nr = fa_element_to_part_nr(fa, element_nr);
275 struct flex_array_part *part;
276
277 if (element_nr >= fa->total_nr_elements)
278 return NULL;
279 if (elements_fit_in_base(fa))
280 part = (struct flex_array_part *)&fa->parts[0];
281 else {
282 part = fa->parts[part_nr];
283 if (!part)
284 return NULL;
285 }
286 return &part->elements[index_inside_part(fa, element_nr)];
287}
288
289static int part_is_free(struct flex_array_part *part)
290{
291 int i;
292
293 for (i = 0; i < sizeof(struct flex_array_part); i++)
294 if (part->elements[i] != FLEX_ARRAY_FREE)
295 return 0;
296 return 1;
297}
298
299
300
301
302
303
304
305
306
307
308int flex_array_shrink(struct flex_array *fa)
309{
310 struct flex_array_part *part;
311 int part_nr;
312 int ret = 0;
313
314 if (elements_fit_in_base(fa))
315 return ret;
316 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
317 part = fa->parts[part_nr];
318 if (!part)
319 continue;
320 if (part_is_free(part)) {
321 fa->parts[part_nr] = NULL;
322 kfree(part);
323 ret++;
324 }
325 }
326 return ret;
327}
328