not enough blocks for JFFS?

not enough blocks for JFFS?

[Tim Wu]

Hi! Everybody:

The system I'm working on use a 4MB NOR flash.
The block size of the 4MB flash is 64KB.
It also has eight smaller(8KB) blocks at bottom.
Since, on this system, I don't have much data to write(less than 10KB),
a CRAMFS(readonly)+JFFS(writable) combination should be pretty good for me.

Here comes the problem.  The bootloader has occupied the first three 8KB 
blocks.  I have only five 8K blocks available for JFFS.  It always fails 
when I overwrite an existed file on the JFFS partition.

I've checked the mailing list archive.  It seems JFFS/JFFS2 needs at 
least five blocks to work and the number '5' is adjustable.  Could 
somebody tell me where I can modify in JFFS source to have it run on 
fewer blocks?

Thanks.

not enough blocks for JFFS?

[Russ Dill]

On Sun, 2003-03-23 at 19:31, Tim Wu wrote:
> Hi! Everybody:
> 
> The system I'm working on use a 4MB NOR flash.
> The block size of the 4MB flash is 64KB.
> It also has eight smaller(8KB) blocks at bottom.
> Since, on this system, I don't have much data to write(less than 10KB),
> a CRAMFS(readonly)+JFFS(writable) combination should be pretty good for me.
> 
> Here comes the problem.  The bootloader has occupied the first three 8KB 
> blocks.  I have only five 8K blocks available for JFFS.  It always fails 
> when I overwrite an existed file on the JFFS partition.

Just make a quick user space implementation. Create a header struct
including revision, header crc, data crc, magic, and length. Write these
onto a block until its full, then erase a second block, write to that
block till thats full, then back to the first, etc... When you look for
data, you:

	a) find the first magic number
	b) check the header crc, if it doesn't match, go to a
	c) check the data crc, if it matches, record this revision as 
		the most recent revision (if it is)
	d) jump forward size + header size bytes

not enough blocks for JFFS?

[Jörn Engel]

On Mon, 24 March 2003 15:17:31 -0700, Russ Dill wrote:
> On Sun, 2003-03-23 at 19:31, Tim Wu wrote:
> > Hi! Everybody:
> > 
> > The system I'm working on use a 4MB NOR flash.
> > The block size of the 4MB flash is 64KB.
> > It also has eight smaller(8KB) blocks at bottom.
> > Since, on this system, I don't have much data to write(less than 10KB),
> > a CRAMFS(readonly)+JFFS(writable) combination should be pretty good for me.
> > 
> > Here comes the problem.  The bootloader has occupied the first three 8KB 
> > blocks.  I have only five 8K blocks available for JFFS.  It always fails 
> > when I overwrite an existed file on the JFFS partition.
> 
> Just make a quick user space implementation.

But a filesystem is nicer than a quick user space implementation. :)

Today I have tweaked jffs2 a little to work without compression,
depending on mount options. (patch will follow)

The nice effect of this is that you should be able to work with less
reserved blocks. My estimate is somewhere between one and three. In
Tims case, that would leave him with 16kB net space, enough for his
data. Cool.

Changing the amount of reserved blocks per filesystem (not per kernel)
is a bit tricky. And figuring out, how many are really needed requires
quite a bit of testing or some math. Without compression, math might
even be doable. :)

Tim, would you volunteer to test patches?

J?rn

-- 
The cost of changing business rules is much more expensive for software
than for a secretaty.
-- unknown

not enough blocks for JFFS?

[Tim Wu]

J?rn:
Thanks for your quick patch.  I will test it.

JFFS2 without compression?
What does it different from JFFS?

No compression is OK for me.  That's why I chose JFFS instead of JFFS2.
Can the idea "with less reserved blocks" apply to JFFS?
I prefer JFFS because JFFS2 is much larger than JFFS in code size, which 
makes
I have to enlarge my flash partition for kernel.


J?rn Engel:

>But a filesystem is nicer than a quick user space implementation. :)
>
>Today I have tweaked jffs2 a little to work without compression,
>depending on mount options. (patch will follow)
>
>The nice effect of this is that you should be able to work with less
>reserved blocks. My estimate is somewhere between one and three. In
>Tims case, that would leave him with 16kB net space, enough for his
>data. Cool.
>
>Changing the amount of reserved blocks per filesystem (not per kernel)
>is a bit tricky. And figuring out, how many are really needed requires
>quite a bit of testing or some math. Without compression, math might
>even be doable. :)
>
>Tim, would you volunteer to test patches?
>
>J?rn
>
>  
>

not enough blocks for JFFS?

[Russ Dill]

On Mon, 2003-03-24 at 19:13, Tim Wu wrote:
> J?rn:
> Thanks for your quick patch.  I will test it.
> 
> JFFS2 without compression?
> What does it different from JFFS?
> 
> No compression is OK for me.  That's why I chose JFFS instead of JFFS2.
> Can the idea "with less reserved blocks" apply to JFFS?
> I prefer JFFS because JFFS2 is much larger than JFFS in code size, which 
> makes
> I have to enlarge my flash partition for kernel.

Your goals would be better served by a user-space solution from what I
can tell. Not only would there be less code, but that code would be
compressed in cramfs. I'm able to use 1 boot block for blob, another for
static configuration, and the remaining two for configuration data saved
in this way.

not enough blocks for JFFS?

[Tim Wu]

So, by this approach, all the data-save write operations must be done 
through this
user-space lib instead of standard UNIX file I/O, right?


Russ Dill :

>Your goals would be better served by a user-space solution from what I
>can tell. Not only would there be less code, but that code would be
>compressed in cramfs. I'm able to use 1 boot block for blob, another for
>static configuration, and the remaining two for configuration data saved
>in this way.
>
>  
>

