"Fossies" - the Fresh Open Source Software Archive

Member "tcpflow-1.6.1/src/netviz/time_histogram.cpp" (19 Feb 2021, 7613 Bytes) of package /linux/misc/tcpflow-1.6.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "time_histogram.cpp" see the Fossies "Dox" file reference documentation.

    1 /**
    2  * time_histogram.cpp: 
    3  * organize packet count histograms of various granularities while transparently
    4  * exposing the best-fit
    5  *
    6  * This source file is public domain, as it is not based on the original tcpflow.
    7  *
    8  * Author: Michael Shick <mike@shick.in>
    9  *
   10  */
   11 
   12 #include <vector>
   13 
   14 #include "time_histogram.h"
   15 
   16 time_histogram::time_histogram() :
   17     histograms(), best_fit_index(0), earliest_ts(), latest_ts(), insert_count(0)
   18 {
   19     // zero value structs courtesy stackoverflow
   20     // http://stackoverflow.com/questions/6462093/reinitialize-timeval-struct
   21     earliest_ts = (struct timeval) { 0 };
   22     latest_ts = (struct timeval) { 0 };
   23 
   24     for(std::vector<span_params>::const_iterator it = spans.begin();
   25             it != spans.end(); it++) {
   26         histograms.push_back(histogram_map(*it));
   27     }
   28 }
   29 
   30 const float time_histogram::underflow_pad_factor = 0.1;
   31 
   32 // spans dictates the granularities of each histogram.  One histogram
   33 // will be created per entry in this vector.  Each value must have a greater
   34 // value of seconds than the previous
   35 const std::vector<time_histogram::span_params> time_histogram::spans = time_histogram::build_spans();
   36 const time_histogram::bucket time_histogram::empty_bucket; // an empty bucket
   37 const unsigned int time_histogram::F_NON_TCP = 0x01;
   38 
   39 void time_histogram::insert(const struct timeval &ts, const in_port_t port, const uint64_t count,
   40         const unsigned int flags)
   41 {
   42     insert_count += count;
   43     if(earliest_ts.tv_sec == 0 || (ts.tv_sec < earliest_ts.tv_sec ||
   44                 (ts.tv_sec == earliest_ts.tv_sec && ts.tv_usec < earliest_ts.tv_usec))) {
   45         earliest_ts = ts;
   46     }
   47     if(ts.tv_sec > latest_ts.tv_sec || (ts.tv_sec == latest_ts.tv_sec && ts.tv_usec > latest_ts.tv_usec)) {
   48         latest_ts = ts;
   49     }
   50     for(std::vector<histogram_map>::iterator it = histograms.begin() + best_fit_index;
   51             it != histograms.end(); it++) {
   52         bool overflowed = it->insert(ts, port, count, flags);
   53         // if there was an overflow and the best fit isn't already the least
   54         // granular histogram, downgrade granularity by one step
   55         if(overflowed && best_fit_index < histograms.size() - 1) {
   56             best_fit_index++;
   57         }
   58     }
   59 }
   60 
   61 // combine each bucket with (factor - 1) subsequent neighbors and increase bucket width by factor
   62 // lots of possible optimizations ignored for simplicity's sake
   63 void time_histogram::condense(double factor)
   64 {
   65     const histogram_map &original = histograms.at(best_fit_index);
   66     histogram_map condensed(span_params(original.span.usec, (uint64_t) ((double) original.span.bucket_count / factor)));
   67 
   68     for(histogram_map::buckets_t::const_iterator it = original.buckets.begin(); it != original.buckets.end(); it++) {
   69 
   70         bucket &bkt = *(it->second);
   71         uint64_t recons_usec = it->first * original.bucket_width + original.base_time;
   72 
   73         struct timeval reconstructed_ts;
   74         reconstructed_ts.tv_usec = (time_t) (recons_usec % (1000LL * 1000LL));
   75         reconstructed_ts.tv_sec = (time_t) (recons_usec / (1000LL * 1000LL));
   76 
   77         for(bucket::counts_t::const_iterator jt = bkt.counts.begin(); jt != bkt.counts.end(); jt++) {
   78             condensed.insert(reconstructed_ts, jt->first, jt->second);
   79         }
   80         condensed.insert(reconstructed_ts, 0, bkt.portless_count, F_NON_TCP);
   81     }
   82 
   83     histograms.at(best_fit_index) = condensed;
   84 }
   85 
   86 uint64_t time_histogram::usec_per_bucket() const
   87 {
   88     return histograms.at(best_fit_index).bucket_width;
   89 }
   90 
   91 uint64_t time_histogram::packet_count() const
   92 {
   93     return histograms.at(best_fit_index).insert_count;
   94 }
   95 
   96 time_t time_histogram::start_date() const
   97 {
   98     return earliest_ts.tv_sec;
   99 }
  100 
  101 time_t time_histogram::end_date() const
  102 {
  103     return latest_ts.tv_sec;
  104 }
  105 
  106 uint64_t time_histogram::tallest_bar() const
  107 {
  108     return histograms.at(best_fit_index).greatest_bucket_sum();
  109 }
  110 
  111 const time_histogram::bucket &time_histogram::at(uint32_t index) const {
  112     const histogram_map::buckets_t hgram = histograms.at(best_fit_index).buckets;
  113     histogram_map::buckets_t::const_iterator bkt = hgram.find(index);
  114     if(bkt == hgram.end()) {
  115         return empty_bucket;
  116     }
  117     return *(bkt->second);
  118 }
  119 
  120 size_t time_histogram::size() const
  121 {
  122     return histograms.at(best_fit_index).buckets.size();
  123 }
  124 
  125 // calculate the number of buckets if this were a non-sparse data structure like a vector
  126 size_t time_histogram::non_sparse_size() const
  127 {
  128     histogram_map::buckets_t buckets = histograms.at(best_fit_index).buckets;
  129     histogram_map::buckets_t::const_iterator least = buckets.begin();
  130     if(least == buckets.end()) {
  131         return 0;
  132     }
  133     histogram_map::buckets_t::const_reverse_iterator most = buckets.rbegin();
  134     return most->first - least->first + 1;
  135 }
  136 
  137 time_histogram::histogram_map::buckets_t::const_iterator time_histogram::begin() const
  138 {
  139     return histograms.at(best_fit_index).buckets.begin();
  140 }
  141 time_histogram::histogram_map::buckets_t::const_iterator time_histogram::end() const
  142 {
  143     return histograms.at(best_fit_index).buckets.end();
  144 }
  145 time_histogram::histogram_map::buckets_t::const_reverse_iterator time_histogram::rbegin() const
  146 {
  147     return histograms.at(best_fit_index).buckets.rbegin();
  148 }
  149 time_histogram::histogram_map::buckets_t::const_reverse_iterator time_histogram::rend() const
  150 {
  151     return histograms.at(best_fit_index).buckets.rend();
  152 }
  153 
  154 /* This should be rewritten, because currently it is building a bunch of spans and then returning a vector which has to be copied.
  155  * It's very inefficient.
  156  */
  157 time_histogram::span_params_vector_t time_histogram::build_spans()
  158 {
  159     span_params_vector_t output;
  160 
  161     output.push_back(span_params(
  162                 1000LL * 1000LL * 60LL, // minute
  163                 600)); // 600 0.1 second buckets
  164     output.push_back(span_params(
  165                 1000LL * 1000LL * 60LL * 60LL, // hour
  166                 3600)); // 3,600 1 second buckets
  167     output.push_back(span_params(
  168                 1000LL * 1000LL * 60LL * 60LL * 24LL, // day
  169                 1440)); // 1,440 1 minute buckets
  170     output.push_back(span_params(
  171                 1000LL * 1000LL * 60LL * 60LL * 24LL * 7LL, // week
  172                 1008)); // 1,008 10 minute buckets
  173     output.push_back(span_params(
  174                 1000LL * 1000LL * 60LL * 60LL * 24LL * 30LL, // month
  175                 720)); // 720 1 hour buckets
  176     output.push_back(span_params(
  177                 1000LL * 1000LL * 60LL * 60LL * 24LL * 30LL * 12LL, // year
  178                 360)); // 360 1 day buckets
  179     output.push_back(span_params(
  180                 1000LL * 1000LL * 60LL * 60LL * 24LL * 3598LL, // approximate decade
  181                 514)); // 514 1 week buckets
  182     output.push_back(span_params(
  183                 1000LL * 1000LL * 60LL * 60LL * 24LL * 30LL * 12LL * 50LL, // semicentury
  184                 200)); // 200 3 month intervals
  185 
  186     return output;
  187 }
  188 
  189 
  190 
  191 
  192 /*
  193  * Insert into the time_histogram.
  194  *
  195  * This is optimized to be as fast as possible, so we compute the sums as necessary when generating the histogram.
  196  */
  197 
  198 bool time_histogram::histogram_map::insert(const struct timeval &ts, const in_port_t port, const uint64_t count,
  199         const unsigned int flags)
  200 {
  201     uint32_t target_index = scale_timeval(ts);
  202 
  203     if(target_index >= span.bucket_count) {
  204         return true;                    // overflow; will cause this histogram to be shut down
  205     }
  206 
  207     buckets_t::iterator it = buckets.find(target_index);
  208     if(it==buckets.end()){
  209         buckets[target_index] = new bucket();
  210     }
  211     buckets[target_index]->increment(port, count, flags);
  212 
  213     insert_count += count;
  214 
  215     return false;
  216 }
  217 
  218