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 }