1 /*
2  * SPDX-FileCopyrightText: 2015-2022 Espressif Systems (Shanghai) CO LTD
3  *
4  * SPDX-License-Identifier: Apache-2.0
5  */
6 #include "nvs_page.hpp"
7 #include <esp_rom_crc.h>
8 #include <cstdio>
9 #include <cstring>
10 
11 namespace nvs
12 {
13 
Page()14 Page::Page() : mPartition(nullptr) { }
15 
calculateCrc32()16 uint32_t Page::Header::calculateCrc32()
17 {
18     return esp_rom_crc32_le(0xffffffff,
19                     reinterpret_cast<uint8_t*>(this) + offsetof(Header, mSeqNumber),
20                     offsetof(Header, mCrc32) - offsetof(Header, mSeqNumber));
21 }
22 
load(Partition * partition,uint32_t sectorNumber)23 esp_err_t Page::load(Partition *partition, uint32_t sectorNumber)
24 {
25     if (partition == nullptr) {
26         return ESP_ERR_INVALID_ARG;
27     }
28 
29     mPartition = partition;
30     mBaseAddress = sectorNumber * SEC_SIZE;
31     mUsedEntryCount = 0;
32     mErasedEntryCount = 0;
33 
34     Header header;
35     auto rc = mPartition->read_raw(mBaseAddress, &header, sizeof(header));
36     if (rc != ESP_OK) {
37         mState = PageState::INVALID;
38         return rc;
39     }
40     if (header.mState == PageState::UNINITIALIZED) {
41         mState = header.mState;
42         // check if the whole page is really empty
43         // reading the whole page takes ~40 times less than erasing it
44         const int BLOCK_SIZE = 128;
45         uint32_t* block = new (std::nothrow) uint32_t[BLOCK_SIZE];
46 
47         if (!block) return ESP_ERR_NO_MEM;
48 
49         for (uint32_t i = 0; i < SPI_FLASH_SEC_SIZE; i += 4 * BLOCK_SIZE) {
50             rc = mPartition->read_raw(mBaseAddress + i, block, 4 * BLOCK_SIZE);
51             if (rc != ESP_OK) {
52                 mState = PageState::INVALID;
53                 delete[] block;
54                 return rc;
55             }
56             if (std::any_of(block, block + BLOCK_SIZE, [](uint32_t val) -> bool { return val != 0xffffffff; })) {
57                 // page isn't as empty after all, mark it as corrupted
58                 mState = PageState::CORRUPT;
59                 break;
60             }
61         }
62         delete[] block;
63     } else if (header.mCrc32 != header.calculateCrc32()) {
64         header.mState = PageState::CORRUPT;
65     } else {
66         mState = header.mState;
67         mSeqNumber = header.mSeqNumber;
68         if(header.mVersion < NVS_VERSION) {
69             return ESP_ERR_NVS_NEW_VERSION_FOUND;
70         } else {
71             mVersion = header.mVersion;
72         }
73     }
74 
75     switch (mState) {
76     case PageState::UNINITIALIZED:
77         break;
78 
79     case PageState::FULL:
80     case PageState::ACTIVE:
81     case PageState::FREEING:
82         mLoadEntryTable();
83         break;
84 
85     default:
86         mState = PageState::CORRUPT;
87         break;
88     }
89 
90     return ESP_OK;
91 }
92 
writeEntry(const Item & item)93 esp_err_t Page::writeEntry(const Item& item)
94 {
95     esp_err_t err;
96 
97     err = mPartition->write(getEntryAddress(mNextFreeEntry), &item, sizeof(item));
98 
99     if (err != ESP_OK) {
100         mState = PageState::INVALID;
101         return err;
102     }
103 
104     err = alterEntryState(mNextFreeEntry, EntryState::WRITTEN);
105     if (err != ESP_OK) {
106         return err;
107     }
108 
109     if (mFirstUsedEntry == INVALID_ENTRY) {
110         mFirstUsedEntry = mNextFreeEntry;
111     }
112 
113     ++mUsedEntryCount;
114     ++mNextFreeEntry;
115 
116     return ESP_OK;
117 }
118 
writeEntryData(const uint8_t * data,size_t size)119 esp_err_t Page::writeEntryData(const uint8_t* data, size_t size)
120 {
121     assert(size % ENTRY_SIZE == 0);
122     assert(mNextFreeEntry != INVALID_ENTRY);
123     assert(mFirstUsedEntry != INVALID_ENTRY);
124     const uint16_t count = size / ENTRY_SIZE;
125 
126     const uint8_t* buf = data;
127 
128 #if !defined LINUX_TARGET
129     // TODO: check whether still necessary with esp_partition* API
130     /* On the ESP32, data can come from DROM, which is not accessible by spi_flash_write
131      * function. To work around this, we copy the data to heap if it came from DROM.
132      * Hopefully this won't happen very often in practice. For data from DRAM, we should
133      * still be able to write it to flash directly.
134      * TODO: figure out how to make this platform-specific check nicer (probably by introducing
135      * a platform-specific flash layer).
136      */
137     if ((uint32_t) data < 0x3ff00000) {
138         buf = (uint8_t*) malloc(size);
139         if (!buf) {
140             return ESP_ERR_NO_MEM;
141         }
142         memcpy((void*)buf, data, size);
143     }
144 #endif // ! LINUX_TARGET
145 
146     auto rc = mPartition->write(getEntryAddress(mNextFreeEntry), buf, size);
147 
148 #if !defined LINUX_TARGET
149     if (buf != data) {
150         free((void*)buf);
151     }
152 #endif // ! LINUX_TARGET
153     if (rc != ESP_OK) {
154         mState = PageState::INVALID;
155         return rc;
156     }
157     auto err = alterEntryRangeState(mNextFreeEntry, mNextFreeEntry + count, EntryState::WRITTEN);
158     if (err != ESP_OK) {
159         return err;
160     }
161     mUsedEntryCount += count;
162     mNextFreeEntry += count;
163     return ESP_OK;
164 }
165 
writeItem(uint8_t nsIndex,ItemType datatype,const char * key,const void * data,size_t dataSize,uint8_t chunkIdx)166 esp_err_t Page::writeItem(uint8_t nsIndex, ItemType datatype, const char* key, const void* data, size_t dataSize, uint8_t chunkIdx)
167 {
168     Item item;
169     esp_err_t err;
170 
171     if (mState == PageState::INVALID) {
172         return ESP_ERR_NVS_INVALID_STATE;
173     }
174 
175     if (mState == PageState::UNINITIALIZED) {
176         err = initialize();
177         if (err != ESP_OK) {
178             return err;
179         }
180     }
181 
182     if (mState == PageState::FULL) {
183         return ESP_ERR_NVS_PAGE_FULL;
184     }
185 
186     const size_t keySize = strlen(key);
187     if (keySize > Item::MAX_KEY_LENGTH) {
188         return ESP_ERR_NVS_KEY_TOO_LONG;
189     }
190 
191     if (dataSize > Page::CHUNK_MAX_SIZE) {
192         return ESP_ERR_NVS_VALUE_TOO_LONG;
193     }
194 
195     if ((!isVariableLengthType(datatype)) && dataSize > 8) {
196         return ESP_ERR_INVALID_ARG;
197     }
198 
199     size_t totalSize = ENTRY_SIZE;
200     size_t entriesCount = 1;
201     if (isVariableLengthType(datatype)) {
202         size_t roundedSize = (dataSize + ENTRY_SIZE - 1) & ~(ENTRY_SIZE - 1);
203         totalSize += roundedSize;
204         entriesCount += roundedSize / ENTRY_SIZE;
205     }
206 
207     // primitive types should fit into one entry
208     assert(totalSize == ENTRY_SIZE ||
209        isVariableLengthType(datatype));
210 
211     if (mNextFreeEntry == INVALID_ENTRY || mNextFreeEntry + entriesCount > ENTRY_COUNT) {
212         // page will not fit this amount of data
213         return ESP_ERR_NVS_PAGE_FULL;
214     }
215 
216     // write first item
217     size_t span = (totalSize + ENTRY_SIZE - 1) / ENTRY_SIZE;
218     item = Item(nsIndex, datatype, span, key, chunkIdx);
219     err = mHashList.insert(item, mNextFreeEntry);
220 
221     if (err != ESP_OK) {
222         return err;
223     }
224 
225     if (!isVariableLengthType(datatype)) {
226         memcpy(item.data, data, dataSize);
227         item.crc32 = item.calculateCrc32();
228         err = writeEntry(item);
229         if (err != ESP_OK) {
230             return err;
231         }
232     } else {
233         const uint8_t* src = reinterpret_cast<const uint8_t*>(data);
234         item.varLength.dataCrc32 = Item::calculateCrc32(src, dataSize);
235         item.varLength.dataSize = dataSize;
236         item.varLength.reserved = 0xffff;
237         item.crc32 = item.calculateCrc32();
238         err = writeEntry(item);
239         if (err != ESP_OK) {
240             return err;
241         }
242 
243         size_t rest = dataSize % ENTRY_SIZE;
244         size_t left = dataSize - rest;
245         if (left > 0) {
246             err = writeEntryData(static_cast<const uint8_t*>(data), left);
247             if (err != ESP_OK) {
248                 return err;
249             }
250         }
251 
252         size_t tail = rest;
253         if (tail > 0) {
254             std::fill_n(item.rawData, ENTRY_SIZE, 0xff);
255             memcpy(item.rawData, static_cast<const uint8_t*>(data) + left, tail);
256             err = writeEntry(item);
257             if (err != ESP_OK) {
258                 return err;
259             }
260         }
261 
262     }
263     return ESP_OK;
264 }
265 
readItem(uint8_t nsIndex,ItemType datatype,const char * key,void * data,size_t dataSize,uint8_t chunkIdx,VerOffset chunkStart)266 esp_err_t Page::readItem(uint8_t nsIndex, ItemType datatype, const char* key, void* data, size_t dataSize, uint8_t chunkIdx, VerOffset chunkStart)
267 {
268     size_t index = 0;
269     Item item;
270 
271     if (mState == PageState::INVALID) {
272         return ESP_ERR_NVS_INVALID_STATE;
273     }
274 
275     esp_err_t rc = findItem(nsIndex, datatype, key, index, item, chunkIdx, chunkStart);
276     if (rc != ESP_OK) {
277         return rc;
278     }
279 
280     if (!isVariableLengthType(datatype)) {
281         if (dataSize != getAlignmentForType(datatype)) {
282             return ESP_ERR_NVS_TYPE_MISMATCH;
283         }
284 
285         memcpy(data, item.data, dataSize);
286         return ESP_OK;
287     }
288 
289     if (dataSize < static_cast<size_t>(item.varLength.dataSize)) {
290         return ESP_ERR_NVS_INVALID_LENGTH;
291     }
292 
293     uint8_t* dst = reinterpret_cast<uint8_t*>(data);
294     size_t left = item.varLength.dataSize;
295     for (size_t i = index + 1; i < index + item.span; ++i) {
296         Item ditem;
297         rc = readEntry(i, ditem);
298         if (rc != ESP_OK) {
299             return rc;
300         }
301         size_t willCopy = ENTRY_SIZE;
302         willCopy = (left < willCopy)?left:willCopy;
303         memcpy(dst, ditem.rawData, willCopy);
304         left -= willCopy;
305         dst += willCopy;
306     }
307     if (Item::calculateCrc32(reinterpret_cast<uint8_t*>(data), item.varLength.dataSize) != item.varLength.dataCrc32) {
308         rc = eraseEntryAndSpan(index);
309         if (rc != ESP_OK) {
310             return rc;
311         }
312         return ESP_ERR_NVS_NOT_FOUND;
313     }
314     return ESP_OK;
315 }
316 
cmpItem(uint8_t nsIndex,ItemType datatype,const char * key,const void * data,size_t dataSize,uint8_t chunkIdx,VerOffset chunkStart)317 esp_err_t Page::cmpItem(uint8_t nsIndex, ItemType datatype, const char* key, const void* data, size_t dataSize, uint8_t chunkIdx, VerOffset chunkStart)
318 {
319     size_t index = 0;
320     Item item;
321 
322     if (mState == PageState::INVALID) {
323         return ESP_ERR_NVS_INVALID_STATE;
324     }
325 
326     esp_err_t rc = findItem(nsIndex, datatype, key, index, item, chunkIdx, chunkStart);
327     if (rc != ESP_OK) {
328         return rc;
329     }
330 
331     if (!isVariableLengthType(datatype)) {
332         if (dataSize != getAlignmentForType(datatype)) {
333             return ESP_ERR_NVS_TYPE_MISMATCH;
334         }
335 
336         if (memcmp(data, item.data, dataSize)) {
337             return ESP_ERR_NVS_CONTENT_DIFFERS;
338         }
339         return ESP_OK;
340     }
341 
342     if (dataSize < static_cast<size_t>(item.varLength.dataSize)) {
343         return ESP_ERR_NVS_INVALID_LENGTH;
344     }
345 
346     const uint8_t* dst = reinterpret_cast<const uint8_t*>(data);
347     size_t left = item.varLength.dataSize;
348     for (size_t i = index + 1; i < index + item.span; ++i) {
349         Item ditem;
350         rc = readEntry(i, ditem);
351         if (rc != ESP_OK) {
352             return rc;
353         }
354         size_t willCopy = ENTRY_SIZE;
355         willCopy = (left < willCopy)?left:willCopy;
356         if (memcmp(dst, ditem.rawData, willCopy)) {
357             return ESP_ERR_NVS_CONTENT_DIFFERS;
358         }
359         left -= willCopy;
360         dst += willCopy;
361     }
362     if (Item::calculateCrc32(reinterpret_cast<const uint8_t*>(data), item.varLength.dataSize) != item.varLength.dataCrc32) {
363         return ESP_ERR_NVS_NOT_FOUND;
364     }
365 
366     return ESP_OK;
367 }
368 
eraseItem(uint8_t nsIndex,ItemType datatype,const char * key,uint8_t chunkIdx,VerOffset chunkStart)369 esp_err_t Page::eraseItem(uint8_t nsIndex, ItemType datatype, const char* key, uint8_t chunkIdx, VerOffset chunkStart)
370 {
371     size_t index = 0;
372     Item item;
373     esp_err_t rc = findItem(nsIndex, datatype, key, index, item, chunkIdx, chunkStart);
374     if (rc != ESP_OK) {
375         return rc;
376     }
377     return eraseEntryAndSpan(index);
378 }
379 
findItem(uint8_t nsIndex,ItemType datatype,const char * key,uint8_t chunkIdx,VerOffset chunkStart)380 esp_err_t Page::findItem(uint8_t nsIndex, ItemType datatype, const char* key, uint8_t chunkIdx, VerOffset chunkStart)
381 {
382     size_t index = 0;
383     Item item;
384     return findItem(nsIndex, datatype, key, index, item, chunkIdx, chunkStart);
385 }
386 
eraseEntryAndSpan(size_t index)387 esp_err_t Page::eraseEntryAndSpan(size_t index)
388 {
389     uint32_t seq_num;
390     getSeqNumber(seq_num);
391     auto state = mEntryTable.get(index);
392 
393     size_t span = 1;
394     if (state == EntryState::WRITTEN) {
395         Item item;
396         auto rc = readEntry(index, item);
397         if (rc != ESP_OK) {
398             return rc;
399         }
400         if (item.calculateCrc32() != item.crc32) {
401             mHashList.erase(index);
402             rc = alterEntryState(index, EntryState::ERASED);
403             --mUsedEntryCount;
404             ++mErasedEntryCount;
405             if (rc != ESP_OK) {
406                 return rc;
407             }
408         } else {
409             mHashList.erase(index);
410             span = item.span;
411             for (ptrdiff_t i = index + span - 1; i >= static_cast<ptrdiff_t>(index); --i) {
412                 if (mEntryTable.get(i) == EntryState::WRITTEN) {
413                     --mUsedEntryCount;
414                 }
415                 ++mErasedEntryCount;
416             }
417             if (span == 1) {
418                 rc = alterEntryState(index, EntryState::ERASED);
419             } else {
420                 rc = alterEntryRangeState(index, index + span, EntryState::ERASED);
421             }
422             if (rc != ESP_OK) {
423                 return rc;
424             }
425         }
426     } else {
427         auto rc = alterEntryState(index, EntryState::ERASED);
428         if (rc != ESP_OK) {
429             return rc;
430         }
431     }
432 
433     if (index == mFirstUsedEntry) {
434         updateFirstUsedEntry(index, span);
435     }
436 
437     if (index + span > mNextFreeEntry) {
438         mNextFreeEntry = index + span;
439     }
440 
441     return ESP_OK;
442 }
443 
updateFirstUsedEntry(size_t index,size_t span)444 void Page::updateFirstUsedEntry(size_t index, size_t span)
445 {
446     assert(index == mFirstUsedEntry);
447     mFirstUsedEntry = INVALID_ENTRY;
448     size_t end = mNextFreeEntry;
449     if (end > ENTRY_COUNT) {
450         end = ENTRY_COUNT;
451     }
452     for (size_t i = index + span; i < end; ++i) {
453         if (mEntryTable.get(i) == EntryState::WRITTEN) {
454             mFirstUsedEntry = i;
455             break;
456         }
457     }
458 }
459 
copyItems(Page & other)460 esp_err_t Page::copyItems(Page& other)
461 {
462     if (mFirstUsedEntry == INVALID_ENTRY) {
463         return ESP_ERR_NVS_NOT_FOUND;
464     }
465 
466     if (other.mState == PageState::UNINITIALIZED) {
467         auto err = other.initialize();
468         if (err != ESP_OK) {
469             return err;
470         }
471     }
472 
473     Item entry;
474     size_t readEntryIndex = mFirstUsedEntry;
475 
476     while (readEntryIndex < ENTRY_COUNT) {
477 
478         if (mEntryTable.get(readEntryIndex) != EntryState::WRITTEN) {
479             assert(readEntryIndex != mFirstUsedEntry);
480             readEntryIndex++;
481             continue;
482         }
483         auto err = readEntry(readEntryIndex, entry);
484         if (err != ESP_OK) {
485             return err;
486         }
487 
488         err = other.mHashList.insert(entry, other.mNextFreeEntry);
489         if (err != ESP_OK) {
490             return err;
491         }
492 
493         err = other.writeEntry(entry);
494         if (err != ESP_OK) {
495             return err;
496         }
497         size_t span = entry.span;
498         size_t end = readEntryIndex + span;
499 
500         assert(end <= ENTRY_COUNT);
501 
502         for (size_t i = readEntryIndex + 1; i < end; ++i) {
503             readEntry(i, entry);
504             err = other.writeEntry(entry);
505             if (err != ESP_OK) {
506                 return err;
507             }
508         }
509         readEntryIndex = end;
510 
511     }
512     return ESP_OK;
513 }
514 
mLoadEntryTable()515 esp_err_t Page::mLoadEntryTable()
516 {
517     // for states where we actually care about data in the page, read entry state table
518     if (mState == PageState::ACTIVE ||
519             mState == PageState::FULL ||
520             mState == PageState::FREEING) {
521         auto rc = mPartition->read_raw(mBaseAddress + ENTRY_TABLE_OFFSET, mEntryTable.data(),
522                                  mEntryTable.byteSize());
523         if (rc != ESP_OK) {
524             mState = PageState::INVALID;
525             return rc;
526         }
527     }
528 
529     mErasedEntryCount = 0;
530     mUsedEntryCount = 0;
531     for (size_t i = 0; i < ENTRY_COUNT; ++i) {
532         auto s = mEntryTable.get(i);
533         if (s == EntryState::WRITTEN) {
534             if (mFirstUsedEntry == INVALID_ENTRY) {
535                 mFirstUsedEntry = i;
536             }
537             ++mUsedEntryCount;
538         } else if (s == EntryState::ERASED) {
539             ++mErasedEntryCount;
540         }
541     }
542 
543     // for PageState::ACTIVE, we may have more data written to this page
544     // as such, we need to figure out where the first unused entry is
545     if (mState == PageState::ACTIVE) {
546         for (size_t i = 0; i < ENTRY_COUNT; ++i) {
547             if (mEntryTable.get(i) == EntryState::EMPTY) {
548                 mNextFreeEntry = i;
549                 break;
550             }
551         }
552 
553         // however, if power failed after some data was written into the entry.
554         // but before the entry state table was altered, the entry locacted via
555         // entry state table may actually be half-written.
556         // this is easy to check by reading EntryHeader (i.e. first word)
557         while (mNextFreeEntry < ENTRY_COUNT) {
558             uint32_t entryAddress = getEntryAddress(mNextFreeEntry);
559             uint32_t header;
560             auto rc = mPartition->read_raw(entryAddress, &header, sizeof(header));
561             if (rc != ESP_OK) {
562                 mState = PageState::INVALID;
563                 return rc;
564             }
565             if (header != 0xffffffff) {
566                 auto oldState = mEntryTable.get(mNextFreeEntry);
567                 auto err = alterEntryState(mNextFreeEntry, EntryState::ERASED);
568                 if (err != ESP_OK) {
569                     mState = PageState::INVALID;
570                     return err;
571                 }
572                 ++mNextFreeEntry;
573                 if (oldState == EntryState::WRITTEN) {
574                     --mUsedEntryCount;
575                 }
576                 ++mErasedEntryCount;
577             }
578             else {
579                 break;
580             }
581         }
582 
583         // check that all variable-length items are written or erased fully
584         Item item;
585         size_t lastItemIndex = INVALID_ENTRY;
586         size_t end = mNextFreeEntry;
587         if (end > ENTRY_COUNT) {
588             end = ENTRY_COUNT;
589         }
590         size_t span;
591         for (size_t i = 0; i < end; i += span) {
592             span = 1;
593             if (mEntryTable.get(i) == EntryState::ERASED) {
594                 lastItemIndex = INVALID_ENTRY;
595                 continue;
596             }
597 
598             if (mEntryTable.get(i) == EntryState::ILLEGAL) {
599                 lastItemIndex = INVALID_ENTRY;
600                 auto err = eraseEntryAndSpan(i);
601                 if (err != ESP_OK) {
602                     mState = PageState::INVALID;
603                     return err;
604                 }
605                 continue;
606             }
607 
608             lastItemIndex = i;
609 
610             auto err = readEntry(i, item);
611             if (err != ESP_OK) {
612                 mState = PageState::INVALID;
613                 return err;
614             }
615 
616             if (item.crc32 != item.calculateCrc32()) {
617                 err = eraseEntryAndSpan(i);
618                 if (err != ESP_OK) {
619                     mState = PageState::INVALID;
620                     return err;
621                 }
622                 continue;
623             }
624 
625             err = mHashList.insert(item, i);
626             if (err != ESP_OK) {
627                 mState = PageState::INVALID;
628                 return err;
629             }
630 
631             // search for potential duplicate item
632             size_t duplicateIndex = mHashList.find(0, item);
633 
634             if (isVariableLengthType(item.datatype)) {
635                 span = item.span;
636                 bool needErase = false;
637                 for (size_t j = i; j < i + span; ++j) {
638                     if (mEntryTable.get(j) != EntryState::WRITTEN) {
639                         needErase = true;
640                         lastItemIndex = INVALID_ENTRY;
641                         break;
642                     }
643                 }
644                 if (needErase) {
645                     eraseEntryAndSpan(i);
646                     continue;
647                 }
648             }
649 
650             /* Note that logic for duplicate detections works fine even
651              * when old-format blob is present along with new-format blob-index
652              * for same key on active page. Since datatype is not used in hash calculation,
653              * old-format blob will be removed.*/
654             if (duplicateIndex < i) {
655                 eraseEntryAndSpan(duplicateIndex);
656             }
657         }
658 
659         // check that last item is not duplicate
660         if (lastItemIndex != INVALID_ENTRY) {
661             size_t findItemIndex = 0;
662             Item dupItem;
663             if (findItem(item.nsIndex, item.datatype, item.key, findItemIndex, dupItem) == ESP_OK) {
664                 if (findItemIndex < lastItemIndex) {
665                     auto err = eraseEntryAndSpan(findItemIndex);
666                     if (err != ESP_OK) {
667                         mState = PageState::INVALID;
668                         return err;
669                     }
670                 }
671             }
672         }
673     } else if (mState == PageState::FULL || mState == PageState::FREEING) {
674         // We have already filled mHashList for page in active state.
675         // Do the same for the case when page is in full or freeing state.
676         Item item;
677         for (size_t i = mFirstUsedEntry; i < ENTRY_COUNT; ++i) {
678             if (mEntryTable.get(i) != EntryState::WRITTEN) {
679                 continue;
680             }
681 
682             auto err = readEntry(i, item);
683             if (err != ESP_OK) {
684                 mState = PageState::INVALID;
685                 return err;
686             }
687 
688             if (item.crc32 != item.calculateCrc32()) {
689                 err = eraseEntryAndSpan(i);
690                 if (err != ESP_OK) {
691                     mState = PageState::INVALID;
692                     return err;
693                 }
694                 continue;
695             }
696 
697             assert(item.span > 0);
698 
699             err = mHashList.insert(item, i);
700             if (err != ESP_OK) {
701                 mState = PageState::INVALID;
702                 return err;
703             }
704 
705             size_t span = item.span;
706 
707             if (isVariableLengthType(item.datatype)) {
708                 for (size_t j = i + 1; j < i + span; ++j) {
709                     if (mEntryTable.get(j) != EntryState::WRITTEN) {
710                         eraseEntryAndSpan(i);
711                         break;
712                     }
713                 }
714             }
715 
716             i += span - 1;
717         }
718 
719     }
720 
721     return ESP_OK;
722 }
723 
724 
initialize()725 esp_err_t Page::initialize()
726 {
727     assert(mState == PageState::UNINITIALIZED);
728     mState = PageState::ACTIVE;
729     Header header;
730     header.mState = mState;
731     header.mSeqNumber = mSeqNumber;
732     header.mVersion = mVersion;
733     header.mCrc32 = header.calculateCrc32();
734 
735     auto rc = mPartition->write_raw(mBaseAddress, &header, sizeof(header));
736     if (rc != ESP_OK) {
737         mState = PageState::INVALID;
738         return rc;
739     }
740 
741     mNextFreeEntry = 0;
742     std::fill_n(mEntryTable.data(), mEntryTable.byteSize() / sizeof(uint32_t), 0xffffffff);
743     return ESP_OK;
744 }
745 
alterEntryState(size_t index,EntryState state)746 esp_err_t Page::alterEntryState(size_t index, EntryState state)
747 {
748     assert(index < ENTRY_COUNT);
749     mEntryTable.set(index, state);
750     size_t wordToWrite = mEntryTable.getWordIndex(index);
751     uint32_t word = mEntryTable.data()[wordToWrite];
752     auto rc = mPartition->write_raw(mBaseAddress + ENTRY_TABLE_OFFSET + static_cast<uint32_t>(wordToWrite) * 4,
753             &word, sizeof(word));
754     if (rc != ESP_OK) {
755         mState = PageState::INVALID;
756         return rc;
757     }
758     return ESP_OK;
759 }
760 
alterEntryRangeState(size_t begin,size_t end,EntryState state)761 esp_err_t Page::alterEntryRangeState(size_t begin, size_t end, EntryState state)
762 {
763     assert(end <= ENTRY_COUNT);
764     assert(end > begin);
765     size_t wordIndex = mEntryTable.getWordIndex(end - 1);
766     for (ptrdiff_t i = end - 1; i >= static_cast<ptrdiff_t>(begin); --i) {
767         mEntryTable.set(i, state);
768         size_t nextWordIndex;
769         if (i == static_cast<ptrdiff_t>(begin)) {
770             nextWordIndex = (size_t) -1;
771         } else {
772             nextWordIndex = mEntryTable.getWordIndex(i - 1);
773         }
774         if (nextWordIndex != wordIndex) {
775             uint32_t word = mEntryTable.data()[wordIndex];
776             auto rc = mPartition->write_raw(mBaseAddress + ENTRY_TABLE_OFFSET + static_cast<uint32_t>(wordIndex) * 4,
777                     &word, 4);
778             if (rc != ESP_OK) {
779                 return rc;
780             }
781         }
782         wordIndex = nextWordIndex;
783     }
784     return ESP_OK;
785 }
786 
alterPageState(PageState state)787 esp_err_t Page::alterPageState(PageState state)
788 {
789     uint32_t state_val = static_cast<uint32_t>(state);
790     auto rc = mPartition->write_raw(mBaseAddress, &state_val, sizeof(state));
791     if (rc != ESP_OK) {
792         mState = PageState::INVALID;
793         return rc;
794     }
795     mState = (PageState) state;
796     return ESP_OK;
797 }
798 
readEntry(size_t index,Item & dst) const799 esp_err_t Page::readEntry(size_t index, Item& dst) const
800 {
801     auto rc = mPartition->read(getEntryAddress(index), &dst, sizeof(dst));
802     if (rc != ESP_OK) {
803         return rc;
804     }
805     return ESP_OK;
806 }
807 
findItem(uint8_t nsIndex,ItemType datatype,const char * key,size_t & itemIndex,Item & item,uint8_t chunkIdx,VerOffset chunkStart)808 esp_err_t Page::findItem(uint8_t nsIndex, ItemType datatype, const char* key, size_t &itemIndex, Item& item, uint8_t chunkIdx, VerOffset chunkStart)
809 {
810     if (mState == PageState::CORRUPT || mState == PageState::INVALID || mState == PageState::UNINITIALIZED) {
811         return ESP_ERR_NVS_NOT_FOUND;
812     }
813 
814     size_t findBeginIndex = itemIndex;
815     if (findBeginIndex >= ENTRY_COUNT) {
816         return ESP_ERR_NVS_NOT_FOUND;
817     }
818 
819     size_t start = mFirstUsedEntry;
820     if (findBeginIndex > mFirstUsedEntry && findBeginIndex < ENTRY_COUNT) {
821         start = findBeginIndex;
822     }
823 
824     size_t end = mNextFreeEntry;
825     if (end > ENTRY_COUNT) {
826         end = ENTRY_COUNT;
827     }
828 
829     if (nsIndex != NS_ANY && datatype != ItemType::ANY && key != NULL) {
830         size_t cachedIndex = mHashList.find(start, Item(nsIndex, datatype, 0, key, chunkIdx));
831         if (cachedIndex < ENTRY_COUNT) {
832             start = cachedIndex;
833         } else {
834             return ESP_ERR_NVS_NOT_FOUND;
835         }
836     }
837 
838     size_t next;
839     for (size_t i = start; i < end; i = next) {
840         next = i + 1;
841         if (mEntryTable.get(i) != EntryState::WRITTEN) {
842             continue;
843         }
844 
845         auto rc = readEntry(i, item);
846         if (rc != ESP_OK) {
847             mState = PageState::INVALID;
848             return rc;
849         }
850 
851         auto crc32 = item.calculateCrc32();
852         if (item.crc32 != crc32) {
853             rc = eraseEntryAndSpan(i);
854             if (rc != ESP_OK) {
855                 mState = PageState::INVALID;
856                 return rc;
857             }
858             continue;
859         }
860 
861         if (isVariableLengthType(item.datatype)) {
862             next = i + item.span;
863         }
864 
865         if (nsIndex != NS_ANY && item.nsIndex != nsIndex) {
866             continue;
867         }
868 
869         if (key != nullptr && strncmp(key, item.key, Item::MAX_KEY_LENGTH) != 0) {
870             continue;
871         }
872         /* For blob data, chunkIndex should match*/
873         if (chunkIdx != CHUNK_ANY
874                 && datatype == ItemType::BLOB_DATA
875                 && item.chunkIndex != chunkIdx) {
876             continue;
877         }
878         /* Blob-index will match the <ns,key> with blob data.
879          * Skip data chunks when searching for blob index*/
880         if (datatype == ItemType::BLOB_IDX
881                 && item.chunkIndex != CHUNK_ANY) {
882             continue;
883         }
884         /* Match the version for blob-index*/
885         if (datatype == ItemType::BLOB_IDX
886                 && chunkStart != VerOffset::VER_ANY
887                 && item.blobIndex.chunkStart != chunkStart) {
888             continue;
889         }
890 
891 
892         if (datatype != ItemType::ANY && item.datatype != datatype) {
893             if (key == nullptr && nsIndex == NS_ANY && chunkIdx == CHUNK_ANY) {
894                 continue; // continue for bruteforce search on blob indices.
895             }
896             itemIndex = i;
897             return ESP_ERR_NVS_TYPE_MISMATCH;
898         }
899 
900         itemIndex = i;
901 
902         return ESP_OK;
903     }
904 
905     return ESP_ERR_NVS_NOT_FOUND;
906 }
907 
getSeqNumber(uint32_t & seqNumber) const908 esp_err_t Page::getSeqNumber(uint32_t& seqNumber) const
909 {
910     if (mState != PageState::UNINITIALIZED && mState != PageState::INVALID && mState != PageState::CORRUPT) {
911         seqNumber = mSeqNumber;
912         return ESP_OK;
913     }
914     return ESP_ERR_NVS_NOT_INITIALIZED;
915 }
916 
917 
setSeqNumber(uint32_t seqNumber)918 esp_err_t Page::setSeqNumber(uint32_t seqNumber)
919 {
920     if (mState != PageState::UNINITIALIZED) {
921         return ESP_ERR_NVS_INVALID_STATE;
922     }
923     mSeqNumber = seqNumber;
924     return ESP_OK;
925 }
926 
setVersion(uint8_t ver)927 esp_err_t Page::setVersion(uint8_t ver)
928 {
929     if (mState != PageState::UNINITIALIZED) {
930         return ESP_ERR_NVS_INVALID_STATE;
931     }
932     mVersion = ver;
933     return ESP_OK;
934 }
935 
erase()936 esp_err_t Page::erase()
937 {
938     auto rc = mPartition->erase_range(mBaseAddress, SPI_FLASH_SEC_SIZE);
939     if (rc != ESP_OK) {
940         mState = PageState::INVALID;
941         return rc;
942     }
943     mUsedEntryCount = 0;
944     mErasedEntryCount = 0;
945     mFirstUsedEntry = INVALID_ENTRY;
946     mNextFreeEntry = INVALID_ENTRY;
947     mState = PageState::UNINITIALIZED;
948     mHashList.clear();
949     return ESP_OK;
950 }
951 
markFreeing()952 esp_err_t Page::markFreeing()
953 {
954     if (mState != PageState::FULL && mState != PageState::ACTIVE) {
955         return ESP_ERR_NVS_INVALID_STATE;
956     }
957     return alterPageState(PageState::FREEING);
958 }
959 
markFull()960 esp_err_t Page::markFull()
961 {
962     if (mState != PageState::ACTIVE) {
963         return ESP_ERR_NVS_INVALID_STATE;
964     }
965     return alterPageState(PageState::FULL);
966 }
967 
getVarDataTailroom() const968 size_t Page::getVarDataTailroom() const
969 {
970     if (mState == PageState::UNINITIALIZED) {
971         return CHUNK_MAX_SIZE;
972     } else if (mState == PageState::FULL) {
973         return 0;
974     }
975     /* Skip one entry for blob data item precessing the data */
976     return ((mNextFreeEntry < (ENTRY_COUNT-1)) ? ((ENTRY_COUNT - mNextFreeEntry - 1) * ENTRY_SIZE): 0);
977 }
978 
pageStateToName(PageState ps)979 const char* Page::pageStateToName(PageState ps)
980 {
981     switch (ps) {
982         case PageState::CORRUPT:
983             return "CORRUPT";
984 
985         case PageState::ACTIVE:
986             return "ACTIVE";
987 
988         case PageState::FREEING:
989             return "FREEING";
990 
991         case PageState::FULL:
992             return "FULL";
993 
994         case PageState::INVALID:
995             return "INVALID";
996 
997         case PageState::UNINITIALIZED:
998             return "UNINITIALIZED";
999 
1000         default:
1001             assert(0 && "invalid state value");
1002             return "";
1003     }
1004 }
1005 
debugDump() const1006 void Page::debugDump() const
1007 {
1008     printf("state=%x (%s) addr=%x seq=%d\nfirstUsed=%d nextFree=%d used=%d erased=%d\n", (uint32_t) mState, pageStateToName(mState), mBaseAddress, mSeqNumber, static_cast<int>(mFirstUsedEntry), static_cast<int>(mNextFreeEntry), mUsedEntryCount, mErasedEntryCount);
1009     size_t skip = 0;
1010     for (size_t i = 0; i < ENTRY_COUNT; ++i) {
1011         printf("%3d: ", static_cast<int>(i));
1012         EntryState state = mEntryTable.get(i);
1013         if (state == EntryState::EMPTY) {
1014             printf("E\n");
1015         } else if (state == EntryState::ERASED) {
1016             printf("X\n");
1017         } else if (state == EntryState::WRITTEN) {
1018             Item item;
1019             readEntry(i, item);
1020             if (skip == 0) {
1021                 printf("W ns=%2u type=%2u span=%3u key=\"%s\" chunkIdx=%d len=%d\n", item.nsIndex, static_cast<unsigned>(item.datatype), item.span, item.key, item.chunkIndex, (item.span != 1)?((int)item.varLength.dataSize):-1);
1022                 if (item.span > 0 && item.span <= ENTRY_COUNT - i) {
1023                     skip = item.span - 1;
1024                 } else {
1025                     skip = 0;
1026                 }
1027             } else {
1028                 printf("D\n");
1029                 skip--;
1030             }
1031         }
1032     }
1033 }
1034 
calcEntries(nvs_stats_t & nvsStats)1035 esp_err_t Page::calcEntries(nvs_stats_t &nvsStats)
1036 {
1037     assert(mState != PageState::FREEING);
1038 
1039     nvsStats.total_entries += ENTRY_COUNT;
1040 
1041     switch (mState) {
1042         case PageState::UNINITIALIZED:
1043         case PageState::CORRUPT:
1044             nvsStats.free_entries += ENTRY_COUNT;
1045             break;
1046 
1047         case PageState::FULL:
1048         case PageState::ACTIVE:
1049             nvsStats.used_entries += mUsedEntryCount;
1050             nvsStats.free_entries += ENTRY_COUNT - mUsedEntryCount; // it's equivalent free + erase entries.
1051             break;
1052 
1053         case PageState::INVALID:
1054             return ESP_ERR_INVALID_STATE;
1055             break;
1056 
1057         default:
1058             assert(false && "Unhandled state");
1059             break;
1060     }
1061     return ESP_OK;
1062 }
1063 
1064 } // namespace nvs
1065