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