git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/util.c

   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 "util.h"
  28
  29 static const char si_units[] = "?kMGTPEZY";
  30
  31 /* string_get_size units: */
  32 static const char *const units_2[] = {
  33         "B", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB", "ZiB", "YiB"
  34 };
  35 static const char *const units_10[] = {
  36         "B", "kB", "MB", "GB", "TB", "PB", "EB", "ZB", "YB"
  37 };
  38
  39 static int parse_u64(const char *cp, u64 *res)
  40 {
  41         const char *start = cp;
  42         u64 v = 0;
  43
  44         if (!isdigit(*cp))
  45                 return -EINVAL;
  46
  47         do {
  48                 if (v > U64_MAX / 10)
  49                         return -ERANGE;
  50                 v *= 10;
  51                 if (v > U64_MAX - (*cp - '0'))
  52                         return -ERANGE;
  53                 v += *cp - '0';
  54                 cp++;
  55         } while (isdigit(*cp));
  56
  57         *res = v;
  58         return cp - start;
  59 }
  60
  61 static int bch2_pow(u64 n, u64 p, u64 *res)
  62 {
  63         *res = 1;
  64
  65         while (p--) {
  66                 if (*res > div_u64(U64_MAX, n))
  67                         return -ERANGE;
  68                 *res *= n;
  69         }
  70         return 0;
  71 }
  72
  73 static int parse_unit_suffix(const char *cp, u64 *res)
  74 {
  75         const char *start = cp;
  76         u64 base = 1024;
  77         unsigned u;
  78         int ret;
  79
  80         if (*cp == ' ')
  81                 cp++;
  82
  83         for (u = 1; u < strlen(si_units); u++)
  84                 if (*cp == si_units[u]) {
  85                         cp++;
  86                         goto got_unit;
  87                 }
  88
  89         for (u = 0; u < ARRAY_SIZE(units_2); u++)
  90                 if (!strncmp(cp, units_2[u], strlen(units_2[u]))) {
  91                         cp += strlen(units_2[u]);
  92                         goto got_unit;
  93                 }
  94
  95         for (u = 0; u < ARRAY_SIZE(units_10); u++)
  96                 if (!strncmp(cp, units_10[u], strlen(units_10[u]))) {
  97                         cp += strlen(units_10[u]);
  98                         base = 1000;
  99                         goto got_unit;
 100                 }
 101
 102         *res = 1;
 103         return 0;
 104 got_unit:
 105         ret = bch2_pow(base, u, res);
 106         if (ret)
 107                 return ret;
 108
 109         return cp - start;
 110 }
 111
 112 #define parse_or_ret(cp, _f)                    \
 113 do {                                            \
 114         int ret = _f;                           \
 115         if (ret < 0)                            \
 116                 return ret;                     \
 117         cp += ret;                              \
 118 } while (0)
 119
 120 static int __bch2_strtou64_h(const char *cp, u64 *res)
 121 {
 122         const char *start = cp;
 123         u64 v = 0, b, f_n = 0, f_d = 1;
 124         int ret;
 125
 126         parse_or_ret(cp, parse_u64(cp, &v));
 127
 128         if (*cp == '.') {
 129                 cp++;
 130                 ret = parse_u64(cp, &f_n);
 131                 if (ret < 0)
 132                         return ret;
 133                 cp += ret;
 134
 135                 ret = bch2_pow(10, ret, &f_d);
 136                 if (ret)
 137                         return ret;
 138         }
 139
 140         parse_or_ret(cp, parse_unit_suffix(cp, &b));
 141
 142         if (v > div_u64(U64_MAX, b))
 143                 return -ERANGE;
 144         v *= b;
 145
 146         if (f_n > div_u64(U64_MAX, b))
 147                 return -ERANGE;
 148
 149         f_n = div_u64(f_n * b, f_d);
 150         if (v + f_n < v)
 151                 return -ERANGE;
 152         v += f_n;
 153
 154         *res = v;
 155         return cp - start;
 156 }
 157
 158 static int __bch2_strtoh(const char *cp, u64 *res,
 159                          u64 t_max, bool t_signed)
 160 {
 161         bool positive = *cp != '-';
 162         u64 v = 0;
 163
 164         if (*cp == '+' || *cp == '-')
 165                 cp++;
 166
 167         parse_or_ret(cp, __bch2_strtou64_h(cp, &v));
 168
 169         if (*cp == '\n')
 170                 cp++;
 171         if (*cp)
 172                 return -EINVAL;
 173
 174         if (positive) {
 175                 if (v > t_max)
 176                         return -ERANGE;
 177         } else {
 178                 if (v && !t_signed)
 179                         return -ERANGE;
 180
 181                 if (v > t_max + 1)
 182                         return -ERANGE;
 183                 v = -v;
 184         }
 185
 186         *res = v;
 187         return 0;
 188 }
 189
 190 #define STRTO_H(name, type)                                     \
 191 int bch2_ ## name ## _h(const char *cp, type *res)              \
 192 {                                                               \
 193         u64 v = 0;                                              \
 194         int ret = __bch2_strtoh(cp, &v, ANYSINT_MAX(type),      \
 195                         ANYSINT_MAX(type) != ((type) ~0ULL));   \
 196         *res = v;                                               \
 197         return ret;                                             \
 198 }
 199
 200 STRTO_H(strtoint, int)
 201 STRTO_H(strtouint, unsigned int)
 202 STRTO_H(strtoll, long long)
 203 STRTO_H(strtoull, unsigned long long)
 204 STRTO_H(strtou64, u64)
 205
 206 u64 bch2_read_flag_list(char *opt, const char * const list[])
 207 {
 208         u64 ret = 0;
 209         char *p, *s, *d = kstrdup(opt, GFP_KERNEL);
 210
 211         if (!d)
 212                 return -ENOMEM;
 213
 214         s = strim(d);
 215
 216         while ((p = strsep(&s, ","))) {
 217                 int flag = match_string(list, -1, p);
 218                 if (flag < 0) {
 219                         ret = -1;
 220                         break;
 221                 }
 222
 223                 ret |= 1 << flag;
 224         }
 225
 226         kfree(d);
 227
 228         return ret;
 229 }
 230
 231 bool bch2_is_zero(const void *_p, size_t n)
 232 {
 233         const char *p = _p;
 234         size_t i;
 235
 236         for (i = 0; i < n; i++)
 237                 if (p[i])
 238                         return false;
 239         return true;
 240 }
 241
 242 static void bch2_quantiles_update(struct quantiles *q, u64 v)
 243 {
 244         unsigned i = 0;
 245
 246         while (i < ARRAY_SIZE(q->entries)) {
 247                 struct quantile_entry *e = q->entries + i;
 248
 249                 if (unlikely(!e->step)) {
 250                         e->m = v;
 251                         e->step = max_t(unsigned, v / 2, 1024);
 252                 } else if (e->m > v) {
 253                         e->m = e->m >= e->step
 254                                 ? e->m - e->step
 255                                 : 0;
 256                 } else if (e->m < v) {
 257                         e->m = e->m + e->step > e->m
 258                                 ? e->m + e->step
 259                                 : U32_MAX;
 260                 }
 261
 262                 if ((e->m > v ? e->m - v : v - e->m) < e->step)
 263                         e->step = max_t(unsigned, e->step / 2, 1);
 264
 265                 if (v >= e->m)
 266                         break;
 267
 268                 i = eytzinger0_child(i, v > e->m);
 269         }
 270 }
 271
 272 void bch2_prt_u64_binary(struct printbuf *out, u64 v, unsigned nr_bits)
 273 {
 274         while (nr_bits)
 275                 prt_char(out, '0' + ((v >> --nr_bits) & 1));
 276 }
 277
 278 void bch2_print_string_as_lines(const char *prefix, const char *lines)
 279 {
 280         const char *p;
 281
 282         if (!lines) {
 283                 printk("%s (null)\n", prefix);
 284                 return;
 285         }
 286
 287         console_lock();
 288         while (1) {
 289                 p = strchrnul(lines, '\n');
 290                 printk("%s%.*s\n", prefix, (int) (p - lines), lines);
 291                 if (!*p)
 292                         break;
 293                 lines = p + 1;
 294                 prefix = KERN_CONT;
 295         }
 296         console_unlock();
 297 }
 298
 299 /* time stats: */
 300
 301 static void bch2_time_stats_update_one(struct time_stats *stats,
 302                                        u64 start, u64 end)
 303 {
 304         u64 duration, freq;
 305
 306         duration        = time_after64(end, start)
 307                 ? end - start : 0;
 308         freq            = time_after64(end, stats->last_event)
 309                 ? end - stats->last_event : 0;
 310
 311         stats->count++;
 312
 313         stats->average_duration = stats->average_duration
 314                 ? ewma_add(stats->average_duration, duration, 6)
 315                 : duration;
 316
 317         stats->average_frequency = stats->average_frequency
 318                 ? ewma_add(stats->average_frequency, freq, 6)
 319                 : freq;
 320
 321         stats->max_duration = max(stats->max_duration, duration);
 322
 323         stats->last_event = end;
 324
 325         bch2_quantiles_update(&stats->quantiles, duration);
 326 }
 327
 328 void __bch2_time_stats_update(struct time_stats *stats, u64 start, u64 end)
 329 {
 330         unsigned long flags;
 331
 332         if (!stats->buffer) {
 333                 spin_lock_irqsave(&stats->lock, flags);
 334                 bch2_time_stats_update_one(stats, start, end);
 335
 336                 if (stats->average_frequency < 32 &&
 337                     stats->count > 1024)
 338                         stats->buffer =
 339                                 alloc_percpu_gfp(struct time_stat_buffer,
 340                                                  GFP_ATOMIC);
 341                 spin_unlock_irqrestore(&stats->lock, flags);
 342         } else {
 343                 struct time_stat_buffer_entry *i;
 344                 struct time_stat_buffer *b;
 345
 346                 preempt_disable();
 347                 b = this_cpu_ptr(stats->buffer);
 348
 349                 BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
 350                 b->entries[b->nr++] = (struct time_stat_buffer_entry) {
 351                         .start = start,
 352                         .end = end
 353                 };
 354
 355                 if (b->nr == ARRAY_SIZE(b->entries)) {
 356                         spin_lock_irqsave(&stats->lock, flags);
 357                         for (i = b->entries;
 358                              i < b->entries + ARRAY_SIZE(b->entries);
 359                              i++)
 360                                 bch2_time_stats_update_one(stats, i->start, i->end);
 361                         spin_unlock_irqrestore(&stats->lock, flags);
 362
 363                         b->nr = 0;
 364                 }
 365
 366                 preempt_enable();
 367         }
 368 }
 369
 370 static const struct time_unit {
 371         const char      *name;
 372         u32             nsecs;
 373 } time_units[] = {
 374         { "ns",         1               },
 375         { "us",         NSEC_PER_USEC   },
 376         { "ms",         NSEC_PER_MSEC   },
 377         { "sec",        NSEC_PER_SEC    },
 378 };
 379
 380 static const struct time_unit *pick_time_units(u64 ns)
 381 {
 382         const struct time_unit *u;
 383
 384         for (u = time_units;
 385              u + 1 < time_units + ARRAY_SIZE(time_units) &&
 386              ns >= u[1].nsecs << 1;
 387              u++)
 388                 ;
 389
 390         return u;
 391 }
 392
 393 static void pr_time_units(struct printbuf *out, u64 ns)
 394 {
 395         const struct time_unit *u = pick_time_units(ns);
 396
 397         prt_printf(out, "%llu %s", div_u64(ns, u->nsecs), u->name);
 398 }
 399
 400 void bch2_time_stats_to_text(struct printbuf *out, struct time_stats *stats)
 401 {
 402         const struct time_unit *u;
 403         u64 freq = READ_ONCE(stats->average_frequency);
 404         u64 q, last_q = 0;
 405         int i;
 406
 407         prt_printf(out, "count:\t\t%llu",
 408                          stats->count);
 409         prt_newline(out);
 410         prt_printf(out, "rate:\t\t%llu/sec",
 411                freq ?  div64_u64(NSEC_PER_SEC, freq) : 0);
 412         prt_newline(out);
 413
 414         prt_printf(out, "frequency:\t");
 415         pr_time_units(out, freq);
 416
 417         prt_newline(out);
 418         prt_printf(out, "avg duration:\t");
 419         pr_time_units(out, stats->average_duration);
 420
 421         prt_newline(out);
 422         prt_printf(out, "max duration:\t");
 423         pr_time_units(out, stats->max_duration);
 424
 425         i = eytzinger0_first(NR_QUANTILES);
 426         u = pick_time_units(stats->quantiles.entries[i].m);
 427
 428         prt_newline(out);
 429         prt_printf(out, "quantiles (%s):\t", u->name);
 430         eytzinger0_for_each(i, NR_QUANTILES) {
 431                 bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1;
 432
 433                 q = max(stats->quantiles.entries[i].m, last_q);
 434                 prt_printf(out, "%llu ",
 435                        div_u64(q, u->nsecs));
 436                 if (is_last)
 437                         prt_newline(out);
 438                 last_q = q;
 439         }
 440 }
 441
 442 void bch2_time_stats_exit(struct time_stats *stats)
 443 {
 444         free_percpu(stats->buffer);
 445 }
 446
 447 void bch2_time_stats_init(struct time_stats *stats)
 448 {
 449         memset(stats, 0, sizeof(*stats));
 450         spin_lock_init(&stats->lock);
 451 }
 452
 453 /* ratelimit: */
 454
 455 /**
 456  * bch2_ratelimit_delay() - return how long to delay until the next time to do
 457  * some work
 458  *
 459  * @d - the struct bch_ratelimit to update
 460  *
 461  * Returns the amount of time to delay by, in jiffies
 462  */
 463 u64 bch2_ratelimit_delay(struct bch_ratelimit *d)
 464 {
 465         u64 now = local_clock();
 466
 467         return time_after64(d->next, now)
 468                 ? nsecs_to_jiffies(d->next - now)
 469                 : 0;
 470 }
 471
 472 /**
 473  * bch2_ratelimit_increment() - increment @d by the amount of work done
 474  *
 475  * @d - the struct bch_ratelimit to update
 476  * @done - the amount of work done, in arbitrary units
 477  */
 478 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done)
 479 {
 480         u64 now = local_clock();
 481
 482         d->next += div_u64(done * NSEC_PER_SEC, d->rate);
 483
 484         if (time_before64(now + NSEC_PER_SEC, d->next))
 485                 d->next = now + NSEC_PER_SEC;
 486
 487         if (time_after64(now - NSEC_PER_SEC * 2, d->next))
 488                 d->next = now - NSEC_PER_SEC * 2;
 489 }
 490
 491 /* pd controller: */
 492
 493 /*
 494  * Updates pd_controller. Attempts to scale inputed values to units per second.
 495  * @target: desired value
 496  * @actual: current value
 497  *
 498  * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing
 499  * it makes actual go down.
 500  */
 501 void bch2_pd_controller_update(struct bch_pd_controller *pd,
 502                               s64 target, s64 actual, int sign)
 503 {
 504         s64 proportional, derivative, change;
 505
 506         unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ;
 507
 508         if (seconds_since_update == 0)
 509                 return;
 510
 511         pd->last_update = jiffies;
 512
 513         proportional = actual - target;
 514         proportional *= seconds_since_update;
 515         proportional = div_s64(proportional, pd->p_term_inverse);
 516
 517         derivative = actual - pd->last_actual;
 518         derivative = div_s64(derivative, seconds_since_update);
 519         derivative = ewma_add(pd->smoothed_derivative, derivative,
 520                               (pd->d_term / seconds_since_update) ?: 1);
 521         derivative = derivative * pd->d_term;
 522         derivative = div_s64(derivative, pd->p_term_inverse);
 523
 524         change = proportional + derivative;
 525
 526         /* Don't increase rate if not keeping up */
 527         if (change > 0 &&
 528             pd->backpressure &&
 529             time_after64(local_clock(),
 530                          pd->rate.next + NSEC_PER_MSEC))
 531                 change = 0;
 532
 533         change *= (sign * -1);
 534
 535         pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change,
 536                                 1, UINT_MAX);
 537
 538         pd->last_actual         = actual;
 539         pd->last_derivative     = derivative;
 540         pd->last_proportional   = proportional;
 541         pd->last_change         = change;
 542         pd->last_target         = target;
 543 }
 544
 545 void bch2_pd_controller_init(struct bch_pd_controller *pd)
 546 {
 547         pd->rate.rate           = 1024;
 548         pd->last_update         = jiffies;
 549         pd->p_term_inverse      = 6000;
 550         pd->d_term              = 30;
 551         pd->d_smooth            = pd->d_term;
 552         pd->backpressure        = 1;
 553 }
 554
 555 void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd)
 556 {
 557         if (!out->nr_tabstops)
 558                 printbuf_tabstop_push(out, 20);
 559
 560         prt_printf(out, "rate:");
 561         prt_tab(out);
 562         prt_human_readable_s64(out, pd->rate.rate);
 563         prt_newline(out);
 564
 565         prt_printf(out, "target:");
 566         prt_tab(out);
 567         prt_human_readable_u64(out, pd->last_target);
 568         prt_newline(out);
 569
 570         prt_printf(out, "actual:");
 571         prt_tab(out);
 572         prt_human_readable_u64(out, pd->last_actual);
 573         prt_newline(out);
 574
 575         prt_printf(out, "proportional:");
 576         prt_tab(out);
 577         prt_human_readable_s64(out, pd->last_proportional);
 578         prt_newline(out);
 579
 580         prt_printf(out, "derivative:");
 581         prt_tab(out);
 582         prt_human_readable_s64(out, pd->last_derivative);
 583         prt_newline(out);
 584
 585         prt_printf(out, "change:");
 586         prt_tab(out);
 587         prt_human_readable_s64(out, pd->last_change);
 588         prt_newline(out);
 589
 590         prt_printf(out, "next io:");
 591         prt_tab(out);
 592         prt_printf(out, "%llims", div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC));
 593         prt_newline(out);
 594 }
 595
 596 /* misc: */
 597
 598 void bch2_bio_map(struct bio *bio, void *base, size_t size)
 599 {
 600         while (size) {
 601                 struct page *page = is_vmalloc_addr(base)
 602                                 ? vmalloc_to_page(base)
 603                                 : virt_to_page(base);
 604                 unsigned offset = offset_in_page(base);
 605                 unsigned len = min_t(size_t, PAGE_SIZE - offset, size);
 606
 607                 BUG_ON(!bio_add_page(bio, page, len, offset));
 608                 size -= len;
 609                 base += len;
 610         }
 611 }
 612
 613 int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask)
 614 {
 615         while (size) {
 616                 struct page *page = alloc_page(gfp_mask);
 617                 unsigned len = min_t(size_t, PAGE_SIZE, size);
 618
 619                 if (!page)
 620                         return -ENOMEM;
 621
 622                 if (unlikely(!bio_add_page(bio, page, len, 0))) {
 623                         __free_page(page);
 624                         break;
 625                 }
 626
 627                 size -= len;
 628         }
 629
 630         return 0;
 631 }
 632
 633 size_t bch2_rand_range(size_t max)
 634 {
 635         size_t rand;
 636
 637         if (!max)
 638                 return 0;
 639
 640         do {
 641                 rand = get_random_long();
 642                 rand &= roundup_pow_of_two(max) - 1;
 643         } while (rand >= max);
 644
 645         return rand;
 646 }
 647
 648 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src)
 649 {
 650         struct bio_vec bv;
 651         struct bvec_iter iter;
 652
 653         __bio_for_each_segment(bv, dst, iter, dst_iter) {
 654                 void *dstp = kmap_atomic(bv.bv_page);
 655                 memcpy(dstp + bv.bv_offset, src, bv.bv_len);
 656                 kunmap_atomic(dstp);
 657
 658                 src += bv.bv_len;
 659         }
 660 }
 661
 662 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
 663 {
 664         struct bio_vec bv;
 665         struct bvec_iter iter;
 666
 667         __bio_for_each_segment(bv, src, iter, src_iter) {
 668                 void *srcp = kmap_atomic(bv.bv_page);
 669                 memcpy(dst, srcp + bv.bv_offset, bv.bv_len);
 670                 kunmap_atomic(srcp);
 671
 672                 dst += bv.bv_len;
 673         }
 674 }
 675
 676 #include "eytzinger.h"
 677
 678 static int alignment_ok(const void *base, size_t align)
 679 {
 680         return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
 681                 ((unsigned long)base & (align - 1)) == 0;
 682 }
 683
 684 static void u32_swap(void *a, void *b, size_t size)
 685 {
 686         u32 t = *(u32 *)a;
 687         *(u32 *)a = *(u32 *)b;
 688         *(u32 *)b = t;
 689 }
 690
 691 static void u64_swap(void *a, void *b, size_t size)
 692 {
 693         u64 t = *(u64 *)a;
 694         *(u64 *)a = *(u64 *)b;
 695         *(u64 *)b = t;
 696 }
 697
 698 static void generic_swap(void *a, void *b, size_t size)
 699 {
 700         char t;
 701
 702         do {
 703                 t = *(char *)a;
 704                 *(char *)a++ = *(char *)b;
 705                 *(char *)b++ = t;
 706         } while (--size > 0);
 707 }
 708
 709 static inline int do_cmp(void *base, size_t n, size_t size,
 710                          int (*cmp_func)(const void *, const void *, size_t),
 711                          size_t l, size_t r)
 712 {
 713         return cmp_func(base + inorder_to_eytzinger0(l, n) * size,
 714                         base + inorder_to_eytzinger0(r, n) * size,
 715                         size);
 716 }
 717
 718 static inline void do_swap(void *base, size_t n, size_t size,
 719                            void (*swap_func)(void *, void *, size_t),
 720                            size_t l, size_t r)
 721 {
 722         swap_func(base + inorder_to_eytzinger0(l, n) * size,
 723                   base + inorder_to_eytzinger0(r, n) * size,
 724                   size);
 725 }
 726
 727 void eytzinger0_sort(void *base, size_t n, size_t size,
 728                      int (*cmp_func)(const void *, const void *, size_t),
 729                      void (*swap_func)(void *, void *, size_t))
 730 {
 731         int i, c, r;
 732
 733         if (!swap_func) {
 734                 if (size == 4 && alignment_ok(base, 4))
 735                         swap_func = u32_swap;
 736                 else if (size == 8 && alignment_ok(base, 8))
 737                         swap_func = u64_swap;
 738                 else
 739                         swap_func = generic_swap;
 740         }
 741
 742         /* heapify */
 743         for (i = n / 2 - 1; i >= 0; --i) {
 744                 for (r = i; r * 2 + 1 < n; r = c) {
 745                         c = r * 2 + 1;
 746
 747                         if (c + 1 < n &&
 748                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 749                                 c++;
 750
 751                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 752                                 break;
 753
 754                         do_swap(base, n, size, swap_func, r, c);
 755                 }
 756         }
 757
 758         /* sort */
 759         for (i = n - 1; i > 0; --i) {
 760                 do_swap(base, n, size, swap_func, 0, i);
 761
 762                 for (r = 0; r * 2 + 1 < i; r = c) {
 763                         c = r * 2 + 1;
 764
 765                         if (c + 1 < i &&
 766                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 767                                 c++;
 768
 769                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 770                                 break;
 771
 772                         do_swap(base, n, size, swap_func, r, c);
 773                 }
 774         }
 775 }
 776
 777 void sort_cmp_size(void *base, size_t num, size_t size,
 778           int (*cmp_func)(const void *, const void *, size_t),
 779           void (*swap_func)(void *, void *, size_t size))
 780 {
 781         /* pre-scale counters for performance */
 782         int i = (num/2 - 1) * size, n = num * size, c, r;
 783
 784         if (!swap_func) {
 785                 if (size == 4 && alignment_ok(base, 4))
 786                         swap_func = u32_swap;
 787                 else if (size == 8 && alignment_ok(base, 8))
 788                         swap_func = u64_swap;
 789                 else
 790                         swap_func = generic_swap;
 791         }
 792
 793         /* heapify */
 794         for ( ; i >= 0; i -= size) {
 795                 for (r = i; r * 2 + size < n; r  = c) {
 796                         c = r * 2 + size;
 797                         if (c < n - size &&
 798                             cmp_func(base + c, base + c + size, size) < 0)
 799                                 c += size;
 800                         if (cmp_func(base + r, base + c, size) >= 0)
 801                                 break;
 802                         swap_func(base + r, base + c, size);
 803                 }
 804         }
 805
 806         /* sort */
 807         for (i = n - size; i > 0; i -= size) {
 808                 swap_func(base, base + i, size);
 809                 for (r = 0; r * 2 + size < i; r = c) {
 810                         c = r * 2 + size;
 811                         if (c < i - size &&
 812                             cmp_func(base + c, base + c + size, size) < 0)
 813                                 c += size;
 814                         if (cmp_func(base + r, base + c, size) >= 0)
 815                                 break;
 816                         swap_func(base + r, base + c, size);
 817                 }
 818         }
 819 }
 820
 821 static void mempool_free_vp(void *element, void *pool_data)
 822 {
 823         size_t size = (size_t) pool_data;
 824
 825         vpfree(element, size);
 826 }
 827
 828 static void *mempool_alloc_vp(gfp_t gfp_mask, void *pool_data)
 829 {
 830         size_t size = (size_t) pool_data;
 831
 832         return vpmalloc(size, gfp_mask);
 833 }
 834
 835 int mempool_init_kvpmalloc_pool(mempool_t *pool, int min_nr, size_t size)
 836 {
 837         return size < PAGE_SIZE
 838                 ? mempool_init_kmalloc_pool(pool, min_nr, size)
 839                 : mempool_init(pool, min_nr, mempool_alloc_vp,
 840                                mempool_free_vp, (void *) size);
 841 }
 842
 843 #if 0
 844 void eytzinger1_test(void)
 845 {
 846         unsigned inorder, eytz, size;
 847
 848         pr_info("1 based eytzinger test:");
 849
 850         for (size = 2;
 851              size < 65536;
 852              size++) {
 853                 unsigned extra = eytzinger1_extra(size);
 854
 855                 if (!(size % 4096))
 856                         pr_info("tree size %u", size);
 857
 858                 BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size));
 859                 BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size));
 860
 861                 BUG_ON(eytzinger1_prev(eytzinger1_first(size), size)    != 0);
 862                 BUG_ON(eytzinger1_next(eytzinger1_last(size), size)     != 0);
 863
 864                 inorder = 1;
 865                 eytzinger1_for_each(eytz, size) {
 866                         BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz);
 867                         BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder);
 868                         BUG_ON(eytz != eytzinger1_last(size) &&
 869                                eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz);
 870
 871                         inorder++;
 872                 }
 873         }
 874 }
 875
 876 void eytzinger0_test(void)
 877 {
 878
 879         unsigned inorder, eytz, size;
 880
 881         pr_info("0 based eytzinger test:");
 882
 883         for (size = 1;
 884              size < 65536;
 885              size++) {
 886                 unsigned extra = eytzinger0_extra(size);
 887
 888                 if (!(size % 4096))
 889                         pr_info("tree size %u", size);
 890
 891                 BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size));
 892                 BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size));
 893
 894                 BUG_ON(eytzinger0_prev(eytzinger0_first(size), size)    != -1);
 895                 BUG_ON(eytzinger0_next(eytzinger0_last(size), size)     != -1);
 896
 897                 inorder = 0;
 898                 eytzinger0_for_each(eytz, size) {
 899                         BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz);
 900                         BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder);
 901                         BUG_ON(eytz != eytzinger0_last(size) &&
 902                                eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz);
 903
 904                         inorder++;
 905                 }
 906         }
 907 }
 908
 909 static inline int cmp_u16(const void *_l, const void *_r, size_t size)
 910 {
 911         const u16 *l = _l, *r = _r;
 912
 913         return (*l > *r) - (*r - *l);
 914 }
 915
 916 static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search)
 917 {
 918         int i, c1 = -1, c2 = -1;
 919         ssize_t r;
 920
 921         r = eytzinger0_find_le(test_array, nr,
 922                                sizeof(test_array[0]),
 923                                cmp_u16, &search);
 924         if (r >= 0)
 925                 c1 = test_array[r];
 926
 927         for (i = 0; i < nr; i++)
 928                 if (test_array[i] <= search && test_array[i] > c2)
 929                         c2 = test_array[i];
 930
 931         if (c1 != c2) {
 932                 eytzinger0_for_each(i, nr)
 933                         pr_info("[%3u] = %12u", i, test_array[i]);
 934                 pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i",
 935                         i, r, c1, c2);
 936         }
 937 }
 938
 939 void eytzinger0_find_test(void)
 940 {
 941         unsigned i, nr, allocated = 1 << 12;
 942         u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL);
 943
 944         for (nr = 1; nr < allocated; nr++) {
 945                 pr_info("testing %u elems", nr);
 946
 947                 get_random_bytes(test_array, nr * sizeof(test_array[0]));
 948                 eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL);
 949
 950                 /* verify array is sorted correctly: */
 951                 eytzinger0_for_each(i, nr)
 952                         BUG_ON(i != eytzinger0_last(nr) &&
 953                                test_array[i] > test_array[eytzinger0_next(i, nr)]);
 954
 955                 for (i = 0; i < U16_MAX; i += 1 << 12)
 956                         eytzinger0_find_test_val(test_array, nr, i);
 957
 958                 for (i = 0; i < nr; i++) {
 959                         eytzinger0_find_test_val(test_array, nr, test_array[i] - 1);
 960                         eytzinger0_find_test_val(test_array, nr, test_array[i]);
 961                         eytzinger0_find_test_val(test_array, nr, test_array[i] + 1);
 962                 }
 963         }
 964
 965         kfree(test_array);
 966 }
 967 #endif
 968
 969 /*
 970  * Accumulate percpu counters onto one cpu's copy - only valid when access
 971  * against any percpu counter is guarded against
 972  */
 973 u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr)
 974 {
 975         u64 *ret;
 976         int cpu;
 977
 978         /* access to pcpu vars has to be blocked by other locking */
 979         preempt_disable();
 980         ret = this_cpu_ptr(p);
 981         preempt_enable();
 982
 983         for_each_possible_cpu(cpu) {
 984                 u64 *i = per_cpu_ptr(p, cpu);
 985
 986                 if (i != ret) {
 987                         acc_u64s(ret, i, nr);
 988                         memset(i, 0, nr * sizeof(u64));
 989                 }
 990         }
 991
 992         return ret;
 993 }