IndexedMemPoolTest.cpp File Reference

#include <folly/IndexedMemPool.h>
#include <folly/portability/GMock.h>
#include <folly/portability/GTest.h>
#include <folly/portability/Semaphore.h>
#include <folly/portability/Unistd.h>
#include <folly/test/DeterministicSchedule.h>
#include <string>
#include <thread>

Go to the source code of this file.

Classes
struct	NonTrivialStruct
struct	MockTraits
struct	MockTraits::Forwarder

Typedefs
using	TraitsTestPool = IndexedMemPool< std::string, 1, 1, std::atomic, MockTraits::Forwarder >
using	IncompleteTestPool = IndexedMemPool< IncompleteTestElement >

Functions
	TEST (IndexedMemPool, unique_ptr)
	TEST (IndexedMemPool, no_starvation)
	TEST (IndexedMemPool, st_capacity)
	TEST (IndexedMemPool, mt_capacity)
	TEST (IndexedMemPool, locate_elem)
	TEST (IndexedMemPool, eager_recycle)
	TEST (IndexedMemPool, late_recycle)
	TEST (IndexedMemPool, no_data_races)
	TEST (IndexedMemPool, construction_destruction)
void	testTraits (TraitsTestPool &pool)
	TEST (IndexedMemPool, use_traits_empty)
	TEST (IndexedMemPool, use_traits_local_list)
	TEST (IndexedMemPool, use_traits_global_list)

Variables
std::atomic< int >	cnum {0}
std::atomic< int >	dnum {0}

Typedef Documentation

using IncompleteTestPool = IndexedMemPool<IncompleteTestElement>

Definition at line 400 of file IndexedMemPoolTest.cpp.

using TraitsTestPool = IndexedMemPool<std::string, 1, 1, std::atomic, MockTraits::Forwarder>

Definition at line 347 of file IndexedMemPoolTest.cpp.

Function Documentation

TEST	(	IndexedMemPool	,
		unique_ptr
	)

Definition at line 31 of file IndexedMemPoolTest.cpp.

References EXPECT_LT, EXPECT_TRUE, i, folly::gen::move, and ptr.

                                 {
  typedef IndexedMemPool<size_t> Pool;
  Pool pool(100);

  for (size_t i = 0; i < 100000; ++i) {
    auto ptr = pool.allocElem();
    EXPECT_TRUE(!!ptr);
    *ptr = i;
  }

  std::vector<Pool::UniquePtr> leak;
  while (true) {
    auto ptr = pool.allocElem();
    if (!ptr) {
      // good, we finally ran out
      break;
    }
    leak.emplace_back(std::move(ptr));
    EXPECT_LT(leak.size(), 10000u);
  }
}

TEST	(	IndexedMemPool	,
		no_starvation
	)

Definition at line 53 of file IndexedMemPoolTest.cpp.

References folly::netops::close(), count, EXPECT_EQ, EXPECT_GE, EXPECT_LE, EXPECT_NE, i, join, pipe(), fizz::detail::read(), uint32_t, folly::detail::distributed_mutex::wait(), and fizz::detail::write().

                                    {
  const int count = 1000;
  const uint32_t poolSize = 100;

  typedef DeterministicSchedule Sched;
  Sched sched(Sched::uniform(0));

  typedef IndexedMemPool<int, 8, 8, DeterministicAtomic> Pool;
  Pool pool(poolSize);

  for (auto pass = 0; pass < 10; ++pass) {
    int fd[2];
    EXPECT_EQ(pipe(fd), 0);

    // makes sure we wait for available nodes, rather than fail allocIndex
    sem_t allocSem;
    sem_init(&allocSem, 0, poolSize);

    // this semaphore is only needed for deterministic replay, so that we
    // always block in an Sched:: operation rather than in a read() syscall
    sem_t readSem;
    sem_init(&readSem, 0, 0);

    std::thread produce = Sched::thread([&]() {
      for (auto i = 0; i < count; ++i) {
        Sched::wait(&allocSem);
        uint32_t idx = pool.allocIndex();
        EXPECT_NE(idx, 0u);
        EXPECT_LE(
            idx, poolSize + (pool.NumLocalLists - 1) * pool.LocalListLimit);
        pool[idx] = i;
        EXPECT_EQ(write(fd[1], &idx, sizeof(idx)), sizeof(idx));
        Sched::post(&readSem);
      }
    });

    std::thread consume = Sched::thread([&]() {
      for (auto i = 0; i < count; ++i) {
        uint32_t idx;
        Sched::wait(&readSem);
        EXPECT_EQ(read(fd[0], &idx, sizeof(idx)), sizeof(idx));
        EXPECT_NE(idx, 0);
        EXPECT_GE(idx, 1u);
        EXPECT_LE(
            idx, poolSize + (Pool::NumLocalLists - 1) * Pool::LocalListLimit);
        EXPECT_EQ(pool[idx], i);
        pool.recycleIndex(idx);
        Sched::post(&allocSem);
      }
    });

    Sched::join(produce);
    Sched::join(consume);
    close(fd[0]);
    close(fd[1]);
  }
}

