1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * random utility 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 parse_u64(const char * cp,u64 * res)40 static int parse_u64(const char *cp, u64 *res) 41 { 42 const char *start = cp; 43 u64 v = 0; 44 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 58 *res = v; 59 return cp - start; 60 } 61 bch2_pow(u64 n,u64 p,u64 * res)62 static int bch2_pow(u64 n, u64 p, u64 *res) 63 { 64 *res = 1; 65 66 while (p--) { 67 if (*res > div64_u64(U64_MAX, n)) 68 return -ERANGE; 69 *res *= n; 70 } 71 return 0; 72 } 73 parse_unit_suffix(const char * cp,u64 * res)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(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 { \ 115 int _ret = _f; \ 116 if (_ret < 0) \ 117 return _ret; \ 118 cp += _ret; \ 119 } while (0) 120 __bch2_strtou64_h(const char * cp,u64 * res)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, &f_n); 132 if (ret < 0) 133 return ret; 134 cp += ret; 135 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 > div64_u64(U64_MAX, b)) 144 return -ERANGE; 145 v *= b; 146 147 if (f_n > div64_u64(U64_MAX, b)) 148 return -ERANGE; 149 150 f_n = div64_u64(f_n * b, 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 __bch2_strtoh(const char * cp,u64 * res,u64 t_max,bool t_signed)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 STRTO_H(strtoint,int)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(const char *opt, const char * const list[]) 208 { 209 u64 ret = 0; 210 char *p, *s, *d = kstrdup(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(list, -1, p); 219 220 if (flag < 0) { 221 ret = -1; 222 break; 223 } 224 225 ret |= BIT_ULL(flag); 226 } 227 228 kfree(d); 229 230 return ret; 231 } 232 bch2_is_zero(const void * _p,size_t n)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 bch2_prt_u64_base2_nbits(struct printbuf * out,u64 v,unsigned nr_bits)244 void bch2_prt_u64_base2_nbits(struct printbuf *out, u64 v, unsigned nr_bits) 245 { 246 while (nr_bits) 247 prt_char(out, '0' + ((v >> --nr_bits) & 1)); 248 } 249 bch2_prt_u64_base2(struct printbuf * out,u64 v)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 __bch2_print_string_as_lines(const char * prefix,const char * lines,bool nonblocking)255 static void __bch2_print_string_as_lines(const char *prefix, const char *lines, 256 bool nonblocking) 257 { 258 bool locked = false; 259 const char *p; 260 261 if (!lines) { 262 printk("%s (null)\n", prefix); 263 return; 264 } 265 266 if (!nonblocking) { 267 console_lock(); 268 locked = true; 269 } else { 270 locked = console_trylock(); 271 } 272 273 while (1) { 274 p = strchrnul(lines, '\n'); 275 printk("%s%.*s\n", prefix, (int) (p - lines), lines); 276 if (!*p) 277 break; 278 lines = p + 1; 279 } 280 if (locked) 281 console_unlock(); 282 } 283 bch2_print_string_as_lines(const char * prefix,const char * lines)284 void bch2_print_string_as_lines(const char *prefix, const char *lines) 285 { 286 return __bch2_print_string_as_lines(prefix, lines, false); 287 } 288 bch2_print_string_as_lines_nonblocking(const char * prefix,const char * lines)289 void bch2_print_string_as_lines_nonblocking(const char *prefix, const char *lines) 290 { 291 return __bch2_print_string_as_lines(prefix, lines, true); 292 } 293 bch2_save_backtrace(bch_stacktrace * stack,struct task_struct * task,unsigned skipnr,gfp_t gfp)294 int bch2_save_backtrace(bch_stacktrace *stack, struct task_struct *task, unsigned skipnr, 295 gfp_t gfp) 296 { 297 #ifdef CONFIG_STACKTRACE 298 unsigned nr_entries = 0; 299 300 stack->nr = 0; 301 int ret = darray_make_room_gfp(stack, 32, gfp); 302 if (ret) 303 return ret; 304 305 if (!down_read_trylock(&task->signal->exec_update_lock)) 306 return -1; 307 308 do { 309 nr_entries = stack_trace_save_tsk(task, stack->data, stack->size, skipnr + 1); 310 } while (nr_entries == stack->size && 311 !(ret = darray_make_room_gfp(stack, stack->size * 2, gfp))); 312 313 stack->nr = nr_entries; 314 up_read(&task->signal->exec_update_lock); 315 316 return ret; 317 #else 318 return 0; 319 #endif 320 } 321 bch2_prt_backtrace(struct printbuf * out,bch_stacktrace * stack)322 void bch2_prt_backtrace(struct printbuf *out, bch_stacktrace *stack) 323 { 324 darray_for_each(*stack, i) { 325 prt_printf(out, "[<0>] %pB", (void *) *i); 326 prt_newline(out); 327 } 328 } 329 bch2_prt_task_backtrace(struct printbuf * out,struct task_struct * task,unsigned skipnr,gfp_t gfp)330 int bch2_prt_task_backtrace(struct printbuf *out, struct task_struct *task, unsigned skipnr, gfp_t gfp) 331 { 332 bch_stacktrace stack = { 0 }; 333 int ret = bch2_save_backtrace(&stack, task, skipnr + 1, gfp); 334 335 bch2_prt_backtrace(out, &stack); 336 darray_exit(&stack); 337 return ret; 338 } 339 340 #ifndef __KERNEL__ 341 #include <time.h> bch2_prt_datetime(struct printbuf * out,time64_t sec)342 void bch2_prt_datetime(struct printbuf *out, time64_t sec) 343 { 344 time_t t = sec; 345 char buf[64]; 346 ctime_r(&t, buf); 347 strim(buf); 348 prt_str(out, buf); 349 } 350 #else bch2_prt_datetime(struct printbuf * out,time64_t sec)351 void bch2_prt_datetime(struct printbuf *out, time64_t sec) 352 { 353 char buf[64]; 354 snprintf(buf, sizeof(buf), "%ptT", &sec); 355 prt_u64(out, sec); 356 } 357 #endif 358 bch2_pr_time_units(struct printbuf * out,u64 ns)359 void bch2_pr_time_units(struct printbuf *out, u64 ns) 360 { 361 const struct time_unit *u = bch2_pick_time_units(ns); 362 363 prt_printf(out, "%llu %s", div64_u64(ns, u->nsecs), u->name); 364 } 365 bch2_pr_time_units_aligned(struct printbuf * out,u64 ns)366 static void bch2_pr_time_units_aligned(struct printbuf *out, u64 ns) 367 { 368 const struct time_unit *u = bch2_pick_time_units(ns); 369 370 prt_printf(out, "%llu \r%s", div64_u64(ns, u->nsecs), u->name); 371 } 372 pr_name_and_units(struct printbuf * out,const char * name,u64 ns)373 static inline void pr_name_and_units(struct printbuf *out, const char *name, u64 ns) 374 { 375 prt_printf(out, "%s\t", name); 376 bch2_pr_time_units_aligned(out, ns); 377 prt_newline(out); 378 } 379 380 #define TABSTOP_SIZE 12 381 bch2_time_stats_to_text(struct printbuf * out,struct bch2_time_stats * stats)382 void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) 383 { 384 struct quantiles *quantiles = time_stats_to_quantiles(stats); 385 s64 f_mean = 0, d_mean = 0; 386 u64 f_stddev = 0, d_stddev = 0; 387 388 if (stats->buffer) { 389 int cpu; 390 391 spin_lock_irq(&stats->lock); 392 for_each_possible_cpu(cpu) 393 __bch2_time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu)); 394 spin_unlock_irq(&stats->lock); 395 } 396 397 /* 398 * avoid divide by zero 399 */ 400 if (stats->freq_stats.n) { 401 f_mean = mean_and_variance_get_mean(stats->freq_stats); 402 f_stddev = mean_and_variance_get_stddev(stats->freq_stats); 403 d_mean = mean_and_variance_get_mean(stats->duration_stats); 404 d_stddev = mean_and_variance_get_stddev(stats->duration_stats); 405 } 406 407 printbuf_tabstop_push(out, out->indent + TABSTOP_SIZE); 408 prt_printf(out, "count:\t%llu\n", stats->duration_stats.n); 409 printbuf_tabstop_pop(out); 410 411 printbuf_tabstops_reset(out); 412 413 printbuf_tabstop_push(out, out->indent + 20); 414 printbuf_tabstop_push(out, TABSTOP_SIZE + 2); 415 printbuf_tabstop_push(out, 0); 416 printbuf_tabstop_push(out, TABSTOP_SIZE + 2); 417 418 prt_printf(out, "\tsince mount\r\trecent\r\n"); 419 420 printbuf_tabstops_reset(out); 421 printbuf_tabstop_push(out, out->indent + 20); 422 printbuf_tabstop_push(out, TABSTOP_SIZE); 423 printbuf_tabstop_push(out, 2); 424 printbuf_tabstop_push(out, TABSTOP_SIZE); 425 426 prt_printf(out, "duration of events\n"); 427 printbuf_indent_add(out, 2); 428 429 pr_name_and_units(out, "min:", stats->min_duration); 430 pr_name_and_units(out, "max:", stats->max_duration); 431 pr_name_and_units(out, "total:", stats->total_duration); 432 433 prt_printf(out, "mean:\t"); 434 bch2_pr_time_units_aligned(out, d_mean); 435 prt_tab(out); 436 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); 437 prt_newline(out); 438 439 prt_printf(out, "stddev:\t"); 440 bch2_pr_time_units_aligned(out, d_stddev); 441 prt_tab(out); 442 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); 443 444 printbuf_indent_sub(out, 2); 445 prt_newline(out); 446 447 prt_printf(out, "time between events\n"); 448 printbuf_indent_add(out, 2); 449 450 pr_name_and_units(out, "min:", stats->min_freq); 451 pr_name_and_units(out, "max:", stats->max_freq); 452 453 prt_printf(out, "mean:\t"); 454 bch2_pr_time_units_aligned(out, f_mean); 455 prt_tab(out); 456 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); 457 prt_newline(out); 458 459 prt_printf(out, "stddev:\t"); 460 bch2_pr_time_units_aligned(out, f_stddev); 461 prt_tab(out); 462 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(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(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 ", div64_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 */ bch2_ratelimit_delay(struct bch_ratelimit * d)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 507 * @d: the struct bch_ratelimit to update 508 * @done: the amount of work done, in arbitrary units 509 */ bch2_ratelimit_increment(struct bch_ratelimit * d,u64 done)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 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 */ bch2_pd_controller_update(struct bch_pd_controller * pd,s64 target,s64 actual,int sign)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 bch2_pd_controller_init(struct bch_pd_controller * pd)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 bch2_pd_controller_debug_to_text(struct printbuf * out,struct bch_pd_controller * pd)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:\t"); 593 prt_human_readable_s64(out, pd->rate.rate); 594 prt_newline(out); 595 596 prt_printf(out, "target:\t"); 597 prt_human_readable_u64(out, pd->last_target); 598 prt_newline(out); 599 600 prt_printf(out, "actual:\t"); 601 prt_human_readable_u64(out, pd->last_actual); 602 prt_newline(out); 603 604 prt_printf(out, "proportional:\t"); 605 prt_human_readable_s64(out, pd->last_proportional); 606 prt_newline(out); 607 608 prt_printf(out, "derivative:\t"); 609 prt_human_readable_s64(out, pd->last_derivative); 610 prt_newline(out); 611 612 prt_printf(out, "change:\t"); 613 prt_human_readable_s64(out, pd->last_change); 614 prt_newline(out); 615 616 prt_printf(out, "next io:\t%llims\n", div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC)); 617 } 618 619 /* misc: */ 620 bch2_bio_map(struct bio * bio,void * base,size_t size)621 void bch2_bio_map(struct bio *bio, void *base, size_t size) 622 { 623 while (size) { 624 struct page *page = is_vmalloc_addr(base) 625 ? vmalloc_to_page(base) 626 : virt_to_page(base); 627 unsigned offset = offset_in_page(base); 628 unsigned len = min_t(size_t, PAGE_SIZE - offset, size); 629 630 BUG_ON(!bio_add_page(bio, page, len, offset)); 631 size -= len; 632 base += len; 633 } 634 } 635 bch2_bio_alloc_pages(struct bio * bio,size_t size,gfp_t gfp_mask)636 int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask) 637 { 638 while (size) { 639 struct page *page = alloc_pages(gfp_mask, 0); 640 unsigned len = min_t(size_t, PAGE_SIZE, size); 641 642 if (!page) 643 return -ENOMEM; 644 645 if (unlikely(!bio_add_page(bio, page, len, 0))) { 646 __free_page(page); 647 break; 648 } 649 650 size -= len; 651 } 652 653 return 0; 654 } 655 bch2_rand_range(size_t max)656 size_t bch2_rand_range(size_t max) 657 { 658 size_t rand; 659 660 if (!max) 661 return 0; 662 663 do { 664 rand = get_random_long(); 665 rand &= roundup_pow_of_two(max) - 1; 666 } while (rand >= max); 667 668 return rand; 669 } 670 memcpy_to_bio(struct bio * dst,struct bvec_iter dst_iter,const void * src)671 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) 672 { 673 struct bio_vec bv; 674 struct bvec_iter iter; 675 676 __bio_for_each_segment(bv, dst, iter, dst_iter) { 677 void *dstp = kmap_local_page(bv.bv_page); 678 679 memcpy(dstp + bv.bv_offset, src, bv.bv_len); 680 kunmap_local(dstp); 681 682 src += bv.bv_len; 683 } 684 } 685 memcpy_from_bio(void * dst,struct bio * src,struct bvec_iter src_iter)686 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) 687 { 688 struct bio_vec bv; 689 struct bvec_iter iter; 690 691 __bio_for_each_segment(bv, src, iter, src_iter) { 692 void *srcp = kmap_local_page(bv.bv_page); 693 694 memcpy(dst, srcp + bv.bv_offset, bv.bv_len); 695 kunmap_local(srcp); 696 697 dst += bv.bv_len; 698 } 699 } 700 701 #if 0 702 void eytzinger1_test(void) 703 { 704 unsigned inorder, eytz, size; 705 706 pr_info("1 based eytzinger test:"); 707 708 for (size = 2; 709 size < 65536; 710 size++) { 711 unsigned extra = eytzinger1_extra(size); 712 713 if (!(size % 4096)) 714 pr_info("tree size %u", size); 715 716 BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); 717 BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); 718 719 BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); 720 BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); 721 722 inorder = 1; 723 eytzinger1_for_each(eytz, size) { 724 BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); 725 BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder); 726 BUG_ON(eytz != eytzinger1_last(size) && 727 eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz); 728 729 inorder++; 730 } 731 } 732 } 733 734 void eytzinger0_test(void) 735 { 736 737 unsigned inorder, eytz, size; 738 739 pr_info("0 based eytzinger test:"); 740 741 for (size = 1; 742 size < 65536; 743 size++) { 744 unsigned extra = eytzinger0_extra(size); 745 746 if (!(size % 4096)) 747 pr_info("tree size %u", size); 748 749 BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); 750 BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); 751 752 BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); 753 BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); 754 755 inorder = 0; 756 eytzinger0_for_each(eytz, size) { 757 BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz); 758 BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder); 759 BUG_ON(eytz != eytzinger0_last(size) && 760 eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz); 761 762 inorder++; 763 } 764 } 765 } 766 767 static inline int cmp_u16(const void *_l, const void *_r, size_t size) 768 { 769 const u16 *l = _l, *r = _r; 770 771 return (*l > *r) - (*r - *l); 772 } 773 774 static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) 775 { 776 int i, c1 = -1, c2 = -1; 777 ssize_t r; 778 779 r = eytzinger0_find_le(test_array, nr, 780 sizeof(test_array[0]), 781 cmp_u16, &search); 782 if (r >= 0) 783 c1 = test_array[r]; 784 785 for (i = 0; i < nr; i++) 786 if (test_array[i] <= search && test_array[i] > c2) 787 c2 = test_array[i]; 788 789 if (c1 != c2) { 790 eytzinger0_for_each(i, nr) 791 pr_info("[%3u] = %12u", i, test_array[i]); 792 pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", 793 i, r, c1, c2); 794 } 795 } 796 797 void eytzinger0_find_test(void) 798 { 799 unsigned i, nr, allocated = 1 << 12; 800 u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); 801 802 for (nr = 1; nr < allocated; nr++) { 803 pr_info("testing %u elems", nr); 804 805 get_random_bytes(test_array, nr * sizeof(test_array[0])); 806 eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); 807 808 /* verify array is sorted correctly: */ 809 eytzinger0_for_each(i, nr) 810 BUG_ON(i != eytzinger0_last(nr) && 811 test_array[i] > test_array[eytzinger0_next(i, nr)]); 812 813 for (i = 0; i < U16_MAX; i += 1 << 12) 814 eytzinger0_find_test_val(test_array, nr, i); 815 816 for (i = 0; i < nr; i++) { 817 eytzinger0_find_test_val(test_array, nr, test_array[i] - 1); 818 eytzinger0_find_test_val(test_array, nr, test_array[i]); 819 eytzinger0_find_test_val(test_array, nr, test_array[i] + 1); 820 } 821 } 822 823 kfree(test_array); 824 } 825 #endif 826 827 /* 828 * Accumulate percpu counters onto one cpu's copy - only valid when access 829 * against any percpu counter is guarded against 830 */ bch2_acc_percpu_u64s(u64 __percpu * p,unsigned nr)831 u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr) 832 { 833 u64 *ret; 834 int cpu; 835 836 /* access to pcpu vars has to be blocked by other locking */ 837 preempt_disable(); 838 ret = this_cpu_ptr(p); 839 preempt_enable(); 840 841 for_each_possible_cpu(cpu) { 842 u64 *i = per_cpu_ptr(p, cpu); 843 844 if (i != ret) { 845 acc_u64s(ret, i, nr); 846 memset(i, 0, nr * sizeof(u64)); 847 } 848 } 849 850 return ret; 851 } 852 bch2_darray_str_exit(darray_str * d)853 void bch2_darray_str_exit(darray_str *d) 854 { 855 darray_for_each(*d, i) 856 kfree(*i); 857 darray_exit(d); 858 } 859 bch2_split_devs(const char * _dev_name,darray_str * ret)860 int bch2_split_devs(const char *_dev_name, darray_str *ret) 861 { 862 darray_init(ret); 863 864 char *dev_name, *s, *orig; 865 866 dev_name = orig = kstrdup(_dev_name, GFP_KERNEL); 867 if (!dev_name) 868 return -ENOMEM; 869 870 while ((s = strsep(&dev_name, ":"))) { 871 char *p = kstrdup(s, GFP_KERNEL); 872 if (!p) 873 goto err; 874 875 if (darray_push(ret, p)) { 876 kfree(p); 877 goto err; 878 } 879 } 880 881 kfree(orig); 882 return 0; 883 err: 884 bch2_darray_str_exit(ret); 885 kfree(orig); 886 return -ENOMEM; 887 } 888