jffs2 and Doc 2000

jffs2 and Doc 2000

[eylon eyal]

hello
1) i saw the thread about recommended fs to Doc.
and i was wonderring if any one has a link to a good howto/tutorial how to 
create a bootable Doc with jffs2 on it? like the excellent tutorial about 
grub and DoC

2) alot of guys asks about ext2 and Doc... if ext2 is so bad so why is the big 
intrest in it? am i missing something about it?

3) anyone used jffs2 with DoC.?

thanks alot

Interest in DOC and YAFFS?

[Charles Manning]

Hi

I'm considering getting YAFFS working on DOC. I'm trying to gauge interest to 
prioritise vs other things.

If you don't know what YAFFS is, it's a NAND-specific  journalling file 
system. Ask Google for more info.

Currently YAFFS works with raw NAND (using software ecc), though some people 
have patched it to use hardware ecc, so I figure DOC support should be 
relatively simple. 

-- CHarles

Re: Interest in DOC and YAFFS?

[Marc Singer]

On Tue, Sep 24, 2002 at 12:03:45PM +1200, Charles Manning wrote:
> Hi
> 
> I'm considering getting YAFFS working on DOC. I'm trying to gauge
> interest to prioritise vs other things.
> 
> If you don't know what YAFFS is, it's a NAND-specific journalling
> file system. Ask Google for more info.
> 
> Currently YAFFS works with raw NAND (using software ecc), though
> some people have patched it to use hardware ecc, so I figure DOC
> support should be relatively simple.

Do you know how it boots?  Does grub support it?

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Charles Manning]

On Tue, 24 Sep 2002 15:44, Marc Singer wrote:
> On Tue, Sep 24, 2002 at 12:03:45PM +1200, Charles Manning wrote:
> > Hi
> >
> > I'm considering getting YAFFS working on DOC. I'm trying to gauge
> > interest to prioritise vs other things.
> >
> > If you don't know what YAFFS is, it's a NAND-specific journalling
> > file system. Ask Google for more info.
> >
> > Currently YAFFS works with raw NAND (using software ecc), though
> > some people have patched it to use hardware ecc, so I figure DOC
> > support should be relatively simple.
>
> Do you know how it boots?  Does grub support it?

By "it" I assume you mean YAFFS.

Doing a yaffs-specific bootloader is pretty simple. We have discussed the 
general approach  on the YAFFS list before. At least two people have done 
yaffs bootloaders. One of these might be rolled in with grub. Maybe someone 
else on the yaffs list can answer that.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 03:58:00PM +1200, Charles Manning wrote:
> On Tue, 24 Sep 2002 15:44, Marc Singer wrote:
> > On Tue, Sep 24, 2002 at 12:03:45PM +1200, Charles Manning wrote:
> > > Hi
> > >
> > > I'm considering getting YAFFS working on DOC. I'm trying to gauge
> > > interest to prioritise vs other things.
> > >
> > > If you don't know what YAFFS is, it's a NAND-specific journalling
> > > file system. Ask Google for more info.
> > >
> > > Currently YAFFS works with raw NAND (using software ecc), though
> > > some people have patched it to use hardware ecc, so I figure DOC
> > > support should be relatively simple.
> >
> > Do you know how it boots?  Does grub support it?
> 
> By "it" I assume you mean YAFFS.
> 
> Doing a yaffs-specific bootloader is pretty simple. We have discussed the 
> general approach  on the YAFFS list before. At least two people have done 
> yaffs bootloaders. One of these might be rolled in with grub. Maybe someone 
> else on the yaffs list can answer that.

Some people think that writing a new kernel would be easy.  %^)

The trouble is coming up with a convenient method.  LILO stores a list
of blocks.  GRUB reads filesystems.  GRUB is better in the long run,
but harder to implement.

Nowadays, I'm using syslinux because LILO is such a pain to get right
and GRUB doesn't (last time I checked) like the DOC.  I just got done
working out the kinks in etherboot so it will run with a DOC.  I guess
GRUB is next.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Russ Dill]

> Some people think that writing a new kernel would be easy.  %^)
> 
> The trouble is coming up with a convenient method.  LILO stores a list
> of blocks.  GRUB reads filesystems.  GRUB is better in the long run,
> but harder to implement.

I've written a cramfs reader for grub, to use on the DOC, and grub works
great on a DOC. Although the grub code is a bit ugly, and there are a
few gotchas, writing a module is pretty straight forward. That being
said, writing a module to load files of a journaled fs (jffs2), is a bit
more time consuming, but as I understand yaffs is greatly optimized
towards NAND (as apposed to NOR) flash layout and lends itself to easy
reading (same sized blocks, no compression iirc).

If I were you, I'd use grub.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 12:53:36AM -0700, Russ Dill wrote:
> 
> > Some people think that writing a new kernel would be easy.  %^)
> > 
> > The trouble is coming up with a convenient method.  LILO stores a list
> > of blocks.  GRUB reads filesystems.  GRUB is better in the long run,
> > but harder to implement.
> 
> I've written a cramfs reader for grub, to use on the DOC, and grub works
> great on a DOC. Although the grub code is a bit ugly, and there are a
> few gotchas, writing a module is pretty straight forward. That being
> said, writing a module to load files of a journaled fs (jffs2), is a bit
> more time consuming, but as I understand yaffs is greatly optimized
> towards NAND (as apposed to NOR) flash layout and lends itself to easy
> reading (same sized blocks, no compression iirc).
> 
> If I were you, I'd use grub.

That's what I'd expect.

A question, though.  I've been doing compression tests with cramfs.
I'm finding that gzip -9 of an ext2 filesystem produces smaller images
than mkcramfs.  Have you ever compared the two?

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Russ Dill]

On Tue, 2002-09-24 at 09:53, Marc Singer wrote:
> On Tue, Sep 24, 2002 at 12:53:36AM -0700, Russ Dill wrote:
> > 
> > > Some people think that writing a new kernel would be easy.  %^)
> > > 
> > > The trouble is coming up with a convenient method.  LILO stores a list
> > > of blocks.  GRUB reads filesystems.  GRUB is better in the long run,
> > > but harder to implement.
> > 
> > I've written a cramfs reader for grub, to use on the DOC, and grub works
> > great on a DOC. Although the grub code is a bit ugly, and there are a
> > few gotchas, writing a module is pretty straight forward. That being
> > said, writing a module to load files of a journaled fs (jffs2), is a bit
> > more time consuming, but as I understand yaffs is greatly optimized
> > towards NAND (as apposed to NOR) flash layout and lends itself to easy
> > reading (same sized blocks, no compression iirc).
> > 
> > If I were you, I'd use grub.
> 
> That's what I'd expect.
> 
> A question, though.  I've been doing compression tests with cramfs.
> I'm finding that gzip -9 of an ext2 filesystem produces smaller images
> than mkcramfs.  Have you ever compared the two?

cramfs is meant to be lean, fast, and low on ram consumption, if you
compress the whole thing at once, you have to load the whole thing into
ram to read any of it, so cramfs compresses PAGE_CACHE (4096) sized
pages at a time

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 09:59:03AM -0700, Russ Dill wrote:
> On Tue, 2002-09-24 at 09:53, Marc Singer wrote:
> > On Tue, Sep 24, 2002 at 12:53:36AM -0700, Russ Dill wrote:
> > > 
> > > > Some people think that writing a new kernel would be easy.  %^)
> > > > 
> > > > The trouble is coming up with a convenient method.  LILO stores a list
> > > > of blocks.  GRUB reads filesystems.  GRUB is better in the long run,
> > > > but harder to implement.
> > > 
> > > I've written a cramfs reader for grub, to use on the DOC, and grub works
> > > great on a DOC. Although the grub code is a bit ugly, and there are a
> > > few gotchas, writing a module is pretty straight forward. That being
> > > said, writing a module to load files of a journaled fs (jffs2), is a bit
> > > more time consuming, but as I understand yaffs is greatly optimized
> > > towards NAND (as apposed to NOR) flash layout and lends itself to easy
> > > reading (same sized blocks, no compression iirc).
> > > 
> > > If I were you, I'd use grub.
> > 
> > That's what I'd expect.
> > 
> > A question, though.  I've been doing compression tests with cramfs.
> > I'm finding that gzip -9 of an ext2 filesystem produces smaller images
> > than mkcramfs.  Have you ever compared the two?
> 
> cramfs is meant to be lean, fast, and low on ram consumption, if you
> compress the whole thing at once, you have to load the whole thing into
> ram to read any of it, so cramfs compresses PAGE_CACHE (4096) sized
> pages at a time

