Prune obsolete raw_node_ref's from RAM

Prune obsolete raw_node_ref's from RAM

[Øyvind Harboe]

[-- Attachment #1: Type: text/plain, Size: 425 bytes --]

This patch prunes raw_node_ref's from RAM so as to achieve a fixed
steady state RAM memory footprint when the number of files is constant. 

The diff is against the eCos repository since thats where all this
started:

http://ecos.sourceware.org/ml/ecos-discuss/2004-07/msg00158.html



Remaining issues to be checked:

- Is the code correct? 
- What performance impact does it have? 

-- 
Øyvind Harboe
http://www.zylin.com


[-- Attachment #2: memleakfix.txt --]
[-- Type: text/x-patch, Size: 2040 bytes --]

Index: nodemgmt.c
===================================================================
RCS file: /cvs/ecos/ecos/packages/fs/jffs2/current/src/nodemgmt.c,v
retrieving revision 1.6
diff -w -u -r1.6 nodemgmt.c
--- nodemgmt.c	11 Dec 2003 23:33:54 -0000	1.6
+++ nodemgmt.c	13 Jul 2004 13:35:44 -0000
@@ -549,6 +549,60 @@
 		printk(KERN_WARNING "Short write in obliterating obsoleted node at 0x%08x: %zd\n", ref_offset(ref), retlen);
 		return;
 	}
+
+	// Merge obsolete nodes into its previous node, i.e. always leave
+	// one node behind so as not to screw up ref_totlen()
+	if (ref->next_in_ino!=NULL)
+	  {	
+	    bool moreToDo;
+	    do {
+	      moreToDo=false;	      
+	      struct jffs2_inode_cache *ic;
+	      ic = jffs2_raw_ref_to_ic(ref);
+
+	      // unlink the node and 
+	      struct jffs2_raw_node_ref *raw;
+	      struct jffs2_raw_node_ref *prev=NULL;
+	      raw = ic->nodes;
+	      for (raw = ic->nodes; raw != (void *)ic; raw = raw->next_in_ino) {
+		// if this node *and* the previous *physical node* are obsolete, combine them.
+		if ((prev!=NULL)&&ref_obsolete(raw)) {
+		  // now take take it off the physcial list, unless it is the 
+		  // first node.
+		  struct jffs2_raw_node_ref *t;
+		  struct jffs2_raw_node_ref *phys_prev=NULL;
+		  t=jeb->first_node;
+		  while (t!=NULL) {
+		    if ((phys_prev!=NULL)&&(t==raw)&&ref_obsolete(prev)) {
+		      // take it off the inode list.
+		      prev->next_in_ino=t->next_in_ino;
+		      
+		      // take it off the physical list
+		      phys_prev->next_phys=t->next_phys;
+		      // update last physical entry pointer...
+		      if (jeb->last_node==t) {
+			jeb->last_node=t->next_phys;
+		      }
+		      
+		      // update physical __totlen field.
+		      phys_prev->__totlen+=t->__totlen;
+	      
+	  
+		      jffs2_free_raw_node_ref(raw);
+		      moreToDo=true;
+
+		      break;
+		    }
+		    phys_prev=t;
+		    t=t->next_phys;
+		  }
+		  break;
+		}
+		prev=raw;
+	      }
+	    } while (moreToDo);
+	      }
+	
 }
 
 #if CONFIG_JFFS2_FS_DEBUG > 0

Re: Prune obsolete raw_node_ref's from RAM

[David Woodhouse]

On Tue, 2004-07-13 at 16:18 +0200, Øyvind Harboe wrote:
> - Is the code correct? 

It looks OK at first glance but I can't actually tell. List mangling
code is hard enough to read when it's in the style I understand :)

I've rewritten it and just posted that version. 

> - What performance impact does it have? 

It'll go walking the lists every time a node is obsoleted. My guess is
it'll make the performance suck _hard_. But it will get you your memory
back. I suspect it should be a configuration option -- or maybe we could
stick the list-walking code into a separate function and call it
periodically to do the cleanup, rather than doing it every time.

Could do with seeing some profiling info.

-- 
dwmw2

Re: Prune obsolete raw_node_ref's from RAM

[Øyvind Harboe]

On Wed, 2004-07-14 at 01:14, David Woodhouse wrote:
> On Tue, 2004-07-13 at 16:18 +0200, Øyvind Harboe wrote:
> > - Is the code correct? 
> 
> It looks OK at first glance but I can't actually tell. List mangling
> code is hard enough to read when it's in the style I understand :)
> 
> I've rewritten it and just posted that version. 

Excellent! I'll make sure to run my tests with your new version.

> > - What performance impact does it have? 
> 
> It'll go walking the lists every time a node is obsoleted. My guess is
> it'll make the performance suck _hard_. But it will get you your memory
> back. I suspect it should be a configuration option -- or maybe we could
> stick the list-walking code into a separate function and call it
> periodically to do the cleanup, rather than doing it every time.

Note that in my case I have the following usage:

- Little RAM(so freeing up is essential)
- Big flash disk(mainly for wear levelling purposes).
- Few and small files
- Lots of deleted nodes
- The application overwrites existing files with regular intervals

