Re: [ECOS] JFFS2 Garbage Collection Error?

[Scott Wilkinson <scott at alliantnetworks dot com>]

> > What I see is that on both the synthetic and real target the exact same
> > behavior happens.  Everything works fine until the first time that
> > jffs2_garbage_collect_dnode() gets called.  A few more calls down the
> > stack and I take and exception caused by rb_remove_color dereferencing a
> > null pointer.
> > 
> > Has anyone seen anything like this? 
> 
> I haven't, but admittedly most of my testing is under Linux. I suspect
> it's a bug with my port of the BSD rbtree code to eCos, or a bug in
> jffs2_add_full_dnode_to_inode() which only manifests itself in eCos for
> some reason.
> 

Indeed this seems to be a problem with the red-black tree implementation
on eCos.  I attached a small sample eCos app which reproduces the
problem.  (Note, with only few small mods you can compile it against the
linux rbtree.[ch] and it runs fine.)

It looks like this rbtree.[ch] came from OpenBSD.  Could there be a
problem there too?

If, for testing purposes, I compile eCos using the linux rbtree.[ch]
instead of the eCos/OpenBSD port, my JFFS2 stuff works (and very well so
far I might add!).

I must admit I am not a rbtree expert, so if anyone sees the problem in
the eCos code, please submit a patch!


#include <string.h>
#include <stdio.h>

#include <cyg/infra/diag.h>            // HAL polled output

#define RB_EXTERNAL_DISPLAY
#include <linux/rbtree.h>

void rb_display(const char* prefix, struct rb_node *node)
{
  char new_prefix[64];

  sprintf(new_prefix,"%s  ", prefix);

  diag_printf("%srb_node (0x%08x)\n", prefix, node);
  diag_printf("%sparent=0x%08x\n", prefix, node->rb_parent);
  diag_printf("%scolor=%s\n", prefix, 
              node->rb_color == RB_BLACK ? "BLACK" : "RED");
  diag_printf("%sleft:\n", prefix);
  if (node->rb_left)
  {
    rb_display(new_prefix, node->rb_left);
  }
  else
  {
    diag_printf("%sNULL\n", new_prefix);
  }
  diag_printf("%sright:\n", prefix);
  if (node->rb_right)
  {
    rb_display(new_prefix, node->rb_right);
  }
  else
  {
    diag_printf("%sNULL\n", new_prefix);
  }
}

int right_insert(struct rb_root *root, struct rb_node *node,
                 struct rb_node *parent)
{
  if (parent->rb_right != NULL)
  {
    diag_printf("Trying to insert over existing node!\n");
    return 0;
  }
  rb_link_node(node, parent, &parent->rb_right);
  rb_insert_color(node, root);

  return 1;
}

void cyg_start(void)
{
  struct rb_node nodes[10];
  struct rb_root root;
  int i;

  diag_printf("Red-Black Tree Test\n");
  
  memset(&root, 0x0, sizeof(struct rb_root));
  memset(nodes, 0x0, sizeof(struct rb_node) * 10);

  /* Insert the first node as the root node */
  rb_link_node(&nodes[0], NULL, &root.rb_node);
  rb_insert_color(&nodes[0], &root);

  /* Insert the remaining nodes, all on the right.  The tree will balance
     iteself. */
  for (i=1; i < 10; i++)
  {
    if (!right_insert(&root, &nodes[i], &nodes[i-1]))
    {
      diag_printf("Failure!\n");
      break;
    }
  }

  rb_display("before: ", root.rb_node);
  diag_printf("\n");

  /* This will cause an exception by derefrencing a NULL pointer, but why!!! */
  rb_erase(&nodes[1], &root);

  rb_display("after: ", root.rb_node);
  diag_printf("\n");
}

-- 
Before posting, please read the FAQ: http://sources.redhat.com/fom/ecos
and search the list archive: http://sources.redhat.com/ml/ecos-discuss