]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2017-2018 Intel Corporation | |
3 | */ | |
4 | ||
9f95a23c | 5 | #include <fcntl.h> |
11fdf7f2 TL |
6 | #include <inttypes.h> |
7 | #include <limits.h> | |
8 | #include <sys/mman.h> | |
9 | #include <stdint.h> | |
10 | #include <errno.h> | |
11 | #include <sys/file.h> | |
12 | #include <string.h> | |
13 | ||
14 | #include <rte_common.h> | |
15 | #include <rte_log.h> | |
16 | #include <rte_errno.h> | |
17 | #include <rte_spinlock.h> | |
18 | #include <rte_tailq.h> | |
19 | ||
20 | #include "eal_filesystem.h" | |
21 | #include "eal_private.h" | |
22 | ||
23 | #include "rte_fbarray.h" | |
24 | ||
25 | #define MASK_SHIFT 6ULL | |
26 | #define MASK_ALIGN (1ULL << MASK_SHIFT) | |
27 | #define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT) | |
28 | #define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN)) | |
29 | #define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod) | |
30 | ||
9f95a23c TL |
31 | /* |
32 | * We use this to keep track of created/attached memory areas to prevent user | |
33 | * errors in API usage. | |
34 | */ | |
35 | struct mem_area { | |
36 | TAILQ_ENTRY(mem_area) next; | |
37 | void *addr; | |
38 | size_t len; | |
39 | int fd; | |
40 | }; | |
41 | TAILQ_HEAD(mem_area_head, mem_area); | |
42 | /* local per-process tailq */ | |
43 | static struct mem_area_head mem_area_tailq = | |
44 | TAILQ_HEAD_INITIALIZER(mem_area_tailq); | |
45 | static rte_spinlock_t mem_area_lock = RTE_SPINLOCK_INITIALIZER; | |
46 | ||
11fdf7f2 TL |
47 | /* |
48 | * This is a mask that is always stored at the end of array, to provide fast | |
49 | * way of finding free/used spots without looping through each element. | |
50 | */ | |
51 | ||
52 | struct used_mask { | |
53 | unsigned int n_masks; | |
54 | uint64_t data[]; | |
55 | }; | |
56 | ||
57 | static size_t | |
58 | calc_mask_size(unsigned int len) | |
59 | { | |
60 | /* mask must be multiple of MASK_ALIGN, even though length of array | |
61 | * itself may not be aligned on that boundary. | |
62 | */ | |
63 | len = RTE_ALIGN_CEIL(len, MASK_ALIGN); | |
64 | return sizeof(struct used_mask) + | |
65 | sizeof(uint64_t) * MASK_LEN_TO_IDX(len); | |
66 | } | |
67 | ||
68 | static size_t | |
69 | calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len) | |
70 | { | |
71 | size_t data_sz = elt_sz * len; | |
72 | size_t msk_sz = calc_mask_size(len); | |
73 | return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz); | |
74 | } | |
75 | ||
76 | static struct used_mask * | |
77 | get_used_mask(void *data, unsigned int elt_sz, unsigned int len) | |
78 | { | |
79 | return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len); | |
80 | } | |
81 | ||
82 | static int | |
83 | resize_and_map(int fd, void *addr, size_t len) | |
84 | { | |
85 | char path[PATH_MAX]; | |
86 | void *map_addr; | |
87 | ||
88 | if (ftruncate(fd, len)) { | |
89 | RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path); | |
90 | /* pass errno up the chain */ | |
91 | rte_errno = errno; | |
92 | return -1; | |
93 | } | |
94 | ||
95 | map_addr = mmap(addr, len, PROT_READ | PROT_WRITE, | |
96 | MAP_SHARED | MAP_FIXED, fd, 0); | |
97 | if (map_addr != addr) { | |
98 | RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno)); | |
99 | /* pass errno up the chain */ | |
100 | rte_errno = errno; | |
101 | return -1; | |
102 | } | |
103 | return 0; | |
104 | } | |
105 | ||
9f95a23c TL |
106 | static int |
107 | overlap(const struct mem_area *ma, const void *start, size_t len) | |
108 | { | |
109 | const void *end = RTE_PTR_ADD(start, len); | |
110 | const void *ma_start = ma->addr; | |
111 | const void *ma_end = RTE_PTR_ADD(ma->addr, ma->len); | |
112 | ||
113 | /* start overlap? */ | |
114 | if (start >= ma_start && start < ma_end) | |
115 | return 1; | |
116 | /* end overlap? */ | |
117 | if (end >= ma_start && end < ma_end) | |
118 | return 1; | |
119 | return 0; | |
120 | } | |
121 | ||
11fdf7f2 TL |
122 | static int |
123 | find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, | |
124 | bool used) | |
125 | { | |
126 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
127 | arr->len); | |
128 | unsigned int msk_idx, lookahead_idx, first, first_mod; | |
129 | unsigned int last, last_mod; | |
130 | uint64_t last_msk, ignore_msk; | |
131 | ||
132 | /* | |
133 | * mask only has granularity of MASK_ALIGN, but start may not be aligned | |
134 | * on that boundary, so construct a special mask to exclude anything we | |
135 | * don't want to see to avoid confusing ctz. | |
136 | */ | |
137 | first = MASK_LEN_TO_IDX(start); | |
138 | first_mod = MASK_LEN_TO_MOD(start); | |
139 | ignore_msk = ~((1ULL << first_mod) - 1); | |
140 | ||
141 | /* array length may not be aligned, so calculate ignore mask for last | |
142 | * mask index. | |
143 | */ | |
144 | last = MASK_LEN_TO_IDX(arr->len); | |
145 | last_mod = MASK_LEN_TO_MOD(arr->len); | |
146 | last_msk = ~(-1ULL << last_mod); | |
147 | ||
148 | for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) { | |
149 | uint64_t cur_msk, lookahead_msk; | |
150 | unsigned int run_start, clz, left; | |
151 | bool found = false; | |
152 | /* | |
153 | * The process of getting n consecutive bits for arbitrary n is | |
154 | * a bit involved, but here it is in a nutshell: | |
155 | * | |
156 | * 1. let n be the number of consecutive bits we're looking for | |
157 | * 2. check if n can fit in one mask, and if so, do n-1 | |
158 | * rshift-ands to see if there is an appropriate run inside | |
159 | * our current mask | |
160 | * 2a. if we found a run, bail out early | |
161 | * 2b. if we didn't find a run, proceed | |
162 | * 3. invert the mask and count leading zeroes (that is, count | |
163 | * how many consecutive set bits we had starting from the | |
164 | * end of current mask) as k | |
165 | * 3a. if k is 0, continue to next mask | |
166 | * 3b. if k is not 0, we have a potential run | |
167 | * 4. to satisfy our requirements, next mask must have n-k | |
168 | * consecutive set bits right at the start, so we will do | |
169 | * (n-k-1) rshift-ands and check if first bit is set. | |
170 | * | |
171 | * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until | |
172 | * we either run out of masks, lose the run, or find what we | |
173 | * were looking for. | |
174 | */ | |
175 | cur_msk = msk->data[msk_idx]; | |
176 | left = n; | |
177 | ||
178 | /* if we're looking for free spaces, invert the mask */ | |
179 | if (!used) | |
180 | cur_msk = ~cur_msk; | |
181 | ||
182 | /* combine current ignore mask with last index ignore mask */ | |
183 | if (msk_idx == last) | |
184 | ignore_msk |= last_msk; | |
185 | ||
186 | /* if we have an ignore mask, ignore once */ | |
187 | if (ignore_msk) { | |
188 | cur_msk &= ignore_msk; | |
189 | ignore_msk = 0; | |
190 | } | |
191 | ||
192 | /* if n can fit in within a single mask, do a search */ | |
193 | if (n <= MASK_ALIGN) { | |
194 | uint64_t tmp_msk = cur_msk; | |
195 | unsigned int s_idx; | |
196 | for (s_idx = 0; s_idx < n - 1; s_idx++) | |
197 | tmp_msk &= tmp_msk >> 1ULL; | |
198 | /* we found what we were looking for */ | |
199 | if (tmp_msk != 0) { | |
200 | run_start = __builtin_ctzll(tmp_msk); | |
201 | return MASK_GET_IDX(msk_idx, run_start); | |
202 | } | |
203 | } | |
204 | ||
205 | /* | |
206 | * we didn't find our run within the mask, or n > MASK_ALIGN, | |
207 | * so we're going for plan B. | |
208 | */ | |
209 | ||
210 | /* count leading zeroes on inverted mask */ | |
211 | if (~cur_msk == 0) | |
212 | clz = sizeof(cur_msk) * 8; | |
213 | else | |
214 | clz = __builtin_clzll(~cur_msk); | |
215 | ||
216 | /* if there aren't any runs at the end either, just continue */ | |
217 | if (clz == 0) | |
218 | continue; | |
219 | ||
220 | /* we have a partial run at the end, so try looking ahead */ | |
221 | run_start = MASK_ALIGN - clz; | |
222 | left -= clz; | |
223 | ||
224 | for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks; | |
225 | lookahead_idx++) { | |
226 | unsigned int s_idx, need; | |
227 | lookahead_msk = msk->data[lookahead_idx]; | |
228 | ||
229 | /* if we're looking for free space, invert the mask */ | |
230 | if (!used) | |
231 | lookahead_msk = ~lookahead_msk; | |
232 | ||
233 | /* figure out how many consecutive bits we need here */ | |
234 | need = RTE_MIN(left, MASK_ALIGN); | |
235 | ||
236 | for (s_idx = 0; s_idx < need - 1; s_idx++) | |
237 | lookahead_msk &= lookahead_msk >> 1ULL; | |
238 | ||
239 | /* if first bit is not set, we've lost the run */ | |
240 | if ((lookahead_msk & 1) == 0) { | |
241 | /* | |
242 | * we've scanned this far, so we know there are | |
243 | * no runs in the space we've lookahead-scanned | |
244 | * as well, so skip that on next iteration. | |
245 | */ | |
246 | ignore_msk = ~((1ULL << need) - 1); | |
247 | msk_idx = lookahead_idx; | |
248 | break; | |
249 | } | |
250 | ||
251 | left -= need; | |
252 | ||
253 | /* check if we've found what we were looking for */ | |
254 | if (left == 0) { | |
255 | found = true; | |
256 | break; | |
257 | } | |
258 | } | |
259 | ||
260 | /* we didn't find anything, so continue */ | |
261 | if (!found) | |
262 | continue; | |
263 | ||
264 | return MASK_GET_IDX(msk_idx, run_start); | |
265 | } | |
266 | /* we didn't find anything */ | |
267 | rte_errno = used ? ENOENT : ENOSPC; | |
268 | return -1; | |
269 | } | |
270 | ||
271 | static int | |
272 | find_next(const struct rte_fbarray *arr, unsigned int start, bool used) | |
273 | { | |
274 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
275 | arr->len); | |
276 | unsigned int idx, first, first_mod; | |
277 | unsigned int last, last_mod; | |
278 | uint64_t last_msk, ignore_msk; | |
279 | ||
280 | /* | |
281 | * mask only has granularity of MASK_ALIGN, but start may not be aligned | |
282 | * on that boundary, so construct a special mask to exclude anything we | |
283 | * don't want to see to avoid confusing ctz. | |
284 | */ | |
285 | first = MASK_LEN_TO_IDX(start); | |
286 | first_mod = MASK_LEN_TO_MOD(start); | |
287 | ignore_msk = ~((1ULL << first_mod) - 1ULL); | |
288 | ||
289 | /* array length may not be aligned, so calculate ignore mask for last | |
290 | * mask index. | |
291 | */ | |
292 | last = MASK_LEN_TO_IDX(arr->len); | |
293 | last_mod = MASK_LEN_TO_MOD(arr->len); | |
294 | last_msk = ~(-(1ULL) << last_mod); | |
295 | ||
296 | for (idx = first; idx < msk->n_masks; idx++) { | |
297 | uint64_t cur = msk->data[idx]; | |
298 | int found; | |
299 | ||
300 | /* if we're looking for free entries, invert mask */ | |
301 | if (!used) | |
302 | cur = ~cur; | |
303 | ||
304 | if (idx == last) | |
305 | cur &= last_msk; | |
306 | ||
307 | /* ignore everything before start on first iteration */ | |
308 | if (idx == first) | |
309 | cur &= ignore_msk; | |
310 | ||
311 | /* check if we have any entries */ | |
312 | if (cur == 0) | |
313 | continue; | |
314 | ||
315 | /* | |
316 | * find first set bit - that will correspond to whatever it is | |
317 | * that we're looking for. | |
318 | */ | |
319 | found = __builtin_ctzll(cur); | |
320 | return MASK_GET_IDX(idx, found); | |
321 | } | |
322 | /* we didn't find anything */ | |
323 | rte_errno = used ? ENOENT : ENOSPC; | |
324 | return -1; | |
325 | } | |
326 | ||
327 | static int | |
328 | find_contig(const struct rte_fbarray *arr, unsigned int start, bool used) | |
329 | { | |
330 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
331 | arr->len); | |
332 | unsigned int idx, first, first_mod; | |
333 | unsigned int last, last_mod; | |
334 | uint64_t last_msk; | |
335 | unsigned int need_len, result = 0; | |
336 | ||
337 | /* array length may not be aligned, so calculate ignore mask for last | |
338 | * mask index. | |
339 | */ | |
340 | last = MASK_LEN_TO_IDX(arr->len); | |
341 | last_mod = MASK_LEN_TO_MOD(arr->len); | |
342 | last_msk = ~(-(1ULL) << last_mod); | |
343 | ||
344 | first = MASK_LEN_TO_IDX(start); | |
345 | first_mod = MASK_LEN_TO_MOD(start); | |
346 | for (idx = first; idx < msk->n_masks; idx++, result += need_len) { | |
347 | uint64_t cur = msk->data[idx]; | |
348 | unsigned int run_len; | |
349 | ||
350 | need_len = MASK_ALIGN; | |
351 | ||
352 | /* if we're looking for free entries, invert mask */ | |
353 | if (!used) | |
354 | cur = ~cur; | |
355 | ||
356 | /* if this is last mask, ignore everything after last bit */ | |
357 | if (idx == last) | |
358 | cur &= last_msk; | |
359 | ||
360 | /* ignore everything before start on first iteration */ | |
361 | if (idx == first) { | |
362 | cur >>= first_mod; | |
363 | /* at the start, we don't need the full mask len */ | |
364 | need_len -= first_mod; | |
365 | } | |
366 | ||
367 | /* we will be looking for zeroes, so invert the mask */ | |
368 | cur = ~cur; | |
369 | ||
370 | /* if mask is zero, we have a complete run */ | |
371 | if (cur == 0) | |
372 | continue; | |
373 | ||
374 | /* | |
375 | * see if current run ends before mask end. | |
376 | */ | |
377 | run_len = __builtin_ctzll(cur); | |
378 | ||
379 | /* add however many zeroes we've had in the last run and quit */ | |
380 | if (run_len < need_len) { | |
381 | result += run_len; | |
382 | break; | |
383 | } | |
384 | } | |
385 | return result; | |
386 | } | |
387 | ||
388 | static int | |
389 | find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, | |
390 | bool used) | |
391 | { | |
392 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
393 | arr->len); | |
394 | unsigned int msk_idx, lookbehind_idx, first, first_mod; | |
395 | uint64_t ignore_msk; | |
396 | ||
397 | /* | |
398 | * mask only has granularity of MASK_ALIGN, but start may not be aligned | |
399 | * on that boundary, so construct a special mask to exclude anything we | |
400 | * don't want to see to avoid confusing ctz. | |
401 | */ | |
402 | first = MASK_LEN_TO_IDX(start); | |
403 | first_mod = MASK_LEN_TO_MOD(start); | |
404 | /* we're going backwards, so mask must start from the top */ | |
405 | ignore_msk = first_mod == MASK_ALIGN - 1 ? | |
406 | -1ULL : /* prevent overflow */ | |
407 | ~(-1ULL << (first_mod + 1)); | |
408 | ||
409 | /* go backwards, include zero */ | |
410 | msk_idx = first; | |
411 | do { | |
412 | uint64_t cur_msk, lookbehind_msk; | |
413 | unsigned int run_start, run_end, ctz, left; | |
414 | bool found = false; | |
415 | /* | |
416 | * The process of getting n consecutive bits from the top for | |
417 | * arbitrary n is a bit involved, but here it is in a nutshell: | |
418 | * | |
419 | * 1. let n be the number of consecutive bits we're looking for | |
420 | * 2. check if n can fit in one mask, and if so, do n-1 | |
421 | * lshift-ands to see if there is an appropriate run inside | |
422 | * our current mask | |
423 | * 2a. if we found a run, bail out early | |
424 | * 2b. if we didn't find a run, proceed | |
425 | * 3. invert the mask and count trailing zeroes (that is, count | |
426 | * how many consecutive set bits we had starting from the | |
427 | * start of current mask) as k | |
428 | * 3a. if k is 0, continue to next mask | |
429 | * 3b. if k is not 0, we have a potential run | |
430 | * 4. to satisfy our requirements, next mask must have n-k | |
431 | * consecutive set bits at the end, so we will do (n-k-1) | |
432 | * lshift-ands and check if last bit is set. | |
433 | * | |
434 | * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until | |
435 | * we either run out of masks, lose the run, or find what we | |
436 | * were looking for. | |
437 | */ | |
438 | cur_msk = msk->data[msk_idx]; | |
439 | left = n; | |
440 | ||
441 | /* if we're looking for free spaces, invert the mask */ | |
442 | if (!used) | |
443 | cur_msk = ~cur_msk; | |
444 | ||
445 | /* if we have an ignore mask, ignore once */ | |
446 | if (ignore_msk) { | |
447 | cur_msk &= ignore_msk; | |
448 | ignore_msk = 0; | |
449 | } | |
450 | ||
451 | /* if n can fit in within a single mask, do a search */ | |
452 | if (n <= MASK_ALIGN) { | |
453 | uint64_t tmp_msk = cur_msk; | |
454 | unsigned int s_idx; | |
455 | for (s_idx = 0; s_idx < n - 1; s_idx++) | |
456 | tmp_msk &= tmp_msk << 1ULL; | |
457 | /* we found what we were looking for */ | |
458 | if (tmp_msk != 0) { | |
459 | /* clz will give us offset from end of mask, and | |
460 | * we only get the end of our run, not start, | |
461 | * so adjust result to point to where start | |
462 | * would have been. | |
463 | */ | |
464 | run_start = MASK_ALIGN - | |
465 | __builtin_clzll(tmp_msk) - n; | |
466 | return MASK_GET_IDX(msk_idx, run_start); | |
467 | } | |
468 | } | |
469 | ||
470 | /* | |
471 | * we didn't find our run within the mask, or n > MASK_ALIGN, | |
472 | * so we're going for plan B. | |
473 | */ | |
474 | ||
475 | /* count trailing zeroes on inverted mask */ | |
476 | if (~cur_msk == 0) | |
477 | ctz = sizeof(cur_msk) * 8; | |
478 | else | |
479 | ctz = __builtin_ctzll(~cur_msk); | |
480 | ||
481 | /* if there aren't any runs at the start either, just | |
482 | * continue | |
483 | */ | |
484 | if (ctz == 0) | |
485 | continue; | |
486 | ||
487 | /* we have a partial run at the start, so try looking behind */ | |
488 | run_end = MASK_GET_IDX(msk_idx, ctz); | |
489 | left -= ctz; | |
490 | ||
491 | /* go backwards, include zero */ | |
492 | lookbehind_idx = msk_idx - 1; | |
493 | ||
494 | /* we can't lookbehind as we've run out of masks, so stop */ | |
495 | if (msk_idx == 0) | |
496 | break; | |
497 | ||
498 | do { | |
499 | const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1); | |
500 | unsigned int s_idx, need; | |
501 | ||
502 | lookbehind_msk = msk->data[lookbehind_idx]; | |
503 | ||
504 | /* if we're looking for free space, invert the mask */ | |
505 | if (!used) | |
506 | lookbehind_msk = ~lookbehind_msk; | |
507 | ||
508 | /* figure out how many consecutive bits we need here */ | |
509 | need = RTE_MIN(left, MASK_ALIGN); | |
510 | ||
511 | for (s_idx = 0; s_idx < need - 1; s_idx++) | |
512 | lookbehind_msk &= lookbehind_msk << 1ULL; | |
513 | ||
514 | /* if last bit is not set, we've lost the run */ | |
515 | if ((lookbehind_msk & last_bit) == 0) { | |
516 | /* | |
517 | * we've scanned this far, so we know there are | |
518 | * no runs in the space we've lookbehind-scanned | |
519 | * as well, so skip that on next iteration. | |
520 | */ | |
521 | ignore_msk = -1ULL << need; | |
522 | msk_idx = lookbehind_idx; | |
523 | break; | |
524 | } | |
525 | ||
526 | left -= need; | |
527 | ||
528 | /* check if we've found what we were looking for */ | |
529 | if (left == 0) { | |
530 | found = true; | |
531 | break; | |
532 | } | |
533 | } while ((lookbehind_idx--) != 0); /* decrement after check to | |
534 | * include zero | |
535 | */ | |
536 | ||
537 | /* we didn't find anything, so continue */ | |
538 | if (!found) | |
539 | continue; | |
540 | ||
541 | /* we've found what we were looking for, but we only know where | |
542 | * the run ended, so calculate start position. | |
543 | */ | |
544 | return run_end - n; | |
545 | } while (msk_idx-- != 0); /* decrement after check to include zero */ | |
546 | /* we didn't find anything */ | |
547 | rte_errno = used ? ENOENT : ENOSPC; | |
548 | return -1; | |
549 | } | |
550 | ||
551 | static int | |
552 | find_prev(const struct rte_fbarray *arr, unsigned int start, bool used) | |
553 | { | |
554 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
555 | arr->len); | |
556 | unsigned int idx, first, first_mod; | |
557 | uint64_t ignore_msk; | |
558 | ||
559 | /* | |
560 | * mask only has granularity of MASK_ALIGN, but start may not be aligned | |
561 | * on that boundary, so construct a special mask to exclude anything we | |
562 | * don't want to see to avoid confusing clz. | |
563 | */ | |
564 | first = MASK_LEN_TO_IDX(start); | |
565 | first_mod = MASK_LEN_TO_MOD(start); | |
566 | /* we're going backwards, so mask must start from the top */ | |
567 | ignore_msk = first_mod == MASK_ALIGN - 1 ? | |
568 | -1ULL : /* prevent overflow */ | |
569 | ~(-1ULL << (first_mod + 1)); | |
570 | ||
571 | /* go backwards, include zero */ | |
572 | idx = first; | |
573 | do { | |
574 | uint64_t cur = msk->data[idx]; | |
575 | int found; | |
576 | ||
577 | /* if we're looking for free entries, invert mask */ | |
578 | if (!used) | |
579 | cur = ~cur; | |
580 | ||
581 | /* ignore everything before start on first iteration */ | |
582 | if (idx == first) | |
583 | cur &= ignore_msk; | |
584 | ||
585 | /* check if we have any entries */ | |
586 | if (cur == 0) | |
587 | continue; | |
588 | ||
589 | /* | |
590 | * find last set bit - that will correspond to whatever it is | |
591 | * that we're looking for. we're counting trailing zeroes, thus | |
592 | * the value we get is counted from end of mask, so calculate | |
593 | * position from start of mask. | |
594 | */ | |
595 | found = MASK_ALIGN - __builtin_clzll(cur) - 1; | |
596 | ||
597 | return MASK_GET_IDX(idx, found); | |
598 | } while (idx-- != 0); /* decrement after check to include zero*/ | |
599 | ||
600 | /* we didn't find anything */ | |
601 | rte_errno = used ? ENOENT : ENOSPC; | |
602 | return -1; | |
603 | } | |
604 | ||
605 | static int | |
606 | find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used) | |
607 | { | |
608 | const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, | |
609 | arr->len); | |
610 | unsigned int idx, first, first_mod; | |
611 | unsigned int need_len, result = 0; | |
612 | ||
613 | first = MASK_LEN_TO_IDX(start); | |
614 | first_mod = MASK_LEN_TO_MOD(start); | |
615 | ||
616 | /* go backwards, include zero */ | |
617 | idx = first; | |
618 | do { | |
619 | uint64_t cur = msk->data[idx]; | |
620 | unsigned int run_len; | |
621 | ||
622 | need_len = MASK_ALIGN; | |
623 | ||
624 | /* if we're looking for free entries, invert mask */ | |
625 | if (!used) | |
626 | cur = ~cur; | |
627 | ||
628 | /* ignore everything after start on first iteration */ | |
629 | if (idx == first) { | |
630 | unsigned int end_len = MASK_ALIGN - first_mod - 1; | |
631 | cur <<= end_len; | |
632 | /* at the start, we don't need the full mask len */ | |
633 | need_len -= end_len; | |
634 | } | |
635 | ||
636 | /* we will be looking for zeroes, so invert the mask */ | |
637 | cur = ~cur; | |
638 | ||
639 | /* if mask is zero, we have a complete run */ | |
640 | if (cur == 0) | |
641 | goto endloop; | |
642 | ||
643 | /* | |
644 | * see where run ends, starting from the end. | |
645 | */ | |
646 | run_len = __builtin_clzll(cur); | |
647 | ||
648 | /* add however many zeroes we've had in the last run and quit */ | |
649 | if (run_len < need_len) { | |
650 | result += run_len; | |
651 | break; | |
652 | } | |
653 | endloop: | |
654 | result += need_len; | |
655 | } while (idx-- != 0); /* decrement after check to include zero */ | |
656 | return result; | |
657 | } | |
658 | ||
659 | static int | |
660 | set_used(struct rte_fbarray *arr, unsigned int idx, bool used) | |
661 | { | |
662 | struct used_mask *msk; | |
663 | uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx); | |
664 | unsigned int msk_idx = MASK_LEN_TO_IDX(idx); | |
665 | bool already_used; | |
666 | int ret = -1; | |
667 | ||
668 | if (arr == NULL || idx >= arr->len) { | |
669 | rte_errno = EINVAL; | |
670 | return -1; | |
671 | } | |
672 | msk = get_used_mask(arr->data, arr->elt_sz, arr->len); | |
673 | ret = 0; | |
674 | ||
675 | /* prevent array from changing under us */ | |
676 | rte_rwlock_write_lock(&arr->rwlock); | |
677 | ||
678 | already_used = (msk->data[msk_idx] & msk_bit) != 0; | |
679 | ||
680 | /* nothing to be done */ | |
681 | if (used == already_used) | |
682 | goto out; | |
683 | ||
684 | if (used) { | |
685 | msk->data[msk_idx] |= msk_bit; | |
686 | arr->count++; | |
687 | } else { | |
688 | msk->data[msk_idx] &= ~msk_bit; | |
689 | arr->count--; | |
690 | } | |
691 | out: | |
692 | rte_rwlock_write_unlock(&arr->rwlock); | |
693 | ||
694 | return ret; | |
695 | } | |
696 | ||
697 | static int | |
698 | fully_validate(const char *name, unsigned int elt_sz, unsigned int len) | |
699 | { | |
700 | if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) { | |
701 | rte_errno = EINVAL; | |
702 | return -1; | |
703 | } | |
704 | ||
705 | if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) { | |
706 | rte_errno = ENAMETOOLONG; | |
707 | return -1; | |
708 | } | |
709 | return 0; | |
710 | } | |
711 | ||
f67539c2 | 712 | int |
11fdf7f2 TL |
713 | rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len, |
714 | unsigned int elt_sz) | |
715 | { | |
716 | size_t page_sz, mmap_len; | |
717 | char path[PATH_MAX]; | |
718 | struct used_mask *msk; | |
9f95a23c | 719 | struct mem_area *ma = NULL; |
11fdf7f2 TL |
720 | void *data = NULL; |
721 | int fd = -1; | |
722 | ||
723 | if (arr == NULL) { | |
724 | rte_errno = EINVAL; | |
725 | return -1; | |
726 | } | |
727 | ||
728 | if (fully_validate(name, elt_sz, len)) | |
729 | return -1; | |
730 | ||
9f95a23c TL |
731 | /* allocate mem area before doing anything */ |
732 | ma = malloc(sizeof(*ma)); | |
733 | if (ma == NULL) { | |
734 | rte_errno = ENOMEM; | |
735 | return -1; | |
736 | } | |
737 | ||
11fdf7f2 | 738 | page_sz = sysconf(_SC_PAGESIZE); |
9f95a23c TL |
739 | if (page_sz == (size_t)-1) { |
740 | free(ma); | |
741 | return -1; | |
742 | } | |
11fdf7f2 TL |
743 | |
744 | /* calculate our memory limits */ | |
745 | mmap_len = calc_data_size(page_sz, elt_sz, len); | |
746 | ||
747 | data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0); | |
9f95a23c TL |
748 | if (data == NULL) { |
749 | free(ma); | |
750 | return -1; | |
751 | } | |
752 | ||
753 | rte_spinlock_lock(&mem_area_lock); | |
754 | ||
755 | fd = -1; | |
11fdf7f2 TL |
756 | |
757 | if (internal_config.no_shconf) { | |
758 | /* remap virtual area as writable */ | |
759 | void *new_data = mmap(data, mmap_len, PROT_READ | PROT_WRITE, | |
9f95a23c | 760 | MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, fd, 0); |
11fdf7f2 TL |
761 | if (new_data == MAP_FAILED) { |
762 | RTE_LOG(DEBUG, EAL, "%s(): couldn't remap anonymous memory: %s\n", | |
763 | __func__, strerror(errno)); | |
764 | goto fail; | |
765 | } | |
766 | } else { | |
767 | eal_get_fbarray_path(path, sizeof(path), name); | |
768 | ||
769 | /* | |
770 | * Each fbarray is unique to process namespace, i.e. the | |
771 | * filename depends on process prefix. Try to take out a lock | |
772 | * and see if we succeed. If we don't, someone else is using it | |
773 | * already. | |
774 | */ | |
775 | fd = open(path, O_CREAT | O_RDWR, 0600); | |
776 | if (fd < 0) { | |
777 | RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n", | |
778 | __func__, path, strerror(errno)); | |
779 | rte_errno = errno; | |
780 | goto fail; | |
781 | } else if (flock(fd, LOCK_EX | LOCK_NB)) { | |
782 | RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n", | |
783 | __func__, path, strerror(errno)); | |
784 | rte_errno = EBUSY; | |
785 | goto fail; | |
786 | } | |
787 | ||
788 | /* take out a non-exclusive lock, so that other processes could | |
789 | * still attach to it, but no other process could reinitialize | |
790 | * it. | |
791 | */ | |
792 | if (flock(fd, LOCK_SH | LOCK_NB)) { | |
793 | rte_errno = errno; | |
794 | goto fail; | |
795 | } | |
796 | ||
797 | if (resize_and_map(fd, data, mmap_len)) | |
798 | goto fail; | |
11fdf7f2 | 799 | } |
9f95a23c TL |
800 | ma->addr = data; |
801 | ma->len = mmap_len; | |
802 | ma->fd = fd; | |
803 | ||
804 | /* do not close fd - keep it until detach/destroy */ | |
805 | TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next); | |
11fdf7f2 TL |
806 | |
807 | /* initialize the data */ | |
808 | memset(data, 0, mmap_len); | |
809 | ||
810 | /* populate data structure */ | |
811 | strlcpy(arr->name, name, sizeof(arr->name)); | |
812 | arr->data = data; | |
813 | arr->len = len; | |
814 | arr->elt_sz = elt_sz; | |
815 | arr->count = 0; | |
816 | ||
817 | msk = get_used_mask(data, elt_sz, len); | |
818 | msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN)); | |
819 | ||
820 | rte_rwlock_init(&arr->rwlock); | |
821 | ||
9f95a23c TL |
822 | rte_spinlock_unlock(&mem_area_lock); |
823 | ||
11fdf7f2 TL |
824 | return 0; |
825 | fail: | |
826 | if (data) | |
827 | munmap(data, mmap_len); | |
828 | if (fd >= 0) | |
829 | close(fd); | |
9f95a23c TL |
830 | free(ma); |
831 | ||
832 | rte_spinlock_unlock(&mem_area_lock); | |
11fdf7f2 TL |
833 | return -1; |
834 | } | |
835 | ||
f67539c2 | 836 | int |
11fdf7f2 TL |
837 | rte_fbarray_attach(struct rte_fbarray *arr) |
838 | { | |
9f95a23c | 839 | struct mem_area *ma = NULL, *tmp = NULL; |
11fdf7f2 TL |
840 | size_t page_sz, mmap_len; |
841 | char path[PATH_MAX]; | |
842 | void *data = NULL; | |
843 | int fd = -1; | |
844 | ||
845 | if (arr == NULL) { | |
846 | rte_errno = EINVAL; | |
847 | return -1; | |
848 | } | |
849 | ||
850 | /* | |
851 | * we don't need to synchronize attach as two values we need (element | |
852 | * size and array length) are constant for the duration of life of | |
853 | * the array, so the parts we care about will not race. | |
854 | */ | |
855 | ||
856 | if (fully_validate(arr->name, arr->elt_sz, arr->len)) | |
857 | return -1; | |
858 | ||
9f95a23c TL |
859 | ma = malloc(sizeof(*ma)); |
860 | if (ma == NULL) { | |
861 | rte_errno = ENOMEM; | |
862 | return -1; | |
863 | } | |
864 | ||
11fdf7f2 | 865 | page_sz = sysconf(_SC_PAGESIZE); |
9f95a23c TL |
866 | if (page_sz == (size_t)-1) { |
867 | free(ma); | |
868 | return -1; | |
869 | } | |
11fdf7f2 TL |
870 | |
871 | mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len); | |
872 | ||
9f95a23c TL |
873 | /* check the tailq - maybe user has already mapped this address space */ |
874 | rte_spinlock_lock(&mem_area_lock); | |
875 | ||
876 | TAILQ_FOREACH(tmp, &mem_area_tailq, next) { | |
877 | if (overlap(tmp, arr->data, mmap_len)) { | |
878 | rte_errno = EEXIST; | |
879 | goto fail; | |
880 | } | |
881 | } | |
882 | ||
883 | /* we know this memory area is unique, so proceed */ | |
884 | ||
11fdf7f2 TL |
885 | data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0); |
886 | if (data == NULL) | |
887 | goto fail; | |
888 | ||
889 | eal_get_fbarray_path(path, sizeof(path), arr->name); | |
890 | ||
891 | fd = open(path, O_RDWR); | |
892 | if (fd < 0) { | |
893 | rte_errno = errno; | |
894 | goto fail; | |
895 | } | |
896 | ||
897 | /* lock the file, to let others know we're using it */ | |
898 | if (flock(fd, LOCK_SH | LOCK_NB)) { | |
899 | rte_errno = errno; | |
900 | goto fail; | |
901 | } | |
902 | ||
903 | if (resize_and_map(fd, data, mmap_len)) | |
904 | goto fail; | |
905 | ||
9f95a23c TL |
906 | /* store our new memory area */ |
907 | ma->addr = data; | |
908 | ma->fd = fd; /* keep fd until detach/destroy */ | |
909 | ma->len = mmap_len; | |
910 | ||
911 | TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next); | |
11fdf7f2 TL |
912 | |
913 | /* we're done */ | |
914 | ||
9f95a23c | 915 | rte_spinlock_unlock(&mem_area_lock); |
11fdf7f2 TL |
916 | return 0; |
917 | fail: | |
918 | if (data) | |
919 | munmap(data, mmap_len); | |
920 | if (fd >= 0) | |
921 | close(fd); | |
9f95a23c TL |
922 | free(ma); |
923 | rte_spinlock_unlock(&mem_area_lock); | |
11fdf7f2 TL |
924 | return -1; |
925 | } | |
926 | ||
f67539c2 | 927 | int |
11fdf7f2 TL |
928 | rte_fbarray_detach(struct rte_fbarray *arr) |
929 | { | |
9f95a23c TL |
930 | struct mem_area *tmp = NULL; |
931 | size_t mmap_len; | |
932 | int ret = -1; | |
933 | ||
11fdf7f2 TL |
934 | if (arr == NULL) { |
935 | rte_errno = EINVAL; | |
936 | return -1; | |
937 | } | |
938 | ||
939 | /* | |
940 | * we don't need to synchronize detach as two values we need (element | |
941 | * size and total capacity) are constant for the duration of life of | |
942 | * the array, so the parts we care about will not race. if the user is | |
943 | * detaching while doing something else in the same process, we can't | |
944 | * really do anything about it, things will blow up either way. | |
945 | */ | |
946 | ||
947 | size_t page_sz = sysconf(_SC_PAGESIZE); | |
948 | ||
949 | if (page_sz == (size_t)-1) | |
950 | return -1; | |
951 | ||
9f95a23c | 952 | mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len); |
11fdf7f2 | 953 | |
9f95a23c TL |
954 | /* does this area exist? */ |
955 | rte_spinlock_lock(&mem_area_lock); | |
956 | ||
957 | TAILQ_FOREACH(tmp, &mem_area_tailq, next) { | |
958 | if (tmp->addr == arr->data && tmp->len == mmap_len) | |
959 | break; | |
960 | } | |
961 | if (tmp == NULL) { | |
962 | rte_errno = ENOENT; | |
963 | ret = -1; | |
964 | goto out; | |
965 | } | |
966 | ||
967 | munmap(arr->data, mmap_len); | |
968 | ||
969 | /* area is unmapped, close fd and remove the tailq entry */ | |
970 | if (tmp->fd >= 0) | |
971 | close(tmp->fd); | |
972 | TAILQ_REMOVE(&mem_area_tailq, tmp, next); | |
973 | free(tmp); | |
974 | ||
975 | ret = 0; | |
976 | out: | |
977 | rte_spinlock_unlock(&mem_area_lock); | |
978 | return ret; | |
11fdf7f2 TL |
979 | } |
980 | ||
f67539c2 | 981 | int |
11fdf7f2 TL |
982 | rte_fbarray_destroy(struct rte_fbarray *arr) |
983 | { | |
9f95a23c TL |
984 | struct mem_area *tmp = NULL; |
985 | size_t mmap_len; | |
11fdf7f2 TL |
986 | int fd, ret; |
987 | char path[PATH_MAX]; | |
988 | ||
9f95a23c TL |
989 | if (arr == NULL) { |
990 | rte_errno = EINVAL; | |
991 | return -1; | |
992 | } | |
11fdf7f2 | 993 | |
9f95a23c TL |
994 | /* |
995 | * we don't need to synchronize detach as two values we need (element | |
996 | * size and total capacity) are constant for the duration of life of | |
997 | * the array, so the parts we care about will not race. if the user is | |
998 | * detaching while doing something else in the same process, we can't | |
999 | * really do anything about it, things will blow up either way. | |
1000 | */ | |
11fdf7f2 | 1001 | |
9f95a23c | 1002 | size_t page_sz = sysconf(_SC_PAGESIZE); |
11fdf7f2 | 1003 | |
9f95a23c | 1004 | if (page_sz == (size_t)-1) |
11fdf7f2 | 1005 | return -1; |
9f95a23c TL |
1006 | |
1007 | mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len); | |
1008 | ||
1009 | /* does this area exist? */ | |
1010 | rte_spinlock_lock(&mem_area_lock); | |
1011 | ||
1012 | TAILQ_FOREACH(tmp, &mem_area_tailq, next) { | |
1013 | if (tmp->addr == arr->data && tmp->len == mmap_len) | |
1014 | break; | |
11fdf7f2 | 1015 | } |
9f95a23c TL |
1016 | if (tmp == NULL) { |
1017 | rte_errno = ENOENT; | |
11fdf7f2 | 1018 | ret = -1; |
9f95a23c | 1019 | goto out; |
11fdf7f2 | 1020 | } |
9f95a23c TL |
1021 | /* with no shconf, there were never any files to begin with */ |
1022 | if (!internal_config.no_shconf) { | |
1023 | /* | |
1024 | * attempt to get an exclusive lock on the file, to ensure it | |
1025 | * has been detached by all other processes | |
1026 | */ | |
1027 | fd = tmp->fd; | |
1028 | if (flock(fd, LOCK_EX | LOCK_NB)) { | |
1029 | RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n"); | |
1030 | rte_errno = EBUSY; | |
1031 | ret = -1; | |
1032 | goto out; | |
1033 | } | |
1034 | ||
1035 | /* we're OK to destroy the file */ | |
1036 | eal_get_fbarray_path(path, sizeof(path), arr->name); | |
1037 | if (unlink(path)) { | |
1038 | RTE_LOG(DEBUG, EAL, "Cannot unlink fbarray: %s\n", | |
1039 | strerror(errno)); | |
1040 | rte_errno = errno; | |
1041 | /* | |
1042 | * we're still holding an exclusive lock, so drop it to | |
1043 | * shared. | |
1044 | */ | |
1045 | flock(fd, LOCK_SH | LOCK_NB); | |
11fdf7f2 | 1046 | |
9f95a23c TL |
1047 | ret = -1; |
1048 | goto out; | |
1049 | } | |
1050 | close(fd); | |
1051 | } | |
1052 | munmap(arr->data, mmap_len); | |
1053 | ||
1054 | /* area is unmapped, remove the tailq entry */ | |
1055 | TAILQ_REMOVE(&mem_area_tailq, tmp, next); | |
1056 | free(tmp); | |
1057 | ret = 0; | |
f67539c2 TL |
1058 | |
1059 | /* reset the fbarray structure */ | |
1060 | memset(arr, 0, sizeof(*arr)); | |
9f95a23c TL |
1061 | out: |
1062 | rte_spinlock_unlock(&mem_area_lock); | |
11fdf7f2 TL |
1063 | return ret; |
1064 | } | |
1065 | ||
f67539c2 | 1066 | void * |
11fdf7f2 TL |
1067 | rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx) |
1068 | { | |
1069 | void *ret = NULL; | |
1070 | if (arr == NULL) { | |
1071 | rte_errno = EINVAL; | |
1072 | return NULL; | |
1073 | } | |
1074 | ||
1075 | if (idx >= arr->len) { | |
1076 | rte_errno = EINVAL; | |
1077 | return NULL; | |
1078 | } | |
1079 | ||
1080 | ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz); | |
1081 | ||
1082 | return ret; | |
1083 | } | |
1084 | ||
f67539c2 | 1085 | int |
11fdf7f2 TL |
1086 | rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx) |
1087 | { | |
1088 | return set_used(arr, idx, true); | |
1089 | } | |
1090 | ||
f67539c2 | 1091 | int |
11fdf7f2 TL |
1092 | rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx) |
1093 | { | |
1094 | return set_used(arr, idx, false); | |
1095 | } | |
1096 | ||
f67539c2 | 1097 | int |
11fdf7f2 TL |
1098 | rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx) |
1099 | { | |
1100 | struct used_mask *msk; | |
1101 | int msk_idx; | |
1102 | uint64_t msk_bit; | |
1103 | int ret = -1; | |
1104 | ||
1105 | if (arr == NULL || idx >= arr->len) { | |
1106 | rte_errno = EINVAL; | |
1107 | return -1; | |
1108 | } | |
1109 | ||
1110 | /* prevent array from changing under us */ | |
1111 | rte_rwlock_read_lock(&arr->rwlock); | |
1112 | ||
1113 | msk = get_used_mask(arr->data, arr->elt_sz, arr->len); | |
1114 | msk_idx = MASK_LEN_TO_IDX(idx); | |
1115 | msk_bit = 1ULL << MASK_LEN_TO_MOD(idx); | |
1116 | ||
1117 | ret = (msk->data[msk_idx] & msk_bit) != 0; | |
1118 | ||
1119 | rte_rwlock_read_unlock(&arr->rwlock); | |
1120 | ||
1121 | return ret; | |
1122 | } | |
1123 | ||
1124 | static int | |
1125 | fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used) | |
1126 | { | |
1127 | int ret = -1; | |
1128 | ||
1129 | if (arr == NULL || start >= arr->len) { | |
1130 | rte_errno = EINVAL; | |
1131 | return -1; | |
1132 | } | |
1133 | ||
1134 | /* prevent array from changing under us */ | |
1135 | rte_rwlock_read_lock(&arr->rwlock); | |
1136 | ||
1137 | /* cheap checks to prevent doing useless work */ | |
1138 | if (!used) { | |
1139 | if (arr->len == arr->count) { | |
1140 | rte_errno = ENOSPC; | |
1141 | goto out; | |
1142 | } | |
1143 | if (arr->count == 0) { | |
1144 | ret = start; | |
1145 | goto out; | |
1146 | } | |
1147 | } else { | |
1148 | if (arr->count == 0) { | |
1149 | rte_errno = ENOENT; | |
1150 | goto out; | |
1151 | } | |
1152 | if (arr->len == arr->count) { | |
1153 | ret = start; | |
1154 | goto out; | |
1155 | } | |
1156 | } | |
1157 | if (next) | |
1158 | ret = find_next(arr, start, used); | |
1159 | else | |
1160 | ret = find_prev(arr, start, used); | |
1161 | out: | |
1162 | rte_rwlock_read_unlock(&arr->rwlock); | |
1163 | return ret; | |
1164 | } | |
1165 | ||
f67539c2 | 1166 | int |
11fdf7f2 TL |
1167 | rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start) |
1168 | { | |
1169 | return fbarray_find(arr, start, true, false); | |
1170 | } | |
1171 | ||
f67539c2 | 1172 | int |
11fdf7f2 TL |
1173 | rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start) |
1174 | { | |
1175 | return fbarray_find(arr, start, true, true); | |
1176 | } | |
1177 | ||
f67539c2 | 1178 | int |
11fdf7f2 TL |
1179 | rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start) |
1180 | { | |
1181 | return fbarray_find(arr, start, false, false); | |
1182 | } | |
1183 | ||
f67539c2 | 1184 | int |
11fdf7f2 TL |
1185 | rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start) |
1186 | { | |
1187 | return fbarray_find(arr, start, false, true); | |
1188 | } | |
1189 | ||
1190 | static int | |
1191 | fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, | |
1192 | bool next, bool used) | |
1193 | { | |
1194 | int ret = -1; | |
1195 | ||
1196 | if (arr == NULL || start >= arr->len || n > arr->len || n == 0) { | |
1197 | rte_errno = EINVAL; | |
1198 | return -1; | |
1199 | } | |
1200 | if (next && (arr->len - start) < n) { | |
1201 | rte_errno = used ? ENOENT : ENOSPC; | |
1202 | return -1; | |
1203 | } | |
1204 | if (!next && start < (n - 1)) { | |
1205 | rte_errno = used ? ENOENT : ENOSPC; | |
1206 | return -1; | |
1207 | } | |
1208 | ||
1209 | /* prevent array from changing under us */ | |
1210 | rte_rwlock_read_lock(&arr->rwlock); | |
1211 | ||
1212 | /* cheap checks to prevent doing useless work */ | |
1213 | if (!used) { | |
1214 | if (arr->len == arr->count || arr->len - arr->count < n) { | |
1215 | rte_errno = ENOSPC; | |
1216 | goto out; | |
1217 | } | |
1218 | if (arr->count == 0) { | |
1219 | ret = next ? start : start - n + 1; | |
1220 | goto out; | |
1221 | } | |
1222 | } else { | |
1223 | if (arr->count < n) { | |
1224 | rte_errno = ENOENT; | |
1225 | goto out; | |
1226 | } | |
1227 | if (arr->count == arr->len) { | |
1228 | ret = next ? start : start - n + 1; | |
1229 | goto out; | |
1230 | } | |
1231 | } | |
1232 | ||
1233 | if (next) | |
1234 | ret = find_next_n(arr, start, n, used); | |
1235 | else | |
1236 | ret = find_prev_n(arr, start, n, used); | |
1237 | out: | |
1238 | rte_rwlock_read_unlock(&arr->rwlock); | |
1239 | return ret; | |
1240 | } | |
1241 | ||
f67539c2 | 1242 | int |
11fdf7f2 TL |
1243 | rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start, |
1244 | unsigned int n) | |
1245 | { | |
1246 | return fbarray_find_n(arr, start, n, true, false); | |
1247 | } | |
1248 | ||
f67539c2 | 1249 | int |
11fdf7f2 TL |
1250 | rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start, |
1251 | unsigned int n) | |
1252 | { | |
1253 | return fbarray_find_n(arr, start, n, true, true); | |
1254 | } | |
1255 | ||
f67539c2 | 1256 | int |
11fdf7f2 TL |
1257 | rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start, |
1258 | unsigned int n) | |
1259 | { | |
1260 | return fbarray_find_n(arr, start, n, false, false); | |
1261 | } | |
1262 | ||
f67539c2 | 1263 | int |
11fdf7f2 TL |
1264 | rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start, |
1265 | unsigned int n) | |
1266 | { | |
1267 | return fbarray_find_n(arr, start, n, false, true); | |
1268 | } | |
1269 | ||
1270 | static int | |
1271 | fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next, | |
1272 | bool used) | |
1273 | { | |
1274 | int ret = -1; | |
1275 | ||
1276 | if (arr == NULL || start >= arr->len) { | |
1277 | rte_errno = EINVAL; | |
1278 | return -1; | |
1279 | } | |
1280 | ||
1281 | /* prevent array from changing under us */ | |
1282 | rte_rwlock_read_lock(&arr->rwlock); | |
1283 | ||
1284 | /* cheap checks to prevent doing useless work */ | |
1285 | if (used) { | |
1286 | if (arr->count == 0) { | |
1287 | ret = 0; | |
1288 | goto out; | |
1289 | } | |
1290 | if (next && arr->count == arr->len) { | |
1291 | ret = arr->len - start; | |
1292 | goto out; | |
1293 | } | |
1294 | if (!next && arr->count == arr->len) { | |
1295 | ret = start + 1; | |
1296 | goto out; | |
1297 | } | |
1298 | } else { | |
1299 | if (arr->len == arr->count) { | |
1300 | ret = 0; | |
1301 | goto out; | |
1302 | } | |
1303 | if (next && arr->count == 0) { | |
1304 | ret = arr->len - start; | |
1305 | goto out; | |
1306 | } | |
1307 | if (!next && arr->count == 0) { | |
1308 | ret = start + 1; | |
1309 | goto out; | |
1310 | } | |
1311 | } | |
1312 | ||
1313 | if (next) | |
1314 | ret = find_contig(arr, start, used); | |
1315 | else | |
1316 | ret = find_rev_contig(arr, start, used); | |
1317 | out: | |
1318 | rte_rwlock_read_unlock(&arr->rwlock); | |
1319 | return ret; | |
1320 | } | |
1321 | ||
9f95a23c TL |
1322 | static int |
1323 | fbarray_find_biggest(struct rte_fbarray *arr, unsigned int start, bool used, | |
1324 | bool rev) | |
1325 | { | |
1326 | int cur_idx, next_idx, cur_len, biggest_idx, biggest_len; | |
1327 | /* don't stack if conditions, use function pointers instead */ | |
1328 | int (*find_func)(struct rte_fbarray *, unsigned int); | |
1329 | int (*find_contig_func)(struct rte_fbarray *, unsigned int); | |
1330 | ||
1331 | if (arr == NULL || start >= arr->len) { | |
1332 | rte_errno = EINVAL; | |
1333 | return -1; | |
1334 | } | |
1335 | /* the other API calls already do their fair share of cheap checks, so | |
1336 | * no need to do them here. | |
1337 | */ | |
1338 | ||
1339 | /* the API's called are thread-safe, but something may still happen | |
f67539c2 | 1340 | * between the API calls, so lock the fbarray. all other API's are |
9f95a23c TL |
1341 | * read-locking the fbarray, so read lock here is OK. |
1342 | */ | |
1343 | rte_rwlock_read_lock(&arr->rwlock); | |
1344 | ||
1345 | /* pick out appropriate functions */ | |
1346 | if (used) { | |
1347 | if (rev) { | |
1348 | find_func = rte_fbarray_find_prev_used; | |
1349 | find_contig_func = rte_fbarray_find_rev_contig_used; | |
1350 | } else { | |
1351 | find_func = rte_fbarray_find_next_used; | |
1352 | find_contig_func = rte_fbarray_find_contig_used; | |
1353 | } | |
1354 | } else { | |
1355 | if (rev) { | |
1356 | find_func = rte_fbarray_find_prev_free; | |
1357 | find_contig_func = rte_fbarray_find_rev_contig_free; | |
1358 | } else { | |
1359 | find_func = rte_fbarray_find_next_free; | |
1360 | find_contig_func = rte_fbarray_find_contig_free; | |
1361 | } | |
1362 | } | |
1363 | ||
1364 | cur_idx = start; | |
1365 | biggest_idx = -1; /* default is error */ | |
1366 | biggest_len = 0; | |
1367 | for (;;) { | |
1368 | cur_idx = find_func(arr, cur_idx); | |
1369 | ||
1370 | /* block found, check its length */ | |
1371 | if (cur_idx >= 0) { | |
1372 | cur_len = find_contig_func(arr, cur_idx); | |
1373 | /* decide where we go next */ | |
1374 | next_idx = rev ? cur_idx - cur_len : cur_idx + cur_len; | |
1375 | /* move current index to start of chunk */ | |
1376 | cur_idx = rev ? next_idx + 1 : cur_idx; | |
1377 | ||
1378 | if (cur_len > biggest_len) { | |
1379 | biggest_idx = cur_idx; | |
1380 | biggest_len = cur_len; | |
1381 | } | |
1382 | cur_idx = next_idx; | |
1383 | /* in reverse mode, next_idx may be -1 if chunk started | |
1384 | * at array beginning. this means there's no more work | |
1385 | * to do. | |
1386 | */ | |
1387 | if (cur_idx < 0) | |
1388 | break; | |
1389 | } else { | |
1390 | /* nothing more to find, stop. however, a failed API | |
1391 | * call has set rte_errno, which we want to ignore, as | |
1392 | * reaching the end of fbarray is not an error. | |
1393 | */ | |
1394 | rte_errno = 0; | |
1395 | break; | |
1396 | } | |
1397 | } | |
1398 | /* if we didn't find anything at all, set rte_errno */ | |
1399 | if (biggest_idx < 0) | |
1400 | rte_errno = used ? ENOENT : ENOSPC; | |
1401 | ||
1402 | rte_rwlock_read_unlock(&arr->rwlock); | |
1403 | return biggest_idx; | |
1404 | } | |
1405 | ||
f67539c2 | 1406 | int |
9f95a23c TL |
1407 | rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start) |
1408 | { | |
1409 | return fbarray_find_biggest(arr, start, false, false); | |
1410 | } | |
1411 | ||
f67539c2 | 1412 | int |
9f95a23c TL |
1413 | rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start) |
1414 | { | |
1415 | return fbarray_find_biggest(arr, start, true, false); | |
1416 | } | |
1417 | ||
f67539c2 | 1418 | int |
9f95a23c TL |
1419 | rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start) |
1420 | { | |
1421 | return fbarray_find_biggest(arr, start, false, true); | |
1422 | } | |
1423 | ||
f67539c2 | 1424 | int |
9f95a23c TL |
1425 | rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start) |
1426 | { | |
1427 | return fbarray_find_biggest(arr, start, true, true); | |
1428 | } | |
1429 | ||
1430 | ||
f67539c2 | 1431 | int |
11fdf7f2 TL |
1432 | rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) |
1433 | { | |
1434 | return fbarray_find_contig(arr, start, true, false); | |
1435 | } | |
1436 | ||
f67539c2 | 1437 | int |
11fdf7f2 TL |
1438 | rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start) |
1439 | { | |
1440 | return fbarray_find_contig(arr, start, true, true); | |
1441 | } | |
1442 | ||
f67539c2 | 1443 | int |
11fdf7f2 TL |
1444 | rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start) |
1445 | { | |
1446 | return fbarray_find_contig(arr, start, false, false); | |
1447 | } | |
1448 | ||
f67539c2 | 1449 | int |
11fdf7f2 TL |
1450 | rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start) |
1451 | { | |
1452 | return fbarray_find_contig(arr, start, false, true); | |
1453 | } | |
1454 | ||
f67539c2 | 1455 | int |
11fdf7f2 TL |
1456 | rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt) |
1457 | { | |
1458 | void *end; | |
1459 | int ret = -1; | |
1460 | ||
1461 | /* | |
1462 | * no need to synchronize as it doesn't matter if underlying data | |
1463 | * changes - we're doing pointer arithmetic here. | |
1464 | */ | |
1465 | ||
1466 | if (arr == NULL || elt == NULL) { | |
1467 | rte_errno = EINVAL; | |
1468 | return -1; | |
1469 | } | |
1470 | end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len); | |
1471 | if (elt < arr->data || elt >= end) { | |
1472 | rte_errno = EINVAL; | |
1473 | return -1; | |
1474 | } | |
1475 | ||
1476 | ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz; | |
1477 | ||
1478 | return ret; | |
1479 | } | |
1480 | ||
f67539c2 | 1481 | void |
11fdf7f2 TL |
1482 | rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f) |
1483 | { | |
1484 | struct used_mask *msk; | |
1485 | unsigned int i; | |
1486 | ||
1487 | if (arr == NULL || f == NULL) { | |
1488 | rte_errno = EINVAL; | |
1489 | return; | |
1490 | } | |
1491 | ||
1492 | if (fully_validate(arr->name, arr->elt_sz, arr->len)) { | |
1493 | fprintf(f, "Invalid file-backed array\n"); | |
1494 | goto out; | |
1495 | } | |
1496 | ||
1497 | /* prevent array from changing under us */ | |
1498 | rte_rwlock_read_lock(&arr->rwlock); | |
1499 | ||
1500 | fprintf(f, "File-backed array: %s\n", arr->name); | |
1501 | fprintf(f, "size: %i occupied: %i elt_sz: %i\n", | |
1502 | arr->len, arr->count, arr->elt_sz); | |
1503 | ||
1504 | msk = get_used_mask(arr->data, arr->elt_sz, arr->len); | |
1505 | ||
1506 | for (i = 0; i < msk->n_masks; i++) | |
1507 | fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]); | |
1508 | out: | |
1509 | rte_rwlock_read_unlock(&arr->rwlock); | |
1510 | } |