1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright (C) 2017 Intel Corporation.
3 * All rights reserved.
4 */
5
6 /**
7 * \file
8 * Generic histogram library
9 */
10
11 #ifndef _SPDK_HISTOGRAM_DATA_H_
12 #define _SPDK_HISTOGRAM_DATA_H_
13
14 #include "spdk/stdinc.h"
15
16 #ifdef __cplusplus
17 extern "C" {
18 #endif
19
20 #define SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT 7
21 #define SPDK_HISTOGRAM_BUCKET_SHIFT(h) h->bucket_shift
22 #define SPDK_HISTOGRAM_BUCKET_LSB(h) (64 - SPDK_HISTOGRAM_BUCKET_SHIFT(h))
23 #define SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) (1ULL << SPDK_HISTOGRAM_BUCKET_SHIFT(h))
24 #define SPDK_HISTOGRAM_BUCKET_MASK(h) (SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) - 1)
25 #define SPDK_HISTOGRAM_NUM_BUCKET_RANGES(h) (SPDK_HISTOGRAM_BUCKET_LSB(h) + 1)
26 #define SPDK_HISTOGRAM_NUM_BUCKETS(h) (SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) * \
27 SPDK_HISTOGRAM_NUM_BUCKET_RANGES(h))
28
29 /*
30 * SPDK histograms are implemented using ranges of bucket arrays. The most common usage
31 * model is using TSC datapoints to capture an I/O latency histogram. For this usage model,
32 * the histogram tracks only TSC deltas - any translation to microseconds is done by the
33 * histogram user calling spdk_histogram_data_iterate() to iterate over the buckets to perform
34 * the translations.
35 *
36 * Each range has a number of buckets determined by SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE
37 * which is 128. The buckets in ranges 0 and 1 each map to one specific datapoint value.
38 * The buckets in subsequent ranges each map to twice as many datapoint values as buckets
39 * in the range before it:
40 *
41 * Range 0: 1 value each - 128 buckets cover 0 to 127 (2^7-1)
42 * Range 1: 1 value each - 128 buckets cover 128 to 255 (2^8-1)
43 * Range 2: 2 values each - 128 buckets cover 256 to 511 (2^9-1)
44 * Range 3: 4 values each - 128 buckets cover 512 to 1023 (2^10-1)
45 * Range 4: 8 values each - 128 buckets cover 1024 to 2047 (2^11-1)
46 * Range 5: 16 values each - 128 buckets cover 2048 to 4095 (2^12-1)
47 * ...
48 * Range 55: 2^54 values each - 128 buckets cover 2^61 to 2^62-1
49 * Range 56: 2^55 values each - 128 buckets cover 2^62 to 2^63-1
50 * Range 57: 2^56 values each - 128 buckets cover 2^63 to 2^64-1
51 *
52 * On a 2.3GHz processor, this strategy results in 50ns buckets in the 7-14us range (sweet
53 * spot for Intel Optane SSD latency testing).
54 *
55 * Buckets can be made more granular by increasing SPDK_HISTOGRAM_BUCKET_SHIFT. This
56 * comes at the cost of additional storage per namespace context to store the bucket data.
57 */
58
59 struct spdk_histogram_data {
60
61 uint32_t bucket_shift;
62 uint64_t *bucket;
63
64 };
65
66 static inline void
__spdk_histogram_increment(struct spdk_histogram_data * h,uint32_t range,uint32_t index)67 __spdk_histogram_increment(struct spdk_histogram_data *h, uint32_t range, uint32_t index)
68 {
69 uint64_t *count;
70
71 count = &h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
72 (*count)++;
73 }
74
75 static inline uint64_t
__spdk_histogram_get_count(const struct spdk_histogram_data * h,uint32_t range,uint32_t index)76 __spdk_histogram_get_count(const struct spdk_histogram_data *h, uint32_t range, uint32_t index)
77 {
78 return h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
79 }
80
81 static inline uint64_t *
__spdk_histogram_get_bucket(const struct spdk_histogram_data * h,uint32_t range,uint32_t index)82 __spdk_histogram_get_bucket(const struct spdk_histogram_data *h, uint32_t range, uint32_t index)
83 {
84 return &h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
85 }
86
87 static inline void
spdk_histogram_data_reset(struct spdk_histogram_data * histogram)88 spdk_histogram_data_reset(struct spdk_histogram_data *histogram)
89 {
90 memset(histogram->bucket, 0, SPDK_HISTOGRAM_NUM_BUCKETS(histogram) * sizeof(uint64_t));
91 }
92
93 static inline uint32_t
__spdk_histogram_data_get_bucket_range(struct spdk_histogram_data * h,uint64_t datapoint)94 __spdk_histogram_data_get_bucket_range(struct spdk_histogram_data *h, uint64_t datapoint)
95 {
96 uint32_t clz, range;
97
98 clz = datapoint > 0 ? __builtin_clzll(datapoint) : 64;
99
100 if (clz <= SPDK_HISTOGRAM_BUCKET_LSB(h)) {
101 range = SPDK_HISTOGRAM_BUCKET_LSB(h) - clz;
102 } else {
103 range = 0;
104 }
105
106 return range;
107 }
108
109 static inline uint32_t
__spdk_histogram_data_get_bucket_index(struct spdk_histogram_data * h,uint64_t datapoint,uint32_t range)110 __spdk_histogram_data_get_bucket_index(struct spdk_histogram_data *h, uint64_t datapoint,
111 uint32_t range)
112 {
113 uint32_t shift;
114
115 if (range == 0) {
116 shift = 0;
117 } else {
118 shift = range - 1;
119 }
120
121 return (datapoint >> shift) & SPDK_HISTOGRAM_BUCKET_MASK(h);
122 }
123
124 static inline void
spdk_histogram_data_tally(struct spdk_histogram_data * histogram,uint64_t datapoint)125 spdk_histogram_data_tally(struct spdk_histogram_data *histogram, uint64_t datapoint)
126 {
127 uint32_t range = __spdk_histogram_data_get_bucket_range(histogram, datapoint);
128 uint32_t index = __spdk_histogram_data_get_bucket_index(histogram, datapoint, range);
129
130 __spdk_histogram_increment(histogram, range, index);
131 }
132
133 static inline uint64_t
__spdk_histogram_data_get_bucket_start(const struct spdk_histogram_data * h,uint32_t range,uint32_t index)134 __spdk_histogram_data_get_bucket_start(const struct spdk_histogram_data *h, uint32_t range,
135 uint32_t index)
136 {
137 uint64_t bucket;
138
139 index += 1;
140 if (range > 0) {
141 bucket = 1ULL << (range + SPDK_HISTOGRAM_BUCKET_SHIFT(h) - 1);
142 bucket += (uint64_t)index << (range - 1);
143 } else {
144 bucket = index;
145 }
146
147 return bucket;
148 }
149
150 typedef void (*spdk_histogram_data_fn)(void *ctx, uint64_t start, uint64_t end, uint64_t count,
151 uint64_t total, uint64_t so_far);
152
153 static inline void
spdk_histogram_data_iterate(const struct spdk_histogram_data * histogram,spdk_histogram_data_fn fn,void * ctx)154 spdk_histogram_data_iterate(const struct spdk_histogram_data *histogram,
155 spdk_histogram_data_fn fn, void *ctx)
156 {
157 uint64_t i, j, count, so_far, total;
158 uint64_t bucket, last_bucket;
159
160 total = 0;
161
162 for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
163 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
164 total += __spdk_histogram_get_count(histogram, i, j);
165 }
166 }
167
168 so_far = 0;
169 bucket = 0;
170
171 for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
172 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
173 count = __spdk_histogram_get_count(histogram, i, j);
174 so_far += count;
175 last_bucket = bucket;
176 bucket = __spdk_histogram_data_get_bucket_start(histogram, i, j);
177 fn(ctx, last_bucket, bucket, count, total, so_far);
178 }
179 }
180 }
181
182 static inline int
spdk_histogram_data_merge(const struct spdk_histogram_data * dst,const struct spdk_histogram_data * src)183 spdk_histogram_data_merge(const struct spdk_histogram_data *dst,
184 const struct spdk_histogram_data *src)
185 {
186 uint64_t i;
187
188 /* Histograms with different bucket_shift values cannot be simply
189 * merged, because the buckets represent different ranges of
190 * values.
191 */
192 if (dst->bucket_shift != src->bucket_shift) {
193 return -EINVAL;
194 }
195
196 for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKETS(dst); i++) {
197 dst->bucket[i] += src->bucket[i];
198 }
199
200 return 0;
201 }
202
203 static inline struct spdk_histogram_data *
spdk_histogram_data_alloc_sized(uint32_t bucket_shift)204 spdk_histogram_data_alloc_sized(uint32_t bucket_shift)
205 {
206 struct spdk_histogram_data *h;
207
208 h = (struct spdk_histogram_data *)calloc(1, sizeof(*h));
209 if (h == NULL) {
210 return NULL;
211 }
212
213 h->bucket_shift = bucket_shift;
214 h->bucket = (uint64_t *)calloc(SPDK_HISTOGRAM_NUM_BUCKETS(h), sizeof(uint64_t));
215 if (h->bucket == NULL) {
216 free(h);
217 return NULL;
218 }
219
220 return h;
221 }
222
223 static inline struct spdk_histogram_data *
spdk_histogram_data_alloc(void)224 spdk_histogram_data_alloc(void)
225 {
226 return spdk_histogram_data_alloc_sized(SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT);
227 }
228
229 static inline void
spdk_histogram_data_free(struct spdk_histogram_data * h)230 spdk_histogram_data_free(struct spdk_histogram_data *h)
231 {
232 if (h == NULL) {
233 return;
234 }
235
236 free(h->bucket);
237 free(h);
238 }
239
240 #ifdef __cplusplus
241 }
242 #endif
243
244 #endif
245