11c6fdbd8SKent Overstreet // SPDX-License-Identifier: GPL-2.0 21c6fdbd8SKent Overstreet /* 31c6fdbd8SKent Overstreet * random utiility code, for bcache but in theory not specific to bcache 41c6fdbd8SKent Overstreet * 51c6fdbd8SKent Overstreet * Copyright 2010, 2011 Kent Overstreet <kent.overstreet@gmail.com> 61c6fdbd8SKent Overstreet * Copyright 2012 Google, Inc. 71c6fdbd8SKent Overstreet */ 81c6fdbd8SKent Overstreet 91c6fdbd8SKent Overstreet #include <linux/bio.h> 101c6fdbd8SKent Overstreet #include <linux/blkdev.h> 11a8f35428SKent Overstreet #include <linux/console.h> 121c6fdbd8SKent Overstreet #include <linux/ctype.h> 131c6fdbd8SKent Overstreet #include <linux/debugfs.h> 141c6fdbd8SKent Overstreet #include <linux/freezer.h> 151c6fdbd8SKent Overstreet #include <linux/kthread.h> 161c6fdbd8SKent Overstreet #include <linux/log2.h> 171c6fdbd8SKent Overstreet #include <linux/math64.h> 181c6fdbd8SKent Overstreet #include <linux/percpu.h> 191c6fdbd8SKent Overstreet #include <linux/preempt.h> 201c6fdbd8SKent Overstreet #include <linux/random.h> 211c6fdbd8SKent Overstreet #include <linux/seq_file.h> 221c6fdbd8SKent Overstreet #include <linux/string.h> 231c6fdbd8SKent Overstreet #include <linux/types.h> 241c6fdbd8SKent Overstreet #include <linux/sched/clock.h> 251c6fdbd8SKent Overstreet 261c6fdbd8SKent Overstreet #include "eytzinger.h" 271c6fdbd8SKent Overstreet #include "util.h" 281c6fdbd8SKent Overstreet 291c6fdbd8SKent Overstreet static const char si_units[] = "?kMGTPEZY"; 301c6fdbd8SKent Overstreet 31a5d18f9eSKent Overstreet /* string_get_size units: */ 32a5d18f9eSKent Overstreet static const char *const units_2[] = { 33a5d18f9eSKent Overstreet "B", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB", "ZiB", "YiB" 34a5d18f9eSKent Overstreet }; 35a5d18f9eSKent Overstreet static const char *const units_10[] = { 36a5d18f9eSKent Overstreet "B", "kB", "MB", "GB", "TB", "PB", "EB", "ZB", "YB" 37a5d18f9eSKent Overstreet }; 381c6fdbd8SKent Overstreet 39a5d18f9eSKent Overstreet static int parse_u64(const char *cp, u64 *res) 40a5d18f9eSKent Overstreet { 41a5d18f9eSKent Overstreet const char *start = cp; 42a5d18f9eSKent Overstreet u64 v = 0; 431c6fdbd8SKent Overstreet 441c6fdbd8SKent Overstreet if (!isdigit(*cp)) 451c6fdbd8SKent Overstreet return -EINVAL; 461c6fdbd8SKent Overstreet 471c6fdbd8SKent Overstreet do { 481c6fdbd8SKent Overstreet if (v > U64_MAX / 10) 491c6fdbd8SKent Overstreet return -ERANGE; 501c6fdbd8SKent Overstreet v *= 10; 511c6fdbd8SKent Overstreet if (v > U64_MAX - (*cp - '0')) 521c6fdbd8SKent Overstreet return -ERANGE; 531c6fdbd8SKent Overstreet v += *cp - '0'; 541c6fdbd8SKent Overstreet cp++; 551c6fdbd8SKent Overstreet } while (isdigit(*cp)); 561c6fdbd8SKent Overstreet 57a5d18f9eSKent Overstreet *res = v; 58a5d18f9eSKent Overstreet return cp - start; 59a5d18f9eSKent Overstreet } 60a5d18f9eSKent Overstreet 61a5d18f9eSKent Overstreet static int bch2_pow(u64 n, u64 p, u64 *res) 62a5d18f9eSKent Overstreet { 63a5d18f9eSKent Overstreet *res = 1; 64a5d18f9eSKent Overstreet 65a5d18f9eSKent Overstreet while (p--) { 66a5d18f9eSKent Overstreet if (*res > div_u64(U64_MAX, n)) 67a5d18f9eSKent Overstreet return -ERANGE; 68a5d18f9eSKent Overstreet *res *= n; 69a5d18f9eSKent Overstreet } 70a5d18f9eSKent Overstreet return 0; 71a5d18f9eSKent Overstreet } 72a5d18f9eSKent Overstreet 73a5d18f9eSKent Overstreet static int parse_unit_suffix(const char *cp, u64 *res) 74a5d18f9eSKent Overstreet { 75a5d18f9eSKent Overstreet const char *start = cp; 76a5d18f9eSKent Overstreet u64 base = 1024; 77a5d18f9eSKent Overstreet unsigned u; 78a5d18f9eSKent Overstreet int ret; 79a5d18f9eSKent Overstreet 80a5d18f9eSKent Overstreet if (*cp == ' ') 81a5d18f9eSKent Overstreet cp++; 82a5d18f9eSKent Overstreet 831c6fdbd8SKent Overstreet for (u = 1; u < strlen(si_units); u++) 841c6fdbd8SKent Overstreet if (*cp == si_units[u]) { 851c6fdbd8SKent Overstreet cp++; 861c6fdbd8SKent Overstreet goto got_unit; 871c6fdbd8SKent Overstreet } 88a5d18f9eSKent Overstreet 89a5d18f9eSKent Overstreet for (u = 0; u < ARRAY_SIZE(units_2); u++) 90a5d18f9eSKent Overstreet if (!strncmp(cp, units_2[u], strlen(units_2[u]))) { 91a5d18f9eSKent Overstreet cp += strlen(units_2[u]); 92a5d18f9eSKent Overstreet goto got_unit; 93a5d18f9eSKent Overstreet } 94a5d18f9eSKent Overstreet 95a5d18f9eSKent Overstreet for (u = 0; u < ARRAY_SIZE(units_10); u++) 96a5d18f9eSKent Overstreet if (!strncmp(cp, units_10[u], strlen(units_10[u]))) { 97a5d18f9eSKent Overstreet cp += strlen(units_10[u]); 98a5d18f9eSKent Overstreet base = 1000; 99a5d18f9eSKent Overstreet goto got_unit; 100a5d18f9eSKent Overstreet } 101a5d18f9eSKent Overstreet 102a5d18f9eSKent Overstreet *res = 1; 103a5d18f9eSKent Overstreet return 0; 1041c6fdbd8SKent Overstreet got_unit: 105a5d18f9eSKent Overstreet ret = bch2_pow(base, u, res); 106a5d18f9eSKent Overstreet if (ret) 107a5d18f9eSKent Overstreet return ret; 108a5d18f9eSKent Overstreet 109a5d18f9eSKent Overstreet return cp - start; 110a5d18f9eSKent Overstreet } 111a5d18f9eSKent Overstreet 112a5d18f9eSKent Overstreet #define parse_or_ret(cp, _f) \ 113a5d18f9eSKent Overstreet do { \ 114a5d18f9eSKent Overstreet int ret = _f; \ 115a5d18f9eSKent Overstreet if (ret < 0) \ 116a5d18f9eSKent Overstreet return ret; \ 117a5d18f9eSKent Overstreet cp += ret; \ 118a5d18f9eSKent Overstreet } while (0) 119a5d18f9eSKent Overstreet 120a5d18f9eSKent Overstreet static int __bch2_strtou64_h(const char *cp, u64 *res) 121a5d18f9eSKent Overstreet { 122a5d18f9eSKent Overstreet const char *start = cp; 123a5d18f9eSKent Overstreet u64 v = 0, b, f_n = 0, f_d = 1; 124a5d18f9eSKent Overstreet int ret; 125a5d18f9eSKent Overstreet 126a5d18f9eSKent Overstreet parse_or_ret(cp, parse_u64(cp, &v)); 127a5d18f9eSKent Overstreet 128a5d18f9eSKent Overstreet if (*cp == '.') { 129a5d18f9eSKent Overstreet cp++; 130a5d18f9eSKent Overstreet ret = parse_u64(cp, &f_n); 131a5d18f9eSKent Overstreet if (ret < 0) 132a5d18f9eSKent Overstreet return ret; 133a5d18f9eSKent Overstreet cp += ret; 134a5d18f9eSKent Overstreet 135a5d18f9eSKent Overstreet ret = bch2_pow(10, ret, &f_d); 136a5d18f9eSKent Overstreet if (ret) 137a5d18f9eSKent Overstreet return ret; 138a5d18f9eSKent Overstreet } 139a5d18f9eSKent Overstreet 140a5d18f9eSKent Overstreet parse_or_ret(cp, parse_unit_suffix(cp, &b)); 141a5d18f9eSKent Overstreet 142a5d18f9eSKent Overstreet if (v > div_u64(U64_MAX, b)) 143a5d18f9eSKent Overstreet return -ERANGE; 144a5d18f9eSKent Overstreet v *= b; 145a5d18f9eSKent Overstreet 146a5d18f9eSKent Overstreet if (f_n > div_u64(U64_MAX, b)) 147a5d18f9eSKent Overstreet return -ERANGE; 148a5d18f9eSKent Overstreet 149a5d18f9eSKent Overstreet f_n = div_u64(f_n * b, f_d); 150a5d18f9eSKent Overstreet if (v + f_n < v) 151a5d18f9eSKent Overstreet return -ERANGE; 152a5d18f9eSKent Overstreet v += f_n; 153a5d18f9eSKent Overstreet 154a5d18f9eSKent Overstreet *res = v; 155a5d18f9eSKent Overstreet return cp - start; 156a5d18f9eSKent Overstreet } 157a5d18f9eSKent Overstreet 158a5d18f9eSKent Overstreet static int __bch2_strtoh(const char *cp, u64 *res, 159a5d18f9eSKent Overstreet u64 t_max, bool t_signed) 160a5d18f9eSKent Overstreet { 161a5d18f9eSKent Overstreet bool positive = *cp != '-'; 162a5d18f9eSKent Overstreet u64 v = 0; 163a5d18f9eSKent Overstreet 164a5d18f9eSKent Overstreet if (*cp == '+' || *cp == '-') 165a5d18f9eSKent Overstreet cp++; 166a5d18f9eSKent Overstreet 167a5d18f9eSKent Overstreet parse_or_ret(cp, __bch2_strtou64_h(cp, &v)); 168a5d18f9eSKent Overstreet 1691c6fdbd8SKent Overstreet if (*cp == '\n') 1701c6fdbd8SKent Overstreet cp++; 1711c6fdbd8SKent Overstreet if (*cp) 1721c6fdbd8SKent Overstreet return -EINVAL; 1731c6fdbd8SKent Overstreet 1741c6fdbd8SKent Overstreet if (positive) { 1751c6fdbd8SKent Overstreet if (v > t_max) 1761c6fdbd8SKent Overstreet return -ERANGE; 1771c6fdbd8SKent Overstreet } else { 1781c6fdbd8SKent Overstreet if (v && !t_signed) 1791c6fdbd8SKent Overstreet return -ERANGE; 1801c6fdbd8SKent Overstreet 1811c6fdbd8SKent Overstreet if (v > t_max + 1) 1821c6fdbd8SKent Overstreet return -ERANGE; 1831c6fdbd8SKent Overstreet v = -v; 1841c6fdbd8SKent Overstreet } 1851c6fdbd8SKent Overstreet 1861c6fdbd8SKent Overstreet *res = v; 1871c6fdbd8SKent Overstreet return 0; 1881c6fdbd8SKent Overstreet } 1891c6fdbd8SKent Overstreet 1901c6fdbd8SKent Overstreet #define STRTO_H(name, type) \ 1911c6fdbd8SKent Overstreet int bch2_ ## name ## _h(const char *cp, type *res) \ 1921c6fdbd8SKent Overstreet { \ 193a5d18f9eSKent Overstreet u64 v = 0; \ 1941c6fdbd8SKent Overstreet int ret = __bch2_strtoh(cp, &v, ANYSINT_MAX(type), \ 1951c6fdbd8SKent Overstreet ANYSINT_MAX(type) != ((type) ~0ULL)); \ 1961c6fdbd8SKent Overstreet *res = v; \ 1971c6fdbd8SKent Overstreet return ret; \ 1981c6fdbd8SKent Overstreet } 1991c6fdbd8SKent Overstreet 2001c6fdbd8SKent Overstreet STRTO_H(strtoint, int) 2011c6fdbd8SKent Overstreet STRTO_H(strtouint, unsigned int) 2021c6fdbd8SKent Overstreet STRTO_H(strtoll, long long) 2031c6fdbd8SKent Overstreet STRTO_H(strtoull, unsigned long long) 2040b847a19SKent Overstreet STRTO_H(strtou64, u64) 2051c6fdbd8SKent Overstreet 2061c6fdbd8SKent Overstreet u64 bch2_read_flag_list(char *opt, const char * const list[]) 2071c6fdbd8SKent Overstreet { 2081c6fdbd8SKent Overstreet u64 ret = 0; 2099d8022dbSKent Overstreet char *p, *s, *d = kstrdup(opt, GFP_KERNEL); 2101c6fdbd8SKent Overstreet 2111c6fdbd8SKent Overstreet if (!d) 2121c6fdbd8SKent Overstreet return -ENOMEM; 2131c6fdbd8SKent Overstreet 2141c6fdbd8SKent Overstreet s = strim(d); 2151c6fdbd8SKent Overstreet 2161c6fdbd8SKent Overstreet while ((p = strsep(&s, ","))) { 2171c6fdbd8SKent Overstreet int flag = match_string(list, -1, p); 2181c6fdbd8SKent Overstreet if (flag < 0) { 2191c6fdbd8SKent Overstreet ret = -1; 2201c6fdbd8SKent Overstreet break; 2211c6fdbd8SKent Overstreet } 2221c6fdbd8SKent Overstreet 2231c6fdbd8SKent Overstreet ret |= 1 << flag; 2241c6fdbd8SKent Overstreet } 2251c6fdbd8SKent Overstreet 2261c6fdbd8SKent Overstreet kfree(d); 2271c6fdbd8SKent Overstreet 2281c6fdbd8SKent Overstreet return ret; 2291c6fdbd8SKent Overstreet } 2301c6fdbd8SKent Overstreet 2311c6fdbd8SKent Overstreet bool bch2_is_zero(const void *_p, size_t n) 2321c6fdbd8SKent Overstreet { 2331c6fdbd8SKent Overstreet const char *p = _p; 2341c6fdbd8SKent Overstreet size_t i; 2351c6fdbd8SKent Overstreet 2361c6fdbd8SKent Overstreet for (i = 0; i < n; i++) 2371c6fdbd8SKent Overstreet if (p[i]) 2381c6fdbd8SKent Overstreet return false; 2391c6fdbd8SKent Overstreet return true; 2401c6fdbd8SKent Overstreet } 2411c6fdbd8SKent Overstreet 242d0b50524SKent Overstreet void bch2_prt_u64_binary(struct printbuf *out, u64 v, unsigned nr_bits) 243d0b50524SKent Overstreet { 244d0b50524SKent Overstreet while (nr_bits) 245d0b50524SKent Overstreet prt_char(out, '0' + ((v >> --nr_bits) & 1)); 246d0b50524SKent Overstreet } 247d0b50524SKent Overstreet 248a8f35428SKent Overstreet void bch2_print_string_as_lines(const char *prefix, const char *lines) 249a8f35428SKent Overstreet { 250a8f35428SKent Overstreet const char *p; 251a8f35428SKent Overstreet 252a8f35428SKent Overstreet if (!lines) { 253a8f35428SKent Overstreet printk("%s (null)\n", prefix); 254a8f35428SKent Overstreet return; 255a8f35428SKent Overstreet } 256a8f35428SKent Overstreet 257a8f35428SKent Overstreet console_lock(); 258a8f35428SKent Overstreet while (1) { 259a8f35428SKent Overstreet p = strchrnul(lines, '\n'); 260a8f35428SKent Overstreet printk("%s%.*s\n", prefix, (int) (p - lines), lines); 261a8f35428SKent Overstreet if (!*p) 262a8f35428SKent Overstreet break; 263a8f35428SKent Overstreet lines = p + 1; 264a8f35428SKent Overstreet } 265a8f35428SKent Overstreet console_unlock(); 266a8f35428SKent Overstreet } 267a8f35428SKent Overstreet 268*1148a97fSKent Overstreet int bch2_prt_backtrace(struct printbuf *out, struct task_struct *task) 269*1148a97fSKent Overstreet { 270*1148a97fSKent Overstreet unsigned long entries[32]; 271*1148a97fSKent Overstreet unsigned i, nr_entries; 272*1148a97fSKent Overstreet int ret; 273*1148a97fSKent Overstreet 274*1148a97fSKent Overstreet ret = down_read_killable(&task->signal->exec_update_lock); 275*1148a97fSKent Overstreet if (ret) 276*1148a97fSKent Overstreet return ret; 277*1148a97fSKent Overstreet 278*1148a97fSKent Overstreet nr_entries = stack_trace_save_tsk(task, entries, ARRAY_SIZE(entries), 0); 279*1148a97fSKent Overstreet for (i = 0; i < nr_entries; i++) { 280*1148a97fSKent Overstreet prt_printf(out, "[<0>] %pB", (void *)entries[i]); 281*1148a97fSKent Overstreet prt_newline(out); 282*1148a97fSKent Overstreet } 283*1148a97fSKent Overstreet 284*1148a97fSKent Overstreet up_read(&task->signal->exec_update_lock); 285*1148a97fSKent Overstreet return 0; 286*1148a97fSKent Overstreet } 287*1148a97fSKent Overstreet 2881c6fdbd8SKent Overstreet /* time stats: */ 2891c6fdbd8SKent Overstreet 2901c6fdbd8SKent Overstreet #ifndef CONFIG_BCACHEFS_NO_LATENCY_ACCT 2911c6fdbd8SKent Overstreet static void bch2_quantiles_update(struct bch2_quantiles *q, u64 v) 2921c6fdbd8SKent Overstreet { 2931c6fdbd8SKent Overstreet unsigned i = 0; 2941c6fdbd8SKent Overstreet 2951c6fdbd8SKent Overstreet while (i < ARRAY_SIZE(q->entries)) { 2961c6fdbd8SKent Overstreet struct bch2_quantile_entry *e = q->entries + i; 2971c6fdbd8SKent Overstreet 2981c6fdbd8SKent Overstreet if (unlikely(!e->step)) { 2991c6fdbd8SKent Overstreet e->m = v; 3001c6fdbd8SKent Overstreet e->step = max_t(unsigned, v / 2, 1024); 3011c6fdbd8SKent Overstreet } else if (e->m > v) { 3021c6fdbd8SKent Overstreet e->m = e->m >= e->step 3031c6fdbd8SKent Overstreet ? e->m - e->step 3041c6fdbd8SKent Overstreet : 0; 3051c6fdbd8SKent Overstreet } else if (e->m < v) { 3061c6fdbd8SKent Overstreet e->m = e->m + e->step > e->m 3071c6fdbd8SKent Overstreet ? e->m + e->step 3081c6fdbd8SKent Overstreet : U32_MAX; 3091c6fdbd8SKent Overstreet } 3101c6fdbd8SKent Overstreet 3111c6fdbd8SKent Overstreet if ((e->m > v ? e->m - v : v - e->m) < e->step) 3121c6fdbd8SKent Overstreet e->step = max_t(unsigned, e->step / 2, 1); 3131c6fdbd8SKent Overstreet 3141c6fdbd8SKent Overstreet if (v >= e->m) 3151c6fdbd8SKent Overstreet break; 3161c6fdbd8SKent Overstreet 3171c6fdbd8SKent Overstreet i = eytzinger0_child(i, v > e->m); 3181c6fdbd8SKent Overstreet } 3191c6fdbd8SKent Overstreet } 3201c6fdbd8SKent Overstreet 3211c6fdbd8SKent Overstreet static void bch2_time_stats_update_one(struct bch2_time_stats *stats, 3221c6fdbd8SKent Overstreet u64 start, u64 end) 3231c6fdbd8SKent Overstreet { 3241c6fdbd8SKent Overstreet u64 duration, freq; 3251c6fdbd8SKent Overstreet 3261c6fdbd8SKent Overstreet duration = time_after64(end, start) 3271c6fdbd8SKent Overstreet ? end - start : 0; 3281c6fdbd8SKent Overstreet freq = time_after64(end, stats->last_event) 3291c6fdbd8SKent Overstreet ? end - stats->last_event : 0; 3301c6fdbd8SKent Overstreet 3311c6fdbd8SKent Overstreet stats->count++; 3321c6fdbd8SKent Overstreet 3331c6fdbd8SKent Overstreet stats->average_duration = stats->average_duration 3341c6fdbd8SKent Overstreet ? ewma_add(stats->average_duration, duration, 6) 3351c6fdbd8SKent Overstreet : duration; 3361c6fdbd8SKent Overstreet 3371c6fdbd8SKent Overstreet stats->average_frequency = stats->average_frequency 3381c6fdbd8SKent Overstreet ? ewma_add(stats->average_frequency, freq, 6) 3391c6fdbd8SKent Overstreet : freq; 3401c6fdbd8SKent Overstreet 3411c6fdbd8SKent Overstreet stats->max_duration = max(stats->max_duration, duration); 3421c6fdbd8SKent Overstreet 3431c6fdbd8SKent Overstreet stats->last_event = end; 3441c6fdbd8SKent Overstreet 3451c6fdbd8SKent Overstreet bch2_quantiles_update(&stats->quantiles, duration); 3461c6fdbd8SKent Overstreet } 3471c6fdbd8SKent Overstreet 3481c6fdbd8SKent Overstreet void __bch2_time_stats_update(struct bch2_time_stats *stats, u64 start, u64 end) 3491c6fdbd8SKent Overstreet { 3501c6fdbd8SKent Overstreet unsigned long flags; 3511c6fdbd8SKent Overstreet 3521c6fdbd8SKent Overstreet if (!stats->buffer) { 3531c6fdbd8SKent Overstreet spin_lock_irqsave(&stats->lock, flags); 3541c6fdbd8SKent Overstreet bch2_time_stats_update_one(stats, start, end); 3551c6fdbd8SKent Overstreet 3561c6fdbd8SKent Overstreet if (stats->average_frequency < 32 && 3571c6fdbd8SKent Overstreet stats->count > 1024) 3581c6fdbd8SKent Overstreet stats->buffer = 3591c6fdbd8SKent Overstreet alloc_percpu_gfp(struct bch2_time_stat_buffer, 3601c6fdbd8SKent Overstreet GFP_ATOMIC); 3611c6fdbd8SKent Overstreet spin_unlock_irqrestore(&stats->lock, flags); 3621c6fdbd8SKent Overstreet } else { 3631c6fdbd8SKent Overstreet struct bch2_time_stat_buffer_entry *i; 3641c6fdbd8SKent Overstreet struct bch2_time_stat_buffer *b; 3651c6fdbd8SKent Overstreet 3661c6fdbd8SKent Overstreet preempt_disable(); 3671c6fdbd8SKent Overstreet b = this_cpu_ptr(stats->buffer); 3681c6fdbd8SKent Overstreet 3691c6fdbd8SKent Overstreet BUG_ON(b->nr >= ARRAY_SIZE(b->entries)); 3701c6fdbd8SKent Overstreet b->entries[b->nr++] = (struct bch2_time_stat_buffer_entry) { 3711c6fdbd8SKent Overstreet .start = start, 3721c6fdbd8SKent Overstreet .end = end 3731c6fdbd8SKent Overstreet }; 3741c6fdbd8SKent Overstreet 3751c6fdbd8SKent Overstreet if (b->nr == ARRAY_SIZE(b->entries)) { 3761c6fdbd8SKent Overstreet spin_lock_irqsave(&stats->lock, flags); 3771c6fdbd8SKent Overstreet for (i = b->entries; 3781c6fdbd8SKent Overstreet i < b->entries + ARRAY_SIZE(b->entries); 3791c6fdbd8SKent Overstreet i++) 3801c6fdbd8SKent Overstreet bch2_time_stats_update_one(stats, i->start, i->end); 3811c6fdbd8SKent Overstreet spin_unlock_irqrestore(&stats->lock, flags); 3821c6fdbd8SKent Overstreet 3831c6fdbd8SKent Overstreet b->nr = 0; 3841c6fdbd8SKent Overstreet } 3851c6fdbd8SKent Overstreet 3861c6fdbd8SKent Overstreet preempt_enable(); 3871c6fdbd8SKent Overstreet } 3881c6fdbd8SKent Overstreet } 3891c6fdbd8SKent Overstreet #endif 3901c6fdbd8SKent Overstreet 3911c6fdbd8SKent Overstreet static const struct time_unit { 3921c6fdbd8SKent Overstreet const char *name; 3931c6fdbd8SKent Overstreet u32 nsecs; 3941c6fdbd8SKent Overstreet } time_units[] = { 3951c6fdbd8SKent Overstreet { "ns", 1 }, 3961c6fdbd8SKent Overstreet { "us", NSEC_PER_USEC }, 3971c6fdbd8SKent Overstreet { "ms", NSEC_PER_MSEC }, 3981c6fdbd8SKent Overstreet { "sec", NSEC_PER_SEC }, 3991c6fdbd8SKent Overstreet }; 4001c6fdbd8SKent Overstreet 4011c6fdbd8SKent Overstreet static const struct time_unit *pick_time_units(u64 ns) 4021c6fdbd8SKent Overstreet { 4031c6fdbd8SKent Overstreet const struct time_unit *u; 4041c6fdbd8SKent Overstreet 4051c6fdbd8SKent Overstreet for (u = time_units; 4061c6fdbd8SKent Overstreet u + 1 < time_units + ARRAY_SIZE(time_units) && 4071c6fdbd8SKent Overstreet ns >= u[1].nsecs << 1; 4081c6fdbd8SKent Overstreet u++) 4091c6fdbd8SKent Overstreet ; 4101c6fdbd8SKent Overstreet 4111c6fdbd8SKent Overstreet return u; 4121c6fdbd8SKent Overstreet } 4131c6fdbd8SKent Overstreet 414b17d3cecSKent Overstreet void bch2_pr_time_units(struct printbuf *out, u64 ns) 4151c6fdbd8SKent Overstreet { 4161c6fdbd8SKent Overstreet const struct time_unit *u = pick_time_units(ns); 4171c6fdbd8SKent Overstreet 418401ec4dbSKent Overstreet prt_printf(out, "%llu %s", div_u64(ns, u->nsecs), u->name); 4191c6fdbd8SKent Overstreet } 4201c6fdbd8SKent Overstreet 4217807e143SKent Overstreet void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) 4221c6fdbd8SKent Overstreet { 4231c6fdbd8SKent Overstreet const struct time_unit *u; 4241c6fdbd8SKent Overstreet u64 freq = READ_ONCE(stats->average_frequency); 4251c6fdbd8SKent Overstreet u64 q, last_q = 0; 4261c6fdbd8SKent Overstreet int i; 4271c6fdbd8SKent Overstreet 42825055c69SDaniel Hill prt_printf(out, "count:\t\t%llu", 4291c6fdbd8SKent Overstreet stats->count); 43025055c69SDaniel Hill prt_newline(out); 43125055c69SDaniel Hill prt_printf(out, "rate:\t\t%llu/sec", 4321c6fdbd8SKent Overstreet freq ? div64_u64(NSEC_PER_SEC, freq) : 0); 43325055c69SDaniel Hill prt_newline(out); 4341c6fdbd8SKent Overstreet 435401ec4dbSKent Overstreet prt_printf(out, "frequency:\t"); 436b17d3cecSKent Overstreet bch2_pr_time_units(out, freq); 4371c6fdbd8SKent Overstreet 43825055c69SDaniel Hill prt_newline(out); 43925055c69SDaniel Hill prt_printf(out, "avg duration:\t"); 440b17d3cecSKent Overstreet bch2_pr_time_units(out, stats->average_duration); 4411c6fdbd8SKent Overstreet 44225055c69SDaniel Hill prt_newline(out); 44325055c69SDaniel Hill prt_printf(out, "max duration:\t"); 444b17d3cecSKent Overstreet bch2_pr_time_units(out, stats->max_duration); 4451c6fdbd8SKent Overstreet 4461c6fdbd8SKent Overstreet i = eytzinger0_first(NR_QUANTILES); 4471c6fdbd8SKent Overstreet u = pick_time_units(stats->quantiles.entries[i].m); 4481c6fdbd8SKent Overstreet 44925055c69SDaniel Hill prt_newline(out); 45025055c69SDaniel Hill prt_printf(out, "quantiles (%s):\t", u->name); 4511c6fdbd8SKent Overstreet eytzinger0_for_each(i, NR_QUANTILES) { 4521c6fdbd8SKent Overstreet bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1; 4531c6fdbd8SKent Overstreet 4541c6fdbd8SKent Overstreet q = max(stats->quantiles.entries[i].m, last_q); 45525055c69SDaniel Hill prt_printf(out, "%llu ", 45625055c69SDaniel Hill div_u64(q, u->nsecs)); 45725055c69SDaniel Hill if (is_last) 45825055c69SDaniel Hill prt_newline(out); 4591c6fdbd8SKent Overstreet last_q = q; 4601c6fdbd8SKent Overstreet } 4611c6fdbd8SKent Overstreet } 4621c6fdbd8SKent Overstreet 4631c6fdbd8SKent Overstreet void bch2_time_stats_exit(struct bch2_time_stats *stats) 4641c6fdbd8SKent Overstreet { 4651c6fdbd8SKent Overstreet free_percpu(stats->buffer); 4661c6fdbd8SKent Overstreet } 4671c6fdbd8SKent Overstreet 4681c6fdbd8SKent Overstreet void bch2_time_stats_init(struct bch2_time_stats *stats) 4691c6fdbd8SKent Overstreet { 4701c6fdbd8SKent Overstreet memset(stats, 0, sizeof(*stats)); 4711c6fdbd8SKent Overstreet spin_lock_init(&stats->lock); 4721c6fdbd8SKent Overstreet } 4731c6fdbd8SKent Overstreet 4741c6fdbd8SKent Overstreet /* ratelimit: */ 4751c6fdbd8SKent Overstreet 4761c6fdbd8SKent Overstreet /** 4771c6fdbd8SKent Overstreet * bch2_ratelimit_delay() - return how long to delay until the next time to do 4781c6fdbd8SKent Overstreet * some work 4791c6fdbd8SKent Overstreet * 4801c6fdbd8SKent Overstreet * @d - the struct bch_ratelimit to update 4811c6fdbd8SKent Overstreet * 4821c6fdbd8SKent Overstreet * Returns the amount of time to delay by, in jiffies 4831c6fdbd8SKent Overstreet */ 4841c6fdbd8SKent Overstreet u64 bch2_ratelimit_delay(struct bch_ratelimit *d) 4851c6fdbd8SKent Overstreet { 4861c6fdbd8SKent Overstreet u64 now = local_clock(); 4871c6fdbd8SKent Overstreet 4881c6fdbd8SKent Overstreet return time_after64(d->next, now) 4891c6fdbd8SKent Overstreet ? nsecs_to_jiffies(d->next - now) 4901c6fdbd8SKent Overstreet : 0; 4911c6fdbd8SKent Overstreet } 4921c6fdbd8SKent Overstreet 4931c6fdbd8SKent Overstreet /** 4941c6fdbd8SKent Overstreet * bch2_ratelimit_increment() - increment @d by the amount of work done 4951c6fdbd8SKent Overstreet * 4961c6fdbd8SKent Overstreet * @d - the struct bch_ratelimit to update 4971c6fdbd8SKent Overstreet * @done - the amount of work done, in arbitrary units 4981c6fdbd8SKent Overstreet */ 4991c6fdbd8SKent Overstreet void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done) 5001c6fdbd8SKent Overstreet { 5011c6fdbd8SKent Overstreet u64 now = local_clock(); 5021c6fdbd8SKent Overstreet 5031c6fdbd8SKent Overstreet d->next += div_u64(done * NSEC_PER_SEC, d->rate); 5041c6fdbd8SKent Overstreet 5051c6fdbd8SKent Overstreet if (time_before64(now + NSEC_PER_SEC, d->next)) 5061c6fdbd8SKent Overstreet d->next = now + NSEC_PER_SEC; 5071c6fdbd8SKent Overstreet 5081c6fdbd8SKent Overstreet if (time_after64(now - NSEC_PER_SEC * 2, d->next)) 5091c6fdbd8SKent Overstreet d->next = now - NSEC_PER_SEC * 2; 5101c6fdbd8SKent Overstreet } 5111c6fdbd8SKent Overstreet 5121c6fdbd8SKent Overstreet /* pd controller: */ 5131c6fdbd8SKent Overstreet 5141c6fdbd8SKent Overstreet /* 5151c6fdbd8SKent Overstreet * Updates pd_controller. Attempts to scale inputed values to units per second. 5161c6fdbd8SKent Overstreet * @target: desired value 5171c6fdbd8SKent Overstreet * @actual: current value 5181c6fdbd8SKent Overstreet * 5191c6fdbd8SKent Overstreet * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing 5201c6fdbd8SKent Overstreet * it makes actual go down. 5211c6fdbd8SKent Overstreet */ 5221c6fdbd8SKent Overstreet void bch2_pd_controller_update(struct bch_pd_controller *pd, 5231c6fdbd8SKent Overstreet s64 target, s64 actual, int sign) 5241c6fdbd8SKent Overstreet { 5251c6fdbd8SKent Overstreet s64 proportional, derivative, change; 5261c6fdbd8SKent Overstreet 5271c6fdbd8SKent Overstreet unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ; 5281c6fdbd8SKent Overstreet 5291c6fdbd8SKent Overstreet if (seconds_since_update == 0) 5301c6fdbd8SKent Overstreet return; 5311c6fdbd8SKent Overstreet 5321c6fdbd8SKent Overstreet pd->last_update = jiffies; 5331c6fdbd8SKent Overstreet 5341c6fdbd8SKent Overstreet proportional = actual - target; 5351c6fdbd8SKent Overstreet proportional *= seconds_since_update; 5361c6fdbd8SKent Overstreet proportional = div_s64(proportional, pd->p_term_inverse); 5371c6fdbd8SKent Overstreet 5381c6fdbd8SKent Overstreet derivative = actual - pd->last_actual; 5391c6fdbd8SKent Overstreet derivative = div_s64(derivative, seconds_since_update); 5401c6fdbd8SKent Overstreet derivative = ewma_add(pd->smoothed_derivative, derivative, 5411c6fdbd8SKent Overstreet (pd->d_term / seconds_since_update) ?: 1); 5421c6fdbd8SKent Overstreet derivative = derivative * pd->d_term; 5431c6fdbd8SKent Overstreet derivative = div_s64(derivative, pd->p_term_inverse); 5441c6fdbd8SKent Overstreet 5451c6fdbd8SKent Overstreet change = proportional + derivative; 5461c6fdbd8SKent Overstreet 5471c6fdbd8SKent Overstreet /* Don't increase rate if not keeping up */ 5481c6fdbd8SKent Overstreet if (change > 0 && 5491c6fdbd8SKent Overstreet pd->backpressure && 5501c6fdbd8SKent Overstreet time_after64(local_clock(), 5511c6fdbd8SKent Overstreet pd->rate.next + NSEC_PER_MSEC)) 5521c6fdbd8SKent Overstreet change = 0; 5531c6fdbd8SKent Overstreet 5541c6fdbd8SKent Overstreet change *= (sign * -1); 5551c6fdbd8SKent Overstreet 5561c6fdbd8SKent Overstreet pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change, 5571c6fdbd8SKent Overstreet 1, UINT_MAX); 5581c6fdbd8SKent Overstreet 5591c6fdbd8SKent Overstreet pd->last_actual = actual; 5601c6fdbd8SKent Overstreet pd->last_derivative = derivative; 5611c6fdbd8SKent Overstreet pd->last_proportional = proportional; 5621c6fdbd8SKent Overstreet pd->last_change = change; 5631c6fdbd8SKent Overstreet pd->last_target = target; 5641c6fdbd8SKent Overstreet } 5651c6fdbd8SKent Overstreet 5661c6fdbd8SKent Overstreet void bch2_pd_controller_init(struct bch_pd_controller *pd) 5671c6fdbd8SKent Overstreet { 5681c6fdbd8SKent Overstreet pd->rate.rate = 1024; 5691c6fdbd8SKent Overstreet pd->last_update = jiffies; 5701c6fdbd8SKent Overstreet pd->p_term_inverse = 6000; 5711c6fdbd8SKent Overstreet pd->d_term = 30; 5721c6fdbd8SKent Overstreet pd->d_smooth = pd->d_term; 5731c6fdbd8SKent Overstreet pd->backpressure = 1; 5741c6fdbd8SKent Overstreet } 5751c6fdbd8SKent Overstreet 5762be7b16eSKent Overstreet void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd) 5771c6fdbd8SKent Overstreet { 578401ec4dbSKent Overstreet if (!out->nr_tabstops) 579401ec4dbSKent Overstreet printbuf_tabstop_push(out, 20); 5801c6fdbd8SKent Overstreet 581401ec4dbSKent Overstreet prt_printf(out, "rate:"); 582401ec4dbSKent Overstreet prt_tab(out); 583401ec4dbSKent Overstreet prt_human_readable_s64(out, pd->rate.rate); 584401ec4dbSKent Overstreet prt_newline(out); 5851c6fdbd8SKent Overstreet 586401ec4dbSKent Overstreet prt_printf(out, "target:"); 587401ec4dbSKent Overstreet prt_tab(out); 588401ec4dbSKent Overstreet prt_human_readable_u64(out, pd->last_target); 589401ec4dbSKent Overstreet prt_newline(out); 5901c6fdbd8SKent Overstreet 591401ec4dbSKent Overstreet prt_printf(out, "actual:"); 592401ec4dbSKent Overstreet prt_tab(out); 593401ec4dbSKent Overstreet prt_human_readable_u64(out, pd->last_actual); 594401ec4dbSKent Overstreet prt_newline(out); 5952be7b16eSKent Overstreet 596401ec4dbSKent Overstreet prt_printf(out, "proportional:"); 597401ec4dbSKent Overstreet prt_tab(out); 598401ec4dbSKent Overstreet prt_human_readable_s64(out, pd->last_proportional); 599401ec4dbSKent Overstreet prt_newline(out); 6002be7b16eSKent Overstreet 601401ec4dbSKent Overstreet prt_printf(out, "derivative:"); 602401ec4dbSKent Overstreet prt_tab(out); 603401ec4dbSKent Overstreet prt_human_readable_s64(out, pd->last_derivative); 604401ec4dbSKent Overstreet prt_newline(out); 6052be7b16eSKent Overstreet 606401ec4dbSKent Overstreet prt_printf(out, "change:"); 607401ec4dbSKent Overstreet prt_tab(out); 608401ec4dbSKent Overstreet prt_human_readable_s64(out, pd->last_change); 609401ec4dbSKent Overstreet prt_newline(out); 6102be7b16eSKent Overstreet 611401ec4dbSKent Overstreet prt_printf(out, "next io:"); 612401ec4dbSKent Overstreet prt_tab(out); 613401ec4dbSKent Overstreet prt_printf(out, "%llims", div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC)); 614401ec4dbSKent Overstreet prt_newline(out); 6151c6fdbd8SKent Overstreet } 6161c6fdbd8SKent Overstreet 6171c6fdbd8SKent Overstreet /* misc: */ 6181c6fdbd8SKent Overstreet 619885678f6SKent Overstreet void bch2_bio_map(struct bio *bio, void *base, size_t size) 6201c6fdbd8SKent Overstreet { 621885678f6SKent Overstreet while (size) { 622885678f6SKent Overstreet struct page *page = is_vmalloc_addr(base) 6231c6fdbd8SKent Overstreet ? vmalloc_to_page(base) 6241c6fdbd8SKent Overstreet : virt_to_page(base); 625885678f6SKent Overstreet unsigned offset = offset_in_page(base); 626885678f6SKent Overstreet unsigned len = min_t(size_t, PAGE_SIZE - offset, size); 6271c6fdbd8SKent Overstreet 628885678f6SKent Overstreet BUG_ON(!bio_add_page(bio, page, len, offset)); 629885678f6SKent Overstreet size -= len; 630885678f6SKent Overstreet base += len; 6311c6fdbd8SKent Overstreet } 6321c6fdbd8SKent Overstreet } 6331c6fdbd8SKent Overstreet 6341c6fdbd8SKent Overstreet int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask) 6351c6fdbd8SKent Overstreet { 6361c6fdbd8SKent Overstreet while (size) { 6371c6fdbd8SKent Overstreet struct page *page = alloc_pages(gfp_mask, 0); 6381c6fdbd8SKent Overstreet unsigned len = min_t(size_t, PAGE_SIZE, size); 6391c6fdbd8SKent Overstreet 6401c6fdbd8SKent Overstreet if (!page) 6411c6fdbd8SKent Overstreet return -ENOMEM; 6421c6fdbd8SKent Overstreet 6431c6fdbd8SKent Overstreet if (unlikely(!bio_add_page(bio, page, len, 0))) { 6441c6fdbd8SKent Overstreet __free_page(page); 6451c6fdbd8SKent Overstreet break; 6461c6fdbd8SKent Overstreet } 6471c6fdbd8SKent Overstreet 6481c6fdbd8SKent Overstreet size -= len; 6491c6fdbd8SKent Overstreet } 6501c6fdbd8SKent Overstreet 6511c6fdbd8SKent Overstreet return 0; 6521c6fdbd8SKent Overstreet } 6531c6fdbd8SKent Overstreet 6541c6fdbd8SKent Overstreet size_t bch2_rand_range(size_t max) 6551c6fdbd8SKent Overstreet { 6561c6fdbd8SKent Overstreet size_t rand; 6571c6fdbd8SKent Overstreet 6581c6fdbd8SKent Overstreet if (!max) 6591c6fdbd8SKent Overstreet return 0; 6601c6fdbd8SKent Overstreet 6611c6fdbd8SKent Overstreet do { 6621c6fdbd8SKent Overstreet rand = get_random_long(); 6631c6fdbd8SKent Overstreet rand &= roundup_pow_of_two(max) - 1; 6641c6fdbd8SKent Overstreet } while (rand >= max); 6651c6fdbd8SKent Overstreet 6661c6fdbd8SKent Overstreet return rand; 6671c6fdbd8SKent Overstreet } 6681c6fdbd8SKent Overstreet 66903c8c747SKent Overstreet void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) 6701c6fdbd8SKent Overstreet { 6711c6fdbd8SKent Overstreet struct bio_vec bv; 6721c6fdbd8SKent Overstreet struct bvec_iter iter; 6731c6fdbd8SKent Overstreet 6741c6fdbd8SKent Overstreet __bio_for_each_segment(bv, dst, iter, dst_iter) { 6751c6fdbd8SKent Overstreet void *dstp = kmap_atomic(bv.bv_page); 6761c6fdbd8SKent Overstreet memcpy(dstp + bv.bv_offset, src, bv.bv_len); 6771c6fdbd8SKent Overstreet kunmap_atomic(dstp); 6781c6fdbd8SKent Overstreet 6791c6fdbd8SKent Overstreet src += bv.bv_len; 6801c6fdbd8SKent Overstreet } 6811c6fdbd8SKent Overstreet } 6821c6fdbd8SKent Overstreet 6831c6fdbd8SKent Overstreet void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) 6841c6fdbd8SKent Overstreet { 6851c6fdbd8SKent Overstreet struct bio_vec bv; 6861c6fdbd8SKent Overstreet struct bvec_iter iter; 6871c6fdbd8SKent Overstreet 6881c6fdbd8SKent Overstreet __bio_for_each_segment(bv, src, iter, src_iter) { 6891c6fdbd8SKent Overstreet void *srcp = kmap_atomic(bv.bv_page); 6901c6fdbd8SKent Overstreet memcpy(dst, srcp + bv.bv_offset, bv.bv_len); 6911c6fdbd8SKent Overstreet kunmap_atomic(srcp); 6921c6fdbd8SKent Overstreet 6931c6fdbd8SKent Overstreet dst += bv.bv_len; 6941c6fdbd8SKent Overstreet } 6951c6fdbd8SKent Overstreet } 6961c6fdbd8SKent Overstreet 6971c6fdbd8SKent Overstreet #include "eytzinger.h" 6981c6fdbd8SKent Overstreet 6991c6fdbd8SKent Overstreet static int alignment_ok(const void *base, size_t align) 7001c6fdbd8SKent Overstreet { 7011c6fdbd8SKent Overstreet return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) || 7021c6fdbd8SKent Overstreet ((unsigned long)base & (align - 1)) == 0; 7031c6fdbd8SKent Overstreet } 7041c6fdbd8SKent Overstreet 7051c6fdbd8SKent Overstreet static void u32_swap(void *a, void *b, size_t size) 7061c6fdbd8SKent Overstreet { 7071c6fdbd8SKent Overstreet u32 t = *(u32 *)a; 7081c6fdbd8SKent Overstreet *(u32 *)a = *(u32 *)b; 7091c6fdbd8SKent Overstreet *(u32 *)b = t; 7101c6fdbd8SKent Overstreet } 7111c6fdbd8SKent Overstreet 7121c6fdbd8SKent Overstreet static void u64_swap(void *a, void *b, size_t size) 7131c6fdbd8SKent Overstreet { 7141c6fdbd8SKent Overstreet u64 t = *(u64 *)a; 7151c6fdbd8SKent Overstreet *(u64 *)a = *(u64 *)b; 7161c6fdbd8SKent Overstreet *(u64 *)b = t; 7171c6fdbd8SKent Overstreet } 7181c6fdbd8SKent Overstreet 7191c6fdbd8SKent Overstreet static void generic_swap(void *a, void *b, size_t size) 7201c6fdbd8SKent Overstreet { 7211c6fdbd8SKent Overstreet char t; 7221c6fdbd8SKent Overstreet 7231c6fdbd8SKent Overstreet do { 7241c6fdbd8SKent Overstreet t = *(char *)a; 7251c6fdbd8SKent Overstreet *(char *)a++ = *(char *)b; 7261c6fdbd8SKent Overstreet *(char *)b++ = t; 7271c6fdbd8SKent Overstreet } while (--size > 0); 7281c6fdbd8SKent Overstreet } 7291c6fdbd8SKent Overstreet 7301c6fdbd8SKent Overstreet static inline int do_cmp(void *base, size_t n, size_t size, 7311c6fdbd8SKent Overstreet int (*cmp_func)(const void *, const void *, size_t), 7321c6fdbd8SKent Overstreet size_t l, size_t r) 7331c6fdbd8SKent Overstreet { 7341c6fdbd8SKent Overstreet return cmp_func(base + inorder_to_eytzinger0(l, n) * size, 7351c6fdbd8SKent Overstreet base + inorder_to_eytzinger0(r, n) * size, 7361c6fdbd8SKent Overstreet size); 7371c6fdbd8SKent Overstreet } 7381c6fdbd8SKent Overstreet 7391c6fdbd8SKent Overstreet static inline void do_swap(void *base, size_t n, size_t size, 7401c6fdbd8SKent Overstreet void (*swap_func)(void *, void *, size_t), 7411c6fdbd8SKent Overstreet size_t l, size_t r) 7421c6fdbd8SKent Overstreet { 7431c6fdbd8SKent Overstreet swap_func(base + inorder_to_eytzinger0(l, n) * size, 7441c6fdbd8SKent Overstreet base + inorder_to_eytzinger0(r, n) * size, 7451c6fdbd8SKent Overstreet size); 7461c6fdbd8SKent Overstreet } 7471c6fdbd8SKent Overstreet 7481c6fdbd8SKent Overstreet void eytzinger0_sort(void *base, size_t n, size_t size, 7491c6fdbd8SKent Overstreet int (*cmp_func)(const void *, const void *, size_t), 7501c6fdbd8SKent Overstreet void (*swap_func)(void *, void *, size_t)) 7511c6fdbd8SKent Overstreet { 7521c6fdbd8SKent Overstreet int i, c, r; 7531c6fdbd8SKent Overstreet 7541c6fdbd8SKent Overstreet if (!swap_func) { 7551c6fdbd8SKent Overstreet if (size == 4 && alignment_ok(base, 4)) 7561c6fdbd8SKent Overstreet swap_func = u32_swap; 7571c6fdbd8SKent Overstreet else if (size == 8 && alignment_ok(base, 8)) 7581c6fdbd8SKent Overstreet swap_func = u64_swap; 7591c6fdbd8SKent Overstreet else 7601c6fdbd8SKent Overstreet swap_func = generic_swap; 7611c6fdbd8SKent Overstreet } 7621c6fdbd8SKent Overstreet 7631c6fdbd8SKent Overstreet /* heapify */ 7641c6fdbd8SKent Overstreet for (i = n / 2 - 1; i >= 0; --i) { 7651c6fdbd8SKent Overstreet for (r = i; r * 2 + 1 < n; r = c) { 7661c6fdbd8SKent Overstreet c = r * 2 + 1; 7671c6fdbd8SKent Overstreet 7681c6fdbd8SKent Overstreet if (c + 1 < n && 7691c6fdbd8SKent Overstreet do_cmp(base, n, size, cmp_func, c, c + 1) < 0) 7701c6fdbd8SKent Overstreet c++; 7711c6fdbd8SKent Overstreet 7721c6fdbd8SKent Overstreet if (do_cmp(base, n, size, cmp_func, r, c) >= 0) 7731c6fdbd8SKent Overstreet break; 7741c6fdbd8SKent Overstreet 7751c6fdbd8SKent Overstreet do_swap(base, n, size, swap_func, r, c); 7761c6fdbd8SKent Overstreet } 7771c6fdbd8SKent Overstreet } 7781c6fdbd8SKent Overstreet 7791c6fdbd8SKent Overstreet /* sort */ 7801c6fdbd8SKent Overstreet for (i = n - 1; i > 0; --i) { 7811c6fdbd8SKent Overstreet do_swap(base, n, size, swap_func, 0, i); 7821c6fdbd8SKent Overstreet 7831c6fdbd8SKent Overstreet for (r = 0; r * 2 + 1 < i; r = c) { 7841c6fdbd8SKent Overstreet c = r * 2 + 1; 7851c6fdbd8SKent Overstreet 7861c6fdbd8SKent Overstreet if (c + 1 < i && 7871c6fdbd8SKent Overstreet do_cmp(base, n, size, cmp_func, c, c + 1) < 0) 7881c6fdbd8SKent Overstreet c++; 7891c6fdbd8SKent Overstreet 7901c6fdbd8SKent Overstreet if (do_cmp(base, n, size, cmp_func, r, c) >= 0) 7911c6fdbd8SKent Overstreet break; 7921c6fdbd8SKent Overstreet 7931c6fdbd8SKent Overstreet do_swap(base, n, size, swap_func, r, c); 7941c6fdbd8SKent Overstreet } 7951c6fdbd8SKent Overstreet } 7961c6fdbd8SKent Overstreet } 7971c6fdbd8SKent Overstreet 7981c6fdbd8SKent Overstreet void sort_cmp_size(void *base, size_t num, size_t size, 7991c6fdbd8SKent Overstreet int (*cmp_func)(const void *, const void *, size_t), 8001c6fdbd8SKent Overstreet void (*swap_func)(void *, void *, size_t size)) 8011c6fdbd8SKent Overstreet { 8021c6fdbd8SKent Overstreet /* pre-scale counters for performance */ 8031c6fdbd8SKent Overstreet int i = (num/2 - 1) * size, n = num * size, c, r; 8041c6fdbd8SKent Overstreet 8051c6fdbd8SKent Overstreet if (!swap_func) { 8061c6fdbd8SKent Overstreet if (size == 4 && alignment_ok(base, 4)) 8071c6fdbd8SKent Overstreet swap_func = u32_swap; 8081c6fdbd8SKent Overstreet else if (size == 8 && alignment_ok(base, 8)) 8091c6fdbd8SKent Overstreet swap_func = u64_swap; 8101c6fdbd8SKent Overstreet else 8111c6fdbd8SKent Overstreet swap_func = generic_swap; 8121c6fdbd8SKent Overstreet } 8131c6fdbd8SKent Overstreet 8141c6fdbd8SKent Overstreet /* heapify */ 8151c6fdbd8SKent Overstreet for ( ; i >= 0; i -= size) { 8161c6fdbd8SKent Overstreet for (r = i; r * 2 + size < n; r = c) { 8171c6fdbd8SKent Overstreet c = r * 2 + size; 8181c6fdbd8SKent Overstreet if (c < n - size && 8191c6fdbd8SKent Overstreet cmp_func(base + c, base + c + size, size) < 0) 8201c6fdbd8SKent Overstreet c += size; 8211c6fdbd8SKent Overstreet if (cmp_func(base + r, base + c, size) >= 0) 8221c6fdbd8SKent Overstreet break; 8231c6fdbd8SKent Overstreet swap_func(base + r, base + c, size); 8241c6fdbd8SKent Overstreet } 8251c6fdbd8SKent Overstreet } 8261c6fdbd8SKent Overstreet 8271c6fdbd8SKent Overstreet /* sort */ 8281c6fdbd8SKent Overstreet for (i = n - size; i > 0; i -= size) { 8291c6fdbd8SKent Overstreet swap_func(base, base + i, size); 8301c6fdbd8SKent Overstreet for (r = 0; r * 2 + size < i; r = c) { 8311c6fdbd8SKent Overstreet c = r * 2 + size; 8321c6fdbd8SKent Overstreet if (c < i - size && 8331c6fdbd8SKent Overstreet cmp_func(base + c, base + c + size, size) < 0) 8341c6fdbd8SKent Overstreet c += size; 8351c6fdbd8SKent Overstreet if (cmp_func(base + r, base + c, size) >= 0) 8361c6fdbd8SKent Overstreet break; 8371c6fdbd8SKent Overstreet swap_func(base + r, base + c, size); 8381c6fdbd8SKent Overstreet } 8391c6fdbd8SKent Overstreet } 8401c6fdbd8SKent Overstreet } 8411c6fdbd8SKent Overstreet 8421c6fdbd8SKent Overstreet static void mempool_free_vp(void *element, void *pool_data) 8431c6fdbd8SKent Overstreet { 8441c6fdbd8SKent Overstreet size_t size = (size_t) pool_data; 8451c6fdbd8SKent Overstreet 8461c6fdbd8SKent Overstreet vpfree(element, size); 8471c6fdbd8SKent Overstreet } 8481c6fdbd8SKent Overstreet 8491c6fdbd8SKent Overstreet static void *mempool_alloc_vp(gfp_t gfp_mask, void *pool_data) 8501c6fdbd8SKent Overstreet { 8511c6fdbd8SKent Overstreet size_t size = (size_t) pool_data; 8521c6fdbd8SKent Overstreet 8531c6fdbd8SKent Overstreet return vpmalloc(size, gfp_mask); 8541c6fdbd8SKent Overstreet } 8551c6fdbd8SKent Overstreet 8561c6fdbd8SKent Overstreet int mempool_init_kvpmalloc_pool(mempool_t *pool, int min_nr, size_t size) 8571c6fdbd8SKent Overstreet { 8581c6fdbd8SKent Overstreet return size < PAGE_SIZE 8591c6fdbd8SKent Overstreet ? mempool_init_kmalloc_pool(pool, min_nr, size) 8601c6fdbd8SKent Overstreet : mempool_init(pool, min_nr, mempool_alloc_vp, 8611c6fdbd8SKent Overstreet mempool_free_vp, (void *) size); 8621c6fdbd8SKent Overstreet } 8631c6fdbd8SKent Overstreet 8641c6fdbd8SKent Overstreet #if 0 8651c6fdbd8SKent Overstreet void eytzinger1_test(void) 8661c6fdbd8SKent Overstreet { 8671c6fdbd8SKent Overstreet unsigned inorder, eytz, size; 8681c6fdbd8SKent Overstreet 8691c6fdbd8SKent Overstreet pr_info("1 based eytzinger test:"); 8701c6fdbd8SKent Overstreet 8711c6fdbd8SKent Overstreet for (size = 2; 8721c6fdbd8SKent Overstreet size < 65536; 8731c6fdbd8SKent Overstreet size++) { 8741c6fdbd8SKent Overstreet unsigned extra = eytzinger1_extra(size); 8751c6fdbd8SKent Overstreet 8761c6fdbd8SKent Overstreet if (!(size % 4096)) 8771c6fdbd8SKent Overstreet pr_info("tree size %u", size); 8781c6fdbd8SKent Overstreet 8791c6fdbd8SKent Overstreet BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); 8801c6fdbd8SKent Overstreet BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); 8811c6fdbd8SKent Overstreet 8821c6fdbd8SKent Overstreet BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); 8831c6fdbd8SKent Overstreet BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); 8841c6fdbd8SKent Overstreet 8851c6fdbd8SKent Overstreet inorder = 1; 8861c6fdbd8SKent Overstreet eytzinger1_for_each(eytz, size) { 8871c6fdbd8SKent Overstreet BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); 8881c6fdbd8SKent Overstreet BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder); 8891c6fdbd8SKent Overstreet BUG_ON(eytz != eytzinger1_last(size) && 8901c6fdbd8SKent Overstreet eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz); 8911c6fdbd8SKent Overstreet 8921c6fdbd8SKent Overstreet inorder++; 8931c6fdbd8SKent Overstreet } 8941c6fdbd8SKent Overstreet } 8951c6fdbd8SKent Overstreet } 8961c6fdbd8SKent Overstreet 8971c6fdbd8SKent Overstreet void eytzinger0_test(void) 8981c6fdbd8SKent Overstreet { 8991c6fdbd8SKent Overstreet 9001c6fdbd8SKent Overstreet unsigned inorder, eytz, size; 9011c6fdbd8SKent Overstreet 9021c6fdbd8SKent Overstreet pr_info("0 based eytzinger test:"); 9031c6fdbd8SKent Overstreet 9041c6fdbd8SKent Overstreet for (size = 1; 9051c6fdbd8SKent Overstreet size < 65536; 9061c6fdbd8SKent Overstreet size++) { 9071c6fdbd8SKent Overstreet unsigned extra = eytzinger0_extra(size); 9081c6fdbd8SKent Overstreet 9091c6fdbd8SKent Overstreet if (!(size % 4096)) 9101c6fdbd8SKent Overstreet pr_info("tree size %u", size); 9111c6fdbd8SKent Overstreet 9121c6fdbd8SKent Overstreet BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); 9131c6fdbd8SKent Overstreet BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); 9141c6fdbd8SKent Overstreet 9151c6fdbd8SKent Overstreet BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); 9161c6fdbd8SKent Overstreet BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); 9171c6fdbd8SKent Overstreet 9181c6fdbd8SKent Overstreet inorder = 0; 9191c6fdbd8SKent Overstreet eytzinger0_for_each(eytz, size) { 9201c6fdbd8SKent Overstreet BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz); 9211c6fdbd8SKent Overstreet BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder); 9221c6fdbd8SKent Overstreet BUG_ON(eytz != eytzinger0_last(size) && 9231c6fdbd8SKent Overstreet eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz); 9241c6fdbd8SKent Overstreet 9251c6fdbd8SKent Overstreet inorder++; 9261c6fdbd8SKent Overstreet } 9271c6fdbd8SKent Overstreet } 9281c6fdbd8SKent Overstreet } 9291c6fdbd8SKent Overstreet 9301c6fdbd8SKent Overstreet static inline int cmp_u16(const void *_l, const void *_r, size_t size) 9311c6fdbd8SKent Overstreet { 9321c6fdbd8SKent Overstreet const u16 *l = _l, *r = _r; 9331c6fdbd8SKent Overstreet 9341c6fdbd8SKent Overstreet return (*l > *r) - (*r - *l); 9351c6fdbd8SKent Overstreet } 9361c6fdbd8SKent Overstreet 9371c6fdbd8SKent Overstreet static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) 9381c6fdbd8SKent Overstreet { 9391c6fdbd8SKent Overstreet int i, c1 = -1, c2 = -1; 9401c6fdbd8SKent Overstreet ssize_t r; 9411c6fdbd8SKent Overstreet 9421c6fdbd8SKent Overstreet r = eytzinger0_find_le(test_array, nr, 9431c6fdbd8SKent Overstreet sizeof(test_array[0]), 9441c6fdbd8SKent Overstreet cmp_u16, &search); 9451c6fdbd8SKent Overstreet if (r >= 0) 9461c6fdbd8SKent Overstreet c1 = test_array[r]; 9471c6fdbd8SKent Overstreet 9481c6fdbd8SKent Overstreet for (i = 0; i < nr; i++) 9491c6fdbd8SKent Overstreet if (test_array[i] <= search && test_array[i] > c2) 9501c6fdbd8SKent Overstreet c2 = test_array[i]; 9511c6fdbd8SKent Overstreet 9521c6fdbd8SKent Overstreet if (c1 != c2) { 9531c6fdbd8SKent Overstreet eytzinger0_for_each(i, nr) 9541c6fdbd8SKent Overstreet pr_info("[%3u] = %12u", i, test_array[i]); 9551c6fdbd8SKent Overstreet pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", 9561c6fdbd8SKent Overstreet i, r, c1, c2); 9571c6fdbd8SKent Overstreet } 9581c6fdbd8SKent Overstreet } 9591c6fdbd8SKent Overstreet 9601c6fdbd8SKent Overstreet void eytzinger0_find_test(void) 9611c6fdbd8SKent Overstreet { 9621c6fdbd8SKent Overstreet unsigned i, nr, allocated = 1 << 12; 9631c6fdbd8SKent Overstreet u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); 9641c6fdbd8SKent Overstreet 9651c6fdbd8SKent Overstreet for (nr = 1; nr < allocated; nr++) { 9661c6fdbd8SKent Overstreet pr_info("testing %u elems", nr); 9671c6fdbd8SKent Overstreet 9681c6fdbd8SKent Overstreet get_random_bytes(test_array, nr * sizeof(test_array[0])); 9691c6fdbd8SKent Overstreet eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); 9701c6fdbd8SKent Overstreet 9711c6fdbd8SKent Overstreet /* verify array is sorted correctly: */ 9721c6fdbd8SKent Overstreet eytzinger0_for_each(i, nr) 9731c6fdbd8SKent Overstreet BUG_ON(i != eytzinger0_last(nr) && 9741c6fdbd8SKent Overstreet test_array[i] > test_array[eytzinger0_next(i, nr)]); 9751c6fdbd8SKent Overstreet 9761c6fdbd8SKent Overstreet for (i = 0; i < U16_MAX; i += 1 << 12) 9771c6fdbd8SKent Overstreet eytzinger0_find_test_val(test_array, nr, i); 9781c6fdbd8SKent Overstreet 9791c6fdbd8SKent Overstreet for (i = 0; i < nr; i++) { 9801c6fdbd8SKent Overstreet eytzinger0_find_test_val(test_array, nr, test_array[i] - 1); 9811c6fdbd8SKent Overstreet eytzinger0_find_test_val(test_array, nr, test_array[i]); 9821c6fdbd8SKent Overstreet eytzinger0_find_test_val(test_array, nr, test_array[i] + 1); 9831c6fdbd8SKent Overstreet } 9841c6fdbd8SKent Overstreet } 9851c6fdbd8SKent Overstreet 9861c6fdbd8SKent Overstreet kfree(test_array); 9871c6fdbd8SKent Overstreet } 9881c6fdbd8SKent Overstreet #endif 9897ef2a73aSKent Overstreet 9907ef2a73aSKent Overstreet /* 9917ef2a73aSKent Overstreet * Accumulate percpu counters onto one cpu's copy - only valid when access 9927ef2a73aSKent Overstreet * against any percpu counter is guarded against 9937ef2a73aSKent Overstreet */ 9947ef2a73aSKent Overstreet u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr) 9957ef2a73aSKent Overstreet { 996107fe5afSKent Overstreet u64 *ret; 9977ef2a73aSKent Overstreet int cpu; 9987ef2a73aSKent Overstreet 999107fe5afSKent Overstreet /* access to pcpu vars has to be blocked by other locking */ 1000107fe5afSKent Overstreet preempt_disable(); 1001107fe5afSKent Overstreet ret = this_cpu_ptr(p); 1002107fe5afSKent Overstreet preempt_enable(); 1003107fe5afSKent Overstreet 10047ef2a73aSKent Overstreet for_each_possible_cpu(cpu) { 10057ef2a73aSKent Overstreet u64 *i = per_cpu_ptr(p, cpu); 10067ef2a73aSKent Overstreet 10077ef2a73aSKent Overstreet if (i != ret) { 10087ef2a73aSKent Overstreet acc_u64s(ret, i, nr); 10097ef2a73aSKent Overstreet memset(i, 0, nr * sizeof(u64)); 10107ef2a73aSKent Overstreet } 10117ef2a73aSKent Overstreet } 10127ef2a73aSKent Overstreet 10137ef2a73aSKent Overstreet return ret; 10147ef2a73aSKent Overstreet } 1015