[Yaffs] heavy file usage in yaffs

[Charles Manning]

Sure that will work as a way to get all the file names in a directory.

The original interface was designed to support the standard POSIX/clib
calls. Bypassing with special calls can work, but will bind you to this
code.

I'm not really that amazed that you get such a speed up. The
opendir/readdir stuff is far from optimal for large directories.

-- Charles


> -----Original Message-----
> From: Jacob Dall [mailto:jacob.dall@operamail.com]=20
> Sent: Monday, 24 January 2005 9:00 a.m.
> To: manningc2@actrix.gen.nz; Charles Manning;=20
> yaffs@stoneboat.aleph1.co.uk
> Subject: Re: [Yaffs] heavy file usage in yaffs
>=20
>=20
> Hello Charles,
>=20
> I accept your priority, but this slow dirlist issue is very=20
> important to me. I really need a way faster method of giving=20
> me the name of the files in a folder.
>=20
> I've come up with a solution - so far, it works for me when=20
> listing the root folder containing files only (no symlinks,=20
> hardlinks or folders). But I'm not sure whether or not it'll=20
> generally work no matter the layout of files and folders.
>=20
> <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;
>=20
>   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=20
> %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>
>=20
> In my system, this function takes approx. 10 secs to complete=20
> - that's amazing 60 times faster than if using the=20
> 'opendir/readdir' implemented in yaffs.
>=20
> Comments are very welcome.
>=20
> Thanks,
> Jacob
>=20
> ----- Original Message -----
> From: "Charles Manning" <manningc2@actrix.gen.nz>
> To: "Jacob Dall" <jacob.dall@operamail.com>, "Charles=20
> Manning" <Charles.Manning@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
> >=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=20
> > > SHORT_NAMES_IN_RAM.
> > >
> > > I've just recompiled my project defining=20
> > > CONFIG_YAFFS_SHORT_NAMES_IN_RAM, but unfortunately I notice no=20
> > > change in time used to perform the dumpDir().
> > >
> > > The files I'm listing, was written before I defined short=20
> names in=20
> > > RAM. In this case, should one expect the operation to take less=20
> > > time?
> > >
> > > The CPU I'm running this test on, is comparable to a Pentium=20
> > > 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=20
> > emulation under Linux.
> >=20
> > This too showed slowing. I did some profiling with gprof=20
> which pretty=20
> > quickly pointed to the problem...
> >=20
> > The way yaffs does the directory searching is to create a=20
> linked list=20
> > of items found so far in the DIR handle. When it does a=20
> read_dir, it=20
> > has to walk the list of children in the directory and check if the=20
> > entry in in the list of items found so far. This makes the look up=20
> > time increase proportional to the square of the number of=20
> items found=20
> > (O(n^2)) so far ( ie. each time it looks at more directory=20
> entries as=20
> > well as compare them to a longer "already found" list).
> >=20
> > The current implementation could be sped up somewhat by using a=20
> > balanced binary tree for the "found list". This would=20
> reduce the time=20
> > to O(n log n). I could be motivated to do something about=20
> this but it=20
> > is not a current priority for me.
> >=20
> > The other approach is the weasle approach. Don't use such large=20
> > directories. but rather structure your directory tree to=20
> use smaller=20
> > sub-directories.
> >=20
> > -- Charles
> >=20
> >=20
> >=20
> > _______________________________________________
> > yaffs mailing list
> > yaffs@stoneboat.aleph1.co.uk=20
> > http://stoneboat.aleph1.co.uk/cgi-bin/mailman/listinfo/yaffs
>=20
>=20