Re: [ECOS] Stress testing JFFS2

Re: [ECOS] Stress testing JFFS2

[Thomas Koeller]

In an attempt to understand what's really going on inside JFFS2, I
spent a day analyzing the code. Here's what I found. Please everybody
comment on this and correct any errors on my side.

- Every operation that changes the contents of the FLASH (even deleting files!)
  is performed by writing new nodes to the FLASH. Every such node is represented
  in RAM by a struct jffs2_raw_node_ref. The memory occupied by these structs
  is never freed unless the file system is unmounted or garbage collection
  takes place. Garbage collection starts when there are only five empty
  erase blocks left. Since every data node on the flash can hold at most one
  page (4KB) worth of data (uncompressed), the number of in-core instances of
  struct jffs2_raw_node_ref can grow very large. So in order to support a larger
  JFFS2 file system, an appropriate amount of RAM is absolutely required.

- The size of a single struct jffs2_raw_node_ref is 16 bytes. In ecos, these
  structs are allocated through calls to malloc(). If the underlying implementation
  is dlmalloc, as is probably the case most often, the minimum allocation size is
  24 bytes, so some memory is wasted here. A fixed-size block allocator would be
  more appropriate.

- In http://lists.infradead.org/pipermail/linux-mtd/2003-August/008372.html,
  David Woodhouse comments on this, suggesting possible improvements. I do not
  know if any work is going on to implement one of these (probably not).

When I originally decided to design my system around JFFS2 I was totally unaware
of these topics. Although everything I found is implicit in David Woodhouse's
paper 'JFFS : The Journalling Flash File System', it is not stated explicitly
anywhere, so I'm doing it here and now: Do not use large JFFS2 file systems if
RAM is a scarce resource!

tk
--------------------------------------------------

Thomas Koeller, Software Development

Basler Vision Technologies
An der Strusbek 60-62
22926 Ahrensburg
Germany

Tel +49 (4102) 463-162
Fax +49 (4102) 463-239

mailto:thomas.koeller@baslerweb.com
http://www.baslerweb.com

==============================

Re: [ECOS] Stress testing JFFS2

[David Woodhouse]

On Wed, 2003-10-15 at 12:11 +0200, Thomas Koeller wrote:
> In an attempt to understand what's really going on inside JFFS2, I
> spent a day analyzing the code. Here's what I found. Please everybody
> comment on this and correct any errors on my side.
> 
> - Every operation that changes the contents of the FLASH (even deleting files!)
>   is performed by writing new nodes to the FLASH. Every such node is represented
>   in RAM by a struct jffs2_raw_node_ref. The memory occupied by these structs
>   is never freed unless the file system is unmounted or garbage collection
>   takes place. Garbage collection starts when there are only five empty
>   erase blocks left. Since every data node on the flash can hold at most one
>   page (4KB) worth of data (uncompressed), the number of in-core instances of
>   struct jffs2_raw_node_ref can grow very large. So in order to support a larger
>   JFFS2 file system, an appropriate amount of RAM is absolutely required.

All correct. But you miss the observation that we also keep a
raw_node_ref around for _obsolete_ nodes, which perhaps we could avoid.
In fact, we do this because the raw_node_ref is in a singly-linked list,
and it's going to be very inefficient to remove obsoleted nodes from
that list when they become obsolete. 

Question: What is your ratio of obsolete to valid nodes, and hence what
benefit, if any, would you gain from turning the singly-linked list into
a doubly-linked list (and increasing the size of the structure by
another pointer) in order to be able to free the obsolete ones? Nobody's
ever checked, to my knowledge.

I suppose it's also possible to take the CPU-time cost of removing the
nodes even from the singly-linked list; nobody's ever done an analysis
of what this would cost either.

Look at jffs2_mark_node_obsolete and see how much time it will take to
start at jeb->first_node, walking the ->next_phys list till you find the
newly-obsoleted raw_node_ref, and free it. You also have to find the
inode number of the inode to which the node belongs (if any), by using
jffs2_raw_ref_to_inum(), and then walk _that_ list too to remove the
raw_node_ref in question.

Note that you can't actually free obsolete node refs which refer to
obsolete directory entries, because we need to keep track of them on
NAND flash. See jffs2_garbage_collect_deletion_dirent() for the gory
details.

> - The size of a single struct jffs2_raw_node_ref is 16 bytes. In ecos, these
>   structs are allocated through calls to malloc(). If the underlying implementation
>   is dlmalloc, as is probably the case most often, the minimum allocation size is
>   24 bytes, so some memory is wasted here. A fixed-size block allocator would be
>   more appropriate.