That's what isn't clear.  I made two filesystems with the same
contents.  One cramfs and the other ext2.  The ext2 filesystem
compressed was smaller than the cramfs.  My understanding is that both
must be uncompressed into a ramfs to be used.  If this is correct,
then the only comparable consideration is the size of the compressed
data.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Brian J. Fox]

   From: Marc Singer <elf@buici.com>
   Cc: Charles Manning <manningc2@actrix.gen.nz>, linux-mtd@lists.infradead.org,
      yaffs@toby-churchill.org
   Date: Tue, 24 Sep 2002 10:14:19 -0700

   On Tue, Sep 24, 2002 at 09:59:03AM -0700, Russ Dill wrote:
   > On Tue, 2002-09-24 at 09:53, Marc Singer wrote:
   > > On Tue, Sep 24, 2002 at 12:53:36AM -0700, Russ Dill wrote:
   > > > 
   > > 
   > > A question, though.  I've been doing compression tests with cramfs.
   > > I'm finding that gzip -9 of an ext2 filesystem produces smaller images
   > > than mkcramfs.  Have you ever compared the two?
   > 
   > cramfs is meant to be lean, fast, and low on ram consumption, if you
   > compress the whole thing at once, you have to load the whole thing into
   > ram to read any of it, so cramfs compresses PAGE_CACHE (4096) sized
   > pages at a time

   That's what isn't clear.  I made two filesystems with the same
   contents.  One cramfs and the other ext2.  The ext2 filesystem
   compressed was smaller than the cramfs.  My understanding is that both
   must be uncompressed into a ramfs to be used.  If this is correct,
   then the only comparable consideration is the size of the compressed
   data.

No, the size of the uncompressed data is also important.

Is the ext2 system uncompressed bigger, smaller, or the same size as
the uncompressed? cramfs?

brian

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Russ Dill]

> > > A question, though.  I've been doing compression tests with cramfs.
> > > I'm finding that gzip -9 of an ext2 filesystem produces smaller images
> > > than mkcramfs.  Have you ever compared the two?
> > 
> > cramfs is meant to be lean, fast, and low on ram consumption, if you
> > compress the whole thing at once, you have to load the whole thing into
> > ram to read any of it, so cramfs compresses PAGE_CACHE (4096) sized
> > pages at a time
> 
> That's what isn't clear.  I made two filesystems with the same
> contents.  One cramfs and the other ext2.  The ext2 filesystem
> compressed was smaller than the cramfs.  My understanding is that both
> must be uncompressed into a ramfs to be used.  If this is correct,
> then the only comparable consideration is the size of the compressed
> data.

no, a cramfs does not need to be loaded into a ramfs, only the pages
that are needed are loaded from the cramfs, and if memory is in a pinch,
fs pages can be dropped. If you gzip a 4M file at once, vs gzip 4096
byte pieces of it at a time, the former will end up smaller. (deflate
uses repetition of information, and runs of things).

of course, it depends which you want, greatly optimized memory usage
(cramfs), or a slightly smaller image.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 10:30:45AM -0700, Russ Dill wrote:
> > > > A question, though.  I've been doing compression tests with cramfs.
> > > > I'm finding that gzip -9 of an ext2 filesystem produces smaller images
> > > > than mkcramfs.  Have you ever compared the two?
> > > 
> > > cramfs is meant to be lean, fast, and low on ram consumption, if you
> > > compress the whole thing at once, you have to load the whole thing into
> > > ram to read any of it, so cramfs compresses PAGE_CACHE (4096) sized
> > > pages at a time
> > 
> > That's what isn't clear.  I made two filesystems with the same
> > contents.  One cramfs and the other ext2.  The ext2 filesystem
> > compressed was smaller than the cramfs.  My understanding is that both
> > must be uncompressed into a ramfs to be used.  If this is correct,
> > then the only comparable consideration is the size of the compressed
> > data.
> 
> no, a cramfs does not need to be loaded into a ramfs, only the pages
> that are needed are loaded from the cramfs, and if memory is in a pinch,
> fs pages can be dropped. If you gzip a 4M file at once, vs gzip 4096
> byte pieces of it at a time, the former will end up smaller. (deflate
> uses repetition of information, and runs of things).
> 
> of course, it depends which you want, greatly optimized memory usage
> (cramfs), or a slightly smaller image.

Yes, that is the trade off.  I was unclear about how cramfs was
loaded.  It was my understanding that the cramfs was unpacked into a
ramfs so that the fs could be used R/W.

I'll evaluate it again when I have a chance.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Kenneth Johansson]

On Tue, 2002-09-24 at 19:14, Marc Singer wrote:
> That's what isn't clear.  I made two filesystems with the same
> contents.  One cramfs and the other ext2.  The ext2 filesystem
> compressed was smaller than the cramfs.  My understanding is that both
> must be uncompressed into a ramfs to be used.  If this is correct,
> then the only comparable consideration is the size of the compressed
> data.

cramfs is a read only filesystem not an archive format like zip or tar
so you do not have to copy the data into another filesystem to use it.
You use cramfs instead of initrd+filesystem.

-- 
Kenneth Johansson	
Ericsson AB                       Tel: +46 8 404 71 83
Borgafjordsgatan 9                Fax: +46 8 404 72 72
164 80 Stockholm                  kenneth.johansson@etx.ericsson.se

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 07:44:58PM +0200, Kenneth Johansson wrote:
> On Tue, 2002-09-24 at 19:14, Marc Singer wrote:
> > That's what isn't clear.  I made two filesystems with the same
> > contents.  One cramfs and the other ext2.  The ext2 filesystem
> > compressed was smaller than the cramfs.  My understanding is that both
> > must be uncompressed into a ramfs to be used.  If this is correct,
> > then the only comparable consideration is the size of the compressed
> > data.
> 
> cramfs is a read only filesystem not an archive format like zip or tar
> so you do not have to copy the data into another filesystem to use it.
> You use cramfs instead of initrd+filesystem.

That isn't really the issue here.  We're talking about using gzip'd
ext2 versus cramfs to do initrd.  The thing is that in my tests,
cramfs images are larger than compressed ext2 images.  Not what I
would expect.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Russ Dill]

> > cramfs is a read only filesystem not an archive format like zip or tar
> > so you do not have to copy the data into another filesystem to use it.
> > You use cramfs instead of initrd+filesystem.
> 
> That isn't really the issue here.  We're talking about using gzip'd
> ext2 versus cramfs to do initrd.  The thing is that in my tests,
> cramfs images are larger than compressed ext2 images.  Not what I
> would expect.

if you are talking about an initrd, then the features of cramfs aren't
quite as usefull, as the whole thing will be loaded into ram anyway. On
the other side:

A cramfs will always be exactly as small as it needs to be, no guessing
on an image size. cramfs is created by population, not by making an
image, formatting it, mounting it loopback, and then copying files.

incedentally, I have a copy of mkcramfs with device table support (as
seen in mkfs.jffs2) as well as permission squashing, so that a cramfs
image can be made withoutt root (complete with suid root programs, and
/dev entries)

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 11:47:43AM -0700, Russ Dill wrote:
> 
> > > cramfs is a read only filesystem not an archive format like zip or tar
> > > so you do not have to copy the data into another filesystem to use it.
> > > You use cramfs instead of initrd+filesystem.
> > 
> > That isn't really the issue here.  We're talking about using gzip'd
> > ext2 versus cramfs to do initrd.  The thing is that in my tests,
> > cramfs images are larger than compressed ext2 images.  Not what I
> > would expect.
> 
> if you are talking about an initrd, then the features of cramfs aren't
> quite as usefull, as the whole thing will be loaded into ram anyway. On
> the other side:

I see.  That is where my understanding comes from.  Now it makes sense.

> A cramfs will always be exactly as small as it needs to be, no guessing
> on an image size. cramfs is created by population, not by making an
> image, formatting it, mounting it loopback, and then copying files.