not enough blocks for JFFS?

[Jörn Engel]

On Mon, 24 March 2003 19:21:47 -0700, Russ Dill wrote:
> 
> Your goals would be better served by a user-space solution from what I
> can tell. Not only would there be less code, but that code would be
> compressed in cramfs. I'm able to use 1 boot block for blob, another for
> static configuration, and the remaining two for configuration data saved
> in this way.

Compressed in cramfs is the point where I really disagree. iirc,
cramfs images are a bit larger than jffs2 images. So if you want a
read-only rootfs, jffs2 might be a better idea, already.

Especially, if you need some if the jffs2 functionality again to save
configuration data. I doubt that you would save a lot with userspace
code + cramfs versus jffs2 both in flash and in memory consumption.

Time might be spend better in improving jffs2, than in reimplementing
a subset of jffs2's functionality each time.

J?rn

-- 
Invincibility is in oneself, vulnerability is in the opponent.
-- Sun Tzu

not enough blocks for JFFS?

[David Woodhouse]

On Tue, 2003-03-25 at 00:05, J??rn Engel wrote:
> But a filesystem is nicer than a quick user space implementation. :)
> 
> Today I have tweaked jffs2 a little to work without compression,
> depending on mount options. (patch will follow)

Hmmm. Why mount options and not take the path which was already sort-of
planned, which was to implement ioctl() and have a per-inode (and
inheritable for directories) set of flags, a la chattr?

> The nice effect of this is that you should be able to work with less
> reserved blocks. My estimate is somewhere between one and three. In
> Tims case, that would leave him with 16kB net space, enough for his
> data. Cool.

I'm not really convinced that the _compression_ makes much difference
here. You still get pages taking up more space when you GC them from a
single node to a pair of nodes because your new node would have crossed
an eraseblock boundary. OK, so the loss of compression efficiency makes
the resulting data payloads slightly larger _too_ but not by much, and
if you want formal proof of correctness you have to have accounted for
the expansion _anyway_.

Turning off compression because you don't have a lot of flash space
available seems rather bizarre to me :)

> Tim, would you volunteer to test patches?

TBH I'm not sure I want stuff that's just tested, I really want stuff
that is shown _mathematically_ to be correct in theory, although I do
tend to prefer if if that's backed up in practice of course :)

First I want to start using the REF_PRISTINE bits we already have to
write clean nodes to _different_ blocks, so we don't keep mixing old
data with new and we get to improve GC efficiency. Then I want to look
at eliminating all cases where the size of the data on the medium could
expand, except for the one where we have to split a GC'd node into two.
Then the amount of space we require for GC is basically calculable and
not too large.

-- 
dwmw2

not enough blocks for JFFS?

[Jörn Engel]

On Tue, 25 March 2003 12:51:06 +0000, David Woodhouse wrote:
> On Tue, 2003-03-25 at 00:05, J?rn Engel wrote:
> > But a filesystem is nicer than a quick user space implementation. :)
> > 
> > Today I have tweaked jffs2 a little to work without compression,
> > depending on mount options. (patch will follow)
> 
> Hmmm. Why mount options and not take the path which was already sort-of
> planned, which was to implement ioctl() and have a per-inode (and
> inheritable for directories) set of flags, a la chattr?

Because it is simple and does exactly what I need. And because I
didn't know about the sort-of-planned stuff.

My application is a ramdisk, where write speed is important. jffs2 is
compressing, so ext2 beats the crap out of it. But without
compression, I can get rid of ext2 (smaller kernel) and have journaling
(yes, that does make sense for a ramdisk).

Compression has to be turned on/off per mounted filesystem, so a mount
option is sufficient. It was also quite straight-forward to implement,
so even I could do it. :)

To the sort-of-planned stuff:
Can you give a short example, where this would be useful and how it
would be used, when implemented? This is quite new to me and I don't
know what to think about it yet.

Also, what is the state of it. How much work do you expect to get it
into place and how much would it cost? Just an extra bit per inode in
an already existing field and one if per read/write?

> > The nice effect of this is that you should be able to work with less
> > reserved blocks. My estimate is somewhere between one and three. In
> > Tims case, that would leave him with 16kB net space, enough for his
> > data. Cool.
> 
> I'm not really convinced that the _compression_ makes much difference
> here. You still get pages taking up more space when you GC them from a
> single node to a pair of nodes because your new node would have crossed
> an eraseblock boundary. OK, so the loss of compression efficiency makes
> the resulting data payloads slightly larger _too_ but not by much, and
> if you want formal proof of correctness you have to have accounted for
> the expansion _anyway_.

ack. Compression does make a formal proof more complicated, though.
Maybe we should do it w/out compression first and then see, how much
more complicated it would be w/ compression.

> Turning off compression because you don't have a lot of flash space
> available seems rather bizarre to me :)

Flash has bizarre problems, so bizarre solutions are just natural. :)

Tims problem is not flash space, it is the number of erase blocks. If
he could double their number and half their size, the solution would
be obvious. But if turning of compression frees one or two erase
blocks, that should do as well. If.

> > Tim, would you volunteer to test patches?
> 
> TBH I'm not sure I want stuff that's just tested, I really want stuff
> that is shown _mathematically_ to be correct in theory, although I do
> tend to prefer if if that's backed up in practice of course :)

Currently, all you have is a conservative default and a lack of known
problems with it. That is pretty far from what you want, isn't it?

> First I want to start using the REF_PRISTINE bits we already have to
> write clean nodes to _different_ blocks, so we don't keep mixing old
> data with new and we get to improve GC efficiency. Then I want to look
> at eliminating all cases where the size of the data on the medium could
> expand, except for the one where we have to split a GC'd node into two.
> Then the amount of space we require for GC is basically calculable and
> not too large.

