pdns/histogram.hh

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of version 2 of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * In addition, for the avoidance of any doubt, permission is granted to
  10  * link this program with OpenSSL and to (re)distribute the binaries
  11  * produced as the result of such linking.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22 #pragma once
  23
  24 #include <cassert>
  25 #include <algorithm>
  26 #include <limits>
  27 #include <stdexcept>
  28 #include <string>
  29 #include <vector>
  30
  31 #include "stat_t.hh"
  32
  33 namespace pdns
  34 {
  35
  36 // By convention, we are using microsecond units
  37 struct Bucket
  38 {
  39   Bucket(std::string name, uint64_t boundary, uint64_t val) :
  40     d_name(std::move(name)), d_boundary(boundary), d_count(val) {}
  41   const std::string d_name;
  42   const uint64_t d_boundary;
  43   mutable uint64_t d_count{0};
  44
  45   Bucket(const Bucket&) = default;
  46   Bucket& operator=(const Bucket& rhs)
  47   {
  48     assert(d_name == rhs.d_name);
  49     assert(d_boundary == rhs.d_boundary);
  50     d_count = rhs.d_count;
  51     return *this;
  52   }
  53 };
  54
  55 struct AtomicBucket
  56 {
  57   // We need the constructors in this case, since atomics have a disabled copy constructor.
  58   AtomicBucket() = default;
  59   AtomicBucket(std::string name, uint64_t boundary, uint64_t val) :
  60     d_name(std::move(name)), d_boundary(boundary), d_count(val) {}
  61   AtomicBucket(const AtomicBucket& rhs) :
  62     d_name(rhs.d_name), d_boundary(rhs.d_boundary), d_count(rhs.d_count.load()) {}
  63
  64   const std::string d_name;
  65   const uint64_t d_boundary{0};
  66   mutable stat_t d_count{0};
  67 };
  68
  69 template <class B, class SumType>
  70 class BaseHistogram
  71 {
  72 public:
  73   BaseHistogram(const std::string& prefix, const std::vector<uint64_t>& boundaries) :
  74     d_name(prefix)
  75   {
  76     if (!std::is_sorted(boundaries.cbegin(), boundaries.cend())) {
  77       throw std::invalid_argument("boundary array must be sorted");
  78     }
  79     if (boundaries.size() == 0) {
  80       throw std::invalid_argument("boundary array must not be empty");
  81     }
  82     if (boundaries[0] == 0) {
  83       throw std::invalid_argument("boundary array's first element should not be zero");
  84     }
  85     d_buckets.reserve(boundaries.size() + 1);
  86     uint64_t prev = 0;
  87     for (auto b : boundaries) {
  88       if (prev == b) {
  89         throw std::invalid_argument("boundary array's elements should be distinct");
  90       }
  91       std::string str = prefix + "le-" + std::to_string(b);
  92       d_buckets.emplace_back(str, b, 0);
  93       prev = b;
  94     }
  95
  96     // everything above last boundary
  97     d_buckets.emplace_back(prefix + "le-max", std::numeric_limits<uint64_t>::max(), 0);
  98   }
  99
 100   BaseHistogram(const std::string& prefix, uint64_t start, int num) :
 101     BaseHistogram(prefix, to125(start, num))
 102   {
 103   }
 104
 105   std::string getName() const
 106   {
 107     return d_name;
 108   }
 109
 110   uint64_t getSum() const
 111   {
 112     return d_sum;
 113   }
 114
 115   const std::vector<B>& getRawData() const
 116   {
 117     return d_buckets;
 118   }
 119
 120   uint64_t getCount(size_t i) const
 121   {
 122     return d_buckets[i].d_count;
 123   }
 124
 125   std::vector<B> getCumulativeBuckets() const
 126   {
 127     std::vector<B> ret;
 128     ret.reserve(d_buckets.size());
 129     uint64_t c{0};
 130     for (const auto& b : d_buckets) {
 131       c += b.d_count;
 132       ret.emplace_back(b.d_name, b.d_boundary, c);
 133     }
 134     return ret;
 135   }
 136
 137   std::vector<uint64_t> getCumulativeCounts() const
 138   {
 139     std::vector<uint64_t> ret;
 140     ret.reserve(d_buckets.size());
 141     uint64_t c = 0;
 142     for (const auto& b : d_buckets) {
 143       c += b.d_count;
 144       ret.emplace_back(c);
 145     }
 146     return ret;
 147   }
 148
 149   static bool lessOrEqual(uint64_t b, const B& bu)
 150   {
 151     return b <= bu.d_boundary;
 152   }
 153
 154   inline void operator()(uint64_t d) const
 155   {
 156     auto index = std::upper_bound(d_buckets.begin(), d_buckets.end(), d, lessOrEqual);
 157     // our index is always valid
 158     ++index->d_count;
 159     d_sum += d;
 160   }
 161
 162   BaseHistogram& operator+=(const BaseHistogram& rhs)
 163   {
 164     assert(d_name == rhs.d_name);
 165     assert(d_buckets.size() == rhs.d_buckets.size());
 166     for (size_t bucket = 0; bucket < d_buckets.size(); ++bucket) {
 167       assert(d_buckets[bucket].d_name == rhs.d_buckets[bucket].d_name);
 168       assert(d_buckets[bucket].d_boundary == rhs.d_buckets[bucket].d_boundary);
 169       d_buckets[bucket].d_count += rhs.d_buckets[bucket].d_count;
 170     }
 171     d_sum += rhs.d_sum;
 172     return *this;
 173   }
 174
 175 private:
 176   std::vector<B> d_buckets;
 177   std::string d_name;
 178   mutable SumType d_sum{0};
 179
 180   std::vector<uint64_t> to125(uint64_t start, int num)
 181   {
 182     std::vector<uint64_t> boundaries;
 183     boundaries.reserve(num);
 184     boundaries.emplace_back(start);
 185     int i = 0;
 186     while (true) {
 187       if (++i >= num) {
 188         break;
 189       }
 190       boundaries.push_back(2 * start);
 191       if (++i >= num) {
 192         break;
 193       }
 194       boundaries.push_back(5 * start);
 195       if (++i >= num) {
 196         break;
 197       }
 198       boundaries.push_back(10 * start);
 199       start *= 10;
 200     }
 201     return boundaries;
 202   }
 203 };
 204
 205 using Histogram = BaseHistogram<Bucket, uint64_t>;
 206
 207 using AtomicHistogram = BaseHistogram<AtomicBucket, pdns::stat_t>;
 208
 209 } // namespace pdns