Indeed.  It can be inconvenient knowing how big to make the loopback
file.

> incedentally, I have a copy of mkcramfs with device table support (as
> seen in mkfs.jffs2) as well as permission squashing, so that a cramfs
> image can be made withoutt root (complete with suid root programs, and
> /dev entries)

I'd appreciate a copy of your mkcramfs changes.

Thanks.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Russ Dill]

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


> > incedentally, I have a copy of mkcramfs with device table support (as
> > seen in mkfs.jffs2) as well as permission squashing, so that a cramfs
> > image can be made withoutt root (complete with suid root programs, and
> > /dev entries)
> 
> I'd appreciate a copy of your mkcramfs changes.
> 

most of the credit here goes to Erik Andersen, as I used his device
table code from mkfs.jffs2.

[-- Attachment #2: mkcramfs.c --]
[-- Type: text/x-c, Size: 32810 bytes --]

/*
 * mkcramfs - make a cramfs file system
 *
 * Copyright (C) 1999-2001 Transmeta Corporation
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Added device table support (code taken from mkfs.jffs2.c, credit to
 * Erik Andersen <andersen@codepoet.org>) as well as an option to squash
 * permissions. - Russ Dill <Russ.Dill@asu.edu> September 2002
 *
 */

#define _GNU_SOURCE
#include <sys/types.h>
#include <stdio.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/fcntl.h>
#include <ctype.h>
#include <dirent.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include <getopt.h>
#include <linux/cramfs_fs.h>
#include <zlib.h>

#define PAD_SIZE 512		/* only 0 and 512 supported by kernel */

static const char *progname = "mkcramfs";

/* N.B. If you change the disk format of cramfs, please update fs/cramfs/README. */

/* Input status of 0 to print help and exit without an error. */
static void usage(int status)
{
	FILE *stream = status ? stderr : stdout;

	fprintf(stream, "usage: %s [-h] [-D file] [-e edition] [-i file] [-n name] dirname outfile\n"
		" -h         print this help\n"
		" -D         Use the named FILE as a device table file\n"
		" -E         make all warnings errors (non-zero exit status)\n"
		" -e edition set edition number (part of fsid)\n"
		" -i file    insert a file image into the filesystem (requires >= 2.4.0)\n"
		" -n name    set name of cramfs filesystem\n"
		" -p         pad by %d bytes for boot code\n"
		" -s         sort directory entries (old option, ignored)\n"
		" -z         make explicit holes (requires >= 2.3.39)\n"
		" -q         squash permissions (make everything owned by root)\n"
		" dirname    root of the filesystem to be compressed\n"
		" outfile    output file\n", progname, PAD_SIZE);

	exit(status);
}

#define PAGE_CACHE_SIZE (4096)
/* The kernel assumes PAGE_CACHE_SIZE as block size. */
static unsigned int blksize = PAGE_CACHE_SIZE;
static long total_blocks = 0, total_nodes = 1; /* pre-count the root node */
static int image_length = 0;

/*
 * If opt_holes is set, then mkcramfs can create explicit holes in the
 * data, which saves 26 bytes per hole (which is a lot smaller a
 * saving than most most filesystems).
 *
 * Note that kernels up to at least 2.3.39 don't support cramfs holes,
 * which is why this is turned off by default.
 */
static int opt_edition = 0;
static int opt_errors = 0;
static int opt_holes = 0;
static int opt_pad = 0;
static int opt_squash = 0;
static char *opt_image = NULL;
static char *opt_name = NULL;

static int warn_dev, warn_gid, warn_namelen, warn_skip, warn_size, warn_uid;

#ifndef MIN
# define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
#endif


/* FIXME:  MKDEV uses illicit insider knowledge of kernel 
 * major/minor representation...  */
#define MINORBITS	8
#define MKDEV(ma,mi)	(((ma) << MINORBITS) | (mi))

static void verror_msg(const char *s, va_list p)
{
	fflush(stdout);
	fprintf(stderr, "mkcramfs: ");
	vfprintf(stderr, s, p);
}

static void vperror_msg(const char *s, va_list p)
{
	int err = errno;

	if (s == 0)
		s = "";
	verror_msg(s, p);
	if (*s)
		s = ": ";
	fprintf(stderr, "%s%s\n", s, strerror(err));
}

static void error_msg_and_die(const char *s, ...)
{
	va_list p;

	va_start(p, s);
	verror_msg(s, p);
	va_end(p);
	putc('\n', stderr);
	exit(EXIT_FAILURE);
}

static void perror_msg_and_die(const char *s, ...)
{
	va_list p;

	va_start(p, s);
	vperror_msg(s, p);
	va_end(p);
	exit(EXIT_FAILURE);
}
#ifndef DMALLOC
static char *xstrdup(const char *s)
{
	char *t;

	if (s == NULL)
		return NULL;

	t = strdup(s);

	if (t == NULL)
		error_msg_and_die("out of memory");

	return t;
}
#endif

static FILE *xfopen(const char *path, const char *mode)
{
	FILE *fp;

	if ((fp = fopen(path, mode)) == NULL)
		perror_msg_and_die("%s", path);
	return fp;
}

/* In-core version of inode / directory entry. */
struct entry {
	/* stats */
	char *name;
	unsigned int mode, size, uid, gid;

	/* FS data */
	void *uncompressed;
        /* points to other identical file */
        struct entry *same;
        unsigned int offset;            /* pointer to compressed data in archive */
	unsigned int dir_offset;	/* Where in the archive is the directory entry? */

	/* organization */
	struct entry *child; /* null for non-directories and empty directories */
	struct entry *next;
};

/*
 * The longest file name component to allow for in the input directory tree.
 * Ext2fs (and many others) allow up to 255 bytes.  A couple of filesystems
 * allow longer (e.g. smbfs 1024), but there isn't much use in supporting
 * >255-byte names in the input directory tree given that such names get
 * truncated to 255 bytes when written to cramfs.
 */
#define MAX_INPUT_NAMELEN 255

static int find_identical_file(struct entry *orig,struct entry *newfile)
{
        if(orig==newfile) return 1;
        if(!orig) return 0;
        if(orig->size==newfile->size && orig->uncompressed && !memcmp(orig->uncompressed,newfile->uncompressed,orig->size)) {
                newfile->same=orig;
                return 1;
        }
        return find_identical_file(orig->child,newfile) ||
                   find_identical_file(orig->next,newfile);
}

static void eliminate_doubles(struct entry *root,struct entry *orig) {
        if(orig) {
                if(orig->size && orig->uncompressed)
			find_identical_file(root,orig);
                eliminate_doubles(root,orig->child);
                eliminate_doubles(root,orig->next);
        }
}

/*
 * We define our own sorting function instead of using alphasort which
 * uses strcoll and changes ordering based on locale information.
 */
static int cramsort (const void *a, const void *b)
{
	return strcmp ((*(const struct dirent **) a)->d_name,
		       (*(const struct dirent **) b)->d_name);
}

static unsigned int parse_directory(struct entry *root_entry, const char *name, struct entry **prev, loff_t *fslen_ub)
{
	struct dirent **dirlist;
	int totalsize = 0, dircount, dirindex;
	char *path, *endpath;
	size_t len = strlen(name);

	/* Set up the path. */
	/* TODO: Reuse the parent's buffer to save memcpy'ing and duplication. */
	path = malloc(len + 1 + MAX_INPUT_NAMELEN + 1);
	if (!path) {
		perror(NULL);
		exit(8);
	}
	memcpy(path, name, len);
	endpath = path + len;
	*endpath = '/';
	endpath++;

        /* read in the directory and sort */
        dircount = scandir(name, &dirlist, 0, cramsort);

	if (dircount < 0) {
		perror(name);
		exit(8);
	}

	/* process directory */
	for (dirindex = 0; dirindex < dircount; dirindex++) {
		struct dirent *dirent;
		struct entry *entry;
		struct stat st;
		int size;
		size_t namelen;

		dirent = dirlist[dirindex];

		/* Ignore "." and ".." - we won't be adding them to the archive */
		if (dirent->d_name[0] == '.') {
			if (dirent->d_name[1] == '\0')
				continue;
			if (dirent->d_name[1] == '.') {
				if (dirent->d_name[2] == '\0')
					continue;
			}
		}
		namelen = strlen(dirent->d_name);
		if (namelen > MAX_INPUT_NAMELEN) {
			fprintf(stderr,
				"Very long (%u bytes) filename `%s' found.\n"
				" Please increase MAX_INPUT_NAMELEN in mkcramfs.c and recompile.  Exiting.\n",
				namelen, dirent->d_name);
			exit(8);
		}
		memcpy(endpath, dirent->d_name, namelen + 1);

		if (lstat(path, &st) < 0) {
			perror(endpath);
			warn_skip = 1;
			continue;
		}
		entry = calloc(1, sizeof(struct entry));
		if (!entry) {
			perror(NULL);
			exit(8);
		}
		entry->name = strdup(dirent->d_name);
		if (!entry->name) {
			perror(NULL);
			exit(8);
		}
		if (namelen > 255) {
			/* Can't happen when reading from ext2fs. */

			/* TODO: we ought to avoid chopping in half
			   multi-byte UTF8 characters. */
			entry->name[namelen = 255] = '\0';
			warn_namelen = 1;
		}
		entry->mode = st.st_mode;
		entry->size = st.st_size;
		entry->uid = opt_squash ? 0 : st.st_uid;
		if (entry->uid >= 1 << CRAMFS_UID_WIDTH)
			warn_uid = 1;
		entry->gid = opt_squash ? 0 : st.st_gid;
		if (entry->gid >= 1 << CRAMFS_GID_WIDTH)
			/* TODO: We ought to replace with a default
                           gid instead of truncating; otherwise there
                           are security problems.  Maybe mode should
                           be &= ~070.  Same goes for uid once Linux
                           supports >16-bit uids. */
			warn_gid = 1;
		size = sizeof(struct cramfs_inode) + ((namelen + 3) & ~3);
		*fslen_ub += size;
		if (S_ISDIR(st.st_mode)) {
			entry->size = parse_directory(root_entry, path, &entry->child, fslen_ub);
		} else if (S_ISREG(st.st_mode)) {
			/* TODO: We ought to open files in do_compress, one
			   at a time, instead of amassing all these memory
			   maps during parse_directory (which don't get used
			   until do_compress anyway).  As it is, we tend to
			   get EMFILE errors (especially if mkcramfs is run
			   by non-root).

			   While we're at it, do analagously for symlinks
			   (which would just save a little memory). */
			int fd = open(path, O_RDONLY);
			if (fd < 0) {
				perror(path);
				warn_skip = 1;
				continue;
			}
			if (entry->size) {
				if ((entry->size >= 1 << CRAMFS_SIZE_WIDTH)) {
					warn_size = 1;
					entry->size = (1 << CRAMFS_SIZE_WIDTH) - 1;
				}

				entry->uncompressed = mmap(NULL, entry->size, PROT_READ, MAP_PRIVATE, fd, 0);
				if (-1 == (int) (long) entry->uncompressed) {
					perror("mmap");
					exit(8);
				}
			}
			close(fd);
		} else if (S_ISLNK(st.st_mode)) {
			entry->uncompressed = malloc(entry->size);
			if (!entry->uncompressed) {
				perror(NULL);
				exit(8);
			}
			if (readlink(path, entry->uncompressed, entry->size) < 0) {
				perror(path);
				warn_skip = 1;
				continue;
			}
		} else if (S_ISFIFO(st.st_mode) || S_ISSOCK(st.st_mode)) {
			/* maybe we should skip sockets */
			entry->size = 0;
		} else {
			entry->size = st.st_rdev;
			if (entry->size & -(1<<CRAMFS_SIZE_WIDTH))
				warn_dev = 1;
		}

		if (S_ISREG(st.st_mode) || S_ISLNK(st.st_mode)) {
			int blocks = ((entry->size - 1) / blksize + 1);

			/* block pointers & data expansion allowance + data */
			if(entry->size)
				*fslen_ub += (4+26)*blocks + entry->size + 3;
                }

		/* Link it into the list */
		*prev = entry;
		prev = &entry->next;
		totalsize += size;
	}
	free(path);
	free(dirlist);		/* allocated by scandir() with malloc() */
	return totalsize;
}

/* Returns sizeof(struct cramfs_super), which includes the root inode. */
static unsigned int write_superblock(struct entry *root, char *base, int size)
{
	struct cramfs_super *super = (struct cramfs_super *) base;
	unsigned int offset = sizeof(struct cramfs_super) + image_length;

	if (opt_pad) {
		offset += opt_pad;
	}

	super->magic = CRAMFS_MAGIC;
	super->flags = CRAMFS_FLAG_FSID_VERSION_2 | CRAMFS_FLAG_SORTED_DIRS;
	if (opt_holes)
		super->flags |= CRAMFS_FLAG_HOLES;
	if (image_length > 0)
		super->flags |= CRAMFS_FLAG_SHIFTED_ROOT_OFFSET;
	super->size = size;
	memcpy(super->signature, CRAMFS_SIGNATURE, sizeof(super->signature));

	super->fsid.crc = crc32(0L, Z_NULL, 0);
	super->fsid.edition = opt_edition;
	super->fsid.blocks = total_blocks;
	super->fsid.files = total_nodes;

	memset(super->name, 0x00, sizeof(super->name));
	if (opt_name)
		strncpy(super->name, opt_name, sizeof(super->name));
	else
		strncpy(super->name, "Compressed", sizeof(super->name));

	super->root.mode = root->mode;
	super->root.uid = root->uid;
	super->root.gid = root->gid;
	super->root.size = root->size;
	super->root.offset = offset >> 2;

	return offset;
}

static void set_data_offset(struct entry *entry, char *base, unsigned long offset)
{
	struct cramfs_inode *inode = (struct cramfs_inode *) (base + entry->dir_offset);
#ifdef DEBUG
	assert ((offset & 3) == 0);
#endif /* DEBUG */
	if (offset >= (1 << (2 + CRAMFS_OFFSET_WIDTH))) {
		fprintf(stderr, "filesystem too big.  Exiting.\n");
		exit(8);
	}
	inode->offset = (offset >> 2);
}


/*
 * We do a width-first printout of the directory
 * entries, using a stack to remember the directories
 * we've seen.
 */
#define MAXENTRIES (100)
static unsigned int write_directory_structure(struct entry *entry, char *base, unsigned int offset)
{
	int stack_entries = 0;
	struct entry *entry_stack[MAXENTRIES];

	for (;;) {
		int dir_start = stack_entries;
		while (entry) {
			struct cramfs_inode *inode = (struct cramfs_inode *) (base + offset);
			size_t len = strlen(entry->name);

			entry->dir_offset = offset;

			inode->mode = entry->mode;
			inode->uid = entry->uid;
			inode->gid = entry->gid;
			inode->size = entry->size;
			inode->offset = 0;
			/* Non-empty directories, regfiles and symlinks will
			   write over inode->offset later. */

			offset += sizeof(struct cramfs_inode);
			total_nodes++;	/* another node */
			memcpy(base + offset, entry->name, len);
			/* Pad up the name to a 4-byte boundary */
			while (len & 3) {
				*(base + offset + len) = '\0';
				len++;
			}
			inode->namelen = len >> 2;
			offset += len;

			/* TODO: this may get it wrong for chars >= 0x80.
			   Most filesystems use UTF8 encoding for filenames,
			   whereas the console is a single-byte character
			   set like iso-latin-1. */
			printf("  %s\n", entry->name);
			if (entry->child) {
				if (stack_entries >= MAXENTRIES) {
					fprintf(stderr, "Exceeded MAXENTRIES.  Raise this value in mkcramfs.c and recompile.  Exiting.\n");
					exit(8);
				}
				entry_stack[stack_entries] = entry;
				stack_entries++;
			}
			entry = entry->next;
		}

		/*
		 * Reverse the order the stack entries pushed during
                 * this directory, for a small optimization of disk
                 * access in the created fs.  This change makes things
                 * `ls -UR' order.
		 */
		{
			struct entry **lo = entry_stack + dir_start;
			struct entry **hi = entry_stack + stack_entries;
			struct entry *tmp;

			while (lo < --hi) {
				tmp = *lo;
				*lo++ = *hi;
				*hi = tmp;
			}
		}

		/* Pop a subdirectory entry from the stack, and recurse. */
		if (!stack_entries)
			break;
		stack_entries--;
		entry = entry_stack[stack_entries];

		set_data_offset(entry, base, offset);
		printf("'%s':\n", entry->name);
		entry = entry->child;
	}
	return offset;
}

static int is_zero(char const *begin, unsigned len)
{
	if (opt_holes)
		/* Returns non-zero iff the first LEN bytes from BEGIN are
		   all NULs. */
		return (len-- == 0 ||
			(begin[0] == '\0' &&
			 (len-- == 0 ||
			  (begin[1] == '\0' &&
			   (len-- == 0 ||
			    (begin[2] == '\0' &&
			     (len-- == 0 ||
			      (begin[3] == '\0' &&
			       memcmp(begin, begin + 4, len) == 0))))))));
	else
		/* Never create holes. */
		return 0;
}

/*
 * One 4-byte pointer per block and then the actual blocked
 * output. The first block does not need an offset pointer,
 * as it will start immediately after the pointer block;
 * so the i'th pointer points to the end of the i'th block
 * (i.e. the start of the (i+1)'th block or past EOF).
 *
 * Note that size > 0, as a zero-sized file wouldn't ever
 * have gotten here in the first place.
 */
static unsigned int do_compress(char *base, unsigned int offset, char const *name, char *uncompressed, unsigned int size)
{
	unsigned long original_size = size;
	unsigned long original_offset = offset;
	unsigned long new_size;
	unsigned long blocks = (size - 1) / blksize + 1;
	unsigned long curr = offset + 4 * blocks;
	int change;

	total_blocks += blocks; 

	do {
		unsigned long len = 2 * blksize;
		unsigned int input = size;
		if (input > blksize)
			input = blksize;
		size -= input;
		if (!is_zero (uncompressed, input)) {
			compress(base + curr, &len, uncompressed, input);
			curr += len;
		}
		uncompressed += input;

		if (len > blksize*2) {
			/* (I don't think this can happen with zlib.) */
			printf("AIEEE: block \"compressed\" to > 2*blocklength (%ld)\n", len);
			exit(8);
		}

		*(u32 *) (base + offset) = curr;
		offset += 4;
	} while (size);

	curr = (curr + 3) & ~3;
	new_size = curr - original_offset;
	/* TODO: Arguably, original_size in these 2 lines should be
	   st_blocks * 512.  But if you say that then perhaps
	   administrative data should also be included in both. */
	change = new_size - original_size;
	printf("%6.2f%% (%+d bytes)\t%s\n",
	       (change * 100) / (double) original_size, change, name);

	return curr;
}


/*
 * Traverse the entry tree, writing data for every item that has
 * non-null entry->compressed (i.e. every symlink and non-empty
 * regfile).
 */
static unsigned int write_data(struct entry *entry, char *base, unsigned int offset)
{
	do {
		if (entry->uncompressed) {
                        if(entry->same) {
                                set_data_offset(entry, base, entry->same->offset);
                                entry->offset=entry->same->offset;
                        } else {
                                set_data_offset(entry, base, offset);
                                entry->offset=offset;
                                offset = do_compress(base, offset, entry->name, entry->uncompressed, entry->size);
                        }
		}
		else if (entry->child)
			offset = write_data(entry->child, base, offset);
                entry=entry->next;
	} while (entry);
	return offset;
}

static unsigned int write_file(char *file, char *base, unsigned int offset)
{
	int fd;
	char *buf;

	fd = open(file, O_RDONLY);
	if (fd < 0) {
		perror(file);
		exit(8);
	}
	buf = mmap(NULL, image_length, PROT_READ, MAP_PRIVATE, fd, 0);
	memcpy(base + offset, buf, image_length);
	munmap(buf, image_length);
	close (fd);
	/* Pad up the image_length to a 4-byte boundary */
	while (image_length & 3) {
		*(base + offset + image_length) = '\0';
		image_length++;
	}
	return (offset + image_length);
}

struct entry *find_entry_in_dir(char *name, struct entry *dir)
{
	struct entry *curr = dir->child;
	
	while (curr && (strcmp(name, curr->name) > 0))
		curr = curr->next;
	if (curr && !strcmp(name, curr->name)) return curr;
	return NULL;
}
	
struct entry *find_entry(char *full, struct entry *root)
{
	struct entry *entry;
	char *name = full, *rest = NULL;
	if (strchr(full, '/')) {
		rest = strchr(full, '/') + 1;
		rest[-1] = '\0';
	}
	if ((entry = find_entry_in_dir(name, root))) {
		if (rest)
			return find_entry(rest, entry);
		else return entry;
	}
	return NULL;
}

void modify_entry(char *full_path, unsigned long uid, unsigned long gid, 
	unsigned long mode, unsigned long rdev, struct entry *root, loff_t *fslen_ub)
{
	char *name, *path, *full;
	struct entry *curr, *parent, *entry, *prev;
	
	full = strdup(full_path);
	if (strrchr(full, '/')) {
		name = strrchr(full, '/') + 1;
		name[-1] = '\0';
		path = full;
		if (!(parent = find_entry(path, root)))
			error_msg_and_die("%s/%s: could not find parent\n", full_path, name);
	} else {
		parent = root;
		name = full;
	}
	if ((entry = find_entry_in_dir(name, parent))) {
		/* its there, just modify permissions */
		entry->mode = mode;
		entry->uid = uid;
		entry->gid = gid;
	} else { /* make a new entry */
	
		size_t namelen;
		/* FIXME: replicated code */
		if (mode & S_IFREG)
			error_msg_and_die("%s: is not in the tree\n", full_path);
	
		namelen = strlen(name);
		if (namelen > MAX_INPUT_NAMELEN) {
			fprintf(stderr,
				"Very long (%u bytes) filename `%s' found.\n"
				" Please increase MAX_INPUT_NAMELEN in mkcramfs.c and recompile.  Exiting.\n",
				namelen, name);
			exit(8);
		}

		entry = calloc(1, sizeof(struct entry));
		if (!entry) {
			perror(NULL);
			exit(8);
		}
		entry->name = strdup(name);
		if (!entry->name) {
			perror(NULL);
			exit(8);
		}
		if (namelen > 255) {
			/* Can't happen when reading from ext2fs. */

			/* TODO: we ought to avoid chopping in half
			   multi-byte UTF8 characters. */
			entry->name[namelen = 255] = '\0';
			warn_namelen = 1;
		}
		entry->mode = mode;
		if (mode & (S_IFCHR | S_IFBLK)) {
			entry->size = rdev;
			if (entry->size & -(1<<CRAMFS_SIZE_WIDTH))
				warn_dev = 1;
		} else entry->size = 0;
		entry->uid = uid;
		entry->gid = gid;
		
		/* ok, now we have to backup and correct the size of all the entry above us */
		*fslen_ub += sizeof(struct cramfs_inode) + ((namelen + 3) & ~3);
		parent->size += sizeof(struct cramfs_inode) + ((namelen + 3) & ~3);

		/* alright, time to link us in */
		curr = parent->child;
		prev = NULL;
		while (curr && strcmp(name, curr->name) > 0) {
			prev = curr;
			curr = curr->next;
		}
		if (!prev) parent->child = entry;
		else prev->next = entry;
		entry->next = curr;
		entry->child = NULL;
	}
	if (entry->uid >= 1 << CRAMFS_UID_WIDTH)
		warn_uid = 1;
	if (entry->gid >= 1 << CRAMFS_GID_WIDTH)
		/* TODO: We ought to replace with a default
                         gid instead of truncating; otherwise there
                         are security problems.  Maybe mode should
                         be &= ~070.  Same goes for uid once Linux
                         supports >16-bit uids. */
		warn_gid = 1;
	free(full);

}

/*  device table entries take the form of:
    <path>	<type> <mode>	<uid>	<gid>	<major>	<minor>	<start>	<inc>	<count>
    /dev/mem    c      640      0       0       1       1       0        0        -

    type can be one of: 
	f	A regular file
	d	Directory
	c	Character special device file
	b	Block special device file
	p	Fifo (named pipe)

    I don't bother with symlinks (permissions are irrelevant), hard
    links (special cases of regular files), or sockets (why bother).

    Regular files must exist in the target root directory.  If a char,
    block, fifo, or directory does not exist, it will be created.
*/
static int interpret_table_entry(char *line, struct entry *root, loff_t *fslen_ub)
{
	char *name;
	char path[BUFSIZ], type;
	unsigned long mode = 0755, uid = 0, gid = 0, major = 0, minor = 0;
	unsigned long start = 0, increment = 1, count = 0;

	if (0 > sscanf(line, "%40s %c %lo %lu %lu %lu %lu %lu %lu %lu", path,
		    &type, &mode, &uid, &gid, &major, &minor, &start,
		    &increment, &count)) 
	{
		return 1;
	}

	if (!strcmp(path, "/"))
		error_msg_and_die("Device table entries require absolute paths\n");

	name = xstrdup(path + 1);

	switch (type) {
	case 'd':
		mode |= S_IFDIR;
		modify_entry(name, uid, gid, mode, 0, root, fslen_ub);
		break;
	case 'f':
		mode |= S_IFREG;
		modify_entry(name, uid, gid, mode, 0, root, fslen_ub);
		break;
	case 'p':
		mode |= S_IFIFO;
		modify_entry(name, uid, gid, mode, 0, root, fslen_ub);
		break;
	case 'c':
	case 'b':
		mode |= (type == 'c') ? S_IFCHR : S_IFBLK;
		if (count > 0) {
			int i;
			dev_t rdev;
			char buf[80];

			for (i = start; i < count; i++) {
				sprintf(buf, "%s%d", name, i);
				/* FIXME:  MKDEV uses illicit insider knowledge of kernel 
				 * major/minor representation...  */
				rdev = MKDEV(major, minor + (i * increment - start));
				modify_entry(buf, uid, gid, mode, rdev, root, fslen_ub);
			}
		} else {
			/* FIXME:  MKDEV uses illicit insider knowledge of kernel 
			 * major/minor representation...  */
			dev_t rdev = MKDEV(major, minor);
			
			modify_entry(name, uid, gid, mode, rdev, root, fslen_ub);
		}
		break;
	default:
		error_msg_and_die("Unsupported file type");
	}
	free(name);
	return 0;
}


static int parse_device_table(FILE *file, struct entry *root, loff_t *fslen_ub)
{
	char *line;
	int status = 0;
	size_t length = 0;

	/* Looks ok so far.  The general plan now is to read in one
	 * line at a time, check for leading comment delimiters ('#'),
	 * then try and parse the line as a device table.  If we fail
	 * to parse things, try and help the poor fool to fix their
	 * device table with a useful error msg... */
	line = NULL;
	while (getline(&line, &length, file) != -1) {
		/* First trim off any whitespace */
		int len = strlen(line);

		/* trim trailing whitespace */
		while (len > 0 && isspace(line[len - 1]))
			line[--len] = '\0';
		/* trim leading whitespace */
		memmove(line, &line[strspn(line, " \n\r\t\v")], len);

		/* If this is NOT a comment line, try to interpret it */
		if (length && *line != '#') {
			if (interpret_table_entry(line, root, fslen_ub))
				status = 1;
		}

		free(line);
		line = NULL;
	}
	fclose(file);

	return status;
}

void traverse(struct entry *entry, int depth)
{
	struct entry *curr = entry;
	int i;

	while (curr) {
		for (i = 0; i < depth; i++) putchar(' ');
		printf("%s: size=%d mode=%d same=%p\n",
			curr->name ? curr->name : "/", 
			curr->size, curr->mode, curr->same);
		if (curr->child) traverse(curr->child, depth + 4);
		curr = curr->next;
	}
}


/*
 * Maximum size fs you can create is roughly 256MB.  (The last file's
 * data must begin within 256MB boundary but can extend beyond that.)
 *
 * Note that if you want it to fit in a ROM then you're limited to what the
 * hardware and kernel can support (64MB?).
 */
#define MAXFSLEN ((((1 << CRAMFS_OFFSET_WIDTH) - 1) << 2) /* offset */ \
		  + (1 << CRAMFS_SIZE_WIDTH) - 1 /* filesize */ \
		  + (1 << CRAMFS_SIZE_WIDTH) * 4 / PAGE_CACHE_SIZE /* block pointers */ )


