Subversion Repositories planix.SVN

#include "stdinc.h"

typedef struct MetaChunk MetaChunk;

struct MetaChunk {
        ushort offset;
        ushort size;
        ushort index;
};

static int stringUnpack(char **s, uchar **p, int *n);
static int meCmp(MetaEntry*, char *s);
static int meCmpOld(MetaEntry*, char *s);



static char EBadMeta[] = "corrupted meta data";
static char ENoFile[] = "file does not exist";

/*
 * integer conversion routines
 */
#define U8GET(p)        ((p)[0])
#define U16GET(p)       (((p)[0]<<8)|(p)[1])
#define U32GET(p)       (((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
#define U48GET(p)       (((uvlong)U16GET(p)<<32)|(uvlong)U32GET((p)+2))
#define U64GET(p)       (((uvlong)U32GET(p)<<32)|(uvlong)U32GET((p)+4))

#define U8PUT(p,v)      (p)[0]=(v)
#define U16PUT(p,v)     (p)[0]=(v)>>8;(p)[1]=(v)
#define U32PUT(p,v)     (p)[0]=(v)>>24;(p)[1]=(v)>>16;(p)[2]=(v)>>8;(p)[3]=(v)
#define U48PUT(p,v,t32) t32=(v)>>32;U16PUT(p,t32);t32=(v);U32PUT((p)+2,t32)
#define U64PUT(p,v,t32) t32=(v)>>32;U32PUT(p,t32);t32=(v);U32PUT((p)+4,t32)

static int
stringUnpack(char **s, uchar **p, int *n)
{
        int nn;

        if(*n < 2)
                return 0;

        nn = U16GET(*p);
        *p += 2;
        *n -= 2;
        if(nn > *n)
                return 0;
        *s = vtMemAlloc(nn+1);
        memmove(*s, *p, nn);
        (*s)[nn] = 0;
        *p += nn;
        *n -= nn;
        return 1;
}

static int
stringPack(char *s, uchar *p)
{
        int n;

        n = strlen(s);
        U16PUT(p, n);
        memmove(p+2, s, n);
        return n+2;
}

int
mbSearch(MetaBlock *mb, char *elem, int *ri, MetaEntry *me)
{
        int i;
        int b, t, x;
if(0)fprint(2, "mbSearch %s\n", elem);

        /* binary search within block */
        b = 0;
        t = mb->nindex;
        while(b < t){
                i = (b+t)>>1;
                meUnpack(me, mb, i);

                if(mb->botch)
                        x = meCmpOld(me, elem);
                else
                        x = meCmp(me, elem);

                if(x == 0){
                        *ri = i;
                        return 1;
                }

                if(x < 0)
                        b = i+1;
                else /* x > 0 */
                        t = i;
        }

        assert(b == t);

        *ri = b;        /* b is the index to insert this entry */
        memset(me, 0, sizeof(*me));

        vtSetError(ENoFile);
        return 0;
}

void
mbInit(MetaBlock *mb, uchar *p, int n, int ne)
{
        memset(p, 0, n);
        mb->maxsize = n;
        mb->maxindex = ne;
        mb->nindex = 0;
        mb->free = 0;
        mb->size = MetaHeaderSize + ne*MetaIndexSize;
        mb->buf = p;
        mb->botch = 0;
}

int
mbUnpack(MetaBlock *mb, uchar *p, int n)
{
        u32int magic;
        int i;
        int eo, en, omin;
        uchar *q;

        mb->maxsize = n;
        mb->buf = p;

        if(n == 0){
                memset(mb, 0, sizeof(MetaBlock));
                return 1;
        }

        magic = U32GET(p);
        if(magic != MetaMagic && magic != MetaMagic-1)
                goto Err;
        mb->size = U16GET(p+4);
        mb->free = U16GET(p+6);
        mb->maxindex = U16GET(p+8);
        mb->nindex = U16GET(p+10);
        mb->botch = magic != MetaMagic;
        if(mb->size > n)
                goto Err;

        omin = MetaHeaderSize + mb->maxindex*MetaIndexSize;
        if(n < omin)
                goto Err;


        p += MetaHeaderSize;

        /* check the index table - ensures that meUnpack and meCmp never fail */
        for(i=0; i<mb->nindex; i++){
                eo = U16GET(p);
                en = U16GET(p+2);
                if(eo < omin || eo+en > mb->size || en < 8)
                        goto Err;
                q = mb->buf + eo;
                if(U32GET(q) != DirMagic)
                        goto Err;
                p += 4;
        }

        return 1;
Err:
        vtSetError(EBadMeta);
        return 0;
}


