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 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 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 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 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 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(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 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, '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, fls64(v) ?: 1); 253 } 254 255 static bool string_is_spaces(const char *str) 256 { 257 while (*str) { 258 if (*str != ' ') 259 return false; 260 str++; 261 } 262 return true; 263 } 264 265 void bch2_print_string_as_lines(const char *prefix, const char *lines) 266 { 267 bool locked = false; 268 const char *p; 269 270 if (!lines) { 271 printk("%s (null)\n", prefix); 272 return; 273 } 274 275 locked = console_trylock(); 276 277 while (*lines) { 278 p = strchrnul(lines, '\n'); 279 if (!*p && string_is_spaces(lines)) 280 break; 281 282 printk("%s%.*s\n", prefix, (int) (p - lines), lines); 283 if (!*p) 284 break; 285 lines = p + 1; 286 } 287 if (locked) 288 console_unlock(); 289 } 290 291 int bch2_save_backtrace(bch_stacktrace *stack, struct task_struct *task, unsigned skipnr, 292 gfp_t gfp) 293 { 294 #ifdef CONFIG_STACKTRACE 295 unsigned nr_entries = 0; 296 297 stack->nr = 0; 298 int ret = darray_make_room_gfp(stack, 32, gfp); 299 if (ret) 300 return ret; 301 302 if (!down_read_trylock(&task->signal->exec_update_lock)) 303 return -1; 304 305 do { 306 nr_entries = stack_trace_save_tsk(task, stack->data, stack->size, skipnr + 1); 307 } while (nr_entries == stack->size && 308 !(ret = darray_make_room_gfp(stack, stack->size * 2, gfp))); 309 310 stack->nr = nr_entries; 311 up_read(&task->signal->exec_update_lock); 312 313 return ret; 314 #else 315 return 0; 316 #endif 317 } 318 319 void bch2_prt_backtrace(struct printbuf *out, bch_stacktrace *stack) 320 { 321 darray_for_each(*stack, i) { 322 prt_printf(out, "[<0>] %pB", (void *) *i); 323 prt_newline(out); 324 } 325 } 326 327 int bch2_prt_task_backtrace(struct printbuf *out, struct task_struct *task, unsigned skipnr, gfp_t gfp) 328 { 329 bch_stacktrace stack = { 0 }; 330 int ret = bch2_save_backtrace(&stack, task, skipnr + 1, gfp); 331 332 bch2_prt_backtrace(out, &stack); 333 darray_exit(&stack); 334 return ret; 335 } 336 337 #ifndef __KERNEL__ 338 #include <time.h> 339 void bch2_prt_datetime(struct printbuf *out, time64_t sec) 340 { 341 time_t t = sec; 342 char buf[64]; 343 ctime_r(&t, buf); 344 strim(buf); 345 prt_str(out, buf); 346 } 347 #else 348 void bch2_prt_datetime(struct printbuf *out, time64_t sec) 349 { 350 char buf[64]; 351 snprintf(buf, sizeof(buf), "%ptT", &sec); 352 prt_u64(out, sec); 353 } 354 #endif 355 356 void bch2_pr_time_units(struct printbuf *out, u64 ns) 357 { 358 const struct time_unit *u = bch2_pick_time_units(ns); 359 360 prt_printf(out, "%llu %s", div64_u64(ns, u->nsecs), u->name); 361 } 362 363 static void bch2_pr_time_units_aligned(struct printbuf *out, u64 ns) 364 { 365 const struct time_unit *u = bch2_pick_time_units(ns); 366 367 prt_printf(out, "%llu \r%s", div64_u64(ns, u->nsecs), u->name); 368 } 369 370 static inline void pr_name_and_units(struct printbuf *out, const char *name, u64 ns) 371 { 372 prt_printf(out, "%s\t", name); 373 bch2_pr_time_units_aligned(out, ns); 374 prt_newline(out); 375 } 376 377 #define TABSTOP_SIZE 12 378 379 void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) 380 { 381 struct quantiles *quantiles = time_stats_to_quantiles(stats); 382 s64 f_mean = 0, d_mean = 0; 383 u64 f_stddev = 0, d_stddev = 0; 384 385 if (stats->buffer) { 386 int cpu; 387 388 spin_lock_irq(&stats->lock); 389 for_each_possible_cpu(cpu) 390 __bch2_time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu)); 391 spin_unlock_irq(&stats->lock); 392 } 393 394 /* 395 * avoid divide by zero 396 */ 397 if (stats->freq_stats.n) { 398 f_mean = mean_and_variance_get_mean(stats->freq_stats); 399 f_stddev = mean_and_variance_get_stddev(stats->freq_stats); 400 d_mean = mean_and_variance_get_mean(stats->duration_stats); 401 d_stddev = mean_and_variance_get_stddev(stats->duration_stats); 402 } 403 404 printbuf_tabstop_push(out, out->indent + TABSTOP_SIZE); 405 prt_printf(out, "count:\t%llu\n", stats->duration_stats.n); 406 printbuf_tabstop_pop(out); 407 408 printbuf_tabstops_reset(out); 409 410 printbuf_tabstop_push(out, out->indent + 20); 411 printbuf_tabstop_push(out, TABSTOP_SIZE + 2); 412 printbuf_tabstop_push(out, 0); 413 printbuf_tabstop_push(out, TABSTOP_SIZE + 2); 414 415 prt_printf(out, "\tsince mount\r\trecent\r\n"); 416 417 printbuf_tabstops_reset(out); 418 printbuf_tabstop_push(out, out->indent + 20); 419 printbuf_tabstop_push(out, TABSTOP_SIZE); 420 printbuf_tabstop_push(out, 2); 421 printbuf_tabstop_push(out, TABSTOP_SIZE); 422 423 prt_printf(out, "duration of events\n"); 424 printbuf_indent_add(out, 2); 425 426 pr_name_and_units(out, "min:", stats->min_duration); 427 pr_name_and_units(out, "max:", stats->max_duration); 428 pr_name_and_units(out, "total:", stats->total_duration); 429 430 prt_printf(out, "mean:\t"); 431 bch2_pr_time_units_aligned(out, d_mean); 432 prt_tab(out); 433 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT)); 434 prt_newline(out); 435 436 prt_printf(out, "stddev:\t"); 437 bch2_pr_time_units_aligned(out, d_stddev); 438 prt_tab(out); 439 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(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\n"); 445 printbuf_indent_add(out, 2); 446 447 pr_name_and_units(out, "min:", stats->min_freq); 448 pr_name_and_units(out, "max:", stats->max_freq); 449 450 prt_printf(out, "mean:\t"); 451 bch2_pr_time_units_aligned(out, f_mean); 452 prt_tab(out); 453 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); 454 prt_newline(out); 455 456 prt_printf(out, "stddev:\t"); 457 bch2_pr_time_units_aligned(out, f_stddev); 458 prt_tab(out); 459 bch2_pr_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT)); 460 461 printbuf_indent_sub(out, 2); 462 prt_newline(out); 463 464 printbuf_tabstops_reset(out); 465 466 if (quantiles) { 467 int i = eytzinger0_first(NR_QUANTILES); 468 const struct time_unit *u = 469 bch2_pick_time_units(quantiles->entries[i].m); 470 u64 last_q = 0; 471 472 prt_printf(out, "quantiles (%s):\t", u->name); 473 eytzinger0_for_each(j, NR_QUANTILES) { 474 bool is_last = eytzinger0_next(j, NR_QUANTILES) == -1; 475 476 u64 q = max(quantiles->entries[j].m, last_q); 477 prt_printf(out, "%llu ", div64_u64(q, u->nsecs)); 478 if (is_last) 479 prt_newline(out); 480 last_q = q; 481 } 482 } 483 } 484 485 /* ratelimit: */ 486 487 /** 488 * bch2_ratelimit_delay() - return how long to delay until the next time to do 489 * some work 490 * @d: the struct bch_ratelimit to update 491 * Returns: the amount of time to delay by, in jiffies 492 */ 493 u64 bch2_ratelimit_delay(struct bch_ratelimit *d) 494 { 495 u64 now = local_clock(); 496 497 return time_after64(d->next, now) 498 ? nsecs_to_jiffies(d->next - now) 499 : 0; 500 } 501 502 /** 503 * bch2_ratelimit_increment() - increment @d by the amount of work done 504 * @d: the struct bch_ratelimit to update 505 * @done: the amount of work done, in arbitrary units 506 */ 507 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done) 508 { 509 u64 now = local_clock(); 510 511 d->next += div_u64(done * NSEC_PER_SEC, d->rate); 512 513 if (time_before64(now + NSEC_PER_SEC, d->next)) 514 d->next = now + NSEC_PER_SEC; 515 516 if (time_after64(now - NSEC_PER_SEC * 2, d->next)) 517 d->next = now - NSEC_PER_SEC * 2; 518 } 519 520 /* pd controller: */ 521 522 /* 523 * Updates pd_controller. Attempts to scale inputed values to units per second. 524 * @target: desired value 525 * @actual: current value 526 * 527 * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing 528 * it makes actual go down. 529 */ 530 void bch2_pd_controller_update(struct bch_pd_controller *pd, 531 s64 target, s64 actual, int sign) 532 { 533 s64 proportional, derivative, change; 534 535 unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ; 536 537 if (seconds_since_update == 0) 538 return; 539 540 pd->last_update = jiffies; 541 542 proportional = actual - target; 543 proportional *= seconds_since_update; 544 proportional = div_s64(proportional, pd->p_term_inverse); 545 546 derivative = actual - pd->last_actual; 547 derivative = div_s64(derivative, seconds_since_update); 548 derivative = ewma_add(pd->smoothed_derivative, derivative, 549 (pd->d_term / seconds_since_update) ?: 1); 550 derivative = derivative * pd->d_term; 551 derivative = div_s64(derivative, pd->p_term_inverse); 552 553 change = proportional + derivative; 554 555 /* Don't increase rate if not keeping up */ 556 if (change > 0 && 557 pd->backpressure && 558 time_after64(local_clock(), 559 pd->rate.next + NSEC_PER_MSEC)) 560 change = 0; 561 562 change *= (sign * -1); 563 564 pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change, 565 1, UINT_MAX); 566 567 pd->last_actual = actual; 568 pd->last_derivative = derivative; 569 pd->last_proportional = proportional; 570 pd->last_change = change; 571 pd->last_target = target; 572 } 573 574 void bch2_pd_controller_init(struct bch_pd_controller *pd) 575 { 576 pd->rate.rate = 1024; 577 pd->last_update = jiffies; 578 pd->p_term_inverse = 6000; 579 pd->d_term = 30; 580 pd->d_smooth = pd->d_term; 581 pd->backpressure = 1; 582 } 583 584 void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd) 585 { 586 if (!out->nr_tabstops) 587 printbuf_tabstop_push(out, 20); 588 589 prt_printf(out, "rate:\t"); 590 prt_human_readable_s64(out, pd->rate.rate); 591 prt_newline(out); 592 593 prt_printf(out, "target:\t"); 594 prt_human_readable_u64(out, pd->last_target); 595 prt_newline(out); 596 597 prt_printf(out, "actual:\t"); 598 prt_human_readable_u64(out, pd->last_actual); 599 prt_newline(out); 600 601 prt_printf(out, "proportional:\t"); 602 prt_human_readable_s64(out, pd->last_proportional); 603 prt_newline(out); 604 605 prt_printf(out, "derivative:\t"); 606 prt_human_readable_s64(out, pd->last_derivative); 607 prt_newline(out); 608 609 prt_printf(out, "change:\t"); 610 prt_human_readable_s64(out, pd->last_change); 611 prt_newline(out); 612 613 prt_printf(out, "next io:\t%llims\n", div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC)); 614 } 615 616 /* misc: */ 617 618 void bch2_bio_map(struct bio *bio, void *base, size_t size) 619 { 620 while (size) { 621 struct page *page = is_vmalloc_addr(base) 622 ? vmalloc_to_page(base) 623 : virt_to_page(base); 624 unsigned offset = offset_in_page(base); 625 unsigned len = min_t(size_t, PAGE_SIZE - offset, size); 626 627 BUG_ON(!bio_add_page(bio, page, len, offset)); 628 size -= len; 629 base += len; 630 } 631 } 632 633 int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask) 634 { 635 while (size) { 636 struct page *page = alloc_pages(gfp_mask, 0); 637 unsigned len = min_t(size_t, PAGE_SIZE, size); 638 639 if (!page) 640 return -ENOMEM; 641 642 if (unlikely(!bio_add_page(bio, page, len, 0))) { 643 __free_page(page); 644 break; 645 } 646 647 size -= len; 648 } 649 650 return 0; 651 } 652 653 u64 bch2_get_random_u64_below(u64 ceil) 654 { 655 if (ceil <= U32_MAX) 656 return __get_random_u32_below(ceil); 657 658 /* this is the same (clever) algorithm as in __get_random_u32_below() */ 659 u64 rand = get_random_u64(); 660 u64 mult = ceil * rand; 661 662 if (unlikely(mult < ceil)) { 663 u64 bound; 664 div64_u64_rem(-ceil, ceil, &bound); 665 while (unlikely(mult < bound)) { 666 rand = get_random_u64(); 667 mult = ceil * rand; 668 } 669 } 670 671 return mul_u64_u64_shr(ceil, rand, 64); 672 } 673 674 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) 675 { 676 struct bio_vec bv; 677 struct bvec_iter iter; 678 679 __bio_for_each_segment(bv, dst, iter, dst_iter) { 680 void *dstp = kmap_local_page(bv.bv_page); 681 682 memcpy(dstp + bv.bv_offset, src, bv.bv_len); 683 kunmap_local(dstp); 684 685 src += bv.bv_len; 686 } 687 } 688 689 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) 690 { 691 struct bio_vec bv; 692 struct bvec_iter iter; 693 694 __bio_for_each_segment(bv, src, iter, src_iter) { 695 void *srcp = kmap_local_page(bv.bv_page); 696 697 memcpy(dst, srcp + bv.bv_offset, bv.bv_len); 698 kunmap_local(srcp); 699 700 dst += bv.bv_len; 701 } 702 } 703 704 #ifdef CONFIG_BCACHEFS_DEBUG 705 void bch2_corrupt_bio(struct bio *bio) 706 { 707 struct bvec_iter iter; 708 struct bio_vec bv; 709 unsigned offset = get_random_u32_below(bio->bi_iter.bi_size / sizeof(u64)); 710 711 bio_for_each_segment(bv, bio, iter) { 712 unsigned u64s = bv.bv_len / sizeof(u64); 713 714 if (offset < u64s) { 715 u64 *segment = bvec_kmap_local(&bv); 716 segment[offset] = get_random_u64(); 717 kunmap_local(segment); 718 return; 719 } 720 offset -= u64s; 721 } 722 } 723 #endif 724 725 void bch2_bio_to_text(struct printbuf *out, struct bio *bio) 726 { 727 prt_printf(out, "bi_remaining:\t%u\n", 728 atomic_read(&bio->__bi_remaining)); 729 prt_printf(out, "bi_end_io:\t%ps\n", 730 bio->bi_end_io); 731 prt_printf(out, "bi_status:\t%u\n", 732 bio->bi_status); 733 } 734 735 #if 0 736 void eytzinger1_test(void) 737 { 738 unsigned inorder, size; 739 740 pr_info("1 based eytzinger test:\n"); 741 742 for (size = 2; 743 size < 65536; 744 size++) { 745 unsigned extra = eytzinger1_extra(size); 746 747 if (!(size % 4096)) 748 pr_info("tree size %u\n", size); 749 750 inorder = 1; 751 eytzinger1_for_each(eytz, size) { 752 BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); 753 BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder); 754 BUG_ON(eytz != eytzinger1_last(size) && 755 eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz); 756 757 inorder++; 758 } 759 BUG_ON(inorder - 1 != size); 760 } 761 } 762 763 void eytzinger0_test(void) 764 { 765 766 unsigned inorder, size; 767 768 pr_info("0 based eytzinger test:\n"); 769 770 for (size = 1; 771 size < 65536; 772 size++) { 773 unsigned extra = eytzinger0_extra(size); 774 775 if (!(size % 4096)) 776 pr_info("tree size %u\n", size); 777 778 inorder = 0; 779 eytzinger0_for_each(eytz, size) { 780 BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz); 781 BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder); 782 BUG_ON(eytz != eytzinger0_last(size) && 783 eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz); 784 785 inorder++; 786 } 787 BUG_ON(inorder != size); 788 789 inorder = size - 1; 790 eytzinger0_for_each_prev(eytz, size) { 791 BUG_ON(eytz != eytzinger0_first(size) && 792 eytzinger0_next(eytzinger0_prev(eytz, size), size) != eytz); 793 794 inorder--; 795 } 796 BUG_ON(inorder != -1); 797 } 798 } 799 800 static inline int cmp_u16(const void *_l, const void *_r) 801 { 802 const u16 *l = _l, *r = _r; 803 804 return (*l > *r) - (*r > *l); 805 } 806 807 static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) 808 { 809 int r, s; 810 bool bad; 811 812 r = eytzinger0_find_le(test_array, nr, 813 sizeof(test_array[0]), 814 cmp_u16, &search); 815 if (r >= 0) { 816 if (test_array[r] > search) { 817 bad = true; 818 } else { 819 s = eytzinger0_next(r, nr); 820 bad = s >= 0 && test_array[s] <= search; 821 } 822 } else { 823 s = eytzinger0_last(nr); 824 bad = s >= 0 && test_array[s] <= search; 825 } 826 827 if (bad) { 828 s = -1; 829 eytzinger0_for_each_prev(j, nr) { 830 if (test_array[j] <= search) { 831 s = j; 832 break; 833 } 834 } 835 836 eytzinger0_for_each(j, nr) 837 pr_info("[%3u] = %12u\n", j, test_array[j]); 838 pr_info("find_le(%12u) = %3i should be %3i\n", 839 search, r, s); 840 BUG(); 841 } 842 } 843 844 static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search) 845 { 846 int r, s; 847 bool bad; 848 849 r = eytzinger0_find_gt(test_array, nr, 850 sizeof(test_array[0]), 851 cmp_u16, &search); 852 if (r >= 0) { 853 if (test_array[r] <= search) { 854 bad = true; 855 } else { 856 s = eytzinger0_prev(r, nr); 857 bad = s >= 0 && test_array[s] > search; 858 } 859 } else { 860 s = eytzinger0_first(nr); 861 bad = s >= 0 && test_array[s] > search; 862 } 863 864 if (bad) { 865 s = -1; 866 eytzinger0_for_each(j, nr) { 867 if (test_array[j] > search) { 868 s = j; 869 break; 870 } 871 } 872 873 eytzinger0_for_each(j, nr) 874 pr_info("[%3u] = %12u\n", j, test_array[j]); 875 pr_info("find_gt(%12u) = %3i should be %3i\n", 876 search, r, s); 877 BUG(); 878 } 879 } 880 881 static void eytzinger0_find_test_ge(u16 *test_array, unsigned nr, u16 search) 882 { 883 int r, s; 884 bool bad; 885 886 r = eytzinger0_find_ge(test_array, nr, 887 sizeof(test_array[0]), 888 cmp_u16, &search); 889 if (r >= 0) { 890 if (test_array[r] < search) { 891 bad = true; 892 } else { 893 s = eytzinger0_prev(r, nr); 894 bad = s >= 0 && test_array[s] >= search; 895 } 896 } else { 897 s = eytzinger0_first(nr); 898 bad = s >= 0 && test_array[s] >= search; 899 } 900 901 if (bad) { 902 s = -1; 903 eytzinger0_for_each(j, nr) { 904 if (test_array[j] >= search) { 905 s = j; 906 break; 907 } 908 } 909 910 eytzinger0_for_each(j, nr) 911 pr_info("[%3u] = %12u\n", j, test_array[j]); 912 pr_info("find_ge(%12u) = %3i should be %3i\n", 913 search, r, s); 914 BUG(); 915 } 916 } 917 918 static void eytzinger0_find_test_eq(u16 *test_array, unsigned nr, u16 search) 919 { 920 unsigned r; 921 int s; 922 bool bad; 923 924 r = eytzinger0_find(test_array, nr, 925 sizeof(test_array[0]), 926 cmp_u16, &search); 927 928 if (r < nr) { 929 bad = test_array[r] != search; 930 } else { 931 s = eytzinger0_find_le(test_array, nr, 932 sizeof(test_array[0]), 933 cmp_u16, &search); 934 bad = s >= 0 && test_array[s] == search; 935 } 936 937 if (bad) { 938 eytzinger0_for_each(j, nr) 939 pr_info("[%3u] = %12u\n", j, test_array[j]); 940 pr_info("find(%12u) = %3i is incorrect\n", 941 search, r); 942 BUG(); 943 } 944 } 945 946 static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) 947 { 948 eytzinger0_find_test_le(test_array, nr, search); 949 eytzinger0_find_test_gt(test_array, nr, search); 950 eytzinger0_find_test_ge(test_array, nr, search); 951 eytzinger0_find_test_eq(test_array, nr, search); 952 } 953 954 void eytzinger0_find_test(void) 955 { 956 unsigned i, nr, allocated = 1 << 12; 957 u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); 958 959 for (nr = 1; nr < allocated; nr++) { 960 u16 prev = 0; 961 962 pr_info("testing %u elems\n", nr); 963 964 get_random_bytes(test_array, nr * sizeof(test_array[0])); 965 eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); 966 967 /* verify array is sorted correctly: */ 968 eytzinger0_for_each(j, nr) { 969 BUG_ON(test_array[j] < prev); 970 prev = test_array[j]; 971 } 972 973 for (i = 0; i < U16_MAX; i += 1 << 12) 974 eytzinger0_find_test_val(test_array, nr, i); 975 976 for (i = 0; i < nr; i++) { 977 eytzinger0_find_test_val(test_array, nr, test_array[i] - 1); 978 eytzinger0_find_test_val(test_array, nr, test_array[i]); 979 eytzinger0_find_test_val(test_array, nr, test_array[i] + 1); 980 } 981 } 982 983 kfree(test_array); 984 } 985 #endif 986 987 /* 988 * Accumulate percpu counters onto one cpu's copy - only valid when access 989 * against any percpu counter is guarded against 990 */ 991 u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr) 992 { 993 u64 *ret; 994 int cpu; 995 996 /* access to pcpu vars has to be blocked by other locking */ 997 preempt_disable(); 998 ret = this_cpu_ptr(p); 999 preempt_enable(); 1000 1001 for_each_possible_cpu(cpu) { 1002 u64 *i = per_cpu_ptr(p, cpu); 1003 1004 if (i != ret) { 1005 acc_u64s(ret, i, nr); 1006 memset(i, 0, nr * sizeof(u64)); 1007 } 1008 } 1009 1010 return ret; 1011 } 1012 1013 void bch2_darray_str_exit(darray_const_str *d) 1014 { 1015 darray_for_each(*d, i) 1016 kfree(*i); 1017 darray_exit(d); 1018 } 1019 1020 int bch2_split_devs(const char *_dev_name, darray_const_str *ret) 1021 { 1022 darray_init(ret); 1023 1024 char *dev_name, *s, *orig; 1025 1026 dev_name = orig = kstrdup(_dev_name, GFP_KERNEL); 1027 if (!dev_name) 1028 return -ENOMEM; 1029 1030 while ((s = strsep(&dev_name, ":"))) { 1031 char *p = kstrdup(s, GFP_KERNEL); 1032 if (!p) 1033 goto err; 1034 1035 if (darray_push(ret, p)) { 1036 kfree(p); 1037 goto err; 1038 } 1039 } 1040 1041 kfree(orig); 1042 return 0; 1043 err: 1044 bch2_darray_str_exit(ret); 1045 kfree(orig); 1046 return -ENOMEM; 1047 } 1048