/*
 * Usage:
 *
 *      mkcramfs directory-name outfile
 *
 * where "directory-name" is simply the root of the directory
 * tree that we want to generate a compressed filesystem out
 * of.
 */
int main(int argc, char **argv)
{
	struct stat st;		/* used twice... */
	struct entry *root_entry;
	char *rom_image;
	ssize_t offset, written;
	int fd;
	FILE *devtable = NULL;
	/* initial guess (upper-bound) of required filesystem size */
	loff_t fslen_ub = sizeof(struct cramfs_super);
	char const *dirname, *outfile;
	u32 crc = crc32(0L, Z_NULL, 0);
	int c;			/* for getopt */

	total_blocks = 0;

	if (argc)
		progname = argv[0];

	/* command line options */
	while ((c = getopt(argc, argv, "hD:Ee:i:n:pszq")) != EOF) {
		switch (c) {
		case 'h':
			usage(0);
		case 'D':
			devtable = xfopen(optarg, "r");
			if (fstat(fileno(devtable), &st) < 0)
				perror_msg_and_die(optarg);
			if (st.st_size < 10)
				error_msg_and_die("%s: not a proper device table file\n", optarg);
			break;
		case 'E':
			opt_errors = 1;
			break;
		case 'e':
			opt_edition = atoi(optarg);
			break;
		case 'i':
			opt_image = optarg;
			if (lstat(opt_image, &st) < 0) {
				perror(opt_image);
				exit(16);
			}
			image_length = st.st_size; /* may be padded later */
			fslen_ub += (image_length + 3); /* 3 is for padding */
			break;
		case 'n':
			opt_name = optarg;
			break;
		case 'p':
			opt_pad = PAD_SIZE;
			fslen_ub += PAD_SIZE;
			break;
		case 's':
			/* old option, ignored */
			break;
		case 'z':
			opt_holes = 1;
			break;
		case 'q':
			opt_squash = 1;
			break;
		}
	}

	if ((argc - optind) != 2)
		usage(16);
	dirname = argv[optind];
	outfile = argv[optind + 1];

	if (stat(dirname, &st) < 0) {
		perror(dirname);
		exit(16);
	}
	fd = open(outfile, O_WRONLY | O_CREAT | O_TRUNC, 0666);

	root_entry = calloc(1, sizeof(struct entry));
	if (!root_entry) {
		perror(NULL);
		exit(8);
	}
	root_entry->mode = st.st_mode;
	root_entry->uid = st.st_uid;
	root_entry->gid = st.st_gid;

	root_entry->size = parse_directory(root_entry, dirname, &root_entry->child, &fslen_ub);

	if (devtable) {
		parse_device_table(devtable, root_entry, &fslen_ub);
		fclose(devtable);
	}

	/* always allocate a multiple of blksize bytes because that's
           what we're going to write later on */
	fslen_ub = ((fslen_ub - 1) | (blksize - 1)) + 1;

	if (fslen_ub > MAXFSLEN) {
		fprintf(stderr,
			"warning: guestimate of required size (upper bound) is %LdMB, but maximum image size is %uMB.  We might die prematurely.\n",
			fslen_ub >> 20,
			MAXFSLEN >> 20);
		fslen_ub = MAXFSLEN;
	}

        /* find duplicate files. TODO: uses the most inefficient algorithm
           possible. */
        eliminate_doubles(root_entry,root_entry);

	/* TODO: Why do we use a private/anonymous mapping here
           followed by a write below, instead of just a shared mapping
           and a couple of ftruncate calls?  Is it just to save us
           having to deal with removing the file afterwards?  If we
           really need this huge anonymous mapping, we ought to mmap
           in smaller chunks, so that the user doesn't need nn MB of
           RAM free.  If the reason is to be able to write to
           un-mmappable block devices, then we could try shared mmap
           and revert to anonymous mmap if the shared mmap fails. */
	rom_image = mmap(NULL, fslen_ub?fslen_ub:1, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

	if (-1 == (int) (long) rom_image) {
		perror("ROM image map");
		exit(8);
	}

	/* Skip the first opt_pad bytes for boot loader code */
	offset = opt_pad;
	memset(rom_image, 0x00, opt_pad);

	/* Skip the superblock and come back to write it later. */
	offset += sizeof(struct cramfs_super);

	/* Insert a file image. */
	if (opt_image) {
		printf("Including: %s\n", opt_image);
		offset = write_file(opt_image, rom_image, offset);
	}

	offset = write_directory_structure(root_entry->child, rom_image, offset);
	printf("Directory data: %d bytes\n", offset);

	offset = write_data(root_entry, rom_image, offset);

	/* We always write a multiple of blksize bytes, so that
           losetup works. */
	offset = ((offset - 1) | (blksize - 1)) + 1;
	printf("Everything: %d kilobytes\n", offset >> 10);

	/* Write the superblock now that we can fill in all of the fields. */
	write_superblock(root_entry, rom_image+opt_pad, offset);
	printf("Super block: %d bytes\n", sizeof(struct cramfs_super));

	/* Put the checksum in. */
	crc = crc32(crc, (rom_image+opt_pad), (offset-opt_pad));
	((struct cramfs_super *) (rom_image+opt_pad))->fsid.crc = crc;
	printf("CRC: %x\n", crc);

	/* Check to make sure we allocated enough space. */
	if (fslen_ub < offset) {
		fprintf(stderr, "not enough space allocated for ROM image (%Ld allocated, %d used)\n",
			fslen_ub, offset);
		exit(8);
	}

	written = write(fd, rom_image, offset);
	if (written < 0) {
		perror("ROM image");
		exit(8);
	}
	if (offset != written) {
		fprintf(stderr, "ROM image write failed (%d %d)\n", written, offset);
		exit(8);
	}

	/* traverse(root_entry, 0); */
	/* (These warnings used to come at the start, but they scroll off the
           screen too quickly.) */
	if (warn_namelen) /* (can't happen when reading from ext2fs) */
		fprintf(stderr, /* bytes, not chars: think UTF8. */
			"warning: filenames truncated to 255 bytes.\n");
	if (warn_skip)
		fprintf(stderr, "warning: files were skipped due to errors.\n");
	if (warn_size)
		fprintf(stderr,
			"warning: file sizes truncated to %luMB (minus 1 byte).\n",
			1L << (CRAMFS_SIZE_WIDTH - 20));
	if (warn_uid) /* (not possible with current Linux versions) */
		fprintf(stderr,
			"warning: uids truncated to %u bits.  (This may be a security concern.)\n",
			CRAMFS_UID_WIDTH);
	if (warn_gid)
		fprintf(stderr,
			"warning: gids truncated to %u bits.  (This may be a security concern.)\n",
			CRAMFS_GID_WIDTH);
	if (warn_dev)
		fprintf(stderr,
			"WARNING: device numbers truncated to %u bits.  This almost certainly means\n"
			"that some device files will be wrong.\n",
			CRAMFS_OFFSET_WIDTH);
	if (opt_errors &&
	    (warn_namelen||warn_skip||warn_size||warn_uid||warn_gid||warn_dev))
		exit(8);
	return 0;
}

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Nick Bane]

