1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * random utiility code, for bcache but in theory not specific to bcache |
4 | * |
5 | * Copyright 2010, 2011 Kent Overstreet <kent.overstreet@gmail.com> |
6 | * Copyright 2012 Google, Inc. |
7 | */ |
8 | |
9 | #include <linux/bio.h> |
10 | #include <linux/blkdev.h> |
11 | #include <linux/console.h> |
12 | #include <linux/ctype.h> |
13 | #include <linux/debugfs.h> |
14 | #include <linux/freezer.h> |
15 | #include <linux/kthread.h> |
16 | #include <linux/log2.h> |
17 | #include <linux/math64.h> |
18 | #include <linux/percpu.h> |
19 | #include <linux/preempt.h> |
20 | #include <linux/random.h> |
21 | #include <linux/seq_file.h> |
22 | #include <linux/string.h> |
23 | #include <linux/types.h> |
24 | #include <linux/sched/clock.h> |
25 | |
26 | #include "eytzinger.h" |
27 | #include "mean_and_variance.h" |
28 | #include "util.h" |
29 | |
30 | static const char si_units[] = "?kMGTPEZY" ; |
31 | |
32 | /* string_get_size units: */ |
33 | static const char *const units_2[] = { |
34 | "B" , "KiB" , "MiB" , "GiB" , "TiB" , "PiB" , "EiB" , "ZiB" , "YiB" |
35 | }; |
36 | static const char *const units_10[] = { |
37 | "B" , "kB" , "MB" , "GB" , "TB" , "PB" , "EB" , "ZB" , "YB" |
38 | }; |
39 | |
40 | static int parse_u64(const char *cp, u64 *res) |
41 | { |
42 | const char *start = cp; |
43 | u64 v = 0; |
44 | |
45 | if (!isdigit(c: *cp)) |
46 | return -EINVAL; |
47 | |
48 | do { |
49 | if (v > U64_MAX / 10) |
50 | return -ERANGE; |
51 | v *= 10; |
52 | if (v > U64_MAX - (*cp - '0')) |
53 | return -ERANGE; |
54 | v += *cp - '0'; |
55 | cp++; |
56 | } while (isdigit(c: *cp)); |
57 | |
58 | *res = v; |
59 | return cp - start; |
60 | } |
61 | |
62 | static int bch2_pow(u64 n, u64 p, u64 *res) |
63 | { |
64 | *res = 1; |
65 | |
66 | while (p--) { |
67 | if (*res > div_u64(U64_MAX, divisor: n)) |
68 | return -ERANGE; |
69 | *res *= n; |
70 | } |
71 | return 0; |
72 | } |
73 | |
74 | static int parse_unit_suffix(const char *cp, u64 *res) |
75 | { |
76 | const char *start = cp; |
77 | u64 base = 1024; |
78 | unsigned u; |
79 | int ret; |
80 | |
81 | if (*cp == ' ') |
82 | cp++; |
83 | |
84 | for (u = 1; u < strlen(si_units); u++) |
85 | if (*cp == si_units[u]) { |
86 | cp++; |
87 | goto got_unit; |
88 | } |
89 | |
90 | for (u = 0; u < ARRAY_SIZE(units_2); u++) |
91 | if (!strncmp(cp, units_2[u], strlen(units_2[u]))) { |
92 | cp += strlen(units_2[u]); |
93 | goto got_unit; |
94 | } |
95 | |
96 | for (u = 0; u < ARRAY_SIZE(units_10); u++) |
97 | if (!strncmp(cp, units_10[u], strlen(units_10[u]))) { |
98 | cp += strlen(units_10[u]); |
99 | base = 1000; |
100 | goto got_unit; |
101 | } |
102 | |
103 | *res = 1; |
104 | return 0; |
105 | got_unit: |
106 | ret = bch2_pow(n: base, p: u, res); |
107 | if (ret) |
108 | return ret; |
109 | |
110 | return cp - start; |
111 | } |
112 | |
113 | #define parse_or_ret(cp, _f) \ |
114 | do { \ |
115 | int _ret = _f; \ |
116 | if (_ret < 0) \ |
117 | return _ret; \ |
118 | cp += _ret; \ |
119 | } while (0) |
120 | |
121 | static int __bch2_strtou64_h(const char *cp, u64 *res) |
122 | { |
123 | const char *start = cp; |
124 | u64 v = 0, b, f_n = 0, f_d = 1; |
125 | int ret; |
126 | |
127 | parse_or_ret(cp, parse_u64(cp, &v)); |
128 | |
129 | if (*cp == '.') { |
130 | cp++; |
131 | ret = parse_u64(cp, res: &f_n); |
132 | if (ret < 0) |
133 | return ret; |
134 | cp += ret; |
135 | |
136 | ret = bch2_pow(n: 10, p: ret, res: &f_d); |
137 | if (ret) |
138 | return ret; |
139 | } |
140 | |
141 | parse_or_ret(cp, parse_unit_suffix(cp, &b)); |
142 | |
143 | if (v > div_u64(U64_MAX, divisor: b)) |
144 | return -ERANGE; |
145 | v *= b; |
146 | |
147 | if (f_n > div_u64(U64_MAX, divisor: b)) |
148 | return -ERANGE; |
149 | |
150 | f_n = div_u64(dividend: f_n * b, divisor: f_d); |
151 | if (v + f_n < v) |
152 | return -ERANGE; |
153 | v += f_n; |
154 | |
155 | *res = v; |
156 | return cp - start; |
157 | } |
158 | |
159 | static int __bch2_strtoh(const char *cp, u64 *res, |
160 | u64 t_max, bool t_signed) |
161 | { |
162 | bool positive = *cp != '-'; |
163 | u64 v = 0; |
164 | |
165 | if (*cp == '+' || *cp == '-') |
166 | cp++; |
167 | |
168 | parse_or_ret(cp, __bch2_strtou64_h(cp, &v)); |
169 | |
170 | if (*cp == '\n') |
171 | cp++; |
172 | if (*cp) |
173 | return -EINVAL; |
174 | |
175 | if (positive) { |
176 | if (v > t_max) |
177 | return -ERANGE; |
178 | } else { |
179 | if (v && !t_signed) |
180 | return -ERANGE; |
181 | |
182 | if (v > t_max + 1) |
183 | return -ERANGE; |
184 | v = -v; |
185 | } |
186 | |
187 | *res = v; |
188 | return 0; |
189 | } |
190 | |
191 | #define STRTO_H(name, type) \ |
192 | int bch2_ ## name ## _h(const char *cp, type *res) \ |
193 | { \ |
194 | u64 v = 0; \ |
195 | int ret = __bch2_strtoh(cp, &v, ANYSINT_MAX(type), \ |
196 | ANYSINT_MAX(type) != ((type) ~0ULL)); \ |
197 | *res = v; \ |
198 | return ret; \ |
199 | } |
200 | |
201 | STRTO_H(strtoint, int) |
202 | STRTO_H(strtouint, unsigned int) |
203 | STRTO_H(strtoll, long long) |
204 | STRTO_H(strtoull, unsigned long long) |
205 | STRTO_H(strtou64, u64) |
206 | |
207 | u64 bch2_read_flag_list(char *opt, const char * const list[]) |
208 | { |
209 | u64 ret = 0; |
210 | char *p, *s, *d = kstrdup(s: opt, GFP_KERNEL); |
211 | |
212 | if (!d) |
213 | return -ENOMEM; |
214 | |
215 | s = strim(d); |
216 | |
217 | while ((p = strsep(&s, "," ))) { |
218 | int flag = match_string(array: list, n: -1, string: p); |
219 | |
220 | if (flag < 0) { |
221 | ret = -1; |
222 | break; |
223 | } |
224 | |
225 | ret |= 1 << flag; |
226 | } |
227 | |
228 | kfree(objp: d); |
229 | |
230 | return ret; |
231 | } |
232 | |
233 | bool bch2_is_zero(const void *_p, size_t n) |
234 | { |
235 | const char *p = _p; |
236 | size_t i; |
237 | |
238 | for (i = 0; i < n; i++) |
239 | if (p[i]) |
240 | return false; |
241 | return true; |
242 | } |
243 | |
244 | void bch2_prt_u64_base2_nbits(struct printbuf *out, u64 v, unsigned nr_bits) |
245 | { |
246 | while (nr_bits) |
247 | prt_char(out, c: '0' + ((v >> --nr_bits) & 1)); |
248 | } |
249 | |
250 | void bch2_prt_u64_base2(struct printbuf *out, u64 v) |
251 | { |
252 | bch2_prt_u64_base2_nbits(out, v, nr_bits: fls64(x: v) ?: 1); |
253 | } |
254 | |
255 | void bch2_print_string_as_lines(const char *prefix, const char *lines) |
256 | { |
257 | const char *p; |
258 | |
259 | if (!lines) { |
260 | printk("%s (null)\n" , prefix); |
261 | return; |
262 | } |
263 | |
264 | console_lock(); |
265 | while (1) { |
266 | p = strchrnul(lines, '\n'); |
267 | printk("%s%.*s\n" , prefix, (int) (p - lines), lines); |
268 | if (!*p) |
269 | break; |
270 | lines = p + 1; |
271 | } |
272 | console_unlock(); |
273 | } |
274 | |
275 | int bch2_save_backtrace(bch_stacktrace *stack, struct task_struct *task, unsigned skipnr, |
276 | gfp_t gfp) |
277 | { |
278 | #ifdef CONFIG_STACKTRACE |
279 | unsigned nr_entries = 0; |
280 | |
281 | stack->nr = 0; |
282 | int ret = darray_make_room_gfp(stack, 32, gfp); |
283 | if (ret) |
284 | return ret; |
285 | |
286 | if (!down_read_trylock(sem: &task->signal->exec_update_lock)) |
287 | return -1; |
288 | |
289 | do { |
290 | nr_entries = stack_trace_save_tsk(task, store: stack->data, size: stack->size, skipnr: skipnr + 1); |
291 | } while (nr_entries == stack->size && |
292 | !(ret = darray_make_room_gfp(stack, stack->size * 2, gfp))); |
293 | |
294 | stack->nr = nr_entries; |
295 | up_read(sem: &task->signal->exec_update_lock); |
296 | |
297 | return ret; |
298 | #else |
299 | return 0; |
300 | #endif |
301 | } |
302 | |
303 | void bch2_prt_backtrace(struct printbuf *out, bch_stacktrace *stack) |
304 | { |
305 | darray_for_each(*stack, i) { |
306 | prt_printf(out, "[<0>] %pB" , (void *) *i); |
307 | prt_newline(out); |
308 | } |
309 | } |
310 | |
311 | int bch2_prt_task_backtrace(struct printbuf *out, struct task_struct *task, unsigned skipnr, gfp_t gfp) |
312 | { |
313 | bch_stacktrace stack = { 0 }; |
314 | int ret = bch2_save_backtrace(stack: &stack, task, skipnr: skipnr + 1, gfp); |
315 | |
316 | bch2_prt_backtrace(out, stack: &stack); |
317 | darray_exit(&stack); |
318 | return ret; |
319 | } |
320 | |
321 | #ifndef __KERNEL__ |
322 | #include <time.h> |
323 | void bch2_prt_datetime(struct printbuf *out, time64_t sec) |
324 | { |
325 | time_t t = sec; |
326 | char buf[64]; |
327 | ctime_r(&t, buf); |
328 | strim(buf); |
329 | prt_str(out, buf); |
330 | } |
331 | #else |
332 | void bch2_prt_datetime(struct printbuf *out, time64_t sec) |
333 | { |
334 | char buf[64]; |
335 | snprintf(buf, size: sizeof(buf), fmt: "%ptT" , &sec); |
336 | prt_u64(out, sec); |
337 | } |
338 | #endif |
339 | |
340 | void bch2_pr_time_units(struct printbuf *out, u64 ns) |
341 | { |
342 | const struct time_unit *u = bch2_pick_time_units(ns); |
343 | |
344 | prt_printf(out, "%llu %s" , div_u64(ns, u->nsecs), u->name); |
345 | } |
346 | |
347 | static void bch2_pr_time_units_aligned(struct printbuf *out, u64 ns) |
348 | { |
349 | const struct time_unit *u = bch2_pick_time_units(ns); |
350 | |
351 | prt_printf(out, "%llu " , div64_u64(ns, u->nsecs)); |
352 | prt_tab_rjust(out); |
353 | prt_printf(out, "%s" , u->name); |
354 | } |
355 | |
356 | static inline void pr_name_and_units(struct printbuf *out, const char *name, u64 ns) |
357 | { |
358 | prt_str(out, str: name); |
359 | prt_tab(out); |
360 | bch2_pr_time_units_aligned(out, ns); |
361 | prt_newline(out); |
362 | } |
363 | |
364 | #define TABSTOP_SIZE 12 |
365 | |
366 | void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) |
367 | { |
368 | struct quantiles *quantiles = time_stats_to_quantiles(stats); |
369 | s64 f_mean = 0, d_mean = 0; |
370 | u64 f_stddev = 0, d_stddev = 0; |
371 | |
372 | if (stats->buffer) { |
373 | int cpu; |
374 | |
375 | spin_lock_irq(lock: &stats->lock); |
376 | for_each_possible_cpu(cpu) |
377 | __bch2_time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu)); |
378 | spin_unlock_irq(lock: &stats->lock); |
379 | } |
380 | |
381 | /* |
382 | * avoid divide by zero |
383 | */ |
384 | if (stats->freq_stats.n) { |
385 | f_mean = mean_and_variance_get_mean(s: stats->freq_stats); |
386 | f_stddev = mean_and_variance_get_stddev(s: stats->freq_stats); |
387 | d_mean = mean_and_variance_get_mean(s: stats->duration_stats); |
388 | d_stddev = mean_and_variance_get_stddev(s: stats->duration_stats); |
389 | } |
390 | |
391 | printbuf_tabstop_push(out, out->indent + TABSTOP_SIZE); |
392 | prt_printf(out, "count:" ); |
393 | prt_tab(out); |
394 | prt_printf(out, "%llu " , |
395 | stats->duration_stats.n); |
396 | printbuf_tabstop_pop(out); |
397 | prt_newline(out); |
398 | |
399 | printbuf_tabstops_reset(out); |
400 | |
401 | printbuf_tabstop_push(out, out->indent + 20); |
402 | printbuf_tabstop_push(out, TABSTOP_SIZE + 2); |
403 | printbuf_tabstop_push(out, 0); |
404 | printbuf_tabstop_push(out, TABSTOP_SIZE + 2); |
405 | |
406 | prt_tab(out); |
407 | prt_printf(out, "since mount" ); |
408 | prt_tab_rjust(out); |
409 | prt_tab(out); |
410 | prt_printf(out, "recent" ); |
411 | prt_tab_rjust(out); |
412 | prt_newline(out); |
413 | |
414 | printbuf_tabstops_reset(out); |
415 | printbuf_tabstop_push(out, out->indent + 20); |
416 | printbuf_tabstop_push(out, TABSTOP_SIZE); |
417 | printbuf_tabstop_push(out, 2); |
418 | printbuf_tabstop_push(out, TABSTOP_SIZE); |
419 | |
420 | prt_printf(out, "duration of events" ); |
421 | prt_newline(out); |
422 | printbuf_indent_add(out, 2); |
423 | |
424 | pr_name_and_units(out, name: "min:" , ns: stats->min_duration); |
425 | pr_name_and_units(out, name: "max:" , ns: stats->max_duration); |
426 | pr_name_and_units(out, name: "total:" , ns: stats->total_duration); |
427 | |
428 | prt_printf(out, "mean:" ); |
429 | prt_tab(out); |
430 | bch2_pr_time_units_aligned(out, ns: d_mean); |
431 | prt_tab(out); |
432 | bch2_pr_time_units_aligned(out, ns: mean_and_variance_weighted_get_mean(s: stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); |
433 | prt_newline(out); |
434 | |
435 | prt_printf(out, "stddev:" ); |
436 | prt_tab(out); |
437 | bch2_pr_time_units_aligned(out, ns: d_stddev); |
438 | prt_tab(out); |
439 | bch2_pr_time_units_aligned(out, ns: mean_and_variance_weighted_get_stddev(s: stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); |
440 | |
441 | printbuf_indent_sub(out, 2); |
442 | prt_newline(out); |
443 | |
444 | prt_printf(out, "time between events" ); |
445 | prt_newline(out); |
446 | printbuf_indent_add(out, 2); |
447 | |
448 | pr_name_and_units(out, name: "min:" , ns: stats->min_freq); |
449 | pr_name_and_units(out, name: "max:" , ns: stats->max_freq); |
450 | |
451 | prt_printf(out, "mean:" ); |
452 | prt_tab(out); |
453 | bch2_pr_time_units_aligned(out, ns: f_mean); |
454 | prt_tab(out); |
455 | bch2_pr_time_units_aligned(out, ns: mean_and_variance_weighted_get_mean(s: stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); |
456 | prt_newline(out); |
457 | |
458 | prt_printf(out, "stddev:" ); |
459 | prt_tab(out); |
460 | bch2_pr_time_units_aligned(out, ns: f_stddev); |
461 | prt_tab(out); |
462 | bch2_pr_time_units_aligned(out, ns: mean_and_variance_weighted_get_stddev(s: stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); |
463 | |
464 | printbuf_indent_sub(out, 2); |
465 | prt_newline(out); |
466 | |
467 | printbuf_tabstops_reset(out); |
468 | |
469 | if (quantiles) { |
470 | int i = eytzinger0_first(NR_QUANTILES); |
471 | const struct time_unit *u = |
472 | bch2_pick_time_units(ns: quantiles->entries[i].m); |
473 | u64 last_q = 0; |
474 | |
475 | prt_printf(out, "quantiles (%s):\t" , u->name); |
476 | eytzinger0_for_each(i, NR_QUANTILES) { |
477 | bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1; |
478 | |
479 | u64 q = max(quantiles->entries[i].m, last_q); |
480 | prt_printf(out, "%llu " , div_u64(q, u->nsecs)); |
481 | if (is_last) |
482 | prt_newline(out); |
483 | last_q = q; |
484 | } |
485 | } |
486 | } |
487 | |
488 | /* ratelimit: */ |
489 | |
490 | /** |
491 | * bch2_ratelimit_delay() - return how long to delay until the next time to do |
492 | * some work |
493 | * @d: the struct bch_ratelimit to update |
494 | * Returns: the amount of time to delay by, in jiffies |
495 | */ |
496 | u64 bch2_ratelimit_delay(struct bch_ratelimit *d) |
497 | { |
498 | u64 now = local_clock(); |
499 | |
500 | return time_after64(d->next, now) |
501 | ? nsecs_to_jiffies(n: d->next - now) |
502 | : 0; |
503 | } |
504 | |
505 | /** |
506 | * bch2_ratelimit_increment() - increment @d by the amount of work done |
507 | * @d: the struct bch_ratelimit to update |
508 | * @done: the amount of work done, in arbitrary units |
509 | */ |
510 | void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done) |
511 | { |
512 | u64 now = local_clock(); |
513 | |
514 | d->next += div_u64(dividend: done * NSEC_PER_SEC, divisor: d->rate); |
515 | |
516 | if (time_before64(now + NSEC_PER_SEC, d->next)) |
517 | d->next = now + NSEC_PER_SEC; |
518 | |
519 | if (time_after64(now - NSEC_PER_SEC * 2, d->next)) |
520 | d->next = now - NSEC_PER_SEC * 2; |
521 | } |
522 | |
523 | /* pd controller: */ |
524 | |
525 | /* |
526 | * Updates pd_controller. Attempts to scale inputed values to units per second. |
527 | * @target: desired value |
528 | * @actual: current value |
529 | * |
530 | * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing |
531 | * it makes actual go down. |
532 | */ |
533 | void bch2_pd_controller_update(struct bch_pd_controller *pd, |
534 | s64 target, s64 actual, int sign) |
535 | { |
536 | s64 proportional, derivative, change; |
537 | |
538 | unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ; |
539 | |
540 | if (seconds_since_update == 0) |
541 | return; |
542 | |
543 | pd->last_update = jiffies; |
544 | |
545 | proportional = actual - target; |
546 | proportional *= seconds_since_update; |
547 | proportional = div_s64(dividend: proportional, divisor: pd->p_term_inverse); |
548 | |
549 | derivative = actual - pd->last_actual; |
550 | derivative = div_s64(dividend: derivative, divisor: seconds_since_update); |
551 | derivative = ewma_add(pd->smoothed_derivative, derivative, |
552 | (pd->d_term / seconds_since_update) ?: 1); |
553 | derivative = derivative * pd->d_term; |
554 | derivative = div_s64(dividend: derivative, divisor: pd->p_term_inverse); |
555 | |
556 | change = proportional + derivative; |
557 | |
558 | /* Don't increase rate if not keeping up */ |
559 | if (change > 0 && |
560 | pd->backpressure && |
561 | time_after64(local_clock(), |
562 | pd->rate.next + NSEC_PER_MSEC)) |
563 | change = 0; |
564 | |
565 | change *= (sign * -1); |
566 | |
567 | pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change, |
568 | 1, UINT_MAX); |
569 | |
570 | pd->last_actual = actual; |
571 | pd->last_derivative = derivative; |
572 | pd->last_proportional = proportional; |
573 | pd->last_change = change; |
574 | pd->last_target = target; |
575 | } |
576 | |
577 | void bch2_pd_controller_init(struct bch_pd_controller *pd) |
578 | { |
579 | pd->rate.rate = 1024; |
580 | pd->last_update = jiffies; |
581 | pd->p_term_inverse = 6000; |
582 | pd->d_term = 30; |
583 | pd->d_smooth = pd->d_term; |
584 | pd->backpressure = 1; |
585 | } |
586 | |
587 | void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd) |
588 | { |
589 | if (!out->nr_tabstops) |
590 | printbuf_tabstop_push(out, 20); |
591 | |
592 | prt_printf(out, "rate:" ); |
593 | prt_tab(out); |
594 | prt_human_readable_s64(out, pd->rate.rate); |
595 | prt_newline(out); |
596 | |
597 | prt_printf(out, "target:" ); |
598 | prt_tab(out); |
599 | prt_human_readable_u64(out, pd->last_target); |
600 | prt_newline(out); |
601 | |
602 | prt_printf(out, "actual:" ); |
603 | prt_tab(out); |
604 | prt_human_readable_u64(out, pd->last_actual); |
605 | prt_newline(out); |
606 | |
607 | prt_printf(out, "proportional:" ); |
608 | prt_tab(out); |
609 | prt_human_readable_s64(out, pd->last_proportional); |
610 | prt_newline(out); |
611 | |
612 | prt_printf(out, "derivative:" ); |
613 | prt_tab(out); |
614 | prt_human_readable_s64(out, pd->last_derivative); |
615 | prt_newline(out); |
616 | |
617 | prt_printf(out, "change:" ); |
618 | prt_tab(out); |
619 | prt_human_readable_s64(out, pd->last_change); |
620 | prt_newline(out); |
621 | |
622 | prt_printf(out, "next io:" ); |
623 | prt_tab(out); |
624 | prt_printf(out, "%llims" , div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC)); |
625 | prt_newline(out); |
626 | } |
627 | |
628 | /* misc: */ |
629 | |
630 | void bch2_bio_map(struct bio *bio, void *base, size_t size) |
631 | { |
632 | while (size) { |
633 | struct page *page = is_vmalloc_addr(x: base) |
634 | ? vmalloc_to_page(addr: base) |
635 | : virt_to_page(base); |
636 | unsigned offset = offset_in_page(base); |
637 | unsigned len = min_t(size_t, PAGE_SIZE - offset, size); |
638 | |
639 | BUG_ON(!bio_add_page(bio, page, len, offset)); |
640 | size -= len; |
641 | base += len; |
642 | } |
643 | } |
644 | |
645 | int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask) |
646 | { |
647 | while (size) { |
648 | struct page *page = alloc_pages(gfp: gfp_mask, order: 0); |
649 | unsigned len = min_t(size_t, PAGE_SIZE, size); |
650 | |
651 | if (!page) |
652 | return -ENOMEM; |
653 | |
654 | if (unlikely(!bio_add_page(bio, page, len, 0))) { |
655 | __free_page(page); |
656 | break; |
657 | } |
658 | |
659 | size -= len; |
660 | } |
661 | |
662 | return 0; |
663 | } |
664 | |
665 | size_t bch2_rand_range(size_t max) |
666 | { |
667 | size_t rand; |
668 | |
669 | if (!max) |
670 | return 0; |
671 | |
672 | do { |
673 | rand = get_random_long(); |
674 | rand &= roundup_pow_of_two(max) - 1; |
675 | } while (rand >= max); |
676 | |
677 | return rand; |
678 | } |
679 | |
680 | void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) |
681 | { |
682 | struct bio_vec bv; |
683 | struct bvec_iter iter; |
684 | |
685 | __bio_for_each_segment(bv, dst, iter, dst_iter) { |
686 | void *dstp = kmap_local_page(page: bv.bv_page); |
687 | |
688 | memcpy(dstp + bv.bv_offset, src, bv.bv_len); |
689 | kunmap_local(dstp); |
690 | |
691 | src += bv.bv_len; |
692 | } |
693 | } |
694 | |
695 | void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) |
696 | { |
697 | struct bio_vec bv; |
698 | struct bvec_iter iter; |
699 | |
700 | __bio_for_each_segment(bv, src, iter, src_iter) { |
701 | void *srcp = kmap_local_page(page: bv.bv_page); |
702 | |
703 | memcpy(dst, srcp + bv.bv_offset, bv.bv_len); |
704 | kunmap_local(srcp); |
705 | |
706 | dst += bv.bv_len; |
707 | } |
708 | } |
709 | |
710 | #if 0 |
711 | void eytzinger1_test(void) |
712 | { |
713 | unsigned inorder, eytz, size; |
714 | |
715 | pr_info("1 based eytzinger test:" ); |
716 | |
717 | for (size = 2; |
718 | size < 65536; |
719 | size++) { |
720 | unsigned extra = eytzinger1_extra(size); |
721 | |
722 | if (!(size % 4096)) |
723 | pr_info("tree size %u" , size); |
724 | |
725 | BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); |
726 | BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); |
727 | |
728 | BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); |
729 | BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); |
730 | |
731 | inorder = 1; |
732 | eytzinger1_for_each(eytz, size) { |
733 | BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); |
734 | BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder); |
735 | BUG_ON(eytz != eytzinger1_last(size) && |
736 | eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz); |
737 | |
738 | inorder++; |
739 | } |
740 | } |
741 | } |
742 | |
743 | void eytzinger0_test(void) |
744 | { |
745 | |
746 | unsigned inorder, eytz, size; |
747 | |
748 | pr_info("0 based eytzinger test:" ); |
749 | |
750 | for (size = 1; |
751 | size < 65536; |
752 | size++) { |
753 | unsigned extra = eytzinger0_extra(size); |
754 | |
755 | if (!(size % 4096)) |
756 | pr_info("tree size %u" , size); |
757 | |
758 | BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); |
759 | BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); |
760 | |
761 | BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); |
762 | BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); |
763 | |
764 | inorder = 0; |
765 | eytzinger0_for_each(eytz, size) { |
766 | BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz); |
767 | BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder); |
768 | BUG_ON(eytz != eytzinger0_last(size) && |
769 | eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz); |
770 | |
771 | inorder++; |
772 | } |
773 | } |
774 | } |
775 | |
776 | static inline int cmp_u16(const void *_l, const void *_r, size_t size) |
777 | { |
778 | const u16 *l = _l, *r = _r; |
779 | |
780 | return (*l > *r) - (*r - *l); |
781 | } |
782 | |
783 | static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) |
784 | { |
785 | int i, c1 = -1, c2 = -1; |
786 | ssize_t r; |
787 | |
788 | r = eytzinger0_find_le(test_array, nr, |
789 | sizeof(test_array[0]), |
790 | cmp_u16, &search); |
791 | if (r >= 0) |
792 | c1 = test_array[r]; |
793 | |
794 | for (i = 0; i < nr; i++) |
795 | if (test_array[i] <= search && test_array[i] > c2) |
796 | c2 = test_array[i]; |
797 | |
798 | if (c1 != c2) { |
799 | eytzinger0_for_each(i, nr) |
800 | pr_info("[%3u] = %12u" , i, test_array[i]); |
801 | pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i" , |
802 | i, r, c1, c2); |
803 | } |
804 | } |
805 | |
806 | void eytzinger0_find_test(void) |
807 | { |
808 | unsigned i, nr, allocated = 1 << 12; |
809 | u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); |
810 | |
811 | for (nr = 1; nr < allocated; nr++) { |
812 | pr_info("testing %u elems" , nr); |
813 | |
814 | get_random_bytes(test_array, nr * sizeof(test_array[0])); |
815 | eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); |
816 | |
817 | /* verify array is sorted correctly: */ |
818 | eytzinger0_for_each(i, nr) |
819 | BUG_ON(i != eytzinger0_last(nr) && |
820 | test_array[i] > test_array[eytzinger0_next(i, nr)]); |
821 | |
822 | for (i = 0; i < U16_MAX; i += 1 << 12) |
823 | eytzinger0_find_test_val(test_array, nr, i); |
824 | |
825 | for (i = 0; i < nr; i++) { |
826 | eytzinger0_find_test_val(test_array, nr, test_array[i] - 1); |
827 | eytzinger0_find_test_val(test_array, nr, test_array[i]); |
828 | eytzinger0_find_test_val(test_array, nr, test_array[i] + 1); |
829 | } |
830 | } |
831 | |
832 | kfree(test_array); |
833 | } |
834 | #endif |
835 | |
836 | /* |
837 | * Accumulate percpu counters onto one cpu's copy - only valid when access |
838 | * against any percpu counter is guarded against |
839 | */ |
840 | u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr) |
841 | { |
842 | u64 *ret; |
843 | int cpu; |
844 | |
845 | /* access to pcpu vars has to be blocked by other locking */ |
846 | preempt_disable(); |
847 | ret = this_cpu_ptr(p); |
848 | preempt_enable(); |
849 | |
850 | for_each_possible_cpu(cpu) { |
851 | u64 *i = per_cpu_ptr(p, cpu); |
852 | |
853 | if (i != ret) { |
854 | acc_u64s(acc: ret, src: i, nr); |
855 | memset(i, 0, nr * sizeof(u64)); |
856 | } |
857 | } |
858 | |
859 | return ret; |
860 | } |
861 | |
862 | void bch2_darray_str_exit(darray_str *d) |
863 | { |
864 | darray_for_each(*d, i) |
865 | kfree(objp: *i); |
866 | darray_exit(d); |
867 | } |
868 | |
869 | int bch2_split_devs(const char *_dev_name, darray_str *ret) |
870 | { |
871 | darray_init(ret); |
872 | |
873 | char *dev_name, *s, *orig; |
874 | |
875 | dev_name = orig = kstrdup(s: _dev_name, GFP_KERNEL); |
876 | if (!dev_name) |
877 | return -ENOMEM; |
878 | |
879 | while ((s = strsep(&dev_name, ":" ))) { |
880 | char *p = kstrdup(s, GFP_KERNEL); |
881 | if (!p) |
882 | goto err; |
883 | |
884 | if (darray_push(ret, p)) { |
885 | kfree(objp: p); |
886 | goto err; |
887 | } |
888 | } |
889 | |
890 | kfree(objp: orig); |
891 | return 0; |
892 | err: |
893 | bch2_darray_str_exit(d: ret); |
894 | kfree(objp: orig); |
895 | return -ENOMEM; |
896 | } |
897 | |