text: /**
   * Copyright (C) 2016 MongoDB Inc.
   *
   * This program is free software: you can redistribute it and/or  modify
   * it under the terms of the GNU Affero General Public License, version 3,
   * as published by the Free Software Foundation.
   *
   * 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 Affero General Public License for more details.
   *
   * You should have received a copy of the GNU Affero General Public License
   * along with this program.  If not, see <http://www.gnu.org/licenses/>.
   *
   * As a special exception, the copyright holders give permission to link the
   * code of portions of this program with the OpenSSL library under certain
   * conditions as described in each individual source file and distribute
   * linked combinations including the program with the OpenSSL library. You
   * must comply with the GNU Affero General Public License in all respects
   * for all of the code used other than as permitted herein. If you modify
   * file(s) with this exception, you may extend this exception to your
   * version of the file(s), but you are not obligated to do so. If you do not
   * wish to do so, delete this exception statement from your version. If you
   * delete this exception statement from all source files in the program,
   * then also delete it in the license file.
   */
  
  #include "mongo/platform/basic.h"
  
  #include "mongo/db/stats/operation_latency_histogram.h"
  
  #include <algorithm>
  
  #include "mongo/bson/bsonobjbuilder.h"
  #include "mongo/db/namespace_string.h"
  #include "mongo/platform/bits.h"
  
  namespace mongo {
  
  const std::array<uint64_t, OperationLatencyHistogram::kMaxBuckets>
      OperationLatencyHistogram::kLowerBounds = {0,
                                                 2,
                                                 4,
                                                 8,
                                                 16,
                                                 32,
                                                 64,
                                                 128,
                                                 256,
                                                 512,
                                                 1024,
                                                 2048,
                                                 3072,
                                                 4096,
                                                 6144,
                                                 8192,
                                                 12288,
                                                 16384,
                                                 24576,
                                                 32768,
                                                 49152,
                                                 65536,
                                                 98304,
                                                 131072,
                                                 196608,
                                                 262144,
                                                 393216,
                                                 524288,
                                                 786432,
                                                 1048576,
                                                 1572864,
                                                 2097152,
                                                 4194304,
                                                 8388608,
                                                 16777216,
                                                 33554432,
                                                 67108864,
                                                 134217728,
                                                 268435456,
                                                 536870912,
                                                 1073741824,
                                                 2147483648,
                                                 4294967296,
                                                 8589934592,
                                                 17179869184,
                                                 34359738368,
                                                 68719476736,
                                                 137438953472,
                                                 274877906944,
                                                 549755813888,
                                                 1099511627776};
  
  void OperationLatencyHistogram::_append(const HistogramData& data,
                                          const char* key,
                                          bool includeHistograms,
                                          BSONObjBuilder* builder) const {
  
      BSONObjBuilder histogramBuilder(builder->subobjStart(key));
      if (includeHistograms) {
          BSONArrayBuilder arrayBuilder(histogramBuilder.subarrayStart("histogram"));
          for (int i = 0; i < kMaxBuckets; i++) {
              if (data.buckets[i] == 0)
                  continue;
              BSONObjBuilder entryBuilder(arrayBuilder.subobjStart());
              entryBuilder.append("micros", static_cast<long long>(kLowerBounds[i]));
              entryBuilder.append("count", static_cast<long long>(data.buckets[i]));
              entryBuilder.doneFast();
          }
          arrayBuilder.doneFast();
      }
      histogramBuilder.append("latency", static_cast<long long>(data.sum));
      histogramBuilder.append("ops", static_cast<long long>(data.entryCount));
      histogramBuilder.doneFast();
  }
  
  void OperationLatencyHistogram::append(bool includeHistograms, BSONObjBuilder* builder) const {
      _append(_reads, "reads", includeHistograms, builder);
      _append(_writes, "writes", includeHistograms, builder);
      _append(_commands, "commands", includeHistograms, builder);
      _append(_transactions, "transactions", includeHistograms, builder);
  }
  
  // Computes the log base 2 of value, and checks for cases of split buckets.
  int OperationLatencyHistogram::_getBucket(uint64_t value) {
      // Zero is a special case since log(0) is undefined.
      if (value == 0) {
          return 0;
      }
  
      int log2 = 63 - countLeadingZeros64(value);
      // Half splits occur in range [2^11, 2^21) giving 10 extra buckets.
      if (log2 < 11) {
          return log2;
      } else if (log2 < 21) {
          int extra = log2 - 11;
          // Split value boundary is at (2^n + 2^(n+1))/2 = 2^n + 2^(n-1).
          // Which corresponds to (1ULL << log2) | (1ULL << (log2 - 1))
          // Which is equivalent to the following:
          uint64_t splitBoundary = 3ULL << (log2 - 1);
          if (value >= splitBoundary) {
              extra++;
          }
          return log2 + extra;
      } else {
          // Add all of the extra 10 buckets.
          return std::min(log2 + 10, kMaxBuckets - 1);
      }
  }
  
  void OperationLatencyHistogram::_incrementData(uint64_t latency, int bucket, HistogramData* data) {
      data->buckets[bucket]++;
      data->entryCount++;
      data->sum += latency;
  }
  
  void OperationLatencyHistogram::increment(uint64_t latency, Command::ReadWriteType type) {
      int bucket = _getBucket(latency);
      switch (type) {
          case Command::ReadWriteType::kRead:
              _incrementData(latency, bucket, &_reads);
              break;
          case Command::ReadWriteType::kWrite:
              _incrementData(latency, bucket, &_writes);
              break;
          case Command::ReadWriteType::kCommand:
              _incrementData(latency, bucket, &_commands);
              break;
          case Command::ReadWriteType::kTransaction:
              _incrementData(latency, bucket, &_transactions);
              break;
          default:
              MONGO_UNREACHABLE;
      }
  }
  
  }  // namespace mongo
  