// SPDX-License-Identifier: GPL-2.0 /* * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet <[email protected]> * Copyright 2012 Google, Inc. */ #include <linux/bio.h> #include <linux/blkdev.h> #include <linux/console.h> #include <linux/ctype.h> #include <linux/debugfs.h> #include <linux/freezer.h> #include <linux/kthread.h> #include <linux/log2.h> #include <linux/math64.h> #include <linux/percpu.h> #include <linux/preempt.h> #include <linux/random.h> #include <linux/seq_file.h> #include <linux/string.h> #include <linux/types.h> #include <linux/sched/clock.h> #include "eytzinger.h" #include "mean_and_variance.h" #include "util.h" static const char si_units[] = …; /* string_get_size units: */ static const char *const units_2[] = …; static const char *const units_10[] = …; static int parse_u64(const char *cp, u64 *res) { … } static int bch2_pow(u64 n, u64 p, u64 *res) { … } static int parse_unit_suffix(const char *cp, u64 *res) { … } #define parse_or_ret(cp, _f) … static int __bch2_strtou64_h(const char *cp, u64 *res) { … } static int __bch2_strtoh(const char *cp, u64 *res, u64 t_max, bool t_signed) { … } #define STRTO_H(name, type) … STRTO_H(…) STRTO_H(…) STRTO_H(…) STRTO_H(…) STRTO_H(strtou64, u64) u64 bch2_read_flag_list(char *opt, const char * const list[]) { … } bool bch2_is_zero(const void *_p, size_t n) { … } void bch2_prt_u64_base2_nbits(struct printbuf *out, u64 v, unsigned nr_bits) { … } void bch2_prt_u64_base2(struct printbuf *out, u64 v) { … } static void __bch2_print_string_as_lines(const char *prefix, const char *lines, bool nonblocking) { … } void bch2_print_string_as_lines(const char *prefix, const char *lines) { … } void bch2_print_string_as_lines_nonblocking(const char *prefix, const char *lines) { … } int bch2_save_backtrace(bch_stacktrace *stack, struct task_struct *task, unsigned skipnr, gfp_t gfp) { … } void bch2_prt_backtrace(struct printbuf *out, bch_stacktrace *stack) { … } int bch2_prt_task_backtrace(struct printbuf *out, struct task_struct *task, unsigned skipnr, gfp_t gfp) { … } #ifndef __KERNEL__ #include <time.h> void bch2_prt_datetime(struct printbuf *out, time64_t sec) { time_t t = sec; char buf[64]; ctime_r(&t, buf); strim(buf); prt_str(out, buf); } #else void bch2_prt_datetime(struct printbuf *out, time64_t sec) { … } #endif void bch2_pr_time_units(struct printbuf *out, u64 ns) { … } static void bch2_pr_time_units_aligned(struct printbuf *out, u64 ns) { … } static inline void pr_name_and_units(struct printbuf *out, const char *name, u64 ns) { … } #define TABSTOP_SIZE … void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats) { … } /* ratelimit: */ /** * bch2_ratelimit_delay() - return how long to delay until the next time to do * some work * @d: the struct bch_ratelimit to update * Returns: the amount of time to delay by, in jiffies */ u64 bch2_ratelimit_delay(struct bch_ratelimit *d) { … } /** * bch2_ratelimit_increment() - increment @d by the amount of work done * @d: the struct bch_ratelimit to update * @done: the amount of work done, in arbitrary units */ void bch2_ratelimit_increment(struct bch_ratelimit *d, u64 done) { … } /* pd controller: */ /* * Updates pd_controller. Attempts to scale inputed values to units per second. * @target: desired value * @actual: current value * * @sign: 1 or -1; 1 if increasing the rate makes actual go up, -1 if increasing * it makes actual go down. */ void bch2_pd_controller_update(struct bch_pd_controller *pd, s64 target, s64 actual, int sign) { … } void bch2_pd_controller_init(struct bch_pd_controller *pd) { … } void bch2_pd_controller_debug_to_text(struct printbuf *out, struct bch_pd_controller *pd) { … } /* misc: */ void bch2_bio_map(struct bio *bio, void *base, size_t size) { … } int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask) { … } size_t bch2_rand_range(size_t max) { … } void memcpy_to_bio(struct bio *dst, struct bvec_iter dst_iter, const void *src) { … } void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) { … } #if 0 void eytzinger1_test(void) { unsigned inorder, eytz, size; pr_info("1 based eytzinger test:"); for (size = 2; size < 65536; size++) { unsigned extra = eytzinger1_extra(size); if (!(size % 4096)) pr_info("tree size %u", size); BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); inorder = 1; eytzinger1_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); BUG_ON(__eytzinger1_to_inorder(eytz, size, extra) != inorder); BUG_ON(eytz != eytzinger1_last(size) && eytzinger1_prev(eytzinger1_next(eytz, size), size) != eytz); inorder++; } } } void eytzinger0_test(void) { unsigned inorder, eytz, size; pr_info("0 based eytzinger test:"); for (size = 1; size < 65536; size++) { unsigned extra = eytzinger0_extra(size); if (!(size % 4096)) pr_info("tree size %u", size); BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); inorder = 0; eytzinger0_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz); BUG_ON(__eytzinger0_to_inorder(eytz, size, extra) != inorder); BUG_ON(eytz != eytzinger0_last(size) && eytzinger0_prev(eytzinger0_next(eytz, size), size) != eytz); inorder++; } } } static inline int cmp_u16(const void *_l, const void *_r, size_t size) { const u16 *l = _l, *r = _r; return (*l > *r) - (*r - *l); } static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) { int i, c1 = -1, c2 = -1; ssize_t r; r = eytzinger0_find_le(test_array, nr, sizeof(test_array[0]), cmp_u16, &search); if (r >= 0) c1 = test_array[r]; for (i = 0; i < nr; i++) if (test_array[i] <= search && test_array[i] > c2) c2 = test_array[i]; if (c1 != c2) { eytzinger0_for_each(i, nr) pr_info("[%3u] = %12u", i, test_array[i]); pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", i, r, c1, c2); } } void eytzinger0_find_test(void) { unsigned i, nr, allocated = 1 << 12; u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); for (nr = 1; nr < allocated; nr++) { pr_info("testing %u elems", nr); get_random_bytes(test_array, nr * sizeof(test_array[0])); eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); /* verify array is sorted correctly: */ eytzinger0_for_each(i, nr) BUG_ON(i != eytzinger0_last(nr) && test_array[i] > test_array[eytzinger0_next(i, nr)]); for (i = 0; i < U16_MAX; i += 1 << 12) eytzinger0_find_test_val(test_array, nr, i); for (i = 0; i < nr; i++) { eytzinger0_find_test_val(test_array, nr, test_array[i] - 1); eytzinger0_find_test_val(test_array, nr, test_array[i]); eytzinger0_find_test_val(test_array, nr, test_array[i] + 1); } } kfree(test_array); } #endif /* * Accumulate percpu counters onto one cpu's copy - only valid when access * against any percpu counter is guarded against */ u64 *bch2_acc_percpu_u64s(u64 __percpu *p, unsigned nr) { … } void bch2_darray_str_exit(darray_str *d) { … } int bch2_split_devs(const char *_dev_name, darray_str *ret) { … }
Codebase Browser
linux