| #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)&0xFF;(p)[1]=((v)>>16)&0xFF;(p)[2]=((v)>>8)&0xFF;(p)[3]=(v)&0xFF |
| #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 = vtmalloc(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)); |
| |
| werrstr(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: |
| werrstr(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(const void *s0, const void *s1) |
| { |
| MetaChunk *mc0, *mc1; |
| |
| mc0 = (MetaChunk*)s0; |
| mc1 = (MetaChunk*)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 = vtmalloc(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); |
| werrstr(EBadMeta); |
| vtfree(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){ |
| vtfree(mc); |
| return mb->buf + o; |
| } |
| o = mc[i].offset + mc[i].size; |
| } |
| |
| if(mb->maxsize - o >= n){ |
| vtfree(mc); |
| return mb->buf + o; |
| } |
| |
| /* compact and return off the end */ |
| mbCompact(mb, mc); |
| vtfree(mc); |
| |
| if(mb->maxsize - mb->size < n){ |
| werrstr(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"); |
| werrstr(EBadMeta); |
| deCleanup(dir); |
| return 0; |
| } |
| |
| void |
| deCleanup(DirEntry *dir) |
| { |
| vtfree(dir->elem); |
| dir->elem = nil; |
| vtfree(dir->uid); |
| dir->uid = nil; |
| vtfree(dir->gid); |
| dir->gid = nil; |
| vtfree(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); |
| } |