* Re: [ECOS] Stress testing JFFS2 [not found] ` <20031008115231.7d1f012f.jani@iv.ro> @ 2003-10-15 10:11 ` Thomas Koeller 2003-10-15 10:52 ` David Woodhouse 0 siblings, 1 reply; 5+ messages in thread From: Thomas Koeller @ 2003-10-15 10:11 UTC (permalink / raw) To: ecos-discuss; +Cc: linux-mtd 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 ============================== ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [ECOS] Stress testing JFFS2 2003-10-15 10:11 ` [ECOS] Stress testing JFFS2 Thomas Koeller @ 2003-10-15 10:52 ` David Woodhouse 2003-10-15 11:30 ` Thomas Koeller 0 siblings, 1 reply; 5+ messages in thread From: David Woodhouse @ 2003-10-15 10:52 UTC (permalink / raw) To: Thomas Koeller; +Cc: linux-mtd, ecos-discuss 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [ECOS] Stress testing JFFS2 2003-10-15 10:52 ` David Woodhouse @ 2003-10-15 11:30 ` Thomas Koeller 2003-10-16 10:25 ` David Woodhouse 0 siblings, 1 reply; 5+ messages in thread From: Thomas Koeller @ 2003-10-15 11:30 UTC (permalink / raw) To: David Woodhouse; +Cc: linux-mtd, ecos-discuss 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 ============================== ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [ECOS] Stress testing JFFS2 2003-10-15 11:30 ` Thomas Koeller @ 2003-10-16 10:25 ` David Woodhouse 0 siblings, 0 replies; 5+ messages in thread From: David Woodhouse @ 2003-10-16 10:25 UTC (permalink / raw) To: Thomas Koeller; +Cc: linux-mtd, ecos-discuss 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
[parent not found: <20031015115257.16327.qmail@web8006.mail.in.yahoo.com>]
* Re: [ECOS] Stress testing JFFS2 [not found] <20031015115257.16327.qmail@web8006.mail.in.yahoo.com> @ 2003-10-15 12:58 ` Thomas Koeller 0 siblings, 0 replies; 5+ messages in thread From: Thomas Koeller @ 2003-10-15 12:58 UTC (permalink / raw) To: Dinesh Kumar; +Cc: linux-mtd, ecos-discuss 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 ============================== ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2003-10-16 10:25 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <1065598642.12197.6.camel@famine> [not found] ` <20031008115231.7d1f012f.jani@iv.ro> 2003-10-15 10:11 ` [ECOS] Stress testing JFFS2 Thomas Koeller 2003-10-15 10:52 ` David Woodhouse 2003-10-15 11:30 ` Thomas Koeller 2003-10-16 10:25 ` David Woodhouse [not found] <20031015115257.16327.qmail@web8006.mail.in.yahoo.com> 2003-10-15 12:58 ` Thomas Koeller
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.