4.1 Formatting an FFS Partition

The formatting utility is responsible for initializing the contents of a Flash File System partition. This is a multi-step process summarized as follows:

Obtain the geometry information for the partition.

1. The formatting utility will need to know the number of erase blocks in a partition and the erase block size. It needs this information to determine the number and size of the blocks in the partition it is formatting. The data structures it is about to create are located at fixed positions within each block. Hence the requirement for the block size and total.

2. Set the number of spare blocks in the partition.

Either assume the partition will have only one spare block, or ask the user if additional spare blocks should be set aside. A spare block is a block that is used by the file system to reclaim deallocated areas in other blocks within the partition. It is NEVER used to store file system structures or data and is only used in the file system's block reclamation process. Unless at least one spare block within the partition exists, the file system will be unable to reclaim space in other blocks in the event that they are entirely filled.

Additional spare blocks, beyond the mandatory one, and up to a maximum of 8, may be set aside by the formatting utility. Having additional spare blocks has two advantages:

a. When the media is extremely full, additional spare blocks speed the file system's deallocated space reclamation process because it does not have to wait on a single block to be erased before it can continue doing writes.

b. If an unrecoverable error occurs in erasing a block, the block is marked as retired. Having additional spare blocks allows the file system to recover from the error and to continue to reclaim deallocated space with the media. However, once all spare blocks are consumed because of erase errors, the file system resorts to WORM behavior and deallocated space reclamation is no longer possible.

3. If a Flash File System partition already exists on the media, obtain information from each block allocation structure and save it.

If a Flash File System partition does not already exist, skip this step. However, if a Flash File System partition does exist, information from each block allocation structure must be read and saved across the format operation.

Recall that the block allocation structure is stored at the END of every block. This means the Status member of the block allocation structure occupies the LAST word in the block.

Obtain the following information from the block allocation structure:

a. The first item of information to be obtained is the Status of the block. A block may have a status of retired indicating that it cannot be reused for some reason. The file system writes the retired status into the block Status to indicate that it is not to be reused.

b. Bits 15-12 of the block Status word contains block status information. If these bits are set to retired status, the block should not be used. The blocks having this condition should be recorded so they can be marked as retired after media erasure.

c. For each block that is not retired save the erase count. This count is needed so that the file system can evenly cycle the reuse of blocks. Each erase count should be incremented and rewritten after the block is erased.

4. Erase the partition.

Erase the entire partition. After erasure all bits within the partition must be 1's. If a block contains bits that cannot be set to 1's, the block number should be saved so that the block can be marked as retired when it is time to update the block's status.

5. Initialize the block allocation structure of all blocks that are not spares. If a Flash File System partition previously existed, the block allocation structure information previously read must be rewritten. Specifically, the erase count and status must be restored.

After all blocks have had their block allocation structures initialized only the boot record and the root directory entry for this partition need be created. Again, note that the block allocation structure is stored at the END of every block. This means the Status member of the block allocation structure occupies the LAST word in the block.

The remainder of the physical block that precedes the block allocation structure must have been erased to all 1's.

Block struc
EraseCount dd ? ; If no file system partition previously existed, this field
; should be set to 1. If a Flash File System partition
; previously existed, this field should be set to the
; updated value of the erase count that you saved for this
; specific physical block.
BlockSeq dw ? ;
BlockSeqChecksum dw ? ; Is simply the 1's complement of the BlockSeq value for
; this physical block.
Status dw C3FFh ; This status indicates a READY block.
; However, if the status of this physical block had been
; previously marked as retired because it was so
; designated in a previously existing file system partition,
; or the erase processing determined that it should be
; retired, the field should be set to 0000h. This status
; value indicates that the block is retired and should NOT
; be reused. Skip all other field assignments for this
; physical block.
Block ends

Since the block is not designated a spare, the BlockSeq and BlockSeqChecksum fields must be initialized. The first physical block in the partition must have a BlockSeq of 0, the second 1, the third 2 and so on. Suppose a partition contains n blocks and has two spare blocks. The partition 'size', as far as the file system is concerned, is (n-2) blocks because the spares are not used for file system storage. In this example the BlockSeq numbers will have the following sequence (0, 1, 2...(n-3)). Note that blocks that have been rejected because of their retired status are NOT included in this sequence.

