1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_kvs/internal/entry_cache.h"
16
17 #include "pw_bytes/array.h"
18 #include "pw_kvs/fake_flash_memory.h"
19 #include "pw_kvs/flash_memory.h"
20 #include "pw_kvs/internal/hash.h"
21 #include "pw_kvs/internal/key_descriptor.h"
22 #include "pw_unit_test/framework.h"
23
24 namespace pw::kvs::internal {
25 namespace {
26
27 using std::byte;
28
29 class EmptyEntryCache : public ::testing::Test {
30 protected:
31 static constexpr size_t kMaxEntries = 32;
32 static constexpr size_t kRedundancy = 3;
33
EmptyEntryCache()34 EmptyEntryCache() : entries_(descriptors_, addresses_, kRedundancy) {}
35
36 Vector<KeyDescriptor, kMaxEntries> descriptors_;
37 EntryCache::AddressList<kMaxEntries, kRedundancy> addresses_;
38
39 EntryCache entries_;
40 };
41
42 constexpr char kTheKey[] = "The Key";
43
44 constexpr KeyDescriptor kDescriptor = {.key_hash = Hash(kTheKey),
45 .transaction_id = 123,
46 .state = EntryState::kValid};
47
TEST_F(EmptyEntryCache,AddNew)48 TEST_F(EmptyEntryCache, AddNew) {
49 EntryMetadata metadata = entries_.AddNew(kDescriptor, 5);
50 EXPECT_EQ(kDescriptor.key_hash, metadata.hash());
51 EXPECT_EQ(kDescriptor.transaction_id, metadata.transaction_id());
52 EXPECT_EQ(kDescriptor.state, metadata.state());
53
54 EXPECT_EQ(5u, metadata.first_address());
55 EXPECT_EQ(1u, metadata.addresses().size());
56 }
57
TEST_F(EmptyEntryCache,EntryMetadata_AddNewAddress)58 TEST_F(EmptyEntryCache, EntryMetadata_AddNewAddress) {
59 EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
60
61 metadata.AddNewAddress(999);
62
63 EXPECT_EQ(2u, metadata.addresses().size());
64 EXPECT_EQ(100u, metadata.first_address());
65 EXPECT_EQ(100u, metadata.addresses()[0]);
66 EXPECT_EQ(999u, metadata.addresses()[1]);
67 }
68
TEST_F(EmptyEntryCache,EntryMetadata_Reset)69 TEST_F(EmptyEntryCache, EntryMetadata_Reset) {
70 EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
71 metadata.AddNewAddress(999);
72
73 metadata.Reset(
74 {.key_hash = 987, .transaction_id = 5, .state = EntryState::kDeleted},
75 8888);
76
77 EXPECT_EQ(987u, metadata.hash());
78 EXPECT_EQ(5u, metadata.transaction_id());
79 EXPECT_EQ(EntryState::kDeleted, metadata.state());
80 EXPECT_EQ(1u, metadata.addresses().size());
81 EXPECT_EQ(8888u, metadata.first_address());
82 EXPECT_EQ(8888u, metadata.addresses()[0]);
83 }
84
TEST_F(EmptyEntryCache,AddNewOrUpdateExisting_NewEntry)85 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry) {
86 ASSERT_EQ(OkStatus(),
87 entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
88
89 EXPECT_EQ(1u, entries_.present_entries());
90
91 for (const EntryMetadata& entry : entries_) {
92 EXPECT_EQ(1000u, entry.first_address());
93 EXPECT_EQ(kDescriptor.key_hash, entry.hash());
94 EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
95 }
96 }
97
TEST_F(EmptyEntryCache,AddNewOrUpdateExisting_NewEntry_Full)98 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry_Full) {
99 for (uint32_t i = 0; i < kMaxEntries; ++i) {
100 ASSERT_EQ( // Fill up the cache
101 OkStatus(),
102 entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
103 }
104 ASSERT_EQ(kMaxEntries, entries_.total_entries());
105 ASSERT_TRUE(entries_.full());
106
107 EXPECT_EQ(Status::ResourceExhausted(),
108 entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1));
109 EXPECT_EQ(kMaxEntries, entries_.total_entries());
110 }
111
TEST_F(EmptyEntryCache,AddNewOrUpdateExisting_UpdatedEntry)112 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_UpdatedEntry) {
113 KeyDescriptor kd = kDescriptor;
114 kd.transaction_id += 3;
115
116 ASSERT_EQ(OkStatus(), entries_.AddNewOrUpdateExisting(kd, 3210, 2000));
117
118 EXPECT_EQ(1u, entries_.present_entries());
119
120 for (const EntryMetadata& entry : entries_) {
121 EXPECT_EQ(3210u, entry.first_address());
122 EXPECT_EQ(kDescriptor.key_hash, entry.hash());
123 EXPECT_EQ(kDescriptor.transaction_id + 3, entry.transaction_id());
124 }
125 }
126
TEST_F(EmptyEntryCache,AddNewOrUpdateExisting_AddDuplicateEntry)127 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntry) {
128 ASSERT_EQ(OkStatus(),
129 entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
130 ASSERT_EQ(OkStatus(),
131 entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
132 ASSERT_EQ(OkStatus(),
133 entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));
134
135 // Duplicates beyond the redundancy are ignored.
136 ASSERT_EQ(OkStatus(),
137 entries_.AddNewOrUpdateExisting(kDescriptor, 9000, 2000));
138
139 EXPECT_EQ(1u, entries_.present_entries());
140
141 for (const EntryMetadata& entry : entries_) {
142 EXPECT_EQ(3u, entry.addresses().size());
143 EXPECT_EQ(1000u, entry.addresses()[0]);
144 EXPECT_EQ(3000u, entry.addresses()[1]);
145 EXPECT_EQ(7000u, entry.addresses()[2]);
146
147 EXPECT_EQ(kDescriptor.key_hash, entry.hash());
148 EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
149 }
150 }
151
TEST_F(EmptyEntryCache,AddNewOrUpdateExisting_AddDuplicateEntryInSameSector)152 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntryInSameSector) {
153 ASSERT_EQ(OkStatus(),
154 entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
155 EXPECT_EQ(Status::DataLoss(),
156 entries_.AddNewOrUpdateExisting(kDescriptor, 1950, 1000));
157
158 EXPECT_EQ(1u, entries_.present_entries());
159
160 for (const EntryMetadata& entry : entries_) {
161 EXPECT_EQ(1u, entry.addresses().size());
162 EXPECT_EQ(1000u, entry.addresses()[0]);
163
164 EXPECT_EQ(kDescriptor.key_hash, entry.hash());
165 EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
166 }
167 }
168
TEST_F(EmptyEntryCache,Iterator_MutableFromConst_CanModify)169 TEST_F(EmptyEntryCache, Iterator_MutableFromConst_CanModify) {
170 entries_.AddNew(kDescriptor, 1);
171 EntryCache::iterator it = static_cast<const EntryCache&>(entries_).begin();
172
173 static_assert(kRedundancy > 1);
174 it->AddNewAddress(1234);
175
176 EXPECT_EQ(1u, it->first_address());
177 EXPECT_EQ(1u, (*it).addresses()[0]);
178 EXPECT_EQ(1234u, it->addresses()[1]);
179 }
180
TEST_F(EmptyEntryCache,Iterator_Const)181 TEST_F(EmptyEntryCache, Iterator_Const) {
182 entries_.AddNew(kDescriptor, 99);
183 EntryCache::const_iterator it = entries_.cbegin();
184
185 EXPECT_EQ(99u, (*it).first_address());
186 EXPECT_EQ(99u, it->first_address());
187 }
188
TEST_F(EmptyEntryCache,Iterator_Const_CanBeAssignedFromMutable)189 TEST_F(EmptyEntryCache, Iterator_Const_CanBeAssignedFromMutable) {
190 entries_.AddNew(kDescriptor, 99);
191 EntryCache::const_iterator it = entries_.begin();
192
193 EXPECT_EQ(99u, (*it).first_address());
194 EXPECT_EQ(99u, it->first_address());
195 }
196
197 constexpr size_t kSectorSize = 64;
198 constexpr uint32_t kMagic = 0xa14ae726;
199 // For KVS entry magic value always use a random 32 bit integer rather than a
200 // human readable 4 bytes. See pw_kvs/format.h for more information.
201 constexpr auto kTheEntry =
202 bytes::Concat(uint32_t(kMagic), // magic
203 uint32_t(0), // checksum
204 uint8_t(0), // alignment (16 B)
205 uint8_t(sizeof(kTheKey) - 1), // key length
206 uint16_t(0), // value size
207 uint32_t(123), // transaction ID
208 bytes::String(kTheKey));
209 constexpr std::array<byte, kSectorSize - kTheEntry.size() % kSectorSize>
210 kPadding1{};
211 constexpr size_t kSize1 = kTheEntry.size() + kPadding1.size();
212
213 constexpr char kCollision1[] = "9FDC";
214 constexpr char kCollision2[] = "axzzK";
215
216 // For KVS entry magic value always use a random 32 bit integer rather than a
217 // human readable 4 bytes. See pw_kvs/format.h for more information.
218 constexpr auto kCollisionEntry =
219 bytes::Concat(uint32_t(kMagic), // magic
220 uint32_t(0), // checksum
221 uint8_t(0), // alignment (16 B)
222 uint8_t(sizeof(kCollision1) - 1), // key length
223 uint16_t(0), // value size
224 uint32_t(123), // transaction ID
225 bytes::String(kCollision1));
226 constexpr std::array<byte, kSectorSize - kCollisionEntry.size() % kSectorSize>
227 kPadding2{};
228 constexpr size_t kSize2 = kCollisionEntry.size() + kPadding2.size();
229
230 // For KVS entry magic value always use a random 32 bit integer rather than a
231 // human readable 4 bytes. See pw_kvs/format.h for more information.
232 constexpr auto kDeletedEntry =
233 bytes::Concat(uint32_t(kMagic), // magic
234 uint32_t(0), // checksum
235 uint8_t(0), // alignment (16 B)
236 uint8_t(sizeof("delorted") - 1), // key length
237 uint16_t(0xffff), // value size (deleted)
238 uint32_t(123), // transaction ID
239 bytes::String("delorted"));
240 constexpr std::array<byte, kSectorSize - kDeletedEntry.size() % kSectorSize>
241 kPadding3{};
242
243 // For KVS entry magic value always use a random 32 bit integer rather than a
244 // human readable 4 bytes. See pw_kvs/format.h for more information.
245 constexpr EntryFormat kFormat{.magic = uint32_t(kMagic), .checksum = nullptr};
246
247 class InitializedEntryCache : public EmptyEntryCache {
248 protected:
249 static_assert(Hash(kCollision1) == Hash(kCollision2));
250
InitializedEntryCache()251 InitializedEntryCache()
252 : flash_(bytes::Concat(kTheEntry,
253 kPadding1,
254 kTheEntry,
255 kPadding1,
256 kCollisionEntry,
257 kPadding2,
258 kDeletedEntry,
259 kPadding3)),
260 partition_(&flash_),
261 sectors_(sector_descriptors_, partition_, nullptr),
262 format_(kFormat) {
263 sectors_.Reset();
264 size_t address = 0;
265 auto entry = entries_.AddNew(kDescriptor, address);
266
267 address += kSize1;
268 entry.AddNewAddress(kSize1);
269
270 address += kSize1;
271 entries_.AddNew({.key_hash = Hash(kCollision1),
272 .transaction_id = 125,
273 .state = EntryState::kDeleted},
274 address);
275
276 address += kSize2;
277 entries_.AddNew({.key_hash = Hash("delorted"),
278 .transaction_id = 256,
279 .state = EntryState::kDeleted},
280 address);
281 }
282
CheckForCorruptSectors(SectorDescriptor * sector1=nullptr,SectorDescriptor * sector2=nullptr)283 void CheckForCorruptSectors(SectorDescriptor* sector1 = nullptr,
284 SectorDescriptor* sector2 = nullptr) {
285 for (const auto& sector : sectors_) {
286 bool expect_corrupt =
287 ((sector1 && §or == sector1) || (sector2 && §or == sector2));
288 EXPECT_EQ(expect_corrupt, sector.corrupt());
289 }
290 }
291
292 static constexpr size_t kTotalSectors = 128;
293 FakeFlashMemoryBuffer<kSectorSize, kTotalSectors> flash_;
294 FlashPartition partition_;
295
296 Vector<SectorDescriptor, kTotalSectors> sector_descriptors_;
297 Sectors sectors_;
298
299 EntryFormats format_;
300 };
301
TEST_F(InitializedEntryCache,EntryCounts)302 TEST_F(InitializedEntryCache, EntryCounts) {
303 EXPECT_EQ(3u, entries_.total_entries());
304 EXPECT_EQ(1u, entries_.present_entries());
305 EXPECT_EQ(kMaxEntries, entries_.max_entries());
306 }
307
TEST_F(InitializedEntryCache,Reset_ClearsEntryCounts)308 TEST_F(InitializedEntryCache, Reset_ClearsEntryCounts) {
309 entries_.Reset();
310
311 EXPECT_EQ(0u, entries_.total_entries());
312 EXPECT_EQ(0u, entries_.present_entries());
313 EXPECT_EQ(kMaxEntries, entries_.max_entries());
314 }
315
TEST_F(InitializedEntryCache,Find_PresentEntry)316 TEST_F(InitializedEntryCache, Find_PresentEntry) {
317 EntryMetadata metadata;
318
319 StatusWithSize result =
320 entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
321
322 ASSERT_EQ(OkStatus(), result.status());
323 EXPECT_EQ(0u, result.size());
324 EXPECT_EQ(Hash(kTheKey), metadata.hash());
325 EXPECT_EQ(EntryState::kValid, metadata.state());
326 CheckForCorruptSectors();
327 }
328
TEST_F(InitializedEntryCache,Find_PresentEntryWithSingleReadError)329 TEST_F(InitializedEntryCache, Find_PresentEntryWithSingleReadError) {
330 // Inject 2 read errors so that the initial key read and the follow-up full
331 // read of the first entry fail.
332 flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 2));
333
334 EntryMetadata metadata;
335
336 StatusWithSize result =
337 entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
338
339 ASSERT_EQ(OkStatus(), result.status());
340 EXPECT_EQ(1u, result.size());
341 EXPECT_EQ(Hash(kTheKey), metadata.hash());
342 EXPECT_EQ(EntryState::kValid, metadata.state());
343 CheckForCorruptSectors(§ors_.FromAddress(0));
344 }
345
TEST_F(InitializedEntryCache,Find_PresentEntryWithMultiReadError)346 TEST_F(InitializedEntryCache, Find_PresentEntryWithMultiReadError) {
347 flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 4));
348
349 EntryMetadata metadata;
350
351 StatusWithSize result =
352 entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
353
354 ASSERT_EQ(Status::DataLoss(), result.status());
355 EXPECT_EQ(1u, result.size());
356 CheckForCorruptSectors(§ors_.FromAddress(0),
357 §ors_.FromAddress(kSize1));
358 }
359
TEST_F(InitializedEntryCache,Find_DeletedEntry)360 TEST_F(InitializedEntryCache, Find_DeletedEntry) {
361 EntryMetadata metadata;
362
363 StatusWithSize result =
364 entries_.Find(partition_, sectors_, format_, "delorted", &metadata);
365
366 ASSERT_EQ(OkStatus(), result.status());
367 EXPECT_EQ(0u, result.size());
368 EXPECT_EQ(Hash("delorted"), metadata.hash());
369 EXPECT_EQ(EntryState::kDeleted, metadata.state());
370 CheckForCorruptSectors();
371 }
372
TEST_F(InitializedEntryCache,Find_MissingEntry)373 TEST_F(InitializedEntryCache, Find_MissingEntry) {
374 EntryMetadata metadata;
375
376 StatusWithSize result =
377 entries_.Find(partition_, sectors_, format_, "3.141", &metadata);
378
379 ASSERT_EQ(Status::NotFound(), result.status());
380 EXPECT_EQ(0u, result.size());
381 CheckForCorruptSectors();
382 }
383
TEST_F(InitializedEntryCache,Find_Collision)384 TEST_F(InitializedEntryCache, Find_Collision) {
385 EntryMetadata metadata;
386
387 StatusWithSize result =
388 entries_.Find(partition_, sectors_, format_, kCollision2, &metadata);
389 EXPECT_EQ(Status::AlreadyExists(), result.status());
390 EXPECT_EQ(0u, result.size());
391 CheckForCorruptSectors();
392 }
393
394 } // namespace
395 } // namespace pw::kvs::internal
396