The modifications I made to bootldr (CRL bootloader as used in iPaq
handhelds) were trivial after mkysffsimage was fixed (ask for a copy as the
CVS one is still badly broken).

Bootldr copies the data 512+16 bytes at a time into non-broken NAND. The
kernel is then booted with prior knowledge as to where to find the YAFFS
data and all is ok.

How this works with DOC I am unclear as I had noticed a while back that
there was hardware assisted ECC. This might get in the way of YAFFS ECC but
maybe this can be circumvented.

Nick Bane

----- Original Message -----
From: "Charles Manning" <manningc2@actrix.gen.nz>
To: "Marc Singer" <elf@buici.com>
Cc: <linux-mtd@lists.infradead.org>; <yaffs@toby-churchill.org>
Sent: Tuesday, September 24, 2002 4:58 AM
Subject: Re: Interest in DOC and YAFFS? --> YAFFS bootloading


> On Tue, 24 Sep 2002 15:44, Marc Singer wrote:
> > On Tue, Sep 24, 2002 at 12:03:45PM +1200, Charles Manning wrote:
> > > Hi
> > >
> > > I'm considering getting YAFFS working on DOC. I'm trying to gauge
> > > interest to prioritise vs other things.
> > >
> > > If you don't know what YAFFS is, it's a NAND-specific journalling
> > > file system. Ask Google for more info.
> > >
> > > Currently YAFFS works with raw NAND (using software ecc), though
> > > some people have patched it to use hardware ecc, so I figure DOC
> > > support should be relatively simple.
> >
> > Do you know how it boots?  Does grub support it?
>
> By "it" I assume you mean YAFFS.
>
> Doing a yaffs-specific bootloader is pretty simple. We have discussed the
> general approach  on the YAFFS list before. At least two people have done
> yaffs bootloaders. One of these might be rolled in with grub. Maybe
someone
> else on the yaffs list can answer that.
>
>
> --------------------------------------------------------------------------
-------------
> This mailing list is hosted by Toby Churchill open software
(www.toby-churchill.org).
> If mailing list membership is no longer wanted you can remove yourself
from the list by
> sending an email to yaffs-request@toby-churchill.org with the text
"unsubscribe"
> (without the quotes) as the subject.
>
>

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Marc Singer]

