Real-time flash simulator

Real-time flash simulator

[Martin Däumler]

Hello,


what is the current development status of a real-time capable flash
simulator? I am searching for a flash simulator similar to nandsim, but
with real-time garantuees.
Has anybody developed such a simulator or is developing one?

Furthermore, there are some efforts to develop a (scaleable) real-time
capable flash file system?


Many thanks,

Martin

Re: Real-time flash simulator

[Artem Bityutskiy]

Martin,

On Fri, 2007-06-22 at 09:19 +0200, Martin Däumler wrote:
> what is the current development status of a real-time capable flash
> simulator? I am searching for a flash simulator similar to nandsim, but
> with real-time garantuees.
> Has anybody developed such a simulator or is developing one?

I am not an expert in real-time, so I would ask you to elaborate on what
particularly makes nandsim not real-time? What are your requirements?
Which nandsim operation/function/part has to be done in fixed time but
it is not? Why do you think other pieces of kernel code are OK but
nandsim is a bottleneck WRT to real-time?

> Furthermore, there are some efforts to develop a (scaleable) real-time
> capable flash file system?

We develop UBIFS (see MTD web site) but we do not set real-time
requirements. You are welcome to collaborate.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Real-time flash simulator

[Martin Däumler]

Hello Artem,

On Fri, 2007-06-22 at 10:09 +0200, Artem Bityutskiy wrote:
> I am not an expert in real-time, so I would ask you to elaborate on what
> particularly makes nandsim not real-time? What are your requirements?

The flash simulator has to simulate a raw flash memory with given
timings, size, etc. Nandsim performs the delays by busy waiting. The
question is if nandsim will meet this timings on every condition, e.g.
under heavy load. This includes write operations as well as read
operations. The simulator is just software but it has to be
deterministic like real raw flash.

This simulator should be a tool to examine the real time behaviour of
flash file systems.

>> Furthermore, there are some efforts to develop a (scaleable) real-time
>> capable flash file system?
> 
> We develop UBIFS (see MTD web site) but we do not set real-time
> requirements. You are welcome to collaborate.

The overall goal of my work is to develop respectively to examine the
feasibility of a scaleable flash file system on raw flash. Like
mentioned on the MTD web site this might be very difficult because
of wear-levelling and bad block management. In my opinion, for real-time
issues it is necessary to avoid garbage collection. So, a layer between
file system and raw flash, performing wear-levelling and bad block
management could be one approach to be investigated furhter. The
real-time flash simulator is just one step in this direction.


Regards,

Martin

Re: Real-time flash simulator

[Jörn Engel]

On Fri, 22 June 2007 11:23:58 +0200, Martin Däumler wrote:
> 
> The overall goal of my work is to develop respectively to examine the
> feasibility of a scaleable flash file system on raw flash. Like
> mentioned on the MTD web site this might be very difficult because
> of wear-levelling and bad block management. In my opinion, for real-time
> issues it is necessary to avoid garbage collection. So, a layer between
> file system and raw flash, performing wear-levelling and bad block
> management could be one approach to be investigated furhter. The
> real-time flash simulator is just one step in this direction.

What makes the "layer between file system and raw flash" so special, if
you don't mind me asking?  If wear-leveling and bad block management
causes latency, that latency does not go away by moving it to some other
layers.

Jörn

-- 
Anything that can go wrong, will.
-- Finagle's Law

Re: Real-time flash simulator

[Martin Däumler]

Hello Jörn,

On Fri, 22 June 2007 11:39 +0200, Jörn Engel wrote:
>> In my opinion, for real-time
>> issues it is necessary to avoid garbage collection. So, a layer between
>> file system and raw flash, performing wear-levelling and bad block
>> management could be one approach to be investigated furhter. The
>> real-time flash simulator is just one step in this direction.
> 
> What makes the "layer between file system and raw flash" so special, if
> you don't mind me asking?  If wear-leveling and bad block management
> causes latency, that latency does not go away by moving it to some other
> layers.

that is right! The idea is to use a (not specified) file system which 
performs in-place updates on top of this layer. This layer should map
logical to physical erase units. So, wear-levelling possibly could be
used to "displace" garbage collection. The goal is to decrase latency
and above all make it more deterministic.

But please note that is just one theoretical idea to make a flash file
system real-time capable. Indeed, other approaches and file systems like
LogFS has to be investigated further for this purpose too.

It seems the development of a real-time flash file system is still in
the fledgling stages, hence I asked here for a flash simulator to make
work easier.


Regards,

Martin

Re: Real-time flash simulator

