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/module.h>
  13 #include <linux/random.h>
  14 #include <linux/seq_file.h>
  15 #include <linux/types.h>
  16
  17 #include <linux/freezer.h>
  18 #include <linux/kthread.h>
  19
  20 #include "util.h"
  21
  22 #define simple_strtoint(c, end, base)   simple_strtol(c, end, base)
  23 #define simple_strtouint(c, end, base)  simple_strtoul(c, end, base)
  24
  25 #define STRTO_H(name, type)                                     \
  26 int bch2_ ## name ## _h(const char *cp, type *res)              \
  27 {                                                               \
  28         int u = 0;                                              \
  29         char *e;                                                \
  30         type i = simple_ ## name(cp, &e, 10);                   \
  31                                                                 \
  32         switch (tolower(*e)) {                                  \
  33         default:                                                \
  34                 return -EINVAL;                                 \
  35         case 'y':                                               \
  36         case 'z':                                               \
  37                 u++;                                            \
  38         case 'e':                                               \
  39                 u++;                                            \
  40         case 'p':                                               \
  41                 u++;                                            \
  42         case 't':                                               \
  43                 u++;                                            \
  44         case 'g':                                               \
  45                 u++;                                            \
  46         case 'm':                                               \
  47                 u++;                                            \
  48         case 'k':                                               \
  49                 u++;                                            \
  50                 if (e++ == cp)                                  \
  51                         return -EINVAL;                         \
  52         case '\n':                                              \
  53         case '\0':                                              \
  54                 if (*e == '\n')                                 \
  55                         e++;                                    \
  56         }                                                       \
  57                                                                 \
  58         if (*e)                                                 \
  59                 return -EINVAL;                                 \
  60                                                                 \
  61         while (u--) {                                           \
  62                 if ((type) ~0 > 0 &&                            \
  63                     (type) ~0 / 1024 <= i)                      \
  64                         return -EINVAL;                         \
  65                 if ((i > 0 && ANYSINT_MAX(type) / 1024 < i) ||  \
  66                     (i < 0 && -ANYSINT_MAX(type) / 1024 > i))   \
  67                         return -EINVAL;                         \
  68                 i *= 1024;                                      \
  69         }                                                       \
  70                                                                 \
  71         *res = i;                                               \
  72         return 0;                                               \
  73 }                                                               \
  74
  75 STRTO_H(strtoint, int)
  76 STRTO_H(strtouint, unsigned int)
  77 STRTO_H(strtoll, long long)
  78 STRTO_H(strtoull, unsigned long long)
  79
  80 ssize_t bch2_hprint(char *buf, s64 v)
  81 {
  82         static const char units[] = "?kMGTPEZY";
  83         char dec[4] = "";
  84         int u, t = 0;
  85
  86         for (u = 0; v >= 1024 || v <= -1024; u++) {
  87                 t = v & ~(~0 << 10);
  88                 v >>= 10;
  89         }
  90
  91         if (!u)
  92                 return sprintf(buf, "%lli", v);
  93
  94         /*
  95          * 103 is magic: t is in the range [-1023, 1023] and we want
  96          * to turn it into [-9, 9]
  97          */
  98         if (v < 100 && v > -100)
  99                 snprintf(dec, sizeof(dec), ".%i", t / 103);
 100
 101         return sprintf(buf, "%lli%s%c", v, dec, units[u]);
 102 }
 103
 104 ssize_t bch2_snprint_string_list(char *buf, size_t size, const char * const list[],
 105                             size_t selected)
 106 {
 107         char *out = buf;
 108         size_t i;
 109
 110         for (i = 0; list[i]; i++)
 111                 out += snprintf(out, buf + size - out,
 112                                 i == selected ? "[%s] " : "%s ", list[i]);
 113
 114         out[-1] = '\n';
 115         return out - buf;
 116 }
 117
 118 ssize_t bch2_read_string_list(const char *buf, const char * const list[])
 119 {
 120         size_t i;
 121         char *s, *d = kstrndup(buf, PAGE_SIZE - 1, GFP_KERNEL);
 122         if (!d)
 123                 return -ENOMEM;
 124
 125         s = strim(d);
 126
 127         for (i = 0; list[i]; i++)
 128                 if (!strcmp(list[i], s))
 129                         break;
 130
 131         kfree(d);
 132
 133         if (!list[i])
 134                 return -EINVAL;
 135
 136         return i;
 137 }
 138
 139 bool bch2_is_zero(const void *_p, size_t n)
 140 {
 141         const char *p = _p;
 142         size_t i;
 143
 144         for (i = 0; i < n; i++)
 145                 if (p[i])
 146                         return false;
 147         return true;
 148 }
 149
 150 void bch2_time_stats_clear(struct time_stats *stats)
 151 {
 152         spin_lock(&stats->lock);
 153
 154         stats->count = 0;
 155         stats->last_duration = 0;
 156         stats->max_duration = 0;
 157         stats->average_duration = 0;
 158         stats->average_frequency = 0;
 159         stats->last = 0;
 160
 161         spin_unlock(&stats->lock);
 162 }
 163
 164 void __bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 165 {
 166         u64 now, duration, last;
 167
 168         stats->count++;
 169
 170         now             = local_clock();
 171         duration        = time_after64(now, start_time)
 172                 ? now - start_time : 0;
 173         last            = time_after64(now, stats->last)
 174                 ? now - stats->last : 0;
 175
 176         stats->last_duration = duration;
 177         stats->max_duration = max(stats->max_duration, duration);
 178
 179         if (stats->last) {
 180                 stats->average_duration = ewma_add(stats->average_duration,
 181                                                    duration << 8, 3);
 182
 183                 if (stats->average_frequency)
 184                         stats->average_frequency =
 185                                 ewma_add(stats->average_frequency,
 186                                          last << 8, 3);
 187                 else
 188                         stats->average_frequency  = last << 8;
 189         } else {
 190                 stats->average_duration = duration << 8;
 191         }
 192
 193         stats->last = now ?: 1;
 194 }
 195
 196 void bch2_time_stats_update(struct time_stats *stats, u64 start_time)
 197 {
 198         spin_lock(&stats->lock);
 199         __bch2_time_stats_update(stats, start_time);
 200         spin_unlock(&stats->lock);
 201 }
 202
 203 /**
 204  * bch2_ratelimit_delay() - return how long to delay until the next time to do
 205  * some work
 206  *
 207  * @d - the struct bch_ratelimit to update
 208  *
 209  * Returns the amount of time to delay by, in jiffies
 210  */
 211 u64 bch2_ratelimit_delay(struct bch_ratelimit *d)
 212 {
 213         u64 now = local_clock();
 214
 215         return time_after64(d->next, now)
 216                 ? nsecs_to_jiffies(d->next - now)
 217                 : 0;
 218 }
 219
 220 /**
 221  * bch2_ratelimit_increment() - increment @d by the amount of work done
 222  *
 223  * @d - the struct bch_ratelimit to update
 224  * @done - the amount of work done, in arbitrary units
 225  */
 226 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done)
 227 {
 228         u64 now = local_clock();
 229
 230         d->next += div_u64(done * NSEC_PER_SEC, d->rate);
 231
 232         if (time_before64(now + NSEC_PER_SEC, d->next))
 233                 d->next = now + NSEC_PER_SEC;
 234
 235         if (time_after64(now - NSEC_PER_SEC * 2, d->next))
 236                 d->next = now - NSEC_PER_SEC * 2;
 237 }
 238
 239 int bch2_ratelimit_wait_freezable_stoppable(struct bch_ratelimit *d)
 240 {
 241         while (1) {
 242                 u64 delay = bch2_ratelimit_delay(d);
 243
 244                 if (delay)
 245                         set_current_state(TASK_INTERRUPTIBLE);
 246
 247                 if (kthread_should_stop())
 248                         return 1;
 249
 250                 if (!delay)
 251                         return 0;
 252
 253                 schedule_timeout(delay);
 254                 try_to_freeze();
 255         }
 256 }
 257
 258 /*
 259  * Updates pd_controller. Attempts to scale inputed values to units per second.
 260  * @target: desired value
 261  * @actual: current value
 262  *
 263  * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing
 264  * it makes actual go down.
 265  */
 266 void bch2_pd_controller_update(struct bch_pd_controller *pd,
 267                               s64 target, s64 actual, int sign)
 268 {
 269         s64 proportional, derivative, change;
 270
 271         unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ;
 272
 273         if (seconds_since_update == 0)
 274                 return;
 275
 276         pd->last_update = jiffies;
 277
 278         proportional = actual - target;
 279         proportional *= seconds_since_update;
 280         proportional = div_s64(proportional, pd->p_term_inverse);
 281
 282         derivative = actual - pd->last_actual;
 283         derivative = div_s64(derivative, seconds_since_update);
 284         derivative = ewma_add(pd->smoothed_derivative, derivative,
 285                               (pd->d_term / seconds_since_update) ?: 1);
 286         derivative = derivative * pd->d_term;
 287         derivative = div_s64(derivative, pd->p_term_inverse);
 288
 289         change = proportional + derivative;
 290
 291         /* Don't increase rate if not keeping up */
 292         if (change > 0 &&
 293             pd->backpressure &&
 294             time_after64(local_clock(),
 295                          pd->rate.next + NSEC_PER_MSEC))
 296                 change = 0;
 297
 298         change *= (sign * -1);
 299
 300         pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change,
 301                                 1, UINT_MAX);
 302
 303         pd->last_actual         = actual;
 304         pd->last_derivative     = derivative;
 305         pd->last_proportional   = proportional;
 306         pd->last_change         = change;
 307         pd->last_target         = target;
 308 }
 309
 310 void bch2_pd_controller_init(struct bch_pd_controller *pd)
 311 {
 312         pd->rate.rate           = 1024;
 313         pd->last_update         = jiffies;
 314         pd->p_term_inverse      = 6000;
 315         pd->d_term              = 30;
 316         pd->d_smooth            = pd->d_term;
 317         pd->backpressure        = 1;
 318 }
 319
 320 size_t bch2_pd_controller_print_debug(struct bch_pd_controller *pd, char *buf)
 321 {
 322         /* 2^64 - 1 is 20 digits, plus null byte */
 323         char rate[21];
 324         char actual[21];
 325         char target[21];
 326         char proportional[21];
 327         char derivative[21];
 328         char change[21];
 329         s64 next_io;
 330
 331         bch2_hprint(rate,       pd->rate.rate);
 332         bch2_hprint(actual,     pd->last_actual);
 333         bch2_hprint(target,     pd->last_target);
 334         bch2_hprint(proportional, pd->last_proportional);
 335         bch2_hprint(derivative, pd->last_derivative);
 336         bch2_hprint(change,     pd->last_change);
 337
 338         next_io = div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC);
 339
 340         return sprintf(buf,
 341                        "rate:\t\t%s/sec\n"
 342                        "target:\t\t%s\n"
 343                        "actual:\t\t%s\n"
 344                        "proportional:\t%s\n"
 345                        "derivative:\t%s\n"
 346                        "change:\t\t%s/sec\n"
 347                        "next io:\t%llims\n",
 348                        rate, target, actual, proportional,
 349                        derivative, change, next_io);
 350 }
 351
 352 void bch2_bio_map(struct bio *bio, void *base)
 353 {
 354         size_t size = bio->bi_iter.bi_size;
 355         struct bio_vec *bv = bio->bi_io_vec;
 356
 357         BUG_ON(!bio->bi_iter.bi_size);
 358         BUG_ON(bio->bi_vcnt);
 359
 360         bv->bv_offset = base ? offset_in_page(base) : 0;
 361         goto start;
 362
 363         for (; size; bio->bi_vcnt++, bv++) {
 364                 bv->bv_offset   = 0;
 365 start:          bv->bv_len      = min_t(size_t, PAGE_SIZE - bv->bv_offset,
 366                                         size);
 367                 BUG_ON(bio->bi_vcnt >= bio->bi_max_vecs);
 368                 if (base) {
 369                         bv->bv_page = is_vmalloc_addr(base)
 370                                 ? vmalloc_to_page(base)
 371                                 : virt_to_page(base);
 372
 373                         base += bv->bv_len;
 374                 }
 375
 376                 size -= bv->bv_len;
 377         }
 378 }
 379
 380 size_t bch2_rand_range(size_t max)
 381 {
 382         size_t rand;
 383
 384         do {
 385                 get_random_bytes(&rand, sizeof(rand));
 386                 rand &= roundup_pow_of_two(max) - 1;
 387         } while (rand >= max);
 388
 389         return rand;
 390 }
 391
 392 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, void *src)
 393 {
 394         struct bio_vec bv;
 395         struct bvec_iter iter;
 396
 397         __bio_for_each_segment(bv, dst, iter, dst_iter) {
 398                 void *dstp = kmap_atomic(bv.bv_page);
 399                 memcpy(dstp + bv.bv_offset, src, bv.bv_len);
 400                 kunmap_atomic(dstp);
 401
 402                 src += bv.bv_len;
 403         }
 404 }
 405
 406 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
 407 {
 408         struct bio_vec bv;
 409         struct bvec_iter iter;
 410
 411         __bio_for_each_segment(bv, src, iter, src_iter) {
 412                 void *srcp = kmap_atomic(bv.bv_page);
 413                 memcpy(dst, srcp + bv.bv_offset, bv.bv_len);
 414                 kunmap_atomic(srcp);
 415
 416                 dst += bv.bv_len;
 417         }
 418 }