Flash Store

How Flash memory works

• Erased bytes are all ones, ie. clean byte has value 0xFF.
• It is possible to "clear" any bit into 0. It's NOT possible to change them back to 1 by "normal" write.
• Changing bits back to 1 is done by blocks. Erase block size depends on model of Flash memory. In Newtons internal memory erase blocks are 64KB big.

Flash Blocks

Due to "block based" nature of Flash memory object store is divided into blocks. Store blocks are of equal length to flash erase blocks.

Generally blocks are divided into two areas - starting on offset 4 there is "object" area, and at the end of block there is "block log" area. In 64KB blocks log area starts at offset 0xFC00.

Log area contains general information about given block. Every log entry contatins few signatures, sequence number and entry size.

There are three types of entries written in block log:

• Flash Block Log Entry

  This is used to store general attributes of given block, like:

  • Logical block number
  • OID prefix for objects
  • Erase count
  • Block signature
• Flash Erase Log Entry

  This log entry stores information about different block, which was erased in that time - most important one is erase count.

• Reserved Block Log Entry

  Reserved blocks are used for substituting logical blocks in case of flash hardware failure.

Objects are placed in object area, one after another, 4 bytes aligned. Every object starts with 8 byte header, which contain:

• Object flags (present/erased)
• Object ID
• Object size
• Object flags

In every block first object has OID 3, and this is "block directory". How it works? It's divided into 64 byte "buckets". Each bucket holds offset to local object in this bucket or logical block number of block for "migrated" objects. When we want to read object from block, hash function of OID is used to find out in which bucket object offset is stored. That way we don't have to scan whole block to find object, just few entries in given bucket (entries in bucket are not sorted in any way). When bucket is full, another object with OID 3 is appended to the end of object area, this time only 64 bytes long, and offset to this object is written to full bucket.

Few "special" values for directory entries are:

• 0xFFFFFFF7 reserved entry for newly created object
• 0x00000000 erased object

Block directory entries can be either:

• Object reference (last byte 0xF7)
• Bucket extension reference (last byte 0x77)
• Migrated object reference (last byte 0xB3)

Migrated object reference does not store offset to object in destination block (in destination block another directory entry is created), but it holds destination block logical number and part of object ID (without block prefix).

Transactions

Every object can be in one of following states:

I'll soon describe steps of transactions, and how objects flags are changed.