#include "stdinc.h"
#include "dat.h"
#include "fns.h"

static int      buckLook(u8int *score, int type, u8int *data, int n);
static int      writeBucket(ISect *is, u32int buck, IBucket *ib, DBlock *b);
static int      okIBucket(IBucket *ib, ISect *is);
static ISect    *initISect1(ISect *is);

static VtLock   *indexLock;     //ZZZ

static char     indexMagic[] = "venti index";

static char IndexMagic[] = "venti index configuration";

Index*
initIndex(char *name, ISect **sects, int n)
{
       IFile f;
       Index *ix;
       ISect *is;
       u32int last, blockSize, tabSize;
       int i;

       if(n <= 0){
               setErr(EOk, "no index sections to initialize index");
               return nil;
       }
       ix = MKZ(Index);
       if(ix == nil){
               setErr(EOk, "can't initialize index: out of memory");
               freeIndex(ix);
               return nil;
       }

       tabSize = sects[0]->tabSize;
       if(!partIFile(&f, sects[0]->part, sects[0]->tabBase, tabSize))
               return 0;
       if(!parseIndex(&f, ix)){
               freeIFile(&f);
               freeIndex(ix);
               return nil;
       }
       freeIFile(&f);
       if(!nameEq(ix->name, name)){
               setErr(ECorrupt, "mismatched index name: found %s expected %s", ix->name, name);
               return nil;
       }
       ix->sects = sects;
       if(ix->nsects != n){
               setErr(ECorrupt, "mismatched number index sections: found %d expected %d", n, ix->nsects);
               freeIndex(ix);
               return nil;
       }
       last = 0;
       blockSize = ix->blockSize;
       for(i = 0; i < ix->nsects; i++){
               is = sects[i];
               if(!nameEq(ix->name, is->index)
               || is->blockSize != blockSize
               || is->tabSize != tabSize
               || !nameEq(is->name, ix->smap[i].name)
               || is->start != ix->smap[i].start
               || is->stop != ix->smap[i].stop
               || last != is->start
               || is->start > is->stop){
                       setErr(ECorrupt, "inconsistent index sections in %s", ix->name);
                       freeIndex(ix);
                       return nil;
               }
               last = is->stop;
       }
       ix->tabSize = tabSize;
       ix->buckets = last;

       ix->div = (((u64int)1 << 32) + last - 1) / last;
       last = (((u64int)1 << 32) - 1) / ix->div + 1;
       if(last != ix->buckets){
               setErr(ECorrupt, "inconsistent math for buckets in %s", ix->name);
               freeIndex(ix);
               return nil;
       }

       ix->arenas = MKNZ(Arena*, ix->narenas);
       if(!mapArenas(ix->amap, ix->arenas, ix->narenas, ix->name)){
               freeIndex(ix);
               return nil;
       }
       return ix;
}

int
wbIndex(Index *ix)
{
       Fmt f;
       ZBlock *b;
       int i;

       if(ix->nsects == 0){
               setErr(EOk, "no sections in index %s", ix->name);
               return 0;
       }
       b = allocZBlock(ix->tabSize, 1);
       if(b == nil){
               setErr(EOk, "can't write index configuration: out of memory");
               return 0;
       }
       fmtZBInit(&f, b);
       if(!outputIndex(&f, ix)){
               setErr(EOk, "can't make index configuration: table storage too small %d", ix->tabSize);
               freeZBlock(b);
               return 0;
       }
       for(i = 0; i < ix->nsects; i++){
               if(!writePart(ix->sects[i]->part, ix->sects[i]->tabBase, b->data, ix->tabSize)){
                       setErr(EOk, "can't write index: %R");
                       freeZBlock(b);
                       return 0;
               }
       }
       freeZBlock(b);

       for(i = 0; i < ix->nsects; i++)
               if(!wbISect(ix->sects[i]))
                       return 0;

       return 1;
}