6. Initialize the block allocation structure of all spare blocks. If a Flash File System partition previously existed, the block allocation structure information previously read must be rewritten. Specifically, the erase count and status must be restored.

A physical block that is a designated as a spare block DOES NOT HAVE ITS BlockSeq OR BlockSeqChecksum FIELDS UPDATED. The file system uses a BlockSeq and a BlockSeqChecksum that are all 1's to indicate that this is a spare block. Spare block(s) can be placed anywhere in the partition. For simplicity, they can be located at the beginning of the partition. Note that there MUST be at least one spare block for the file system to operate correctly.

The remainder of the physical block that precedes the block allocation structure must have been erased to all 1's.

Block struc
EraseCount dd ? ; If no file system partition previously existed, this field
; should set to 1. If a Flash File System partition
; previously existed, this field should be set to the
; updated value of the erase count that you saved for this
; specific physical block.
BlockSeq dw FFFFh ; Is all 1's for a spare block.
BlockSeqChecksum dw FFFFh ; Is all 1's for a spare block.
Status dw F3FFh ; This status indicates a spare block.
; However, if the status of this physical block had been
; previously marked as retired because it was so
; designated in a previously existing file system partition,
; or the erase processing determined that it should be
; retired, the field should be set to 0000h. This status
; value indicates that the block is retired and should NOT
; be reused. Skip all other field assignments for this
; physical block.
Block ends

7. Create and write the boot record and root directory entry in the first block of the partition. The boot record, in this example, is located at offset 0 within this block. The formatting utility will need the media geometry information previously obtained. The block allocation structure in the first block will also have to be updated to include the entries for the boot record and root directory. If desired, the formatting utility can also include a 'volume label' during the formatting process. A 'volume label' is created by creating a FileEntry structure, assigning it the attribute of 'volume label', and pointing the primary pointer of the root directory at the FileEntry. This makes the 'volume label' appear as a child of the root directory, which it must properly be. If a volume label isn't desired, then the root directory entry PrimaryPtr is simply left FNULL and the volume label isn't written. This example includes a volume label.

The physical block containing the BlockSeq value of 0 was arbitrarily chosen to contain the boot record, root directory entry, volume label, and corresponding block allocation structure for this partition. However, they could be located anywhere in the partition.

The structure members of the BootRecord must be assigned the following values.

BootRecord struc
Signature dw F1A5h ; FLASH media signature.
SerialNumber dd ? ; Holds a unique identifier for the partition.
FFSWriteVersion dw 0200h ; FFS Version 2.0 required for write.
FFSReadVersion dw 0200h ; FFS Version 2.0 required for read.
TotalBlockCount dw ? ; Media implementation dependent.
SpareBlockCount dw 0001h ; Minimum of one. Maximum of 8.
BlockLen dd ? ; Media implementation dependent.
RootDirectoryPtr dd 00000001h ; Pointer to the root DirEntry.
Status dw FFFFh ; MS-DOS file naming conventions.
BootCodeLen dw 0000h ; Indicates no boot code is in this boot record. This
; card is not bootable.
BootCode db ... ; If the media were bootable, boot code would be inserted
; here. This field is not allocated. BootCodeLen is the last
; valid field.
BootRecord ends

The root DirEntry, in this example, immediately follows the BootRecord structure. It starts precisely where the BootRecord ends. The structure members of the root DirEntry structure should be assigned the following values.

RootDirEntry struc
Status dw FFE1h ; Indicates that the directory entry exists & does NOT
; have most recent attribute/date/time information,
; & primary pointer is valid (points to volume label).
SiblingPtr dd FFFFFFFFh ; FNULL pointer value.
; The ROOT must NEVER have a sibling!
PrimaryPtr dd 00000002h ; Pointer to the volume label.
SecondaryPtr dd FFFFFFFFh ; FNULL pointer value.
; The ROOT must NEVER be superseded!
Attributes db 10h ; Same format as MS-DOS attributes.
; Bits Definition
; 7-6 Reserved. Must be 0's.
; 5 1 = ARCHIVE file was modified
; 4 1 = DIRECTORY 0 = file
; 3 1 = VOLUME label
; 2 1 = SYSTEM file or directory
; 1 1 = HIDDEN file or directory
; 0 1 = READONLY file
Time dw FFFFh ; Left all ones (unused).