Maybe I can help you with this. Do you have any documentation on known
problems? Doesn't have to be pretty, just enough for me to understand
it. Old emails might be fine as well.

J?rn

PS: Damn! I really didn't want to get back into this. Sometimes you
just can't help it, I guess.

not enough blocks for JFFS?

[David Woodhouse]

On Tue, 2003-03-25 at 13:33, J??rn Engel wrote:
> Because it is simple and does exactly what I need. And because I
> didn't know about the sort-of-planned stuff.

Fair enough :)

> My application is a ramdisk, where write speed is important. jffs2 is
> compressing, so ext2 beats the crap out of it. But without
> compression, I can get rid of ext2 (smaller kernel) and have journaling
> (yes, that does make sense for a ramdisk).

Why so? Wouldn't ramfs be better? Or is this a persistent ramdisk as
used on the iPAQ which isn't cleared between reboots?

> Compression has to be turned on/off per mounted filesystem, so a mount
> option is sufficient. It was also quite straight-forward to implement,
> so even I could do it. :)
> 
> To the sort-of-planned stuff:
> Can you give a short example, where this would be useful and how it
> would be used, when implemented? This is quite new to me and I don't
> know what to think about it yet.

> Also, what is the state of it. How much work do you expect to get it
> into place and how much would it cost? Just an extra bit per inode in
> an already existing field and one if per read/write?

See the 'flags' and 'usercompr' fields which have been in the
jffs2_raw_inode structure from the start. The latter was intended to
hold a compression type suggested by the user as the best compression
type for this inode, where that can be JFFS2_COMPR_NONE. It's relatively
easy to make the jffs2_compress() function obey it, to make sure it gets
stored and hence correctly preserved when new nodes are written out, and
to add an ioctl to read/set it for any given inode. Oh, and to make sure
it's inherited from the parent directory when an inode is created.

> ack. Compression does make a formal proof more complicated, though.
> Maybe we should do it w/out compression first and then see, how much
> more complicated it would be w/ compression.

I'll accept formal proof without compression, and a bit of handwaving
which says we're compensating for compression OK -- since the additional
GC overhead of compression is probably minimal.

> > Turning off compression because you don't have a lot of flash space
> > available seems rather bizarre to me :)
> 
> Flash has bizarre problems, so bizarre solutions are just natural. :)

True :)

> Tims problem is not flash space, it is the number of erase blocks. If
> he could double their number and half their size, the solution would
> be obvious. But if turning of compression frees one or two erase
> blocks, that should do as well. If.

I agree -- if indeed it does work. I don't think it _will_ work like
that,, but I'm prepared to be contradicted by the real world; it happens
0often enough that I'm no longer inclined to get upset when it happens
:)

> > TBH I'm not sure I want stuff that's just tested, I really want stuff
> > that is shown _mathematically_ to be correct in theory, although I do
> > tend to prefer if if that's backed up in practice of course :)
> 
> Currently, all you have is a conservative default and a lack of known
> problems with it. That is pretty far from what you want, isn't it?

Well, I'm not _entirely_ unhappy with the 'lack of known problems' bit,
but yes, I'd much rather be able to point at the calculations and know
that it _shouldn't_ fall over by filling itself up.

> Maybe I can help you with this. Do you have any documentation on known
> problems? Doesn't have to be pretty, just enough for me to understand
> it. Old emails might be fine as well.

Back to basics... the garbage collector works by writing out new nodes
to replace (and hence obsolete) the old ones that it's trying to get rid
of.

The problem occurs when the node(s) it needs to write out in replacement
take up _more_ space than the original node which is being obsoleted.

That can happen when the new node is being written to the end of an
erase block, so what was a single node before is now two separate nodes,
with an extra 70-odd bytes of node header (and less efficient
compression).

It can also happen when the old node was a _hole_ node (i.e. no data
payload and JFFS2_COMPR_ZERO), which is allowed to cross page boundaries
-- and since it was written, some _real_ data were written 'inside' the
range it covers. The normal way to obsolete it would be to write _two_
(or more) hole nodes covering the ranges which are still 'empty'. In
fact I think we already have code to combat this -- we write out the
original hole node with the _old_ version number so it stays 'behind'
the new data, and all is well.

There may be others, but the third and worst one I can think of right
now is that if you lose power _during_ a GC write, you end up with an
incomplete node on the flash and you've basically lost that space. On
some flash chips you can _try_ to be clever and actually make use of
partially-written nodes -- if there's just a node header you can write
out almost any other node to go with it, if there's an inode number and
offset you can recreate what you're writing etc.... but that's hard. 

Basically, the main task is to calculate the amount of space that is
required to allow for expansion by splitting nodes -- probably just 70
bytes for each eraseblock in the file system -- and double-check that
there are no other cases which can lead to expansion. 

Then build in some slack to deal with stuff like the third possibility I
mentioned above, and blocks actually going bad on us. 


> PS: Damn! I really didn't want to get back into this. Sometimes you
> just can't help it, I guess.

I know the feeling. When I first arrived at Red Hat almost three years
ago and my first task was to beat JFFS into shape for shipping to a
customer, I insisted that I knew _nothing_ about file systems... :)

-- 
dwmw2

not enough blocks for JFFS?

[Russ Dill]

On Tue, 2003-03-25 at 05:33, J?rn Engel wrote:
> On Mon, 24 March 2003 19:21:47 -0700, Russ Dill wrote:
> > 
> > Your goals would be better served by a user-space solution from what I
> > can tell. Not only would there be less code, but that code would be
> > compressed in cramfs. I'm able to use 1 boot block for blob, another for
> > static configuration, and the remaining two for configuration data saved
> > in this way.
> 
> Compressed in cramfs is the point where I really disagree. iirc,
> cramfs images are a bit larger than jffs2 images. So if you want a
> read-only rootfs, jffs2 might be a better idea, already.

