Line data    Source code

       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
      67          22 : __spdk_histogram_increment(struct spdk_histogram_data *h, uint32_t range, uint32_t index)
      68             : {
      69          22 :         uint64_t *count;
      70             : 
      71          22 :         count = &h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
      72          22 :         (*count)++;
      73          22 : }
      74             : 
      75             : static inline uint64_t
      76      103936 : __spdk_histogram_get_count(const struct spdk_histogram_data *h, uint32_t range, uint32_t index)
      77             : {
      78      103936 :         return h->bucket[(range << SPDK_HISTOGRAM_BUCKET_SHIFT(h)) + index];
      79             : }
      80             : 
      81             : static inline uint64_t *
      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
      88           0 : spdk_histogram_data_reset(struct spdk_histogram_data *histogram)
      89             : {
      90           0 :         memset(histogram->bucket, 0, SPDK_HISTOGRAM_NUM_BUCKETS(histogram) * sizeof(uint64_t));
      91           0 : }
      92             : 
      93             : static inline uint32_t
      94          22 : __spdk_histogram_data_get_bucket_range(struct spdk_histogram_data *h, uint64_t datapoint)
      95             : {
      96          22 :         uint32_t clz, range;
      97             : 
      98          22 :         clz = datapoint > 0 ? __builtin_clzll(datapoint) : 64;
      99             : 
     100          22 :         if (clz <= SPDK_HISTOGRAM_BUCKET_LSB(h)) {
     101          12 :                 range = SPDK_HISTOGRAM_BUCKET_LSB(h) - clz;
     102          12 :         } else {
     103          10 :                 range = 0;
     104             :         }
     105             : 
     106          44 :         return range;
     107          22 : }
     108             : 
     109             : static inline uint32_t
     110          22 : __spdk_histogram_data_get_bucket_index(struct spdk_histogram_data *h, uint64_t datapoint,
     111             :                                        uint32_t range)
     112             : {
     113          22 :         uint32_t shift;
     114             : 
     115          22 :         if (range == 0) {
     116          10 :                 shift = 0;
     117          10 :         } else {
     118          12 :                 shift = range - 1;
     119             :         }
     120             : 
     121          22 :         return (datapoint >> shift) & SPDK_HISTOGRAM_BUCKET_MASK(h);
     122          22 : }
     123             : 
     124             : static inline void
     125          22 : spdk_histogram_data_tally(struct spdk_histogram_data *histogram, uint64_t datapoint)
     126             : {
     127          22 :         uint32_t range = __spdk_histogram_data_get_bucket_range(histogram, datapoint);
     128          22 :         uint32_t index = __spdk_histogram_data_get_bucket_index(histogram, datapoint, range);
     129             : 
     130          22 :         __spdk_histogram_increment(histogram, range, index);
     131          22 : }
     132             : 
     133             : static inline uint64_t
     134       51968 : __spdk_histogram_data_get_bucket_start(const struct spdk_histogram_data *h, uint32_t range,
     135             :                                        uint32_t index)
     136             : {
     137       51968 :         uint64_t bucket;
     138             : 
     139       51968 :         index += 1;
     140       51968 :         if (range > 0) {
     141       51072 :                 bucket = 1ULL << (range + SPDK_HISTOGRAM_BUCKET_SHIFT(h) - 1);
     142       51072 :                 bucket += (uint64_t)index << (range - 1);
     143       51072 :         } else {
     144         896 :                 bucket = index;
     145             :         }
     146             : 
     147      103936 :         return bucket;
     148       51968 : }
     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
     154           7 : spdk_histogram_data_iterate(const struct spdk_histogram_data *histogram,
     155             :                             spdk_histogram_data_fn fn, void *ctx)
     156             : {
     157           7 :         uint64_t i, j, count, so_far, total;
     158           7 :         uint64_t bucket, last_bucket;
     159             : 
     160           7 :         total = 0;
     161             : 
     162         413 :         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
     163       52374 :                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
     164       51968 :                         total += __spdk_histogram_get_count(histogram, i, j);
     165       51968 :                 }
     166         406 :         }
     167             : 
     168           7 :         so_far = 0;
     169           7 :         bucket = 0;
     170             : 
     171         413 :         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKET_RANGES(histogram); i++) {
     172       52374 :                 for (j = 0; j < SPDK_HISTOGRAM_NUM_BUCKETS_PER_RANGE(histogram); j++) {
     173       51968 :                         count = __spdk_histogram_get_count(histogram, i, j);
     174       51968 :                         so_far += count;
     175       51968 :                         last_bucket = bucket;
     176       51968 :                         bucket = __spdk_histogram_data_get_bucket_start(histogram, i, j);
     177       51968 :                         fn(ctx, last_bucket, bucket, count, total, so_far);
     178       51968 :                 }
     179         406 :         }
     180           7 : }
     181             : 
     182             : static inline int
     183           8 : spdk_histogram_data_merge(const struct spdk_histogram_data *dst,
     184             :                           const struct spdk_histogram_data *src)
     185             : {
     186           8 :         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           8 :         if (dst->bucket_shift != src->bucket_shift) {
     193           1 :                 return -EINVAL;
     194             :         }
     195             : 
     196       51975 :         for (i = 0; i < SPDK_HISTOGRAM_NUM_BUCKETS(dst); i++) {
     197       51968 :                 dst->bucket[i] += src->bucket[i];
     198       51968 :         }
     199             : 
     200           7 :         return 0;
     201           8 : }
     202             : 
     203             : static inline struct spdk_histogram_data *
     204          10 : spdk_histogram_data_alloc_sized(uint32_t bucket_shift)
     205             : {
     206          10 :         struct spdk_histogram_data *h;
     207             : 
     208          10 :         h = (struct spdk_histogram_data *)calloc(1, sizeof(*h));
     209          10 :         if (h == NULL) {
     210           0 :                 return NULL;
     211             :         }
     212             : 
     213          10 :         h->bucket_shift = bucket_shift;
     214          10 :         h->bucket = (uint64_t *)calloc(SPDK_HISTOGRAM_NUM_BUCKETS(h), sizeof(uint64_t));
     215          10 :         if (h->bucket == NULL) {
     216           0 :                 free(h);
     217           0 :                 return NULL;
     218             :         }
     219             : 
     220          10 :         return h;
     221          10 : }
     222             : 
     223             : static inline struct spdk_histogram_data *
     224           8 : spdk_histogram_data_alloc(void)
     225             : {
     226           8 :         return spdk_histogram_data_alloc_sized(SPDK_HISTOGRAM_BUCKET_SHIFT_DEFAULT);
     227             : }
     228             : 
     229             : static inline void
     230          10 : spdk_histogram_data_free(struct spdk_histogram_data *h)
     231             : {
     232          10 :         if (h == NULL) {
     233           0 :                 return;
     234             :         }
     235             : 
     236          10 :         free(h->bucket);
     237          10 :         free(h);
     238          10 : }
     239             : 
     240             : #ifdef __cplusplus
     241             : }
     242             : #endif
     243             : 
     244             : #endif