src/tests/testClpMap.cc

   1 /*
   2  * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #include "squid.h"
  10 #include "base/ClpMap.h"
  11 #include "compat/cppunit.h"
  12 #include "SquidConfig.h"
  13 #include "unitTestMain.h"
  14
  15 #include <ctime>
  16
  17 class TestClpMap: public CPPUNIT_NS::TestFixture
  18 {
  19     CPPUNIT_TEST_SUITE( TestClpMap );
  20     CPPUNIT_TEST( testMemoryCounter );
  21     CPPUNIT_TEST( testConstructor );
  22     CPPUNIT_TEST( testEntryCounter );
  23     CPPUNIT_TEST( testPutGetDelete );
  24     CPPUNIT_TEST( testMisses );
  25     CPPUNIT_TEST( testMemoryLimit );
  26     CPPUNIT_TEST( testTtlExpiration );
  27     CPPUNIT_TEST( testReplaceEntryWithShorterTtl );
  28     CPPUNIT_TEST( testZeroTtl );
  29     CPPUNIT_TEST( testNegativeTtl );
  30     CPPUNIT_TEST( testPurgeIsLru );
  31     CPPUNIT_TEST_SUITE_END();
  32
  33 public:
  34     void setUp() override;
  35
  36 protected:
  37     using Map = ClpMap<std::string, int>;
  38
  39     void testMemoryCounter();
  40     void testConstructor();
  41     void testEntryCounter();
  42     void testPutGetDelete();
  43     void testMisses();
  44     void testMemoryLimit();
  45     void testTtlExpiration();
  46     void testReplaceEntryWithShorterTtl();
  47     void testZeroTtl();
  48     void testNegativeTtl();
  49     void testPurgeIsLru();
  50
  51     /// Generate and insert the given number of entries into the given map. Each
  52     /// entry is guaranteed to be inserted, but that insertion may purge other
  53     /// entries, including entries previously added during the same method call.
  54     void addSequenceOfEntriesToMap(Map &, size_t count, Map::mapped_type startWith, Map::Ttl);
  55
  56     /// add (more than) enough entries to make the map full
  57     void fillMapWithEntries(Map &);
  58
  59     /// generate and add an entry with a given value (and a matching key) to the
  60     /// map using map-default TTL
  61     void addOneEntry(Map &, Map::mapped_type);
  62
  63     /// generate and add an entry with a given value, a matching key, and a
  64     /// given TTL to the map
  65     void addOneEntry(Map &, Map::mapped_type, Map::Ttl);
  66 };
  67
  68 CPPUNIT_TEST_SUITE_REGISTRATION( TestClpMap );
  69
  70 class SquidConfig Config;
  71
  72 void
  73 TestClpMap::addSequenceOfEntriesToMap(Map &m, size_t count, const Map::mapped_type startWith, const Map::Ttl ttl)
  74 {
  75     for (auto j = startWith; count; ++j, --count)
  76         CPPUNIT_ASSERT(m.add(std::to_string(j), j, ttl));
  77 }
  78
  79 void
  80 TestClpMap::fillMapWithEntries(Map &m)
  81 {
  82     addSequenceOfEntriesToMap(m, m.memLimit() / sizeof(Map::mapped_type), 0, 10);
  83 }
  84
  85 void
  86 TestClpMap::addOneEntry(Map &m, const Map::mapped_type value)
  87 {
  88     const auto key = std::to_string(value);
  89     CPPUNIT_ASSERT(m.add(key, value));
  90     CPPUNIT_ASSERT(m.get(key));
  91     CPPUNIT_ASSERT_EQUAL(value, *m.get(key));
  92 }
  93
  94 void
  95 TestClpMap::addOneEntry(Map &m, const Map::mapped_type value, const Map::Ttl ttl)
  96 {
  97     const auto key = std::to_string(value);
  98     CPPUNIT_ASSERT(m.add(key, value, ttl));
  99     CPPUNIT_ASSERT(m.get(key));
 100     CPPUNIT_ASSERT_EQUAL(value, *m.get(key));
 101 }
 102
 103 void
 104 TestClpMap::setUp()
 105 {
 106     squid_curtime = time(nullptr);
 107 }
 108
 109 void
 110 TestClpMap::testPutGetDelete()
 111 {
 112     Map m(1024);
 113     addSequenceOfEntriesToMap(m, 10, 0, 10);
 114     CPPUNIT_ASSERT(m.get("1")); // we get something
 115     CPPUNIT_ASSERT_EQUAL(1, *(m.get("1"))); // we get what we put in
 116     CPPUNIT_ASSERT(m.get("9"));
 117     CPPUNIT_ASSERT_EQUAL(9, *(m.get("9")));
 118     m.add("1", 99);
 119     CPPUNIT_ASSERT(m.get("1"));
 120     CPPUNIT_ASSERT_EQUAL(99, *(m.get("1")));
 121     m.del("1");
 122     CPPUNIT_ASSERT(!m.get("1")); // entry has been cleared
 123 }
 124
 125 void
 126 TestClpMap::testMisses()
 127 {
 128     Map m(1024);
 129     fillMapWithEntries(m);
 130     const auto entriesBefore = m.entries();
 131     CPPUNIT_ASSERT(!m.get("not-there"));
 132     m.del("not-there");
 133     CPPUNIT_ASSERT_EQUAL(entriesBefore, m.entries());
 134 }
 135
 136 void
 137 TestClpMap::testEntryCounter()
 138 {
 139     {
 140         Map m(10*1024*1024, 10);
 141         CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(0), m.entries());
 142         addSequenceOfEntriesToMap(m, 10, 10, 10);
 143         CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(10), m.entries());
 144         m.add("new-key", 0);
 145         CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(11), m.entries());
 146     }
 147     {
 148         Map m(1024, 5);
 149         addSequenceOfEntriesToMap(m, 1000, 0, 10);
 150         CPPUNIT_ASSERT(m.entries() < 1000);
 151     }
 152 }
 153
 154 void
 155 TestClpMap::testMemoryCounter()
 156 {
 157     CPPUNIT_ASSERT_EQUAL(sizeof(int), static_cast<size_t>(DefaultMemoryUsage(int{})));
 158     CPPUNIT_ASSERT_EQUAL(sizeof(int32_t), static_cast<size_t>(DefaultMemoryUsage(int32_t{})));
 159     CPPUNIT_ASSERT_EQUAL(sizeof(int64_t), static_cast<size_t>(DefaultMemoryUsage(int64_t{})));
 160     CPPUNIT_ASSERT_EQUAL(sizeof(char), static_cast<size_t>(DefaultMemoryUsage(char{})));
 161     using Str = char[10];
 162     CPPUNIT_ASSERT_EQUAL(sizeof(Str), static_cast<size_t>(DefaultMemoryUsage(Str{})));
 163 }
 164
 165 void
 166 TestClpMap::testConstructor()
 167 {
 168     const Map nilA(0);
 169     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilA.memLimit());
 170     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilA.freeMem());
 171     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilA.memoryUsed());
 172     CPPUNIT_ASSERT_EQUAL(size_t(0), nilA.entries());
 173
 174     const Map nilB(0, 0);
 175     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilB.memLimit());
 176     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilB.freeMem());
 177     CPPUNIT_ASSERT_EQUAL(uint64_t(0), nilB.memoryUsed());
 178     CPPUNIT_ASSERT_EQUAL(size_t(0), nilB.entries());
 179
 180     const Map emptyC(1);
 181     CPPUNIT_ASSERT_EQUAL(uint64_t(1), emptyC.memLimit());
 182     CPPUNIT_ASSERT_EQUAL(uint64_t(1), emptyC.freeMem());
 183     CPPUNIT_ASSERT_EQUAL(uint64_t(0), emptyC.memoryUsed());
 184     CPPUNIT_ASSERT_EQUAL(size_t(0), emptyC.entries());
 185
 186     const Map emptyD(1024);
 187     CPPUNIT_ASSERT_EQUAL(uint64_t(1024), emptyD.memLimit());
 188     CPPUNIT_ASSERT_EQUAL(uint64_t(1024), emptyD.freeMem());
 189     CPPUNIT_ASSERT_EQUAL(uint64_t(0), emptyD.memoryUsed());
 190     CPPUNIT_ASSERT_EQUAL(size_t(0), emptyD.entries());
 191 }
 192
 193 void
 194 TestClpMap::testMemoryLimit()
 195 {
 196     const size_t initialCapacity = 1024; // bytes
 197     Map m(initialCapacity);
 198     fillMapWithEntries(m);
 199     const auto entriesAtInitialCapacity = m.entries();
 200
 201     // check that all entries are removed if we prohibit storage of any entries
 202     m.setMemLimit(0);
 203     CPPUNIT_ASSERT_EQUAL(size_t(0), m.entries());
 204
 205     // test whether the map can grow after the all-at-once purging above
 206     const auto increasedCapacity = initialCapacity * 2;
 207     m.setMemLimit(increasedCapacity);
 208     fillMapWithEntries(m);
 209     CPPUNIT_ASSERT(m.entries() > entriesAtInitialCapacity);
 210
 211     // test that memory usage and entry count decrease when the map is shrinking
 212     // but prevent endless loops no matter how broken ClpMap implementation is
 213     auto iterationsLeft = m.entries();
 214     CPPUNIT_ASSERT(0 < iterationsLeft && iterationsLeft <= increasedCapacity);
 215     while (m.entries()) {
 216         // TODO: Check that we can still add a (smaller) entry here.
 217
 218         const auto memoryUsedBefore = m.memoryUsed();
 219         const auto entriesBefore = m.entries();
 220
 221         const auto newMemoryLimit = memoryUsedBefore/2; // may become zero
 222         m.setMemLimit(newMemoryLimit);
 223
 224         CPPUNIT_ASSERT(m.memoryUsed() <= newMemoryLimit);
 225         CPPUNIT_ASSERT(m.entries() < entriesBefore);
 226
 227         // the assertion below may fail if ClpMap::entries() returns bogus numbers
 228         CPPUNIT_ASSERT(iterationsLeft > 0);
 229         --iterationsLeft;
 230     }
 231
 232     // test whether the map can grow after all that gradual purging above
 233     m.setMemLimit(increasedCapacity);
 234     fillMapWithEntries(m);
 235     CPPUNIT_ASSERT(m.entries() > entriesAtInitialCapacity);
 236 }
 237
 238 void
 239 TestClpMap::testTtlExpiration()
 240 {
 241     {
 242         Map m(2048);
 243         addOneEntry(m, 0, 100);
 244         squid_curtime += 20;
 245         CPPUNIT_ASSERT(m.get("0")); // still fresh
 246         squid_curtime += 100;
 247         CPPUNIT_ASSERT(!m.get("0")); // has expired
 248     }
 249
 250     {
 251         // same test, but using a map-specific TTL instead of entry-specific one
 252         Map m(2048, 100);
 253         addOneEntry(m, 0);
 254         squid_curtime += 20;
 255         CPPUNIT_ASSERT(m.get("0")); // still fresh
 256         squid_curtime += 100;
 257         CPPUNIT_ASSERT(!m.get("0")); // has expired
 258     }
 259
 260     {
 261         // same test, but using both map-specific and entry-specific TTLs
 262         Map m(2048, 1);
 263         addOneEntry(m, 0, 100);
 264         squid_curtime += 20;
 265         CPPUNIT_ASSERT(m.get("0")); // still fresh
 266         squid_curtime += 100;
 267         CPPUNIT_ASSERT(!m.get("0")); // has expired
 268     }
 269 }
 270
 271 void
 272 TestClpMap::testReplaceEntryWithShorterTtl()
 273 {
 274     Map m(2048);
 275     addOneEntry(m, 0, 100);
 276     addOneEntry(m, 0, 10); // same (key, value) entry but with shorter TTL
 277     squid_curtime += 20;
 278     CPPUNIT_ASSERT(!m.get("0")); // has expired
 279
 280     // now the same sequence but with a time change between additions
 281     addOneEntry(m, 0, 100);
 282     squid_curtime += 200;
 283     addOneEntry(m, 0, 10);
 284     CPPUNIT_ASSERT(m.get("0")); // still fresh due to new TTL
 285     squid_curtime += 20;
 286     CPPUNIT_ASSERT(!m.get("0")); // has expired
 287 }
 288
 289 void
 290 TestClpMap::testZeroTtl()
 291 {
 292     {
 293         Map m(2048);
 294         addOneEntry(m, 0, 0);
 295         squid_curtime += 1;
 296         CPPUNIT_ASSERT(!m.get("0")); // expired, we get nothing
 297     }
 298
 299     {
 300         // same test, but using a map-specific TTL instead of entry-specific one
 301         Map m(2048, 0);
 302         addOneEntry(m, 0);
 303         squid_curtime += 1;
 304         CPPUNIT_ASSERT(!m.get("0")); // expired, we get nothing
 305     }
 306
 307     {
 308         // same test, but using both map-specific and entry-specific TTLs
 309         Map m(2048, 10);
 310         addOneEntry(m, 0, 0);
 311         squid_curtime += 1;
 312         CPPUNIT_ASSERT(!m.get("0")); // expired, we get nothing
 313     }
 314 }
 315
 316 void
 317 TestClpMap::testNegativeTtl()
 318 {
 319     Map m(2048);
 320
 321     // we start with an ordinary-TTL entry to check that it will be purged below
 322     addOneEntry(m, 0, 10);
 323
 324     // check that negative-TTL entries are rejected
 325     CPPUNIT_ASSERT(!m.add("0", 0, -1));
 326
 327     // check that an attempt to add a negative-TTL entry purges the previously
 328     // added ordinary-TTL entry
 329     CPPUNIT_ASSERT(!m.get("0"));
 330
 331     // check that the same entry can be re-added with a non-negative TTL
 332     addOneEntry(m, 0);
 333 }
 334
 335 void
 336 TestClpMap::testPurgeIsLru()
 337 {
 338     Map m(2048);
 339     for (int j = 0; j < 10; ++j)
 340         addOneEntry(m, j);
 341     // now overflow the map while keeping "0" the Least Recently Used
 342     for (int j = 100; j < 1000; ++j) {
 343         addOneEntry(m, j);
 344         CPPUNIT_ASSERT(m.get("0"));
 345     }
 346     // these should have been aged out
 347     CPPUNIT_ASSERT(!m.get("1"));
 348     CPPUNIT_ASSERT(!m.get("2"));
 349     CPPUNIT_ASSERT(!m.get("3"));
 350     CPPUNIT_ASSERT(!m.get("4"));
 351
 352     fillMapWithEntries(m);
 353     CPPUNIT_ASSERT(!m.get("0")); // removable when not recently used
 354 }