On Tue, Sep 24, 2002 at 08:23:06AM +0100, Nick Bane wrote:
> The modifications I made to bootldr (CRL bootloader as used in iPaq
> handhelds) were trivial after mkysffsimage was fixed (ask for a copy as the
> CVS one is still badly broken).
> 
> Bootldr copies the data 512+16 bytes at a time into non-broken NAND. The
> kernel is then booted with prior knowledge as to where to find the YAFFS
> data and all is ok.

What is non-broken NAND?

> How this works with DOC I am unclear as I had noticed a while back that
> there was hardware assisted ECC. This might get in the way of YAFFS ECC but
> maybe this can be circumvented.

As far as I can tell, the hardware ECC just makes the DOC faster.
Also, I think that Microsys has released information about how to use
the hardware ECC.

Re: Interest in DOC and YAFFS? --> YAFFS bootloading

[Nick Bane]

> On Tue, Sep 24, 2002 at 08:23:06AM +0100, Nick Bane wrote:
> > The modifications I made to bootldr (CRL bootloader as used in iPaq
> > handhelds) were trivial after mkysffsimage was fixed (ask for a copy as
the
> > CVS one is still badly broken).
> >
> > Bootldr copies the data 512+16 bytes at a time into non-broken NAND. The
> > kernel is then booted with prior knowledge as to where to find the YAFFS
> > data and all is ok.
>
> What is non-broken NAND?
>
NAND is not guarranteed 100% working. Individual pages may break. This
renders the whole erase block (a collection of pages) unusable. The
tradition is to mark the block as broken by clearing more than one bit in
certain bytes of the oob (spare) data on each page. Non-broken NAND is where
this oob data is marked as valid - typically 0xff.

