ceph/src/seastar/tests/unit/chunked_fifo_test.cc

   1 /*
   2  * This file is open source software, licensed to you under the terms
   3  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   4  * distributed with this work for additional information regarding copyright
   5  * ownership.  You may not use this file except in compliance with the License.
   6  *
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing,
  12  * software distributed under the License is distributed on an
  13  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14  * KIND, either express or implied.  See the License for the
  15  * specific language governing permissions and limitations
  16  * under the License.
  17  */
  18 /*
  19  * Copyright (C) 2016 ScyllaDB Ltd.
  20  */
  21
  22
  23 #define BOOST_TEST_MODULE core
  24
  25 #include <boost/test/included/unit_test.hpp>
  26 #include <seastar/core/chunked_fifo.hh>
  27 #include <stdlib.h>
  28 #include <chrono>
  29 #include <deque>
  30 #include <seastar/core/circular_buffer.hh>
  31
  32 using namespace seastar;
  33
  34 BOOST_AUTO_TEST_CASE(chunked_fifo_small) {
  35     // Check all the methods of chunked_fifo but with a trivial type (int) and
  36     // only a few elements - and in particular a single chunk is enough.
  37     chunked_fifo<int> fifo;
  38     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
  39     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
  40     fifo.push_back(3);
  41     BOOST_REQUIRE_EQUAL(fifo.size(), 1u);
  42     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
  43     BOOST_REQUIRE_EQUAL(fifo.front(), 3);
  44     fifo.push_back(17);
  45     BOOST_REQUIRE_EQUAL(fifo.size(), 2u);
  46     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
  47     BOOST_REQUIRE_EQUAL(fifo.front(), 3);
  48     fifo.pop_front();
  49     BOOST_REQUIRE_EQUAL(fifo.size(), 1u);
  50     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
  51     BOOST_REQUIRE_EQUAL(fifo.front(), 17);
  52     fifo.pop_front();
  53     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
  54     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
  55     // The previously allocated chunk should have been freed, and now
  56     // a new one will need to be allocated:
  57     fifo.push_back(57);
  58     BOOST_REQUIRE_EQUAL(fifo.size(), 1u);
  59     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
  60     BOOST_REQUIRE_EQUAL(fifo.front(), 57);
  61     // check miscelleneous methods (at least they shouldn't crash)
  62     fifo.clear();
  63     fifo.shrink_to_fit();
  64     fifo.reserve(1);
  65     fifo.reserve(100);
  66     fifo.reserve(1280);
  67     fifo.shrink_to_fit();
  68     fifo.reserve(1280);
  69 }
  70
  71 BOOST_AUTO_TEST_CASE(chunked_fifo_fullchunk) {
  72     // Grow a chunked_fifo to exactly fill a chunk, and see what happens when
  73     // we cross that chunk.
  74     constexpr size_t N = 128;
  75     chunked_fifo<int, N> fifo;
  76     for (int i = 0; i < static_cast<int>(N); i++) {
  77         fifo.push_back(i);
  78     }
  79     BOOST_REQUIRE_EQUAL(fifo.size(), N);
  80     fifo.push_back(N);
  81     BOOST_REQUIRE_EQUAL(fifo.size(), N+1);
  82     for (int i = 0 ; i < static_cast<int>(N+1); i++) {
  83         BOOST_REQUIRE_EQUAL(fifo.front(), i);
  84         BOOST_REQUIRE_EQUAL(fifo.size(), N+1-i);
  85         fifo.pop_front();
  86     }
  87     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
  88     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
  89 }
  90
  91 BOOST_AUTO_TEST_CASE(chunked_fifo_big) {
  92     // Grow a chunked_fifo to many elements, and see things are working as
  93     // expected
  94     chunked_fifo<int> fifo;
  95     constexpr size_t N = 100'000;
  96     for (int i=0; i < static_cast<int>(N); i++) {
  97         fifo.push_back(i);
  98     }
  99     BOOST_REQUIRE_EQUAL(fifo.size(), N);
 100     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
 101     for (int i = 0 ; i < static_cast<int>(N); i++) {
 102         BOOST_REQUIRE_EQUAL(fifo.front(), i);
 103         BOOST_REQUIRE_EQUAL(fifo.size(), N-i);
 104         fifo.pop_front();
 105     }
 106     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 107     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 108 }
 109
 110 BOOST_AUTO_TEST_CASE(chunked_fifo_constructor) {
 111     // Check that chunked_fifo appropriately calls the type's constructor
 112     // and destructor, and doesn't need anything else.
 113     struct typ {
 114         int val;
 115         unsigned* constructed;
 116         unsigned* destructed;
 117         typ(int val, unsigned* constructed, unsigned* destructed)
 118             : val(val), constructed(constructed), destructed(destructed) {
 119                 ++*constructed;
 120         }
 121         ~typ() { ++*destructed; }
 122     };
 123     chunked_fifo<typ> fifo;
 124     unsigned constructed = 0, destructed = 0;
 125     constexpr unsigned N = 1000;
 126     for (unsigned i = 0; i < N; i++) {
 127         fifo.emplace_back(i, &constructed, &destructed);
 128     }
 129     BOOST_REQUIRE_EQUAL(fifo.size(), N);
 130     BOOST_REQUIRE_EQUAL(constructed, N);
 131     BOOST_REQUIRE_EQUAL(destructed, 0u);
 132     for (unsigned i = 0 ; i < N; i++) {
 133         BOOST_REQUIRE_EQUAL(fifo.front().val, static_cast<int>(i));
 134         BOOST_REQUIRE_EQUAL(fifo.size(), N-i);
 135         fifo.pop_front();
 136         BOOST_REQUIRE_EQUAL(destructed, i+1);
 137     }
 138     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 139     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 140     // Check that destructing a fifo also destructs the objects it still
 141     // contains
 142     constructed = destructed = 0;
 143     {
 144         chunked_fifo<typ> fifo;
 145         for (unsigned i = 0; i < N; i++) {
 146             fifo.emplace_back(i, &constructed, &destructed);
 147             BOOST_REQUIRE_EQUAL(fifo.front().val, 0);
 148             BOOST_REQUIRE_EQUAL(fifo.size(), i+1);
 149             BOOST_REQUIRE_EQUAL(fifo.empty(), false);
 150             BOOST_REQUIRE_EQUAL(constructed, i+1);
 151             BOOST_REQUIRE_EQUAL(destructed, 0u);
 152         }
 153     }
 154     BOOST_REQUIRE_EQUAL(constructed, N);
 155     BOOST_REQUIRE_EQUAL(destructed, N);
 156 }
 157
 158 BOOST_AUTO_TEST_CASE(chunked_fifo_construct_fail) {
 159     // Check that if we fail to construct the item pushed, the queue remains
 160     // empty.
 161     class my_exception {};
 162     struct typ {
 163         typ() {
 164             throw my_exception();
 165         }
 166     };
 167     chunked_fifo<typ> fifo;
 168     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 169     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 170     try {
 171         fifo.emplace_back();
 172     } catch(my_exception) {
 173         // expected, ignore
 174     }
 175     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 176     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 177 }
 178
 179 BOOST_AUTO_TEST_CASE(chunked_fifo_construct_fail2) {
 180     // A slightly more elaborate test, with a chunk size of 2
 181     // items, and the third addition failing, so the question is
 182     // not whether empty() is wrong immediately, but whether after
 183     // we pop the two items, it will become true or we'll be left
 184     // with an empty chunk.
 185     class my_exception {};
 186     struct typ {
 187         typ(bool fail) {
 188             if (fail) {
 189                 throw my_exception();
 190             }
 191         }
 192     };
 193     chunked_fifo<typ, 2> fifo;
 194     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 195     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 196     fifo.emplace_back(false);
 197     fifo.emplace_back(false);
 198     try {
 199         fifo.emplace_back(true);
 200     } catch(my_exception) {
 201         // expected, ignore
 202     }
 203     BOOST_REQUIRE_EQUAL(fifo.size(), 2u);
 204     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
 205     fifo.pop_front();
 206     BOOST_REQUIRE_EQUAL(fifo.size(), 1u);
 207     BOOST_REQUIRE_EQUAL(fifo.empty(), false);
 208     fifo.pop_front();
 209     BOOST_REQUIRE_EQUAL(fifo.size(), 0u);
 210     BOOST_REQUIRE_EQUAL(fifo.empty(), true);
 211 }
 212
 213 // Enable the following to run some benchmarks on different queue options
 214 #if 0
 215 // Unfortunately, C++ lacks the trivial feature of converting a type's name,
 216 // in compile time, to a string (akin to the C preprocessor's "#" feature).
 217 // Here is a neat trick to replace it - use typeinfo<T>::name() or
 218 // type_name<T>() to get a constant string name of the type.
 219 #include <cxxabi.h>
 220 template <typename T>
 221 class typeinfo {
 222 private:
 223     static const char *_name;
 224 public:
 225     static const char *name() {
 226         int status;
 227         if (!_name)
 228             _name = abi::__cxa_demangle(typeid(T).name(), 0, 0, &status);
 229         return _name;
 230     }
 231 };
 232 template<typename T> const char *typeinfo<T>::_name = nullptr;
 233 template<typename T> const char *type_name() {
 234     return typeinfo<T>::name();
 235 }
 236
 237
 238 template<typename FIFO_TYPE> void
 239 benchmark_random_push_pop() {
 240     // A test involving a random sequence of pushes and pops. Because the
 241     // random walk is bounded the 0 end (the queue cannot be popped after
 242     // being empty), the queue's expected length at the end of the test is
 243     // not zero.
 244     // The test uses the same random sequence each time so can be used for
 245     // benchmarking different queue implementations on the same sequence.
 246     constexpr int N = 1'000'000'000;
 247     FIFO_TYPE fifo;
 248     unsigned int seed = 0;
 249     int entropy = 0;
 250     auto start = std::chrono::high_resolution_clock::now();
 251     for (int i = 0; i < N; i++) {
 252         if (!entropy) {
 253             entropy = rand_r(&seed);
 254         }
 255         if (entropy & 1) {
 256             fifo.push_back(i);
 257         } else {
 258             if (!fifo.empty()) {
 259                 fifo.pop_front();
 260             }
 261         }
 262         entropy >>= 1;
 263     }
 264     auto end = std::chrono::high_resolution_clock::now();
 265     auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
 266     std::cerr << type_name<FIFO_TYPE>() << ", " << N << " random push-and-pop " << fifo.size() << " " << ms << "ms.\n";
 267 }
 268
 269 template<typename FIFO_TYPE> void
 270 benchmark_push_pop() {
 271     // A benchmark involving repeated push and then pop to a queue, which
 272     // will have 0 or 1 items at all times.
 273     constexpr int N = 1'000'000'000;
 274     FIFO_TYPE fifo;
 275     auto start = std::chrono::high_resolution_clock::now();
 276     for (int i = 0; i < N; i++) {
 277         fifo.push_back(1);
 278         fifo.pop_front();
 279     }
 280     auto end = std::chrono::high_resolution_clock::now();
 281     auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
 282     std::cerr << type_name<FIFO_TYPE>() << ", " << N << " push-and-pop " << ms << "ms.\n";
 283 }
 284
 285 template<typename FIFO_TYPE> void
 286 benchmark_push_pop_k() {
 287     // A benchmark involving repeated pushes of a few items and then popping
 288     // to a queue, which will have just one chunk (or 0) at all times.
 289     constexpr int N = 1'000'000'000;
 290     constexpr int K = 100;
 291     FIFO_TYPE fifo;
 292     auto start = std::chrono::high_resolution_clock::now();
 293     for (int i = 0; i < N/K; i++) {
 294         for(int j = 0; j < K; j++) {
 295             fifo.push_back(j);
 296         }
 297         for(int j = 0; j < K; j++) {
 298             fifo.pop_front();
 299         }
 300     }
 301     auto end = std::chrono::high_resolution_clock::now();
 302     auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
 303     std::cerr << type_name<FIFO_TYPE>() << ", " << N << " push-and-pop-" << K << " " << ms << "ms.\n";
 304 }
 305
 306 template<typename FIFO_TYPE> void
 307 benchmark_pushes_pops() {
 308     // A benchmark of pushing a lot of items, and then popping all of them
 309     constexpr int N = 100'000'000;
 310     FIFO_TYPE fifo;
 311     auto start = std::chrono::high_resolution_clock::now();
 312     for (int i = 0; i < N; i++) {
 313         fifo.push_back(1);
 314     }
 315     for (int i = 0; i < N; i++) {
 316         fifo.pop_front();
 317     }
 318     auto end = std::chrono::high_resolution_clock::now();
 319     auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
 320     std::cerr << type_name<FIFO_TYPE>() << ", " << N << " push-all-then-pop-all " << ms << "ms.\n";
 321 }
 322
 323 template<typename FIFO_TYPE> void
 324 benchmark_all() {
 325     std::cerr << "\n  --- " << type_name<FIFO_TYPE>() << ": \n";
 326     benchmark_random_push_pop<FIFO_TYPE>();
 327     benchmark_push_pop<FIFO_TYPE>();
 328     benchmark_push_pop_k<FIFO_TYPE>();
 329     benchmark_pushes_pops<FIFO_TYPE>();
 330 }
 331
 332 BOOST_AUTO_TEST_CASE(chunked_fifo_benchmark) {
 333     benchmark_all<chunked_fifo<int>>();
 334     benchmark_all<circular_buffer<int>>();
 335     benchmark_all<std::deque<int>>();
 336     benchmark_all<std::list<int>>();
 337 }
 338 #endif
 339
 340 BOOST_AUTO_TEST_CASE(chunked_fifo_iterator) {
 341     constexpr auto items_per_chunk = 8;
 342     auto fifo = chunked_fifo<int, items_per_chunk>{};
 343     auto reference = std::deque<int>{};
 344
 345     BOOST_REQUIRE(fifo.begin() == fifo.end());
 346
 347     for (int i = 0; i < items_per_chunk * 4; ++i) {
 348         fifo.push_back(i);
 349         reference.push_back(i);
 350         BOOST_REQUIRE(std::equal(fifo.begin(), fifo.end(), reference.begin(), reference.end()));
 351     }
 352
 353     for (int i = 0; i < items_per_chunk * 2; ++i) {
 354         fifo.pop_front();
 355         reference.pop_front();
 356         BOOST_REQUIRE(std::equal(fifo.begin(), fifo.end(), reference.begin(), reference.end()));
 357     }
 358 }
 359
 360 BOOST_AUTO_TEST_CASE(chunked_fifo_const_iterator) {
 361     constexpr auto items_per_chunk = 8;
 362     auto fifo = chunked_fifo<int, items_per_chunk>{};
 363     auto reference = std::deque<int>{};
 364
 365     BOOST_REQUIRE(fifo.cbegin() == fifo.cend());
 366
 367     for (int i = 0; i < items_per_chunk * 4; ++i) {
 368         fifo.push_back(i);
 369         reference.push_back(i);
 370         BOOST_REQUIRE(std::equal(fifo.cbegin(), fifo.cend(), reference.cbegin(), reference.cend()));
 371     }
 372
 373     for (int i = 0; i < items_per_chunk * 2; ++i) {
 374         fifo.pop_front();
 375         reference.pop_front();
 376         BOOST_REQUIRE(std::equal(fifo.cbegin(), fifo.cend(), reference.cbegin(), reference.cend()));
 377     }
 378 }