not a chance....

russ:~/src/build$ du -sh out_dir-arm/
2.3M    out_dir-arm/
russ:~/src/build$ ls -l image.*
-rw-r--r--    1 russ     russ      1286144 Mar 25 12:03 image.cramfs
-rw-r--r--    1 russ     russ      1364676 Mar 25 12:02 image.jffs2

> Especially, if you need some if the jffs2 functionality again to save
> configuration data. I doubt that you would save a lot with userspace
> code + cramfs versus jffs2 both in flash and in memory consumption.

cramfs.o is 7662 bytes, jffs2.o is 74046 bytes. cramfs requires almost
no kernel allocated memory to run, jffs2 creates large data structures
to keep track of nodes. A simple userspace implementation to read and
write nodes to flash that include crc's and revisions in 4296 bytes
(object file before linking)

> Time might be spend better in improving jffs2, than in reimplementing
> a subset of jffs2's functionality each time.

A userspace library would be nice

not enough blocks for JFFS?

[Jörn Engel]

On Tue, 25 March 2003 12:06:05 -0700, Russ Dill wrote:
> On Tue, 2003-03-25 at 05:33, J?rn Engel wrote:
> > 
> > Compressed in cramfs is the point where I really disagree. iirc,
> > cramfs images are a bit larger than jffs2 images. So if you want a
> > read-only rootfs, jffs2 might be a better idea, already.
> 
> not a chance....
> 
> russ:~/src/build$ du -sh out_dir-arm/
> 2.3M    out_dir-arm/
> russ:~/src/build$ ls -l image.*
> -rw-r--r--    1 russ     russ      1286144 Mar 25 12:03 image.cramfs
> -rw-r--r--    1 russ     russ      1364676 Mar 25 12:02 image.jffs2

Correct, my tests disagree with my memory as well. 

> > Especially, if you need some if the jffs2 functionality again to save
> > configuration data. I doubt that you would save a lot with userspace
> > code + cramfs versus jffs2 both in flash and in memory consumption.
> 
> cramfs.o is 7662 bytes, jffs2.o is 74046 bytes. cramfs requires almost
> no kernel allocated memory to run, jffs2 creates large data structures
> to keep track of nodes. A simple userspace implementation to read and
> write nodes to flash that include crc's and revisions in 4296 bytes
> (object file before linking)

Also correct. Over here, jffs2 accounts for 45k of zipped kernel
image, cramfs for 15k. Both numbers include zlib (not shared).

> > Time might be spend better in improving jffs2, than in reimplementing
> > a subset of jffs2's functionality each time.
> 
> A userspace library would be nice

Agreed.

Your suggestion still doesn't apply to my problems, but it would make
more sense for Tim.

J?rn

-- 
Good warriors cause others to come to them and do not go to others.
-- Sun Tzu

not enough blocks for JFFS?

[Jörn Engel]

On Tue, 25 March 2003 14:36:39 +0000, David Woodhouse wrote:
> 
> > My application is a ramdisk, where write speed is important. jffs2 is
> > compressing, so ext2 beats the crap out of it. But without
> > compression, I can get rid of ext2 (smaller kernel) and have journaling
> > (yes, that does make sense for a ramdisk).
> 
> Why so? Wouldn't ramfs be better? Or is this a persistent ramdisk as
> used on the iPAQ which isn't cleared between reboots?

Yes, the ramdisk is persistent between reboots.

Maybe some people dig out the requirement that we need dynamic
growing/shrinking as well, but that is quite simple to add to jffs2.
Should make less of an impact than linking yet another fs.

> See the 'flags' and 'usercompr' fields which have been in the
> jffs2_raw_inode structure from the start. The latter was intended to
> hold a compression type suggested by the user as the best compression
> type for this inode, where that can be JFFS2_COMPR_NONE. It's relatively
> easy to make the jffs2_compress() function obey it, to make sure it gets
> stored and hence correctly preserved when new nodes are written out, and
> to add an ioctl to read/set it for any given inode. Oh, and to make sure
> it's inherited from the parent directory when an inode is created.

Sounds quite sane.

But we would need a new userspace tool to "chattr compr=none foo",
wouldn't we?

> I'll accept formal proof without compression, and a bit of handwaving
> which says we're compensating for compression OK -- since the additional
> GC overhead of compression is probably minimal.

Still hard enough. Maybe I can come up with something...

> > Tims problem is not flash space, it is the number of erase blocks. If
> > he could double their number and half their size, the solution would
> > be obvious. But if turning of compression frees one or two erase
> > blocks, that should do as well. If.
> 
> I agree -- if indeed it does work. I don't think it _will_ work like
> that,, but I'm prepared to be contradicted by the real world; it happens
> 0often enough that I'm no longer inclined to get upset when it happens
> :)

It is easier to prove me wrong, than right. I'll try to set up a
testbed and punish it for some time. Let's see where things break
w/out compression.

> Well, I'm not _entirely_ unhappy with the 'lack of known problems' bit,
> but yes, I'd much rather be able to point at the calculations and know
> that it _shouldn't_ fall over by filling itself up.

Right. Our calculations will have one "magic" problem, if we ever get
there. We'll have to say, some like:
"There are exectly 15 different cases for the garbage collector. Now
we are going to formally prove each case to be harmless."

What if there are in fact 16 cases? Or, what if another case gets
introduced by code change, some time later?

> > Maybe I can help you with this. Do you have any documentation on known
> > problems? Doesn't have to be pretty, just enough for me to understand
> > it. Old emails might be fine as well.
> 
> Back to basics... the garbage collector works by writing out new nodes
> to replace (and hence obsolete) the old ones that it's trying to get rid
> of.
> 
> [...]