/*
* index: IndexMagic '\n' version '\n' name '\n' blockSize '\n' sections arenas
* version, blockSize: u32int
* name: max. ANameSize string
* sections, arenas: AMap
*/
int
outputIndex(Fmt *f, Index *ix)
{
       if(fmtprint(f, "%s\n%ud\n%s\n%ud\n", IndexMagic, ix->version, ix->name, ix->blockSize) < 0)
               return 0;
       return outputAMap(f, ix->smap, ix->nsects) && outputAMap(f, ix->amap, ix->narenas);
}

int
parseIndex(IFile *f, Index *ix)
{
       AMapN amn;
       u32int v;
       char *s;

       /*
        * magic
        */
       s = ifileLine(f);
       if(s == nil || strcmp(s, IndexMagic) != 0){
               setErr(ECorrupt, "bad index magic for %s", f->name);
               return 0;
       }

       /*
        * version
        */
       if(!ifileU32Int(f, &v)){
               setErr(ECorrupt, "syntax error: bad version number in %s", f->name);
               return 0;
       }
       ix->version = v;
       if(ix->version != IndexVersion){
               setErr(ECorrupt, "bad version number in %s", f->name);
               return 0;
       }

       /*
        * name
        */
       if(!ifileName(f, ix->name)){
               setErr(ECorrupt, "syntax error: bad index name in %s", f->name);
               return 0;
       }

       /*
        * block size
        */
       if(!ifileU32Int(f, &v)){
               setErr(ECorrupt, "syntax error: bad version number in %s", f->name);
               return 0;
       }
       ix->blockSize = v;

       if(!parseAMap(f, &amn))
               return 0;
       ix->nsects = amn.n;
       ix->smap = amn.map;

       if(!parseAMap(f, &amn))
               return 0;
       ix->narenas = amn.n;
       ix->amap = amn.map;

       return 1;
}

/*
* initialize an entirely new index
*/
Index *
newIndex(char *name, ISect **sects, int n)
{
       Index *ix;
       AMap *smap;
       u64int nb;
       u32int div, ub, xb, start, stop, blockSize, tabSize;
       int i, j;

       if(n < 1){
               setErr(EOk, "creating index with no index sections");
               return nil;
       }

       /*
        * compute the total buckets available in the index,
        * and the total buckets which are used.
        */
       nb = 0;
       blockSize = sects[0]->blockSize;
       tabSize = sects[0]->tabSize;
       for(i = 0; i < n; i++){
               if(sects[i]->start != 0 || sects[i]->stop != 0
               || sects[i]->index[0] != '\0'){
                       setErr(EOk, "creating new index using non-empty section %s", sects[i]->name);
                       return nil;
               }
               if(blockSize != sects[i]->blockSize){
                       setErr(EOk, "mismatched block sizes in index sections");
                       return nil;
               }
               if(tabSize != sects[i]->tabSize){
                       setErr(EOk, "mismatched config table sizes in index sections");
                       return nil;
               }
               nb += sects[i]->blocks;
       }

       /*
        * check for duplicate names
        */
       for(i = 0; i < n; i++){
               for(j = i + 1; j < n; j++){
                       if(nameEq(sects[i]->name, sects[j]->name)){
                               setErr(EOk, "duplicate section name %s for index %s", sects[i]->name, name);
                               return nil;
                       }
               }
       }

       if(nb >= ((u64int)1 << 32)){
               setErr(EBug, "index too large");
               return nil;
       }
       div = (((u64int)1 << 32) + nb - 1) / nb;
       ub = (((u64int)1 << 32) - 1) / div + 1;
       if(div < 100){
               setErr(EBug, "index divisor too coarse");
               return nil;
       }
       if(ub > nb){
               setErr(EBug, "index initialization math wrong");
               return nil;
       }

       /*
        * initialize each of the index sections
        * and the section map table
        */
       smap = MKNZ(AMap, n);
       if(smap == nil){
               setErr(EOk, "can't create new index: out of memory");
               return nil;
       }
       xb = nb - ub;
       start = 0;
       for(i = 0; i < n; i++){
               stop = start + sects[i]->blocks - xb / n;
               if(i == n - 1)
                       stop = ub;
               sects[i]->start = start;
               sects[i]->stop = stop;
               nameCp(sects[i]->index, name);

               smap[i].start = start;
               smap[i].stop = stop;
               nameCp(smap[i].name, sects[i]->name);
               start = stop;
       }

       /*
        * initialize the index itself
        */
       ix = MKZ(Index);
       if(ix == nil){
               setErr(EOk, "can't create new index: out of memory");
               free(smap);
               return nil;
       }
       ix->version = IndexVersion;
       nameCp(ix->name, name);
       ix->sects = sects;
       ix->smap = smap;
       ix->nsects = n;
       ix->blockSize = blockSize;
       ix->div = div;
       ix->buckets = ub;
       ix->tabSize = tabSize;
       return ix;
}

