xref: /linux/fs/bcachefs/util.c (revision 1148a97f1fb9b80ef5355021f0c2dfc7b8f003a2)
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