/*

 * Copyright (c) 2020 Red Hat, Inc.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2

 * of the License, or (at your option) any later version.

 * 

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

 * 02110-1301, USA. 

 *

 * $Id: //eng/vdo-releases/aluminum/src/c++/vdo/kernel/histogram.c#2 $

 */

#include <linux/kobject.h>

#include "memoryAlloc.h"

#include "typeDefs.h"

#include "histogram.h"

#include "logger.h"

#include "numUtils.h"

/*

 * Set NO_BUCKETS to streamline the histogram code by reducing it to

 * tracking just minimum, maximum, mean, etc. Only one bucket counter

 * (the final one for "bigger" values) will be used, no range checking

 * is needed to find the right bucket, and no histogram will be

 * reported. With newer compilers, the histogram output code will be

 * optimized out.

 */

enum {

  NO_BUCKETS = 1

};

/*

 * Support histogramming in the VDO code.

 *

 * This is not a complete and general histogram package.  It follows the XP

 * practice of implementing the "customer" requirements, and no more.  We can

 * support other requirements after we know what they are.

 *

 * The code was originally borrowed from Albireo, and includes both linear and

 * logarithmic histograms.  VDO only uses the logarithmic histograms.

 *

 * All samples are uint64_t values.

 *

 * A unit conversion option is supported internally to allow sample values to

 * be supplied in "jiffies" and results to be reported via /sys in

 * milliseconds. Depending on the system configuration, this could mean a

 * factor of four (a bucket for values of 1 jiffy is reported as 4-7

 * milliseconds). In theory it could be a non-integer ratio (including less

 * than one), but as the x86-64 platforms we've encountered appear to use 1 or

 * 4 milliseconds per jiffy, we don't support non-integer values yet.

 *

 * All internal processing uses the values as passed to enterHistogramSample.

 * Conversions only affect the values seen or input through the /sys interface,

 * including possibly rounding a "limit" value entered.

 */

struct histogram {

  // These fields are ordered so that enterHistogramSample touches

  // only the first cache line.

  atomic64_t     *counters;     // Counter for each bucket

  uint64_t        limit;        // We want to know how many samples are larger

  atomic64_t      sum;          // Sum of all the samples

  atomic64_t      count;        // Number of samples

  atomic64_t      minimum;      // Minimum value

  atomic64_t      maximum;      // Maximum value

  atomic64_t      unacceptable; // Number of samples that exceed the limit

  int             numBuckets;   // The number of buckets

  bool            logFlag;      // True if the y scale should be logarithmic

  // These fields are used only when reporting results.

  const char     *label;        // Histogram label

  const char     *countedItems; // Name for things being counted

  const char     *metric;       // Term for value used to divide into buckets

  const char     *sampleUnits;  // Unit for measuring metric; NULL for count

  unsigned int    conversionFactor; // Converts input units to reporting units

  struct kobject  kobj;

};

/*

 * Fixed table defining the top value for each bucket of a logarithmic

 * histogram.  We arbitrarily limit the histogram to 12 orders of magnitude.

 */

enum { MAX_LOG_SIZE = 12 };

static const uint64_t bottomValue[1 + 10 * MAX_LOG_SIZE] = {

  // 0 to 10 - The first 10 buckets are linear

  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

  // 10 to 100 - From this point on, the Nth entry of the table is

  //             floor(exp10((double)N/10.0)).

  12, 15, 19, 25, 31, 39, 50, 63, 79, 100,

  // 100 to 1K

  125, 158, 199, 251, 316, 398, 501, 630, 794, 1000,

  // 1K to 10K

  1258, 1584, 1995, 2511, 3162, 3981, 5011, 6309, 7943, 10000,

  // 10K to 100K

  12589, 15848, 19952, 25118, 31622, 39810, 50118, 63095, 79432, 100000,

  // 100K to 1M

  125892, 158489, 199526, 251188, 316227,

  398107, 501187, 630957, 794328, 1000000,

  // 1M to 10M

  1258925, 1584893, 1995262, 2511886, 3162277,

  3981071, 5011872, 6309573, 7943282, 10000000,

  // 10M to 100M

  12589254, 15848931, 19952623, 25118864, 31622776,

  39810717, 50118723, 63095734, 79432823, 100000000,

  // 100M to 1G

  125892541, 158489319, 199526231, 251188643, 316227766,

  398107170, 501187233, 630957344, 794328234, 1000000000,

  // 1G to 10G

  1258925411L, 1584893192L, 1995262314L, 2511886431L, 3162277660L,

  3981071705L, 5011872336L, 6309573444L, 7943282347L, 10000000000L,

  // 10G to 100G

  12589254117L, 15848931924L, 19952623149L, 25118864315L, 31622776601L,

  39810717055L, 50118723362L, 63095734448L, 79432823472L, 100000000000L,

  // 100G to 1T

  125892541179L, 158489319246L, 199526231496L, 251188643150L, 316227766016L,

  398107170553L, 501187233627L, 630957344480L, 794328234724L, 1000000000000L,

};

