499 lines · c
1/* SPDX-License-Identifier: GPL-2.0 */2 3#ifndef _BCACHE_UTIL_H4#define _BCACHE_UTIL_H5 6#include <linux/blkdev.h>7#include <linux/closure.h>8#include <linux/errno.h>9#include <linux/kernel.h>10#include <linux/sched/clock.h>11#include <linux/llist.h>12#include <linux/min_heap.h>13#include <linux/ratelimit.h>14#include <linux/vmalloc.h>15#include <linux/workqueue.h>16#include <linux/crc64.h>17 18struct closure;19 20#ifdef CONFIG_BCACHE_DEBUG21 22#define EBUG_ON(cond) BUG_ON(cond)23#define atomic_dec_bug(v) BUG_ON(atomic_dec_return(v) < 0)24#define atomic_inc_bug(v, i) BUG_ON(atomic_inc_return(v) <= i)25 26#else /* DEBUG */27 28#define EBUG_ON(cond) do { if (cond) do {} while (0); } while (0)29#define atomic_dec_bug(v) atomic_dec(v)30#define atomic_inc_bug(v, i) atomic_inc(v)31 32#endif33 34#define init_heap(heap, _size, gfp) \35({ \36 size_t _bytes; \37 (heap)->nr = 0; \38 (heap)->size = (_size); \39 _bytes = (heap)->size * sizeof(*(heap)->data); \40 (heap)->data = kvmalloc(_bytes, (gfp) & GFP_KERNEL); \41 (heap)->data; \42})43 44#define free_heap(heap) \45do { \46 kvfree((heap)->data); \47 (heap)->data = NULL; \48} while (0)49 50#define DECLARE_FIFO(type, name) \51 struct { \52 size_t front, back, size, mask; \53 type *data; \54 } name55 56#define fifo_for_each(c, fifo, iter) \57 for (iter = (fifo)->front; \58 c = (fifo)->data[iter], iter != (fifo)->back; \59 iter = (iter + 1) & (fifo)->mask)60 61#define __init_fifo(fifo, gfp) \62({ \63 size_t _allocated_size, _bytes; \64 BUG_ON(!(fifo)->size); \65 \66 _allocated_size = roundup_pow_of_two((fifo)->size + 1); \67 _bytes = _allocated_size * sizeof(*(fifo)->data); \68 \69 (fifo)->mask = _allocated_size - 1; \70 (fifo)->front = (fifo)->back = 0; \71 \72 (fifo)->data = kvmalloc(_bytes, (gfp) & GFP_KERNEL); \73 (fifo)->data; \74})75 76#define init_fifo_exact(fifo, _size, gfp) \77({ \78 (fifo)->size = (_size); \79 __init_fifo(fifo, gfp); \80})81 82#define init_fifo(fifo, _size, gfp) \83({ \84 (fifo)->size = (_size); \85 if ((fifo)->size > 4) \86 (fifo)->size = roundup_pow_of_two((fifo)->size) - 1; \87 __init_fifo(fifo, gfp); \88})89 90#define free_fifo(fifo) \91do { \92 kvfree((fifo)->data); \93 (fifo)->data = NULL; \94} while (0)95 96#define fifo_used(fifo) (((fifo)->back - (fifo)->front) & (fifo)->mask)97#define fifo_free(fifo) ((fifo)->size - fifo_used(fifo))98 99#define fifo_empty(fifo) (!fifo_used(fifo))100#define fifo_full(fifo) (!fifo_free(fifo))101 102#define fifo_front(fifo) ((fifo)->data[(fifo)->front])103#define fifo_back(fifo) \104 ((fifo)->data[((fifo)->back - 1) & (fifo)->mask])105 106#define fifo_idx(fifo, p) (((p) - &fifo_front(fifo)) & (fifo)->mask)107 108#define fifo_push_back(fifo, i) \109({ \110 bool _r = !fifo_full((fifo)); \111 if (_r) { \112 (fifo)->data[(fifo)->back++] = (i); \113 (fifo)->back &= (fifo)->mask; \114 } \115 _r; \116})117 118#define fifo_pop_front(fifo, i) \119({ \120 bool _r = !fifo_empty((fifo)); \121 if (_r) { \122 (i) = (fifo)->data[(fifo)->front++]; \123 (fifo)->front &= (fifo)->mask; \124 } \125 _r; \126})127 128#define fifo_push_front(fifo, i) \129({ \130 bool _r = !fifo_full((fifo)); \131 if (_r) { \132 --(fifo)->front; \133 (fifo)->front &= (fifo)->mask; \134 (fifo)->data[(fifo)->front] = (i); \135 } \136 _r; \137})138 139#define fifo_pop_back(fifo, i) \140({ \141 bool _r = !fifo_empty((fifo)); \142 if (_r) { \143 --(fifo)->back; \144 (fifo)->back &= (fifo)->mask; \145 (i) = (fifo)->data[(fifo)->back] \146 } \147 _r; \148})149 150#define fifo_push(fifo, i) fifo_push_back(fifo, (i))151#define fifo_pop(fifo, i) fifo_pop_front(fifo, (i))152 153#define fifo_swap(l, r) \154do { \155 swap((l)->front, (r)->front); \156 swap((l)->back, (r)->back); \157 swap((l)->size, (r)->size); \158 swap((l)->mask, (r)->mask); \159 swap((l)->data, (r)->data); \160} while (0)161 162#define fifo_move(dest, src) \163do { \164 typeof(*((dest)->data)) _t; \165 while (!fifo_full(dest) && \166 fifo_pop(src, _t)) \167 fifo_push(dest, _t); \168} while (0)169 170/*171 * Simple array based allocator - preallocates a number of elements and you can172 * never allocate more than that, also has no locking.173 *174 * Handy because if you know you only need a fixed number of elements you don't175 * have to worry about memory allocation failure, and sometimes a mempool isn't176 * what you want.177 *178 * We treat the free elements as entries in a singly linked list, and the179 * freelist as a stack - allocating and freeing push and pop off the freelist.180 */181 182#define DECLARE_ARRAY_ALLOCATOR(type, name, size) \183 struct { \184 type *freelist; \185 type data[size]; \186 } name187 188#define array_alloc(array) \189({ \190 typeof((array)->freelist) _ret = (array)->freelist; \191 \192 if (_ret) \193 (array)->freelist = *((typeof((array)->freelist) *) _ret);\194 \195 _ret; \196})197 198#define array_free(array, ptr) \199do { \200 typeof((array)->freelist) _ptr = ptr; \201 \202 *((typeof((array)->freelist) *) _ptr) = (array)->freelist; \203 (array)->freelist = _ptr; \204} while (0)205 206#define array_allocator_init(array) \207do { \208 typeof((array)->freelist) _i; \209 \210 BUILD_BUG_ON(sizeof((array)->data[0]) < sizeof(void *)); \211 (array)->freelist = NULL; \212 \213 for (_i = (array)->data; \214 _i < (array)->data + ARRAY_SIZE((array)->data); \215 _i++) \216 array_free(array, _i); \217} while (0)218 219#define array_freelist_empty(array) ((array)->freelist == NULL)220 221#define ANYSINT_MAX(t) \222 ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1)223 224int bch_strtoint_h(const char *cp, int *res);225int bch_strtouint_h(const char *cp, unsigned int *res);226int bch_strtoll_h(const char *cp, long long *res);227int bch_strtoull_h(const char *cp, unsigned long long *res);228 229static inline int bch_strtol_h(const char *cp, long *res)230{231#if BITS_PER_LONG == 32232 return bch_strtoint_h(cp, (int *) res);233#else234 return bch_strtoll_h(cp, (long long *) res);235#endif236}237 238static inline int bch_strtoul_h(const char *cp, long *res)239{240#if BITS_PER_LONG == 32241 return bch_strtouint_h(cp, (unsigned int *) res);242#else243 return bch_strtoull_h(cp, (unsigned long long *) res);244#endif245}246 247#define strtoi_h(cp, res) \248 (__builtin_types_compatible_p(typeof(*res), int) \249 ? bch_strtoint_h(cp, (void *) res) \250 : __builtin_types_compatible_p(typeof(*res), long) \251 ? bch_strtol_h(cp, (void *) res) \252 : __builtin_types_compatible_p(typeof(*res), long long) \253 ? bch_strtoll_h(cp, (void *) res) \254 : __builtin_types_compatible_p(typeof(*res), unsigned int) \255 ? bch_strtouint_h(cp, (void *) res) \256 : __builtin_types_compatible_p(typeof(*res), unsigned long) \257 ? bch_strtoul_h(cp, (void *) res) \258 : __builtin_types_compatible_p(typeof(*res), unsigned long long)\259 ? bch_strtoull_h(cp, (void *) res) : -EINVAL)260 261#define strtoul_safe(cp, var) \262({ \263 unsigned long _v; \264 int _r = kstrtoul(cp, 10, &_v); \265 if (!_r) \266 var = _v; \267 _r; \268})269 270#define strtoul_safe_clamp(cp, var, min, max) \271({ \272 unsigned long _v; \273 int _r = kstrtoul(cp, 10, &_v); \274 if (!_r) \275 var = clamp_t(typeof(var), _v, min, max); \276 _r; \277})278 279ssize_t bch_hprint(char *buf, int64_t v);280 281bool bch_is_zero(const char *p, size_t n);282int bch_parse_uuid(const char *s, char *uuid);283 284struct time_stats {285 spinlock_t lock;286 /*287 * all fields are in nanoseconds, averages are ewmas stored left shifted288 * by 8289 */290 uint64_t max_duration;291 uint64_t average_duration;292 uint64_t average_frequency;293 uint64_t last;294};295 296void bch_time_stats_update(struct time_stats *stats, uint64_t time);297 298static inline unsigned int local_clock_us(void)299{300 return local_clock() >> 10;301}302 303#define NSEC_PER_ns 1L304#define NSEC_PER_us NSEC_PER_USEC305#define NSEC_PER_ms NSEC_PER_MSEC306#define NSEC_PER_sec NSEC_PER_SEC307 308#define __print_time_stat(stats, name, stat, units) \309 sysfs_print(name ## _ ## stat ## _ ## units, \310 div_u64((stats)->stat >> 8, NSEC_PER_ ## units))311 312#define sysfs_print_time_stats(stats, name, \313 frequency_units, \314 duration_units) \315do { \316 __print_time_stat(stats, name, \317 average_frequency, frequency_units); \318 __print_time_stat(stats, name, \319 average_duration, duration_units); \320 sysfs_print(name ## _ ##max_duration ## _ ## duration_units, \321 div_u64((stats)->max_duration, \322 NSEC_PER_ ## duration_units)); \323 \324 sysfs_print(name ## _last_ ## frequency_units, (stats)->last \325 ? div_s64(local_clock() - (stats)->last, \326 NSEC_PER_ ## frequency_units) \327 : -1LL); \328} while (0)329 330#define sysfs_time_stats_attribute(name, \331 frequency_units, \332 duration_units) \333read_attribute(name ## _average_frequency_ ## frequency_units); \334read_attribute(name ## _average_duration_ ## duration_units); \335read_attribute(name ## _max_duration_ ## duration_units); \336read_attribute(name ## _last_ ## frequency_units)337 338#define sysfs_time_stats_attribute_list(name, \339 frequency_units, \340 duration_units) \341&sysfs_ ## name ## _average_frequency_ ## frequency_units, \342&sysfs_ ## name ## _average_duration_ ## duration_units, \343&sysfs_ ## name ## _max_duration_ ## duration_units, \344&sysfs_ ## name ## _last_ ## frequency_units,345 346#define ewma_add(ewma, val, weight, factor) \347({ \348 (ewma) *= (weight) - 1; \349 (ewma) += (val) << factor; \350 (ewma) /= (weight); \351 (ewma) >> factor; \352})353 354struct bch_ratelimit {355 /* Next time we want to do some work, in nanoseconds */356 uint64_t next;357 358 /*359 * Rate at which we want to do work, in units per second360 * The units here correspond to the units passed to bch_next_delay()361 */362 atomic_long_t rate;363};364 365static inline void bch_ratelimit_reset(struct bch_ratelimit *d)366{367 d->next = local_clock();368}369 370uint64_t bch_next_delay(struct bch_ratelimit *d, uint64_t done);371 372#define __DIV_SAFE(n, d, zero) \373({ \374 typeof(n) _n = (n); \375 typeof(d) _d = (d); \376 _d ? _n / _d : zero; \377})378 379#define DIV_SAFE(n, d) __DIV_SAFE(n, d, 0)380 381#define container_of_or_null(ptr, type, member) \382({ \383 typeof(ptr) _ptr = ptr; \384 _ptr ? container_of(_ptr, type, member) : NULL; \385})386 387#define RB_INSERT(root, new, member, cmp) \388({ \389 __label__ dup; \390 struct rb_node **n = &(root)->rb_node, *parent = NULL; \391 typeof(new) this; \392 int res, ret = -1; \393 \394 while (*n) { \395 parent = *n; \396 this = container_of(*n, typeof(*(new)), member); \397 res = cmp(new, this); \398 if (!res) \399 goto dup; \400 n = res < 0 \401 ? &(*n)->rb_left \402 : &(*n)->rb_right; \403 } \404 \405 rb_link_node(&(new)->member, parent, n); \406 rb_insert_color(&(new)->member, root); \407 ret = 0; \408dup: \409 ret; \410})411 412#define RB_SEARCH(root, search, member, cmp) \413({ \414 struct rb_node *n = (root)->rb_node; \415 typeof(&(search)) this, ret = NULL; \416 int res; \417 \418 while (n) { \419 this = container_of(n, typeof(search), member); \420 res = cmp(&(search), this); \421 if (!res) { \422 ret = this; \423 break; \424 } \425 n = res < 0 \426 ? n->rb_left \427 : n->rb_right; \428 } \429 ret; \430})431 432#define RB_GREATER(root, search, member, cmp) \433({ \434 struct rb_node *n = (root)->rb_node; \435 typeof(&(search)) this, ret = NULL; \436 int res; \437 \438 while (n) { \439 this = container_of(n, typeof(search), member); \440 res = cmp(&(search), this); \441 if (res < 0) { \442 ret = this; \443 n = n->rb_left; \444 } else \445 n = n->rb_right; \446 } \447 ret; \448})449 450#define RB_FIRST(root, type, member) \451 container_of_or_null(rb_first(root), type, member)452 453#define RB_LAST(root, type, member) \454 container_of_or_null(rb_last(root), type, member)455 456#define RB_NEXT(ptr, member) \457 container_of_or_null(rb_next(&(ptr)->member), typeof(*ptr), member)458 459#define RB_PREV(ptr, member) \460 container_of_or_null(rb_prev(&(ptr)->member), typeof(*ptr), member)461 462static inline uint64_t bch_crc64(const void *p, size_t len)463{464 uint64_t crc = 0xffffffffffffffffULL;465 466 crc = crc64_be(crc, p, len);467 return crc ^ 0xffffffffffffffffULL;468}469 470/*471 * A stepwise-linear pseudo-exponential. This returns 1 << (x >>472 * frac_bits), with the less-significant bits filled in by linear473 * interpolation.474 *475 * This can also be interpreted as a floating-point number format,476 * where the low frac_bits are the mantissa (with implicit leading477 * 1 bit), and the more significant bits are the exponent.478 * The return value is 1.mantissa * 2^exponent.479 *480 * The way this is used, fract_bits is 6 and the largest possible481 * input is CONGESTED_MAX-1 = 1023 (exponent 16, mantissa 0x1.fc),482 * so the maximum output is 0x1fc00.483 */484static inline unsigned int fract_exp_two(unsigned int x,485 unsigned int fract_bits)486{487 unsigned int mantissa = 1 << fract_bits; /* Implicit bit */488 489 mantissa += x & (mantissa - 1);490 x >>= fract_bits; /* The exponent */491 /* Largest intermediate value 0x7f0000 */492 return mantissa << x >> fract_bits;493}494 495void bch_bio_map(struct bio *bio, void *base);496int bch_bio_alloc_pages(struct bio *bio, gfp_t gfp_mask);497 498#endif /* _BCACHE_UTIL_H */499