tickv/
tickv.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! The TicKV implementation.
6
7use crate::crc32;
8use crate::error_codes::ErrorCode;
9use crate::flash_controller::FlashController;
10use crate::success_codes::SuccessCode;
11use core::cell::Cell;
12
13/// The current version of TicKV
14pub const VERSION: u8 = 1;
15
16#[derive(Clone, Copy, PartialEq)]
17pub(crate) enum InitState {
18    /// Trying to read the key from a region
19    GetKeyReadRegion(usize),
20    /// Trying to erase a region
21    EraseRegion(usize),
22    /// Finished erasing regions
23    EraseComplete,
24    /// Trying to read a region while appending a key
25    AppendKeyReadRegion(usize),
26}
27
28#[derive(Clone, Copy, PartialEq)]
29pub(crate) enum KeyState {
30    /// Trying to read the key from a region
31    ReadRegion(usize),
32}
33
34#[derive(Clone, Copy, PartialEq)]
35pub(crate) enum RubbishState {
36    ReadRegion(usize, usize),
37    EraseRegion(usize, usize),
38}
39
40#[derive(Clone, Copy, PartialEq)]
41/// The current state machine when trying to complete a previous operation.
42/// This is used when returning from a complete async `FlashController` call.
43pub(crate) enum State {
44    /// No previous state
45    None,
46    /// Init Operation
47    Init(InitState),
48    /// Appending a key
49    AppendKey(KeyState),
50    /// Getting a key
51    GetKey(KeyState),
52    /// Invalidating a key
53    InvalidateKey(KeyState),
54    /// Zeroizing a key
55    ZeroiseKey(KeyState),
56    /// Running garbage collection
57    GarbageCollect(RubbishState),
58}
59
60/// The struct storing all of the TicKV information.
61pub struct TicKV<'a, C: FlashController<S>, const S: usize> {
62    /// The controller used for flash commands
63    pub controller: C,
64    flash_size: usize,
65    pub(crate) read_buffer: Cell<Option<&'a mut [u8; S]>>,
66    pub(crate) state: Cell<State>,
67}
68
69/// This is the current object header used for TicKV objects
70struct ObjectHeader {
71    version: u8,
72    // In reality this is a u4.
73    flags: u8,
74    // In reality this is a u12.
75    len: u16,
76    hashed_key: u64,
77}
78
79pub(crate) const FLAGS_VALID: u8 = 8;
80
81impl ObjectHeader {
82    fn new(hashed_key: u64, len: u16) -> Self {
83        assert!(len < 0xFFF);
84        Self {
85            version: VERSION,
86            flags: FLAGS_VALID,
87            len,
88            hashed_key,
89        }
90    }
91}
92
93// A list of offsets into the ObjectHeader
94pub(crate) const VERSION_OFFSET: usize = 0;
95pub(crate) const LEN_OFFSET: usize = 1;
96pub(crate) const HASH_OFFSET: usize = 3;
97pub(crate) const HEADER_LENGTH: usize = HASH_OFFSET + 8;
98pub(crate) const CHECK_SUM_LEN: usize = 4;
99
100/// The main key. A hashed version of this should be passed to
101/// `initialise()`.
102pub const MAIN_KEY: &[u8; 15] = b"tickv-super-key";
103
104/// This is the main TicKV struct.
105impl<'a, C: FlashController<S>, const S: usize> TicKV<'a, C, S> {
106    /// Create a new struct
107    ///
108    /// `C`: An implementation of the `FlashController` trait
109    ///
110    /// `controller`: An new struct implementing `FlashController`
111    /// `flash_size`: The total size of the flash used for TicKV
112    pub fn new(controller: C, read_buffer: &'a mut [u8; S], flash_size: usize) -> Self {
113        Self {
114            controller,
115            flash_size,
116            read_buffer: Cell::new(Some(read_buffer)),
117            state: Cell::new(State::None),
118        }
119    }
120
121    /// This function setups the flash region to be used as a key-value store.
122    /// If the region is already initialised this won't make any changes.
123    ///
124    /// `hashed_main_key`: The u64 hash of the const string `MAIN_KEY`.
125    ///
126    /// If the specified region has not already been setup for TicKV
127    /// the entire region will be erased.
128    ///
129    /// On success nothing will be returned.
130    /// On error a `ErrorCode` will be returned.
131    pub fn initialise(&self, hashed_main_key: u64) -> Result<SuccessCode, ErrorCode> {
132        let mut buf: [u8; 0] = [0; 0];
133
134        let key_ret = match self.state.get() {
135            State::None => self.get_key(hashed_main_key, &mut buf),
136            State::Init(state) => match state {
137                InitState::GetKeyReadRegion(_) => self.get_key(hashed_main_key, &mut buf),
138                _ => Err(ErrorCode::EraseNotReady(0)),
139            },
140            _ => unreachable!(),
141        };
142
143        match key_ret {
144            Ok((ret, _len)) => Ok(ret),
145            Err(e) => {
146                match e {
147                    ErrorCode::ReadNotReady(reg) => {
148                        self.state
149                            .set(State::Init(InitState::GetKeyReadRegion(reg)));
150                        Err(ErrorCode::ReadNotReady(reg))
151                    }
152                    _ => {
153                        match self.state.get() {
154                            State::None
155                            | State::Init(InitState::GetKeyReadRegion(_))
156                            | State::Init(InitState::EraseRegion(_)) => {
157                                // Erase all regions
158                                let mut start = 0;
159                                if let State::Init(InitState::EraseRegion(reg)) = self.state.get() {
160                                    // We already erased region reg, so move to the next one
161                                    start = reg + 1;
162                                }
163
164                                if start < (self.flash_size / S) {
165                                    for r in start..(self.flash_size / S) {
166                                        if let Err(e) = self.controller.erase_region(r) {
167                                            self.state.set(State::Init(InitState::EraseRegion(r)));
168                                            return Err(e);
169                                        }
170                                    }
171                                }
172
173                                self.state.set(State::Init(InitState::EraseComplete));
174                            }
175                            _ => {}
176                        }
177
178                        // Save the main key
179                        match self.append_key(hashed_main_key, &buf) {
180                            Ok(ret) => {
181                                self.state.set(State::None);
182                                Ok(ret)
183                            }
184                            Err(e) => match e {
185                                ErrorCode::ReadNotReady(reg) => {
186                                    self.state
187                                        .set(State::Init(InitState::AppendKeyReadRegion(reg)));
188                                    Err(e)
189                                }
190                                ErrorCode::WriteNotReady(_) => {
191                                    self.state.set(State::None);
192                                    Ok(SuccessCode::Queued)
193                                }
194                                _ => Err(e),
195                            },
196                        }
197                    }
198                }
199            }
200        }
201    }
202
203    /// Get region number from a hashed key
204    fn get_region(&self, hash: u64) -> usize {
205        assert_ne!(hash, 0xFFFF_FFFF_FFFF_FFFF);
206        assert_ne!(hash, 0);
207
208        // Determine the number of regions
209        let num_region = self.flash_size / S;
210
211        // Determine the block where the data should be
212        (hash as usize & 0xFFFF) % num_region
213    }
214
215    // Determine the new region offset to try.
216    //
217    // `region` is the base region. This is the default region
218    // for the object, this won't change per key.
219    // `region_offset` is the current region offset are trying to use
220    // If multiple attempts are required this value will be different
221    // on each iteration. This should be the previous return value of
222    // this function, or zero on the first iteration.
223    //
224    // This function will return an offset that can be applied to
225    // region to determine a new flash region
226    // Returns None if there aren't any more in range.
227    fn increment_region_offset(&self, region: usize, region_offset: isize) -> Option<isize> {
228        let mut too_big = false;
229        let mut too_small = false;
230        let mut new_offset = region_offset;
231
232        // Loop until we find a region we can use
233        while !too_big || !too_small {
234            new_offset = match new_offset {
235                // If this is the first iteration, just try the next region
236                0 => 1,
237                // If the offset is positive, return the negative value
238                new_offset if new_offset > 0 => -new_offset,
239                // If the offset is negative, convert to positive and increment by 1
240                new_offset if new_offset < 0 => -new_offset + 1,
241                _ => unreachable!(),
242            };
243
244            // Make sure our new offset is valid
245            if (region as isize + new_offset) > ((self.flash_size / S) - 1) as isize {
246                too_big = true;
247                continue;
248            }
249
250            if (region as isize + new_offset) < 0 {
251                too_small = true;
252                continue;
253            }
254
255            return Some(new_offset);
256        }
257
258        None
259    }
260
261    /// Find a key in some loaded region data.
262    ///
263    /// On success return the offset in the region_data where the key is and the
264    /// total length of the key.
265    /// On failure return a bool indicating if the caller should keep looking in
266    /// neighboring regions and the error code.
267    fn find_key_offset(
268        &self,
269        hash: u64,
270        region_data: &[u8],
271    ) -> Result<(usize, u16), (bool, ErrorCode)> {
272        // Determine the total size of our payload
273
274        // Split the hash
275        let hash = hash.to_ne_bytes();
276
277        let mut offset: usize = 0;
278        let mut empty: bool = true;
279
280        loop {
281            if offset + HEADER_LENGTH >= S {
282                // We have reached the end of the region
283                return Err((false, ErrorCode::KeyNotFound));
284            }
285
286            // Check to see if we have data
287            if *region_data
288                .get(offset + VERSION_OFFSET)
289                .ok_or((false, ErrorCode::KeyNotFound))?
290                != 0xFF
291            {
292                // Mark that this region isn't empty
293                empty = false;
294
295                // We found a version, check that we support it
296                if *region_data
297                    .get(offset + VERSION_OFFSET)
298                    .ok_or((false, ErrorCode::KeyNotFound))?
299                    != VERSION
300                {
301                    return Err((false, ErrorCode::UnsupportedVersion));
302                }
303
304                // Find this entries length
305                let total_length = ((*region_data
306                    .get(offset + LEN_OFFSET)
307                    .ok_or((false, ErrorCode::CorruptData))?
308                    as u16)
309                    & !0xF0)
310                    << 8
311                    | *region_data
312                        .get(offset + LEN_OFFSET + 1)
313                        .ok_or((false, ErrorCode::CorruptData))? as u16;
314
315                // Check to see if all fields are just 0
316                if total_length == 0 {
317                    // We found something invalid here
318                    return Err((false, ErrorCode::KeyNotFound));
319                }
320
321                // Check to see if the entry has been deleted
322                if *region_data
323                    .get(offset + LEN_OFFSET)
324                    .ok_or((false, ErrorCode::CorruptData))?
325                    & 0x80
326                    != 0x80
327                {
328                    // Increment our offset by the length and repeat the loop
329                    offset += total_length as usize;
330                    continue;
331                }
332
333                // We have found a valid entry, see if it is ours.
334                if *region_data
335                    .get(offset + HASH_OFFSET)
336                    .ok_or((false, ErrorCode::CorruptData))?
337                    != *hash.get(7).ok_or((false, ErrorCode::CorruptData))?
338                    || *region_data
339                        .get(offset + HASH_OFFSET + 1)
340                        .ok_or((false, ErrorCode::CorruptData))?
341                        != *hash.get(6).ok_or((false, ErrorCode::CorruptData))?
342                    || *region_data
343                        .get(offset + HASH_OFFSET + 2)
344                        .ok_or((false, ErrorCode::CorruptData))?
345                        != *hash.get(5).ok_or((false, ErrorCode::CorruptData))?
346                    || *region_data
347                        .get(offset + HASH_OFFSET + 3)
348                        .ok_or((false, ErrorCode::CorruptData))?
349                        != *hash.get(4).ok_or((false, ErrorCode::CorruptData))?
350                    || *region_data
351                        .get(offset + HASH_OFFSET + 4)
352                        .ok_or((false, ErrorCode::CorruptData))?
353                        != *hash.get(3).ok_or((false, ErrorCode::CorruptData))?
354                    || *region_data
355                        .get(offset + HASH_OFFSET + 5)
356                        .ok_or((false, ErrorCode::CorruptData))?
357                        != *hash.get(2).ok_or((false, ErrorCode::CorruptData))?
358                    || *region_data
359                        .get(offset + HASH_OFFSET + 6)
360                        .ok_or((false, ErrorCode::CorruptData))?
361                        != *hash.get(1).ok_or((false, ErrorCode::CorruptData))?
362                    || *region_data
363                        .get(offset + HASH_OFFSET + 7)
364                        .ok_or((false, ErrorCode::CorruptData))?
365                        != *hash.first().ok_or((false, ErrorCode::CorruptData))?
366                {
367                    // Increment our offset by the length and repeat the loop
368                    offset += total_length as usize;
369                    continue;
370                }
371
372                // If we get here we have found out value (assuming no collisions)
373                return Ok((offset, total_length));
374            } else {
375                // We hit the end.
376                return Err((!empty, ErrorCode::KeyNotFound));
377            }
378        }
379    }
380
381    /// Appends the key/value pair to flash storage.
382    ///
383    /// `hash`: A hashed key. This key will be used in future to retrieve
384    ///         or remove the `value`.
385    /// `value`: A buffer containing the data to be stored to flash.
386    ///
387    /// On success nothing will be returned.
388    /// On error a `ErrorCode` will be returned.
389    pub fn append_key(&self, hash: u64, value: &[u8]) -> Result<SuccessCode, ErrorCode> {
390        let region = self.get_region(hash);
391        let check_sum = crc32::Crc32::new();
392
393        // Length not including check sum
394        let package_length = HEADER_LENGTH + value.len();
395        let object_length = HEADER_LENGTH + value.len() + CHECK_SUM_LEN;
396
397        if object_length > 0xFFF {
398            return Err(ErrorCode::ObjectTooLarge);
399        }
400
401        // Create the header:
402        let header = ObjectHeader::new(hash, object_length as u16);
403
404        let mut region_offset: isize = 0;
405
406        loop {
407            let new_region = match self.state.get() {
408                State::None => (region as isize + region_offset) as usize,
409                State::Init(state) => {
410                    match state {
411                        InitState::AppendKeyReadRegion(reg) => reg,
412                        _ => {
413                            // Get the data from that region
414                            (region as isize + region_offset) as usize
415                        }
416                    }
417                }
418                State::AppendKey(key_state) => match key_state {
419                    KeyState::ReadRegion(reg) => reg,
420                },
421                _ => unreachable!(),
422            };
423
424            let region_data = self.read_buffer.take().unwrap();
425            if self.state.get() != State::AppendKey(KeyState::ReadRegion(new_region))
426                && self.state.get() != State::Init(InitState::AppendKeyReadRegion(new_region))
427            {
428                if let Err(e) = self.controller.read_region(new_region, region_data) {
429                    self.read_buffer.replace(Some(region_data));
430                    if let ErrorCode::ReadNotReady(reg) = e {
431                        self.state.set(State::AppendKey(KeyState::ReadRegion(reg)));
432                    }
433                    return Err(e);
434                }
435            }
436
437            if self.find_key_offset(hash, region_data).is_ok() {
438                // Check to make sure we don't already have this key
439                self.read_buffer.replace(Some(region_data));
440                return Err(ErrorCode::KeyAlreadyExists);
441            }
442
443            let mut offset: usize = 0;
444
445            loop {
446                if offset + package_length >= S {
447                    // We have reached the end of the region
448                    // We will need to try the next region
449
450                    // Replace the buffer
451                    self.read_buffer.replace(Some(region_data));
452
453                    region_offset = new_region as isize - region as isize;
454                    match self.increment_region_offset(region, region_offset) {
455                        Some(o) => {
456                            region_offset = o;
457                            self.state.set(State::None);
458                        }
459                        None => {
460                            return Err(ErrorCode::FlashFull);
461                        }
462                    }
463                    break;
464                }
465
466                // Check to see if we have data
467                if *region_data
468                    .get(offset + VERSION_OFFSET)
469                    .ok_or(ErrorCode::KeyNotFound)?
470                    != 0xFF
471                {
472                    // We found a version, check that we support it
473                    if *region_data
474                        .get(offset + VERSION_OFFSET)
475                        .ok_or(ErrorCode::KeyNotFound)?
476                        != VERSION
477                    {
478                        self.read_buffer.replace(Some(region_data));
479                        return Err(ErrorCode::UnsupportedVersion);
480                    }
481
482                    // Find this entries length
483                    let total_length = ((*region_data
484                        .get(offset + LEN_OFFSET)
485                        .ok_or(ErrorCode::CorruptData)?
486                        as u16)
487                        & !0xF0)
488                        << 8
489                        | *region_data
490                            .get(offset + LEN_OFFSET + 1)
491                            .ok_or(ErrorCode::CorruptData)? as u16;
492
493                    // Increment our offset by the length and repeat the loop
494                    offset += total_length as usize;
495                    continue;
496                }
497
498                // If we get here we have found an empty spot
499                // Double check that there is no valid hash
500
501                // Check to see if the entire header is 0xFFFF_FFFF_FFFF_FFFF
502                // To avoid operating on 64-bit values check every 8 bytes at a time
503                if *region_data
504                    .get(offset + HASH_OFFSET)
505                    .ok_or(ErrorCode::CorruptData)?
506                    != 0xFF
507                {
508                    self.read_buffer.replace(Some(region_data));
509                    return Err(ErrorCode::CorruptData);
510                }
511                if *region_data
512                    .get(offset + HASH_OFFSET + 1)
513                    .ok_or(ErrorCode::CorruptData)?
514                    != 0xFF
515                {
516                    self.read_buffer.replace(Some(region_data));
517                    return Err(ErrorCode::CorruptData);
518                }
519                if *region_data
520                    .get(offset + HASH_OFFSET + 2)
521                    .ok_or(ErrorCode::CorruptData)?
522                    != 0xFF
523                {
524                    self.read_buffer.replace(Some(region_data));
525                    return Err(ErrorCode::CorruptData);
526                }
527                if *region_data
528                    .get(offset + HASH_OFFSET + 3)
529                    .ok_or(ErrorCode::CorruptData)?
530                    != 0xFF
531                {
532                    self.read_buffer.replace(Some(region_data));
533                    return Err(ErrorCode::CorruptData);
534                }
535                if *region_data
536                    .get(offset + HASH_OFFSET + 4)
537                    .ok_or(ErrorCode::CorruptData)?
538                    != 0xFF
539                {
540                    self.read_buffer.replace(Some(region_data));
541                    return Err(ErrorCode::CorruptData);
542                }
543                if *region_data
544                    .get(offset + HASH_OFFSET + 5)
545                    .ok_or(ErrorCode::CorruptData)?
546                    != 0xFF
547                {
548                    self.read_buffer.replace(Some(region_data));
549                    return Err(ErrorCode::CorruptData);
550                }
551                if *region_data
552                    .get(offset + HASH_OFFSET + 6)
553                    .ok_or(ErrorCode::CorruptData)?
554                    != 0xFF
555                {
556                    self.read_buffer.replace(Some(region_data));
557                    return Err(ErrorCode::CorruptData);
558                }
559                if *region_data
560                    .get(offset + HASH_OFFSET + 7)
561                    .ok_or(ErrorCode::CorruptData)?
562                    != 0xFF
563                {
564                    self.read_buffer.replace(Some(region_data));
565                    return Err(ErrorCode::CorruptData);
566                }
567
568                // If we get here we have found an empty spot
569
570                // Copy in new header
571                // This is a little painful, but avoids any unsafe Rust
572                *region_data
573                    .get_mut(offset + VERSION_OFFSET)
574                    .ok_or(ErrorCode::RegionFull)? = header.version;
575                *region_data
576                    .get_mut(offset + LEN_OFFSET)
577                    .ok_or(ErrorCode::RegionFull)? =
578                    (header.len >> 8) as u8 & 0x0F | (header.flags << 4) & 0xF0;
579                *region_data
580                    .get_mut(offset + LEN_OFFSET + 1)
581                    .ok_or(ErrorCode::RegionFull)? = (header.len & 0xFF) as u8;
582                *region_data
583                    .get_mut(offset + HASH_OFFSET)
584                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 56) as u8;
585                *region_data
586                    .get_mut(offset + HASH_OFFSET + 1)
587                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 48) as u8;
588                *region_data
589                    .get_mut(offset + HASH_OFFSET + 2)
590                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 40) as u8;
591                *region_data
592                    .get_mut(offset + HASH_OFFSET + 3)
593                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 32) as u8;
594                *region_data
595                    .get_mut(offset + HASH_OFFSET + 4)
596                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 24) as u8;
597                *region_data
598                    .get_mut(offset + HASH_OFFSET + 5)
599                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 16) as u8;
600                *region_data
601                    .get_mut(offset + HASH_OFFSET + 6)
602                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key >> 8) as u8;
603                *region_data
604                    .get_mut(offset + HASH_OFFSET + 7)
605                    .ok_or(ErrorCode::RegionFull)? = (header.hashed_key) as u8;
606
607                // Hash the new header data
608                check_sum.update(
609                    region_data
610                        .get(offset + VERSION_OFFSET..=offset + HASH_OFFSET + 7)
611                        .ok_or(ErrorCode::CorruptData)?,
612                );
613
614                // Copy the value
615                let slice = region_data
616                    .get_mut((offset + HEADER_LENGTH)..(offset + package_length))
617                    .ok_or(ErrorCode::ObjectTooLarge)?;
618                slice.copy_from_slice(value);
619
620                // Include the value in the hash
621                check_sum.update(value);
622
623                // Append a Check Hash
624                let check_sum = check_sum.finalise();
625                let slice = region_data
626                    .get_mut((offset + package_length)..(offset + package_length + CHECK_SUM_LEN))
627                    .ok_or(ErrorCode::ObjectTooLarge)?;
628                slice.copy_from_slice(&check_sum.to_ne_bytes());
629
630                // Write the data back to the region
631                if let Err(e) = self.controller.write(
632                    S * new_region + offset,
633                    region_data
634                        .get(offset..(offset + package_length + CHECK_SUM_LEN))
635                        .ok_or(ErrorCode::ObjectTooLarge)?,
636                ) {
637                    self.read_buffer.replace(Some(region_data));
638                    match e {
639                        ErrorCode::WriteNotReady(_) => return Ok(SuccessCode::Queued),
640                        _ => return Err(e),
641                    }
642                }
643
644                self.read_buffer.replace(Some(region_data));
645                return Ok(SuccessCode::Written);
646            }
647        }
648    }
649
650    /// Retrieves the value from flash storage.
651    ///
652    /// - `hash`: A hashed key.
653    /// - `buf`: A buffer to store the value to.
654    ///
655    /// On success a `SuccessCode` will be returned and the length of the value
656    /// for the corresponding key. On error a `ErrorCode` will be returned.
657    ///
658    /// If a power loss occurs before success is returned the data is assumed to
659    /// be lost.
660    pub fn get_key(&self, hash: u64, buf: &mut [u8]) -> Result<(SuccessCode, usize), ErrorCode> {
661        let region = self.get_region(hash);
662
663        let mut region_offset: isize = 0;
664
665        loop {
666            let check_sum = crc32::Crc32::new();
667            let new_region = match self.state.get() {
668                State::None => (region as isize + region_offset) as usize,
669                State::Init(state) => {
670                    match state {
671                        InitState::GetKeyReadRegion(reg) => reg,
672                        _ => {
673                            // Get the data from that region
674                            (region as isize + region_offset) as usize
675                        }
676                    }
677                }
678                State::GetKey(key_state) => match key_state {
679                    KeyState::ReadRegion(reg) => reg,
680                },
681                _ => unreachable!(),
682            };
683
684            // Get the data from that region
685            let region_data = self.read_buffer.take().unwrap();
686            if self.state.get() != State::GetKey(KeyState::ReadRegion(new_region))
687                && self.state.get() != State::Init(InitState::GetKeyReadRegion(new_region))
688            {
689                if let Err(e) = self.controller.read_region(new_region, region_data) {
690                    self.read_buffer.replace(Some(region_data));
691                    if let ErrorCode::ReadNotReady(reg) = e {
692                        self.state.set(State::GetKey(KeyState::ReadRegion(reg)));
693                    }
694                    return Err(e);
695                }
696            }
697
698            match self.find_key_offset(hash, region_data) {
699                Ok((offset, total_length)) => {
700                    // Add the header data to the check hash
701                    check_sum.update(
702                        region_data
703                            .get(offset..(HEADER_LENGTH + offset))
704                            .ok_or(ErrorCode::ObjectTooLarge)?,
705                    );
706
707                    // The size of the stored object's actual data;
708                    let value_length = total_length as usize - HEADER_LENGTH - CHECK_SUM_LEN;
709
710                    // Make sure if will fit in the buffer
711                    if buf.len() < value_length {
712                        // The entire value is not going to fit,
713                        // Let's still copy in what we can and return an error
714                        for i in 0..buf.len() {
715                            *buf.get_mut(i)
716                                .ok_or(ErrorCode::BufferTooSmall(value_length))? = *region_data
717                                .get(offset + HEADER_LENGTH + i)
718                                .ok_or(ErrorCode::BufferTooSmall(value_length))?;
719                        }
720
721                        self.read_buffer.replace(Some(region_data));
722                        return Err(ErrorCode::BufferTooSmall(value_length));
723                    }
724
725                    // Copy in the value
726                    for i in 0..value_length {
727                        *buf.get_mut(i)
728                            .ok_or(ErrorCode::BufferTooSmall(value_length))? = *region_data
729                            .get(offset + HEADER_LENGTH + i)
730                            .ok_or(ErrorCode::CorruptData)?;
731                        check_sum.update(&[*buf.get(i).ok_or(ErrorCode::CorruptData)?])
732                    }
733
734                    // Check the hash
735                    let check_sum = check_sum.finalise();
736                    let check_sum = check_sum.to_ne_bytes();
737
738                    if *check_sum.get(3).ok_or(ErrorCode::InvalidCheckSum)?
739                        != *region_data
740                            .get(offset + total_length as usize - 1)
741                            .ok_or(ErrorCode::InvalidCheckSum)?
742                        || *check_sum.get(2).ok_or(ErrorCode::InvalidCheckSum)?
743                            != *region_data
744                                .get(offset + total_length as usize - 2)
745                                .ok_or(ErrorCode::InvalidCheckSum)?
746                        || *check_sum.get(1).ok_or(ErrorCode::InvalidCheckSum)?
747                            != *region_data
748                                .get(offset + total_length as usize - 3)
749                                .ok_or(ErrorCode::InvalidCheckSum)?
750                        || *check_sum.first().ok_or(ErrorCode::InvalidCheckSum)?
751                            != *region_data
752                                .get(offset + total_length as usize - 4)
753                                .ok_or(ErrorCode::InvalidCheckSum)?
754                    {
755                        self.read_buffer.replace(Some(region_data));
756                        return Err(ErrorCode::InvalidCheckSum);
757                    }
758
759                    self.read_buffer.replace(Some(region_data));
760                    return Ok((SuccessCode::Complete, value_length));
761                }
762                Err((cont, e)) => {
763                    self.read_buffer.replace(Some(region_data));
764
765                    if cont {
766                        region_offset = new_region as isize - region as isize;
767                        match self.increment_region_offset(region, region_offset) {
768                            Some(o) => {
769                                region_offset = o;
770                                self.state.set(State::None);
771                            }
772                            None => {
773                                return Err(e);
774                            }
775                        }
776                    } else {
777                        return Err(e);
778                    }
779                }
780            }
781        }
782    }
783
784    /// Invalidates the key in flash storage
785    ///
786    /// `hash`: A hashed key.
787    ///
788    /// On success nothing will be returned.
789    /// On error a `ErrorCode` will be returned.
790    ///
791    /// If a power loss occurs before success is returned the data is
792    /// assumed to be lost.
793    pub fn invalidate_key(&self, hash: u64) -> Result<SuccessCode, ErrorCode> {
794        let region = self.get_region(hash);
795
796        let mut region_offset: isize = 0;
797
798        loop {
799            // Get the data from that region
800            let new_region = match self.state.get() {
801                State::None => (region as isize + region_offset) as usize,
802                State::InvalidateKey(key_state) => match key_state {
803                    KeyState::ReadRegion(reg) => reg,
804                },
805                _ => unreachable!(),
806            };
807
808            // Get the data from that region
809            let region_data = self.read_buffer.take().unwrap();
810            if self.state.get() != State::InvalidateKey(KeyState::ReadRegion(new_region)) {
811                if let Err(e) = self.controller.read_region(new_region, region_data) {
812                    self.read_buffer.replace(Some(region_data));
813                    if let ErrorCode::ReadNotReady(reg) = e {
814                        self.state
815                            .set(State::InvalidateKey(KeyState::ReadRegion(reg)));
816                    }
817                    return Err(e);
818                }
819            }
820
821            match self.find_key_offset(hash, region_data) {
822                Ok((offset, _data_len)) => {
823                    // We found a key, let's delete it
824                    *region_data
825                        .get_mut(offset + LEN_OFFSET)
826                        .ok_or(ErrorCode::CorruptData)? &= !0x80;
827
828                    if let Err(e) = self.controller.write(
829                        S * new_region + offset + LEN_OFFSET,
830                        region_data
831                            .get(offset + LEN_OFFSET..offset + LEN_OFFSET + 1)
832                            .ok_or(ErrorCode::ObjectTooLarge)?,
833                    ) {
834                        self.read_buffer.replace(Some(region_data));
835                        match e {
836                            ErrorCode::WriteNotReady(_) => return Ok(SuccessCode::Queued),
837                            _ => return Err(e),
838                        }
839                    }
840
841                    self.read_buffer.replace(Some(region_data));
842                    return Ok(SuccessCode::Written);
843                }
844                Err((cont, e)) => {
845                    self.read_buffer.replace(Some(region_data));
846
847                    if cont {
848                        region_offset = new_region as isize - region as isize;
849                        match self.increment_region_offset(region, region_offset) {
850                            Some(o) => {
851                                region_offset = o;
852                                self.state.set(State::None);
853                            }
854                            None => {
855                                return Err(e);
856                            }
857                        }
858                    } else {
859                        return Err(e);
860                    }
861                }
862            }
863        }
864    }
865
866    /// Zeroises the key in flash storage.
867    ///
868    /// This is similar to the `invalidate_key()` function, but instead will
869    /// change all `1`s in the value and checksum to `0`s. This does
870    /// not remove the header, as that is required for garbage collection
871    /// later on, so the length and hashed key will still be preserved.
872    ///
873    /// The values will be changed by a single write operation to the flash.
874    /// The values are not securley overwritten to make restoring data
875    /// difficult.
876    ///
877    /// Users will need to check with the hardware specifications to determine
878    /// if this is cryptographically secure for their use case.
879    ///
880    /// <https://en.wikipedia.org/wiki/Zeroisation>
881    ///
882    /// `hash`: A hashed key.
883    ///
884    /// On success nothing will be returned.
885    /// On error a `ErrorCode` will be returned.
886    ///
887    /// If a power loss occurs before success is returned the data is
888    /// assumed to be lost.
889    pub fn zeroise_key(&self, hash: u64) -> Result<SuccessCode, ErrorCode> {
890        let region = self.get_region(hash);
891
892        let mut region_offset: isize = 0;
893
894        loop {
895            // Get the data from that region
896            let new_region = match self.state.get() {
897                State::None => (region as isize + region_offset) as usize,
898                State::ZeroiseKey(key_state) => match key_state {
899                    KeyState::ReadRegion(reg) => reg,
900                },
901                _ => unreachable!(),
902            };
903
904            // Get the data from that region
905            let region_data = self.read_buffer.take().unwrap();
906            if self.state.get() != State::ZeroiseKey(KeyState::ReadRegion(new_region)) {
907                if let Err(e) = self.controller.read_region(new_region, region_data) {
908                    self.read_buffer.replace(Some(region_data));
909                    if let ErrorCode::ReadNotReady(reg) = e {
910                        self.state.set(State::ZeroiseKey(KeyState::ReadRegion(reg)));
911                    }
912                    return Err(e);
913                }
914            }
915
916            match self.find_key_offset(hash, region_data) {
917                Ok((offset, data_len)) => {
918                    // We found a key, let's delete it
919                    *region_data
920                        .get_mut(offset + LEN_OFFSET)
921                        .ok_or(ErrorCode::CorruptData)? &= !0x80;
922
923                    // Replace Value with 0s
924                    for i in HEADER_LENGTH..(data_len as usize + HEADER_LENGTH) {
925                        *region_data
926                            .get_mut(offset + i)
927                            .ok_or(ErrorCode::RegionFull)? = 0;
928                    }
929
930                    let write_len = data_len as usize;
931
932                    if let Err(e) = self.controller.write(
933                        S * new_region + offset,
934                        region_data
935                            .get(offset..offset + write_len)
936                            .ok_or(ErrorCode::ObjectTooLarge)?,
937                    ) {
938                        self.read_buffer.replace(Some(region_data));
939                        match e {
940                            ErrorCode::WriteNotReady(_) => return Ok(SuccessCode::Queued),
941                            _ => return Err(e),
942                        }
943                    }
944
945                    self.read_buffer.replace(Some(region_data));
946                    return Ok(SuccessCode::Written);
947                }
948                Err((cont, e)) => {
949                    self.read_buffer.replace(Some(region_data));
950
951                    if cont {
952                        region_offset = new_region as isize - region as isize;
953                        match self.increment_region_offset(region, region_offset) {
954                            Some(o) => {
955                                region_offset = o;
956                                self.state.set(State::None);
957                            }
958                            None => {
959                                return Err(e);
960                            }
961                        }
962                    } else {
963                        return Err(e);
964                    }
965                }
966            }
967        }
968    }
969
970    fn garbage_collect_region(
971        &self,
972        region: usize,
973        flash_freed: usize,
974    ) -> Result<usize, ErrorCode> {
975        // Get the data from that region
976        let region_data = self.read_buffer.take().unwrap();
977        if self.state.get() != State::GarbageCollect(RubbishState::ReadRegion(region, flash_freed))
978        {
979            if let Err(e) = self.controller.read_region(region, region_data) {
980                self.read_buffer.replace(Some(region_data));
981                if let ErrorCode::ReadNotReady(reg) = e {
982                    self.state
983                        .set(State::GarbageCollect(RubbishState::ReadRegion(
984                            reg,
985                            flash_freed,
986                        )));
987                }
988                return Err(e);
989            }
990        }
991
992        let mut entry_found = false;
993        let mut offset: usize = 0;
994
995        loop {
996            if offset >= S {
997                // We have reached the end of the region without finding a
998                // valid object. All entries must be marked for deletion then.
999                break;
1000            }
1001
1002            // Check to see if we have data
1003            if *region_data
1004                .get(offset + VERSION_OFFSET)
1005                .ok_or(ErrorCode::KeyNotFound)?
1006                != 0xFF
1007            {
1008                // We found a version, check that we support it
1009                if *region_data
1010                    .get(offset + VERSION_OFFSET)
1011                    .ok_or(ErrorCode::KeyNotFound)?
1012                    != VERSION
1013                {
1014                    self.read_buffer.replace(Some(region_data));
1015                    return Err(ErrorCode::UnsupportedVersion);
1016                }
1017
1018                entry_found = true;
1019
1020                // Find this entries length
1021                let total_length = ((*region_data
1022                    .get(offset + LEN_OFFSET)
1023                    .ok_or(ErrorCode::CorruptData)? as u16)
1024                    & !0xF0)
1025                    << 8
1026                    | *region_data
1027                        .get(offset + LEN_OFFSET + 1)
1028                        .ok_or(ErrorCode::CorruptData)? as u16;
1029
1030                // Check to see if the entry has been deleted
1031                if *region_data
1032                    .get(offset + LEN_OFFSET)
1033                    .ok_or(ErrorCode::CorruptData)?
1034                    & 0x80
1035                    != 0x80
1036                {
1037                    // The entry has been deleted, this region might be ready
1038                    // for erasure.
1039                    // Increment our offset by the length and repeat the loop
1040                    offset += total_length as usize;
1041                    continue;
1042                }
1043
1044                // We have found a valid entry!
1045                // Don't perform an erase!
1046                self.read_buffer.replace(Some(region_data));
1047                return Ok(0);
1048            } else {
1049                // We hit the end of valid data.
1050                // The possible outcomes:
1051                //    * The region is empty, we don't need to do anything
1052                //    * The region has entries, all of which are marked for
1053                //      deletion
1054                if !entry_found {
1055                    // We didn't find anything, don't bother erasing an empty region.
1056                    self.read_buffer.replace(Some(region_data));
1057                    return Ok(0);
1058                }
1059                break;
1060            }
1061        }
1062
1063        self.read_buffer.replace(Some(region_data));
1064
1065        // If we got down here, the region is ready to be erased.
1066
1067        if let Err(e) = self.controller.erase_region(region) {
1068            if let ErrorCode::EraseNotReady(reg) = e {
1069                self.state
1070                    .set(State::GarbageCollect(RubbishState::EraseRegion(
1071                        reg,
1072                        flash_freed + S,
1073                    )));
1074            }
1075            return Err(e);
1076        }
1077
1078        Ok(S)
1079    }
1080
1081    /// Perform a garbage collection on TicKV
1082    ///
1083    /// On success the number of bytes freed will be returned.
1084    /// On error a `ErrorCode` will be returned.
1085    pub fn garbage_collect(&self) -> Result<usize, ErrorCode> {
1086        let num_region = self.flash_size / S;
1087        let mut flash_freed = 0;
1088        let start = match self.state.get() {
1089            State::None => 0,
1090            State::GarbageCollect(state) => match state {
1091                RubbishState::ReadRegion(reg, ff) => {
1092                    flash_freed += ff;
1093                    reg
1094                }
1095                // We already erased region reg, so move to the next one
1096                RubbishState::EraseRegion(reg, ff) => {
1097                    flash_freed += ff;
1098                    reg + 1
1099                }
1100            },
1101            _ => unreachable!(),
1102        };
1103
1104        for i in start..num_region {
1105            match self.garbage_collect_region(i, flash_freed) {
1106                Ok(freed) => flash_freed += freed,
1107                Err(e) => return Err(e),
1108            }
1109        }
1110
1111        Ok(flash_freed)
1112    }
1113}
tickv/tickv.rs

tickv/
tickv.rs