void
mbPack(MetaBlock *mb)
{
        uchar *p;

        p = mb->buf;

        assert(!mb->botch);

        U32PUT(p, MetaMagic);
        U16PUT(p+4, mb->size);
        U16PUT(p+6, mb->free);
        U16PUT(p+8, mb->maxindex);
        U16PUT(p+10, mb->nindex);
}


void
mbDelete(MetaBlock *mb, int i)
{
        uchar *p;
        int n;
        MetaEntry me;

        assert(i < mb->nindex);
        meUnpack(&me, mb, i);
        memset(me.p, 0, me.size);

        if(me.p - mb->buf + me.size == mb->size)
                mb->size -= me.size;
        else
                mb->free += me.size;

        p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
        n = (mb->nindex-i-1)*MetaIndexSize;
        memmove(p, p+MetaIndexSize, n);
        memset(p+n, 0, MetaIndexSize);
        mb->nindex--;
}

void
mbInsert(MetaBlock *mb, int i, MetaEntry *me)
{
        uchar *p;
        int o, n;

        assert(mb->nindex < mb->maxindex);

        o = me->p - mb->buf;
        n = me->size;
        if(o+n > mb->size){
                mb->free -= mb->size - o;
                mb->size = o + n;
        }else
                mb->free -= n;

        p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
        n = (mb->nindex-i)*MetaIndexSize;
        memmove(p+MetaIndexSize, p, n);
        U16PUT(p, me->p - mb->buf);
        U16PUT(p+2, me->size);
        mb->nindex++;
}

int
mbResize(MetaBlock *mb, MetaEntry *me, int n)
{
        uchar *p, *ep;

        /* easy case */
        if(n <= me->size){
                me->size = n;
                return 1;
        }

        /* try and expand entry */

        p = me->p + me->size;
        ep = mb->buf + mb->maxsize;
        while(p < ep && *p == 0)
                p++;
        if(n <= p - me->p){
                me->size = n;
                return 1;
        }

        p = mbAlloc(mb, n);
        if(p != nil){
                me->p = p;
                me->size = n;
                return 1;
        }

        return 0;
}

void
meUnpack(MetaEntry *me, MetaBlock *mb, int i)
{
        uchar *p;
        int eo, en;

        assert(i >= 0 && i < mb->nindex);

        p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
        eo = U16GET(p);
        en = U16GET(p+2);

        me->p = mb->buf + eo;
        me->size = en;

        /* checked by mbUnpack */
        assert(me->size >= 8);
}

/* assumes a small amount of checking has been done in mbEntry */
static int
meCmp(MetaEntry *me, char *s)
{
        int n;
        uchar *p;

        p = me->p;

        /* skip magic & version */
        p += 6;
        n = U16GET(p);
        p += 2;

        if(n > me->size - 8)
                n = me->size - 8;

        while(n > 0){
                if(*s == 0)
                        return 1;
                if(*p < (uchar)*s)
                        return -1;
                if(*p > (uchar)*s)
                        return 1;
                p++;
                s++;
                n--;
        }
        return -(*s != 0);
}

/*
 * This is the old and broken meCmp.
 * This cmp routine reverse the sense of the comparison
 * when one string is a prefix of the other.
 * In other words, it put "ab" after "abc" rather
 * than before.  This behaviour is ok; binary search
 * and sort still work.  However, it is goes against
 * the usual convention.
 */
static int
meCmpOld(MetaEntry *me, char *s)
{
        int n;
        uchar *p;

        p = me->p;

        /* skip magic & version */
        p += 6;
        n = U16GET(p);
        p += 2;

        if(n > me->size - 8)
                n = me->size - 8;

        while(n > 0){
                if(*s == 0)
                        return -1;
                if(*p < (uchar)*s)
                        return -1;
                if(*p > (uchar)*s)
                        return 1;
                p++;
                s++;
                n--;
        }
        return *s != 0;
}

static int
offsetCmp(void *s0, void *s1)
{
        MetaChunk *mc0, *mc1;

        mc0 = s0;
        mc1 = s1;
        if(mc0->offset < mc1->offset)
                return -1;
        if(mc0->offset > mc1->offset)
                return 1;
        return 0;
}

