4k-aligned nodes

[Jörn Engel]

Guys,

while giving a presentation about mtd/jffs2, an interesting idea
popped up. Might be old. If it is, please tell me to shut up.


Problem:
GC runs into many interesting corner-cases when collecting nodes that
were partially obsoleted by smaller nodes, etc. Most notably is this
scenario:

Node 1: 1234567890abcdef1234567890abcdef
Node 2: 12
Node 3: 1234567890abcde
Node 4: 234567890abcdef

Node 1 is old and contains two copies of non-compressable data. With
zlib, the two copies are detected and the compressed data basically
has the size of one of the two copies.

Node 2 overwrites some bytes of node 1 right where both copies are
concatenated.

When GC has to copy parts of node 1, it may create two nodes 3 and 4,
that each contain one copy of non-compressable data. Each of them has
roughly the same size as node 1, so both of them have twice the size.
GC didn't shrink flash footprint, bad.


Solution:
GC always tries to write out 4k-aligned nodes with 4k of uncompressed
data.

This also causes GC to run into corner-cases and occasionally use more
flash footprint than original data. But in the long run, it should
cause data to be in the most efficient format on-flash.


Jörn

[David Woodhouse]

That's why we have an extra threshold, for the amount of free space
which is required for GC to merge nodes. See the logic in
jffs2_garbage_collect_dnode() which expands 'start' and 'end'.

220loc, looks a bit complicated. If only I had some time to work on
jffs2!

Heh. You and me both :)

[David Woodhouse]

Post by Jörn Engel
GC always tries to write out 4k-aligned nodes with 4k of uncompressed
data.

We've been doing that in JFFS2 since February 2001. :)

Post by Jörn Engel
This also causes GC to run into corner-cases and occasionally use more
flash footprint than original data. But in the long run, it should
cause data to be in the most efficient format on-flash.

That's why we have an extra threshold, for the amount of free space
which is required for GC to merge nodes. See the logic in
jffs2_garbage_collect_dnode() which expands 'start' and 'end'.

[Jörn Engel]

Post by David Woodhouse

Post by Jörn Engel
GC always tries to write out 4k-aligned nodes with 4k of uncompressed
data.

We've been doing that in JFFS2 since February 2001. :)

Ok. I'll remember that when giving the next presentation.

Post by David Woodhouse

Post by Jörn Engel
This also causes GC to run into corner-cases and occasionally use more
flash footprint than original data. But in the long run, it should
cause data to be in the most efficient format on-flash.

That's why we have an extra threshold, for the amount of free space
which is required for GC to merge nodes. See the logic in
jffs2_garbage_collect_dnode() which expands 'start' and 'end'.

220loc, looks a bit complicated. If only I had some time to work on
jffs2!

Jörn