5 static int bucklook(u8int *score, int type, u8int *data, int n);
6 static int writebucket(ISect *is, u32int buck, IBucket *ib, DBlock *b);
7 static int okibucket(IBucket *ib, ISect *is);
8 static ISect *initisect1(ISect *is);
10 //static QLock indexlock; //ZZZ
12 static char IndexMagic[] = "venti index configuration";
15 initindex(char *name, ISect **sects, int n)
20 u32int last, blocksize, tabsize;
24 seterr(EOk, "no index sections to initialize index");
29 seterr(EOk, "can't initialize index: out of memory");
34 tabsize = sects[0]->tabsize;
35 if(partifile(&f, sects[0]->part, sects[0]->tabbase, tabsize) < 0)
37 if(parseindex(&f, ix) < 0){
43 if(namecmp(ix->name, name) != 0){
44 seterr(ECorrupt, "mismatched index name: found %s expected %s", ix->name, name);
48 seterr(ECorrupt, "mismatched number index sections: found %d expected %d", n, ix->nsects);
54 blocksize = ix->blocksize;
55 for(i = 0; i < ix->nsects; i++){
57 if(namecmp(ix->name, is->index) != 0
58 || is->blocksize != blocksize
59 || is->tabsize != tabsize
60 || namecmp(is->name, ix->smap[i].name) != 0
61 || is->start != ix->smap[i].start
62 || is->stop != ix->smap[i].stop
64 || is->start > is->stop){
65 seterr(ECorrupt, "inconsistent index sections in %s", ix->name);
71 ix->tabsize = tabsize;
74 ix->div = (((u64int)1 << 32) + last - 1) / last;
75 last = (((u64int)1 << 32) - 1) / ix->div + 1;
76 if(last != ix->buckets){
77 seterr(ECorrupt, "inconsistent math for buckets in %s", ix->name);
82 ix->arenas = MKNZ(Arena*, ix->narenas);
83 if(maparenas(ix->amap, ix->arenas, ix->narenas, ix->name) < 0){
98 seterr(EOk, "no sections in index %s", ix->name);
101 b = alloczblock(ix->tabsize, 1);
103 seterr(EOk, "can't write index configuration: out of memory");
107 if(outputindex(&f, ix) < 0){
108 seterr(EOk, "can't make index configuration: table storage too small %d", ix->tabsize);
112 for(i = 0; i < ix->nsects; i++){
113 if(writepart(ix->sects[i]->part, ix->sects[i]->tabbase, b->data, ix->tabsize) < 0){
114 seterr(EOk, "can't write index: %r");
121 for(i = 0; i < ix->nsects; i++)
122 if(wbisect(ix->sects[i]) < 0)
129 * index: IndexMagic '\n' version '\n' name '\n' blocksize '\n' sections arenas
130 * version, blocksize: u32int
131 * name: max. ANameSize string
132 * sections, arenas: AMap
135 outputindex(Fmt *f, Index *ix)
137 if(fmtprint(f, "%s\n%ud\n%s\n%ud\n", IndexMagic, ix->version, ix->name, ix->blocksize) < 0
138 || outputamap(f, ix->smap, ix->nsects) < 0
139 || outputamap(f, ix->amap, ix->narenas) < 0)
145 parseindex(IFile *f, Index *ix)
155 if(s == nil || strcmp(s, IndexMagic) != 0){
156 seterr(ECorrupt, "bad index magic for %s", f->name);
163 if(ifileu32int(f, &v) < 0){
164 seterr(ECorrupt, "syntax error: bad version number in %s", f->name);
168 if(ix->version != IndexVersion){
169 seterr(ECorrupt, "bad version number in %s", f->name);
176 if(ifilename(f, ix->name) < 0){
177 seterr(ECorrupt, "syntax error: bad index name in %s", f->name);
184 if(ifileu32int(f, &v) < 0){
185 seterr(ECorrupt, "syntax error: bad version number in %s", f->name);
190 if(parseamap(f, &amn) < 0)
195 if(parseamap(f, &amn) < 0)
204 * initialize an entirely new index
207 newindex(char *name, ISect **sects, int n)
212 u32int div, ub, xb, start, stop, blocksize, tabsize;
216 seterr(EOk, "creating index with no index sections");
221 * compute the total buckets available in the index,
222 * and the total buckets which are used.
225 blocksize = sects[0]->blocksize;
226 tabsize = sects[0]->tabsize;
227 for(i = 0; i < n; i++){
228 if(sects[i]->start != 0 || sects[i]->stop != 0
229 || sects[i]->index[0] != '\0'){
230 seterr(EOk, "creating new index using non-empty section %s", sects[i]->name);
233 if(blocksize != sects[i]->blocksize){
234 seterr(EOk, "mismatched block sizes in index sections");
237 if(tabsize != sects[i]->tabsize){
238 seterr(EOk, "mismatched config table sizes in index sections");
241 nb += sects[i]->blocks;
245 * check for duplicate names
247 for(i = 0; i < n; i++){
248 for(j = i + 1; j < n; j++){
249 if(namecmp(sects[i]->name, sects[j]->name) == 0){
250 seterr(EOk, "duplicate section name %s for index %s", sects[i]->name, name);
256 if(nb >= ((u64int)1 << 32)){
257 seterr(EBug, "index too large");
260 div = (((u64int)1 << 32) + nb - 1) / nb;
261 ub = (((u64int)1 << 32) - 1) / div + 1;
263 seterr(EBug, "index divisor too coarse");
267 seterr(EBug, "index initialization math wrong");
272 * initialize each of the index sections
273 * and the section map table
275 smap = MKNZ(AMap, n);
277 seterr(EOk, "can't create new index: out of memory");
282 for(i = 0; i < n; i++){
283 stop = start + sects[i]->blocks - xb / n;
286 sects[i]->start = start;
287 sects[i]->stop = stop;
288 namecp(sects[i]->index, name);
290 smap[i].start = start;
292 namecp(smap[i].name, sects[i]->name);
297 * initialize the index itself
301 seterr(EOk, "can't create new index: out of memory");
305 ix->version = IndexVersion;
306 namecp(ix->name, name);
310 ix->blocksize = blocksize;
313 ix->tabsize = tabsize;
318 initisect(Part *part)
324 b = alloczblock(HeadSize, 0);
325 if(b == nil || readpart(part, PartBlank, b->data, HeadSize) < 0){
326 seterr(EAdmin, "can't read index section header: %r");
336 ok = unpackisect(is, b->data);
339 seterr(ECorrupt, "corrupted index section header: %r");
344 if(is->version != ISectVersion){
345 seterr(EAdmin, "unknown index section version %d", is->version);
350 return initisect1(is);
354 newisect(Part *part, char *name, u32int blocksize, u32int tabsize)
363 namecp(is->name, name);
364 is->version = ISectVersion;
366 is->blocksize = blocksize;
369 tabbase = (PartBlank + HeadSize + blocksize - 1) & ~(blocksize - 1);
370 is->blockbase = (tabbase + tabsize + blocksize - 1) & ~(blocksize - 1);
371 is->blocks = is->part->size / blocksize - is->blockbase / blocksize;
381 * initialize the computed paramaters for an index
384 initisect1(ISect *is)
388 is->buckmax = (is->blocksize - IBucketSize) / IEntrySize;
389 is->blocklog = u64log2(is->blocksize);
390 if(is->blocksize != (1 << is->blocklog)){
391 seterr(ECorrupt, "illegal non-power-of-2 bucket size %d\n", is->blocksize);
395 partblocksize(is->part, is->blocksize);
396 is->tabbase = (PartBlank + HeadSize + is->blocksize - 1) & ~(is->blocksize - 1);
397 if(is->tabbase >= is->blockbase){
398 seterr(ECorrupt, "index section config table overlaps bucket storage");
402 is->tabsize = is->blockbase - is->tabbase;
403 v = is->part->size & ~(u64int)(is->blocksize - 1);
404 if(is->blockbase + (u64int)is->blocks * is->blocksize != v){
405 seterr(ECorrupt, "invalid blocks in index section %s", is->name);
411 if(is->stop - is->start > is->blocks){
412 seterr(ECorrupt, "index section overflows available space");
416 if(is->start > is->stop){
417 seterr(ECorrupt, "invalid index section range");
430 b = alloczblock(HeadSize, 1);
435 if(packisect(is, b->data) < 0){
436 seterr(ECorrupt, "can't make index section header: %r");
440 if(writepart(is->part, PartBlank, b->data, HeadSize) < 0){
441 seterr(EAdmin, "can't write index section header: %r");
468 for(i = 0; i < ix->nsects; i++)
469 freeisect(ix->sects[i]);
476 * write a clump to an available arena in the index
477 * and return the address of the clump within the index.
478 ZZZ question: should this distinguish between an arena
479 filling up and real errors writing the clump?
482 writeiclump(Index *ix, Clump *c, u8int *clbuf)
487 for(i = ix->mapalloc; i < ix->narenas; i++){
488 a = writeaclump(ix->arenas[i], c, clbuf);
490 return a + ix->amap[i].start;
493 seterr(EAdmin, "no space left in arenas");
498 * convert an arena index to an relative address address
501 amapitoa(Index *ix, u64int a, u64int *aa)
509 if(ix->amap[m].start <= a)
516 if(a > ix->amap[l].stop){
517 for(i=0; i<ix->narenas; i++)
518 print("arena %d: %llux - %llux\n", i, ix->amap[i].start, ix->amap[i].stop);
519 print("want arena %d for %llux\n", l, a);
520 seterr(ECrash, "unmapped address passed to amapitoa");
524 if(ix->arenas[l] == nil){
525 seterr(ECrash, "unmapped arena selected in amapitoa");
528 *aa = a - ix->amap[l].start;
529 return ix->arenas[l];
533 iaddrcmp(IAddr *ia1, IAddr *ia2)
535 return ia1->type != ia2->type
536 || ia1->size != ia2->size
537 || ia1->blocks != ia2->blocks
538 || ia1->addr != ia2->addr;
542 * lookup the score in the partition
544 * nothing needs to be explicitly locked:
545 * only static parts of ix are used, and
546 * the bucket is locked by the DBlock lock.
549 loadientry(Index *ix, u8int *score, int type, IEntry *ie)
557 fprint(2, "loadientry %V %d\n", score, type);
558 buck = hashbits(score, 32) / ix->div;
563 qunlock(&stats.lock);
564 is = findisect(ix, buck);
566 seterr(EAdmin, "bad math in loadientry");
570 b = getdblock(is->part, is->blockbase + ((u64int)buck << is->blocklog), 1);
574 unpackibucket(&ib, b->data);
575 if(okibucket(&ib, is) < 0)
578 h = bucklook(score, type, ib.data, ib.n);
581 unpackientry(ie, &ib.data[h]);
593 * insert or update an index entry into the appropriate bucket
596 storeientry(Index *ix, IEntry *ie)
604 buck = hashbits(ie->score, 32) / ix->div;
609 qunlock(&stats.lock);
610 is = findisect(ix, buck);
612 seterr(EAdmin, "bad math in storeientry");
616 b = getdblock(is->part, is->blockbase + ((u64int)buck << is->blocklog), 1);
620 unpackibucket(&ib, b->data);
621 if(okibucket(&ib, is) < 0)
624 h = bucklook(ie->score, ie->ia.type, ib.data, ib.n);
627 packientry(ie, &ib.data[h]);
628 ok = writebucket(is, buck, &ib, b);
632 if(ib.n < is->buckmax){
633 memmove(&ib.data[h + IEntrySize], &ib.data[h], ib.n * IEntrySize - h);
636 packientry(ie, &ib.data[h]);
637 ok = writebucket(is, buck, &ib, b);
649 writebucket(ISect *is, u32int buck, IBucket *ib, DBlock *b)
651 if(buck >= is->blocks)
652 seterr(EAdmin, "index write out of bounds: %d >= %d\n",
656 qunlock(&stats.lock);
657 packibucket(ib, b->data);
658 return writepart(is->part, is->blockbase + ((u64int)buck << is->blocklog), b->data, is->blocksize);
662 * find the number of the index section holding score
665 indexsect(Index *ix, u8int *score)
670 buck = hashbits(score, 32) / ix->div;
675 if(ix->sects[m]->start <= buck)
684 * find the index section which holds buck
687 findisect(Index *ix, u32int buck)
696 if(ix->sects[m]->start <= buck)
701 is = ix->sects[l - 1];
702 if(is->start <= buck && is->stop > buck)
708 okibucket(IBucket *ib, ISect *is)
710 if(ib->n <= is->buckmax && (ib->next == 0 || ib->next >= is->start && ib->next < is->stop))
713 seterr(EICorrupt, "corrupted disk index bucket: n=%ud max=%ud, next=%lud range=[%lud,%lud)",
714 ib->n, is->buckmax, ib->next, is->start, is->stop);
719 * look for score within data;
720 * return 1 | byte index of matching index,
721 * or 0 | index of least element > score
724 bucklook(u8int *score, int otype, u8int *data, int n)
726 int i, r, l, m, h, c, cc, type;
728 type = vttodisktype(otype);
729 fprint(2, "bucklook %V %d->%d %d\n", score, otype, type, n);
735 fprint(2, "perhaps %V %d\n", data+h, data[h+IEntryTypeOff]);
736 for(i = 0; i < VtScoreSize; i++){
747 cc = data[h + IEntryTypeOff];
759 return l * IEntrySize;
763 * compare two IEntries; consistent with bucklook
766 ientrycmp(const void *vie1, const void *vie2)
773 for(i = 0; i < VtScoreSize; i++){
782 v1 = ie1[IEntryTypeOff];
783 v2 = ie2[IEntryTypeOff];