> > How this works with DOC I am unclear as I had noticed a while back that
> > there was hardware assisted ECC. This might get in the way of YAFFS ECC
but
> > maybe this can be circumvented.
>
> As far as I can tell, the hardware ECC just makes the DOC faster.
Umm. It may use some of the oob data area for its own ECC in a YAFFS
incompatible way. I am not sure of my ground here, only that you need to
check it out.

> Also, I think that Microsys has released information about how to use
> the hardware ECC.
>
Ok.

Nick

>

Re: Interest in DOC and YAFFS?

[Charles Manning]

> > > How this works with DOC I am unclear as I had noticed a while back that
> > > there was hardware assisted ECC. This might get in the way of YAFFS ECC
>
> but
>
> > > maybe this can be circumvented.
> >
> > As far as I can tell, the hardware ECC just makes the DOC faster.
>
> Umm. It may use some of the oob data area for its own ECC in a YAFFS
> incompatible way. I am not sure of my ground here, only that you need to
> check it out.
>
> > Also, I think that Microsys has released information about how to use
> > the hardware ECC.
>
> Ok.

Determining, then straightening out, OOB conflicts is essetially what DOC 
support boils down to.

As far as I am aware, the ECC does not actually impact on the NAND and works 
something like as follows.
* As you write bytes to the NAND buffer, an ECC is calculated on the side in 
the ASIC.
* You can then read ASIC registers to determine the ECC.