ISect*
initISect(Part *part)
{
       ISect *is;
       ZBlock *b;
       int ok;

       b = allocZBlock(HeadSize, 0);
       if(b == nil || !readPart(part, PartBlank, b->data, HeadSize)){
               setErr(EAdmin, "can't read index section header: %R");
               return nil;
       }

       is = MKZ(ISect);
       if(is == nil){
               freeZBlock(b);
               return nil;
       }
       is->part = part;
       ok = unpackISect(is, b->data);
       freeZBlock(b);
       if(!ok){
               setErr(ECorrupt, "corrupted index section header: %R");
               freeISect(is);
               return nil;
       }

       if(is->version != ISectVersion){
               setErr(EAdmin, "unknown index section version %d", is->version);
               freeISect(is);
               return nil;
       }

       return initISect1(is);
}

ISect*
newISect(Part *part, char *name, u32int blockSize, u32int tabSize)
{
       ISect *is;
       u32int tabBase;

       is = MKZ(ISect);
       if(is == nil)
               return nil;

       nameCp(is->name, name);
       is->version = ISectVersion;
       is->part = part;
       is->blockSize = blockSize;
       is->start = 0;
       is->stop = 0;
       tabBase = (PartBlank + HeadSize + blockSize - 1) & ~(blockSize - 1);
       is->blockBase = (tabBase + tabSize + blockSize - 1) & ~(blockSize - 1);
       is->blocks = is->part->size / blockSize - is->blockBase / blockSize;

       is = initISect1(is);
       if(is == nil)
               return nil;

       return is;
}

/*
* initialize the computed paramaters for an index
*/
static ISect*
initISect1(ISect *is)
{
       u64int v;

       is->buckMax = (is->blockSize - IBucketSize) / IEntrySize;
       is->blockLog = u64log2(is->blockSize);
       if(is->blockSize != (1 << is->blockLog)){
               setErr(ECorrupt, "illegal non-power-of-2 bucket size %d\n", is->blockSize);
               freeISect(is);
               return nil;
       }
       partBlockSize(is->part, is->blockSize);
       is->tabBase = (PartBlank + HeadSize + is->blockSize - 1) & ~(is->blockSize - 1);
       if(is->tabBase >= is->blockBase){
               setErr(ECorrupt, "index section config table overlaps bucket storage");
               freeISect(is);
               return nil;
       }
       is->tabSize = is->blockBase - is->tabBase;
       v = is->part->size & ~(u64int)(is->blockSize - 1);
       if(is->blockBase + (u64int)is->blocks * is->blockSize != v){
               setErr(ECorrupt, "invalid blocks in index section %s", is->name);
//ZZZZZZZZZ
//              freeISect(is);
//              return nil;
       }

       if(is->stop - is->start > is->blocks){
               setErr(ECorrupt, "index section overflows available space");
               freeISect(is);
               return nil;
       }
       if(is->start > is->stop){
               setErr(ECorrupt, "invalid index section range");
               freeISect(is);
               return nil;
       }

if(indexLock == nil)indexLock = vtLockAlloc();
       return is;
}

int
wbISect(ISect *is)
{
       ZBlock *b;

       b = allocZBlock(HeadSize, 1);
       if(b == nil)
//ZZZ set error?
               return 0;

       if(!packISect(is, b->data)){
               setErr(ECorrupt, "can't make index section header: %R");
               freeZBlock(b);
               return 0;
       }
       if(!writePart(is->part, PartBlank, b->data, HeadSize)){
               setErr(EAdmin, "can't write index section header: %R");
               freeZBlock(b);
               return 0;
       }
       freeZBlock(b);

       return 1;
}