In this scenario, the performance should be fine.

In a scneario with:

- lots of files
- lots of ram
- occasional freing up

Performance should suck.

> Could do with seeing some profiling info.

Would all the performance problems go away if the lists were doubly
linked?

-- 
Øyvind Harboe
http://www.zylin.com

Re: Prune obsolete raw_node_ref's from RAM

[David Woodhouse]

On Wed, 2004-07-14 at 08:26 +0200, Øyvind Harboe wrote:
> Would all the performance problems go away if the lists were doubly
> linked?

Well yes, but since the object of the exercise was to save memory,
doubling the size of the objects in question doesn't really strike me as
being the right way to approach the problem :)

-- 
dwmw2

Re: Prune obsolete raw_node_ref's from RAM

[Øyvind Harboe]

On Wed, 2004-07-14 at 08:41, David Woodhouse wrote:
> On Wed, 2004-07-14 at 08:26 +0200, Øyvind Harboe wrote:
> > Would all the performance problems go away if the lists were doubly
> > linked?
> 
> Well yes, but since the object of the exercise was to save memory,
> doubling the size of the objects in question doesn't really strike me as
> being the right way to approach the problem :)

The memory problem I ran into wasn't the size of the un-obsolete nodes,
but that they grew with the number of obsolete nodes.

I hate #if's in code as much as the next guy, but JFFS2 spans deeply
embedded systems to full-fledged PCs and it is only to be expected that
the different profiles have different needs.

-- 
Øyvind Harboe
http://www.zylin.com

Re: Prune obsolete raw_node_ref's from RAM

[David Woodhouse]

On Wed, 2004-07-14 at 08:51 +0200, Øyvind Harboe wrote:
> On Wed, 2004-07-14 at 08:41, David Woodhouse wrote:
> > On Wed, 2004-07-14 at 08:26 +0200, Øyvind Harboe wrote:
> > > Would all the performance problems go away if the lists were doubly
> > > linked?
> > 
> > Well yes, but since the object of the exercise was to save memory,
> > doubling the size of the objects in question doesn't really strike me as
> > being the right way to approach the problem :)
> 
> The memory problem I ran into wasn't the size of the un-obsolete nodes,
> but that they grew with the number of obsolete nodes.
> 
> I hate #if's in code as much as the next guy, but JFFS2 spans deeply
> embedded systems to full-fledged PCs and it is only to be expected that
> the different profiles have different needs.

Well, I'm more than happy to do 
	#define jffs2_prune_ref_lists(c, ref) do { } while (0)
in the Linux code and let the implementation we're playing with live in
eCos code alone. It would be nicer if it were generic though -- that's
why I'm thinking about making it happen in a periodic pass, rather than
doing it all on _every_ obsoletion. By doing it every single time, we
maximise the amount of list-walking required. 

We could walk the next_in_ino list when we remove a given inode from the
inode cache, dropping all obsolete nodes from it then in a single pass. 

And we could walk each eraseblock's list at some other time...



-- 
dwmw2

Re: Prune obsolete raw_node_ref's from RAM

[Øyvind Harboe]

On Wed, 2004-07-14 at 09:08, David Woodhouse wrote:
> On Wed, 2004-07-14 at 08:51 +0200, Øyvind Harboe wrote:
> > On Wed, 2004-07-14 at 08:41, David Woodhouse wrote:
> > > On Wed, 2004-07-14 at 08:26 +0200, Øyvind Harboe wrote:
> > > > Would all the performance problems go away if the lists were doubly
> > > > linked?
> > > 
> > > Well yes, but since the object of the exercise was to save memory,
> > > doubling the size of the objects in question doesn't really strike me as
> > > being the right way to approach the problem :)
> > 
> > The memory problem I ran into wasn't the size of the un-obsolete nodes,
> > but that they grew with the number of obsolete nodes.
> > 
> > I hate #if's in code as much as the next guy, but JFFS2 spans deeply
> > embedded systems to full-fledged PCs and it is only to be expected that
> > the different profiles have different needs.
> 
> Well, I'm more than happy to do 
> 	#define jffs2_prune_ref_lists(c, ref) do { } while (0)
> in the Linux code and let the implementation we're playing with live in
> eCos code alone. It would be nicer if it were generic though -- that's
> why I'm thinking about making it happen in a periodic pass, rather than
> doing it all on _every_ obsoletion. By doing it every single time, we
> maximise the amount of list-walking required. 
> 
> We could walk the next_in_ino list when we remove a given inode from the
> inode cache, dropping all obsolete nodes from it then in a single pass. 
> 
> And we could walk each eraseblock's list at some other time...

Hmmm... how about a configurable threshold(i.e. a maximum number
obsolete nodes) that triggers a "purge" at the end of
jffs2_mark_node_obsolete()?

A "purge" would be to loop through all the physical nodes and merge
those that can be merged.

For my purposes, I need to make sure that there is a predictable peak
usage of RAM. What precisely that peak usage is, is somewhat less
important.

-- 
Øyvind Harboe
http://www.zylin.com