static MetaChunk *
metaChunks(MetaBlock *mb)
{
        MetaChunk *mc;
        int oo, o, n, i;
        uchar *p;

        mc = vtMemAlloc(mb->nindex*sizeof(MetaChunk));
        p = mb->buf + MetaHeaderSize;
        for(i = 0; i<mb->nindex; i++){
                mc[i].offset = U16GET(p);
                mc[i].size = U16GET(p+2);
                mc[i].index = i;
                p += MetaIndexSize;
        }

        qsort(mc, mb->nindex, sizeof(MetaChunk), offsetCmp);

        /* check block looks ok */
        oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
        o = oo;
        n = 0;
        for(i=0; i<mb->nindex; i++){
                o = mc[i].offset;
                n = mc[i].size;
                if(o < oo)
                        goto Err;
                oo += n;
        }
        if(o+n > mb->size)
                goto Err;
        if(mb->size - oo != mb->free)
                goto Err;

        return mc;
Err:
fprint(2, "metaChunks failed!\n");
oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
for(i=0; i<mb->nindex; i++){
fprint(2, "\t%d: %d %d\n", i, mc[i].offset, mc[i].offset + mc[i].size);
oo += mc[i].size;
}
fprint(2, "\tused=%d size=%d free=%d free2=%d\n", oo, mb->size, mb->free, mb->size - oo);
        vtSetError(EBadMeta);
        vtMemFree(mc);
        return nil;
}

static void
mbCompact(MetaBlock *mb, MetaChunk *mc)
{
        int oo, o, n, i;

        oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;

        for(i=0; i<mb->nindex; i++){
                o = mc[i].offset;
                n = mc[i].size;
                if(o != oo){
                        memmove(mb->buf + oo, mb->buf + o, n);
                        U16PUT(mb->buf + MetaHeaderSize + mc[i].index*MetaIndexSize, oo);
                }
                oo += n;
        }

        mb->size = oo;
        mb->free = 0;
}

uchar *
mbAlloc(MetaBlock *mb, int n)
{
        int i, o;
        MetaChunk *mc;

        /* off the end */
        if(mb->maxsize - mb->size >= n)
                return mb->buf + mb->size;

        /* check if possible */
        if(mb->maxsize - mb->size + mb->free < n)
                return nil;

        mc = metaChunks(mb);
        if(mc == nil){
fprint(2, "mbAlloc: metaChunks failed: %r\n");
                return nil;
        }

        /* look for hole */
        o = MetaHeaderSize + mb->maxindex*MetaIndexSize;
        for(i=0; i<mb->nindex; i++){
                if(mc[i].offset - o >= n){
                        vtMemFree(mc);
                        return mb->buf + o;
                }
                o = mc[i].offset + mc[i].size;
        }

        if(mb->maxsize - o >= n){
                vtMemFree(mc);
                return mb->buf + o;
        }

        /* compact and return off the end */
        mbCompact(mb, mc);
        vtMemFree(mc);

        if(mb->maxsize - mb->size < n){
                vtSetError(EBadMeta);
                return nil;
        }
        return mb->buf + mb->size;
}

int
deSize(DirEntry *dir)
{
        int n;

        /* constant part */

        n =     4 +     /* magic */
                2 +     /* version */
                4 +     /* entry */
                4 +     /* guid */
                4 +     /* mentry */
                4 +     /* mgen */
                8 +     /* qid */
                4 +     /* mtime */
                4 +     /* mcount */
                4 +     /* ctime */
                4 +     /* atime */
                4 +     /* mode */
                0;

        /* strings */
        n += 2 + strlen(dir->elem);
        n += 2 + strlen(dir->uid);
        n += 2 + strlen(dir->gid);
        n += 2 + strlen(dir->mid);

        /* optional sections */
        if(dir->qidSpace){
                n +=    3 +     /* option header */
                        8 +     /* qidOffset */
                        8;      /* qid Max */
        }

        return n;
}

void
dePack(DirEntry *dir, MetaEntry *me)
{
        uchar *p;
        ulong t32;

        p = me->p;

        U32PUT(p, DirMagic);
        U16PUT(p+4, 9);         /* version */
        p += 6;

        p += stringPack(dir->elem, p);

        U32PUT(p, dir->entry);
        U32PUT(p+4, dir->gen);
        U32PUT(p+8, dir->mentry);
        U32PUT(p+12, dir->mgen);
        U64PUT(p+16, dir->qid, t32);
        p += 24;

        p += stringPack(dir->uid, p);
        p += stringPack(dir->gid, p);
        p += stringPack(dir->mid, p);

        U32PUT(p, dir->mtime);
        U32PUT(p+4, dir->mcount);
        U32PUT(p+8, dir->ctime);
        U32PUT(p+12, dir->atime);
        U32PUT(p+16, dir->mode);
        p += 5*4;

        if(dir->qidSpace){
                U8PUT(p, DeQidSpace);
                U16PUT(p+1, 2*8);
                p += 3;
                U64PUT(p, dir->qidOffset, t32);
                U64PUT(p+8, dir->qidMax, t32);
                p += 16;
        }

        assert(p == me->p + me->size);
}