Thank you! I'll have a close look into this later. My brain returns
-EBUSY on a regular basis, since I got back to jffs2 - on top of my
other stuff. :)

> I know the feeling. When I first arrived at Red Hat almost three years
> ago and my first task was to beat JFFS into shape for shipping to a
> customer, I insisted that I knew _nothing_ about file systems... :)

Well, for being a bloody amateur, you are doing quite well. ;)

J?rn

-- 
Fancy algorithms are buggier than simple ones, and they're much harder
to implement. Use simple algorithms as well as simple data structures.
-- Rob Pike

not enough blocks for JFFS?

[Jörn Engel]

On Tue, 25 March 2003 14:36:39 +0000, David Woodhouse wrote:
> 
> Back to basics... the garbage collector works by writing out new nodes
> to replace (and hence obsolete) the old ones that it's trying to get rid
> of.
> 
> The problem occurs when the node(s) it needs to write out in replacement
> take up _more_ space than the original node which is being obsoleted.
> 
> That can happen when the new node is being written to the end of an
> erase block, so what was a single node before is now two separate nodes,
> with an extra 70-odd bytes of node header (and less efficient
> compression).

In the worst case, this would mean one additional node header per
erase block. We need more slack space the more and the smaller the
erase blocks are.

Can the following scenario happen?
Node foo gets split up in foo1 and foo2, living in the first and last
bytes of two erase blocks. In the next GC round, foo1 gets split up
again, in foo11 and foo12, so the original node has three fragments
now.

> It can also happen when the old node was a _hole_ node (i.e. no data
> payload and JFFS2_COMPR_ZERO), which is allowed to cross page boundaries
> -- and since it was written, some _real_ data were written 'inside' the
> range it covers. The normal way to obsolete it would be to write _two_
> (or more) hole nodes covering the ranges which are still 'empty'. In
> fact I think we already have code to combat this -- we write out the
> original hole node with the _old_ version number so it stays 'behind'
> the new data, and all is well.

We should double check this. If so, that case should be harmless now.

> There may be others, but the third and worst one I can think of right
> now is that if you lose power _during_ a GC write, you end up with an
> incomplete node on the flash and you've basically lost that space. On
> some flash chips you can _try_ to be clever and actually make use of
> partially-written nodes -- if there's just a node header you can write
> out almost any other node to go with it, if there's an inode number and
> offset you can recreate what you're writing etc.... but that's hard. 

I don't really like clever tricks. :)

It should be more robust to remember the erase block that contains
such a node and GC it next. Finish the last block that was scheduled
for GC, delete it, GC this borked block and then continue with normal
operations.

If power fails again (and again and again...) this block will be worn
off faster than others. But if we ever get out of this nightmare, it
will be another blocks turn, so this doesn't matter. And if we never
get out of this nightmare, it doesn't matter anyway.

The problem of this case is that you cannot calculate it at all. If
you start to write a node and power fail, before it's completely
written, in a loop, no amount of extra block will help you.

But if the power fails are rare enough, so you can usually reclaim the
last block, where GC was in progress and this one, which is wasting
space, one erase block for slack should be enough.

> Basically, the main task is to calculate the amount of space that is
> required to allow for expansion by splitting nodes -- probably just 70
> bytes for each eraseblock in the file system -- and double-check that
> there are no other cases which can lead to expansion. 

70+x Bytes per block for case 1.
0 for case 2.
1 Block for case 3

> Then build in some slack to deal with stuff like the third possibility I
> mentioned above, and blocks actually going bad on us. 

For NOR, you don't have to worry about blocks going bad too much. If
it happens to hit one of the bootloader or kernel blocks, you're dead
anyway.

For NAND, yes, we should use some extra.

For RAM, we don't need anything extra either.

-----
Bottom line:
It might be a good idea to get rid of the macros and add those values
to the struct superblock instead. Then we can calculate their values
on mount. Everything else can follow.

J?rn

-- 
This above all: to thine own self be true.
-- Shakespeare

not enough blocks for JFFS?

[Jörn Engel]

On Sun, 30 March 2003 21:01:20 +0200, J?rn Engel wrote:
> 
> It might be a good idea to get rid of the macros and add those values
> to the struct superblock instead. Then we can calculate their values
> on mount. Everything else can follow.

And in the next patch, I'd like to add one to all the numbers we
calculated and print out a big fat warning, if we ever needed this
safety block. :)

J?rn

-- 
Simplicity is prerequisite for reliability.
-- Edsger W. Dijkstra

not enough blocks for JFFS?

[David Woodhouse]

On Sun, 2003-03-30 at 20:01, J?rn Engel wrote:
> In the worst case, this would mean one additional node header per
> erase block. We need more slack space the more and the smaller the
> erase blocks are.

Yep. Hence my wanting to limit the _minimum_ size of erase blocks, when
we started working on NAND flash. But I couldn't justify myself without
handwaving so Thomas changed that back.

> Can the following scenario happen?
> Node foo gets split up in foo1 and foo2, living in the first and last
> bytes of two erase blocks. In the next GC round, foo1 gets split up
> again, in foo11 and foo12, so the original node has three fragments
> now.

It shouldn't. We try to combine pages whenever we can, so that split
nodes, whether they be split through GC or just because the user wrote
them out like that, get merged. 

Unfortunately we have logic to avoid doing this when we need it most --
when we're right out of space and doing so would prevent us from making
it to the end of the block. :)

Arguably if we get into that situation we're already buggered though.

> We should double check this. If so, that case should be harmless now.

Should be. I want to double-check its behaviour on NAND flash where we
can't mark the old one obsolete, and hence on remount we end up with two
identical copies of the same node. That's OK because we delete one --
but I'm not convinced we delete the _right_ one, and I'm not entirely
sure what brokenness that causes, if any.

