[Yaffs] heavy file usage in yaffs

[Jacob Dall]

Hello Charles,

I accept your priority, but this slow dirlist issue is very important to me=
. I really need a way faster method of giving me the name of the files in a=
 folder.

I've come up with a solution - so far, it works for me when listing the roo=
t folder containing files only (no symlinks, hardlinks or folders). But I'm=
 not sure whether or not it'll generally work no matter the layout of files=
 and folders.

<code>
char *yaffs_Dir (const char *path) {
  char *rest;
  yaffs_Device *dev =3D NULL;
  yaffs_Object *obj;
  yaffs_Object *entry =3D NULL;
  struct list_head *i;
  char name[1000], str[1000], info[1000];
  char *names =3D (char*)malloc(15*10000);
  int nOk =3D 0, nNull =3D 0;
  int len =3D strlen(path);
  struct yaffs_stat s;

  memset(names, 0, 15*10000);
  obj =3D yaffsfs_FindRoot(path,&rest);
  if (obj && obj->variantType =3D=3D YAFFS_OBJECT_TYPE_DIRECTORY) {
    list_for_each(i,&obj->variant.directoryVariant.children) {
      entry =3D (i) ? list_entry(i, yaffs_Object,siblings) : NULL;
  	if (entry) {
        yaffs_GetObjectName(entry,name,YNAME_MAX+1);
        sprintf(str, "%s/%s", path, name);
        yaffs_lstat(str,&s);
        sprintf(info, "%s length %ld mode %x\n",name,s.st_size,s.st_mode);
        strcat(names, info);
        nOk++;
  	} else {
  	  nNull++;
  	}
    }
  }
  printf("nOk=3D%d, nNull=3D%d\n",nOk,nNull);
  return names;
}
</code>

In my system, this function takes approx. 10 secs to complete - that's amaz=
ing 60 times faster than if using the 'opendir/readdir' implemented in yaff=
s.

Comments are very welcome.

Thanks,
Jacob

----- Original Message -----
From: "Charles Manning" <manningc2@actrix.gen.nz>
To: "Jacob Dall" <jacob.dall@operamail.com>, "Charles Manning" <Charles.Man=
ning@trimble.co.nz>, yaffs@stoneboat.aleph1.co.uk
Subject: Re: [Yaffs] heavy file usage in yaffs
Date: Tue, 18 Jan 2005 15:20:57 +1300

>=20
> On Tuesday 18 January 2005 04:00, Jacob Dall wrote:
> > Hello Charles,
> >
> > All file names are on a 8.3 format, and NO, I'm not using
> > SHORT_NAMES_IN_RAM.
> >
> > I've just recompiled my project defining CONFIG_YAFFS_SHORT_NAMES_IN_RA=
M,
> > but unfortunately I notice no change in time used to perform the dumpDi=
r().
> >
> > The files I'm listing, was written before I defined short names in RAM.=
 In
> > this case, should one expect the operation to take less time?
> >
> > The CPU I'm running this test on, is comparable to a Pentium I-200MHz.
>=20
>=20
> NB This only applies to yaffs_direct, not to Linux.
>=20
> I did some tests using yaffs direct as a user application on a ram emulat=
ion
> under Linux.
>=20
> This too showed slowing. I did some profiling with gprof which pretty qui=
ckly
> pointed to the problem...
>=20
> The way yaffs does the directory searching is to create a linked list of
> items found so far in the DIR handle. When it does a read_dir, it has to =
walk
> the list of children in the directory and check if the entry in in the li=
st
> of items found so far. This makes the look up time increase proportional =
to
> the square of the number of items found (O(n^2)) so far ( ie. each time it
> looks at more directory entries as well as compare them to a longer "alre=
ady
> found" list).
>=20
> The current implementation could be sped up somewhat by using a balanced
> binary tree for the "found list". This would reduce the time to O(n log n=
). I
> could be motivated to do something about this but it is not a current
> priority for me.
>=20
> The other approach is the weasle approach. Don't use such large directori=
es.
> but rather structure your directory tree to use smaller sub-directories.
>=20
> -- Charles
>=20
>=20
>=20
> _______________________________________________
> yaffs mailing list
> yaffs@stoneboat.aleph1.co.uk
> http://stoneboat.aleph1.co.uk/cgi-bin/mailman/listinfo/yaffs