int
deUnpack(DirEntry *dir, MetaEntry *me)
{
        int t, nn, n, version;
        uchar *p;

        p = me->p;
        n = me->size;

        memset(dir, 0, sizeof(DirEntry));

if(0)print("deUnpack\n");
        /* magic */
        if(n < 4 || U32GET(p) != DirMagic)
                goto Err;
        p += 4;
        n -= 4;

if(0)print("deUnpack: got magic\n");
        /* version */
        if(n < 2)
                goto Err;
        version = U16GET(p);
        if(version < 7 || version > 9)
                goto Err;
        p += 2;
        n -= 2;

if(0)print("deUnpack: got version\n");

        /* elem */
        if(!stringUnpack(&dir->elem, &p, &n))
                goto Err;

if(0)print("deUnpack: got elem\n");

        /* entry  */
        if(n < 4)
                goto Err;
        dir->entry = U32GET(p);
        p += 4;
        n -= 4;

if(0)print("deUnpack: got entry\n");

        if(version < 9){
                dir->gen = 0;
                dir->mentry = dir->entry+1;
                dir->mgen = 0;
        }else{
                if(n < 3*4)
                        goto Err;
                dir->gen = U32GET(p);
                dir->mentry = U32GET(p+4);
                dir->mgen = U32GET(p+8);
                p += 3*4;
                n -= 3*4;
        }

if(0)print("deUnpack: got gen etc\n");

        /* size is gotten from VtEntry */
        dir->size = 0;

        /* qid */
        if(n < 8)
                goto Err;
        dir->qid = U64GET(p);
        p += 8;
        n -= 8;

if(0)print("deUnpack: got qid\n");
        /* skip replacement */
        if(version == 7){
                if(n < VtScoreSize)
                        goto Err;
                p += VtScoreSize;
                n -= VtScoreSize;
        }

        /* uid */
        if(!stringUnpack(&dir->uid, &p, &n))
                goto Err;

        /* gid */
        if(!stringUnpack(&dir->gid, &p, &n))
                goto Err;

        /* mid */
        if(!stringUnpack(&dir->mid, &p, &n))
                goto Err;

if(0)print("deUnpack: got ids\n");
        if(n < 5*4)
                goto Err;
        dir->mtime = U32GET(p);
        dir->mcount = U32GET(p+4);
        dir->ctime = U32GET(p+8);
        dir->atime = U32GET(p+12);
        dir->mode = U32GET(p+16);
        p += 5*4;
        n -= 5*4;

if(0)print("deUnpack: got times\n");
        /* optional meta data */
        while(n > 0){
                if(n < 3)
                        goto Err;
                t = p[0];
                nn = U16GET(p+1);
                p += 3;
                n -= 3;
                if(n < nn)
                        goto Err;
                switch(t){
                case DePlan9:
                        /* not valid in version >= 9 */
                        if(version >= 9)
                                break;
                        if(dir->plan9 || nn != 12)
                                goto Err;
                        dir->plan9 = 1;
                        dir->p9path = U64GET(p);
                        dir->p9version = U32GET(p+8);
                        if(dir->mcount == 0)
                                dir->mcount = dir->p9version;
                        break;
                case DeGen:
                        /* not valid in version >= 9 */
                        if(version >= 9)
                                break;
                        break;
                case DeQidSpace:
                        if(dir->qidSpace || nn != 16)
                                goto Err;
                        dir->qidSpace = 1;
                        dir->qidOffset = U64GET(p);
                        dir->qidMax = U64GET(p+8);
                        break;
                }
                p += nn;
                n -= nn;
        }
if(0)print("deUnpack: got options\n");

        if(p != me->p + me->size)
                goto Err;

if(0)print("deUnpack: correct size\n");
        return 1;
Err:
if(0)print("deUnpack: XXXXXXXXXXXX EBadMeta\n");
        vtSetError(EBadMeta);
        deCleanup(dir);
        return 0;
}

void
deCleanup(DirEntry *dir)
{
        vtMemFree(dir->elem);
        dir->elem = nil;
        vtMemFree(dir->uid);
        dir->uid = nil;
        vtMemFree(dir->gid);
        dir->gid = nil;
        vtMemFree(dir->mid);
        dir->mid = nil;
}

void
deCopy(DirEntry *dst, DirEntry *src)
{
        *dst = *src;
        dst->elem = vtStrDup(src->elem);
        dst->uid = vtStrDup(src->uid);
        dst->gid = vtStrDup(src->gid);
        dst->mid = vtStrDup(src->mid);
}