/***********************************************************************/

static unsigned int divideRoundingToNearest(uint64_t number, uint64_t divisor)

{

  number += divisor / 2;

  return number / divisor;

}

/***********************************************************************/

static int maxBucket(Histogram *h)

{

  int max = h->numBuckets;

  while ((max >= 0) && (atomic64_read(&h->counters[max]) == 0)) {

    max--;

  }

  // max == -1 means that there were no samples

  return max;

}

/***********************************************************************/

typedef struct {

  struct attribute attr;

  ssize_t (*show)(Histogram *h, char *buf);

  ssize_t (*store)(Histogram *h, const char *buf, size_t length);

} HistogramAttribute;

/***********************************************************************/

static void histogramKobjRelease(struct kobject *kobj)

{

  Histogram *h = container_of(kobj, Histogram, kobj);

  FREE(h->counters);

  FREE(h);

}

/***********************************************************************/

static ssize_t histogramShow(struct kobject   *kobj,

                             struct attribute *attr,

                             char             *buf)

{

  HistogramAttribute *ha = container_of(attr, HistogramAttribute, attr);

  if (ha->show == NULL) {

    return -EINVAL;

  }

  Histogram *h = container_of(kobj, Histogram, kobj);

  return ha->show(h, buf);

}

/***********************************************************************/

static ssize_t histogramStore(struct kobject   *kobj,

                              struct attribute *attr,

                              const char       *buf,

                              size_t            length)

{

  HistogramAttribute *ha = container_of(attr, HistogramAttribute, attr);

  if (ha->show == NULL) {

    return -EINVAL;

  }

  Histogram *h = container_of(kobj, Histogram, kobj);

  return ha->store(h, buf, length);

}

/***********************************************************************/

static ssize_t histogramShowCount(Histogram *h, char *buf)

{

  int64_t count = atomic64_read(&h->count);

  return sprintf(buf, "%" PRId64 "\n", count);

}

/***********************************************************************/

static ssize_t histogramShowHistogram(Histogram *h, char *buffer)

{

  /*

   * We're given one page in which to write. The caller logs a complaint if we

   * report that we've written too much, so we'll truncate to PAGE_SIZE-1.

   */

  size_t bufferSize = PAGE_SIZE;

  bool bars = true;

  ssize_t length = 0;

  int max = maxBucket(h);

  // If max is -1, we'll fall through to reporting the total of zero.

  enum { BAR_SIZE = 50 };

  char bar[BAR_SIZE + 2];

  bar[0] = ' ';

  memset(bar + 1, '=', BAR_SIZE);

  bar[BAR_SIZE + 1] = '\0';

  uint64_t total = 0;

  for (int i = 0; i <= max; i++) {

    total += atomic64_read(&h->counters[i]);

  }

  length += snprintf(buffer, bufferSize, "%s Histogram - number of %s by %s",

                     h->label, h->countedItems, h->metric);

  if (length >= (bufferSize - 1)) {

    return bufferSize - 1;

  }

  if (h->sampleUnits != NULL) {

    length += snprintf(buffer + length, bufferSize - length, " (%s)",

                       h->sampleUnits);

    if (length >= (bufferSize - 1)) {

      return bufferSize - 1;

    }

  }

  length += snprintf(buffer + length, bufferSize - length, "\n");

  if (length >= (bufferSize - 1)) {

    return bufferSize - 1;

  }

  for (int i = 0; i <= max; i++) {

    uint64_t value = atomic64_read(&h->counters[i]);

    unsigned int barLength;

    if (bars && (total != 0)) {

      // +1 for the space at the beginning

      barLength = (divideRoundingToNearest(value * BAR_SIZE, total) + 1);

      if (barLength == 1) {

        // Don't bother printing just the initial space.

        barLength = 0;

      }

    } else {

      // 0 means skip the space and the bar

      barLength = 0;

    }

    if (h->logFlag) {

      if (i == h->numBuckets) {

        length += snprintf(buffer + length, bufferSize - length, "%-16s",

                           "Bigger");

      } else {

        unsigned int lower = h->conversionFactor * bottomValue[i];

        unsigned int upper = h->conversionFactor * bottomValue[i + 1] - 1;

        length += snprintf(buffer + length, bufferSize - length, "%6u - %7u",

                           lower, upper);

      }

    } else {

      if (i == h->numBuckets) {

        length += snprintf(buffer + length, bufferSize - length, "%6s",

                           "Bigger");

      } else {

        length += snprintf(buffer + length, bufferSize - length, "%6d", i);

      }

    }

    if (length >= (bufferSize - 1)) {

      return bufferSize - 1;

    }

    length += snprintf(buffer + length, bufferSize - length,

                       " : %12llu%.*s\n", value, barLength, bar);

    if (length >= (bufferSize - 1)) {

      return bufferSize - 1;

    }

  }

  length += snprintf(buffer + length, bufferSize - length,

                     "total %llu\n", total);

  return minSizeT(bufferSize - 1, length);

}