Date dw FFFFh ; Left all ones (unused).
VarStructLen dw 0 ; No variable length structs follow Name.Ext.
NameLen db 11 ; MS-DOS name length.
Name db "ROOT " ; The root directory has a name.ext of 'ROOT '.
Ext db " " ;
RootDirEntry ends

The volume label VolLabelFileEntry, in this example, immediately follows the RootDirEntry structure. It starts precisely where the RootDirEntry ends. The structure members of the root VolLabFileEntry structure should be assigned the following values.

VolLabFileEntry struc
Status dw FFF7h ; Indicates that the file entry exists, ; & has most recent attrib/time/date information.
SiblingPtr dd FFFFFFFFh ; FNULL pointer value (no initial siblings).
PrimayPtr dd FFFFFFFFh ; FNULL pointer value (no children, ever).
SecondaryPtr dd FFFFFFFFh ; FNULL pointer value (not superseded).
; The ROOT will never be superseded!
Attributes db 08h ; Same format as MS-DOS attributes.
; Bits Definition
; 7-6 Reserved. Must be 0's.
; 5 1 = ARCHIVE file was modified
; 4 1 = DIRECTORY 0 = file
; 3 1 = VOLUME label
; 2 1 = SYSTEM file or directory
; 1 1 = HIDDEN file or directory
; 0 1 = READONLY file
Time dw (FILL IN) ; Same format as MS-DOS time.
; Bits Definition
; 15..11 Binary number of hours (0-23).
; 10...5 Binary number of minutes (0-59).
; 4...0 Binary number of 2 second increments
; (0-29, corresponding to 0-58 seconds).
Date dw (FILL IN) ; Same format as MS-DOS date.
; Bits Definition
; 15...9 Year (relative to 1980)
; 8...5 Month (1-12)
; 4...0 Day of month (1-31)
VarStructLen dw 0 ; No variable length structs follow Name.Ext.
NameLen db 11 ; MS-DOS name length.
Name db "BOGFLOB " ; The volume is named 'BOGFLOB '.
Ext db " " ;
VolLabFileEntry ends

The Block Allocation structure must be located at the end of the specified physical block. The structure members of the Block Allocation structure must be assigned the following values.

Block struc

;------------------------------------------------------------------------------

; Alloc[2] --- Third, and last, allocation: the volume label

;------------------------------------------------------------------------------

Status2 db BFh ; Active & last FileEntry allocation.

Offset2 db (size BootRecord + size RootDirEntry),0,0 ; Offset, relative to the beginning of this

; block, of the volume label FileEntry.

Len2 dw (size VolLabFileEntry) ; Length of this allocation.

;------------------------------------------------------------------------------

; Alloc[1] --- Second, and not last, allocation: the root directory

;------------------------------------------------------------------------------

Status1 db 3Fh ; Active & not last DirEntry allocation.

Offset1 db size BootRecord,0,0 ; Offset, relative to the beginning of this block,

; of the root DirEntry.

Len1 dw (size RootDirEntry) ; Length of this allocation.

;------------------------------------------------------------------------------

; Alloc[0] --- First, and not last, allocation: the boot record

;------------------------------------------------------------------------------

Status0 db 3Fh ; Active & not last BootRecord allocation.

Offset0 db 0, 0, 0 ; Offset, relative to the beginning of this block,

; of the BootRecord.

Len0 dw (size BootRecord) ; Length of this allocation.

;------------------------------------------------------------------------------

; Fixed length portion of BlockAlloc record

;------------------------------------------------------------------------------

BootRecordPtr dd 00000000h ; Pointer to the BootRecord.
EraseCount dd (FILL IN) ; Must be at least 1 or greater depending on whether
; this partition had been used previously.
BlockSeq dw 0000h ; Block 0 within the sequence of blocks in this
; partition.
BlockSeqChecksum dw FFFFh ; Checksum for a block sequence value of 0.
Status dw C3FEh ; Block contains allocations and the boot record for
; the partition and is ready for use.
Block ends

8. Indicate to the file system that the media has changed. Not doing so will cause the file system to malfunction.

At this point the newly created partition is ready for use. The guidelines provided in this section assume that the format utility is processing blocks in their physical order starting at the first block and proceeding to the last block in the partition. This is done only for the sake of example.