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 void
 110 spdk_histogram_data_reset(struct spdk_histogram_data *histogram)
 111 {
 112         memset(histogram->bucket, 0, SPDK_HISTOGRAM_NUM_BUCKETS(histogram) * sizeof(uint64_t));
 113 }
 114
 115 static inline uint32_t
 116 __spdk_histogram_data_get_bucket_range(struct spdk_histogram_data *h, uint64_t datapoint)
 117 {
 118         uint32_t clz, range;
 119
 120         assert(datapoint != 0);
 121
 122         clz = __builtin_clzll(datapoint);
 123
 124         if (clz <= SPDK_HISTOGRAM_BUCKET_LSB(h)) {
 125                 range = SPDK_HISTOGRAM_BUCKET_LSB(h) - clz;
 126         } else {
 127                 range = 0;
 128         }
 129
 130         return range;
 131 }
 132
 133 static inline uint32_t
 134 __spdk_histogram_data_get_bucket_index(struct spdk_histogram_data *h, uint64_t datapoint,
 135                                        uint32_t range)
 136 {
 137         uint32_t shift;
 138
 139         if (range == 0) {
 140                 shift = 0;
 141         } else {
 142                 shift = range - 1;
 143         }
 144
 145         return (datapoint >> shift) & SPDK_HISTOGRAM_BUCKET_MASK(h);
 146 }
 147
 148 static inline void
 149 spdk_histogram_data_tally(struct spdk_histogram_data *histogram, uint64_t datapoint)
 150 {
 151         uint32_t range = __spdk_histogram_data_get_bucket_range(histogram, datapoint);
 152         uint32_t index = __spdk_histogram_data_get_bucket_index(histogram, datapoint, range);
 153
 154         __spdk_histogram_increment(histogram, range, index);
 155 }
 156
 157 static inline uint64_t
 158 __spdk_histogram_data_get_bucket_start(const struct spdk_histogram_data *h, uint32_t range,
 159                                        uint32_t index)
 160 {
 161         uint64_t bucket;
 162
 163         index += 1;
 164         if (range > 0) {
 165                 bucket = 1ULL << (range + SPDK_HISTOGRAM_BUCKET_SHIFT(h) - 1);
 166                 bucket += (uint64_t)index << (range - 1);
 167         } else {
 168                 bucket = index;
 169         }
 170
 171         return bucket;
 172 }
 173
 174 typedef void (*spdk_histogram_data_fn)(void *ctx, uint64_t start, uint64_t end, uint64_t count,
 175                                        uint64_t total, uint64_t so_far);
 176
 177 static inline void
 178 spdk_histogram_data_iterate(const struct spdk_histogram_data *histogram,
 179                             spdk_histogram_data_fn fn, void *ctx)
 180 {
 181         uint64_t i, j, count, so_far, total;
 182         uint64_t bucket, last_bucket;
 183
 184         total = 0;
 185
 186         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
 187                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
 188                         total += __spdk_histogram_get_count(histogram, i, j);
 189                 }
 190         }
 191
 192         so_far = 0;
 193         bucket = 0;
 194
 195         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
 196                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
 197                         count = __spdk_histogram_get_count(histogram, i, j);
 198                         so_far += count;
 199                         last_bucket = bucket;
 200                         bucket = __spdk_histogram_data_get_bucket_start(histogram, i, j);
 201                         fn(ctx, last_bucket, bucket, count, total, so_far);
 202                 }
 203         }
 204 }
 205
 206 static inline struct spdk_histogram_data *
 207 spdk_histogram_data_alloc_sized(uint32_t bucket_shift)
 208 {
 209         struct spdk_histogram_data *h;
 210
 211         h = (struct spdk_histogram_data *)calloc(1, sizeof(*h));
 212         if (h == NULL) {
 213                 return NULL;
 214         }
 215
 216         h->bucket_shift = bucket_shift;
 217         h->bucket = (uint64_t *)calloc(SPDK_HISTOGRAM_NUM_BUCKETS(h), sizeof(uint64_t));
 218         if (h->bucket == NULL) {
 219                 free(h);
 220                 return NULL;
 221         }
 222
 223         return h;
 224 }
 225
 226 static inline struct spdk_histogram_data *
 227 spdk_histogram_data_alloc(void)
 228 {
 229         return spdk_histogram_data_alloc_sized(SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT);
 230 }
 231
 232 static inline void
 233 spdk_histogram_data_free(struct spdk_histogram_data *h)
 234 {
 235         if (h == NULL) {
 236                 return;
 237         }
 238
 239         free(h->bucket);
 240         free(h);
 241 }
 242
 243 #ifdef __cplusplus
 244 }
 245 #endif
 246
 247 #endif