However, after an unexpected reboot, it would take considerable time to rebuild
the direct and indirect maps, which are incompatible with the request of a fast
reboot time. Also, many of these algorithms are patented.
While algorithms based on virtual block mapping can greatly extend the lifetime
of flash memory, this comes at the price of increased complexity, of a large memory
footprint, and of a garbage collection mechanism for reclaiming invalid sectors. As
this is again incompatible with real-time constraints, it is not an option in our case.
Another approach is the use of a log-structured file system such as JFFS [64].
Log-structured file systems do not structurally separate metadata and payload data
but instead maintain a comprehensive log of all performed operations in chronological order.
While wear leveling is implicit in such systems, they still suffer from the garbage
collection problem, which again disqualifies them for use.
Therefore, we refrain from using such advanced storing schemata and propose a
simple circular buffer structure, where recovery points are stored linear on the flash,
aligned to flash blocks. Whenever a new erase unit is entered, an erase operation is
performed as a preparation for subsequent writing.
The obvious drawback of this scheme is internal fragmentation if the size of a
recovery point is not an exact multiple of the elementary block size. We consider
this as acceptable in particular because recovery points usually occupy a high
number of blocks, which results in a very low percentage of lost space.
8.7.4 Implementation Aspects
In addition to the recovery points, some metadata is recorded on the stable storage:
The Stable Storage (SS) header occupies n erase blocks and describes the current
contents of the stable storage. If only full system snapshots are supported, no header
at all is required, as the recovery points have fixed size.
The stable storage is partitioned in m buckets, aligned to erase blocks and the
recovery points are stored in increasing order in the buckets. The latest used bucket
is kept in memory to ensure fast access to the last stored recovery point and a
sequence number stored together with the recovery point ensures that the recovery
point history is recoverable if the memory is corrupted due to a fault.
If recovery points do not cover the whole system, i.e., task-based, the size of
each recovery point varies and the stable storage cannot be partitioned in fixed-size
buckets.
Instead, a header is introduced that contains a chronological list of stored recovery points. Such a header entry contains a global sequence number (analog to a
timestamp), and the start and end block where the recovery point is stored.
The same sequence number, a unique fingerprint, a state variable, and a
checksum calculated over the whole recovery point are stored with the actual
recovery point data. The recovery points are again aligned to erase blocks, and the
index of the latest stored recovery point is kept in memory for fast access.
134
8 Recovery Preparation
the direct and indirect maps, which are incompatible with the request of a fast
reboot time. Also, many of these algorithms are patented.
While algorithms based on virtual block mapping can greatly extend the lifetime
of flash memory, this comes at the price of increased complexity, of a large memory
footprint, and of a garbage collection mechanism for reclaiming invalid sectors. As
this is again incompatible with real-time constraints, it is not an option in our case.
Another approach is the use of a log-structured file system such as JFFS [64].
Log-structured file systems do not structurally separate metadata and payload data
but instead maintain a comprehensive log of all performed operations in chronological order.
While wear leveling is implicit in such systems, they still suffer from the garbage
collection problem, which again disqualifies them for use.
Therefore, we refrain from using such advanced storing schemata and propose a
simple circular buffer structure, where recovery points are stored linear on the flash,
aligned to flash blocks. Whenever a new erase unit is entered, an erase operation is
performed as a preparation for subsequent writing.
The obvious drawback of this scheme is internal fragmentation if the size of a
recovery point is not an exact multiple of the elementary block size. We consider
this as acceptable in particular because recovery points usually occupy a high
number of blocks, which results in a very low percentage of lost space.
8.7.4 Implementation Aspects
In addition to the recovery points, some metadata is recorded on the stable storage:
The Stable Storage (SS) header occupies n erase blocks and describes the current
contents of the stable storage. If only full system snapshots are supported, no header
at all is required, as the recovery points have fixed size.
The stable storage is partitioned in m buckets, aligned to erase blocks and the
recovery points are stored in increasing order in the buckets. The latest used bucket
is kept in memory to ensure fast access to the last stored recovery point and a
sequence number stored together with the recovery point ensures that the recovery
point history is recoverable if the memory is corrupted due to a fault.
If recovery points do not cover the whole system, i.e., task-based, the size of
each recovery point varies and the stable storage cannot be partitioned in fixed-size
buckets.
Instead, a header is introduced that contains a chronological list of stored recovery points. Such a header entry contains a global sequence number (analog to a
timestamp), and the start and end block where the recovery point is stored.
The same sequence number, a unique fingerprint, a state variable, and a
checksum calculated over the whole recovery point are stored with the actual
recovery point data. The recovery points are again aligned to erase blocks, and the
index of the latest stored recovery point is kept in memory for fast access.
134
8 Recovery Preparation