Essentially you can just ignore the ECC and see raw NAND chips, ie the ECC is 
non-intrusive.

Thus, the current YAFFS page programming would change from something like:

* Calculate ecc. + tags and format up OOB (spare)
* Write data + oob
* Program page

to:

* Write data
* Read ECC from ASIC
* Format up and write oob.
* Program page

Essentially, the hw ecc saves the ecc calcs - that's all.

Christian Gan has implemented a hw ecc scheme which I think is like above in 
YAFFS, so I suspect DOC support might almost be done :-).

-- Charles

RE: Interest in DOC and YAFFS?

[Christian Gan]

Hello all,

I heard my name being mentioned so I thought to respond :)

Currently I do have an implementation of HW_ECC for nand working.  Most of
the structure is already in the NAND mtd.  Our NAND is connected through a
custom FPGA that does the ECC for us.

The current breakdown is this:

1. YAFFS calls write_page in the MTD.  write_page fills the page and the HW
ECC data in OOB where YAFFS expects it to be (using custom enable_hwecc and
calc_ecc).
2. YAFFS calls write_oob for the tag data, however the ECC bytes are filled
with 0xff so that it doesn't corrupt the ECC already written by the MTD.
i.e. my CalcECC function in YAFFS just writes 0xff.
3. When YAFFS verifies the tag data, the ECC bytes are skipped since YAFFS
will not know what they are supposed to be.

Problems with this is that Steps 1 and 2 need to be combined to once write
call, otherwise we may blow the specs of some NANDs for max writes to OOBs.

Verbose version of things needed to make HW ECC work with YAFFS:

MTD Changes:
============
- the nand_chip struct has a pointer to a function for enable_hwecc, you'll
have to create your own function depending on your system and have the
structure point to it.  The mtd calls this function to reset the HW ECC on
the NAND device.  So it gets called once in the beginning of a page and
again at the 256 byte mark.
- calculate_ecc has to be changed so that it now reads the registers
containing the calculated ECC in HW.
- the problem with this implementation is that YAFFS needs a NAND MTD that
allows it to write the page and OOB at the same time.  Here's a snipped of
email I wrote on the YAFFS mailing list earlier:

"A further problem I have to think about now is the max number of allowable
writes in the OOB.  Some NANDs allow for three writes but there are some
who's maxes are speced for two.  Which means that in my case:

  1 write to OOB by the MTD when writing a page (for HW ECC).
  1 write to OOB by YAFFS for tags.
  1 write to OOB by YAFFS to mark pages deleted.
  = 3 writes
which of course would violate some NAND specs..."

- Finally, the current MTD uses the OOB to write the ECCs and also a "valid
ECC" byte.  YAFFS tags has no room for the valid ECC byte in the OOB so I
had to ignore it, which is not exactly ideal.  The byte location that the
MTD writes to the OOB for ECC also must be changed (by defining the ecc_pos
in the oob config).

YAFFS Changes:
==============
- Remove any instance where YAFFS tries to read / write ECC.  i.e. when
YAFFS writes it's tags, have it write 0xff for the ECC bytes.  Don't verify
the ECC in the tag/oob area in VerifyCompare and don't try to correct data
in ReadChunkFromNand.
- I'm working on getting Charles this code so that he can put in a NO_ECC
macro of some sort.

> -----Original Message-----
> From: Charles Manning [mailto:manningc2@actrix.gen.nz]
> Sent: Tuesday, September 24, 2002 3:54 PM
> To: Nick Bane; Marc Singer
> Cc: linux-mtd@lists.infradead.org; yaffs@toby-churchill.org
> Subject: Re: Interest in DOC and YAFFS?
>
>
>
> > > > How this works with DOC I am unclear as I had noticed a
> while back that
> > > > there was hardware assisted ECC. This might get in the way
> of YAFFS ECC
> >
> > but
> >
> > > > maybe this can be circumvented.
> > >
> > > As far as I can tell, the hardware ECC just makes the DOC faster.
> >
> > Umm. It may use some of the oob data area for its own ECC in a YAFFS
> > incompatible way. I am not sure of my ground here, only that you need to
> > check it out.
> >
> > > Also, I think that Microsys has released information about how to use
> > > the hardware ECC.
> >
> > Ok.
>
> Determining, then straightening out, OOB conflicts is essetially what DOC
> support boils down to.
>
> As far as I am aware, the ECC does not actually impact on the
> NAND and works
> something like as follows.
> * As you write bytes to the NAND buffer, an ECC is calculated on
> the side in
> the ASIC.
> * You can then read ASIC registers to determine the ECC.
>
> Essentially you can just ignore the ECC and see raw NAND chips,
> ie the ECC is
> non-intrusive.
>
> Thus, the current YAFFS page programming would change from something like:
>
> * Calculate ecc. + tags and format up OOB (spare)
> * Write data + oob
> * Program page
>
> to:
>
> * Write data
> * Read ECC from ASIC
> * Format up and write oob.
> * Program page
>
> Essentially, the hw ecc saves the ecc calcs - that's all.
>
> Christian Gan has implemented a hw ecc scheme which I think is
> like above in
> YAFFS, so I suspect DOC support might almost be done :-).
>
> -- Charles
>
>
> ------------------------------------------------------------------
> ---------------------
> This mailing list is hosted by Toby Churchill open software
(www.toby-churchill.org).
If mailing list membership is no longer wanted you can remove yourself from
the list by
sending an email to yaffs-request@toby-churchill.org with the text
"unsubscribe"
(without the quotes) as the subject.

Re: Interest in DOC and YAFFS?

[Thomas Gleixner]

On Wednesday 25 September 2002 00:46, Christian Gan wrote:
> MTD Changes:
> ============
> - Finally, the current MTD uses the OOB to write the ECCs and also a "valid
> ECC" byte.  YAFFS tags has no room for the valid ECC byte in the OOB so I
> had to ignore it, which is not exactly ideal.  The byte location that the
> MTD writes to the OOB for ECC also must be changed (by defining the ecc_pos
> in the oob config).
The current nand.c in MTD CVS supports not longer a ECC-valid byte.

Further changes:
Use buffered read/write only for non pagealigned access, speed up the
aligned path by using the filesystem-buffer.

Reset chip removed from nand_select(), implicit done only, when erase is
interrupted 

waitfuntion use yield, instead of schedule_timeout

support for 6byte/512byte hardware ECC

read_ecc, write_ecc extended for different oob-layout selections: 
Implemented NAND_NONE_OOB, NAND_JFFS2_OOB, NAND_YAFFS_OOB. 
fs-driver gives one of these constants to select the oob-layout fitting
the filesystem.I have added int oobsel as parameter to each function.
oobdata can be read together with the raw data, when the fs-driver
supplies a big enough buffer. 
size = 12 * number of pages to read (256B pagesize) 
       24 * number of pages to read (512B pagesize)
The buffer contains 8/16 byte oobdata and 4/8 byte returncode from
correct_ecc
oobbuf [0-15] oob-data 1st read page 
oobbuf [16-19] return code from correct_ecc byte 0-255
oobbuf [20-23] return code from correct_ecc byte 256-511
oobbuf [24-39] oob-data 2nd read page
oobbuf [40-31] return code from correct_ecc byte 0-255
.....
The returnvalue of read_ecc is -EIO, if any correct_ecc returned -1. But
retlen is equal to the requested length, so fs-driver can decide what to
do.

oobdata can be given from filesystem to program them in one go together
with the raw data. ECC codes are filled in at the place selected by
oobsel.
This supports multipage programming. 
oobbuf[0-15] 1st page to write
oobbuf[16-31] 2nd page to write
ECC is filled in at the selected place.

I hope these changes are a good compromise for YAFFS folks. In this way
we enable YAFFS support and do not break anything. And you have HW-ECC
support out of the box. Maybe the multipage write/read is useful for you
too.

It's not the maximum speedup, which could be done with a YAFFS-specific
layer, but it enables people to use YAFFS and JFFS2 on the same machine,
even on the same flash chip. 

I started already to write a DOC hardware driver, but at the moment it's 
stucked, because I have to do some paid work :). It's not a really big 
problem to write a DOC driver  for nand.c now.

-- 
Thomas
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de