gnupic: Ideas towards small/compact/wear-leveling PIC FlashFS (was: Re: flash filesystem for pic and 24xxx EEPROMs?)
Subject:
Ideas towards small/compact/wear-leveling PIC FlashFS (was: Re: flash
filesystem for pic and 24xxx EEPROMs?)
From:
David McNab ####@####.####
Date:
7 Jan 2005 14:11:25 +0000
Message-Id: <41DE9840.7060709@rebirthing.co.nz>
Bernd Oefinger wrote:
>>I still can't understand what do you mean with 'wear-leveling'!
> Therefore the memory may be "worn out" (=> unusable because the
> first locations cannot be written anymore) far too early compared to
> a filesystem that takes care of this fact and uses no fixed locations for
> management information (=> wear-leveling).
> Modern flash filesystems e.g. those used by Linux take care of this
> problem. Unfortulately they are much too complex to be ported to PIC.
> The only thing that may be ported is the "idea" behind the algorithms.
I've been thinking of a wear-leveling scheme which might suit the
small-footprint requirements of PICs. So here goes with some ideas.
First notion is that the filesystem directories and data be comprised
only of fixed-sized blocks, where each block is prefixed with a 24- or
32-bit 'write count', indicating the number of times that block has been
written to.
Second notion is of small 'master key' blocks, containing only a write
count plus the 'address' within flash space of the filesystem root block.
The directory/data blocks would be allocated from the beginning of flash
address space, and grow upwards. The 'master key' blocks would be
allocated from the end of flash space, and grow downwards.
Before use, the filesystem itself would need to be 'opened'. This would
be a simple function, pseudo-coded in C below:
for (addr = FLASH_ADDR_END - sizeof(MASTER_KEY_BLOCK)
{
flash_set_address(addr);
writecount = flash_read_4_bytes();
if (writecount < FLASH_MAX_WRITES)
break; // this master block is ok
}
root_block_addr = flash_read_4_bytes(); // maybe 2 or 3 would do
This starts at the very end, checking 'master key' blocks till it finds
one whose write limit hasn't been maxed out. The 'root block address'
read from that block points to the location of the data block containing
the filesystem info.
Directory blocks (including the root directory block) would be arranged
in a linked list, sufficient to hold all info on all files (and
subdirectories). For instance, if we're working with 256-byte blocks,
and a directory entry requires 32 bytes, we could have 8 directory
entries per directory block.
When formatting a flash drive, there'd be no need to carve up the whole
space into blocks. We'd only need to create one 'master key' block at
the end, one 'root block' at the front, followed immediately by one
'root directory' block.
When allocating new blocks for creating/appending directories or files,
we would first try the 'free blocks' chain. If empty, we could just
allocate the first available space immediately after the last known block.
So, again using C to specify:
typedef struct
{
uint32 write_count;
uint32 root_block_addr;
}
master_key_block;
typedef struct
{
uint32 write_count;
uint32 root_directory_addr;
uint32 first_free_block;
uint32 start_of_empty_space; // after last allocated block
}
volume_root_block;
typedef struct
{
uint8 name[MAX_NAME_LENGTH];
bool is_a_directory;
uint32 size;
uint32 first_data_block_addr;
}
dir_entry;
typedef struct
{
uint32 write_count;
uint16 num_entries;
uint32 next_block_addr;
dir_entry entries[MAX_DIR_ENTRIES_PER_BLOCK];
}
dir_block;
One last area relates to the in-RAM data structure needed to hold the
info on a currently open file:
typedef struct
{
uint32 dir_block_addr; // address of directory block
// which references the file
uint8 file_idx; // index into 'entries' array
uint32 position; // as in 'ftell()'
uint32 data_block_addr; // address of data block currently
// being accessed
}
FILE;
With careful coding, I envisage the entire filesystem could be
implemented in as little as 2-3kWords on a PIC16F87x or 18Fxx2.
In summary, every possible block on the disk would contain a record of
how many times the block has been written to. If this exceeds the rated
wear count, the block is marked inactive, and its contents are copied to
a freshly allocated block.
Sorry to have gone long, but I needed to get this all down, and onto the
table for discussion, before forgetting any of it.
Thoughts?
--
Cheers
David
