1 /**
2  * @file unit-lru_cache.cc
3  *
4  * @section LICENSE
5  *
6  * The MIT License
7  *
8  * @copyright Copyright (c) 2017-2021 TileDB, Inc.
9  *
10  * Permission is hereby granted, free of charge, to any person obtaining a copy
11  * of this software and associated documentation files (the "Software"), to deal
12  * in the Software without restriction, including without limitation the rights
13  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14  * copies of the Software, and to permit persons to whom the Software is
15  * furnished to do so, subject to the following conditions:
16  *
17  * The above copyright notice and this permission notice shall be included in
18  * all copies or substantial portions of the Software.
19  *
20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
23  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
26  * THE SOFTWARE.
27  *
28  * @section DESCRIPTION
29  *
30  * This file unit-tests class BufferLRUCache.
31  */
32 
33 #include "catch.hpp"
34 #include "tiledb/sm/buffer/buffer.h"
35 #include "tiledb/sm/cache/buffer_lru_cache.h"
36 
37 using namespace tiledb::common;
38 using namespace tiledb::sm;
39 
40 #define CACHE_SIZE 10 * sizeof(int)
41 #define CACHE_ZERO_SIZE 0
42 
43 struct BufferLRUCacheFx {
44   BufferLRUCache* lru_cache_;
45 
BufferLRUCacheFxBufferLRUCacheFx46   BufferLRUCacheFx() {
47     lru_cache_ = new BufferLRUCache(CACHE_SIZE);
48   }
49 
~BufferLRUCacheFxBufferLRUCacheFx50   ~BufferLRUCacheFx() {
51     delete lru_cache_;
52   }
53 
check_key_orderBufferLRUCacheFx54   bool check_key_order(const std::string& golden_order) {
55     auto it = lru_cache_->item_iter_begin();
56     auto it_end = lru_cache_->item_iter_end();
57     std::string keys;
58     for (; it != it_end; ++it)
59       keys += it->key_;
60     return keys == golden_order;
61   }
62 };
63 
64 TEST_CASE_METHOD(
65     BufferLRUCacheFx, "Unit-test class BufferLRUCache", "[lru_cache]") {
66   // Insert an object larger than CACHE_SIZE
67   Buffer v;
68   CHECK(v.realloc(CACHE_SIZE + 1).ok());
69   bool success;
70   Status st = lru_cache_->insert("key", std::move(v));
71   CHECK(st.ok());
72   Buffer v_buf;
73   st = lru_cache_->read("key", &v_buf, 0, sizeof(int), &success);
74   CHECK(st.ok());
75   CHECK(!success);
76 
77   // Prepare some vectors
78   Buffer v1;
79   Buffer v2;
80   Buffer v3;
81   CHECK(v1.realloc(sizeof(int) * 3).ok());
82   CHECK(v2.realloc(sizeof(int) * 3).ok());
83   CHECK(v3.realloc(sizeof(int) * 3).ok());
84   v1.set_size(v1.alloced_size());
85   v2.set_size(v2.alloced_size());
86   v3.set_size(v3.alloced_size());
87 
88   for (int i = 0; i < 3; ++i) {
89     static_cast<int*>(v1.data())[i] = i;
90     static_cast<int*>(v2.data())[i] = 3 + i;
91     static_cast<int*>(v3.data())[i] = 6 + i;
92   }
93 
94   // Insert 3 items in the cache
95   Buffer v1_cp(v1);
96   st = lru_cache_->insert("v1", std::move(v1_cp));
97   CHECK(st.ok());
98   Buffer v2_cp(v2);
99   st = lru_cache_->insert("v2", std::move(v2_cp));
100   CHECK(st.ok());
101   Buffer v3_cp(v3);
102   st = lru_cache_->insert("v3", std::move(v3_cp));
103   CHECK(st.ok());
104 
105   // Check that the order in the linked list is v1-v2-v3
106   CHECK(check_key_order("v1v2v3"));
107 
108   // Read non-existent item
109   v_buf.reset_offset();
110   st = lru_cache_->read("v", &v_buf, 0, sizeof(int), &success);
111   CHECK(st.ok());
112   CHECK(!success);
113 
114   // Read full v3
115   v_buf.reset_offset();
116   st = lru_cache_->read("v3", &v_buf, 0, 3 * sizeof(int), &success);
117   CHECK(st.ok());
118   CHECK(success);
119   CHECK(!memcmp(v_buf.data(), v3.data(), 3 * sizeof(int)));
120 
121   // Check that the order in the linked list is v1-v2-v3
122   CHECK(check_key_order("v1v2v3"));
123 
124   // Read partial v2
125   v_buf.reset_offset();
126   st = lru_cache_->read("v2", &v_buf, sizeof(int), sizeof(int), &success);
127   CHECK(st.ok());
128   CHECK(success);
129   CHECK(v_buf.value<int>(0) == v2.value<int>(1 * sizeof(int)));
130 
131   // Check that the order in the linked list is v1-v3-v2
132   CHECK(check_key_order("v1v3v2"));
133 
134   // Read out of bounds
135   v_buf.reset_offset();
136   st = lru_cache_->read("v2", &v_buf, sizeof(int), 4 * sizeof(int), &success);
137   CHECK(!st.ok());
138 
139   // Test eviction
140   Buffer v4;
141   CHECK(v4.realloc(sizeof(int) * 5).ok());
142   st = lru_cache_->insert("v4", std::move(v4));
143   CHECK(st.ok());
144 
145   // Check that the order in the linked list is v2-v4
146   CHECK(check_key_order("v2v4"));
147 
148   // Test clear
149   lru_cache_->clear();
150   auto it = lru_cache_->item_iter_begin();
151   auto it_end = lru_cache_->item_iter_end();
152   CHECK(it == it_end);
153 }
154 
155 TEST_CASE_METHOD(
156     BufferLRUCacheFx, "BufferLRUCache item invalidation", "[lru_cache]") {
157   Buffer v1;
158   Buffer v2;
159   Buffer v3;
160   Buffer v4;
161   CHECK(v1.realloc(sizeof(int) * 3).ok());
162   CHECK(v2.realloc(sizeof(int) * 3).ok());
163   CHECK(v3.realloc(sizeof(int) * 3).ok());
164   CHECK(v4.realloc(sizeof(int) * 4).ok());
165   v1.set_size(v1.alloced_size());
166   v2.set_size(v2.alloced_size());
167   v3.set_size(v3.alloced_size());
168   v4.set_size(v4.alloced_size());
169   for (int i = 0; i < 3; ++i) {
170     static_cast<int*>(v1.data())[i] = i + 1;
171     static_cast<int*>(v2.data())[i] = 3 + i + 1;
172     static_cast<int*>(v3.data())[i] = 6 + i + 1;
173     static_cast<int*>(v4.data())[i] = 9 + i + 1;
174   }
175 
176   Buffer v1_cp(v1);
177   Status st = lru_cache_->insert("v1", std::move(v1_cp));
178   CHECK(st.ok());
179   Buffer v2_cp(v2);
180   st = lru_cache_->insert("v2", std::move(v2_cp));
181   CHECK(st.ok());
182 
183   // Check invalidate non-existent key
184   bool success;
185   st = lru_cache_->invalidate("key", &success);
186   CHECK(st.ok());
187   CHECK(!success);
188   CHECK(check_key_order("v1v2"));
189 
190   // Check invalidate head of list
191   st = lru_cache_->invalidate("v1", &success);
192   CHECK(st.ok());
193   CHECK(success);
194   CHECK(check_key_order("v2"));
195   st = lru_cache_->invalidate("v1", &success);
196   CHECK(st.ok());
197   CHECK(!success);
198   CHECK(check_key_order("v2"));
199 
200   Buffer v3_cp(v3);
201   st = lru_cache_->insert("v3", std::move(v3_cp));
202   CHECK(st.ok());
203   Buffer v4_cp(v4);
204   st = lru_cache_->insert("v4", std::move(v4_cp));
205   CHECK(st.ok());
206   CHECK(check_key_order("v2v3v4"));
207 
208   // Check invalidate middle of list
209   st = lru_cache_->invalidate("v3", &success);
210   CHECK(st.ok());
211   CHECK(success);
212   CHECK(check_key_order("v2v4"));
213 
214   // Check invalidate end of list
215   st = lru_cache_->invalidate("v4", &success);
216   CHECK(st.ok());
217   CHECK(success);
218   CHECK(check_key_order("v2"));
219 
220   // Check invalidate final element
221   st = lru_cache_->invalidate("v2", &success);
222   CHECK(st.ok());
223   CHECK(success);
224   auto it = lru_cache_->item_iter_begin();
225   auto it_end = lru_cache_->item_iter_end();
226   CHECK(it == it_end);
227 }
228 
229 TEST_CASE("BufferLRUCache of 0 capacity", "[lru_cache]") {
230   // Create 0 size cache
231   BufferLRUCache* lru_cache = new BufferLRUCache(CACHE_ZERO_SIZE);
232   auto it = lru_cache->item_iter_begin();
233   auto it_end = lru_cache->item_iter_end();
234   CHECK(it == it_end);
235 
236   // Test insert
237   Buffer v;
238   CHECK(v.realloc(CACHE_ZERO_SIZE + 1).ok());
239   Status st = lru_cache->insert("key", std::move(v));
240   CHECK(st.ok());
241 
242   // Test read
243   Buffer v_buf;
244   bool success;
245   st = lru_cache->read("key", &v_buf, 0, sizeof(int), &success);
246   CHECK(st.ok());
247   CHECK(!success);
248 
249   // Test invalidate
250   st = lru_cache->invalidate("key", &success);
251   CHECK(st.ok());
252   CHECK(!success);
253 
254   // Test clear
255   lru_cache->clear();
256   it = lru_cache->item_iter_begin();
257   it_end = lru_cache->item_iter_end();
258   CHECK(it == it_end);
259 
260   delete lru_cache;
261 }