xrpld
Loading...
Searching...
No Matches
TaggedCache.cpp
1#include <xrpl/basics/TaggedCache.h>
2
3#include <xrpl/basics/IntrusivePointer.h>
4#include <xrpl/basics/IntrusiveRefCounts.h>
5#include <xrpl/basics/TaggedCache.ipp> // IWYU pragma: keep
6#include <xrpl/basics/chrono.h>
7#include <xrpl/beast/utility/Journal.h>
8#include <xrpl/protocol/Protocol.h>
9
10#include <gtest/gtest.h>
11#include <helpers/TestSink.h>
12
13#include <chrono>
14#include <memory>
15#include <string>
16#include <utility>
17
18namespace xrpl {
19
20struct TaggedCacheTestBase : public ::testing::Test
21{
23
24 // A single `++clock` plus a sweep is enough to age any entry out.
25 static constexpr std::chrono::seconds kExpiration{1};
26 static constexpr int kTargetSize = 1;
27
30};
31
39
40TEST_F(TaggedCacheTest, insert_then_retrieve)
41{
42 EXPECT_EQ(cache.getCacheSize(), 0);
43 EXPECT_EQ(cache.getTrackSize(), 0);
44
45 EXPECT_FALSE(cache.insert(1, "one"));
46 EXPECT_EQ(cache.getCacheSize(), 1);
47 EXPECT_EQ(cache.getTrackSize(), 1);
48
49 std::string retrieved;
50 EXPECT_TRUE(cache.retrieve(1, retrieved));
51 EXPECT_EQ(retrieved, "one");
52}
53
54TEST_F(TaggedCacheTest, sweep_purges_an_aged_entry)
55{
56 EXPECT_FALSE(cache.insert(1, "one"));
57
58 ++clock;
59 cache.sweep();
60
61 EXPECT_EQ(cache.getCacheSize(), 0);
62 EXPECT_EQ(cache.getTrackSize(), 0);
63}
64
65TEST_F(TaggedCacheTest, sweep_keeps_tracking_an_entry_a_caller_still_holds)
66{
67 EXPECT_FALSE(cache.insert(2, "two"));
68 EXPECT_EQ(cache.getCacheSize(), 1);
69 EXPECT_EQ(cache.getTrackSize(), 1);
70
71 {
72 // Scope is load-bearing: the entry survives the sweep only while this
73 // pointer is alive.
74 auto const held = cache.fetch(2);
75 EXPECT_NE(held, nullptr);
76
77 ++clock;
78 cache.sweep();
79 EXPECT_EQ(cache.getCacheSize(), 0);
80 EXPECT_EQ(cache.getTrackSize(), 1);
81 }
82
83 ++clock;
84 cache.sweep();
85 EXPECT_EQ(cache.getCacheSize(), 0);
86 EXPECT_EQ(cache.getTrackSize(), 0);
87}
88
89TEST_F(TaggedCacheTest, canonicalize_replace_client_hands_back_the_cached_object)
90{
91 EXPECT_FALSE(cache.insert(3, "three"));
92
93 {
94 // Scope is load-bearing: both pointers must die before the sweep below.
95 auto const cached = cache.fetch(3);
96 auto candidate = std::make_shared<Value>("three");
97 cache.canonicalizeReplaceClient(3, candidate);
98
99 EXPECT_EQ(cached.get(), candidate.get());
100 }
101
102 // Canonicalizing left no lingering reference, so the entry still ages out.
103 ++clock;
104 cache.sweep();
105 EXPECT_EQ(cache.getCacheSize(), 0);
106 EXPECT_EQ(cache.getTrackSize(), 0);
107}
108
109TEST_F(TaggedCacheTest, canonicalize_replace_client_revives_a_swept_entry)
110{
111 EXPECT_FALSE(cache.insert(4, "four"));
112 EXPECT_EQ(cache.getCacheSize(), 1);
113 EXPECT_EQ(cache.getTrackSize(), 1);
114
115 {
116 // Scope is load-bearing: the final sweep must see nothing held.
117 auto const held = cache.fetch(4);
118 EXPECT_NE(held, nullptr);
119 // Fetching does not disturb the counts.
120 EXPECT_EQ(cache.getCacheSize(), 1);
121 EXPECT_EQ(cache.getTrackSize(), 1);
122
123 ++clock;
124 cache.sweep();
125 EXPECT_EQ(cache.getCacheSize(), 0);
126 EXPECT_EQ(cache.getTrackSize(), 1);
127
128 auto candidate = std::make_shared<Value>("four");
129 EXPECT_TRUE(cache.canonicalizeReplaceClient(4, candidate));
130 EXPECT_EQ(cache.getCacheSize(), 1);
131 EXPECT_EQ(cache.getTrackSize(), 1);
132
133 EXPECT_EQ(held.get(), candidate.get());
134 }
135
136 ++clock;
137 cache.sweep();
138 EXPECT_EQ(cache.getCacheSize(), 0);
139 EXPECT_EQ(cache.getTrackSize(), 0);
140}
141
142TEST_F(TaggedCacheTest, canonicalize_replace_cache_installs_the_new_object)
143{
144 EXPECT_FALSE(cache.insert(5, "five"));
145 EXPECT_EQ(cache.getCacheSize(), 1);
146 EXPECT_EQ(cache.size(), 1);
147
148 {
149 // Scope is load-bearing: the final sweep must see nothing held.
150 auto const held = cache.fetch(5);
151 EXPECT_NE(held, nullptr);
152 // Fetching does not disturb the counts.
153 EXPECT_EQ(cache.getCacheSize(), 1);
154 EXPECT_EQ(cache.size(), 1);
155
156 ++clock;
157 cache.sweep();
158 EXPECT_EQ(cache.getCacheSize(), 0);
159 EXPECT_EQ(cache.size(), 1);
160
161 auto const replacement = std::make_shared<Value>("five_2");
162 EXPECT_TRUE(cache.canonicalizeReplaceCache(5, replacement));
163 EXPECT_EQ(cache.getCacheSize(), 1);
164 EXPECT_EQ(cache.size(), 1);
165
166 // Unlike ReplaceClient, the caller's object wins and the old one is
167 // left untouched in the caller's hands.
168 EXPECT_NE(held.get(), replacement.get());
169 EXPECT_EQ(*replacement, "five_2");
170
171 auto const refetched = cache.fetch(5);
172 EXPECT_NE(refetched, nullptr);
173 EXPECT_EQ(refetched.get(), replacement.get());
174 EXPECT_NE(refetched.get(), held.get());
175 }
176
177 ++clock;
178 cache.sweep();
179 EXPECT_EQ(cache.getCacheSize(), 0);
180 EXPECT_EQ(cache.size(), 0);
181}
182
183namespace {
184
185struct TestRefCountObject : IntrusiveRefCounts
186{
187 std::string data;
188
189 // Needed to support weak intrusive pointers
190 virtual void
191 partialDestructor()
192 {
193 }
194
195 TestRefCountObject() = default;
196 explicit TestRefCountObject(std::string data) : data(std::move(data))
197 {
198 }
199
200 bool
201 operator==(std::string const& other) const
202 {
203 return data == other;
204 }
205};
206
207} // namespace
208
220
221TEST_F(IntrusiveTaggedCacheTest, canonicalize_replace_cache_replaces_the_entry)
222{
223 intrPtrCache.canonicalizeReplaceCache(1, intr_ptr::makeShared<TestRefCountObject>("one"));
224 EXPECT_EQ(intrPtrCache.getCacheSize(), 1);
225 EXPECT_EQ(intrPtrCache.size(), 1);
226
227 intrPtrCache.canonicalizeReplaceCache(
229 EXPECT_EQ(*intrPtrCache.fetch(1), "one_replaced");
230}
231
232TEST_F(IntrusiveTaggedCacheTest, canonicalize_replace_cache_replaces_a_swept_entry)
233{
234 intrPtrCache.canonicalizeReplaceCache(1, intr_ptr::makeShared<TestRefCountObject>("one"));
235
236 // Load-bearing: without this the sweep drops the entry and size() is 0.
237 auto const held = intrPtrCache.fetch(1);
238
239 ++clock;
240 intrPtrCache.sweep();
241 EXPECT_EQ(intrPtrCache.getCacheSize(), 0);
242 EXPECT_EQ(intrPtrCache.size(), 1);
243
244 intrPtrCache.canonicalizeReplaceCache(
245 1, intr_ptr::makeShared<TestRefCountObject>("one_replaced_2"));
246 EXPECT_EQ(*intrPtrCache.fetch(1), "one_replaced_2");
247}
248
249TEST_F(IntrusiveTaggedCacheTest, an_entry_can_be_reinserted_after_del)
250{
251 intrPtrCache.canonicalizeReplaceCache(1, intr_ptr::makeShared<TestRefCountObject>("one"));
252
253 // Nothing else holds the entry, so del() drops it from the map too.
254 EXPECT_TRUE(intrPtrCache.del(1, true));
255 EXPECT_EQ(intrPtrCache.getCacheSize(), 0);
256 EXPECT_EQ(intrPtrCache.size(), 0);
257
258 intrPtrCache.canonicalizeReplaceCache(
259 1, intr_ptr::makeShared<TestRefCountObject>("one_replaced_3"));
260 EXPECT_EQ(*intrPtrCache.fetch(1), "one_replaced_3");
261}
262
263TEST_F(IntrusiveTaggedCacheTest, an_expired_weak_entry_is_replaced_after_del)
264{
265 intrPtrCache.canonicalizeReplaceCache(1, intr_ptr::makeShared<TestRefCountObject>("one"));
266 {
267 // While held, del() only demotes the entry to a weak pointer, so it
268 // stays in the map and expires once this scope releases it.
269 auto const held = intrPtrCache.fetch(1);
270 EXPECT_TRUE(intrPtrCache.del(1, true));
271 EXPECT_EQ(intrPtrCache.getCacheSize(), 0);
272 EXPECT_EQ(intrPtrCache.size(), 1);
273 }
274
275 EXPECT_FALSE(intrPtrCache.canonicalizeReplaceCache(
276 1, intr_ptr::makeShared<TestRefCountObject>("one_replaced")));
277 EXPECT_EQ(intrPtrCache.getCacheSize(), 1);
278 EXPECT_EQ(intrPtrCache.size(), 1);
279 EXPECT_EQ(*intrPtrCache.fetch(1), "one_replaced");
280}
281
282TEST_F(IntrusiveTaggedCacheTest, sweep_empties_the_cache_once_nothing_is_held)
283{
284 intrPtrCache.canonicalizeReplaceCache(1, intr_ptr::makeShared<TestRefCountObject>("one"));
285
286 ++clock;
287 intrPtrCache.sweep();
288 EXPECT_EQ(intrPtrCache.getCacheSize(), 0);
289 EXPECT_EQ(intrPtrCache.size(), 0);
290}
291
292TEST_F(TaggedCacheTest, fetch_and_modify_revives_a_swept_entry)
293{
294 cache.fetchAndModify(1, [](std::string& v) { v = "one"; });
295 auto const held = cache.fetch(1);
296 ASSERT_NE(held, nullptr);
297
298 ++clock;
299 cache.sweep();
300 EXPECT_EQ(cache.getCacheSize(), 0); // demoted to weak
301 EXPECT_EQ(cache.getTrackSize(), 1); // still tracked while `held` is alive
302
303 cache.fetchAndModify(1, [](std::string& v) { v += "_modified"; });
304 EXPECT_EQ(*held, "one_modified"); // the same object was mutated
305 EXPECT_EQ(cache.getCacheSize(), 1); // and promoted back to strong
306 EXPECT_EQ(cache.getTrackSize(), 1);
307 EXPECT_EQ(cache.fetch(1).get(), held.get());
308}
309
310TEST_F(TaggedCacheTest, fetch_and_modify_replaces_an_expired_entry)
311{
312 cache.fetchAndModify(1, [](std::string& v) { v = "one"; });
313 {
314 auto const held = cache.fetch(1);
315 ASSERT_NE(held, nullptr);
316 ++clock;
317 cache.sweep();
318 EXPECT_EQ(cache.getCacheSize(), 0);
319 EXPECT_EQ(cache.getTrackSize(), 1);
320 }
321 // The weak entry is now expired but has not been erased by a sweep yet.
322 std::string observed = "unset";
323 cache.fetchAndModify(1, [&observed](std::string& v) {
324 observed = v;
325 v = "two";
326 });
327 EXPECT_EQ(observed, ""); // a fresh, default-constructed object
328 EXPECT_EQ(cache.getCacheSize(), 1);
329 EXPECT_EQ(cache.getTrackSize(), 1);
330 EXPECT_EQ(*cache.fetch(1), "two");
331}
332
333TEST_F(IntrusiveTaggedCacheTest, fetch_and_modify_supports_intrusive_pointers)
334{
335 // Miss: the placeholder is built with intr_ptr::makeShared and installed.
336 intrPtrCache.fetchAndModify(1, [](TestRefCountObject& v) { v.data = "one"; });
337 EXPECT_EQ(intrPtrCache.getCacheSize(), 1);
338 EXPECT_EQ(intrPtrCache.getTrackSize(), 1);
339
340 auto const held = intrPtrCache.fetch(1);
341 ASSERT_NE(held, nullptr);
342 EXPECT_EQ(*held, "one");
343
344 // Hit: the cached object is mutated in place, no new entry.
345 intrPtrCache.fetchAndModify(1, [](TestRefCountObject& v) { v.data += "_modified"; });
346 EXPECT_EQ(*held, "one_modified");
347 EXPECT_EQ(intrPtrCache.getCacheSize(), 1);
348 EXPECT_EQ(intrPtrCache.fetch(1).get(), held.get());
349}
350
351TEST_F(TaggedCacheTest, fetch_and_modify)
352{
353 using namespace std::chrono_literals;
354 beast::Journal const journal{TestSink::instance()};
355
356 TestStopwatch clock;
357 clock.set(0);
358
359 struct MutableValue
360 {
361 int counter = 0;
362 std::string name;
363 };
364
365 using Key = LedgerIndex;
366 using MutCache = TaggedCache<Key, MutableValue>;
367
368 MutCache mc("mutable_test", 2, 2s, clock, journal);
369
370 // A. Insert on miss: fetchAndModify creates entry and mutates it.
371 mc.fetchAndModify(5, [](MutableValue& v) {
372 v.counter = 42;
373 v.name = "initial";
374 });
375
376 EXPECT_EQ(mc.getCacheSize(), 1);
377 EXPECT_EQ(mc.getTrackSize(), 1);
378
379 // Verify the mutation persisted.
380 auto const p1 = mc.fetch(5);
381 ASSERT_NE(p1, nullptr);
382 EXPECT_EQ(p1->counter, 42);
383 EXPECT_EQ(p1->name, "initial");
384
385 // Keep a second strong pointer to verify in-place modification.
386 auto const p2 = mc.fetch(5);
387 ASSERT_NE(p2, nullptr);
388 EXPECT_EQ(p1.get(), p2.get()); // Same object
389
390 // B. Modify existing object on hit.
391 mc.fetchAndModify(5, [](MutableValue& v) {
392 v.counter += 10;
393 v.name = "modified";
394 });
395
396 // No new entry was created.
397 EXPECT_EQ(mc.getCacheSize(), 1);
398 EXPECT_EQ(mc.getTrackSize(), 1);
399
400 // The same object was mutated (both strong pointers see the change).
401 EXPECT_EQ(p1->counter, 52);
402 EXPECT_EQ(p1->name, "modified");
403 EXPECT_EQ(p2->counter, 52);
404
405 // Fresh fetch returns the same object identity.
406 auto const p3 = mc.fetch(5);
407 ASSERT_NE(p3, nullptr);
408 EXPECT_EQ(p3.get(), p1.get());
409 EXPECT_EQ(p3->counter, 52);
410}
411
412} // namespace xrpl
A generic endpoint for log messages.
Definition Journal.h:44
Map/cache combination.
Definition TaggedCache.h:67
static TestSink & instance()
Definition TestSink.h:12
T make_shared(T... args)
T move(T... args)
SharedWeakUnion< T > SharedWeakUnionPtr
SharedIntrusive< T > SharedPtr
SharedPtr< T > makeShared(A &&... args)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
constexpr bool operator==(BaseUInt< Bits, Tag > const &lhs, BaseUInt< Bits, Tag > const &rhs)
Definition base_uint.h:613
std::uint32_t LedgerIndex
A ledger index.
Definition Protocol.h:409
TEST_F(HardenedHashTest, user_types)
beast::ManualClock< std::chrono::steady_clock > TestStopwatch
A manual Stopwatch for unit tests.
Definition chrono.h:95
TaggedCache< Key, TestRefCountObject, false, intr_ptr::SharedWeakUnionPtr< TestRefCountObject >, intr_ptr::SharedPtr< TestRefCountObject > > IntrPtrCache
static constexpr std::chrono::seconds kExpiration
static constexpr int kTargetSize
beast::Journal const journal
TestStopwatch clock
ManualClock starts at zero.
TaggedCache< Key, Value > Cache