> > There may be others, but the third and worst one I can think of right
> > now is that if you lose power _during_ a GC write, you end up with an
> > incomplete node on the flash and you've basically lost that space. On
> > some flash chips you can _try_ to be clever and actually make use of
> > partially-written nodes -- if there's just a node header you can write
> > out almost any other node to go with it, if there's an inode number and
> > offset you can recreate what you're writing etc.... but that's hard. 
> 
> I don't really like clever tricks. :)

Agreed.

> It should be more robust to remember the erase block that contains
> such a node and GC it next. Finish the last block that was scheduled
> for GC, delete it, GC this borked block and then continue with normal
> operations.

Nah, there's no point in that AFAICT. If you're going to let it remain
borked, then it's just dirty space like any other, and you don't have to
treat it at all specially. If you're short of space, you still want to
GC the block with most dirty space, and it doesn't matter why it's dirty
-- whether it's nodes which were valid and now are not, or nodes you
never finished writing before you got interrupted.

> The problem of this case is that you cannot calculate it at all. If
> you start to write a node and power fail, before it's completely
> written, in a loop, no amount of extra block will help you.

Indeed. Hence the evil trick I suggested to try to avoid it. 

> But if the power fails are rare enough, so you can usually reclaim the
> last block, where GC was in progress and this one, which is wasting
> space, one erase block for slack should be enough.

Yeah, that's probably an accurate assessment.

> > Basically, the main task is to calculate the amount of space that is
> > required to allow for expansion by splitting nodes -- probably just 70
> > bytes for each eraseblock in the file system -- and double-check that
> > there are no other cases which can lead to expansion. 
> 
> 70+x Bytes per block for case 1.
> 0 for case 2.
> 1 Block for case 3
> 
> > Then build in some slack to deal with stuff like the third possibility I
> > mentioned above, and blocks actually going bad on us. 
> 
> For NOR, you don't have to worry about blocks going bad too much. If
> it happens to hit one of the bootloader or kernel blocks, you're dead
> anyway.

The bootloader very rarely gets written so isn't likely to go bad, and
bootloaders like RedBoot and the Compaq bootldr can read kernels out of
JFFS2 now so that one isn't an issue now either. But yeah -- we don't
need to worry _too_ much. 

> For NAND, yes, we should use some extra.
> 
> For RAM, we don't need anything extra either.
> 
> -----
> Bottom line:
> It might be a good idea to get rid of the macros and add those values
> to the struct superblock instead. Then we can calculate their values
> on mount. Everything else can follow.

Makes sense, and perhaps we can make them user-tunable somehow too, or
mount options. I'm wondering if we want to continue having them in units
of blocks, or whether we want to count bytes.


-- 
dwmw2

not enough blocks for JFFS?

[Jörn Engel]

On Sun, 30 March 2003 20:23:47 +0100, David Woodhouse wrote:
> On Sun, 2003-03-30 at 20:01, J?rn Engel wrote:
> > In the worst case, this would mean one additional node header per
> > erase block. We need more slack space the more and the smaller the
> > erase blocks are.
> 
> Yep. Hence my wanting to limit the _minimum_ size of erase blocks, when
> we started working on NAND flash. But I couldn't justify myself without
> handwaving so Thomas changed that back.

This case is interesting anyway. 70 Bytes per node and 512 Bytes per
erase block are 14% in my book. That is quite nasty, but it also is
worst case. You can calculate the propability of that with many
blocks. :)

Now, what propability are you going to accept? Or how can you make
sure that those 14% are never reached. A tough one.

> > Can the following scenario happen?
> > Node foo gets split up in foo1 and foo2, living in the first and last
> > bytes of two erase blocks. In the next GC round, foo1 gets split up
> > again, in foo11 and foo12, so the original node has three fragments
> > now.
> 
> It shouldn't. We try to combine pages whenever we can, so that split
> nodes, whether they be split through GC or just because the user wrote
> them out like that, get merged. 
> 
> Unfortunately we have logic to avoid doing this when we need it most --
> when we're right out of space and doing so would prevent us from making
> it to the end of the block. :)
> 
> Arguably if we get into that situation we're already buggered though.

Yes, I agree. If things get too low, we just have to accept the fs to
be read-only now and figure out, what got us into that situation in
the first place. I'm even somewhat inclined to rip such code out.

But first I have to identify it and make sure that we never hit it in
operation.

> > We should double check this. If so, that case should be harmless now.
> 
> Should be. I want to double-check its behaviour on NAND flash where we
> can't mark the old one obsolete, and hence on remount we end up with two
> identical copies of the same node. That's OK because we delete one --
> but I'm not convinced we delete the _right_ one, and I'm not entirely
> sure what brokenness that causes, if any.

Ack. That is a different problem, so I ignore it for now.

> > I don't really like clever tricks. :)
> 
> Agreed.
> 
> > It should be more robust to remember the erase block that contains
> > such a node and GC it next. Finish the last block that was scheduled
> > for GC, delete it, GC this borked block and then continue with normal
> > operations.
> 
> Nah, there's no point in that AFAICT. If you're going to let it remain
> borked, then it's just dirty space like any other, and you don't have to
> treat it at all specially. If you're short of space, you still want to
> GC the block with most dirty space, and it doesn't matter why it's dirty
> -- whether it's nodes which were valid and now are not, or nodes you
> never finished writing before you got interrupted.

I have to think about this some more. If the behaviour is not worse in
any case, I agree with you. Shouldn't be, but better give it some more
thought.

> > The problem of this case is that you cannot calculate it at all. If
> > you start to write a node and power fail, before it's completely
> > written, in a loop, no amount of extra block will help you.
> 
> Indeed. Hence the evil trick I suggested to try to avoid it. 

