I would like to implement a simple stack in my microcontroller firmware. The stack I would like to implement is like this, i.e. something standard.
The problem is that the flash memory IC I am using supports page-granularity for write but sector-granularity for erasing and just like any other NAND flash, before writing some data on the flash, you should erase that part.
So as a summary, I erase a sector and write some data on its first page. For rewriting even one byte of that page, I should erase the whole sector first.
In my stack,
| O | O | O | O | O | O |
I push some data:
| W | W | W | O | O | O |
and then pop one of them:
| W | W | P | O | O | O |
Now I would like to push another data. Here the problem appears. If just like a standard stack, I decide to write on previous data and just change the index, I must delete the whole sector first! Therefore I should solve this problem programmatically.
Any ideas?
P.S: The flash memory map is: 16 Blocks -> Each Block = 16 Sectors -> Each Sector = 16 Pages -> Each Page = 256 Bytes
I have a write-command at page level with an offset and erase command for sector and block.
Well, if you don't want to write a whole sector with every push, you'll have to tolerate some old data in your stack:
| W | W | P | W | O | O |
You will need to reserve at least one bit in each item that allows you to distinguish between the valid and invalid ones. Assuming that a sector-erase fills it with 1s, then leave the valid bit 1 in all valid items that you write. You will then be able to change it to a 0 by writing just one page when you pop the item off, marking it as invalid.
Since you can't reuse item slots in this scheme, your stack will grow continuously toward the end of memory. That is actually what you want, since that NAND flash can only be written so many times before it dies, and this scheme will spread the writes out somewhat. When you get to the end of space, you can erase and rewrite the whole thing to remove all the gaps.
It may happen that you end up with a very long sequence of invalid items, so popping past them could involve scanning all the intermediate ones. You can fix this problem by reserving more than one bit in each item. When you write a valid item, you use these bits to store the number of invalid items that precede it, plus 1. This lets you skip back quickly and pop in constant time.
Then, when you want to mark an item as invalid, you can change the bits reserved for this count to all 0s, again by writing just one page. This zero count could not appear in a valid item, so it serves as an invalid mark.