/***********************************************************************/

static ssize_t histogramShowMaximum(Histogram *h, char *buf)

{

  // Maximum is initialized to 0.

  unsigned long value = atomic64_read(&h->maximum);

  return sprintf(buf, "%lu\n", h->conversionFactor * value);

}

/***********************************************************************/

static ssize_t histogramShowMinimum(Histogram *h, char *buf)

{

  // Minimum is initialized to -1.

  unsigned long value = ((atomic64_read(&h->count) > 0)

                         ? atomic64_read(&h->minimum)

                         : 0);

  return sprintf(buf, "%lu\n", h->conversionFactor * value);

}

/***********************************************************************/

static ssize_t histogramShowLimit(Histogram *h, char *buf)

{

  // Display the limit in the reporting units

  return sprintf(buf, "%u\n", (unsigned int)(h->conversionFactor * h->limit));

}

/***********************************************************************/

static ssize_t histogramStoreLimit(Histogram  *h,

                                   const char *buf,

                                   size_t      length)

{

  unsigned int value;

  if ((length > 12) || (sscanf(buf, "%u", &value) != 1)) {

    return -EINVAL;

  }

  /*

   * Convert input from reporting units (e.g., milliseconds) to internal

   * recording units (e.g., jiffies).

   *

   * computeBucketCount could also be called "divideRoundingUp".

   */

  h->limit = computeBucketCount(value, h->conversionFactor);

  atomic64_set(&h->unacceptable, 0);

  return length;

}

/***********************************************************************/

static ssize_t histogramShowMean(Histogram *h, char *buf)

{

  uint64_t count = atomic64_read(&h->count);

  if (count == 0) {

    return sprintf(buf, "0/0\n");

  }

  // Compute mean, scaled up by 1000, in reporting units

  unsigned long sumTimes1000InReportingUnits

    = h->conversionFactor * atomic64_read(&h->sum) * 1000;

  unsigned int meanTimes1000

    = divideRoundingToNearest(sumTimes1000InReportingUnits, count);

  // Print mean with fractional part

  return sprintf(buf, "%u.%03u\n", meanTimes1000 / 1000,

                 meanTimes1000 % 1000);

}

/***********************************************************************/

static ssize_t histogramShowUnacceptable(Histogram *h, char *buf)

{

  int64_t count = atomic64_read(&h->unacceptable);

  return sprintf(buf, "%" PRId64 "\n", count);

}

/***********************************************************************/

static ssize_t histogramShowLabel(Histogram *h, char *buf)

{

  return sprintf(buf, "%s\n", h->label);

}

/***********************************************************************/

static ssize_t histogramShowUnit(Histogram *h, char *buf)

{

  if (h->sampleUnits != NULL) {

    return sprintf(buf, "%s\n", h->sampleUnits);

  } else {

    *buf = 0;

    return 0;

  }

}

/***********************************************************************/

static struct sysfs_ops histogramSysfsOps = {

  .show  = histogramShow,

  .store = histogramStore,

};

static HistogramAttribute countAttribute = {

  .attr = { .name = "count", .mode = 0444, },

  .show = histogramShowCount,

};