How long does it take for GC to write one erase block? How long does
it take to boot the machine far enough to start GC? If GC is not more
than 90% of the sum and we get trapped in such a loop, forever, things
are getting quite unlikely.

If this ever happens someone is trying to break jffs2 on purpose, just
to make it read-only. Do we need to worry about this? And if so, can
we prevent it under *any* circumstances? If not, let's ignore that
case.

> > For NOR, you don't have to worry about blocks going bad too much. If
> > it happens to hit one of the bootloader or kernel blocks, you're dead
> > anyway.
> 
> The bootloader very rarely gets written so isn't likely to go bad, and
> bootloaders like RedBoot and the Compaq bootldr can read kernels out of
> JFFS2 now so that one isn't an issue now either. But yeah -- we don't
> need to worry _too_ much. 

Manufacturers give us 100.000 erase cycles per block. I read that as
100.000 erase cycles before the first block fails. There is no number
saying 120.000 before the second or third block fails, so that number
should still be 100.000, if you want to be on the safe side.

I'd rather worry about the application that writes 100.000 times the
file system size to *flash*. :)

> > Bottom line:
> > It might be a good idea to get rid of the macros and add those values
> > to the struct superblock instead. Then we can calculate their values
> > on mount. Everything else can follow.
> 
> Makes sense, and perhaps we can make them user-tunable somehow too, or
> mount options. I'm wondering if we want to continue having them in units
> of blocks, or whether we want to count bytes.

Bytes make more sense to me.

I don't expect to work on it next week, but I can already give you my
mount option "parser", if you are interested.

J?rn

-- 
My second remark is that our intellectual powers are rather geared to
master static relations and that our powers to visualize processes
evolving in time are relatively poorly developed.
-- Edsger W. Dijkstra

Re: not enough blocks for JFFS?

[Jörn Engel]

On Sun, 30 March 2003 22:08:20 +0200, Jörn Engel wrote:
> 
> > > Bottom line:
> > > It might be a good idea to get rid of the macros and add those values
> > > to the struct superblock instead. Then we can calculate their values
> > > on mount. Everything else can follow.
> > 
> > Makes sense, and perhaps we can make them user-tunable somehow too, or
> > mount options. I'm wondering if we want to continue having them in units
> > of blocks, or whether we want to count bytes.
> 
> Bytes make more sense to me.
> 
> I don't expect to work on it next week, but I can already give you my
> mount option "parser", if you are interested.

That week is over, so let's get back. :)

First version of the patch. This moves the macros to superblocks
fields, initializes them on read_super and shouldn't change the
behaviour. Untested, though.

Jörn

-- 
A surrounded army must be given a way out.
-- Sun Tzu

