Commit | Line | Data |
---|---|---|
1c6fdbd8 KO |
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> | |
a8f35428 | 11 | #include <linux/console.h> |
1c6fdbd8 KO |
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" | |
bf8f8b20 | 27 | #include "mean_and_variance.h" |
1c6fdbd8 KO |
28 | #include "util.h" |
29 | ||
1c6fdbd8 KO |
30 | static const char si_units[] = "?kMGTPEZY"; |
31 | ||
a5d18f9e KO |
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) | |
1c6fdbd8 | 41 | { |
a5d18f9e | 42 | const char *start = cp; |
1c6fdbd8 KO |
43 | u64 v = 0; |
44 | ||
1c6fdbd8 KO |
45 | if (!isdigit(*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(*cp)); | |
57 | ||
a5d18f9e KO |
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, 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 | ||
1c6fdbd8 KO |
84 | for (u = 1; u < strlen(si_units); u++) |
85 | if (*cp == si_units[u]) { | |
86 | cp++; | |
87 | goto got_unit; | |
88 | } | |
a5d18f9e KO |
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; | |
1c6fdbd8 | 105 | got_unit: |
a5d18f9e KO |
106 | ret = bch2_pow(base, u, res); |
107 | if (ret) | |
108 | return ret; | |
109 | ||
110 | return cp - start; | |
111 | } | |
112 | ||
113 | #define parse_or_ret(cp, _f) \ | |
114 | do { \ | |
96dea3d5 KO |
115 | int _ret = _f; \ |
116 | if (_ret < 0) \ | |
117 | return _ret; \ | |
118 | cp += _ret; \ | |
a5d18f9e KO |
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 == '.') { | |
1c6fdbd8 | 130 | cp++; |
a5d18f9e KO |
131 | ret = parse_u64(cp, &f_n); |
132 | if (ret < 0) | |
133 | return ret; | |
134 | cp += ret; | |
1c6fdbd8 | 135 | |
a5d18f9e KO |
136 | ret = bch2_pow(10, ret, &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, b)) | |
144 | return -ERANGE; | |
145 | v *= b; | |
146 | ||
147 | if (f_n > div_u64(U64_MAX, b)) | |
148 | return -ERANGE; | |
149 | ||
150 | f_n = div_u64(f_n * b, f_d); | |
151 | if (v + f_n < v) | |
1c6fdbd8 | 152 | return -ERANGE; |
a5d18f9e KO |
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; | |
1c6fdbd8 | 164 | |
a5d18f9e KO |
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; | |
1c6fdbd8 KO |
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 | { \ | |
a5d18f9e | 194 | u64 v = 0; \ |
1c6fdbd8 KO |
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) | |
0b847a19 | 205 | STRTO_H(strtou64, u64) |
1c6fdbd8 | 206 | |
1c6fdbd8 KO |
207 | u64 bch2_read_flag_list(char *opt, const char * const list[]) |
208 | { | |
209 | u64 ret = 0; | |
9d8022db | 210 | char *p, *s, *d = kstrdup(opt, GFP_KERNEL); |
1c6fdbd8 KO |
211 | |
212 | if (!d) | |
213 | return -ENOMEM; | |
214 | ||
215 | s = strim(d); | |
216 | ||
217 | while ((p = strsep(&s, ","))) { | |
218 | int flag = match_string(list, -1, p); | |
1e81f89b | 219 | |
1c6fdbd8 KO |
220 | if (flag < 0) { |
221 | ret = -1; | |
222 | break; | |
223 | } | |
224 | ||
225 | ret |= 1 << flag; | |
226 | } | |
227 | ||
228 | kfree(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 | ||
189c176c | 244 | void bch2_prt_u64_base2_nbits(struct printbuf *out, u64 v, unsigned nr_bits) |
d0b50524 KO |
245 | { |
246 | while (nr_bits) | |
247 | prt_char(out, '0' + ((v >> --nr_bits) & 1)); | |
248 | } | |
249 | ||
189c176c KO |
250 | void bch2_prt_u64_base2(struct printbuf *out, u64 v) |
251 | { | |
252 | bch2_prt_u64_base2_nbits(out, v, fls64(v) ?: 1); | |
253 | } | |
254 | ||
a8f35428 KO |
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 | ||
612e1110 KO |
275 | int bch2_save_backtrace(bch_stacktrace *stack, struct task_struct *task, unsigned skipnr, |
276 | gfp_t gfp) | |
1148a97f | 277 | { |
e5570df2 | 278 | #ifdef CONFIG_STACKTRACE |
3ea4219d | 279 | unsigned nr_entries = 0; |
3ea4219d KO |
280 | |
281 | stack->nr = 0; | |
612e1110 | 282 | int ret = darray_make_room_gfp(stack, 32, gfp); |
3ea4219d KO |
283 | if (ret) |
284 | return ret; | |
1148a97f | 285 | |
3e57db65 | 286 | if (!down_read_trylock(&task->signal->exec_update_lock)) |
3ea4219d KO |
287 | return -1; |
288 | ||
289 | do { | |
c13fbb7d | 290 | nr_entries = stack_trace_save_tsk(task, stack->data, stack->size, skipnr + 1); |
3ea4219d | 291 | } while (nr_entries == stack->size && |
5197728f | 292 | !(ret = darray_make_room_gfp(stack, stack->size * 2, gfp))); |
3ea4219d KO |
293 | |
294 | stack->nr = nr_entries; | |
295 | up_read(&task->signal->exec_update_lock); | |
296 | ||
297 | return ret; | |
e5570df2 KO |
298 | #else |
299 | return 0; | |
300 | #endif | |
3ea4219d KO |
301 | } |
302 | ||
303 | void bch2_prt_backtrace(struct printbuf *out, bch_stacktrace *stack) | |
304 | { | |
3ea4219d KO |
305 | darray_for_each(*stack, i) { |
306 | prt_printf(out, "[<0>] %pB", (void *) *i); | |
1148a97f KO |
307 | prt_newline(out); |
308 | } | |
3ea4219d | 309 | } |
1148a97f | 310 | |
612e1110 | 311 | int bch2_prt_task_backtrace(struct printbuf *out, struct task_struct *task, unsigned skipnr, gfp_t gfp) |
3ea4219d KO |
312 | { |
313 | bch_stacktrace stack = { 0 }; | |
612e1110 | 314 | int ret = bch2_save_backtrace(&stack, task, skipnr + 1, gfp); |
3ea4219d KO |
315 | |
316 | bch2_prt_backtrace(out, &stack); | |
317 | darray_exit(&stack); | |
318 | return ret; | |
1148a97f KO |
319 | } |
320 | ||
066a2646 KO |
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); | |
5fd24caf | 328 | strim(buf); |
066a2646 KO |
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, sizeof(buf), "%ptT", &sec); | |
336 | prt_u64(out, sec); | |
337 | } | |
338 | #endif | |
339 | ||
066a2646 KO |
340 | void bch2_pr_time_units(struct printbuf *out, u64 ns) |
341 | { | |
f1ca1abf | 342 | const struct time_unit *u = bch2_pick_time_units(ns); |
066a2646 KO |
343 | |
344 | prt_printf(out, "%llu %s", div_u64(ns, u->nsecs), u->name); | |
345 | } | |
346 | ||
bf8f8b20 DH |
347 | static void bch2_pr_time_units_aligned(struct printbuf *out, u64 ns) |
348 | { | |
f1ca1abf | 349 | const struct time_unit *u = bch2_pick_time_units(ns); |
bf8f8b20 DH |
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 | ||
bf8f8b20 DH |
356 | static inline void pr_name_and_units(struct printbuf *out, const char *name, u64 ns) |
357 | { | |
55b8550d | 358 | prt_str(out, name); |
bf8f8b20 DH |
359 | prt_tab(out); |
360 | bch2_pr_time_units_aligned(out, ns); | |
361 | prt_newline(out); | |
362 | } | |
363 | ||
066a2646 KO |
364 | #define TABSTOP_SIZE 12 |
365 | ||
7807e143 | 366 | void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) |
1c6fdbd8 | 367 | { |
273960b8 | 368 | struct quantiles *quantiles = time_stats_to_quantiles(stats); |
bf8f8b20 | 369 | s64 f_mean = 0, d_mean = 0; |
f1ca1abf | 370 | u64 f_stddev = 0, d_stddev = 0; |
066a2646 KO |
371 | |
372 | if (stats->buffer) { | |
373 | int cpu; | |
374 | ||
375 | spin_lock_irq(&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(&stats->lock); | |
379 | } | |
380 | ||
bf8f8b20 DH |
381 | /* |
382 | * avoid divide by zero | |
383 | */ | |
384 | if (stats->freq_stats.n) { | |
385 | f_mean = mean_and_variance_get_mean(stats->freq_stats); | |
386 | f_stddev = mean_and_variance_get_stddev(stats->freq_stats); | |
387 | d_mean = mean_and_variance_get_mean(stats->duration_stats); | |
388 | d_stddev = mean_and_variance_get_stddev(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, "min:", stats->min_duration); | |
425 | pr_name_and_units(out, "max:", stats->max_duration); | |
066a2646 | 426 | pr_name_and_units(out, "total:", stats->total_duration); |
1c6fdbd8 | 427 | |
bf8f8b20 DH |
428 | prt_printf(out, "mean:"); |
429 | prt_tab(out); | |
430 | bch2_pr_time_units_aligned(out, d_mean); | |
431 | prt_tab(out); | |
4b4f0876 | 432 | bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); |
25055c69 | 433 | prt_newline(out); |
bf8f8b20 DH |
434 | |
435 | prt_printf(out, "stddev:"); | |
436 | prt_tab(out); | |
437 | bch2_pr_time_units_aligned(out, d_stddev); | |
438 | prt_tab(out); | |
4b4f0876 | 439 | bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); |
bf8f8b20 DH |
440 | |
441 | printbuf_indent_sub(out, 2); | |
25055c69 | 442 | prt_newline(out); |
1c6fdbd8 | 443 | |
bf8f8b20 DH |
444 | prt_printf(out, "time between events"); |
445 | prt_newline(out); | |
446 | printbuf_indent_add(out, 2); | |
1c6fdbd8 | 447 | |
bf8f8b20 DH |
448 | pr_name_and_units(out, "min:", stats->min_freq); |
449 | pr_name_and_units(out, "max:", stats->max_freq); | |
450 | ||
451 | prt_printf(out, "mean:"); | |
452 | prt_tab(out); | |
453 | bch2_pr_time_units_aligned(out, f_mean); | |
454 | prt_tab(out); | |
4b4f0876 | 455 | bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); |
25055c69 | 456 | prt_newline(out); |
1c6fdbd8 | 457 | |
bf8f8b20 DH |
458 | prt_printf(out, "stddev:"); |
459 | prt_tab(out); | |
460 | bch2_pr_time_units_aligned(out, f_stddev); | |
461 | prt_tab(out); | |
4b4f0876 | 462 | bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); |
bf8f8b20 DH |
463 | |
464 | printbuf_indent_sub(out, 2); | |
25055c69 | 465 | prt_newline(out); |
bf8f8b20 DH |
466 | |
467 | printbuf_tabstops_reset(out); | |
1c6fdbd8 | 468 | |
273960b8 | 469 | if (quantiles) { |
f1ca1abf KO |
470 | int i = eytzinger0_first(NR_QUANTILES); |
471 | const struct time_unit *u = | |
273960b8 | 472 | bch2_pick_time_units(quantiles->entries[i].m); |
f1ca1abf KO |
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 | ||
273960b8 | 479 | u64 q = max(quantiles->entries[i].m, last_q); |
f1ca1abf KO |
480 | prt_printf(out, "%llu ", div_u64(q, u->nsecs)); |
481 | if (is_last) | |
482 | prt_newline(out); | |
483 | last_q = q; | |
484 | } | |
1c6fdbd8 | 485 | } |
1c6fdbd8 | 486 | } |
1c6fdbd8 KO |
487 | |
488 | /* ratelimit: */ | |
489 | ||
490 | /** | |
491 | * bch2_ratelimit_delay() - return how long to delay until the next time to do | |
96dea3d5 KO |
492 | * some work |
493 | * @d: the struct bch_ratelimit to update | |
494 | * Returns: the amount of time to delay by, in jiffies | |
1c6fdbd8 KO |
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(d->next - now) | |
502 | : 0; | |
503 | } | |
504 | ||
505 | /** | |
506 | * bch2_ratelimit_increment() - increment @d by the amount of work done | |
96dea3d5 KO |
507 | * @d: the struct bch_ratelimit to update |
508 | * @done: the amount of work done, in arbitrary units | |
1c6fdbd8 KO |
509 | */ |
510 | void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done) | |
511 | { | |
512 | u64 now = local_clock(); | |
513 | ||
514 | d->next += div_u64(done * NSEC_PER_SEC, 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 | ||
1c6fdbd8 KO |
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(proportional, pd->p_term_inverse); | |
548 | ||
549 | derivative = actual - pd->last_actual; | |
550 | derivative = div_s64(derivative, 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(derivative, 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 | ||
2be7b16e | 587 | void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd) |
1c6fdbd8 | 588 | { |
401ec4db KO |
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); | |
1c6fdbd8 KO |
626 | } |
627 | ||
628 | /* misc: */ | |
629 | ||
885678f6 | 630 | void bch2_bio_map(struct bio *bio, void *base, size_t size) |
1c6fdbd8 | 631 | { |
885678f6 KO |
632 | while (size) { |
633 | struct page *page = is_vmalloc_addr(base) | |
1c6fdbd8 KO |
634 | ? vmalloc_to_page(base) |
635 | : virt_to_page(base); | |
885678f6 KO |
636 | unsigned offset = offset_in_page(base); |
637 | unsigned len = min_t(size_t, PAGE_SIZE - offset, size); | |
1c6fdbd8 | 638 | |
885678f6 KO |
639 | BUG_ON(!bio_add_page(bio, page, len, offset)); |
640 | size -= len; | |
641 | base += len; | |
1c6fdbd8 KO |
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_mask, 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 | ||
03c8c747 | 680 | void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) |
1c6fdbd8 KO |
681 | { |
682 | struct bio_vec bv; | |
683 | struct bvec_iter iter; | |
684 | ||
685 | __bio_for_each_segment(bv, dst, iter, dst_iter) { | |
1e81f89b KO |
686 | void *dstp = kmap_local_page(bv.bv_page); |
687 | ||
1c6fdbd8 | 688 | memcpy(dstp + bv.bv_offset, src, bv.bv_len); |
1e81f89b | 689 | kunmap_local(dstp); |
1c6fdbd8 KO |
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) { | |
1e81f89b KO |
701 | void *srcp = kmap_local_page(bv.bv_page); |
702 | ||
1c6fdbd8 | 703 | memcpy(dst, srcp + bv.bv_offset, bv.bv_len); |
1e81f89b | 704 | kunmap_local(srcp); |
1c6fdbd8 KO |
705 | |
706 | dst += bv.bv_len; | |
707 | } | |
708 | } | |
709 | ||
1c6fdbd8 KO |
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 | |
7ef2a73a KO |
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 | { | |
107fe5af | 842 | u64 *ret; |
7ef2a73a KO |
843 | int cpu; |
844 | ||
107fe5af KO |
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 | ||
7ef2a73a KO |
850 | for_each_possible_cpu(cpu) { |
851 | u64 *i = per_cpu_ptr(p, cpu); | |
852 | ||
853 | if (i != ret) { | |
854 | acc_u64s(ret, i, nr); | |
855 | memset(i, 0, nr * sizeof(u64)); | |
856 | } | |
857 | } | |
858 | ||
859 | return ret; | |
860 | } | |
806ebf2a KO |
861 | |
862 | void bch2_darray_str_exit(darray_str *d) | |
863 | { | |
864 | darray_for_each(*d, i) | |
865 | kfree(*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 | ||
e240c1b3 SY |
873 | char *dev_name, *s, *orig; |
874 | ||
875 | dev_name = orig = kstrdup(_dev_name, GFP_KERNEL); | |
806ebf2a KO |
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(p); | |
886 | goto err; | |
887 | } | |
888 | } | |
889 | ||
e240c1b3 | 890 | kfree(orig); |
806ebf2a KO |
891 | return 0; |
892 | err: | |
893 | bch2_darray_str_exit(ret); | |
e240c1b3 | 894 | kfree(orig); |
806ebf2a KO |
895 | return -ENOMEM; |
896 | } |