static HistogramAttribute histogramAttribute = {

  .attr = { .name = "histogram", .mode = 0444, },

  .show = histogramShowHistogram,

};

static HistogramAttribute labelAttribute = {

  .attr = { .name = "label", .mode = 0444, },

  .show = histogramShowLabel,

};

static HistogramAttribute maximumAttribute = {

  .attr = { .name = "maximum", .mode = 0444, },

  .show = histogramShowMaximum,

};

static HistogramAttribute minimumAttribute = {

  .attr = { .name = "minimum", .mode = 0444, },

  .show = histogramShowMinimum,

};

static HistogramAttribute limitAttribute = {

  .attr  = { .name = "limit", .mode = 0644, },

  .show  = histogramShowLimit,

  .store = histogramStoreLimit,

};

static HistogramAttribute meanAttribute = {

  .attr = { .name = "mean", .mode = 0444, },

  .show = histogramShowMean,

};

static HistogramAttribute unacceptableAttribute = {

  .attr = { .name = "unacceptable", .mode = 0444, },

  .show = histogramShowUnacceptable,

};

static HistogramAttribute unitAttribute = {

  .attr = { .name = "unit", .mode = 0444, },

  .show = histogramShowUnit,

};

// "Real" histogram plotting.

static struct attribute *histogramAttributes[] = {

  &countAttribute.attr,

  &histogramAttribute.attr,

  &labelAttribute.attr,

  &limitAttribute.attr,

  &maximumAttribute.attr,

  &meanAttribute.attr,

  &minimumAttribute.attr,

  &unacceptableAttribute.attr,

  &unitAttribute.attr,

  NULL,

};

static struct kobj_type histogramKobjType = {

  .release       = histogramKobjRelease,

  .sysfs_ops     = &histogramSysfsOps,

  .default_attrs = histogramAttributes,

};

static struct attribute *bucketlessHistogramAttributes[] = {

  &countAttribute.attr,

  &labelAttribute.attr,

  &maximumAttribute.attr,

  &meanAttribute.attr,

  &minimumAttribute.attr,

  &unitAttribute.attr,

  NULL,

};

static struct kobj_type bucketlessHistogramKobjType = {

  .release       = histogramKobjRelease,

  .sysfs_ops     = &histogramSysfsOps,

  .default_attrs = bucketlessHistogramAttributes,

};

/***********************************************************************/

static Histogram *makeHistogram(struct kobject *parent,

                                const char     *name,

                                const char     *label,

                                const char     *countedItems,

                                const char     *metric,

                                const char     *sampleUnits,

                                int             numBuckets,

                                unsigned long   conversionFactor,

                                bool            logFlag)

{

  Histogram *h;

  if (ALLOCATE(1, Histogram, "histogram", &h) != UDS_SUCCESS) {

    return NULL;

  }

  if (NO_BUCKETS) {

    numBuckets = 0;             // plus 1 for "bigger" bucket

  }

  if (numBuckets <= 10) {

    /*

     * The first buckets in a "logarithmic" histogram are still

     * linear, but the bucket-search mechanism is a wee bit slower

     * than for linear, so change the type.

     */

    logFlag = false;

  }

  h->label            = label;

  h->countedItems     = countedItems;

  h->metric           = metric;

  h->sampleUnits      = sampleUnits;

  h->logFlag          = logFlag;

  h->numBuckets       = numBuckets;

  h->conversionFactor = conversionFactor;

  atomic64_set(&h->minimum, -1UL);

  if (ALLOCATE(h->numBuckets + 1, atomic64_t, "histogram counters",

               &h->counters) != UDS_SUCCESS) {

    histogramKobjRelease(&h->kobj);

    return NULL;

  }

  kobject_init(&h->kobj,

               ((numBuckets > 0)

                ? &histogramKobjType

                : &bucketlessHistogramKobjType));

  if (kobject_add(&h->kobj, parent, name) != 0) {

    histogramKobjRelease(&h->kobj);

    return NULL;

  }

  return h;

}

/***********************************************************************/

Histogram *makeLinearHistogram(struct kobject *parent,

                               const char     *name,

                               const char     *initLabel,

                               const char     *countedItems,

                               const char     *metric,

                               const char     *sampleUnits,

                               int             size)

{

  return makeHistogram(parent, name, initLabel, countedItems,

                       metric, sampleUnits, size, 1, false);

}