[Jörn Engel]

On Fri, 22 June 2007 12:11:29 +0200, Martin Däumler wrote:
> 
> that is right! The idea is to use a (not specified) file system which 
> performs in-place updates on top of this layer. This layer should map
> logical to physical erase units. So, wear-levelling possibly could be
> used to "displace" garbage collection. The goal is to decrase latency
> and above all make it more deterministic.

Sounds just like FAT on smartmedia.  Worst case latency is both
deterministic and low.  Random writes of small blocks are also
prohibitively slow.  Works great when writing few large files, like jpg
images in digital cameras.

> But please note that is just one theoretical idea to make a flash file
> system real-time capable. Indeed, other approaches and file systems like
> LogFS has to be investigated further for this purpose too.
> 
> It seems the development of a real-time flash file system is still in
> the fledgling stages, hence I asked here for a flash simulator to make
> work easier.

I guess the first thing you need to do is define what real-time actually
means.  In particular you need to define the following:
o Maximal latency for single read.
o Maximal latency for single write.
o Maximal throughput for reads.
o Maximal throughput for writes.
o Read behaviour (random bytes from random files, sequential, etc.)
o Write behaviour (dito)
o Acceptable rate of higher latency reads/writes.

Once you have this, it is possible to determine whether some storage
stack (filesystem, middle layers, hardware) can fulfill your
requirements, or how it would need to be changed to do so.

Alternatively you can go the other way and take a given storage stack,
trying to determine the characteristics of it.

Jörn

-- 
A quarrel is quickly settled when deserted by one party; there is
no battle unless there be two.
-- Seneca

Re: Real-time flash simulator

[Artem Bityutskiy]

On Fri, 2007-06-22 at 12:24 +0200, Jörn Engel wrote:
> On Fri, 22 June 2007 12:11:29 +0200, Martin Däumler wrote:
> > 
> > that is right! The idea is to use a (not specified) file system which 
> > performs in-place updates on top of this layer. This layer should map
> > logical to physical erase units. So, wear-levelling possibly could be
> > used to "displace" garbage collection. The goal is to decrase latency
> > and above all make it more deterministic.
> 
> Sounds just like FAT on smartmedia.  Worst case latency is both
> deterministic and low.  Random writes of small blocks are also
> prohibitively slow.  Works great when writing few large files, like jpg
> images in digital cameras.

It is about EB mappings, not FTL.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Real-time flash simulator

[Jörn Engel]

On Fri, 22 June 2007 13:59:54 +0300, Artem Bityutskiy wrote:
> > 
> > Sounds just like FAT on smartmedia.  Worst case latency is both
> > deterministic and low.  Random writes of small blocks are also
> > prohibitively slow.  Works great when writing few large files, like jpg
> > images in digital cameras.
> 
> It is about EB mappings, not FTL.

EB mapping is all smartmedia does.

Jörn

-- 
Joern's library part 3:
http://inst.eecs.berkeley.edu/~cs152/fa05/handouts/clark-test.pdf

Re: Real-time flash simulator

[Martin Däumler]

Hello Jörn,

On Fri, 22 June 2007 12:24 +0200, Jörn Engel wrote:
> 
> I guess the first thing you need to do is define what real-time actually
> means.  In particular you need to define the following:
> 
> [...]
> 
> Once you have this, it is possible to determine whether some storage
> stack (filesystem, middle layers, hardware) can fulfill your
> requirements, or how it would need to be changed to do so.
> 
> Alternatively you can go the other way and take a given storage stack,
> trying to determine the characteristics of it.

that is what I do at the moment. The resulting flash file system should
have low-fluctuating latencies. Of course, the overall performance
should not be that bad (it has to be scaleable as well). But it seems I
have to write a real-time capable flash simulator at first ;).

Thank you for your help!


Regards,

Martin

Re: Real-time flash simulator

[Jörn Engel]

On Fri, 22 June 2007 09:19:19 +0200, Martin Däumler wrote:
> 
> Furthermore, there are some efforts to develop a (scaleable) real-time
> capable flash file system?

LogFS certainly is real-time.  There is an upper bound to any requests
that can be calculated.  Whether you are happy with it is a different
matter, as the bound is some tens of seconds.

And I claim that you fundamentally cannot have a better upper bound.
All you can do is cheat by reserving a pool of pre-erased blocks.  As
long as the pool lasts, you can guarantee relatively low response times.
But you cannot guarantee the pool to last forever under write pressure.

Jörn

-- 
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;
-- /usr/src/linux/init/main.c