The problem that I didn't think out

[zhao, forrest]

> > If we store the erase block usage information in a file on flash,
> > we need to sort it in RAM in order to find the dirtiest one.
> > Then this sort operation is O(N), N is the number of erase blocks.
> > Also the memory consumed by this sorted data structure is O(N).
> We may devide this file on constant-size chunks, and search only one 
> chunk at a time. And we may have a list of 10 most worn out eraseblocks 
> and keep it in the superblock. So the scalability will be O(1) IMO.
> 
I think keeping track of a list of 10 most worn out eraseblocks
is hard to be O(1) since this list is changed dynamically.
In particular, we need to recalculate the list after every update
operation; in order to recalculate the list we need to keep the usage
information of all erase blocks in RAM in sorted manner. So if this is
the case, the RAM occupation is O(N).


> > I used to think that we could put the sorted data structure on flash,
> > but this will incur enormous update operations.
> Enormous? This needs measuring and evaluating. Let's create a user-level 
> prototype and see.

Agree. We need to do much measuring, evaluating and comparing work
before achieving the final design decision.
Do you have a time table for the user-level prototype? I think I can
give my contribution to it.


Thanks,
Forrest