diff -Naur linux-2.4.20-pre7/fs/jffs2/background.c linux-2.4.20-pre7-jffs2/fs/jffs2/background.c
--- linux-2.4.20-pre7/fs/jffs2/background.c	2001-10-25 09:07:09.000000000 +0200
+++ linux-2.4.20-pre7-jffs2/fs/jffs2/background.c	2003-04-07 13:58:51.000000000 +0200
@@ -175,7 +175,7 @@
 {
 	D1(printk(KERN_DEBUG "thread_should_wake(): nr_free_blocks %d, nr_erasing_blocks %d, dirty_size 0x%x\n", 
 		  c->nr_free_blocks, c->nr_erasing_blocks, c->dirty_size));
-	if (c->nr_free_blocks + c->nr_erasing_blocks < JFFS2_RESERVED_BLOCKS_GCTRIGGER &&
+	if (c->nr_free_blocks + c->nr_erasing_blocks < c->reserved_blocks_gctrigger &&
 	    c->dirty_size > c->sector_size)
 		return 1;
 	else 
diff -Naur linux-2.4.20-pre7/fs/jffs2/gc.c linux-2.4.20-pre7-jffs2/fs/jffs2/gc.c
--- linux-2.4.20-pre7/fs/jffs2/gc.c	2002-11-29 00:53:15.000000000 +0100
+++ linux-2.4.20-pre7-jffs2/fs/jffs2/gc.c	2003-04-07 13:51:00.000000000 +0200
@@ -66,7 +66,7 @@
 
 	/* Pick an eraseblock to garbage collect next. This is where we'll
 	   put the clever wear-levelling algorithms. Eventually.  */
-	if (!list_empty(&c->bad_used_list) && c->nr_free_blocks > JFFS2_RESERVED_BLOCKS_GCBAD) {
+	if (!list_empty(&c->bad_used_list) && c->nr_free_blocks > c->reserved_blocks_gcbad) {
 		D1(printk(KERN_DEBUG "Picking block from bad_used_list to GC next\n"));
 		nextlist = &c->bad_used_list;
 	} else if (jiffies % 100 && !list_empty(&c->dirty_list)) {
@@ -572,7 +572,7 @@
 	   the GC would churn and churn, and just leave dirty blocks in
 	   it's wake.
 	*/
-	if(c->nr_free_blocks + c->nr_erasing_blocks > JFFS2_RESERVED_BLOCKS_GCMERGE - (fn->raw->next_phys?0:1)) {
+	if(c->nr_free_blocks + c->nr_erasing_blocks > c->reserved_blocks_gcmerge - (fn->raw->next_phys?0:1)) {
 		/* Shitloads of space */
 		/* FIXME: Integrate this properly with GC calculations */
 		start &= ~(PAGE_CACHE_SIZE-1);
diff -Naur linux-2.4.20-pre7/fs/jffs2/nodelist.h linux-2.4.20-pre7-jffs2/fs/jffs2/nodelist.h
--- linux-2.4.20-pre7/fs/jffs2/nodelist.h	2003-04-07 12:17:44.000000000 +0200
+++ linux-2.4.20-pre7-jffs2/fs/jffs2/nodelist.h	2003-04-07 13:42:06.000000000 +0200
@@ -222,13 +222,6 @@
 #define ALLOC_DELETION	1	/* Deletion node. Best to allow it */
 #define ALLOC_GC	2	/* Space requested for GC. Give it or die */
 
-#define JFFS2_RESERVED_BLOCKS_BASE 3						/* Number of free blocks there must be before we... */
-#define JFFS2_RESERVED_BLOCKS_WRITE (JFFS2_RESERVED_BLOCKS_BASE + 2)		/* ... allow a normal filesystem write */
-#define JFFS2_RESERVED_BLOCKS_DELETION (JFFS2_RESERVED_BLOCKS_BASE + 1)		/* ... allow a normal filesystem deletion */
-#define JFFS2_RESERVED_BLOCKS_GCTRIGGER (JFFS2_RESERVED_BLOCKS_BASE + 3)	/* ... wake up the GC thread */
-#define JFFS2_RESERVED_BLOCKS_GCBAD (JFFS2_RESERVED_BLOCKS_BASE + 1)		/* ... pick a block from the bad_list to GC */
-#define JFFS2_RESERVED_BLOCKS_GCMERGE (JFFS2_RESERVED_BLOCKS_BASE)		/* ... merge pages when garbage collecting */
-
 
 #define PAD(x) (((x)+3)&~3)
 
diff -Naur linux-2.4.20-pre7/fs/jffs2/nodemgmt.c linux-2.4.20-pre7-jffs2/fs/jffs2/nodemgmt.c
--- linux-2.4.20-pre7/fs/jffs2/nodemgmt.c	2002-08-03 02:39:45.000000000 +0200
+++ linux-2.4.20-pre7-jffs2/fs/jffs2/nodemgmt.c	2003-04-07 13:57:40.000000000 +0200
@@ -67,12 +67,12 @@
 int jffs2_reserve_space(struct jffs2_sb_info *c, __u32 minsize, __u32 *ofs, __u32 *len, int prio)
 {
 	int ret = -EAGAIN;
-	int blocksneeded = JFFS2_RESERVED_BLOCKS_WRITE;
+	int blocksneeded = c->reserved_blocks_write;
 	/* align it */
 	minsize = PAD(minsize);
 
 	if (prio == ALLOC_DELETION)
-		blocksneeded = JFFS2_RESERVED_BLOCKS_DELETION;
+		blocksneeded = c->reserved_blocks_deletion;
 
 	D1(printk(KERN_DEBUG "jffs2_reserve_space(): Requested 0x%x bytes\n", minsize));
 	down(&c->alloc_sem);
diff -Naur linux-2.4.20-pre7/fs/jffs2/super.c linux-2.4.20-pre7-jffs2/fs/jffs2/super.c
--- linux-2.4.20-pre7/fs/jffs2/super.c	2002-11-29 00:53:15.000000000 +0100
+++ linux-2.4.20-pre7-jffs2/fs/jffs2/super.c	2003-04-07 14:54:32.000000000 +0200
@@ -86,8 +86,8 @@
 	spin_lock_bh(&c->erase_completion_lock);
 
 	avail = c->dirty_size + c->free_size;
-	if (avail > c->sector_size * JFFS2_RESERVED_BLOCKS_WRITE)
-		avail -= c->sector_size * JFFS2_RESERVED_BLOCKS_WRITE;
+	if (avail > c->sector_size * c->reserved_blocks_write)
+		avail -= c->sector_size * c->reserved_blocks_write;
 	else
 		avail = 0;
 
@@ -196,6 +196,7 @@
 	struct jffs2_sb_info *c;
 	struct inode *root_i;
 	int i;
+	uint32_t reserved_blocks_base = 3;
 
 	D1(printk(KERN_DEBUG "jffs2: read_super for device %s\n", kdevname(sb->s_dev)));
 
@@ -245,6 +246,12 @@
 	INIT_LIST_HEAD(&c->bad_used_list);
 	c->highest_ino = 1;
 
+	c->reserved_blocks_write	= reserved_blocks_base + 2;
+	c->reserved_blocks_deletion	= reserved_blocks_base + 1;
+	c->reserved_blocks_gctrigger	= reserved_blocks_base + 3;
+	c->reserved_blocks_gcbad	= reserved_blocks_base + 1;
+	c->reserved_blocks_gcmerge	= reserved_blocks_base + 0;
+
 	if (jffs2_build_filesystem(c)) {
 		D1(printk(KERN_DEBUG "build_fs failed\n"));
 		goto out_nodes;
diff -Naur linux-2.4.20-pre7/include/linux/jffs2_fs_sb.h linux-2.4.20-pre7-jffs2/include/linux/jffs2_fs_sb.h
--- linux-2.4.20-pre7/include/linux/jffs2_fs_sb.h	2002-08-03 02:39:45.000000000 +0200
+++ linux-2.4.20-pre7-jffs2/include/linux/jffs2_fs_sb.h	2003-04-07 13:41:50.000000000 +0200
@@ -71,6 +71,12 @@
 	wait_queue_head_t erase_wait;		/* For waiting for erases to complete */
 	struct jffs2_inode_cache *inocache_list[INOCACHE_HASHSIZE];
 	spinlock_t inocache_lock;
+	/* Reserved blocks for various actions */
+	uint32_t reserved_blocks_write; 
+	uint32_t reserved_blocks_deletion; 
+	uint32_t reserved_blocks_gctrigger; 
+	uint32_t reserved_blocks_gcbad; 
+	uint32_t reserved_blocks_gcmerge; 
 };
 
 #ifdef JFFS2_OUT_OF_KERNEL