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

   1 #ifndef _BCACHE_UTIL_H
   2 #define _BCACHE_UTIL_H
   3
   4 #include <linux/bio.h>
   5 #include <linux/blkdev.h>
   6 #include <linux/closure.h>
   7 #include <linux/errno.h>
   8 #include <linux/freezer.h>
   9 #include <linux/kernel.h>
  10 #include <linux/sched/clock.h>
  11 #include <linux/llist.h>
  12 #include <linux/log2.h>
  13 #include <linux/ratelimit.h>
  14 #include <linux/slab.h>
  15 #include <linux/vmalloc.h>
  16 #include <linux/workqueue.h>
  17
  18 #define PAGE_SECTOR_SHIFT       (PAGE_SHIFT - 9)
  19 #define PAGE_SECTORS            (1UL << PAGE_SECTOR_SHIFT)
  20
  21 struct closure;
  22
  23 #ifdef CONFIG_BCACHEFS_DEBUG
  24
  25 #define EBUG_ON(cond)           BUG_ON(cond)
  26 #define atomic_dec_bug(v)       BUG_ON(atomic_dec_return(v) < 0)
  27 #define atomic_inc_bug(v, i)    BUG_ON(atomic_inc_return(v) <= i)
  28 #define atomic_sub_bug(i, v)    BUG_ON(atomic_sub_return(i, v) < 0)
  29 #define atomic_add_bug(i, v)    BUG_ON(atomic_add_return(i, v) < 0)
  30 #define atomic_long_dec_bug(v)          BUG_ON(atomic_long_dec_return(v) < 0)
  31 #define atomic_long_sub_bug(i, v)       BUG_ON(atomic_long_sub_return(i, v) < 0)
  32 #define atomic64_dec_bug(v)     BUG_ON(atomic64_dec_return(v) < 0)
  33 #define atomic64_inc_bug(v, i)  BUG_ON(atomic64_inc_return(v) <= i)
  34 #define atomic64_sub_bug(i, v)  BUG_ON(atomic64_sub_return(i, v) < 0)
  35 #define atomic64_add_bug(i, v)  BUG_ON(atomic64_add_return(i, v) < 0)
  36
  37 #define memcpy(_dst, _src, _len)                                        \
  38 ({                                                                      \
  39         BUG_ON(!((void *) (_dst) >= (void *) (_src) + (_len) ||         \
  40                  (void *) (_dst) + (_len) <= (void *) (_src)));         \
  41         memcpy(_dst, _src, _len);                                       \
  42 })
  43
  44 #else /* DEBUG */
  45
  46 #define EBUG_ON(cond)
  47 #define atomic_dec_bug(v)       atomic_dec(v)
  48 #define atomic_inc_bug(v, i)    atomic_inc(v)
  49 #define atomic_sub_bug(i, v)    atomic_sub(i, v)
  50 #define atomic_add_bug(i, v)    atomic_add(i, v)
  51 #define atomic_long_dec_bug(v)          atomic_long_dec(v)
  52 #define atomic_long_sub_bug(i, v)       atomic_long_sub(i, v)
  53 #define atomic64_dec_bug(v)     atomic64_dec(v)
  54 #define atomic64_inc_bug(v, i)  atomic64_inc(v)
  55 #define atomic64_sub_bug(i, v)  atomic64_sub(i, v)
  56 #define atomic64_add_bug(i, v)  atomic64_add(i, v)
  57
  58 #endif
  59
  60 #ifndef __CHECKER__
  61 #define __flatten __attribute__((flatten))
  62 #else
  63 /* sparse doesn't know about attribute((flatten)) */
  64 #define __flatten
  65 #endif
  66
  67 #ifdef __LITTLE_ENDIAN
  68 #define CPU_BIG_ENDIAN          0
  69 #else
  70 #define CPU_BIG_ENDIAN          1
  71 #endif
  72
  73 /* type hackery */
  74
  75 #define type_is_exact(_val, _type)                                      \
  76         __builtin_types_compatible_p(typeof(_val), _type)
  77
  78 #define type_is(_val, _type)                                            \
  79         (__builtin_types_compatible_p(typeof(_val), _type) ||           \
  80          __builtin_types_compatible_p(typeof(_val), const _type))
  81
  82 static inline void vpfree(void *p, size_t size)
  83 {
  84         if (is_vmalloc_addr(p))
  85                 vfree(p);
  86         else
  87                 free_pages((unsigned long) p, get_order(size));
  88 }
  89
  90 static inline void *vpmalloc(size_t size, gfp_t gfp_mask)
  91 {
  92         return (void *) __get_free_pages(gfp_mask|__GFP_NOWARN,
  93                                          get_order(size)) ?:
  94                 __vmalloc(size, gfp_mask, PAGE_KERNEL);
  95 }
  96
  97 static inline void kvpfree(void *p, size_t size)
  98 {
  99         if (size < PAGE_SIZE)
 100                 kfree(p);
 101         else
 102                 vpfree(p, size);
 103 }
 104
 105 static inline void *kvpmalloc(size_t size, gfp_t gfp_mask)
 106 {
 107         return size < PAGE_SIZE
 108                 ? kmalloc(size, gfp_mask)
 109                 : vpmalloc(size, gfp_mask);
 110 }
 111
 112 void mempool_free_vp(void *element, void *pool_data);
 113 void *mempool_alloc_vp(gfp_t gfp_mask, void *pool_data);
 114
 115 static inline int mempool_init_vp_pool(mempool_t *pool, int min_nr, size_t size)
 116 {
 117         return mempool_init(pool, min_nr, mempool_alloc_vp,
 118                             mempool_free_vp, (void *) size);
 119 }
 120
 121 #define HEAP(type)                                                      \
 122 struct {                                                                \
 123         size_t size, used;                                              \
 124         type *data;                                                     \
 125 }
 126
 127 #define DECLARE_HEAP(type, name) HEAP(type) name
 128
 129 #define init_heap(heap, _size, gfp)                                     \
 130 ({                                                                      \
 131         (heap)->used = 0;                                               \
 132         (heap)->size = (_size);                                         \
 133         (heap)->data = kvpmalloc((heap)->size * sizeof((heap)->data[0]),\
 134                                  (gfp));                                \
 135 })
 136
 137 #define free_heap(heap)                                                 \
 138 do {                                                                    \
 139         kvpfree((heap)->data, (heap)->size * sizeof((heap)->data[0]));  \
 140         (heap)->data = NULL;                                            \
 141 } while (0)
 142
 143 #define heap_swap(h, i, j)      swap((h)->data[i], (h)->data[j])
 144
 145 #define heap_peek(h)                                                    \
 146 ({                                                                      \
 147         EBUG_ON(!(h)->used);                                            \
 148         (h)->data[0];                                                   \
 149 })
 150
 151 #define heap_full(h)    ((h)->used == (h)->size)
 152
 153 #define heap_sift_down(h, i, cmp)                                       \
 154 do {                                                                    \
 155         size_t _c, _j = i;                                              \
 156                                                                         \
 157         for (; _j * 2 + 1 < (h)->used; _j = _c) {                       \
 158                 _c = _j * 2 + 1;                                        \
 159                 if (_c + 1 < (h)->used &&                               \
 160                     cmp(h, (h)->data[_c], (h)->data[_c + 1]) >= 0)      \
 161                         _c++;                                           \
 162                                                                         \
 163                 if (cmp(h, (h)->data[_c], (h)->data[_j]) >= 0)          \
 164                         break;                                          \
 165                 heap_swap(h, _c, _j);                                   \
 166         }                                                               \
 167 } while (0)
 168
 169 #define heap_sift_up(h, i, cmp)                                         \
 170 do {                                                                    \
 171         while (i) {                                                     \
 172                 size_t p = (i - 1) / 2;                                 \
 173                 if (cmp(h, (h)->data[i], (h)->data[p]) >= 0)            \
 174                         break;                                          \
 175                 heap_swap(h, i, p);                                     \
 176                 i = p;                                                  \
 177         }                                                               \
 178 } while (0)
 179
 180 #define heap_add(h, new, cmp)                                           \
 181 ({                                                                      \
 182         bool _r = !heap_full(h);                                        \
 183         if (_r) {                                                       \
 184                 size_t _i = (h)->used++;                                \
 185                 (h)->data[_i] = new;                                    \
 186                                                                         \
 187                 heap_sift_up(h, _i, cmp);                               \
 188         }                                                               \
 189         _r;                                                             \
 190 })
 191
 192 #define heap_add_or_replace(h, new, cmp)                                \
 193 do {                                                                    \
 194         if (!heap_add(h, new, cmp) &&                                   \
 195             cmp(h, new, heap_peek(h)) >= 0) {                           \
 196                 (h)->data[0] = new;                                     \
 197                 heap_sift_down(h, 0, cmp);                              \
 198         }                                                               \
 199 } while (0)
 200
 201 #define heap_del(h, i, cmp)                                             \
 202 do {                                                                    \
 203         size_t _i = (i);                                                \
 204                                                                         \
 205         BUG_ON(_i >= (h)->used);                                        \
 206         (h)->used--;                                                    \
 207         heap_swap(h, _i, (h)->used);                                    \
 208         heap_sift_up(h, _i, cmp);                                       \
 209         heap_sift_down(h, _i, cmp);                                     \
 210 } while (0)
 211
 212 #define heap_pop(h, d, cmp)                                             \
 213 ({                                                                      \
 214         bool _r = (h)->used;                                            \
 215         if (_r) {                                                       \
 216                 (d) = (h)->data[0];                                     \
 217                 heap_del(h, 0, cmp);                                    \
 218         }                                                               \
 219         _r;                                                             \
 220 })
 221
 222 #define heap_resort(heap, cmp)                                          \
 223 do {                                                                    \
 224         ssize_t _i;                                                     \
 225         for (_i = (ssize_t) (heap)->used / 2 -  1; _i >= 0; --_i)       \
 226                 heap_sift_down(heap, _i, cmp);                          \
 227 } while (0)
 228
 229 /*
 230  * Simple array based allocator - preallocates a number of elements and you can
 231  * never allocate more than that, also has no locking.
 232  *
 233  * Handy because if you know you only need a fixed number of elements you don't
 234  * have to worry about memory allocation failure, and sometimes a mempool isn't
 235  * what you want.
 236  *
 237  * We treat the free elements as entries in a singly linked list, and the
 238  * freelist as a stack - allocating and freeing push and pop off the freelist.
 239  */
 240
 241 #define DECLARE_ARRAY_ALLOCATOR(type, name, size)                       \
 242         struct {                                                        \
 243                 type    *freelist;                                      \
 244                 type    data[size];                                     \
 245         } name
 246
 247 #define array_alloc(array)                                              \
 248 ({                                                                      \
 249         typeof((array)->freelist) _ret = (array)->freelist;             \
 250                                                                         \
 251         if (_ret)                                                       \
 252                 (array)->freelist = *((typeof((array)->freelist) *) _ret);\
 253                                                                         \
 254         _ret;                                                           \
 255 })
 256
 257 #define array_free(array, ptr)                                          \
 258 do {                                                                    \
 259         typeof((array)->freelist) _ptr = ptr;                           \
 260                                                                         \
 261         *((typeof((array)->freelist) *) _ptr) = (array)->freelist;      \
 262         (array)->freelist = _ptr;                                       \
 263 } while (0)
 264
 265 #define array_allocator_init(array)                                     \
 266 do {                                                                    \
 267         typeof((array)->freelist) _i;                                   \
 268                                                                         \
 269         BUILD_BUG_ON(sizeof((array)->data[0]) < sizeof(void *));        \
 270         (array)->freelist = NULL;                                       \
 271                                                                         \
 272         for (_i = (array)->data;                                        \
 273              _i < (array)->data + ARRAY_SIZE((array)->data);            \
 274              _i++)                                                      \
 275                 array_free(array, _i);                                  \
 276 } while (0)
 277
 278 #define array_freelist_empty(array)     ((array)->freelist == NULL)
 279
 280 #define ANYSINT_MAX(t)                                                  \
 281         ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1)
 282
 283 int bch2_strtoint_h(const char *, int *);
 284 int bch2_strtouint_h(const char *, unsigned int *);
 285 int bch2_strtoll_h(const char *, long long *);
 286 int bch2_strtoull_h(const char *, unsigned long long *);
 287
 288 static inline int bch2_strtol_h(const char *cp, long *res)
 289 {
 290 #if BITS_PER_LONG == 32
 291         return bch2_strtoint_h(cp, (int *) res);
 292 #else
 293         return bch2_strtoll_h(cp, (long long *) res);
 294 #endif
 295 }
 296
 297 static inline int bch2_strtoul_h(const char *cp, long *res)
 298 {
 299 #if BITS_PER_LONG == 32
 300         return bch2_strtouint_h(cp, (unsigned int *) res);
 301 #else
 302         return bch2_strtoull_h(cp, (unsigned long long *) res);
 303 #endif
 304 }
 305
 306 #define strtoi_h(cp, res)                                               \
 307         ( type_is(*res, int)            ? bch2_strtoint_h(cp, (void *) res)\
 308         : type_is(*res, long)           ? bch2_strtol_h(cp, (void *) res)\
 309         : type_is(*res, long long)      ? bch2_strtoll_h(cp, (void *) res)\
 310         : type_is(*res, unsigned)       ? bch2_strtouint_h(cp, (void *) res)\
 311         : type_is(*res, unsigned long)  ? bch2_strtoul_h(cp, (void *) res)\
 312         : type_is(*res, unsigned long long) ? bch2_strtoull_h(cp, (void *) res)\
 313         : -EINVAL)
 314
 315 #define strtoul_safe(cp, var)                                           \
 316 ({                                                                      \
 317         unsigned long _v;                                               \
 318         int _r = kstrtoul(cp, 10, &_v);                                 \
 319         if (!_r)                                                        \
 320                 var = _v;                                               \
 321         _r;                                                             \
 322 })
 323
 324 #define strtoul_safe_clamp(cp, var, min, max)                           \
 325 ({                                                                      \
 326         unsigned long _v;                                               \
 327         int _r = kstrtoul(cp, 10, &_v);                                 \
 328         if (!_r)                                                        \
 329                 var = clamp_t(typeof(var), _v, min, max);               \
 330         _r;                                                             \
 331 })
 332
 333 #define strtoul_safe_restrict(cp, var, min, max)                        \
 334 ({                                                                      \
 335         unsigned long _v;                                               \
 336         int _r = kstrtoul(cp, 10, &_v);                                 \
 337         if (!_r && _v >= min && _v <= max)                              \
 338                 var = _v;                                               \
 339         else                                                            \
 340                 _r = -EINVAL;                                           \
 341         _r;                                                             \
 342 })
 343
 344 #define snprint(buf, size, var)                                         \
 345         snprintf(buf, size,                                             \
 346                    type_is(var, int)            ? "%i\n"                \
 347                  : type_is(var, unsigned)       ? "%u\n"                \
 348                  : type_is(var, long)           ? "%li\n"               \
 349                  : type_is(var, unsigned long)  ? "%lu\n"               \
 350                  : type_is(var, s64)            ? "%lli\n"              \
 351                  : type_is(var, u64)            ? "%llu\n"              \
 352                  : type_is(var, char *)         ? "%s\n"                \
 353                  : "%i\n", var)
 354
 355 ssize_t bch2_hprint(char *buf, s64 v);
 356
 357 bool bch2_is_zero(const void *, size_t);
 358
 359 ssize_t bch2_snprint_string_list(char *buf, size_t size, const char * const list[],
 360                             size_t selected);
 361
 362 ssize_t bch2_read_string_list(const char *buf, const char * const list[]);
 363
 364 struct time_stats {
 365         spinlock_t      lock;
 366         u64             count;
 367         /*
 368          * all fields are in nanoseconds, averages are ewmas stored left shifted
 369          * by 8
 370          */
 371         u64             last_duration;
 372         u64             max_duration;
 373         u64             average_duration;
 374         u64             average_frequency;
 375         u64             last;
 376 };
 377
 378 void bch2_time_stats_clear(struct time_stats *stats);
 379 void __bch2_time_stats_update(struct time_stats *stats, u64 time);
 380 void bch2_time_stats_update(struct time_stats *stats, u64 time);
 381
 382 static inline unsigned local_clock_us(void)
 383 {
 384         return local_clock() >> 10;
 385 }
 386
 387 #define NSEC_PER_ns                     1L
 388 #define NSEC_PER_us                     NSEC_PER_USEC
 389 #define NSEC_PER_ms                     NSEC_PER_MSEC
 390 #define NSEC_PER_sec                    NSEC_PER_SEC
 391
 392 #define __print_time_stat(stats, name, stat, units)                     \
 393         sysfs_print(name ## _ ## stat ## _ ## units,                    \
 394                     div_u64((stats)->stat >> 8, NSEC_PER_ ## units))
 395
 396 #define sysfs_print_time_stats(stats, name,                             \
 397                                frequency_units,                         \
 398                                duration_units)                          \
 399 do {                                                                    \
 400         __print_time_stat(stats, name,                                  \
 401                           average_frequency,    frequency_units);       \
 402         __print_time_stat(stats, name,                                  \
 403                           average_duration,     duration_units);        \
 404         sysfs_print(name ## _ ##count, (stats)->count);                 \
 405         sysfs_print(name ## _ ##last_duration ## _ ## duration_units,   \
 406                         div_u64((stats)->last_duration,                 \
 407                                 NSEC_PER_ ## duration_units));          \
 408         sysfs_print(name ## _ ##max_duration ## _ ## duration_units,    \
 409                         div_u64((stats)->max_duration,                  \
 410                                 NSEC_PER_ ## duration_units));          \
 411                                                                         \
 412         sysfs_print(name ## _last_ ## frequency_units, (stats)->last    \
 413                     ? div_s64(local_clock() - (stats)->last,            \
 414                               NSEC_PER_ ## frequency_units)             \
 415                     : -1LL);                                            \
 416 } while (0)
 417
 418 #define sysfs_clear_time_stats(stats, name)                             \
 419 do {                                                                    \
 420         if (attr == &sysfs_ ## name ## _clear)                          \
 421                 bch2_time_stats_clear(stats);                           \
 422 } while (0)
 423
 424 #define sysfs_time_stats_attribute(name,                                \
 425                                    frequency_units,                     \
 426                                    duration_units)                      \
 427 write_attribute(name ## _clear);                                        \
 428 read_attribute(name ## _count);                                         \
 429 read_attribute(name ## _average_frequency_ ## frequency_units);         \
 430 read_attribute(name ## _average_duration_ ## duration_units);           \
 431 read_attribute(name ## _last_duration_ ## duration_units);              \
 432 read_attribute(name ## _max_duration_ ## duration_units);               \
 433 read_attribute(name ## _last_ ## frequency_units)
 434
 435 #define sysfs_time_stats_attribute_list(name,                           \
 436                                         frequency_units,                \
 437                                         duration_units)                 \
 438 &sysfs_ ## name ## _clear,                                              \
 439 &sysfs_ ## name ## _count,                                              \
 440 &sysfs_ ## name ## _average_frequency_ ## frequency_units,              \
 441 &sysfs_ ## name ## _average_duration_ ## duration_units,                \
 442 &sysfs_ ## name ## _last_duration_ ## duration_units,                   \
 443 &sysfs_ ## name ## _max_duration_ ## duration_units,                    \
 444 &sysfs_ ## name ## _last_ ## frequency_units,
 445
 446 #define ewma_add(ewma, val, weight)                                     \
 447 ({                                                                      \
 448         typeof(ewma) _ewma = (ewma);                                    \
 449         typeof(weight) _weight = (weight);                              \
 450                                                                         \
 451         (((_ewma << _weight) - _ewma) + (val)) >> _weight;              \
 452 })
 453
 454 struct bch_ratelimit {
 455         /* Next time we want to do some work, in nanoseconds */
 456         u64                     next;
 457
 458         /*
 459          * Rate at which we want to do work, in units per nanosecond
 460          * The units here correspond to the units passed to
 461          * bch2_ratelimit_increment()
 462          */
 463         unsigned                rate;
 464 };
 465
 466 static inline void bch2_ratelimit_reset(struct bch_ratelimit *d)
 467 {
 468         d->next = local_clock();
 469 }
 470
 471 u64 bch2_ratelimit_delay(struct bch_ratelimit *);
 472 void bch2_ratelimit_increment(struct bch_ratelimit *, u64);
 473 int bch2_ratelimit_wait_freezable_stoppable(struct bch_ratelimit *);
 474
 475 struct bch_pd_controller {
 476         struct bch_ratelimit    rate;
 477         unsigned long           last_update;
 478
 479         s64                     last_actual;
 480         s64                     smoothed_derivative;
 481
 482         unsigned                p_term_inverse;
 483         unsigned                d_smooth;
 484         unsigned                d_term;
 485
 486         /* for exporting to sysfs (no effect on behavior) */
 487         s64                     last_derivative;
 488         s64                     last_proportional;
 489         s64                     last_change;
 490         s64                     last_target;
 491
 492         /* If true, the rate will not increase if bch2_ratelimit_delay()
 493          * is not being called often enough. */
 494         bool                    backpressure;
 495 };
 496
 497 void bch2_pd_controller_update(struct bch_pd_controller *, s64, s64, int);
 498 void bch2_pd_controller_init(struct bch_pd_controller *);
 499 size_t bch2_pd_controller_print_debug(struct bch_pd_controller *, char *);
 500
 501 #define sysfs_pd_controller_attribute(name)                             \
 502         rw_attribute(name##_rate);                                      \
 503         rw_attribute(name##_rate_bytes);                                \
 504         rw_attribute(name##_rate_d_term);                               \
 505         rw_attribute(name##_rate_p_term_inverse);                       \
 506         read_attribute(name##_rate_debug)
 507
 508 #define sysfs_pd_controller_files(name)                                 \
 509         &sysfs_##name##_rate,                                           \
 510         &sysfs_##name##_rate_bytes,                                     \
 511         &sysfs_##name##_rate_d_term,                                    \
 512         &sysfs_##name##_rate_p_term_inverse,                            \
 513         &sysfs_##name##_rate_debug
 514
 515 #define sysfs_pd_controller_show(name, var)                             \
 516 do {                                                                    \
 517         sysfs_hprint(name##_rate,               (var)->rate.rate);      \
 518         sysfs_print(name##_rate_bytes,          (var)->rate.rate);      \
 519         sysfs_print(name##_rate_d_term,         (var)->d_term);         \
 520         sysfs_print(name##_rate_p_term_inverse, (var)->p_term_inverse); \
 521                                                                         \
 522         if (attr == &sysfs_##name##_rate_debug)                         \
 523                 return bch2_pd_controller_print_debug(var, buf);                \
 524 } while (0)
 525
 526 #define sysfs_pd_controller_store(name, var)                            \
 527 do {                                                                    \
 528         sysfs_strtoul_clamp(name##_rate,                                \
 529                             (var)->rate.rate, 1, UINT_MAX);             \
 530         sysfs_strtoul_clamp(name##_rate_bytes,                          \
 531                             (var)->rate.rate, 1, UINT_MAX);             \
 532         sysfs_strtoul(name##_rate_d_term,       (var)->d_term);         \
 533         sysfs_strtoul_clamp(name##_rate_p_term_inverse,                 \
 534                             (var)->p_term_inverse, 1, INT_MAX);         \
 535 } while (0)
 536
 537 #define __DIV_SAFE(n, d, zero)                                          \
 538 ({                                                                      \
 539         typeof(n) _n = (n);                                             \
 540         typeof(d) _d = (d);                                             \
 541         _d ? _n / _d : zero;                                            \
 542 })
 543
 544 #define DIV_SAFE(n, d)  __DIV_SAFE(n, d, 0)
 545
 546 #define container_of_or_null(ptr, type, member)                         \
 547 ({                                                                      \
 548         typeof(ptr) _ptr = ptr;                                         \
 549         _ptr ? container_of(_ptr, type, member) : NULL;                 \
 550 })
 551
 552 #define RB_INSERT(root, new, member, cmp)                               \
 553 ({                                                                      \
 554         __label__ dup;                                                  \
 555         struct rb_node **n = &(root)->rb_node, *parent = NULL;          \
 556         typeof(new) this;                                               \
 557         int res, ret = -1;                                              \
 558                                                                         \
 559         while (*n) {                                                    \
 560                 parent = *n;                                            \
 561                 this = container_of(*n, typeof(*(new)), member);        \
 562                 res = cmp(new, this);                                   \
 563                 if (!res)                                               \
 564                         goto dup;                                       \
 565                 n = res < 0                                             \
 566                         ? &(*n)->rb_left                                \
 567                         : &(*n)->rb_right;                              \
 568         }                                                               \
 569                                                                         \
 570         rb_link_node(&(new)->member, parent, n);                        \
 571         rb_insert_color(&(new)->member, root);                          \
 572         ret = 0;                                                        \
 573 dup:                                                                    \
 574         ret;                                                            \
 575 })
 576
 577 #define RB_SEARCH(root, search, member, cmp)                            \
 578 ({                                                                      \
 579         struct rb_node *n = (root)->rb_node;                            \
 580         typeof(&(search)) this, ret = NULL;                             \
 581         int res;                                                        \
 582                                                                         \
 583         while (n) {                                                     \
 584                 this = container_of(n, typeof(search), member);         \
 585                 res = cmp(&(search), this);                             \
 586                 if (!res) {                                             \
 587                         ret = this;                                     \
 588                         break;                                          \
 589                 }                                                       \
 590                 n = res < 0                                             \
 591                         ? n->rb_left                                    \
 592                         : n->rb_right;                                  \
 593         }                                                               \
 594         ret;                                                            \
 595 })
 596
 597 #define RB_GREATER(root, search, member, cmp)                           \
 598 ({                                                                      \
 599         struct rb_node *n = (root)->rb_node;                            \
 600         typeof(&(search)) this, ret = NULL;                             \
 601         int res;                                                        \
 602                                                                         \
 603         while (n) {                                                     \
 604                 this = container_of(n, typeof(search), member);         \
 605                 res = cmp(&(search), this);                             \
 606                 if (res < 0) {                                          \
 607                         ret = this;                                     \
 608                         n = n->rb_left;                                 \
 609                 } else                                                  \
 610                         n = n->rb_right;                                \
 611         }                                                               \
 612         ret;                                                            \
 613 })
 614
 615 #define RB_FIRST(root, type, member)                                    \
 616         container_of_or_null(rb_first(root), type, member)
 617
 618 #define RB_LAST(root, type, member)                                     \
 619         container_of_or_null(rb_last(root), type, member)
 620
 621 #define RB_NEXT(ptr, member)                                            \
 622         container_of_or_null(rb_next(&(ptr)->member), typeof(*ptr), member)
 623
 624 #define RB_PREV(ptr, member)                                            \
 625         container_of_or_null(rb_prev(&(ptr)->member), typeof(*ptr), member)
 626
 627 /* Does linear interpolation between powers of two */
 628 static inline unsigned fract_exp_two(unsigned x, unsigned fract_bits)
 629 {
 630         unsigned fract = x & ~(~0 << fract_bits);
 631
 632         x >>= fract_bits;
 633         x   = 1 << x;
 634         x  += (x * fract) >> fract_bits;
 635
 636         return x;
 637 }
 638
 639 void bch2_bio_map(struct bio *bio, void *base);
 640
 641 static inline sector_t bdev_sectors(struct block_device *bdev)
 642 {
 643         return bdev->bd_inode->i_size >> 9;
 644 }
 645
 646 #define closure_bio_submit(bio, cl)                                     \
 647 do {                                                                    \
 648         closure_get(cl);                                                \
 649         submit_bio(bio);                                                \
 650 } while (0)
 651
 652 #define kthread_wait_freezable(cond)                                    \
 653 ({                                                                      \
 654         int _ret = 0;                                                   \
 655         while (1) {                                                     \
 656                 set_current_state(TASK_INTERRUPTIBLE);                  \
 657                 if (kthread_should_stop()) {                            \
 658                         _ret = -1;                                      \
 659                         break;                                          \
 660                 }                                                       \
 661                                                                         \
 662                 if (cond)                                               \
 663                         break;                                          \
 664                                                                         \
 665                 schedule();                                             \
 666                 try_to_freeze();                                        \
 667         }                                                               \
 668         set_current_state(TASK_RUNNING);                                \
 669         _ret;                                                           \
 670 })
 671
 672 size_t bch2_rand_range(size_t);
 673
 674 void memcpy_to_bio(struct bio *, struct bvec_iter, void *);
 675 void memcpy_from_bio(void *, struct bio *, struct bvec_iter);
 676
 677 static inline void __memcpy_u64s(void *dst, const void *src,
 678                                  unsigned u64s)
 679 {
 680 #ifdef CONFIG_X86_64
 681         long d0, d1, d2;
 682         asm volatile("rep ; movsq"
 683                      : "=&c" (d0), "=&D" (d1), "=&S" (d2)
 684                      : "0" (u64s), "1" (dst), "2" (src)
 685                      : "memory");
 686 #else
 687         u64 *d = dst;
 688         const u64 *s = src;
 689
 690         while (u64s--)
 691                 *d++ = *s++;
 692 #endif
 693 }
 694
 695 static inline void memcpy_u64s(void *dst, const void *src,
 696                                unsigned u64s)
 697 {
 698         EBUG_ON(!(dst >= src + u64s * sizeof(u64) ||
 699                  dst + u64s * sizeof(u64) <= src));
 700
 701         __memcpy_u64s(dst, src, u64s);
 702 }
 703
 704 static inline void __memmove_u64s_down(void *dst, const void *src,
 705                                        unsigned u64s)
 706 {
 707         __memcpy_u64s(dst, src, u64s);
 708 }
 709
 710 static inline void memmove_u64s_down(void *dst, const void *src,
 711                                      unsigned u64s)
 712 {
 713         EBUG_ON(dst > src);
 714
 715         __memmove_u64s_down(dst, src, u64s);
 716 }
 717
 718 static inline void __memmove_u64s_up(void *_dst, const void *_src,
 719                                      unsigned u64s)
 720 {
 721         u64 *dst = (u64 *) _dst + u64s - 1;
 722         u64 *src = (u64 *) _src + u64s - 1;
 723
 724 #ifdef CONFIG_X86_64
 725         long d0, d1, d2;
 726         asm volatile("std ;\n"
 727                      "rep ; movsq\n"
 728                      "cld ;\n"
 729                      : "=&c" (d0), "=&D" (d1), "=&S" (d2)
 730                      : "0" (u64s), "1" (dst), "2" (src)
 731                      : "memory");
 732 #else
 733         while (u64s--)
 734                 *dst-- = *src--;
 735 #endif
 736 }
 737
 738 static inline void memmove_u64s_up(void *dst, const void *src,
 739                                    unsigned u64s)
 740 {
 741         EBUG_ON(dst < src);
 742
 743         __memmove_u64s_up(dst, src, u64s);
 744 }
 745
 746 static inline void memmove_u64s(void *dst, const void *src,
 747                                 unsigned u64s)
 748 {
 749         if (dst < src)
 750                 __memmove_u64s_down(dst, src, u64s);
 751         else
 752                 __memmove_u64s_up(dst, src, u64s);
 753 }
 754
 755 static inline struct bio_vec next_contig_bvec(struct bio *bio,
 756                                               struct bvec_iter *iter)
 757 {
 758         struct bio_vec bv = bio_iter_iovec(bio, *iter);
 759
 760         bio_advance_iter(bio, iter, bv.bv_len);
 761 #ifndef CONFIG_HIGHMEM
 762         while (iter->bi_size) {
 763                 struct bio_vec next = bio_iter_iovec(bio, *iter);
 764
 765                 if (page_address(bv.bv_page) + bv.bv_offset + bv.bv_len !=
 766                     page_address(next.bv_page) + next.bv_offset)
 767                         break;
 768
 769                 bv.bv_len += next.bv_len;
 770                 bio_advance_iter(bio, iter, next.bv_len);
 771         }
 772 #endif
 773         return bv;
 774 }
 775
 776 #define __bio_for_each_contig_segment(bv, bio, iter, start)             \
 777         for (iter = (start);                                            \
 778              (iter).bi_size &&                                          \
 779                 ((bv = next_contig_bvec((bio), &(iter))), 1);)
 780
 781 #define bio_for_each_contig_segment(bv, bio, iter)                      \
 782         __bio_for_each_contig_segment(bv, bio, iter, (bio)->bi_iter)
 783
 784 size_t bch_scnmemcpy(char *, size_t, const char *, size_t);
 785
 786 void sort_cmp_size(void *base, size_t num, size_t size,
 787           int (*cmp_func)(const void *, const void *, size_t),
 788           void (*swap_func)(void *, void *, size_t));
 789
 790 #endif /* _BCACHE_UTIL_H */