ceph/src/spdk/include/spdk/histogram_data.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright (c) Intel Corporation.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /**
  35  * \file
  36  * Generic histogram library
  37  */
  38
  39 #ifndef _SPDK_HISTOGRAM_DATA_H_
  40 #define _SPDK_HISTOGRAM_DATA_H_
  41
  42 #include "spdk/stdinc.h"
  43
  44 #ifdef __cplusplus
  45 extern "C" {
  46 #endif
  47
  48 #define SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT     7
  49 #define SPDK_HISTOGRAM_BUCKET_SHIFT(h)          h->bucket_shift
  50 #define SPDK_HISTOGRAM_BUCKET_LSB(h)            (64 - SPDK_HISTOGRAM_BUCKET_SHIFT(h))
  51 #define SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) (1ULL << SPDK_HISTOGRAM_BUCKET_SHIFT(h))
  52 #define SPDK_HISTOGRAM_BUCKET_MASK(h)           (SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) - 1)
  53 #define SPDK_HISTOGRAM_NUM_BUCKET_RANGES(h)     (SPDK_HISTOGRAM_BUCKET_LSB(h) + 1)
  54 #define SPDK_HISTOGRAM_NUM_BUCKETS(h)           (SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(h) * \
  55                                                  SPDK_HISTOGRAM_NUM_BUCKET_RANGES(h))
  56
  57 /*
  58  * SPDK histograms are implemented using ranges of bucket arrays.  The most common usage
  59  * model is using TSC datapoints to capture an I/O latency histogram.  For this usage model,
  60  * the histogram tracks only TSC deltas - any translation to microseconds is done by the
  61  * histogram user calling spdk_histogram_data_iterate() to iterate over the buckets to perform
  62  * the translations.
  63  *
  64  * Each range has a number of buckets determined by SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE
  65  * which is 128.  The buckets in ranges 0 and 1 each map to one specific datapoint value.
  66  * The buckets in subsequent ranges each map to twice as many datapoint values as buckets
  67  * in the range before it:
  68  *
  69  * Range 0:  1 value each  - 128 buckets cover 0 to 127 (2^7-1)
  70  * Range 1:  1 value each  - 128 buckets cover 128 to 255 (2^8-1)
  71  * Range 2:  2 values each - 128 buckets cover 256 to 511 (2^9-1)
  72  * Range 3:  4 values each - 128 buckets cover 512 to 1023 (2^10-1)
  73  * Range 4:  8 values each - 128 buckets cover 1024 to 2047 (2^11-1)
  74  * Range 5: 16 values each - 128 buckets cover 2048 to 4095 (2^12-1)
  75  * ...
  76  * Range 55: 2^54 values each - 128 buckets cover 2^61 to 2^62-1
  77  * Range 56: 2^55 values each - 128 buckets cover 2^62 to 2^63-1
  78  * Range 57: 2^56 values each - 128 buckets cover 2^63 to 2^64-1
  79  *
  80  * On a 2.3GHz processor, this strategy results in 50ns buckets in the 7-14us range (sweet
  81  * spot for Intel Optane SSD latency testing).
  82  *
  83  * Buckets can be made more granular by increasing SPDK_HISTOGRAM_BUCKET_SHIFT.  This
  84  * comes at the cost of additional storage per namespace context to store the bucket data.
  85  */
  86
  87 struct spdk_histogram_data {
  88
  89         uint32_t        bucket_shift;
  90         uint64_t        *bucket;
  91
  92 };
  93
  94 static inline void
  95 __spdk_histogram_increment(struct spdk_histogram_data *h, uint32_t range, uint32_t index)
  96 {
  97         uint64_t *count;
  98
  99         count = &h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
 100         (*count)++;
 101 }
 102
 103 static inline uint64_t
 104 __spdk_histogram_get_count(const struct spdk_histogram_data *h, uint32_t range, uint32_t index)
 105 {
 106         return h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
 107 }
 108
 109 static inline uint64_t *
 110 __spdk_histogram_get_bucket(const struct spdk_histogram_data *h, uint32_t range, uint32_t index)
 111 {
 112         return &h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
 113 }
 114
 115 static inline void
 116 spdk_histogram_data_reset(struct spdk_histogram_data *histogram)
 117 {
 118         memset(histogram->bucket, 0, SPDK_HISTOGRAM_NUM_BUCKETS(histogram) * sizeof(uint64_t));
 119 }
 120
 121 static inline uint32_t
 122 __spdk_histogram_data_get_bucket_range(struct spdk_histogram_data *h, uint64_t datapoint)
 123 {
 124         uint32_t clz, range;
 125
 126         assert(datapoint != 0);
 127
 128         clz = __builtin_clzll(datapoint);
 129
 130         if (clz <= SPDK_HISTOGRAM_BUCKET_LSB(h)) {
 131                 range = SPDK_HISTOGRAM_BUCKET_LSB(h) - clz;
 132         } else {
 133                 range = 0;
 134         }
 135
 136         return range;
 137 }
 138
 139 static inline uint32_t
 140 __spdk_histogram_data_get_bucket_index(struct spdk_histogram_data *h, uint64_t datapoint,
 141                                        uint32_t range)
 142 {
 143         uint32_t shift;
 144
 145         if (range == 0) {
 146                 shift = 0;
 147         } else {
 148                 shift = range - 1;
 149         }
 150
 151         return (datapoint >> shift) & SPDK_HISTOGRAM_BUCKET_MASK(h);
 152 }
 153
 154 static inline void
 155 spdk_histogram_data_tally(struct spdk_histogram_data *histogram, uint64_t datapoint)
 156 {
 157         uint32_t range = __spdk_histogram_data_get_bucket_range(histogram, datapoint);
 158         uint32_t index = __spdk_histogram_data_get_bucket_index(histogram, datapoint, range);
 159
 160         __spdk_histogram_increment(histogram, range, index);
 161 }
 162
 163 static inline uint64_t
 164 __spdk_histogram_data_get_bucket_start(const struct spdk_histogram_data *h, uint32_t range,
 165                                        uint32_t index)
 166 {
 167         uint64_t bucket;
 168
 169         index += 1;
 170         if (range > 0) {
 171                 bucket = 1ULL << (range + SPDK_HISTOGRAM_BUCKET_SHIFT(h) - 1);
 172                 bucket += (uint64_t)index << (range - 1);
 173         } else {
 174                 bucket = index;
 175         }
 176
 177         return bucket;
 178 }
 179
 180 typedef void (*spdk_histogram_data_fn)(void *ctx, uint64_t start, uint64_t end, uint64_t count,
 181                                        uint64_t total, uint64_t so_far);
 182
 183 static inline void
 184 spdk_histogram_data_iterate(const struct spdk_histogram_data *histogram,
 185                             spdk_histogram_data_fn fn, void *ctx)
 186 {
 187         uint64_t i, j, count, so_far, total;
 188         uint64_t bucket, last_bucket;
 189
 190         total = 0;
 191
 192         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
 193                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
 194                         total += __spdk_histogram_get_count(histogram, i, j);
 195                 }
 196         }
 197
 198         so_far = 0;
 199         bucket = 0;
 200
 201         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
 202                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
 203                         count = __spdk_histogram_get_count(histogram, i, j);
 204                         so_far += count;
 205                         last_bucket = bucket;
 206                         bucket = __spdk_histogram_data_get_bucket_start(histogram, i, j);
 207                         fn(ctx, last_bucket, bucket, count, total, so_far);
 208                 }
 209         }
 210 }
 211
 212 static inline void
 213 spdk_histogram_data_merge(const struct spdk_histogram_data *dst,
 214                           const struct spdk_histogram_data *src)
 215 {
 216         uint64_t i;
 217
 218         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKETS(dst); i++) {
 219                 dst->bucket[i] += src->bucket[i];
 220         }
 221 }
 222
 223 static inline struct spdk_histogram_data *
 224 spdk_histogram_data_alloc_sized(uint32_t bucket_shift)
 225 {
 226         struct spdk_histogram_data *h;
 227
 228         h = (struct spdk_histogram_data *)calloc(1, sizeof(*h));
 229         if (h == NULL) {
 230                 return NULL;
 231         }
 232
 233         h->bucket_shift = bucket_shift;
 234         h->bucket = (uint64_t *)calloc(SPDK_HISTOGRAM_NUM_BUCKETS(h), sizeof(uint64_t));
 235         if (h->bucket == NULL) {
 236                 free(h);
 237                 return NULL;
 238         }
 239
 240         return h;
 241 }
 242
 243 static inline struct spdk_histogram_data *
 244 spdk_histogram_data_alloc(void)
 245 {
 246         return spdk_histogram_data_alloc_sized(SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT);
 247 }
 248
 249 static inline void
 250 spdk_histogram_data_free(struct spdk_histogram_data *h)
 251 {
 252         if (h == NULL) {
 253                 return;
 254         }
 255
 256         free(h->bucket);
 257         free(h);
 258 }
 259
 260 #ifdef __cplusplus
 261 }
 262 #endif
 263
 264 #endif