2 * random utiility code, for bcache but in theory not specific to bcache
4 * Copyright 2010, 2011 Kent Overstreet <kent.overstreet@gmail.com>
5 * Copyright 2012 Google, Inc.
9 #include <linux/blkdev.h>
10 #include <linux/ctype.h>
11 #include <linux/debugfs.h>
12 #include <linux/freezer.h>
13 #include <linux/kthread.h>
14 #include <linux/log2.h>
15 #include <linux/math64.h>
16 #include <linux/random.h>
17 #include <linux/seq_file.h>
18 #include <linux/string.h>
19 #include <linux/types.h>
23 #define simple_strtoint(c, end, base) simple_strtol(c, end, base)
24 #define simple_strtouint(c, end, base) simple_strtoul(c, end, base)
26 #define STRTO_H(name, type) \
27 int bch2_ ## name ## _h(const char *cp, type *res) \
31 type i = simple_ ## name(cp, &e, 10); \
33 switch (tolower(*e)) { \
63 if ((type) ~0 > 0 && \
64 (type) ~0 / 1024 <= i) \
66 if ((i > 0 && ANYSINT_MAX(type) / 1024 < i) || \
67 (i < 0 && -ANYSINT_MAX(type) / 1024 > i)) \
76 STRTO_H(strtoint, int)
77 STRTO_H(strtouint, unsigned int)
78 STRTO_H(strtoll, long long)
79 STRTO_H(strtoull, unsigned long long)
81 ssize_t bch2_hprint(char *buf, s64 v)
83 static const char units[] = "?kMGTPEZY";
87 for (u = 0; v >= 1024 || v <= -1024; u++) {
93 return sprintf(buf, "%lli", v);
96 * 103 is magic: t is in the range [-1023, 1023] and we want
97 * to turn it into [-9, 9]
99 if (v < 100 && v > -100)
100 snprintf(dec, sizeof(dec), ".%i", t / 103);
102 return sprintf(buf, "%lli%s%c", v, dec, units[u]);
105 ssize_t bch2_snprint_string_list(char *buf, size_t size, const char * const list[],
111 for (i = 0; list[i]; i++)
112 out += snprintf(out, buf + size - out,
113 i == selected ? "[%s] " : "%s ", list[i]);
119 ssize_t bch2_read_string_list(const char *buf, const char * const list[])
122 char *s, *d = kstrndup(buf, PAGE_SIZE - 1, GFP_KERNEL);
128 for (i = 0; list[i]; i++)
129 if (!strcmp(list[i], s))
140 bool bch2_is_zero(const void *_p, size_t n)
145 for (i = 0; i < n; i++)
151 void bch2_time_stats_clear(struct time_stats *stats)
153 spin_lock(&stats->lock);
156 stats->last_duration = 0;
157 stats->max_duration = 0;
158 stats->average_duration = 0;
159 stats->average_frequency = 0;
162 spin_unlock(&stats->lock);
165 void __bch2_time_stats_update(struct time_stats *stats, u64 start_time)
167 u64 now, duration, last;
172 duration = time_after64(now, start_time)
173 ? now - start_time : 0;
174 last = time_after64(now, stats->last)
175 ? now - stats->last : 0;
177 stats->last_duration = duration;
178 stats->max_duration = max(stats->max_duration, duration);
181 stats->average_duration = ewma_add(stats->average_duration,
184 if (stats->average_frequency)
185 stats->average_frequency =
186 ewma_add(stats->average_frequency,
189 stats->average_frequency = last << 8;
191 stats->average_duration = duration << 8;
194 stats->last = now ?: 1;
197 void bch2_time_stats_update(struct time_stats *stats, u64 start_time)
199 spin_lock(&stats->lock);
200 __bch2_time_stats_update(stats, start_time);
201 spin_unlock(&stats->lock);
205 * bch2_ratelimit_delay() - return how long to delay until the next time to do
208 * @d - the struct bch_ratelimit to update
210 * Returns the amount of time to delay by, in jiffies
212 u64 bch2_ratelimit_delay(struct bch_ratelimit *d)
214 u64 now = local_clock();
216 return time_after64(d->next, now)
217 ? nsecs_to_jiffies(d->next - now)
222 * bch2_ratelimit_increment() - increment @d by the amount of work done
224 * @d - the struct bch_ratelimit to update
225 * @done - the amount of work done, in arbitrary units
227 void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done)
229 u64 now = local_clock();
231 d->next += div_u64(done * NSEC_PER_SEC, d->rate);
233 if (time_before64(now + NSEC_PER_SEC, d->next))
234 d->next = now + NSEC_PER_SEC;
236 if (time_after64(now - NSEC_PER_SEC * 2, d->next))
237 d->next = now - NSEC_PER_SEC * 2;
240 int bch2_ratelimit_wait_freezable_stoppable(struct bch_ratelimit *d)
243 u64 delay = bch2_ratelimit_delay(d);
246 set_current_state(TASK_INTERRUPTIBLE);
248 if (kthread_should_stop())
254 schedule_timeout(delay);
260 * Updates pd_controller. Attempts to scale inputed values to units per second.
261 * @target: desired value
262 * @actual: current value
264 * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing
265 * it makes actual go down.
267 void bch2_pd_controller_update(struct bch_pd_controller *pd,
268 s64 target, s64 actual, int sign)
270 s64 proportional, derivative, change;
272 unsigned long seconds_since_update = (jiffies - pd->last_update) / HZ;
274 if (seconds_since_update == 0)
277 pd->last_update = jiffies;
279 proportional = actual - target;
280 proportional *= seconds_since_update;
281 proportional = div_s64(proportional, pd->p_term_inverse);
283 derivative = actual - pd->last_actual;
284 derivative = div_s64(derivative, seconds_since_update);
285 derivative = ewma_add(pd->smoothed_derivative, derivative,
286 (pd->d_term / seconds_since_update) ?: 1);
287 derivative = derivative * pd->d_term;
288 derivative = div_s64(derivative, pd->p_term_inverse);
290 change = proportional + derivative;
292 /* Don't increase rate if not keeping up */
295 time_after64(local_clock(),
296 pd->rate.next + NSEC_PER_MSEC))
299 change *= (sign * -1);
301 pd->rate.rate = clamp_t(s64, (s64) pd->rate.rate + change,
304 pd->last_actual = actual;
305 pd->last_derivative = derivative;
306 pd->last_proportional = proportional;
307 pd->last_change = change;
308 pd->last_target = target;
311 void bch2_pd_controller_init(struct bch_pd_controller *pd)
313 pd->rate.rate = 1024;
314 pd->last_update = jiffies;
315 pd->p_term_inverse = 6000;
317 pd->d_smooth = pd->d_term;
318 pd->backpressure = 1;
321 size_t bch2_pd_controller_print_debug(struct bch_pd_controller *pd, char *buf)
323 /* 2^64 - 1 is 20 digits, plus null byte */
327 char proportional[21];
332 bch2_hprint(rate, pd->rate.rate);
333 bch2_hprint(actual, pd->last_actual);
334 bch2_hprint(target, pd->last_target);
335 bch2_hprint(proportional, pd->last_proportional);
336 bch2_hprint(derivative, pd->last_derivative);
337 bch2_hprint(change, pd->last_change);
339 next_io = div64_s64(pd->rate.next - local_clock(), NSEC_PER_MSEC);
345 "proportional:\t%s\n"
347 "change:\t\t%s/sec\n"
348 "next io:\t%llims\n",
349 rate, target, actual, proportional,
350 derivative, change, next_io);
353 void bch2_bio_map(struct bio *bio, void *base)
355 size_t size = bio->bi_iter.bi_size;
356 struct bio_vec *bv = bio->bi_io_vec;
358 BUG_ON(!bio->bi_iter.bi_size);
359 BUG_ON(bio->bi_vcnt);
361 bv->bv_offset = base ? offset_in_page(base) : 0;
364 for (; size; bio->bi_vcnt++, bv++) {
366 start: bv->bv_len = min_t(size_t, PAGE_SIZE - bv->bv_offset,
368 BUG_ON(bio->bi_vcnt >= bio->bi_max_vecs);
370 bv->bv_page = is_vmalloc_addr(base)
371 ? vmalloc_to_page(base)
372 : virt_to_page(base);
381 size_t bch2_rand_range(size_t max)
386 get_random_bytes(&rand, sizeof(rand));
387 rand &= roundup_pow_of_two(max) - 1;
388 } while (rand >= max);
393 void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, void *src)
396 struct bvec_iter iter;
398 __bio_for_each_segment(bv, dst, iter, dst_iter) {
399 void *dstp = kmap_atomic(bv.bv_page);
400 memcpy(dstp + bv.bv_offset, src, bv.bv_len);
407 void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
410 struct bvec_iter iter;
412 __bio_for_each_segment(bv, src, iter, src_iter) {
413 void *srcp = kmap_atomic(bv.bv_page);
414 memcpy(dst, srcp + bv.bv_offset, bv.bv_len);