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

tickv/
tickv.rs
