From: Greg Haerr <greg_at_censoft.com>
Date: Fri, 8 Nov 2002 08:37:58 -0700

Bjorn,
    I thought I'd send you some code that shows what an
implementation would look like using this buffer-cache idea.
Ultimately, I've realized that this requires some rewriting,
and I'm not sure you're interested in that. The benefits
are simpler code, though, for a filesystem that works for
all read/write/creat/open cases. In addition, for arbitary i/o,
the system uses buffers and buffers files in a superior fashion.
However, the approach is a bit different than your design.
I haven't yet added the optimized case for multi-sector
read/writes.

Let me know what you think of this. I'm doing it for fun,
but I'd certainly like to help Rockbox as well. All the
cacheoffset code, as well as fat_readwrite and
fat_seek, can be removed.

Another point - all code that uses "int" for sectors, clusters,
and positions should be changed to "unsigned long". Take
a look at the gcc -S output and you'll see huge differences
with code speed and size when an unsigned divide or modulo
is computed, versus a signed divide/modulo. I've started
this in this design, in case you're wondering.

Greg

[bio.h]
/* buffer flag bits*/
#define B_NEEDREAD 0x01 /* buffer doesn't contain disk data*/
#define B_DIRTY 0x02 /* buffer needs writing*/
#define B_FAT 0x04 /* buffer is FAT data*/
#define B_DIR 0x08 /* buffer is DIR data*/

#define NOSECTOR ((unsigned long)-1L) /* buffer available*/

struct buffer {
    int flags; /* buffer flags*/
    int lru; /* last accessed timestamp*/
    unsigned long sector; /* disk sector # of data*/
    unsigned char buf[SECTOR_SIZE]; /* buffer data*/
};

[bio.c]
static struct buffer buffers[MAX_BUFFERS];
static int timestamp;

void
initbuffers(void)
{
    struct buffer *bp;

    /* mark all buffers not used*/
    for (bp=buffers; bp<&buffers[MAX_BUFFERS]; ++bp)
        bp->sector = NOSECTOR;
}

/*
 * Write given buffer, return 0 on error.
 */
int
bwrite(struct buffer *bp)
{
    int err;

    DEBUGF("bwrite: sector 0x%x\n", bp->sector);
    err = ata_write_sectors(bp->sector+startsector, 1, bp->buf);
    if (err) {
        DEBUGF("bwrite: error #%d writing sector 0x%x\n", err, bp->sector);
        return 0;
    }
    bp->flags &= ~B_DIRTY;
    return 1;
}

/*
 * Assign a buffer for a given sector.
 */
struct buffer *
getbuf(unsigned long sector)
{
    struct buffer *bp;
    struct buffer *newbp = NULL;

    /* search for cached buffer*/
    for (bp=buffers; bp<&buffers[MAX_BUFFERS]; ++bp) {
        if (bp->sector == sector) {
            bp->lru = ++timestamp;
            return bp;
        }

        /* remember least recently used buffer*/
        if (!newbp || bp->lru < newbp->lru)
            newbp = bp;
    }

    /* not cached, write previous buffer contents*/
    if (newbp->flags & B_DIRTY) {
        if (!bwrite(newbp))
            return NULL;
    }
    
    /* assign new sector to buffer*/
    newbp->flags = B_NEEDREAD;
    newbp->sector = sector;
    newbp->lru = ++timestamp;
    return newbp;
}

/*
 * Read (if necessary) a sector and return a buffer pointer.
 */
struct buffer *
bread(unsigned long sector)
{
    struct buffer *bp;
    int err;

    bp = getbuf(sector);

    if (bp && (bp->flags & B_NEEDREAD)) {
        DEBUGF("bread: read sector 0x%x\n", bp->sector);
        err = ata_read_sectors(sector+startsector, 1, bp->buf);
        if (err) {
            DEBUGF("bread: error #%d reading sector 0x%x\n", err, bp->sector);
            bp->sector = NOSECTOR;
            return NULL;
        }
        bp->flags &= ~B_NEEDREAD;
    }

    return bp;
}