void
freeISect(ISect *is)
{
       if(is == nil)
               return;
       free(is);
}

void
freeIndex(Index *ix)
{
       int i;

       if(ix == nil)
               return;
       free(ix->amap);
       free(ix->arenas);
       for(i = 0; i < ix->nsects; i++)
               freeISect(ix->sects[i]);
       free(ix->sects);
       free(ix->smap);
       free(ix);
}

/*
* write a clump to an available arena in the index
* and return the address of the clump within the index.
ZZZ question: should this distinguish between an arena
filling up and real errors writing the clump?
*/
u64int
writeIClump(Index *ix, Clump *c, u8int *clbuf)
{
       u64int a;
       int i;

       for(i = ix->mapAlloc; i < ix->narenas; i++){
               a = writeAClump(ix->arenas[i], c, clbuf);
               if(a != TWID64)
                       return a + ix->amap[i].start;
       }

       setErr(EAdmin, "no space left in arenas");
       return 0;
}

/*
* convert an arena index to an relative address address
*/
Arena*
amapItoA(Index *ix, u64int a, u64int *aa)
{
       int r, l, m;

       l = 1;
       r = ix->narenas - 1;
       while(l <= r){
               m = (r + l) / 2;
               if(ix->amap[m].start <= a)
                       l = m + 1;
               else
                       r = m - 1;
       }
       l--;

       if(a > ix->amap[l].stop){
               setErr(ECrash, "unmapped address passed to amapItoA");
               return nil;
       }

       if(ix->arenas[l] == nil){
               setErr(ECrash, "unmapped arena selected in amapItoA");
               return nil;
       }
       *aa = a - ix->amap[l].start;
       return ix->arenas[l];
}

int
iAddrEq(IAddr *ia1, IAddr *ia2)
{
       return ia1->type == ia2->type
               && ia1->size == ia2->size
               && ia1->blocks == ia2->blocks
               && ia1->addr == ia2->addr;
}

/*
* lookup the the score int the partition
*
* nothing needs to be explicitly locked:
* only static parts of ix are used, and
* the bucket is locked by the DBlock lock.
*/
int
loadIEntry(Index *ix, u8int *score, int type, IEntry *ie)
{
       ISect *is;
       DBlock *b;
       IBucket ib;
       u32int buck;
       int h, ok;

       buck = hashBits(score, 32) / ix->div;
       ok = 0;
       for(;;){
               vtLock(stats.lock);
               stats.indexReads++;
               vtUnlock(stats.lock);
               is = findISect(ix, buck);
               if(is == nil){
                       setErr(EAdmin, "bad math in loadIEntry");
                       return 0;
               }
               buck -= is->start;
               b = getDBlock(is->part, is->blockBase + ((u64int)buck << is->blockLog), 1);
               if(b == nil)
                       break;

               unpackIBucket(&ib, b->data);
               if(!okIBucket(&ib, is))
                       break;

               h = buckLook(score, type, ib.data, ib.n);
               if(h & 1){
                       h ^= 1;
                       unpackIEntry(ie, &ib.data[h]);
                       ok = 1;
                       break;
               }

               break;
       }
       putDBlock(b);
       return ok;
}

/*
* insert or update an index entry into the appropriate bucket
*/
int
storeIEntry(Index *ix, IEntry *ie)
{
       ISect *is;
       DBlock *b;
       IBucket ib;
       u32int buck;
       int h, ok;

       buck = hashBits(ie->score, 32) / ix->div;
       ok = 0;
       for(;;){
               vtLock(stats.lock);
               stats.indexWReads++;
               vtUnlock(stats.lock);
               is = findISect(ix, buck);
               if(is == nil){
                       setErr(EAdmin, "bad math in storeIEntry");
                       return 0;
               }
               buck -= is->start;
               b = getDBlock(is->part, is->blockBase + ((u64int)buck << is->blockLog), 1);
               if(b == nil)
                       break;

               unpackIBucket(&ib, b->data);
               if(!okIBucket(&ib, is))
                       break;

               h = buckLook(ie->score, ie->ia.type, ib.data, ib.n);
               if(h & 1){
                       h ^= 1;
                       packIEntry(ie, &ib.data[h]);
                       ok = writeBucket(is, buck, &ib, b);
                       break;
               }

               if(ib.n < is->buckMax){
                       memmove(&ib.data[h + IEntrySize], &ib.data[h], ib.n * IEntrySize - h);
                       ib.n++;

                       packIEntry(ie, &ib.data[h]);
                       ok = writeBucket(is, buck, &ib, b);
                       break;
               }

               break;
       }

       putDBlock(b);
       return ok;
}