/**

 * Intermediate routine for creating logarithmic histograms.

 *

 * Limits the histogram size, and computes the bucket count from the

 * orders-of-magnitude count.

 *

 * @param parent            The parent kobject.

 * @param name              The short name of the histogram.  This label is

 *                          used for the sysfs node.

 * @param initLabel         The label for the sampled data.  This label is used

 *                          when we plot the data.

 * @param countedItems      A name (plural) for the things being counted.

 * @param metric            The measure being used to divide samples into

 *                          buckets.

 * @param sampleUnits       The units (plural) for the metric, or NULL if it's

 *                          a simple counter.

 * @param logSize           The number of buckets.  There are buckets for a

 *                          range of sizes up to 10^logSize, and an extra

 *                          bucket for larger samples.

 * @param conversionFactor  Unit conversion factor for reporting.

 *

 * @return the histogram

 **/

static Histogram *

makeLogarithmicHistogramWithConversionFactor(struct kobject *parent,

                                             const char     *name,

                                             const char     *initLabel,

                                             const char     *countedItems,

                                             const char     *metric,

                                             const char     *sampleUnits,

                                             int             logSize,

                                             uint64_t        conversionFactor)

{

  if (logSize > MAX_LOG_SIZE) {

    logSize = MAX_LOG_SIZE;

  }

  return makeHistogram(parent, name,

                       initLabel, countedItems, metric, sampleUnits,

                       10 * logSize, conversionFactor, true);

}

/***********************************************************************/

Histogram *makeLogarithmicHistogram(struct kobject *parent,

                                    const char     *name,

                                    const char     *initLabel,

                                    const char     *countedItems,

                                    const char     *metric,

                                    const char     *sampleUnits,

                                    int             logSize)

{

  return makeLogarithmicHistogramWithConversionFactor(parent, name, initLabel,

                                                      countedItems,

                                                      metric, sampleUnits,

                                                      logSize, 1);

}

/***********************************************************************/

Histogram *makeLogarithmicJiffiesHistogram(struct kobject *parent,

                                           const char     *name,

                                           const char     *initLabel,

                                           const char     *countedItems,

                                           const char     *metric,

                                           int             logSize)

{

  /*

   * If these fail, we have a jiffy duration that is not an integral number of

   * milliseconds, and the unit conversion code needs updating.

   */

  STATIC_ASSERT(HZ <= MSEC_PER_SEC);

  STATIC_ASSERT((MSEC_PER_SEC % HZ) == 0);

  return makeLogarithmicHistogramWithConversionFactor(parent, name, initLabel,

                                                      countedItems,

                                                      metric, "milliseconds",

                                                      logSize,

                                                      jiffies_to_msecs(1));

}

/***********************************************************************/

void enterHistogramSample(Histogram *h, uint64_t sample)

{

  int bucket;

  if (h->logFlag) {

    int lo = 0;

    int hi = h->numBuckets;

    while (lo < hi) {

      int middle = (lo + hi) / 2;

      if (sample < bottomValue[middle + 1]) {

        hi = middle;

      } else {

        lo = middle + 1;

      }

    }

    bucket = lo;

  } else {

    bucket = sample < h->numBuckets ? sample : h->numBuckets;

  }

  atomic64_inc(&h->counters[bucket]);

  atomic64_inc(&h->count);

  atomic64_add(sample, &h->sum);

  if ((h->limit > 0) && (sample > h->limit)) {

    atomic64_inc(&h->unacceptable);

  }

  /*

   * Theoretically this could loop a lot; in practice it should rarely

   * do more than a single read, with no memory barrier, from a cache

   * line we've already referenced above.

   */

  uint64_t oldMaximum = atomic64_read(&h->maximum);

  while (oldMaximum < sample) {

    uint64_t readValue = atomic64_cmpxchg(&h->maximum, oldMaximum, sample);

    if (readValue == oldMaximum) {

      break;

    }

    oldMaximum = readValue;

  }

  uint64_t oldMinimum = atomic64_read(&h->minimum);

  while (oldMinimum > sample) {

    uint64_t readValue = atomic64_cmpxchg(&h->minimum, oldMinimum, sample);

    if (readValue == oldMinimum) {

      break;

    }

    oldMinimum = readValue;

  }

}

/***********************************************************************/

void freeHistogram(Histogram **hp)

{

  if (*hp != NULL) {

    Histogram *h = *hp;

    kobject_put(&h->kobj);

    *hp = NULL;

  }

}