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                 snprintf(dec, sizeof(dec), ".%i", t / 103);
 102
 103         return sprintf(buf, "%lli%s%c", v, dec, units[u]);
 104 }
 105
 106 ssize_t bch2_snprint_string_list(char *buf, size_t size, const char * const list[],
 107                             size_t selected)
 108 {
 109         char *out = buf;
 110         size_t i;
 111
 112         for (i = 0; list[i]; i++)
 113                 out += snprintf(out, buf + size - out,
 114                                 i == selected ? "[%s] " : "%s ", list[i]);
 115
 116         out[-1] = '\n';
 117         return out - buf;
 118 }
 119
 120 ssize_t bch2_read_string_list(const char *buf, const char * const list[])
 121 {
 122         size_t i;
 123         char *s, *d = kstrndup(buf, PAGE_SIZE - 1, GFP_KERNEL);
 124         if (!d)
 125                 return -ENOMEM;
 126
 127         s = strim(d);
 128
 129         for (i = 0; list[i]; i++)
 130                 if (!strcmp(list[i], s))
 131                         break;
 132
 133         kfree(d);
 134
 135         if (!list[i])
 136                 return -EINVAL;
 137
 138         return i;
 139 }
 140
 141 bool bch2_is_zero(const void *_p, size_t n)
 142 {
 143         const char *p = _p;
 144         size_t i;
 145
 146         for (i = 0; i < n; i++)
 147                 if (p[i])
 148                         return false;
 149         return true;
 150 }
 151
 152 void bch2_time_stats_clear(struct time_stats *stats)
 153 {
 154         spin_lock(&stats->lock);
 155
 156         stats->count = 0;
 157         stats->last_duration = 0;
 158         stats->max_duration = 0;
 159         stats->average_duration = 0;
 160         stats->average_frequency = 0;
 161         stats->last = 0;
 162
 163         spin_unlock(&stats->lock);
 164 }
 165
 166 void __bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 167 {
 168         u64 now, duration, last;
 169
 170         stats->count++;
 171
 172         now             = local_clock();
 173         duration        = time_after64(now, start_time)
 174                 ? now - start_time : 0;
 175         last            = time_after64(now, stats->last)
 176                 ? now - stats->last : 0;
 177
 178         stats->last_duration = duration;
 179         stats->max_duration = max(stats->max_duration, duration);
 180
 181         if (stats->last) {
 182                 stats->average_duration = ewma_add(stats->average_duration,
 183                                                    duration << 8, 3);
 184
 185                 if (stats->average_frequency)
 186                         stats->average_frequency =
 187                                 ewma_add(stats->average_frequency,
 188                                          last << 8, 3);
 189                 else
 190                         stats->average_frequency  = last << 8;
 191         } else {
 192                 stats->average_duration = duration << 8;
 193         }
 194
 195         stats->last = now ?: 1;
 196 }
 197
 198 void bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 199 {
 200         spin_lock(&stats->lock);
 201         __bch2_time_stats_update(stats, start_time);
 202         spin_unlock(&stats->lock);
 203 }
 204
 205 /**
 206  * bch2_ratelimit_delay() - return how long to delay until the next time to do
 207  * some work
 208  *
 209  * @d - the struct bch_ratelimit to update
 210  *
 211  * Returns the amount of time to delay by, in jiffies
 212  */
 213 u64 bch2_ratelimit_delay(struct bch_ratelimit *d)
 214 {
 215         u64 now = local_clock();
 216
 217         return time_after64(d->next, now)
 218                 ? nsecs_to_jiffies(d->next - now)
 219                 : 0;
 220 }
 221
 222 /**
 223  * bch2_ratelimit_increment() - increment @d by the amount of work done
 224  *
 225  * @d - the struct bch_ratelimit to update
 226  * @done - the amount of work done, in arbitrary units
 227  */
 228 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done)
 229 {
 230         u64 now = local_clock();
 231
 232         d->next += div_u64(done * NSEC_PER_SEC, d->rate);
 233
 234         if (time_before64(now + NSEC_PER_SEC, d->next))
 235                 d->next = now + NSEC_PER_SEC;
 236
 237         if (time_after64(now - NSEC_PER_SEC * 2, d->next))
 238                 d->next = now - NSEC_PER_SEC * 2;
 239 }
 240
 241 int bch2_ratelimit_wait_freezable_stoppable(struct bch_ratelimit *d)
 242 {
 243         while (1) {
 244                 u64 delay = bch2_ratelimit_delay(d);
 245
 246                 if (delay)
 247                         set_current_state(TASK_INTERRUPTIBLE);
 248
 249                 if (kthread_should_stop())
 250                         return 1;
 251
 252                 if (!delay)
 253                         return 0;
 254
 255                 schedule_timeout(delay);
 256                 try_to_freeze();
 257         }
 258 }
 259
 260 /*
 261  * Updates pd_controller. Attempts to scale inputed values to units per second.
 262  * @target: desired value
 263  * @actual: current value
 264  *
 265  * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing
 266  * it makes actual go down.
 267  */
 268 void bch2_pd_controller_update(struct bch_pd_controller *pd,
 269                               s64 target, s64 actual, int sign)
 270 {
 271         s64 proportional, derivative, change;
 272
 273         unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ;
 274
 275         if (seconds_since_update == 0)
 276                 return;
 277
 278         pd->last_update = jiffies;
 279
 280         proportional = actual - target;
 281         proportional *= seconds_since_update;
 282         proportional = div_s64(proportional, pd->p_term_inverse);
 283
 284         derivative = actual - pd->last_actual;
 285         derivative = div_s64(derivative, seconds_since_update);
 286         derivative = ewma_add(pd->smoothed_derivative, derivative,
 287                               (pd->d_term / seconds_since_update) ?: 1);
 288         derivative = derivative * pd->d_term;
 289         derivative = div_s64(derivative, pd->p_term_inverse);
 290
 291         change = proportional + derivative;
 292
 293         /* Don't increase rate if not keeping up */
 294         if (change > 0 &&
 295             pd->backpressure &&
 296             time_after64(local_clock(),
 297                          pd->rate.next + NSEC_PER_MSEC))
 298                 change = 0;
 299
 300         change *= (sign * -1);
 301
 302         pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change,
 303                                 1, UINT_MAX);
 304
 305         pd->last_actual         = actual;
 306         pd->last_derivative     = derivative;
 307         pd->last_proportional   = proportional;
 308         pd->last_change         = change;
 309         pd->last_target         = target;
 310 }
 311
 312 void bch2_pd_controller_init(struct bch_pd_controller *pd)
 313 {
 314         pd->rate.rate           = 1024;
 315         pd->last_update         = jiffies;
 316         pd->p_term_inverse      = 6000;
 317         pd->d_term              = 30;
 318         pd->d_smooth            = pd->d_term;
 319         pd->backpressure        = 1;
 320 }
 321
 322 size_t bch2_pd_controller_print_debug(struct bch_pd_controller *pd, char *buf)
 323 {
 324         /* 2^64 - 1 is 20 digits, plus null byte */
 325         char rate[21];
 326         char actual[21];
 327         char target[21];
 328         char proportional[21];
 329         char derivative[21];
 330         char change[21];
 331         s64 next_io;
 332
 333         bch2_hprint(rate,       pd->rate.rate);
 334         bch2_hprint(actual,     pd->last_actual);
 335         bch2_hprint(target,     pd->last_target);
 336         bch2_hprint(proportional, pd->last_proportional);
 337         bch2_hprint(derivative, pd->last_derivative);
 338         bch2_hprint(change,     pd->last_change);
 339
 340         next_io = div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC);
 341
 342         return sprintf(buf,
 343                        "rate:\t\t%s/sec\n"
 344                        "target:\t\t%s\n"
 345                        "actual:\t\t%s\n"
 346                        "proportional:\t%s\n"
 347                        "derivative:\t%s\n"
 348                        "change:\t\t%s/sec\n"
 349                        "next io:\t%llims\n",
 350                        rate, target, actual, proportional,
 351                        derivative, change, next_io);
 352 }
 353
 354 void bch2_bio_map(struct bio *bio, void *base)
 355 {
 356         size_t size = bio->bi_iter.bi_size;
 357         struct bio_vec *bv = bio->bi_io_vec;
 358
 359         BUG_ON(!bio->bi_iter.bi_size);
 360         BUG_ON(bio->bi_vcnt);
 361
 362         bv->bv_offset = base ? offset_in_page(base) : 0;
 363         goto start;
 364
 365         for (; size; bio->bi_vcnt++, bv++) {
 366                 bv->bv_offset   = 0;
 367 start:          bv->bv_len      = min_t(size_t, PAGE_SIZE - bv->bv_offset,
 368                                         size);
 369                 BUG_ON(bio->bi_vcnt >= bio->bi_max_vecs);
 370                 if (base) {
 371                         bv->bv_page = is_vmalloc_addr(base)
 372                                 ? vmalloc_to_page(base)
 373                                 : virt_to_page(base);
 374
 375                         base += bv->bv_len;
 376                 }
 377
 378                 size -= bv->bv_len;
 379         }
 380 }
 381
 382 size_t bch2_rand_range(size_t max)
 383 {
 384         size_t rand;
 385
 386         do {
 387                 get_random_bytes(&rand, sizeof(rand));
 388                 rand &= roundup_pow_of_two(max) - 1;
 389         } while (rand >= max);
 390
 391         return rand;
 392 }
 393
 394 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, void *src)
 395 {
 396         struct bio_vec bv;
 397         struct bvec_iter iter;
 398
 399         __bio_for_each_segment(bv, dst, iter, dst_iter) {
 400                 void *dstp = kmap_atomic(bv.bv_page);
 401                 memcpy(dstp + bv.bv_offset, src, bv.bv_len);
 402                 kunmap_atomic(dstp);
 403
 404                 src += bv.bv_len;
 405         }
 406 }
 407
 408 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
 409 {
 410         struct bio_vec bv;
 411         struct bvec_iter iter;
 412
 413         __bio_for_each_segment(bv, src, iter, src_iter) {
 414                 void *srcp = kmap_atomic(bv.bv_page);
 415                 memcpy(dst, srcp + bv.bv_offset, bv.bv_len);
 416                 kunmap_atomic(srcp);
 417
 418                 dst += bv.bv_len;
 419         }
 420 }
 421
 422 size_t bch_scnmemcpy(char *buf, size_t size, const char *src, size_t len)
 423 {
 424         size_t n;
 425
 426         if (!size)
 427                 return 0;
 428
 429         n = min(size - 1, len);
 430         memcpy(buf, src, n);
 431         buf[n] = '\0';
 432
 433         return n;
 434 }
 435
 436 #include "eytzinger.h"
 437
 438 static int alignment_ok(const void *base, size_t align)
 439 {
 440         return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
 441                 ((unsigned long)base & (align - 1)) == 0;
 442 }
 443
 444 static void u32_swap(void *a, void *b, size_t size)
 445 {
 446         u32 t = *(u32 *)a;
 447         *(u32 *)a = *(u32 *)b;
 448         *(u32 *)b = t;
 449 }
 450
 451 static void u64_swap(void *a, void *b, size_t size)
 452 {
 453         u64 t = *(u64 *)a;
 454         *(u64 *)a = *(u64 *)b;
 455         *(u64 *)b = t;
 456 }
 457
 458 static void generic_swap(void *a, void *b, size_t size)
 459 {
 460         char t;
 461
 462         do {
 463                 t = *(char *)a;
 464                 *(char *)a++ = *(char *)b;
 465                 *(char *)b++ = t;
 466         } while (--size > 0);
 467 }
 468
 469 static inline int do_cmp(void *base, size_t n, size_t size,
 470                          int (*cmp_func)(const void *, const void *, size_t),
 471                          size_t l, size_t r)
 472 {
 473         return cmp_func(base + inorder_to_eytzinger0(l, n) * size,
 474                         base + inorder_to_eytzinger0(r, n) * size,
 475                         size);
 476 }
 477
 478 static inline void do_swap(void *base, size_t n, size_t size,
 479                            void (*swap_func)(void *, void *, size_t),
 480                            size_t l, size_t r)
 481 {
 482         swap_func(base + inorder_to_eytzinger0(l, n) * size,
 483                   base + inorder_to_eytzinger0(r, n) * size,
 484                   size);
 485 }
 486
 487 void eytzinger0_sort(void *base, size_t n, size_t size,
 488                      int (*cmp_func)(const void *, const void *, size_t),
 489                      void (*swap_func)(void *, void *, size_t))
 490 {
 491         int i, c, r;
 492
 493         if (!swap_func) {
 494                 if (size == 4 && alignment_ok(base, 4))
 495                         swap_func = u32_swap;
 496                 else if (size == 8 && alignment_ok(base, 8))
 497                         swap_func = u64_swap;
 498                 else
 499                         swap_func = generic_swap;
 500         }
 501
 502         /* heapify */
 503         for (i = n / 2 - 1; i >= 0; --i) {
 504                 for (r = i; r * 2 + 1 < n; r = c) {
 505                         c = r * 2 + 1;
 506
 507                         if (c + 1 < n &&
 508                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 509                                 c++;
 510
 511                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 512                                 break;
 513
 514                         do_swap(base, n, size, swap_func, r, c);
 515                 }
 516         }
 517
 518         /* sort */
 519         for (i = n - 1; i > 0; --i) {
 520                 do_swap(base, n, size, swap_func, 0, i);
 521
 522                 for (r = 0; r * 2 + 1 < i; r = c) {
 523                         c = r * 2 + 1;
 524
 525                         if (c + 1 < i &&
 526                             do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
 527                                 c++;
 528
 529                         if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
 530                                 break;
 531
 532                         do_swap(base, n, size, swap_func, r, c);
 533                 }
 534         }
 535 }