ceph/src/test/common/test_intrusive_lru.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include <stdio.h>
   5 #include "gtest/gtest.h"
   6 #include "common/intrusive_lru.h"
   7
   8 template <typename TestLRUItem>
   9 struct item_to_unsigned {
  10   using type = unsigned;
  11   const type &operator()(const TestLRUItem &item) {
  12     return item.key;
  13   }
  14 };
  15
  16 struct TestLRUItem : public ceph::common::intrusive_lru_base<
  17   ceph::common::intrusive_lru_config<
  18     unsigned, TestLRUItem, item_to_unsigned<TestLRUItem>>> {
  19   unsigned key = 0;
  20   int value = 0;
  21
  22   TestLRUItem(unsigned key) : key(key) {}
  23 };
  24
  25 class LRUTest : public TestLRUItem::lru_t {
  26 public:
  27   auto add(unsigned int key, int value) {
  28     auto [ref, key_existed] = get_or_create(key);
  29     if (!key_existed) {
  30       ref->value = value;
  31     }
  32     return std::pair(ref, key_existed);
  33   }
  34 };
  35
  36 TEST(LRU, add_immediate_evict) {
  37   LRUTest cache;
  38   unsigned int key = 1;
  39   int value1 = 2;
  40   int value2 = 3;
  41   {
  42     auto [ref, existed] = cache.add(key, value1);
  43     ASSERT_TRUE(ref);
  44     ASSERT_EQ(value1, ref->value);
  45     ASSERT_FALSE(existed);
  46   }
  47   {
  48     auto [ref2, existed] = cache.add(key, value2);
  49     ASSERT_EQ(value2, ref2->value);
  50     ASSERT_FALSE(existed);
  51   }
  52 }
  53
  54 TEST(LRU, lookup_lru_size) {
  55   LRUTest cache;
  56   int key = 1;
  57   int value = 1;
  58   cache.set_target_size(1);
  59   {
  60     auto [ref, existed] = cache.add(key, value);
  61     ASSERT_TRUE(ref);
  62     ASSERT_FALSE(existed);
  63   }
  64   {
  65     auto [ref, existed] = cache.add(key, value);
  66     ASSERT_TRUE(ref);
  67     ASSERT_TRUE(existed);
  68   }
  69   cache.set_target_size(0);
  70   auto [ref2, existed2] = cache.add(key, value);
  71   ASSERT_TRUE(ref2);
  72   ASSERT_FALSE(existed2);
  73   {
  74     auto [ref, existed] = cache.add(key, value);
  75     ASSERT_TRUE(ref);
  76     ASSERT_TRUE(existed);
  77   }
  78 }
  79
  80 TEST(LRU, eviction) {
  81   const unsigned SIZE = 3;
  82   LRUTest cache;
  83   cache.set_target_size(SIZE);
  84
  85   for (unsigned i = 0; i < SIZE; ++i) {
  86     auto [ref, existed] = cache.add(i, i);
  87     ASSERT_TRUE(ref && !existed);
  88   }
  89
  90   {
  91     auto [ref, existed] = cache.add(0, 0);
  92     ASSERT_TRUE(ref && existed);
  93   }
  94
  95   for (unsigned i = SIZE; i < (2*SIZE) - 1; ++i) {
  96     auto [ref, existed]  = cache.add(i, i);
  97     ASSERT_TRUE(ref && !existed);
  98   }
  99
 100   {
 101     auto [ref, existed] = cache.add(0, 0);
 102     ASSERT_TRUE(ref && existed);
 103   }
 104
 105   for (unsigned i = 1; i < SIZE; ++i) {
 106     auto [ref, existed] = cache.add(i, i);
 107     ASSERT_TRUE(ref && !existed);
 108   }
 109 }
 110
 111 TEST(LRU, eviction_live_ref) {
 112   const unsigned SIZE = 3;
 113   LRUTest cache;
 114   cache.set_target_size(SIZE);
 115
 116   auto [live_ref, existed2] = cache.add(1, 1);
 117   ASSERT_TRUE(live_ref && !existed2);
 118
 119   for (unsigned i = 0; i < SIZE; ++i) {
 120     auto [ref, existed] = cache.add(i, i);
 121     ASSERT_TRUE(ref);
 122     if (i == 1) {
 123       ASSERT_TRUE(existed);
 124     } else {
 125       ASSERT_FALSE(existed);
 126     }
 127   }
 128
 129   {
 130     auto [ref, existed] = cache.add(0, 0);
 131     ASSERT_TRUE(ref && existed);
 132   }
 133
 134   for (unsigned i = SIZE; i < (2*SIZE) - 1; ++i) {
 135     auto [ref, existed]  = cache.add(i, i);
 136     ASSERT_TRUE(ref && !existed);
 137   }
 138
 139   for (unsigned i = 0; i < SIZE; ++i) {
 140     auto [ref, existed] = cache.add(i, i);
 141     ASSERT_TRUE(ref);
 142     if (i == 1) {
 143       ASSERT_TRUE(existed);
 144     } else {
 145       ASSERT_FALSE(existed);
 146     }
 147   }
 148 }
 149
 150 TEST(LRU, clear_range) {
 151   LRUTest cache;
 152   const unsigned SIZE = 10;
 153   cache.set_target_size(SIZE);
 154   {
 155     auto [ref, existed] = cache.add(1, 4);
 156     ASSERT_FALSE(existed);
 157   }
 158   {
 159     auto [ref, existed] = cache.add(2, 4);
 160     ASSERT_FALSE(existed);
 161   }
 162   {
 163     auto [ref, existed] = cache.add(3, 4);
 164     ASSERT_FALSE(existed);
 165   }
 166   // Unlike above, the reference is not being destroyed
 167   auto [live_ref1, existed1] = cache.add(4, 4);
 168   ASSERT_FALSE(existed1);
 169
 170   auto [live_ref2, existed2] = cache.add(5, 4);
 171   ASSERT_FALSE(existed2);
 172
 173   cache.clear_range(0,4);
 174
 175   // Should not exists (Unreferenced):
 176   {
 177     auto [ref, existed] = cache.add(1, 4);
 178     ASSERT_FALSE(existed);
 179   }
 180   {
 181     auto [ref, existed] = cache.add(2, 4);
 182     ASSERT_FALSE(existed);
 183   }
 184   {
 185     auto [ref, existed] = cache.add(3, 4);
 186     ASSERT_FALSE(existed);
 187   }
 188   // Should exist (Still being referenced):
 189   {
 190     auto [ref, existed] = cache.add(4, 4);
 191     ASSERT_TRUE(existed);
 192   }
 193   // Should exists (Still being referenced and wasn't removed)
 194   {
 195     auto [ref, existed] = cache.add(5, 4);
 196     ASSERT_TRUE(existed);
 197   }
 198   // Test out of bound deletion:
 199   {
 200     cache.clear_range(3,8);
 201     auto [ref, existed] = cache.add(4, 4);
 202     ASSERT_TRUE(existed);
 203   }
 204   {
 205     auto [ref, existed] = cache.add(3, 4);
 206     ASSERT_FALSE(existed);
 207   }
 208 }