TEST	(	IndexedMemPool	,
		st_capacity
	)

Definition at line 111 of file IndexedMemPoolTest.cpp.

References EXPECT_EQ, EXPECT_NE, and i.

                                  {
  // only one local list => capacity is exact
  typedef IndexedMemPool<int, 1, 32> Pool;
  Pool pool(10);

  EXPECT_EQ(pool.capacity(), 10u);
  EXPECT_EQ(Pool::maxIndexForCapacity(10), 10u);
  for (auto i = 0; i < 10; ++i) {
    EXPECT_NE(pool.allocIndex(), 0u);
  }
  EXPECT_EQ(pool.allocIndex(), 0u);
}

TEST	(	IndexedMemPool	,
		mt_capacity
	)

Definition at line 124 of file IndexedMemPoolTest.cpp.

References EXPECT_EQ, EXPECT_NE, i, threads, and uint32_t.

                                  {
  typedef IndexedMemPool<int, 16, 32> Pool;
  Pool pool(1000);

  std::thread threads[10];
  for (auto i = 0; i < 10; ++i) {
    threads[i] = std::thread([&]() {
      for (auto j = 0; j < 100; ++j) {
        uint32_t idx = pool.allocIndex();
        EXPECT_NE(idx, 0u);
      }
    });
  }

  for (auto i = 0; i < 10; ++i) {
    threads[i].join();
  }

  for (auto i = 0; i < 16 * 32; ++i) {
    pool.allocIndex();
  }
  EXPECT_EQ(pool.allocIndex(), 0u);
}

TEST	(	IndexedMemPool	,
		locate_elem
	)

Definition at line 148 of file IndexedMemPoolTest.cpp.

References folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocIndex(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::locateElem().

                                  {
  IndexedMemPool<int> pool(1000);

  for (auto i = 0; i < 1000; ++i) {
    auto idx = pool.allocIndex();
    EXPECT_FALSE(idx == 0);
    int* elem = &pool[idx];
    EXPECT_TRUE(idx == pool.locateElem(elem));
  }

  EXPECT_EQ(pool.locateElem(nullptr), 0);
}

TEST	(	IndexedMemPool	,
		eager_recycle
	)

Definition at line 183 of file IndexedMemPoolTest.cpp.

References NonTrivialStruct::count, EXPECT_EQ, EXPECT_TRUE, i, folly::gen::move, ptr, and string.

                                    {
  typedef IndexedMemPool<NonTrivialStruct> Pool;
  Pool pool(100);

  EXPECT_EQ(NonTrivialStruct::count, 0);

  for (size_t i = 0; i < 10; ++i) {
    {
      std::unique_ptr<std::string> arg{new std::string{"abc"}};
      auto ptr = pool.allocElem(std::move(arg), 100);
      EXPECT_EQ(NonTrivialStruct::count, 1);
      EXPECT_EQ(ptr->elem_, 103);
      EXPECT_TRUE(!!ptr);
    }
    EXPECT_EQ(NonTrivialStruct::count, 0);
  }
}

TEST	(	IndexedMemPool	,
		late_recycle
	)

Definition at line 201 of file IndexedMemPoolTest.cpp.

References NonTrivialStruct::count, EXPECT_EQ, EXPECT_TRUE, i, and ptr.

                                   {
  {
    using Pool = IndexedMemPool<
        NonTrivialStruct,
        8,
        8,
        std::atomic,
        IndexedMemPoolTraitsLazyRecycle<NonTrivialStruct>>;
    Pool pool(100);

    EXPECT_EQ(NonTrivialStruct::count, 0);

    for (size_t i = 0; i < 10; ++i) {
      {
        auto ptr = pool.allocElem();
        EXPECT_TRUE(NonTrivialStruct::count > 0);
        EXPECT_TRUE(!!ptr);
        ptr->elem_ = i;
      }
      EXPECT_TRUE(NonTrivialStruct::count > 0);
    }
  }
  EXPECT_EQ(NonTrivialStruct::count, 0);
}

TEST	(	IndexedMemPool	,
		no_data_races
	)

Definition at line 226 of file IndexedMemPoolTest.cpp.

References count, EXPECT_LE, EXPECT_NE, i, nthreads, folly::pushmi::detail::t, and uint32_t.

                                    {
  const int count = 1000;
  const uint32_t poolSize = 100;
  const int nthreads = 10;

  using Pool = IndexedMemPool<int, 8, 8>;
  Pool pool(poolSize);

  std::vector<std::thread> thr(nthreads);
  for (auto i = 0; i < nthreads; ++i) {
    thr[i] = std::thread([&]() {
      for (auto j = 0; j < count; ++j) {
        uint32_t idx = pool.allocIndex();
        EXPECT_NE(idx, 0u);
        EXPECT_LE(
            idx, poolSize + (pool.NumLocalLists - 1) * pool.LocalListLimit);
        pool[idx] = j;
        pool.recycleIndex(idx);
      }
    });
  }
  for (auto& t : thr) {
    t.join();
  }
}

TEST	(	IndexedMemPool	,
		construction_destruction
	)

Definition at line 255 of file IndexedMemPoolTest.cpp.

References cnum, count, dnum, i, nthreads, start, folly::pushmi::detail::t, and uint32_t.

                                               {
  struct Foo {
    Foo() {
      cnum.fetch_add(1);
    }
    ~Foo() {
      dnum.fetch_add(1);
    }
  };

  std::atomic<bool> start{false};
  std::atomic<int> started{0};

  using Pool = IndexedMemPool<
      Foo,
      1,
      1,
      std::atomic,
      IndexedMemPoolTraitsLazyRecycle<Foo>>;
  int nthreads = 20;
  int count = 1000;

  {
    Pool pool(2);
    std::vector<std::thread> thr(nthreads);
    for (auto i = 0; i < nthreads; ++i) {
      thr[i] = std::thread([&]() {
        started.fetch_add(1);
        while (!start.load()) {
          ;
        }
        for (auto j = 0; j < count; ++j) {
          uint32_t idx = pool.allocIndex();
          if (idx != 0) {
            pool.recycleIndex(idx);
          }
        }
      });
    }

    while (started.load() < nthreads) {
      ;
    }
    start.store(true);

    for (auto& t : thr) {
      t.join();
    }
  }

  CHECK_EQ(cnum.load(), dnum.load());
}

TEST	(	IndexedMemPool	,
		use_traits_empty
	)

Definition at line 370 of file IndexedMemPoolTest.cpp.

References testTraits().

                                       {
  TraitsTestPool pool(10);
  testTraits(pool);
}

TEST	(	IndexedMemPool	,
		use_traits_local_list
	)

Definition at line 376 of file IndexedMemPoolTest.cpp.

References testing::_, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocElem(), EXPECT_CALL, and testTraits().

                                            {
  TraitsTestPool pool(10);
  MockTraits traits;
  EXPECT_CALL(traits, onAllocate(_, _));
  // Allocate and immediately recycle an element to populate the local list.
  pool.allocElem("");
  testTraits(pool);
}

TEST	(	IndexedMemPool	,
		use_traits_global_list
	)

Definition at line 386 of file IndexedMemPoolTest.cpp.

References testing::_, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocElem(), EXPECT_CALL, and testTraits().

                                             {
  TraitsTestPool pool(10);
  MockTraits traits;
  EXPECT_CALL(traits, onAllocate(_, _)).Times(2);
  auto global = pool.allocElem("");
  // Allocate and immediately recycle an element to fill the local list.
  pool.allocElem("");
  // Recycle an element to populate the global list.
  global.reset();
  testTraits(pool);
}

void testTraits

(

TraitsTestPool &

pool

)

Definition at line 349 of file IndexedMemPoolTest.cpp.

References testing::_, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocElem(), EXPECT_CALL, EXPECT_EQ, EXPECT_FALSE, testing::Invoke(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::isAllocated(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::locateElem(), ptr, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::recycleIndex(), s, and string.

Referenced by TEST().

                                      {
  MockTraits traits;
  const std::string* elem = nullptr;
  EXPECT_CALL(traits, onAllocate(_, _))
      .WillOnce(Invoke([&](std::string* s, auto) {
        EXPECT_FALSE(pool.isAllocated(pool.locateElem(s)));
        elem = s;
      }));
  std::string* ptr = pool.allocElem("foo").release();
  EXPECT_EQ(ptr, elem);

  elem = nullptr;
  EXPECT_CALL(traits, onRecycle(_)).WillOnce(Invoke([&](std::string* s) {
    EXPECT_FALSE(pool.isAllocated(pool.locateElem(s)));
    elem = s;
  }));
  pool.recycleIndex(pool.locateElem(ptr));
  EXPECT_EQ(ptr, elem);
}

Variable Documentation

std::atomic<int> cnum {0}

Definition at line 252 of file IndexedMemPoolTest.cpp.

Referenced by TEST().

std::atomic<int> dnum {0}

Definition at line 253 of file IndexedMemPoolTest.cpp.

Referenced by TEST().