[file.c excerpt]
int
read(int fd, void *buf, int count)
{
    int nread = 0;
    unsigned long blk, offset;
    unsigned long n, left;
    unsigned long sector;
    struct filedesc *f = &openfiles[fd];
    struct buffer *bp;

    if (count == 0)
        return 0;

    do {
        left = f->size - f->fileoffset;
        if (left <= 0)
            break;
        blk = f->fileoffset >> 9;
        offset = f->fileoffset & 511;
        n = min(count, left);
        n = min(512-offset, n);
        if ((sector = fat_bmap(&f->fatfile, blk)) == 0)
            break;
        bp = bread(sector);
        if (!bp) {
            DEBUGF("read: failed reading sector %d\n", sector);
            errno = EIO;
            return -2;
        }
        memcpy(buf, bp->buf+offset, n);
        count -= n;
        nread += n;
        ((char *)buf) += n;
        f->fileoffset += n;
    } while (count != 0);

    return nread;
}

int
write(int fd, void *buf, int count)
{
    int nwritten = 0;
    unsigned long blk, offset;
    unsigned long n;
    unsigned long sector;
    struct filedesc *f = &openfiles[fd];
    struct buffer *bp;

    if (count == 0)
        return 0;

    do {
        blk = f->fileoffset >> 9;
        offset = f->fileoffset & 511;
        n = min(512-offset, count);
        if ((sector = fat_bmap(&f->fatfile, blk)) == 0)
            break; // FIXME: return error?
        if (n == 512)
            bp = getbuf(sector);
        else
            bp = bread(sector);
        if (!bp) {
            DEBUGF("write: failed reading sector %d\n", sector);
            errno = EIO;
            return -2;
        }
        memcpy(bp->buf+offset, buf, n);
        bp->flags |= B_DIRTY;
        count -= n;
        nwritten += n;
        ((char *)buf) += n;
        f->fileoffset += n;
        if (f->fileoffset > f->size)
            f->size = f->fileoffset;
    } while (count != 0);

    return nwritten;
}

// FIXME unsigned long
int
lseek(int fd, int offset, int whence)
{
    int pos;

    LDEBUGF("lseek(%d,%d,%d)\n",fd,offset,whence);

    if ( !openfiles[fd].busy ) {
        errno = EBADF;
        return -1;
    }

    switch ( whence ) {
        case SEEK_SET:
            pos = offset;
            break;

        case SEEK_CUR:
            pos = openfiles[fd].fileoffset + offset;
            break;

        case SEEK_END:
            pos = openfiles[fd].size + offset;
            break;

        default:
            errno = EINVAL;
            return -2;
    }

    if (pos > openfiles[fd].size) {
        errno = EINVAL;
        return -3;
    }

    openfiles[fd].fileoffset = pos;
    return pos;
}

[fat.c]
[remove fat_readwrite, fat_seek]
/*
 * Map a FAT file logical block number into a disk sector number.
 */
unsigned long
fat_bmap(struct fat_file *file, unsigned long blk)
{
    unsigned long cluster = file->firstcluster;
    unsigned long nextcluster;
    long clusternum, i;
    int sector, tmp;

    sector = blk % fat_bpb.bpb_secperclus;

    if (!cluster || blk >= fat_bpb.bpb_secperclus) {
        clusternum = blk / fat_bpb.bpb_secperclus;
        if (!cluster)
            ++clusternum;
        for (i=0; i<clusternum; ++i) {
            nextcluster = get_next_cluster(cluster);
            if (!nextcluster) {
                /* not found, must be writing*/
                nextcluster = next_write_cluster(file, cluster, &tmp);
                if (!nextcluster)
                    return 0;
            }
            cluster = nextcluster;
        }
    }

    /* save lastcluster for close time truncation*/
    file->lastcluster = cluster;

    // FIXME save clusternum and cluster here for speed
    return cluster2sec(cluster) + sector;
}
Received on 2002-11-08