That one should be relatively easy to do. We do it in Linux already;
each object type already has its own allocation function in malloc.c

> - In http://lists.infradead.org/pipermail/linux-mtd/2003-August/008372.html,
>   David Woodhouse comments on this, suggesting possible improvements. I do not
>   know if any work is going on to implement one of these (probably not).

Omitting the 'totlen' field should be relatively simple if you're not
freeing obsolete refs. Observe that in 99% of cases, it's true that

	ref->totlen == ref_offset(ref->next_phys) - ref_offset(ref)

Make it 100% and make me believe it, and you can remove totlen from the
structure.

You do have the choice between freeing obsolete refs and the totlen
optimisation though -- obviously they don't really work together. You
could _merge_ contiguous obsolete data-node refs and free some RAM
though, while still keeping the simple way of finding totlen.

-- 
dwmw2

Re: [ECOS] Stress testing JFFS2

[Thomas Koeller]

Hi David,

thanks for your quick response.

> All correct. But you miss the observation that we also keep a
> raw_node_ref around for _obsolete_ nodes, which perhaps we could avoid.
> In fact, we do this because the raw_node_ref is in a singly-linked list,
> and it's going to be very inefficient to remove obsoleted nodes from
> that list when they become obsolete.

I do not think this path leads anywhere I want to go. The flash size
was chosen to meet the expected storage requirements, which means that
at some point the flash will be filled with valid data and consequently
there will be few obsoleted nodes. I expect this to be true for most
systems.

> Omitting the 'totlen' field should be relatively simple if you're not
> freeing obsolete refs. Observe that in 99% of cases, it's true that
>
> 	ref->totlen == ref_offset(ref->next_phys) - ref_offset(ref)
>
> Make it 100% and make me believe it, and you can remove totlen from the
> structure.
>

I will consider that.

tk
--------------------------------------------------

Thomas Koeller, Software Development

Basler Vision Technologies
An der Strusbek 60-62
22926 Ahrensburg
Germany

Tel +49 (4102) 463-162
Fax +49 (4102) 463-239

mailto:thomas.koeller@baslerweb.com
http://www.baslerweb.com

==============================

Re: [ECOS] Stress testing JFFS2

[David Woodhouse]

On Wed, 2003-10-15 at 13:30 +0200, Thomas Koeller wrote:
> I do not think this path leads anywhere I want to go. The flash size
> was chosen to meet the expected storage requirements, which means that
> at some point the flash will be filled with valid data and consequently
> there will be few obsoleted nodes. I expect this to be true for most
> systems.

A sane observation.

> > Omitting the 'totlen' field should be relatively simple if you're not
> > freeing obsolete refs. Observe that in 99% of cases, it's true that
> >
> > 	ref->totlen == ref_offset(ref->next_phys) - ref_offset(ref)
> >
> > Make it 100% and make me believe it, and you can remove totlen from the
> > structure.
> >
> 
> I will consider that.

OK... I've made it slightly easier for you by switching all use of
'ref->totlen' to an accessor function ref_totlen(c, jeb, ref), where
'jeb' can be NULL if the caller doesn't know it -- it _can_ be
calculated in the relatively rare case that it's required, but if it's
already to hand we might as well use it.

I've written what I suspect will be the new version of that accessor
function, and included some sanity checks for it. It's in #if 0 for now
since we know it'll be broken -- look in nodelist.h. We may end up
wanting it out of line, since it's not entirely trivial.

To make it usable, we need to ensure that we have a node reference for
areas of dirty space which we've previously been ignoring -- scan.c can
no longer just skip over stuff it ignores but must allocate node
references for it, and we must allocate node references for the wasted
space at the end of eraseblocks when we've filled them _almost_ to the
end and then filed them elsewhere.

It should be relatively simple.

-- 
dwmw2

Re: [ECOS] Stress testing JFFS2

[Thomas Koeller]

Dinesh Kumar wrote:
> I am newbie to JFFS2. What is the reason behind not
> freeing jffs2_raw_node_ref from RAM (even after they
> have been used)?

Their purpose is to represent physical nodes in the FLASH,
and so they must remain just as long as those.

tk
--------------------------------------------------

Thomas Koeller, Software Development

Basler Vision Technologies
An der Strusbek 60-62
22926 Ahrensburg
Germany

Tel +49 (4102) 463-162
Fax +49 (4102) 463-239

mailto:thomas.koeller@baslerweb.com
http://www.baslerweb.com

==============================