Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 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 | // KVS is a key-value storage format for flash based memory. |
| 16 | // |
| 17 | // Currently it stores key-value sets in chunks aligned with the flash memory. |
| 18 | // Each chunk contains a header (KvsHeader), which is immediately followed by |
| 19 | // the key, and then the data blob. To support different alignments both the |
| 20 | // key length and value length are rounded up to be aligned. |
| 21 | // |
| 22 | // Example memory layout of sector with two KVS chunks: |
| 23 | // [ SECTOR_HEADER - Meta | alignment_padding ] |
| 24 | // [ SECTOR_HEADER - Cleaning State | alignment_padding ] |
| 25 | // [First Chunk Header | alignment_padding ] |
| 26 | // [First Chunk Key | alignment_padding ] |
| 27 | // [First Chunk Value | alignment_padding ] |
| 28 | // [Second Chunk Header | alignment_padding ] |
| 29 | // [Second Chunk Key | alignment_padding ] |
| 30 | // [Second Chunk Value | alignment_padding ] |
| 31 | // |
| 32 | // For efficiency if a key's value is rewritten the new value is just appended |
| 33 | // to the same sector, a clean of the sector is only needed if there is no more |
| 34 | // room. Cleaning the sector involves moving the most recent value of each key |
| 35 | // to another sector and erasing the sector. Erasing data is treated the same |
| 36 | // as rewriting data, but an erased chunk has the erased flag set, and no data. |
| 37 | // |
| 38 | // KVS maintains a data structure in RAM for quick indexing of each key's most |
| 39 | // recent value, but no caching of data is ever performed. If a write/erase |
| 40 | // function returns successfully, it is guaranteed that the data has been |
| 41 | // pushed to flash. The KVS should also be resistant to sudden unplanned power |
| 42 | // outages and be capable of recovering even mid clean (this is accomplished |
| 43 | // using a flag which marks the sector before the clean is started). |
| 44 | |
| 45 | #include "pw_kvs/key_value_store.h" |
| 46 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 47 | #include <algorithm> |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 48 | #include <cstring> |
| 49 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 50 | #include "pw_checksum/ccitt_crc16.h" |
| 51 | #include "pw_kvs/flash.h" |
| 52 | #include "pw_log/log.h" |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 53 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 54 | namespace pw::kvs { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 55 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 56 | using std::byte; |
| 57 | |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 58 | Status KeyValueStore::Enable() { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 59 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 60 | if (enabled_) { |
| 61 | return Status::OK; |
| 62 | } |
| 63 | |
| 64 | // Reset parameters. |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 65 | std::memset(sector_space_remaining_, 0, sizeof(sector_space_remaining_)); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 66 | map_size_ = 0; |
| 67 | |
| 68 | // For now alignment is set to use partitions alignment. |
| 69 | alignment_bytes_ = partition_.GetAlignmentBytes(); |
| 70 | DCHECK(alignment_bytes_ <= kMaxAlignmentBytes); |
| 71 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 72 | if (partition_.GetSectorCount() > kSectorCountMax) { |
| 73 | PW_LOG_WARN( |
| 74 | "Partition is larger then KVS max sector count, " |
| 75 | "not all space will be used."); |
| 76 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 77 | // Load map and setup sectors if needed (first word isn't kSectorReadyValue). |
| 78 | next_sector_clean_order_ = 0; |
| 79 | for (SectorIndex i = 0; i < SectorCount(); i++) { |
| 80 | KvsSectorHeaderMeta sector_header_meta; |
| 81 | // Because underlying flash can be encrypted + erased, trying to readback |
| 82 | // may give random values. It's important to make sure that data is not |
| 83 | // erased before trying to see if there is a token match. |
| 84 | bool is_sector_meta_erased; |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 85 | if (Status status = partition_.IsChunkErased( |
| 86 | SectorIndexToAddress(i), |
| 87 | RoundUpForAlignment(sizeof(sector_header_meta)), |
| 88 | &is_sector_meta_erased); |
| 89 | !status.ok()) { |
| 90 | return status; |
| 91 | }; |
| 92 | if (Status status = |
| 93 | UnalignedRead(&partition_, |
| 94 | reinterpret_cast<uint8_t*>(§or_header_meta), |
| 95 | SectorIndexToAddress(i), |
| 96 | sizeof(sector_header_meta)); |
| 97 | !status.ok()) { |
| 98 | return status; |
| 99 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 100 | |
| 101 | constexpr int kVersion3 = 3; // Version 3 only cleans 1 sector at a time. |
| 102 | constexpr int kVersion2 = 2; // Version 2 is always 1 byte aligned. |
| 103 | if (is_sector_meta_erased || |
| 104 | sector_header_meta.synchronize_token != kSectorReadyValue) { |
| 105 | // Sector needs to be setup |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 106 | if (Status status = ResetSector(i); !status.ok()) { |
| 107 | return status; |
| 108 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 109 | continue; |
| 110 | } else if (sector_header_meta.version != kVersion && |
| 111 | sector_header_meta.version != kVersion3 && // Allow version 3 |
| 112 | sector_header_meta.version != kVersion2) { // Allow version 2 |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 113 | PW_LOG_ERROR("Unsupported KVS version in sector: %u", |
| 114 | static_cast<unsigned>(i)); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 115 | return Status::FAILED_PRECONDITION; |
| 116 | } |
| 117 | uint32_t sector_header_cleaning_offset = |
| 118 | RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)); |
| 119 | |
| 120 | bool clean_not_pending; |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 121 | if (Status status = partition_.IsChunkErased( |
| 122 | SectorIndexToAddress(i) + sector_header_cleaning_offset, |
| 123 | RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning)), |
| 124 | &clean_not_pending); |
| 125 | !status.ok()) { |
| 126 | return status; |
| 127 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 128 | |
| 129 | if (!clean_not_pending) { |
| 130 | // Sector is marked for cleaning, read the sector_clean_order |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 131 | if (Status status = UnalignedRead( |
| 132 | &partition_, |
| 133 | reinterpret_cast<uint8_t*>(§or_clean_order_[i]), |
| 134 | SectorIndexToAddress(i) + sector_header_cleaning_offset, |
| 135 | sizeof(KvsSectorHeaderCleaning::sector_clean_order)); |
| 136 | !status.ok()) { |
| 137 | return status; |
| 138 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 139 | next_sector_clean_order_ = |
| 140 | std::max(sector_clean_order_[i] + 1, next_sector_clean_order_); |
| 141 | } else { |
| 142 | sector_clean_order_[i] = kSectorCleanNotPending; |
| 143 | } |
| 144 | |
| 145 | // Handle alignment |
| 146 | if (sector_header_meta.version == kVersion2) { |
| 147 | sector_header_meta.alignment_bytes = 1; |
| 148 | } |
| 149 | if (sector_header_meta.alignment_bytes != alignment_bytes_) { |
| 150 | // NOTE: For now all sectors must have same alignment. |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 151 | PW_LOG_ERROR("Sector %u has unexpected alignment %u != %u", |
| 152 | unsigned(i), |
| 153 | unsigned(alignment_bytes_), |
| 154 | unsigned(sector_header_meta.alignment_bytes)); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 155 | return Status::FAILED_PRECONDITION; |
| 156 | } |
| 157 | |
| 158 | // Scan through sector and add key/value pairs to map. |
| 159 | FlashPartition::Address offset = |
| 160 | RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)) + |
| 161 | RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning)); |
| 162 | sector_space_remaining_[i] = partition_.GetSectorSizeBytes() - offset; |
| 163 | while (offset < partition_.GetSectorSizeBytes() - |
| 164 | RoundUpForAlignment(sizeof(KvsHeader))) { |
| 165 | FlashPartition::Address address = SectorIndexToAddress(i) + offset; |
| 166 | |
| 167 | // Read header |
| 168 | KvsHeader header; |
| 169 | bool is_kvs_header_erased; |
| 170 | // Because underlying flash can be encrypted + erased, trying to readback |
| 171 | // may give random values. It's important to make sure that data is not |
| 172 | // erased before trying to see if there is a token match. |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 173 | if (Status status = |
| 174 | partition_.IsChunkErased(address, |
| 175 | RoundUpForAlignment(sizeof(header)), |
| 176 | &is_kvs_header_erased); |
| 177 | !status.ok()) { |
| 178 | return status; |
| 179 | } |
| 180 | if (Status status = UnalignedRead(&partition_, |
| 181 | reinterpret_cast<uint8_t*>(&header), |
| 182 | address, |
| 183 | sizeof(header)); |
| 184 | !status.ok()) { |
| 185 | return status; |
| 186 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 187 | if (is_kvs_header_erased || header.synchronize_token != kChunkSyncValue) { |
| 188 | if (!is_kvs_header_erased) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 189 | PW_LOG_ERROR("Next sync_token is not clear!"); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 190 | // TODO: handle this? |
| 191 | } |
| 192 | break; // End of elements in sector |
| 193 | } |
| 194 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 195 | if (header.key_len > kChunkKeyLengthMax) { |
| 196 | PW_LOG_CRITICAL("Found key with invalid length %u; maximum is %u", |
| 197 | header.key_len, |
| 198 | static_cast<unsigned>(kChunkKeyLengthMax)); |
| 199 | return Status::DATA_LOSS; |
| 200 | } |
| 201 | static_assert(sizeof(temp_key_buffer_) >= kChunkKeyLengthMax + 1, |
| 202 | "Key buffer must be at least large enough for a key and " |
| 203 | "null terminator"); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 204 | |
| 205 | // Read key and add to map |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 206 | if (Status status = |
| 207 | UnalignedRead(&partition_, |
| 208 | reinterpret_cast<uint8_t*>(&temp_key_buffer_), |
| 209 | address + RoundUpForAlignment(sizeof(header)), |
| 210 | header.key_len); |
| 211 | !status.ok()) { |
| 212 | return status; |
| 213 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 214 | temp_key_buffer_[header.key_len] = '\0'; |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 215 | std::string_view key(temp_key_buffer_, header.key_len); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 216 | bool is_erased = header.flags & kFlagsIsErasedMask; |
| 217 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 218 | KeyIndex index = FindKeyInMap(key); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 219 | if (index == kListCapacityMax) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 220 | if (Status status = |
| 221 | AppendToMap(key, address, header.chunk_len, is_erased); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 222 | !status.ok()) { |
| 223 | return status; |
| 224 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 225 | } else if (sector_clean_order_[i] >= |
| 226 | sector_clean_order_[AddressToSectorIndex( |
| 227 | key_map_[index].address)]) { |
| 228 | // The value being added is also in another sector (which is marked for |
| 229 | // cleaning), but the current sector's order is larger and thefore this |
| 230 | // is a newer version then what is already in the map. |
| 231 | UpdateMap(index, address, header.chunk_len, is_erased); |
| 232 | } |
| 233 | |
| 234 | // Increment search |
| 235 | offset += ChunkSize(header.key_len, header.chunk_len); |
| 236 | } |
| 237 | sector_space_remaining_[i] = |
| 238 | clean_not_pending ? partition_.GetSectorSizeBytes() - offset : 0; |
| 239 | } |
| 240 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 241 | if (Status status = EnforceFreeSector(); !status.ok()) { |
| 242 | PW_LOG_ERROR( |
| 243 | "%s: Failed to force clean at boot, no free sectors available!", |
| 244 | status.str()); |
| 245 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 246 | enabled_ = true; |
| 247 | return Status::OK; |
| 248 | } |
| 249 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 250 | Status KeyValueStore::Get(const std::string_view& key, |
| 251 | const span<byte>& value, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 252 | uint16_t offset) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 253 | if (InvalidKey(key)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 254 | return Status::INVALID_ARGUMENT; |
| 255 | } |
| 256 | |
| 257 | // TODO: Support unaligned offset reads. |
| 258 | if (offset % alignment_bytes_ != 0) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 259 | PW_LOG_ERROR("Currently unaligned offsets are not supported"); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 260 | return Status::INVALID_ARGUMENT; |
| 261 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 262 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 263 | if (!enabled_) { |
| 264 | return Status::FAILED_PRECONDITION; |
| 265 | } |
| 266 | |
| 267 | KeyIndex key_index = FindKeyInMap(key); |
| 268 | if (key_index == kListCapacityMax || key_map_[key_index].is_erased) { |
| 269 | return Status::NOT_FOUND; |
| 270 | } |
| 271 | KvsHeader header; |
| 272 | // TODO: Could cache the CRC and avoid reading the header. |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 273 | if (Status status = UnalignedRead(&partition_, |
| 274 | reinterpret_cast<uint8_t*>(&header), |
| 275 | key_map_[key_index].address, |
| 276 | sizeof(header)); |
| 277 | !status.ok()) { |
| 278 | return status; |
| 279 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 280 | if (kChunkSyncValue != header.synchronize_token) { |
| 281 | return Status::DATA_LOSS; |
| 282 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 283 | if (value.size() + offset > header.chunk_len) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 284 | PW_LOG_ERROR("Out of bounds read: offset(%u) + size(%u) > data_size(%u)", |
| 285 | offset, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 286 | unsigned(value.size()), |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 287 | header.chunk_len); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 288 | return Status::INVALID_ARGUMENT; |
| 289 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 290 | if (Status status = UnalignedRead( |
| 291 | &partition_, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 292 | value.data(), |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 293 | key_map_[key_index].address + RoundUpForAlignment(sizeof(KvsHeader)) + |
| 294 | RoundUpForAlignment(header.key_len) + offset, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 295 | value.size()); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 296 | !status.ok()) { |
| 297 | return status; |
| 298 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 299 | |
| 300 | // Verify CRC only when full packet was read. |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 301 | if (offset == 0 && value.size() == header.chunk_len) { |
| 302 | uint16_t crc = CalculateCrc(key, value); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 303 | if (crc != header.crc) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 304 | // TODO: Figure out how to print the key's string_view. For now, using %s |
| 305 | // with a maximum length (8 characters). This still could trigger a small |
| 306 | // out-of-bounds read. |
| 307 | PW_LOG_ERROR( |
| 308 | "KVS CRC does not match for key=%.8s [expected %u, found %u]", |
| 309 | key.data(), |
| 310 | header.crc, |
| 311 | crc); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 312 | return Status::DATA_LOSS; |
| 313 | } |
| 314 | } |
| 315 | return Status::OK; |
| 316 | } |
| 317 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 318 | uint16_t KeyValueStore::CalculateCrc(const std::string_view& key, |
| 319 | const span<const byte>& value) const { |
| 320 | uint16_t crc = checksum::CcittCrc16(as_bytes(span(key))); |
| 321 | return checksum::CcittCrc16(value, crc); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 322 | } |
| 323 | |
| 324 | Status KeyValueStore::CalculateCrcFromValueAddress( |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 325 | const std::string_view& key, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 326 | FlashPartition::Address value_address, |
| 327 | uint16_t value_size, |
| 328 | uint16_t* crc_ret) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 329 | uint16_t crc = checksum::CcittCrc16(as_bytes(span(key))); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 330 | for (size_t i = 0; i < value_size; i += TempBufferAlignedSize()) { |
| 331 | auto read_size = std::min(value_size - i, TempBufferAlignedSize()); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 332 | if (Status status = UnalignedRead( |
| 333 | &partition_, temp_buffer_, value_address + i, read_size); |
| 334 | !status.ok()) { |
| 335 | return status; |
| 336 | } |
| 337 | crc = checksum::CcittCrc16(as_bytes(span(temp_buffer_, read_size))); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 338 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 339 | *crc_ret = crc; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 340 | return Status::OK; |
| 341 | } |
| 342 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 343 | Status KeyValueStore::Put(const std::string_view& key, |
| 344 | const span<const byte>& value) { |
| 345 | if (InvalidKey(key)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 346 | return Status::INVALID_ARGUMENT; |
| 347 | } |
| 348 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 349 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 350 | if (!enabled_) { |
| 351 | return Status::FAILED_PRECONDITION; |
| 352 | } |
| 353 | |
| 354 | KeyIndex index = FindKeyInMap(key); |
| 355 | if (index != kListCapacityMax) { // Key already in map, rewrite value |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 356 | return RewriteValue(index, value); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 357 | } |
| 358 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 359 | FlashPartition::Address address = |
| 360 | FindSpace(ChunkSize(key.size(), value.size())); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 361 | if (address == kSectorInvalid) { |
| 362 | return Status::RESOURCE_EXHAUSTED; |
| 363 | } |
| 364 | |
| 365 | // Check if this would use the last empty sector on KVS with multiple sectors |
| 366 | if (SectorCount() > 1 && IsInLastFreeSector(address)) { |
| 367 | // Forcing a full garbage collect to free more sectors. |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 368 | if (Status status = FullGarbageCollect(); !status.ok()) { |
| 369 | return status; |
| 370 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 371 | address = FindSpace(ChunkSize(key.size(), value.size())); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 372 | if (address == kSectorInvalid || IsInLastFreeSector(address)) { |
| 373 | // Couldn't find space, KVS is full. |
| 374 | return Status::RESOURCE_EXHAUSTED; |
| 375 | } |
| 376 | } |
| 377 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 378 | if (Status status = WriteKeyValue(address, key, value); !status.ok()) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 379 | return status; |
| 380 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 381 | if (Status status = AppendToMap(key, address, value.size()); !status.ok()) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 382 | return status; |
| 383 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 384 | |
| 385 | return Status::OK; |
| 386 | } |
| 387 | |
| 388 | // Garbage collection cleans sectors to try to free up space. |
| 389 | // If clean_pending_sectors is true, it will only clean sectors which are |
| 390 | // currently pending a clean. |
| 391 | // If clean_pending_sectors is false, it will only clean sectors which are not |
| 392 | // currently pending a clean, instead it will mark them for cleaning and attempt |
| 393 | // a clean. |
| 394 | // If exit_when_have_free_sector is true, it will exit once a single free sector |
| 395 | // exists. |
| 396 | Status KeyValueStore::GarbageCollectImpl(bool clean_pending_sectors, |
| 397 | bool exit_when_have_free_sector) { |
| 398 | // Try to clean any pending sectors |
| 399 | for (SectorIndex sector = 0; sector < SectorCount(); sector++) { |
| 400 | if (clean_pending_sectors == |
| 401 | (sector_clean_order_[sector] != kSectorCleanNotPending)) { |
| 402 | if (!clean_pending_sectors) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 403 | if (Status status = MarkSectorForClean(sector); !status.ok()) { |
| 404 | return status; |
| 405 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 406 | } |
| 407 | Status status = CleanSector(sector); |
| 408 | if (!status.ok() && status != Status::RESOURCE_EXHAUSTED) { |
| 409 | return status; |
| 410 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 411 | if (exit_when_have_free_sector && HasEmptySector()) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 412 | return Status::OK; // Now have a free sector |
| 413 | } |
| 414 | } |
| 415 | } |
| 416 | return Status::OK; |
| 417 | } |
| 418 | |
| 419 | Status KeyValueStore::EnforceFreeSector() { |
| 420 | if (SectorCount() == 1 || HasEmptySector()) { |
| 421 | return Status::OK; |
| 422 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 423 | PW_LOG_INFO("KVS garbage collecting to get a free sector"); |
| 424 | if (Status status = GarbageCollectImpl(true /*clean_pending_sectors*/, |
| 425 | true /*exit_when_have_free_sector*/); |
| 426 | !status.ok()) { |
| 427 | return status; |
| 428 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 429 | if (HasEmptySector()) { |
| 430 | return Status::OK; |
| 431 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 432 | PW_LOG_INFO("KVS: trying to clean non-pending sectors for more space"); |
| 433 | if (Status status = GarbageCollectImpl(false /*clean_pending_sectors*/, |
| 434 | true /*exit_when_have_free_sector*/); |
| 435 | !status.ok()) { |
| 436 | return status; |
| 437 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 438 | return HasEmptySector() ? Status::OK : Status::RESOURCE_EXHAUSTED; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 439 | } |
| 440 | |
| 441 | Status KeyValueStore::FullGarbageCollect() { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 442 | PW_LOG_INFO("KVS: Full garbage collecting to try to free space"); |
| 443 | if (Status status = GarbageCollectImpl(true /*clean_pending_sectors*/, |
| 444 | false /*exit_when_have_free_sector*/); |
| 445 | !status.ok()) { |
| 446 | return status; |
| 447 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 448 | return GarbageCollectImpl(false /*clean_pending_sectors*/, |
| 449 | false /*exit_when_have_free_sector*/); |
| 450 | } |
| 451 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 452 | Status KeyValueStore::RewriteValue(KeyIndex index, |
| 453 | const span<const byte>& value, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 454 | bool is_erased) { |
| 455 | // Compare values, return if values are the same. |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 456 | if (ValueMatches(index, value, is_erased)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 457 | return Status::OK; |
| 458 | } |
| 459 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 460 | if (key_map_[index].key_length > kChunkKeyLengthMax) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 461 | return Status::INTERNAL; |
| 462 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 463 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 464 | uint32_t space_required = ChunkSize(key_map_[index].key_length, value.size()); |
| 465 | SectorIndex sector = AddressToSectorIndex(key_map_[index].address); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 466 | uint32_t sector_space_remaining = SectorSpaceRemaining(sector); |
| 467 | |
| 468 | FlashPartition::Address address = kSectorInvalid; |
| 469 | if (sector_space_remaining >= space_required) { |
| 470 | // Space available within sector, append to end |
| 471 | address = SectorIndexToAddress(sector) + partition_.GetSectorSizeBytes() - |
| 472 | sector_space_remaining; |
| 473 | } else { |
| 474 | // No space in current sector, mark sector for clean and use another sector. |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 475 | if (Status status = MarkSectorForClean(sector); !status.ok()) { |
| 476 | return status; |
| 477 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 478 | address = FindSpace(ChunkSize(key_map_[index].key_length, value.size())); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 479 | } |
| 480 | if (address == kSectorInvalid) { |
| 481 | return Status::RESOURCE_EXHAUSTED; |
| 482 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 483 | if (Status status = |
| 484 | WriteKeyValue(address, key_map_[index].key(), value, is_erased); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 485 | !status.ok()) { |
| 486 | return status; |
| 487 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 488 | UpdateMap(index, address, value.size(), is_erased); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 489 | |
| 490 | return EnforceFreeSector(); |
| 491 | } |
| 492 | |
| 493 | bool KeyValueStore::ValueMatches(KeyIndex index, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 494 | const span<const byte>& value, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 495 | bool is_erased) { |
| 496 | // Compare sizes of CRC. |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 497 | if (value.size() != key_map_[index].chunk_len) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 498 | return false; |
| 499 | } |
| 500 | KvsHeader header; |
| 501 | UnalignedRead(&partition_, |
| 502 | reinterpret_cast<uint8_t*>(&header), |
| 503 | key_map_[index].address, |
| 504 | sizeof(header)); |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 505 | std::string_view key = key_map_[index].key(); |
| 506 | if (InvalidKey(key)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 507 | return false; |
| 508 | } |
| 509 | |
| 510 | if ((header.flags & kFlagsIsErasedMask) != is_erased) { |
| 511 | return false; |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 512 | } |
| 513 | if ((header.flags & kFlagsIsErasedMask) && is_erased) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 514 | return true; |
| 515 | } |
| 516 | |
| 517 | // Compare checksums. |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 518 | if (header.crc != CalculateCrc(key_map_[index].key(), value)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 519 | return false; |
| 520 | } |
| 521 | FlashPartition::Address address = key_map_[index].address + |
| 522 | RoundUpForAlignment(sizeof(KvsHeader)) + |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 523 | RoundUpForAlignment(key.size()); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 524 | // Compare full values. |
| 525 | for (size_t i = 0; i < key_map_[index].chunk_len; |
| 526 | i += TempBufferAlignedSize()) { |
| 527 | auto read_size = |
| 528 | std::min(key_map_[index].chunk_len - i, TempBufferAlignedSize()); |
| 529 | auto status = |
| 530 | UnalignedRead(&partition_, temp_buffer_, address + i, read_size); |
| 531 | if (!status.ok()) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 532 | PW_LOG_ERROR("%s: Failed to read chunk", status.str()); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 533 | return false; |
| 534 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 535 | if (std::memcmp(&value[i], temp_buffer_, read_size) != 0) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 536 | return false; |
| 537 | } |
| 538 | } |
| 539 | return true; |
| 540 | } |
| 541 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 542 | Status KeyValueStore::Erase(const std::string_view& key) { |
| 543 | if (InvalidKey(key)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 544 | return Status::INVALID_ARGUMENT; |
| 545 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 546 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 547 | if (!enabled_) { |
| 548 | return Status::FAILED_PRECONDITION; |
| 549 | } |
| 550 | |
| 551 | KeyIndex key_index = FindKeyInMap(key); |
| 552 | if (key_index == kListCapacityMax || key_map_[key_index].is_erased) { |
| 553 | return Status::NOT_FOUND; |
| 554 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 555 | return RewriteValue(key_index, span<byte>(), true); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 556 | } |
| 557 | |
| 558 | Status KeyValueStore::ResetSector(SectorIndex sector_index) { |
| 559 | KvsSectorHeaderMeta sector_header = {.synchronize_token = kSectorReadyValue, |
| 560 | .version = kVersion, |
| 561 | .alignment_bytes = alignment_bytes_, |
| 562 | .padding = 0xFFFF}; |
| 563 | bool sector_erased = false; |
| 564 | partition_.IsChunkErased(SectorIndexToAddress(sector_index), |
| 565 | partition_.GetSectorSizeBytes(), |
| 566 | §or_erased); |
| 567 | auto status = partition_.Erase(SectorIndexToAddress(sector_index), 1); |
| 568 | |
| 569 | // If erasure failed, check first to see if it's merely unimplemented |
| 570 | // (as in sub-sector KVSs). |
| 571 | if (!status.ok() && !(status == Status::UNIMPLEMENTED && sector_erased)) { |
| 572 | return status; |
| 573 | } |
| 574 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 575 | if (Status status = |
| 576 | PaddedWrite(&partition_, |
| 577 | SectorIndexToAddress(sector_index), |
| 578 | reinterpret_cast<const uint8_t*>(§or_header), |
| 579 | sizeof(sector_header)); |
| 580 | !status.ok()) { |
| 581 | return status; |
| 582 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 583 | |
| 584 | // Update space remaining |
| 585 | sector_clean_order_[sector_index] = kSectorCleanNotPending; |
| 586 | sector_space_remaining_[sector_index] = SectorSpaceAvailableWhenEmpty(); |
| 587 | return Status::OK; |
| 588 | } |
| 589 | |
| 590 | Status KeyValueStore::WriteKeyValue(FlashPartition::Address address, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 591 | const std::string_view& key, |
| 592 | const span<const byte>& value, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 593 | bool is_erased) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 594 | if (InvalidKey(key) || |
| 595 | value.size() > |
| 596 | std::numeric_limits<decltype(KvsHeader::chunk_len)>::max()) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 597 | return Status::INTERNAL; |
| 598 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 599 | |
| 600 | constexpr uint16_t kFlagDefaultValue = 0; |
| 601 | KvsHeader header = { |
| 602 | .synchronize_token = kChunkSyncValue, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 603 | .crc = CalculateCrc(key, value), |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 604 | .flags = is_erased ? kFlagsIsErasedMask : kFlagDefaultValue, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 605 | .key_len = static_cast<uint8_t>(key.size()), |
| 606 | .chunk_len = static_cast<uint16_t>(value.size())}; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 607 | |
| 608 | SectorIndex sector = AddressToSectorIndex(address); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 609 | if (Status status = PaddedWrite(&partition_, |
| 610 | address, |
| 611 | reinterpret_cast<uint8_t*>(&header), |
| 612 | sizeof(header)); |
| 613 | !status.ok()) { |
| 614 | return status; |
| 615 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 616 | address += RoundUpForAlignment(sizeof(header)); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 617 | if (Status status = PaddedWrite(&partition_, |
| 618 | address, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 619 | reinterpret_cast<const uint8_t*>(key.data()), |
| 620 | key.size()); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 621 | !status.ok()) { |
| 622 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 623 | address += RoundUpForAlignment(key.size()); |
| 624 | if (!value.empty()) { |
| 625 | Status status = |
| 626 | PaddedWrite(&partition_, address, value.data(), value.size()); |
| 627 | if (!status.ok()) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 628 | return status; |
| 629 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 630 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 631 | sector_space_remaining_[sector] -= ChunkSize(key.size(), value.size()); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 632 | return Status::OK; |
| 633 | } |
| 634 | |
| 635 | Status KeyValueStore::MoveChunk(FlashPartition::Address dest_address, |
| 636 | FlashPartition::Address src_address, |
| 637 | uint16_t size) { |
| 638 | DCHECK_EQ(src_address % partition_.GetAlignmentBytes(), 0); |
| 639 | DCHECK_EQ(dest_address % partition_.GetAlignmentBytes(), 0); |
| 640 | DCHECK_EQ(size % partition_.GetAlignmentBytes(), 0); |
| 641 | |
| 642 | // Copy data over in chunks to reduce the size of the temporary buffer |
| 643 | for (size_t i = 0; i < size; i += TempBufferAlignedSize()) { |
| 644 | size_t move_size = std::min(size - i, TempBufferAlignedSize()); |
| 645 | DCHECK_EQ(move_size % alignment_bytes_, 0); |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 646 | if (Status status = |
| 647 | partition_.Read(temp_buffer_, src_address + i, move_size); |
| 648 | !status.ok()) { |
| 649 | return status; |
| 650 | } |
| 651 | if (Status status = |
| 652 | partition_.Write(dest_address + i, temp_buffer_, move_size); |
| 653 | !status.ok()) { |
| 654 | return status; |
| 655 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 656 | } |
| 657 | return Status::OK; |
| 658 | } |
| 659 | |
| 660 | Status KeyValueStore::MarkSectorForClean(SectorIndex sector) { |
| 661 | if (sector_clean_order_[sector] != kSectorCleanNotPending) { |
| 662 | return Status::OK; // Sector is already marked for clean |
| 663 | } |
| 664 | |
| 665 | // Flag the sector as clean being active. This ensures we can handle losing |
| 666 | // power while a clean is active. |
| 667 | const KvsSectorHeaderCleaning kValue = {next_sector_clean_order_}; |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 668 | if (Status status = |
| 669 | PaddedWrite(&partition_, |
| 670 | SectorIndexToAddress(sector) + |
| 671 | RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)), |
| 672 | reinterpret_cast<const uint8_t*>(&kValue), |
| 673 | sizeof(kValue)); |
| 674 | !status.ok()) { |
| 675 | return status; |
| 676 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 677 | sector_space_remaining_[sector] = 0; |
| 678 | sector_clean_order_[sector] = next_sector_clean_order_; |
| 679 | next_sector_clean_order_++; |
| 680 | return Status::OK; |
| 681 | } |
| 682 | |
| 683 | Status KeyValueStore::CleanSector(SectorIndex sector) { |
| 684 | // Iterate through the map, for each valid element which is in this sector: |
| 685 | // - Find space in another sector which can fit this chunk. |
| 686 | // - Add to the other sector and update the map. |
| 687 | for (KeyValueStore::KeyIndex i = 0; i < map_size_; i++) { |
| 688 | // If this key is an erased chunk don't need to move it. |
| 689 | while (i < map_size_ && |
| 690 | sector == AddressToSectorIndex(key_map_[i].address) && |
| 691 | key_map_[i].is_erased) { // Remove this key from the map. |
| 692 | RemoveFromMap(i); |
| 693 | // NOTE: i is now a new key, and map_size_ has been decremented. |
| 694 | } |
| 695 | |
| 696 | if (i < map_size_ && sector == AddressToSectorIndex(key_map_[i].address)) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 697 | FlashPartition::Address address = key_map_[i].address; |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 698 | auto size = ChunkSize(key_map_[i].key_length, key_map_[i].chunk_len); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 699 | FlashPartition::Address move_address = FindSpace(size); |
| 700 | if (move_address == kSectorInvalid) { |
| 701 | return Status::RESOURCE_EXHAUSTED; |
| 702 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 703 | if (Status status = MoveChunk(move_address, address, size); |
| 704 | !status.ok()) { |
| 705 | return status; |
| 706 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 707 | sector_space_remaining_[AddressToSectorIndex(move_address)] -= size; |
| 708 | key_map_[i].address = move_address; // Update map |
| 709 | } |
| 710 | } |
| 711 | ResetSector(sector); |
| 712 | return Status::OK; |
| 713 | } |
| 714 | |
| 715 | Status KeyValueStore::CleanOneSector(bool* all_sectors_have_been_cleaned) { |
| 716 | if (all_sectors_have_been_cleaned == nullptr) { |
| 717 | return Status::INVALID_ARGUMENT; |
| 718 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 719 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 720 | bool have_cleaned_sector = false; |
| 721 | for (SectorIndex sector = 0; sector < SectorCount(); sector++) { |
| 722 | if (sector_clean_order_[sector] != kSectorCleanNotPending) { |
| 723 | if (have_cleaned_sector) { // only clean 1 sector |
| 724 | *all_sectors_have_been_cleaned = false; |
| 725 | return Status::OK; |
| 726 | } |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 727 | if (Status status = CleanSector(sector); !status.ok()) { |
| 728 | return status; |
| 729 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 730 | have_cleaned_sector = true; |
| 731 | } |
| 732 | } |
| 733 | *all_sectors_have_been_cleaned = true; |
| 734 | return Status::OK; |
| 735 | } |
| 736 | |
| 737 | Status KeyValueStore::CleanAllInternal() { |
| 738 | for (SectorIndex sector = 0; sector < SectorCount(); sector++) { |
| 739 | if (sector_clean_order_[sector] != kSectorCleanNotPending) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 740 | if (Status status = CleanSector(sector); !status.ok()) { |
| 741 | return status; |
| 742 | } |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 743 | } |
| 744 | } |
| 745 | return Status::OK; |
| 746 | } |
| 747 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 748 | FlashPartition::Address KeyValueStore::FindSpace(size_t requested_size) const { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 749 | if (requested_size > SectorSpaceAvailableWhenEmpty()) { |
| 750 | return kSectorInvalid; // This would never fit |
| 751 | } |
| 752 | // Iterate through sectors, find first available sector with enough space. |
| 753 | SectorIndex first_empty_sector = kSectorInvalid; |
| 754 | for (SectorIndex i = 0; i < SectorCount(); i++) { |
| 755 | uint32_t space_remaining = SectorSpaceRemaining(i); |
| 756 | if (space_remaining == SectorSpaceAvailableWhenEmpty() && |
| 757 | first_empty_sector == kSectorInvalid) { |
| 758 | // Skip the first empty sector to encourage keeping one sector free. |
| 759 | first_empty_sector = i; |
| 760 | continue; |
| 761 | } |
| 762 | if (space_remaining >= requested_size) { |
| 763 | return SectorIndexToAddress(i) + partition_.GetSectorSizeBytes() - |
| 764 | space_remaining; |
| 765 | } |
| 766 | } |
| 767 | // Use first empty sector if that is all that is available. |
| 768 | if (first_empty_sector != kSectorInvalid) { |
| 769 | return SectorIndexToAddress(first_empty_sector) + |
| 770 | partition_.GetSectorSizeBytes() - SectorSpaceAvailableWhenEmpty(); |
| 771 | } |
| 772 | return kSectorInvalid; |
| 773 | } |
| 774 | |
| 775 | uint32_t KeyValueStore::SectorSpaceRemaining(SectorIndex sector_index) const { |
| 776 | return sector_space_remaining_[sector_index]; |
| 777 | } |
| 778 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 779 | StatusWithSize KeyValueStore::GetValueSize(const std::string_view& key) { |
| 780 | if (InvalidKey(key)) { |
| 781 | return StatusWithSize(Status::INVALID_ARGUMENT, 0); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 782 | } |
| 783 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 784 | // TODO: LOCK MUTEX |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 785 | if (!enabled_) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 786 | return StatusWithSize(Status::FAILED_PRECONDITION, 0); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 787 | } |
| 788 | |
| 789 | uint8_t idx = FindKeyInMap(key); |
| 790 | if (idx == kListCapacityMax || key_map_[idx].is_erased) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 791 | return StatusWithSize(Status::NOT_FOUND, 0); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 792 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 793 | return StatusWithSize(key_map_[idx].chunk_len); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 794 | } |
| 795 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 796 | Status KeyValueStore::AppendToMap(const std::string_view& key, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 797 | FlashPartition::Address address, |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 798 | size_t chunk_len, |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 799 | bool is_erased) { |
| 800 | if (map_size_ >= kListCapacityMax) { |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 801 | PW_LOG_ERROR("Can't add: reached max supported keys %d", kListCapacityMax); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 802 | return Status::INTERNAL; |
| 803 | } |
| 804 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 805 | auto& entry = key_map_[map_size_]; |
| 806 | entry.key_buffer[key.copy(entry.key_buffer, sizeof(KeyMap::key_buffer) - 1)] = |
| 807 | '\0'; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 808 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 809 | entry.key_length = key.size(); |
| 810 | entry.address = address; |
| 811 | entry.chunk_len = static_cast<uint16_t>(chunk_len); |
| 812 | entry.is_erased = is_erased; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 813 | map_size_++; |
| 814 | |
| 815 | return Status::OK; |
| 816 | } |
| 817 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 818 | KeyValueStore::KeyIndex KeyValueStore::FindKeyInMap( |
| 819 | const std::string_view& key) const { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 820 | for (KeyIndex i = 0; i < map_size_; i++) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 821 | if (key == std::string_view(key_map_[i].key())) { |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 822 | return i; |
| 823 | } |
| 824 | } |
| 825 | return kListCapacityMax; |
| 826 | } |
| 827 | |
| 828 | void KeyValueStore::UpdateMap(KeyIndex index, |
| 829 | FlashPartition::Address address, |
| 830 | uint16_t chunk_len, |
| 831 | bool is_erased) { |
| 832 | key_map_[index].address = address; |
| 833 | key_map_[index].chunk_len = chunk_len; |
| 834 | key_map_[index].is_erased = is_erased; |
| 835 | } |
| 836 | |
| 837 | void KeyValueStore::RemoveFromMap(KeyIndex key_index) { |
| 838 | key_map_[key_index] = key_map_[--map_size_]; |
| 839 | } |
| 840 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 841 | size_t KeyValueStore::KeyCount() const { |
| 842 | size_t count = 0; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 843 | for (unsigned i = 0; i < map_size_; i++) { |
| 844 | count += key_map_[i].is_erased ? 0 : 1; |
| 845 | } |
| 846 | return count; |
| 847 | } |
| 848 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 849 | std::string_view KeyValueStore::GetKey(size_t idx) const { |
| 850 | unsigned count = 0; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 851 | for (unsigned i = 0; i < map_size_; i++) { |
| 852 | if (!key_map_[i].is_erased) { |
| 853 | if (idx == count) { |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 854 | return key_map_[i].key(); |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 855 | } |
| 856 | count++; |
| 857 | } |
| 858 | } |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 859 | return {}; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 860 | } |
| 861 | |
Wyatt Hepler | acaacf9 | 2020-01-24 10:58:30 -0800 | [diff] [blame^] | 862 | size_t KeyValueStore::GetValueSize(size_t idx) const { |
| 863 | size_t count = 0; |
Wyatt Hepler | b760954 | 2020-01-24 10:29:54 -0800 | [diff] [blame] | 864 | for (unsigned i = 0; i < map_size_; i++) { |
| 865 | if (!key_map_[i].is_erased) { |
| 866 | if (idx == count++) { |
| 867 | return key_map_[i].chunk_len; |
| 868 | } |
| 869 | } |
| 870 | } |
| 871 | return 0; |
| 872 | } |
| 873 | |
Wyatt Hepler | 2ad6067 | 2020-01-21 08:00:16 -0800 | [diff] [blame] | 874 | } // namespace pw::kvs |