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

   1 /*
   2  * random utiility code, for bcache but in theory not specific to bcache
   3  *
   4  * Copyright 2010, 2011 Kent Overstreet <kent.overstreet@gmail.com>
   5  * Copyright 2012 Google, Inc.
   6  */
   7
   8 #include <linux/bio.h>
   9 #include <linux/blkdev.h>
  10 #include <linux/ctype.h>
  11 #include <linux/debugfs.h>
  12 #include <linux/freezer.h>
  13 #include <linux/kthread.h>
  14 #include <linux/log2.h>
  15 #include <linux/math64.h>
  16 #include <linux/random.h>
  17 #include <linux/seq_file.h>
  18 #include <linux/string.h>
  19 #include <linux/types.h>
  20 #include <linux/sched/clock.h>
  21
  22 #include "util.h"
  23
  24 #define simple_strtoint(c, end, base)   simple_strtol(c, end, base)
  25 #define simple_strtouint(c, end, base)  simple_strtoul(c, end, base)
  26
  27 #define STRTO_H(name, type)                                     \
  28 int bch2_ ## name ## _h(const char *cp, type *res)              \
  29 {                                                               \
  30         int u = 0;                                              \
  31         char *e;                                                \
  32         type i = simple_ ## name(cp, &e, 10);                   \
  33                                                                 \
  34         switch (tolower(*e)) {                                  \
  35         default:                                                \
  36                 return -EINVAL;                                 \
  37         case 'y':                                               \
  38         case 'z':                                               \
  39                 u++;                                            \
  40         case 'e':                                               \
  41                 u++;                                            \
  42         case 'p':                                               \
  43                 u++;                                            \
  44         case 't':                                               \
  45                 u++;                                            \
  46         case 'g':                                               \
  47                 u++;                                            \
  48         case 'm':                                               \
  49                 u++;                                            \
  50         case 'k':                                               \
  51                 u++;                                            \
  52                 if (e++ == cp)                                  \
  53                         return -EINVAL;                         \
  54         case '\n':                                              \
  55         case '\0':                                              \
  56                 if (*e == '\n')                                 \
  57                         e++;                                    \
  58         }                                                       \
  59                                                                 \
  60         if (*e)                                                 \
  61                 return -EINVAL;                                 \
  62                                                                 \
  63         while (u--) {                                           \
  64                 if ((type) ~0 > 0 &&                            \
  65                     (type) ~0 / 1024 <= i)                      \
  66                         return -EINVAL;                         \
  67                 if ((i > 0 && ANYSINT_MAX(type) / 1024 < i) ||  \
  68                     (i < 0 && -ANYSINT_MAX(type) / 1024 > i))   \
  69                         return -EINVAL;                         \
  70                 i *= 1024;                                      \
  71         }                                                       \
  72                                                                 \
  73         *res = i;                                               \
  74         return 0;                                               \
  75 }                                                               \
  76
  77 STRTO_H(strtoint, int)
  78 STRTO_H(strtouint, unsigned int)
  79 STRTO_H(strtoll, long long)
  80 STRTO_H(strtoull, unsigned long long)
  81
  82 ssize_t bch2_hprint(char *buf, s64 v)
  83 {
  84         static const char units[] = "?kMGTPEZY";
  85         char dec[4] = "";
  86         int u, t = 0;
  87
  88         for (u = 0; v >= 1024 || v <= -1024; u++) {
  89                 t = v & ~(~0U << 10);
  90                 v >>= 10;
  91         }
  92
  93         if (!u)
  94                 return sprintf(buf, "%lli", v);
  95
  96         /*
  97          * 103 is magic: t is in the range [-1023, 1023] and we want
  98          * to turn it into [-9, 9]
  99          */
 100         if (v < 100 && v > -100)
 101                 scnprintf(dec, sizeof(dec), ".%i", t / 103);
 102
 103         return sprintf(buf, "%lli%s%c", v, dec, units[u]);
 104 }
 105
 106 ssize_t bch2_scnprint_string_list(char *buf, size_t size,
 107                                   const char * const list[],
 108                                   size_t selected)
 109 {
 110         char *out = buf;
 111         size_t i;
 112
 113         if (size)
 114                 *out = '\0';
 115
 116         for (i = 0; list[i]; i++)
 117                 out += scnprintf(out, buf + size - out,
 118                                  i == selected ? "[%s] " : "%s ", list[i]);
 119
 120         if (out != buf)
 121                 *--out = '\0';
 122
 123         return out - buf;
 124 }
 125
 126 ssize_t bch2_read_string_list(const char *buf, const char * const list[])
 127 {
 128         size_t i, len;
 129
 130         buf = skip_spaces(buf);
 131
 132         len = strlen(buf);
 133         while (len && isspace(buf[len - 1]))
 134                 --len;
 135
 136         for (i = 0; list[i]; i++)
 137                 if (strlen(list[i]) == len &&
 138                     !memcmp(buf, list[i], len))
 139                         break;
 140
 141         return list[i] ? i : -EINVAL;
 142 }
 143
 144 ssize_t bch2_scnprint_flag_list(char *buf, size_t size,
 145                                 const char * const list[], u64 flags)
 146 {
 147         char *out = buf, *end = buf + size;
 148         unsigned bit, nr = 0;
 149
 150         while (list[nr])
 151                 nr++;
 152
 153         if (size)
 154                 *out = '\0';
 155
 156         while (flags && (bit = __ffs(flags)) < nr) {
 157                 out += scnprintf(out, end - out, "%s,", list[bit]);
 158                 flags ^= 1 << bit;
 159         }
 160
 161         if (out != buf)
 162                 *--out = '\0';
 163
 164         return out - buf;
 165 }
 166
 167 u64 bch2_read_flag_list(char *opt, const char * const list[])
 168 {
 169         u64 ret = 0;
 170         char *p, *s, *d = kstrndup(opt, PAGE_SIZE - 1, GFP_KERNEL);
 171
 172         if (!d)
 173                 return -ENOMEM;
 174
 175         s = strim(d);
 176
 177         while ((p = strsep(&s, ","))) {
 178                 int flag = bch2_read_string_list(p, list);
 179                 if (flag < 0) {
 180                         ret = -1;
 181                         break;
 182                 }
 183
 184                 ret |= 1 << flag;
 185         }
 186
 187         kfree(d);
 188
 189         return ret;
 190 }
 191
 192 bool bch2_is_zero(const void *_p, size_t n)
 193 {
 194         const char *p = _p;
 195         size_t i;
 196
 197         for (i = 0; i < n; i++)
 198                 if (p[i])
 199                         return false;
 200         return true;
 201 }
 202
 203 void bch2_time_stats_clear(struct time_stats *stats)
 204 {
 205         spin_lock(&stats->lock);
 206
 207         stats->count = 0;
 208         stats->last_duration = 0;
 209         stats->max_duration = 0;
 210         stats->average_duration = 0;
 211         stats->average_frequency = 0;
 212         stats->last = 0;
 213
 214         spin_unlock(&stats->lock);
 215 }
 216
 217 void __bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 218 {
 219         u64 now, duration, last;
 220
 221         stats->count++;
 222
 223         now             = local_clock();
 224         duration        = time_after64(now, start_time)
 225                 ? now - start_time : 0;
 226         last            = time_after64(now, stats->last)
 227                 ? now - stats->last : 0;
 228
 229         stats->last_duration = duration;
 230         stats->max_duration = max(stats->max_duration, duration);
 231
 232         if (stats->last) {
 233                 stats->average_duration = ewma_add(stats->average_duration,
 234                                                    duration << 8, 3);
 235
 236                 if (stats->average_frequency)
 237                         stats->average_frequency =
 238                                 ewma_add(stats->average_frequency,
 239                                          last << 8, 3);
 240                 else
 241                         stats->average_frequency  = last << 8;
 242         } else {
 243                 stats->average_duration = duration << 8;
 244         }
 245
 246         stats->last = now ?: 1;
 247 }
 248
 249 void bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 250 {
 251         spin_lock(&stats->lock);
 252         __bch2_time_stats_update(stats, start_time);
 253         spin_unlock(&stats->lock);
 254 }
 255
 256 /**
 257  * bch2_ratelimit_delay() - return how long to delay until the next time to do
 258  * some work
 259  *
 260  * @d - the struct bch_ratelimit to update
 261  *
 262  * Returns the amount of time to delay by, in jiffies
 263  */
 264 u64 bch2_ratelimit_delay(struct bch_ratelimit *d)
 265 {
 266         u64 now = local_clock();
 267
 268         return time_after64(d->next, now)
 269                 ? nsecs_to_jiffies(d->next - now)
 270                 : 0;
 271 }
 272
 273 /**
 274  * bch2_ratelimit_increment() - increment @d by the amount of work done
 275  *
 276  * @d - the struct bch_ratelimit to update
 277  * @done - the amount of work done, in arbitrary units
 278  */
 279 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done)
 280 {
 281         u64 now = local_clock();
 282
 283         d->next += div_u64(done * NSEC_PER_SEC, d->rate);
 284
 285         if (time_before64(now + NSEC_PER_SEC, d->next))
 286                 d->next = now + NSEC_PER_SEC;
 287
 288         if (time_after64(now - NSEC_PER_SEC * 2, d->next))
 289                 d->next = now - NSEC_PER_SEC * 2;
 290 }
 291
 292 int bch2_ratelimit_wait_freezable_stoppable(struct bch_ratelimit *d)
 293 {
 294         while (1) {
 295                 u64 delay = bch2_ratelimit_delay(d);
 296
 297                 if (delay)
 298                         set_current_state(TASK_INTERRUPTIBLE);
 299
 300                 if (kthread_should_stop())
 301                         return 1;
 302
 303                 if (!delay)
 304                         return 0;
 305
 306                 schedule_timeout(delay);
 307                 try_to_freeze();
 308         }
 309 }
 310
 311 /*
 312  * Updates pd_controller. Attempts to scale inputed values to units per second.
 313  * @target: desired value
 314  * @actual: current value
 315  *
 316  * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing
 317  * it makes actual go down.
 318  */
 319 void bch2_pd_controller_update(struct bch_pd_controller *pd,
 320                               s64 target, s64 actual, int sign)
 321 {
 322         s64 proportional, derivative, change;
 323
 324         unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ;
 325
 326         if (seconds_since_update == 0)
 327                 return;
 328
 329         pd->last_update = jiffies;
 330
 331         proportional = actual - target;
 332         proportional *= seconds_since_update;
 333         proportional = div_s64(proportional, pd->p_term_inverse);
 334
 335         derivative = actual - pd->last_actual;
 336         derivative = div_s64(derivative, seconds_since_update);
 337         derivative = ewma_add(pd->smoothed_derivative, derivative,
 338                               (pd->d_term / seconds_since_update) ?: 1);
 339         derivative = derivative * pd->d_term;
 340         derivative = div_s64(derivative, pd->p_term_inverse);
 341
 342         change = proportional + derivative;
 343
 344         /* Don't increase rate if not keeping up */
 345         if (change > 0 &&
 346             pd->backpressure &&
 347             time_after64(local_clock(),
 348                          pd->rate.next + NSEC_PER_MSEC))
 349                 change = 0;
 350
 351         change *= (sign * -1);
 352
 353         pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change,
 354                                 1, UINT_MAX);
 355
 356         pd->last_actual         = actual;
 357         pd->last_derivative     = derivative;
 358         pd->last_proportional   = proportional;
 359         pd->last_change         = change;
 360         pd->last_target         = target;
 361 }
 362
 363 void bch2_pd_controller_init(struct bch_pd_controller *pd)
 364 {
 365         pd->rate.rate           = 1024;
 366         pd->last_update         = jiffies;
 367         pd->p_term_inverse      = 6000;
 368         pd->d_term              = 30;
 369         pd->d_smooth            = pd->d_term;
 370         pd->backpressure        = 1;
 371 }
 372
 373 size_t bch2_pd_controller_print_debug(struct bch_pd_controller *pd, char *buf)
 374 {
 375         /* 2^64 - 1 is 20 digits, plus null byte */
 376         char rate[21];
 377         char actual[21];
 378         char target[21];
 379         char proportional[21];
 380         char derivative[21];
 381         char change[21];
 382         s64 next_io;
 383
 384         bch2_hprint(rate,       pd->rate.rate);
 385         bch2_hprint(actual,     pd->last_actual);
 386         bch2_hprint(target,     pd->last_target);
 387         bch2_hprint(proportional, pd->last_proportional);
 388         bch2_hprint(derivative, pd->last_derivative);
 389         bch2_hprint(change,     pd->last_change);
 390
 391         next_io = div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC);
 392
 393         return sprintf(buf,
 394                        "rate:\t\t%s/sec\n"
 395                        "target:\t\t%s\n"
 396                        "actual:\t\t%s\n"
 397                        "proportional:\t%s\n"
 398                        "derivative:\t%s\n"
 399                        "change:\t\t%s/sec\n"
 400                        "next io:\t%llims\n",
 401                        rate, target, actual, proportional,
 402                        derivative, change, next_io);
 403 }
 404
 405 void bch2_bio_map(struct bio *bio, void *base)
 406 {
 407         size_t size = bio->bi_iter.bi_size;
 408         struct bio_vec *bv = bio->bi_io_vec;
 409
 410         BUG_ON(!bio->bi_iter.bi_size);
 411         BUG_ON(bio->bi_vcnt);
 412
 413         bv->bv_offset = base ? offset_in_page(base) : 0;
 414         goto start;
 415
 416         for (; size; bio->bi_vcnt++, bv++) {
 417                 bv->bv_offset   = 0;
 418 start:          bv->bv_len      = min_t(size_t, PAGE_SIZE - bv->bv_offset,
 419                                         size);
 420                 BUG_ON(bio->bi_vcnt >= bio->bi_max_vecs);
 421                 if (base) {
 422                         bv->bv_page = is_vmalloc_addr(base)
 423                                 ? vmalloc_to_page(base)
 424                                 : virt_to_page(base);
 425
 426                         base += bv->bv_len;
 427                 }
 428
 429                 size -= bv->bv_len;
 430         }
 431 }
 432
 433 size_t bch2_rand_range(size_t max)
 434 {
 435         size_t rand;
 436
 437         do {
 438                 get_random_bytes(&rand, sizeof(rand));
 439                 rand &= roundup_pow_of_two(max) - 1;
 440         } while (rand >= max);
 441
 442         return rand;
 443 }
 444
 445 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, void *src)
 446 {
 447         struct bio_vec bv;
 448         struct bvec_iter iter;
 449
 450         __bio_for_each_segment(bv, dst, iter, dst_iter) {
 451                 void *dstp = kmap_atomic(bv.bv_page);
 452                 memcpy(dstp + bv.bv_offset, src, bv.bv_len);
 453                 kunmap_atomic(dstp);
 454
 455                 src += bv.bv_len;
 456         }
 457 }
 458
 459 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
 460 {
 461         struct bio_vec bv;
 462         struct bvec_iter iter;
 463
 464         __bio_for_each_segment(bv, src, iter, src_iter) {
 465                 void *srcp = kmap_atomic(bv.bv_page);
 466                 memcpy(dst, srcp + bv.bv_offset, bv.bv_len);
 467                 kunmap_atomic(srcp);
 468
 469                 dst += bv.bv_len;
 470         }
 471 }
 472
 473 size_t bch_scnmemcpy(char *buf, size_t size, const char *src, size_t len)
 474 {
 475         size_t n;
 476
 477         if (!size)
 478                 return 0;
 479
 480         n = min(size - 1, len);
 481         memcpy(buf, src, n);
 482         buf[n] = '\0';
 483
 484         return n;
 485 }
 486
 487 #include "eytzinger.h"
 488
 489 static int alignment_ok(const void *base, size_t align)
 490 {
 491         return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
 492                 ((unsigned long)base & (align - 1)) == 0;
 493 }
 494
 495 static void u32_swap(void *a, void *b, size_t size)
 496 {
 497         u32 t = *(u32 *)a;
 498         *(u32 *)a = *(u32 *)b;
 499         *(u32 *)b = t;
 500 }
 501
 502 static void u64_swap(void *a, void *b, size_t size)
 503 {
 504         u64 t = *(u64 *)a;
 505         *(u64 *)a = *(u64 *)b;
 506         *(u64 *)b = t;
 507 }
 508
 509 static void generic_swap(void *a, void *b, size_t size)
 510 {
 511         char t;
 512
 513         do {
 514                 t = *(char *)a;
 515                 *(char *)a++ = *(char *)b;
 516                 *(char *)b++ = t;
 517         } while (--size > 0);
 518 }
 519
 520 static inline int do_cmp(void *base, size_t n, size_t size,
 521                          int (*cmp_func)(const void *, const void *, size_t),
 522                          size_t l, size_t r)
 523 {
 524         return cmp_func(base + inorder_to_eytzinger0(l, n) * size,
 525                         base + inorder_to_eytzinger0(r, n) * size,
 526                         size);
 527 }
 528
 529 static inline void do_swap(void *base, size_t n, size_t size,
 530                            void (*swap_func)(void *, void *, size_t),
 531                            size_t l, size_t r)
 532 {
 533         swap_func(base + inorder_to_eytzinger0(l, n) * size,
 534                   base + inorder_to_eytzinger0(r, n) * size,
 535                   size);
 536 }
 537
 538 void eytzinger0_sort(void *base, size_t n, size_t size,
 539                      int (*cmp_func)(const void *, const void *, size_t),
 540                      void (*swap_func)(void *, void *, size_t))
 541 {
 542         int i, c, r;
 543
 544         if (!swap_func) {
 545                 if (size == 4 && alignment_ok(base, 4))
 546                         swap_func = u32_swap;
 547                 else if (size == 8 && alignment_ok(base, 8))
 548                         swap_func = u64_swap;
 549                 else
 550                         swap_func = generic_swap;
 551         }
 552
 553         /* heapify */
 554         for (i = n / 2 - 1; i >= 0; --i) {
 555                 for (r = i; r * 2 + 1 < n; r = c) {
 556                         c = r * 2 + 1;
 557
 558                         if (c + 1 < n &&
 559                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 560                                 c++;
 561
 562                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 563                                 break;
 564
 565                         do_swap(base, n, size, swap_func, r, c);
 566                 }
 567         }
 568
 569         /* sort */
 570         for (i = n - 1; i > 0; --i) {
 571                 do_swap(base, n, size, swap_func, 0, i);
 572
 573                 for (r = 0; r * 2 + 1 < i; r = c) {
 574                         c = r * 2 + 1;
 575
 576                         if (c + 1 < i &&
 577                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 578                                 c++;
 579
 580                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 581                                 break;
 582
 583                         do_swap(base, n, size, swap_func, r, c);
 584                 }
 585         }
 586 }
 587
 588 void sort_cmp_size(void *base, size_t num, size_t size,
 589           int (*cmp_func)(const void *, const void *, size_t),
 590           void (*swap_func)(void *, void *, size_t size))
 591 {
 592         /* pre-scale counters for performance */
 593         int i = (num/2 - 1) * size, n = num * size, c, r;
 594
 595         if (!swap_func) {
 596                 if (size == 4 && alignment_ok(base, 4))
 597                         swap_func = u32_swap;
 598                 else if (size == 8 && alignment_ok(base, 8))
 599                         swap_func = u64_swap;
 600                 else
 601                         swap_func = generic_swap;
 602         }
 603
 604         /* heapify */
 605         for ( ; i >= 0; i -= size) {
 606                 for (r = i; r * 2 + size < n; r  = c) {
 607                         c = r * 2 + size;
 608                         if (c < n - size &&
 609                             cmp_func(base + c, base + c + size, size) < 0)
 610                                 c += size;
 611                         if (cmp_func(base + r, base + c, size) >= 0)
 612                                 break;
 613                         swap_func(base + r, base + c, size);
 614                 }
 615         }
 616
 617         /* sort */
 618         for (i = n - size; i > 0; i -= size) {
 619                 swap_func(base, base + i, size);
 620                 for (r = 0; r * 2 + size < i; r = c) {
 621                         c = r * 2 + size;
 622                         if (c < i - size &&
 623                             cmp_func(base + c, base + c + size, size) < 0)
 624                                 c += size;
 625                         if (cmp_func(base + r, base + c, size) >= 0)
 626                                 break;
 627                         swap_func(base + r, base + c, size);
 628                 }
 629         }
 630 }
 631
 632 void mempool_free_vp(void *element, void *pool_data)
 633 {
 634         size_t size = (size_t) pool_data;
 635
 636         vpfree(element, size);
 637 }
 638
 639 void *mempool_alloc_vp(gfp_t gfp_mask, void *pool_data)
 640 {
 641         size_t size = (size_t) pool_data;
 642
 643         return vpmalloc(size, gfp_mask);
 644 }