static int
writeBucket(ISect *is, u32int buck, IBucket *ib, DBlock *b)
{
       if(buck >= is->blocks)
               setErr(EAdmin, "index write out of bounds: %d >= %d\n",
                               buck, is->blocks);
       vtLock(stats.lock);
       stats.indexWrites++;
       vtUnlock(stats.lock);
       packIBucket(ib, b->data);
       return writePart(is->part, is->blockBase + ((u64int)buck << is->blockLog), b->data, is->blockSize);
}

/*
* find the number of the index section holding score
*/
int
indexSect(Index *ix, u8int *score)
{
       u32int buck;
       int r, l, m;

       buck = hashBits(score, 32) / ix->div;
       l = 1;
       r = ix->nsects - 1;
       while(l <= r){
               m = (r + l) >> 1;
               if(ix->sects[m]->start <= buck)
                       l = m + 1;
               else
                       r = m - 1;
       }
       return l - 1;
}

/*
* find the index section which holds buck
*/
ISect*
findISect(Index *ix, u32int buck)
{
       ISect *is;
       int r, l, m;

       l = 1;
       r = ix->nsects - 1;
       while(l <= r){
               m = (r + l) >> 1;
               if(ix->sects[m]->start <= buck)
                       l = m + 1;
               else
                       r = m - 1;
       }
       is = ix->sects[l - 1];
       if(is->start <= buck && is->stop > buck)
               return is;
       return nil;
}

static int
okIBucket(IBucket *ib, ISect *is)
{
       if(ib->n <= is->buckMax && (ib->next == 0 || ib->next >= is->start && ib->next < is->stop))
               return 1;

       setErr(EICorrupt, "corrupted disk index bucket: n=%ud max=%ud, next=%lud range=[%lud,%lud)",
               ib->n, is->buckMax, ib->next, is->start, is->stop);
       return 0;
}

/*
* look for score within data;
* return 1 | byte index of matching index,
* or 0 | index of least element > score
*/
static int
buckLook(u8int *score, int type, u8int *data, int n)
{
       int i, r, l, m, h, c, cc;

       l = 0;
       r = n - 1;
       while(l <= r){
               m = (r + l) >> 1;
               h = m * IEntrySize;
               for(i = 0; i < VtScoreSize; i++){
                       c = score[i];
                       cc = data[h + i];
                       if(c != cc){
                               if(c > cc)
                                       l = m + 1;
                               else
                                       r = m - 1;
                               goto cont;
                       }
               }
               cc = data[h + IEntryTypeOff];
               if(type != cc){
                       if(type > cc)
                               l = m + 1;
                       else
                               r = m - 1;
                       goto cont;
               }
               return h | 1;
       cont:;
       }

       return l * IEntrySize;
}

/*
* compare two IEntries; consistent with buckLook
*/
int
ientryCmp(void *vie1, void *vie2)
{
       u8int *ie1, *ie2;
       int i, v1, v2;

       ie1 = vie1;
       ie2 = vie2;
       for(i = 0; i < VtScoreSize; i++){
               v1 = ie1[i];
               v2 = ie2[i];
               if(v1 != v2){
                       if(v1 < v2)
                               return -1;
                       return 1;
               }
       }
       v1 = ie1[IEntryTypeOff];
       v2 = ie2[IEntryTypeOff];
       if(v1 != v2){
               if(v1 < v2)
                       return -1;
               return 1;
       }
       return 0;
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.