From fb4152aeab06d037bc2004329b0027ae7cef3a4c Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Thu, 23 Jan 2014 18:09:43 -0800 Subject: [PATCH] histogram: move to common, add unit tests Signed-off-by: Sage Weil --- src/common/Makefile.am | 2 + src/common/TrackedOp.h | 2 +- src/common/histogram.cc | 50 +++++++++++++++ src/{include => common}/histogram.h | 26 ++++++-- src/include/Makefile.am | 1 - src/mon/PGMonitor.h | 2 +- src/osd/osd_types.cc | 34 ----------- src/osd/osd_types.h | 2 +- src/test/Makefile.am | 5 ++ src/test/common/histogram.cc | 95 +++++++++++++++++++++++++++++ src/test/encoding/types.h | 2 +- 11 files changed, 177 insertions(+), 44 deletions(-) create mode 100644 src/common/histogram.cc rename src/{include => common}/histogram.h (87%) create mode 100644 src/test/common/histogram.cc diff --git a/src/common/Makefile.am b/src/common/Makefile.am index ec1f31e24ae41..b8ce83be9efa0 100644 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -40,6 +40,7 @@ libcommon_la_SOURCES = \ common/buffer.cc \ common/code_environment.cc \ common/dout.cc \ + common/histogram.cc \ common/signal.cc \ common/simple_spin.cc \ common/Thread.cc \ @@ -141,6 +142,7 @@ noinst_HEADERS += \ common/fd.h \ common/version.h \ common/hex.h \ + common/histogram.h \ common/entity_name.h \ common/errno.h \ common/environment.h \ diff --git a/src/common/TrackedOp.h b/src/common/TrackedOp.h index 97c657424e8b8..4673c1b80f4f8 100644 --- a/src/common/TrackedOp.h +++ b/src/common/TrackedOp.h @@ -17,7 +17,7 @@ #include #include #include "common/Mutex.h" -#include "include/histogram.h" +#include "common/histogram.h" #include "include/xlist.h" #include "msg/Message.h" #include "include/memory.h" diff --git a/src/common/histogram.cc b/src/common/histogram.cc new file mode 100644 index 0000000000000..a9431d93e136e --- /dev/null +++ b/src/common/histogram.cc @@ -0,0 +1,50 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Ceph - scalable distributed file system + * + * Copyright (C) 2011 New Dream Network + * + * This is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License version 2.1, as published by the Free Software + * Foundation. See file COPYING. + * + */ + +#include "common/histogram.h" +#include "common/Formatter.h" + +// -- pow2_hist_t -- +void pow2_hist_t::dump(Formatter *f) const +{ + f->open_array_section("histogram"); + for (std::vector::const_iterator p = h.begin(); p != h.end(); ++p) + f->dump_int("count", *p); + f->close_section(); + f->dump_int("upper_bound", upper_bound()); +} + +void pow2_hist_t::encode(bufferlist& bl) const +{ + ENCODE_START(1, 1, bl); + ::encode(h, bl); + ENCODE_FINISH(bl); +} + +void pow2_hist_t::decode(bufferlist::iterator& p) +{ + DECODE_START(1, p); + ::decode(h, p); + DECODE_FINISH(p); +} + +void pow2_hist_t::generate_test_instances(std::list& ls) +{ + ls.push_back(new pow2_hist_t); + ls.push_back(new pow2_hist_t); + ls.back()->h.push_back(1); + ls.back()->h.push_back(3); + ls.back()->h.push_back(0); + ls.back()->h.push_back(2); +} diff --git a/src/include/histogram.h b/src/common/histogram.h similarity index 87% rename from src/include/histogram.h rename to src/common/histogram.h index 5feebfc1e757f..1497bc988461d 100644 --- a/src/include/histogram.h +++ b/src/common/histogram.h @@ -10,8 +10,17 @@ * Copyright 2013 Inktank */ -#ifndef HISTOGRAM_H_ -#define HISTOGRAM_H_ +#ifndef CEPH_HISTOGRAM_H +#define CEPH_HISTOGRAM_H + +#include +#include + +#include "include/encoding.h" + +namespace ceph { + class Formatter; +} /** * power of 2 histogram @@ -23,7 +32,7 @@ struct pow2_hist_t { // * bin size is 2^index * value is count of elements that are <= the current bin but > the previous bin. */ - vector h; + std::vector h; private: /// expand to at least another's size @@ -49,6 +58,13 @@ public: _contract(); } + void add(int32_t v) { + int bin = calc_bits_of(v); + _expand_to(bin + 1); + h[bin]++; + _contract(); + } + static int calc_bits_of(int t) { int b = 0; while (t > 0) { @@ -68,7 +84,7 @@ public: /// @param upper [out] pointer to the upper bound (0..1000000) int get_position_micro(int32_t v, unsigned *lower, unsigned *upper) { if (v < 0) - return -ERANGE; + return -1; unsigned bin = calc_bits_of(v); unsigned lower_sum = 0, upper_sum = 0, total = 0; for (unsigned i=0; i& o) o.push_back(new request_redirect_t(loc)); } -// -- pow2_hist_t -- -void pow2_hist_t::dump(Formatter *f) const -{ - f->open_array_section("histogram"); - for (vector::const_iterator p = h.begin(); p != h.end(); ++p) - f->dump_int("count", *p); - f->close_section(); - f->dump_int("upper_bound", upper_bound()); -} - -void pow2_hist_t::encode(bufferlist& bl) const -{ - ENCODE_START(1, 1, bl); - ::encode(h, bl); - ENCODE_FINISH(bl); -} - -void pow2_hist_t::decode(bufferlist::iterator& p) -{ - DECODE_START(1, p); - ::decode(h, p); - DECODE_FINISH(p); -} - -void pow2_hist_t::generate_test_instances(list& ls) -{ - ls.push_back(new pow2_hist_t); - ls.push_back(new pow2_hist_t); - ls.back()->h.push_back(1); - ls.back()->h.push_back(3); - ls.back()->h.push_back(0); - ls.back()->h.push_back(2); -} - void objectstore_perf_stat_t::dump(Formatter *f) const { f->dump_unsigned("commit_latency_ms", filestore_commit_latency); diff --git a/src/osd/osd_types.h b/src/osd/osd_types.h index d253dd2e49ad7..416535953907e 100644 --- a/src/osd/osd_types.h +++ b/src/osd/osd_types.h @@ -27,7 +27,7 @@ #include "include/types.h" #include "include/utime.h" #include "include/CompatSet.h" -#include "include/histogram.h" +#include "common/histogram.h" #include "include/interval_set.h" #include "common/Formatter.h" #include "common/bloom_filter.hpp" diff --git a/src/test/Makefile.am b/src/test/Makefile.am index 7af43bbd20c05..a5d47597d1c3d 100644 --- a/src/test/Makefile.am +++ b/src/test/Makefile.am @@ -271,6 +271,11 @@ unittest_bloom_filter_CXXFLAGS = $(UNITTEST_CXXFLAGS) unittest_bloom_filter_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) check_PROGRAMS += unittest_bloom_filter +unittest_histogram_SOURCES = test/common/histogram.cc +unittest_histogram_CXXFLAGS = $(UNITTEST_CXXFLAGS) +unittest_histogram_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) +check_PROGRAMS += unittest_histogram + unittest_str_map_SOURCES = test/common/test_str_map.cc unittest_str_map_CXXFLAGS = $(UNITTEST_CXXFLAGS) unittest_str_map_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) diff --git a/src/test/common/histogram.cc b/src/test/common/histogram.cc new file mode 100644 index 0000000000000..c07d6c26dba29 --- /dev/null +++ b/src/test/common/histogram.cc @@ -0,0 +1,95 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Ceph - scalable distributed file system + * + * Copyright (C) 2014 Inktank + * + * LGPL2.1 (see COPYING-LGPL2.1) or later + */ + +#include +#include + +#include "common/histogram.h" +#include "include/stringify.h" + +TEST(Histogram, Basic) { + pow2_hist_t h; + + h.add(0); + h.add(0); + h.add(0); + ASSERT_EQ(3, h.h[0]); + ASSERT_EQ(1u, h.h.size()); + + h.add(1); + ASSERT_EQ(3, h.h[0]); + ASSERT_EQ(1, h.h[1]); + ASSERT_EQ(2u, h.h.size()); + + h.add(2); + h.add(2); + ASSERT_EQ(3, h.h[0]); + ASSERT_EQ(1, h.h[1]); + ASSERT_EQ(2, h.h[2]); + ASSERT_EQ(3u, h.h.size()); +} + +TEST(Histogram, Set) { + pow2_hist_t h; + h.set_bin(0, 12); + h.set_bin(2, 12); + ASSERT_EQ(12, h.h[0]); + ASSERT_EQ(0, h.h[1]); + ASSERT_EQ(12, h.h[2]); + ASSERT_EQ(3u, h.h.size()); +} + +TEST(Histogram, Position) { + { + pow2_hist_t h; + unsigned lb, ub; + h.add(0); + ASSERT_EQ(-1, h.get_position_micro(-20, &lb, &ub)); + } + { + pow2_hist_t h; + h.add(0); + unsigned lb, ub; + h.get_position_micro(0, &lb, &ub); + ASSERT_EQ(0, lb); + ASSERT_EQ(1000000, ub); + h.add(0); + h.add(0); + h.add(0); + h.get_position_micro(0, &lb, &ub); + ASSERT_EQ(0, lb); + ASSERT_EQ(1000000, ub); + } + { + pow2_hist_t h; + h.add(1); + h.add(1); + unsigned lb, ub; + h.get_position_micro(0, &lb, &ub); + ASSERT_EQ(0, lb); + ASSERT_EQ(0, ub); + h.add(0); + h.get_position_micro(0, &lb, &ub); + ASSERT_EQ(0, lb); + ASSERT_EQ(333333, ub); + h.get_position_micro(1, &lb, &ub); + ASSERT_EQ(333333, lb); + ASSERT_EQ(1000000, ub); + } + { + pow2_hist_t h; + h.add(1); + h.add(10); + unsigned lb, ub; + h.get_position_micro(4, &lb, &ub); + ASSERT_EQ(500000, lb); + ASSERT_EQ(500000, ub); + } +} diff --git a/src/test/encoding/types.h b/src/test/encoding/types.h index ce0af02d807cf..2b79bfbac072b 100644 --- a/src/test/encoding/types.h +++ b/src/test/encoding/types.h @@ -36,7 +36,7 @@ TYPEWITHSTRAYDATA(OSDMap::Incremental) #include "crush/CrushWrapper.h" TYPE_NOCOPY(CrushWrapper) -#include "include/histogram.h" +#include "common/histogram.h" TYPE(pow2_hist_t) #include "osd/osd_types.h" -- 2.39.5