1 a0d146ed 2005-07-12 devnull /*
  2 fa325e9b 2020-01-10 cross  * Index, mapping scores to log positions.
  3 a0d146ed 2005-07-12 devnull  *
  4 a0d146ed 2005-07-12 devnull  * The index is made up of some number of index sections, each of
  5 fa325e9b 2020-01-10 cross  * which is typically stored on a different disk.  The blocks in all the
  6 fa325e9b 2020-01-10 cross  * index sections are logically numbered, with each index section
  7 a0d146ed 2005-07-12 devnull  * responsible for a range of blocks.  Blocks are typically 8kB.
  8 a0d146ed 2005-07-12 devnull  *
  9 a0d146ed 2005-07-12 devnull  * The N index blocks are treated as a giant hash table.  The top 32 bits
 10 a0d146ed 2005-07-12 devnull  * of score are used as the key for a lookup.  Each index block holds
 11 a0d146ed 2005-07-12 devnull  * one hash bucket, which is responsible for ceil(2^32 / N) of the key space.
 12 fa325e9b 2020-01-10 cross  *
 13 fa325e9b 2020-01-10 cross  * The index is sized so that a particular bucket is extraordinarily
 14 fa325e9b 2020-01-10 cross  * unlikely to overflow: assuming compressed data blocks are 4kB
 15 a0d146ed 2005-07-12 devnull  * on disk, and assuming each block has a 40 byte index entry,
 16 a0d146ed 2005-07-12 devnull  * the index data will be 1% of the total data.  Since scores are essentially
 17 a0d146ed 2005-07-12 devnull  * random, all buckets should be about the same fullness.
 18 fa325e9b 2020-01-10 cross  * A factor of 5 gives us a wide comfort boundary to account for
 19 a0d146ed 2005-07-12 devnull  * random variation.  So the index disk space should be 5% of the arena disk space.
 20 a0d146ed 2005-07-12 devnull  */
 21 a0d146ed 2005-07-12 devnull 
 22 a0d146ed 2005-07-12 devnull #include "stdinc.h"
 23 a0d146ed 2005-07-12 devnull #include "dat.h"
 24 a0d146ed 2005-07-12 devnull #include "fns.h"
 25 a0d146ed 2005-07-12 devnull 
 26 a0d146ed 2005-07-12 devnull static int	initindex1(Index*);
 27 a0d146ed 2005-07-12 devnull static ISect	*initisect1(ISect *is);
 28 a0d146ed 2005-07-12 devnull 
 29 a0d146ed 2005-07-12 devnull #define KEY(k,d)	((d) ? (k)>>(32-(d)) : 0)
 30 a0d146ed 2005-07-12 devnull 
 31 a0d146ed 2005-07-12 devnull static char IndexMagic[] = "venti index configuration";
 32 a0d146ed 2005-07-12 devnull 
 33 a0d146ed 2005-07-12 devnull Index*
 34 a0d146ed 2005-07-12 devnull initindex(char *name, ISect **sects, int n)
 35 a0d146ed 2005-07-12 devnull {
 36 a0d146ed 2005-07-12 devnull 	IFile f;
 37 a0d146ed 2005-07-12 devnull 	Index *ix;
 38 a0d146ed 2005-07-12 devnull 	ISect *is;
 39 a0d146ed 2005-07-12 devnull 	u32int last, blocksize, tabsize;
 40 a0d146ed 2005-07-12 devnull 	int i;
 41 a0d146ed 2005-07-12 devnull 
 42 a0d146ed 2005-07-12 devnull 	if(n <= 0){
 43 a0d146ed 2005-07-12 devnull fprint(2, "bad n\n");
 44 a0d146ed 2005-07-12 devnull 		seterr(EOk, "no index sections to initialize index");
 45 a0d146ed 2005-07-12 devnull 		return nil;
 46 a0d146ed 2005-07-12 devnull 	}
 47 a0d146ed 2005-07-12 devnull 	ix = MKZ(Index);
 48 a0d146ed 2005-07-12 devnull 	if(ix == nil){
 49 a0d146ed 2005-07-12 devnull fprint(2, "no mem\n");
 50 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't initialize index: out of memory");
 51 a0d146ed 2005-07-12 devnull 		freeindex(ix);
 52 a0d146ed 2005-07-12 devnull 		return nil;
 53 a0d146ed 2005-07-12 devnull 	}
 54 a0d146ed 2005-07-12 devnull 
 55 a0d146ed 2005-07-12 devnull 	tabsize = sects[0]->tabsize;
 56 a0d146ed 2005-07-12 devnull 	if(partifile(&f, sects[0]->part, sects[0]->tabbase, tabsize) < 0)
 57 a0d146ed 2005-07-12 devnull 		return nil;
 58 a0d146ed 2005-07-12 devnull 	if(parseindex(&f, ix) < 0){
 59 a0d146ed 2005-07-12 devnull 		freeifile(&f);
 60 a0d146ed 2005-07-12 devnull 		freeindex(ix);
 61 a0d146ed 2005-07-12 devnull 		return nil;
 62 a0d146ed 2005-07-12 devnull 	}
 63 a0d146ed 2005-07-12 devnull 	freeifile(&f);
 64 a0d146ed 2005-07-12 devnull 	if(namecmp(ix->name, name) != 0){
 65 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "mismatched index name: found %s expected %s", ix->name, name);
 66 a0d146ed 2005-07-12 devnull 		return nil;
 67 a0d146ed 2005-07-12 devnull 	}
 68 a0d146ed 2005-07-12 devnull 	if(ix->nsects != n){
 69 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "mismatched number index sections: found %d expected %d", n, ix->nsects);
 70 a0d146ed 2005-07-12 devnull 		freeindex(ix);
 71 a0d146ed 2005-07-12 devnull 		return nil;
 72 a0d146ed 2005-07-12 devnull 	}
 73 a0d146ed 2005-07-12 devnull 	ix->sects = sects;
 74 a0d146ed 2005-07-12 devnull 	last = 0;
 75 a0d146ed 2005-07-12 devnull 	blocksize = ix->blocksize;
 76 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ix->nsects; i++){
 77 a0d146ed 2005-07-12 devnull 		is = sects[i];
 78 3b06b757 2008-12-23 rsc 		if(namecmp(is->index, ix->name) != 0) {
 79 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: index name is %s, not %s",
 80 3b06b757 2008-12-23 rsc 				sects[i]->part->name, is->index, ix->name);
 81 3b06b757 2008-12-23 rsc 		bad:
 82 a0d146ed 2005-07-12 devnull 			freeindex(ix);
 83 a0d146ed 2005-07-12 devnull 			return nil;
 84 a0d146ed 2005-07-12 devnull 		}
 85 3b06b757 2008-12-23 rsc 		if(is->blocksize != blocksize) {
 86 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: blocksize is %d, not %d",
 87 3b06b757 2008-12-23 rsc 				sects[i]->part->name, (int)is->blocksize, (int)blocksize);
 88 3b06b757 2008-12-23 rsc 			goto bad;
 89 3b06b757 2008-12-23 rsc 		}
 90 3b06b757 2008-12-23 rsc 		if(is->tabsize != tabsize) {
 91 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: tabsize is %d, not %d",
 92 3b06b757 2008-12-23 rsc 				sects[i]->part->name, (int)is->tabsize, (int)tabsize);
 93 3b06b757 2008-12-23 rsc 			goto bad;
 94 3b06b757 2008-12-23 rsc 		}
 95 3b06b757 2008-12-23 rsc 		if(namecmp(is->name, ix->smap[i].name) != 0) {
 96 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: name is %s, not %s",
 97 3b06b757 2008-12-23 rsc 				sects[i]->part->name, is->name, ix->smap[i].name);
 98 3b06b757 2008-12-23 rsc 			goto bad;
 99 3b06b757 2008-12-23 rsc 		}
100 3b06b757 2008-12-23 rsc 		if(is->start != ix->smap[i].start || is->stop != ix->smap[i].stop) {
101 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: range is %lld,%lld, not %lld,%lld",
102 3b06b757 2008-12-23 rsc 				sects[i]->part->name, is->start, is->stop,
103 3b06b757 2008-12-23 rsc 				ix->smap[i].start, ix->smap[i].stop);
104 3b06b757 2008-12-23 rsc 			goto bad;
105 3b06b757 2008-12-23 rsc 		}
106 3b06b757 2008-12-23 rsc 		if(is->start > is->stop) {
107 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: invalid range %lld,%lld",
108 3b06b757 2008-12-23 rsc 				sects[i]->part->name, is->start, is->stop);
109 3b06b757 2008-12-23 rsc 			goto bad;
110 3b06b757 2008-12-23 rsc 		}
111 3b06b757 2008-12-23 rsc 		if(is->start != last || is->start > is->stop) {
112 3b06b757 2008-12-23 rsc 			seterr(ECorrupt, "%s: range %lld-%lld, but last section ended at %lld",
113 3b06b757 2008-12-23 rsc 				sects[i]->part->name, is->start, is->stop, last);
114 3b06b757 2008-12-23 rsc 			goto bad;
115 3b06b757 2008-12-23 rsc 		}
116 a0d146ed 2005-07-12 devnull 		last = is->stop;
117 a0d146ed 2005-07-12 devnull 	}
118 a0d146ed 2005-07-12 devnull 	ix->tabsize = tabsize;
119 a0d146ed 2005-07-12 devnull 	ix->buckets = last;
120 a0d146ed 2005-07-12 devnull 
121 a0d146ed 2005-07-12 devnull 	if(initindex1(ix) < 0){
122 a0d146ed 2005-07-12 devnull 		freeindex(ix);
123 a0d146ed 2005-07-12 devnull 		return nil;
124 a0d146ed 2005-07-12 devnull 	}
125 a0d146ed 2005-07-12 devnull 
126 a0d146ed 2005-07-12 devnull 	ix->arenas = MKNZ(Arena*, ix->narenas);
127 a0d146ed 2005-07-12 devnull 	if(maparenas(ix->amap, ix->arenas, ix->narenas, ix->name) < 0){
128 a0d146ed 2005-07-12 devnull 		freeindex(ix);
129 a0d146ed 2005-07-12 devnull 		return nil;
130 a0d146ed 2005-07-12 devnull 	}
131 a0d146ed 2005-07-12 devnull 
132 a0d146ed 2005-07-12 devnull 	return ix;
133 a0d146ed 2005-07-12 devnull }
134 a0d146ed 2005-07-12 devnull 
135 a0d146ed 2005-07-12 devnull static int
136 a0d146ed 2005-07-12 devnull initindex1(Index *ix)
137 a0d146ed 2005-07-12 devnull {
138 a0d146ed 2005-07-12 devnull 	u32int buckets;
139 a0d146ed 2005-07-12 devnull 
140 a0d146ed 2005-07-12 devnull 	ix->div = (((u64int)1 << 32) + ix->buckets - 1) / ix->buckets;
141 a0d146ed 2005-07-12 devnull 	buckets = (((u64int)1 << 32) - 1) / ix->div + 1;
142 a0d146ed 2005-07-12 devnull 	if(buckets != ix->buckets){
143 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "inconsistent math for divisor and buckets in %s", ix->name);
144 a0d146ed 2005-07-12 devnull 		return -1;
145 a0d146ed 2005-07-12 devnull 	}
146 a0d146ed 2005-07-12 devnull 
147 a0d146ed 2005-07-12 devnull 	return 0;
148 a0d146ed 2005-07-12 devnull }
149 a0d146ed 2005-07-12 devnull 
150 a0d146ed 2005-07-12 devnull int
151 a0d146ed 2005-07-12 devnull wbindex(Index *ix)
152 a0d146ed 2005-07-12 devnull {
153 a0d146ed 2005-07-12 devnull 	Fmt f;
154 a0d146ed 2005-07-12 devnull 	ZBlock *b;
155 a0d146ed 2005-07-12 devnull 	int i;
156 a0d146ed 2005-07-12 devnull 
157 a0d146ed 2005-07-12 devnull 	if(ix->nsects == 0){
158 a0d146ed 2005-07-12 devnull 		seterr(EOk, "no sections in index %s", ix->name);
159 a0d146ed 2005-07-12 devnull 		return -1;
160 a0d146ed 2005-07-12 devnull 	}
161 a0d146ed 2005-07-12 devnull 	b = alloczblock(ix->tabsize, 1, ix->blocksize);
162 a0d146ed 2005-07-12 devnull 	if(b == nil){
163 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't write index configuration: out of memory");
164 a0d146ed 2005-07-12 devnull 		return -1;
165 a0d146ed 2005-07-12 devnull 	}
166 a0d146ed 2005-07-12 devnull 	fmtzbinit(&f, b);
167 a0d146ed 2005-07-12 devnull 	if(outputindex(&f, ix) < 0){
168 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't make index configuration: table storage too small %d", ix->tabsize);
169 a0d146ed 2005-07-12 devnull 		freezblock(b);
170 a0d146ed 2005-07-12 devnull 		return -1;
171 a0d146ed 2005-07-12 devnull 	}
172 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ix->nsects; i++){
173 e46cacb0 2007-04-27 devnull 		if(writepart(ix->sects[i]->part, ix->sects[i]->tabbase, b->data, ix->tabsize) < 0
174 e46cacb0 2007-04-27 devnull 		|| flushpart(ix->sects[i]->part) < 0){
175 a0d146ed 2005-07-12 devnull 			seterr(EOk, "can't write index: %r");
176 a0d146ed 2005-07-12 devnull 			freezblock(b);
177 a0d146ed 2005-07-12 devnull 			return -1;
178 a0d146ed 2005-07-12 devnull 		}
179 a0d146ed 2005-07-12 devnull 	}
180 a0d146ed 2005-07-12 devnull 	freezblock(b);
181 a0d146ed 2005-07-12 devnull 
182 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ix->nsects; i++)
183 a0d146ed 2005-07-12 devnull 		if(wbisect(ix->sects[i]) < 0)
184 a0d146ed 2005-07-12 devnull 			return -1;
185 a0d146ed 2005-07-12 devnull 
186 a0d146ed 2005-07-12 devnull 	return 0;
187 a0d146ed 2005-07-12 devnull }
188 a0d146ed 2005-07-12 devnull 
189 a0d146ed 2005-07-12 devnull /*
190 a0d146ed 2005-07-12 devnull  * index: IndexMagic '\n' version '\n' name '\n' blocksize '\n' [V2: bitblocks '\n'] sections arenas
191 a0d146ed 2005-07-12 devnull  * version, blocksize: u32int
192 a0d146ed 2005-07-12 devnull  * name: max. ANameSize string
193 a0d146ed 2005-07-12 devnull  * sections, arenas: AMap
194 a0d146ed 2005-07-12 devnull  */
195 a0d146ed 2005-07-12 devnull int
196 a0d146ed 2005-07-12 devnull outputindex(Fmt *f, Index *ix)
197 a0d146ed 2005-07-12 devnull {
198 a0d146ed 2005-07-12 devnull 	if(fmtprint(f, "%s\n%ud\n%s\n%ud\n", IndexMagic, ix->version, ix->name, ix->blocksize) < 0
199 a0d146ed 2005-07-12 devnull 	|| outputamap(f, ix->smap, ix->nsects) < 0
200 a0d146ed 2005-07-12 devnull 	|| outputamap(f, ix->amap, ix->narenas) < 0)
201 a0d146ed 2005-07-12 devnull 		return -1;
202 a0d146ed 2005-07-12 devnull 	return 0;
203 a0d146ed 2005-07-12 devnull }
204 a0d146ed 2005-07-12 devnull 
205 a0d146ed 2005-07-12 devnull int
206 a0d146ed 2005-07-12 devnull parseindex(IFile *f, Index *ix)
207 a0d146ed 2005-07-12 devnull {
208 a0d146ed 2005-07-12 devnull 	AMapN amn;
209 a0d146ed 2005-07-12 devnull 	u32int v;
210 a0d146ed 2005-07-12 devnull 	char *s;
211 a0d146ed 2005-07-12 devnull 
212 a0d146ed 2005-07-12 devnull 	/*
213 a0d146ed 2005-07-12 devnull 	 * magic
214 a0d146ed 2005-07-12 devnull 	 */
215 a0d146ed 2005-07-12 devnull 	s = ifileline(f);
216 a0d146ed 2005-07-12 devnull 	if(s == nil || strcmp(s, IndexMagic) != 0){
217 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "bad index magic for %s", f->name);
218 a0d146ed 2005-07-12 devnull 		return -1;
219 a0d146ed 2005-07-12 devnull 	}
220 a0d146ed 2005-07-12 devnull 
221 a0d146ed 2005-07-12 devnull 	/*
222 a0d146ed 2005-07-12 devnull 	 * version
223 a0d146ed 2005-07-12 devnull 	 */
224 a0d146ed 2005-07-12 devnull 	if(ifileu32int(f, &v) < 0){
225 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "syntax error: bad version number in %s", f->name);
226 a0d146ed 2005-07-12 devnull 		return -1;
227 a0d146ed 2005-07-12 devnull 	}
228 a0d146ed 2005-07-12 devnull 	ix->version = v;
229 a0d146ed 2005-07-12 devnull 	if(ix->version != IndexVersion){
230 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "bad version number in %s", f->name);
231 a0d146ed 2005-07-12 devnull 		return -1;
232 a0d146ed 2005-07-12 devnull 	}
233 a0d146ed 2005-07-12 devnull 
234 a0d146ed 2005-07-12 devnull 	/*
235 a0d146ed 2005-07-12 devnull 	 * name
236 a0d146ed 2005-07-12 devnull 	 */
237 a0d146ed 2005-07-12 devnull 	if(ifilename(f, ix->name) < 0){
238 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "syntax error: bad index name in %s", f->name);
239 a0d146ed 2005-07-12 devnull 		return -1;
240 a0d146ed 2005-07-12 devnull 	}
241 a0d146ed 2005-07-12 devnull 
242 a0d146ed 2005-07-12 devnull 	/*
243 a0d146ed 2005-07-12 devnull 	 * block size
244 a0d146ed 2005-07-12 devnull 	 */
245 a0d146ed 2005-07-12 devnull 	if(ifileu32int(f, &v) < 0){
246 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "syntax error: bad block size number in %s", f->name);
247 a0d146ed 2005-07-12 devnull 		return -1;
248 a0d146ed 2005-07-12 devnull 	}
249 a0d146ed 2005-07-12 devnull 	ix->blocksize = v;
250 a0d146ed 2005-07-12 devnull 
251 a0d146ed 2005-07-12 devnull 	if(parseamap(f, &amn) < 0)
252 a0d146ed 2005-07-12 devnull 		return -1;
253 a0d146ed 2005-07-12 devnull 	ix->nsects = amn.n;
254 a0d146ed 2005-07-12 devnull 	ix->smap = amn.map;
255 a0d146ed 2005-07-12 devnull 
256 a0d146ed 2005-07-12 devnull 	if(parseamap(f, &amn) < 0)
257 a0d146ed 2005-07-12 devnull 		return -1;
258 a0d146ed 2005-07-12 devnull 	ix->narenas = amn.n;
259 a0d146ed 2005-07-12 devnull 	ix->amap = amn.map;
260 a0d146ed 2005-07-12 devnull 
261 a0d146ed 2005-07-12 devnull 	return 0;
262 a0d146ed 2005-07-12 devnull }
263 a0d146ed 2005-07-12 devnull 
264 a0d146ed 2005-07-12 devnull /*
265 a0d146ed 2005-07-12 devnull  * initialize an entirely new index
266 a0d146ed 2005-07-12 devnull  */
267 a0d146ed 2005-07-12 devnull Index *
268 a0d146ed 2005-07-12 devnull newindex(char *name, ISect **sects, int n)
269 a0d146ed 2005-07-12 devnull {
270 a0d146ed 2005-07-12 devnull 	Index *ix;
271 a0d146ed 2005-07-12 devnull 	AMap *smap;
272 a0d146ed 2005-07-12 devnull 	u64int nb;
273 07029cdb 2007-04-23 devnull 	u32int div, ub, xb, start, stop, blocksize, tabsize;
274 a0d146ed 2005-07-12 devnull 	int i, j;
275 a0d146ed 2005-07-12 devnull 
276 a0d146ed 2005-07-12 devnull 	if(n < 1){
277 a0d146ed 2005-07-12 devnull 		seterr(EOk, "creating index with no index sections");
278 a0d146ed 2005-07-12 devnull 		return nil;
279 a0d146ed 2005-07-12 devnull 	}
280 a0d146ed 2005-07-12 devnull 
281 a0d146ed 2005-07-12 devnull 	/*
282 a0d146ed 2005-07-12 devnull 	 * compute the total buckets available in the index,
283 a0d146ed 2005-07-12 devnull 	 * and the total buckets which are used.
284 a0d146ed 2005-07-12 devnull 	 */
285 a0d146ed 2005-07-12 devnull 	nb = 0;
286 a0d146ed 2005-07-12 devnull 	blocksize = sects[0]->blocksize;
287 a0d146ed 2005-07-12 devnull 	tabsize = sects[0]->tabsize;
288 a0d146ed 2005-07-12 devnull 	for(i = 0; i < n; i++){
289 7e452401 2007-04-27 devnull 		/*
290 7e452401 2007-04-27 devnull 		 * allow index, start, and stop to be set if index is correct
291 7e452401 2007-04-27 devnull 		 * and start and stop are what we would have picked.
292 7e452401 2007-04-27 devnull 		 * this allows calling fmtindex to reformat the index after
293 7e452401 2007-04-27 devnull 		 * replacing a bad index section with a freshly formatted one.
294 7e452401 2007-04-27 devnull 		 * start and stop are checked below.
295 7e452401 2007-04-27 devnull 		 */
296 7e452401 2007-04-27 devnull 		if(sects[i]->index[0] != '\0' && strcmp(sects[i]->index, name) != 0){
297 a0d146ed 2005-07-12 devnull 			seterr(EOk, "creating new index using non-empty section %s", sects[i]->name);
298 a0d146ed 2005-07-12 devnull 			return nil;
299 a0d146ed 2005-07-12 devnull 		}
300 a0d146ed 2005-07-12 devnull 		if(blocksize != sects[i]->blocksize){
301 3b06b757 2008-12-23 rsc 			seterr(EOk, "%s has block size %d, but %s has %d",
302 3b06b757 2008-12-23 rsc 				sects[0]->part->name, (int)blocksize,
303 3b06b757 2008-12-23 rsc 				sects[i]->part->name, (int)sects[i]->blocksize);
304 a0d146ed 2005-07-12 devnull 			return nil;
305 a0d146ed 2005-07-12 devnull 		}
306 a0d146ed 2005-07-12 devnull 		if(tabsize != sects[i]->tabsize){
307 3b06b757 2008-12-23 rsc 			seterr(EOk, "%s has table size %d, but %s has %d",
308 3b06b757 2008-12-23 rsc 				sects[0]->part->name, (int)tabsize,
309 3b06b757 2008-12-23 rsc 				sects[i]->part->name, (int)sects[i]->tabsize);
310 a0d146ed 2005-07-12 devnull 			return nil;
311 a0d146ed 2005-07-12 devnull 		}
312 a0d146ed 2005-07-12 devnull 		nb += sects[i]->blocks;
313 a0d146ed 2005-07-12 devnull 	}
314 a0d146ed 2005-07-12 devnull 
315 a0d146ed 2005-07-12 devnull 	/*
316 a0d146ed 2005-07-12 devnull 	 * check for duplicate names
317 a0d146ed 2005-07-12 devnull 	 */
318 a0d146ed 2005-07-12 devnull 	for(i = 0; i < n; i++){
319 a0d146ed 2005-07-12 devnull 		for(j = i + 1; j < n; j++){
320 a0d146ed 2005-07-12 devnull 			if(namecmp(sects[i]->name, sects[j]->name) == 0){
321 3b06b757 2008-12-23 rsc 				seterr(EOk, "%s and %s both have section name %s",
322 3b06b757 2008-12-23 rsc 					sects[i]->part->name,
323 3b06b757 2008-12-23 rsc 					sects[j]->part->name,
324 3b06b757 2008-12-23 rsc 					sects[i]->name);
325 a0d146ed 2005-07-12 devnull 				return nil;
326 a0d146ed 2005-07-12 devnull 			}
327 a0d146ed 2005-07-12 devnull 		}
328 a0d146ed 2005-07-12 devnull 	}
329 a0d146ed 2005-07-12 devnull 
330 a0d146ed 2005-07-12 devnull 	if(nb >= ((u64int)1 << 32)){
331 f5a8ea6f 2011-06-02 rsc 		fprint(2, "%s: index is 2^32 blocks or more; ignoring some of it\n",
332 f5a8ea6f 2011-06-02 rsc 			argv0);
333 f5a8ea6f 2011-06-02 rsc 		nb = ((u64int)1 << 32) - 1;
334 a0d146ed 2005-07-12 devnull 	}
335 a0d146ed 2005-07-12 devnull 
336 a0d146ed 2005-07-12 devnull 	div = (((u64int)1 << 32) + nb - 1) / nb;
337 a0d146ed 2005-07-12 devnull 	if(div < 100){
338 f5a8ea6f 2011-06-02 rsc 		fprint(2, "%s: index divisor %d too coarse; "
339 f5a8ea6f 2011-06-02 rsc 			"index larger than needed, ignoring some of it\n",
340 f5a8ea6f 2011-06-02 rsc 			argv0, div);
341 f5a8ea6f 2011-06-02 rsc 		div = 100;
342 f5a8ea6f 2011-06-02 rsc 		nb = (((u64int)1 << 32) - 1) / (100 - 1);
343 a0d146ed 2005-07-12 devnull 	}
344 f5a8ea6f 2011-06-02 rsc 	ub = (((u64int)1 << 32) - 1) / div + 1;
345 a0d146ed 2005-07-12 devnull 	if(ub > nb){
346 a0d146ed 2005-07-12 devnull 		seterr(EBug, "index initialization math wrong");
347 a0d146ed 2005-07-12 devnull 		return nil;
348 a0d146ed 2005-07-12 devnull 	}
349 a0d146ed 2005-07-12 devnull 	xb = nb - ub;
350 a0d146ed 2005-07-12 devnull 
351 a0d146ed 2005-07-12 devnull 	/*
352 a0d146ed 2005-07-12 devnull 	 * initialize each of the index sections
353 a0d146ed 2005-07-12 devnull 	 * and the section map table
354 a0d146ed 2005-07-12 devnull 	 */
355 a0d146ed 2005-07-12 devnull 	smap = MKNZ(AMap, n);
356 a0d146ed 2005-07-12 devnull 	if(smap == nil){
357 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't create new index: out of memory");
358 a0d146ed 2005-07-12 devnull 		return nil;
359 a0d146ed 2005-07-12 devnull 	}
360 a0d146ed 2005-07-12 devnull 	start = 0;
361 a0d146ed 2005-07-12 devnull 	for(i = 0; i < n; i++){
362 a0d146ed 2005-07-12 devnull 		stop = start + sects[i]->blocks - xb / n;
363 a0d146ed 2005-07-12 devnull 		if(i == n - 1)
364 a0d146ed 2005-07-12 devnull 			stop = ub;
365 7e452401 2007-04-27 devnull 
366 7e452401 2007-04-27 devnull 		if(sects[i]->start != 0 || sects[i]->stop != 0)
367 7e452401 2007-04-27 devnull 		if(sects[i]->start != start || sects[i]->stop != stop){
368 7e452401 2007-04-27 devnull 			seterr(EOk, "creating new index using non-empty section %s", sects[i]->name);
369 7e452401 2007-04-27 devnull 			return nil;
370 7e452401 2007-04-27 devnull 		}
371 7e452401 2007-04-27 devnull 
372 a0d146ed 2005-07-12 devnull 		sects[i]->start = start;
373 a0d146ed 2005-07-12 devnull 		sects[i]->stop = stop;
374 a0d146ed 2005-07-12 devnull 		namecp(sects[i]->index, name);
375 a0d146ed 2005-07-12 devnull 
376 a0d146ed 2005-07-12 devnull 		smap[i].start = start;
377 a0d146ed 2005-07-12 devnull 		smap[i].stop = stop;
378 a0d146ed 2005-07-12 devnull 		namecp(smap[i].name, sects[i]->name);
379 a0d146ed 2005-07-12 devnull 		start = stop;
380 a0d146ed 2005-07-12 devnull 	}
381 a0d146ed 2005-07-12 devnull 
382 a0d146ed 2005-07-12 devnull 	/*
383 a0d146ed 2005-07-12 devnull 	 * initialize the index itself
384 a0d146ed 2005-07-12 devnull 	 */
385 a0d146ed 2005-07-12 devnull 	ix = MKZ(Index);
386 a0d146ed 2005-07-12 devnull 	if(ix == nil){
387 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't create new index: out of memory");
388 a0d146ed 2005-07-12 devnull 		free(smap);
389 a0d146ed 2005-07-12 devnull 		return nil;
390 a0d146ed 2005-07-12 devnull 	}
391 a0d146ed 2005-07-12 devnull 	ix->version = IndexVersion;
392 a0d146ed 2005-07-12 devnull 	namecp(ix->name, name);
393 a0d146ed 2005-07-12 devnull 	ix->sects = sects;
394 a0d146ed 2005-07-12 devnull 	ix->smap = smap;
395 a0d146ed 2005-07-12 devnull 	ix->nsects = n;
396 a0d146ed 2005-07-12 devnull 	ix->blocksize = blocksize;
397 a0d146ed 2005-07-12 devnull 	ix->buckets = ub;
398 a0d146ed 2005-07-12 devnull 	ix->tabsize = tabsize;
399 a0d146ed 2005-07-12 devnull 	ix->div = div;
400 a0d146ed 2005-07-12 devnull 
401 a0d146ed 2005-07-12 devnull 	if(initindex1(ix) < 0){
402 a0d146ed 2005-07-12 devnull 		free(smap);
403 a0d146ed 2005-07-12 devnull 		return nil;
404 a0d146ed 2005-07-12 devnull 	}
405 a0d146ed 2005-07-12 devnull 
406 a0d146ed 2005-07-12 devnull 	return ix;
407 a0d146ed 2005-07-12 devnull }
408 a0d146ed 2005-07-12 devnull 
409 a0d146ed 2005-07-12 devnull ISect*
410 a0d146ed 2005-07-12 devnull initisect(Part *part)
411 a0d146ed 2005-07-12 devnull {
412 a0d146ed 2005-07-12 devnull 	ISect *is;
413 a0d146ed 2005-07-12 devnull 	ZBlock *b;
414 a0d146ed 2005-07-12 devnull 	int ok;
415 a0d146ed 2005-07-12 devnull 
416 a0d146ed 2005-07-12 devnull 	b = alloczblock(HeadSize, 0, 0);
417 a0d146ed 2005-07-12 devnull 	if(b == nil || readpart(part, PartBlank, b->data, HeadSize) < 0){
418 a0d146ed 2005-07-12 devnull 		seterr(EAdmin, "can't read index section header: %r");
419 a0d146ed 2005-07-12 devnull 		return nil;
420 a0d146ed 2005-07-12 devnull 	}
421 a0d146ed 2005-07-12 devnull 
422 a0d146ed 2005-07-12 devnull 	is = MKZ(ISect);
423 a0d146ed 2005-07-12 devnull 	if(is == nil){
424 a0d146ed 2005-07-12 devnull 		freezblock(b);
425 a0d146ed 2005-07-12 devnull 		return nil;
426 a0d146ed 2005-07-12 devnull 	}
427 a0d146ed 2005-07-12 devnull 	is->part = part;
428 a0d146ed 2005-07-12 devnull 	ok = unpackisect(is, b->data);
429 a0d146ed 2005-07-12 devnull 	freezblock(b);
430 a0d146ed 2005-07-12 devnull 	if(ok < 0){
431 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "corrupted index section header: %r");
432 a0d146ed 2005-07-12 devnull 		freeisect(is);
433 a0d146ed 2005-07-12 devnull 		return nil;
434 a0d146ed 2005-07-12 devnull 	}
435 a0d146ed 2005-07-12 devnull 
436 a0d146ed 2005-07-12 devnull 	if(is->version != ISectVersion1 && is->version != ISectVersion2){
437 a0d146ed 2005-07-12 devnull 		seterr(EAdmin, "unknown index section version %d", is->version);
438 a0d146ed 2005-07-12 devnull 		freeisect(is);
439 a0d146ed 2005-07-12 devnull 		return nil;
440 a0d146ed 2005-07-12 devnull 	}
441 a0d146ed 2005-07-12 devnull 
442 a0d146ed 2005-07-12 devnull 	return initisect1(is);
443 a0d146ed 2005-07-12 devnull }
444 a0d146ed 2005-07-12 devnull 
445 a0d146ed 2005-07-12 devnull ISect*
446 a0d146ed 2005-07-12 devnull newisect(Part *part, u32int vers, char *name, u32int blocksize, u32int tabsize)
447 a0d146ed 2005-07-12 devnull {
448 a0d146ed 2005-07-12 devnull 	ISect *is;
449 a0d146ed 2005-07-12 devnull 	u32int tabbase;
450 a0d146ed 2005-07-12 devnull 
451 a0d146ed 2005-07-12 devnull 	is = MKZ(ISect);
452 a0d146ed 2005-07-12 devnull 	if(is == nil)
453 a0d146ed 2005-07-12 devnull 		return nil;
454 a0d146ed 2005-07-12 devnull 
455 a0d146ed 2005-07-12 devnull 	namecp(is->name, name);
456 a0d146ed 2005-07-12 devnull 	is->version = vers;
457 a0d146ed 2005-07-12 devnull 	is->part = part;
458 a0d146ed 2005-07-12 devnull 	is->blocksize = blocksize;
459 a0d146ed 2005-07-12 devnull 	is->start = 0;
460 a0d146ed 2005-07-12 devnull 	is->stop = 0;
461 a0d146ed 2005-07-12 devnull 	tabbase = (PartBlank + HeadSize + blocksize - 1) & ~(blocksize - 1);
462 a0d146ed 2005-07-12 devnull 	is->blockbase = (tabbase + tabsize + blocksize - 1) & ~(blocksize - 1);
463 a0d146ed 2005-07-12 devnull 	is->blocks = is->part->size / blocksize - is->blockbase / blocksize;
464 a0d146ed 2005-07-12 devnull 	is->bucketmagic = 0;
465 a0d146ed 2005-07-12 devnull 	if(is->version == ISectVersion2){
466 a0d146ed 2005-07-12 devnull 		do{
467 a0d146ed 2005-07-12 devnull 			is->bucketmagic = fastrand();
468 a0d146ed 2005-07-12 devnull 		}while(is->bucketmagic==0);
469 a0d146ed 2005-07-12 devnull 	}
470 a0d146ed 2005-07-12 devnull 	is = initisect1(is);
471 a0d146ed 2005-07-12 devnull 	if(is == nil)
472 a0d146ed 2005-07-12 devnull 		return nil;
473 a0d146ed 2005-07-12 devnull 
474 a0d146ed 2005-07-12 devnull 	return is;
475 a0d146ed 2005-07-12 devnull }
476 a0d146ed 2005-07-12 devnull 
477 a0d146ed 2005-07-12 devnull /*
478 a0d146ed 2005-07-12 devnull  * initialize the computed parameters for an index
479 a0d146ed 2005-07-12 devnull  */
480 a0d146ed 2005-07-12 devnull static ISect*
481 a0d146ed 2005-07-12 devnull initisect1(ISect *is)
482 a0d146ed 2005-07-12 devnull {
483 a0d146ed 2005-07-12 devnull 	u64int v;
484 a0d146ed 2005-07-12 devnull 
485 a0d146ed 2005-07-12 devnull 	is->buckmax = (is->blocksize - IBucketSize) / IEntrySize;
486 a0d146ed 2005-07-12 devnull 	is->blocklog = u64log2(is->blocksize);
487 a0d146ed 2005-07-12 devnull 	if(is->blocksize != (1 << is->blocklog)){
488 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "illegal non-power-of-2 bucket size %d\n", is->blocksize);
489 a0d146ed 2005-07-12 devnull 		freeisect(is);
490 a0d146ed 2005-07-12 devnull 		return nil;
491 a0d146ed 2005-07-12 devnull 	}
492 a0d146ed 2005-07-12 devnull 	partblocksize(is->part, is->blocksize);
493 a0d146ed 2005-07-12 devnull 	is->tabbase = (PartBlank + HeadSize + is->blocksize - 1) & ~(is->blocksize - 1);
494 a0d146ed 2005-07-12 devnull 	if(is->tabbase >= is->blockbase){
495 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "index section config table overlaps bucket storage");
496 a0d146ed 2005-07-12 devnull 		freeisect(is);
497 a0d146ed 2005-07-12 devnull 		return nil;
498 a0d146ed 2005-07-12 devnull 	}
499 a0d146ed 2005-07-12 devnull 	is->tabsize = is->blockbase - is->tabbase;
500 a0d146ed 2005-07-12 devnull 	v = is->part->size & ~(u64int)(is->blocksize - 1);
501 a0d146ed 2005-07-12 devnull 	if(is->blockbase + (u64int)is->blocks * is->blocksize != v){
502 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "invalid blocks in index section %s", is->name);
503 fa325e9b 2020-01-10 cross 		/* ZZZ what to do?
504 28b49df3 2006-07-18 devnull 		freeisect(is);
505 28b49df3 2006-07-18 devnull 		return nil;
506 28b49df3 2006-07-18 devnull 		*/
507 a0d146ed 2005-07-12 devnull 	}
508 a0d146ed 2005-07-12 devnull 
509 a0d146ed 2005-07-12 devnull 	if(is->stop - is->start > is->blocks){
510 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "index section overflows available space");
511 a0d146ed 2005-07-12 devnull 		freeisect(is);
512 a0d146ed 2005-07-12 devnull 		return nil;
513 a0d146ed 2005-07-12 devnull 	}
514 a0d146ed 2005-07-12 devnull 	if(is->start > is->stop){
515 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "invalid index section range");
516 a0d146ed 2005-07-12 devnull 		freeisect(is);
517 a0d146ed 2005-07-12 devnull 		return nil;
518 a0d146ed 2005-07-12 devnull 	}
519 a0d146ed 2005-07-12 devnull 
520 a0d146ed 2005-07-12 devnull 	return is;
521 a0d146ed 2005-07-12 devnull }
522 a0d146ed 2005-07-12 devnull 
523 a0d146ed 2005-07-12 devnull int
524 a0d146ed 2005-07-12 devnull wbisect(ISect *is)
525 a0d146ed 2005-07-12 devnull {
526 a0d146ed 2005-07-12 devnull 	ZBlock *b;
527 a0d146ed 2005-07-12 devnull 
528 a0d146ed 2005-07-12 devnull 	b = alloczblock(HeadSize, 1, 0);
529 28b49df3 2006-07-18 devnull 	if(b == nil){
530 28b49df3 2006-07-18 devnull 		/* ZZZ set error? */
531 a0d146ed 2005-07-12 devnull 		return -1;
532 28b49df3 2006-07-18 devnull 	}
533 a0d146ed 2005-07-12 devnull 
534 a0d146ed 2005-07-12 devnull 	if(packisect(is, b->data) < 0){
535 a0d146ed 2005-07-12 devnull 		seterr(ECorrupt, "can't make index section header: %r");
536 a0d146ed 2005-07-12 devnull 		freezblock(b);
537 a0d146ed 2005-07-12 devnull 		return -1;
538 a0d146ed 2005-07-12 devnull 	}
539 e46cacb0 2007-04-27 devnull 	if(writepart(is->part, PartBlank, b->data, HeadSize) < 0 || flushpart(is->part) < 0){
540 a0d146ed 2005-07-12 devnull 		seterr(EAdmin, "can't write index section header: %r");
541 a0d146ed 2005-07-12 devnull 		freezblock(b);
542 a0d146ed 2005-07-12 devnull 		return -1;
543 a0d146ed 2005-07-12 devnull 	}
544 a0d146ed 2005-07-12 devnull 	freezblock(b);
545 a0d146ed 2005-07-12 devnull 
546 a0d146ed 2005-07-12 devnull 	return 0;
547 a0d146ed 2005-07-12 devnull }
548 a0d146ed 2005-07-12 devnull 
549 a0d146ed 2005-07-12 devnull void
550 a0d146ed 2005-07-12 devnull freeisect(ISect *is)
551 a0d146ed 2005-07-12 devnull {
552 a0d146ed 2005-07-12 devnull 	if(is == nil)
553 a0d146ed 2005-07-12 devnull 		return;
554 a0d146ed 2005-07-12 devnull 	free(is);
555 a0d146ed 2005-07-12 devnull }
556 a0d146ed 2005-07-12 devnull 
557 a0d146ed 2005-07-12 devnull void
558 a0d146ed 2005-07-12 devnull freeindex(Index *ix)
559 a0d146ed 2005-07-12 devnull {
560 a0d146ed 2005-07-12 devnull 	int i;
561 a0d146ed 2005-07-12 devnull 
562 a0d146ed 2005-07-12 devnull 	if(ix == nil)
563 a0d146ed 2005-07-12 devnull 		return;
564 a0d146ed 2005-07-12 devnull 	free(ix->amap);
565 a0d146ed 2005-07-12 devnull 	free(ix->arenas);
566 a0d146ed 2005-07-12 devnull 	if(ix->sects)
567 a0d146ed 2005-07-12 devnull 		for(i = 0; i < ix->nsects; i++)
568 a0d146ed 2005-07-12 devnull 			freeisect(ix->sects[i]);
569 a0d146ed 2005-07-12 devnull 	free(ix->sects);
570 a0d146ed 2005-07-12 devnull 	free(ix->smap);
571 a0d146ed 2005-07-12 devnull 	free(ix);
572 a0d146ed 2005-07-12 devnull }
573 a0d146ed 2005-07-12 devnull 
574 a0d146ed 2005-07-12 devnull /*
575 a0d146ed 2005-07-12 devnull  * write a clump to an available arena in the index
576 a0d146ed 2005-07-12 devnull  * and return the address of the clump within the index.
577 a0d146ed 2005-07-12 devnull ZZZ question: should this distinguish between an arena
578 a0d146ed 2005-07-12 devnull filling up and real errors writing the clump?
579 a0d146ed 2005-07-12 devnull  */
580 a0d146ed 2005-07-12 devnull u64int
581 45ac814c 2007-10-29 rsc writeiclump(Index *ix, Clump *c, u8int *clbuf)
582 a0d146ed 2005-07-12 devnull {
583 a0d146ed 2005-07-12 devnull 	u64int a;
584 a0d146ed 2005-07-12 devnull 	int i;
585 45ac814c 2007-10-29 rsc 	IAddr ia;
586 45ac814c 2007-10-29 rsc 	AState as;
587 a0d146ed 2005-07-12 devnull 
588 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "writeiclump enter");
589 45ac814c 2007-10-29 rsc 	qlock(&ix->writing);
590 45ac814c 2007-10-29 rsc 	for(i = ix->mapalloc; i < ix->narenas; i++){
591 45ac814c 2007-10-29 rsc 		a = writeaclump(ix->arenas[i], c, clbuf);
592 a0d146ed 2005-07-12 devnull 		if(a != TWID64){
593 45ac814c 2007-10-29 rsc 			ix->mapalloc = i;
594 45ac814c 2007-10-29 rsc 			ia.addr = ix->amap[i].start + a;
595 45ac814c 2007-10-29 rsc 			ia.type = c->info.type;
596 45ac814c 2007-10-29 rsc 			ia.size = c->info.uncsize;
597 45ac814c 2007-10-29 rsc 			ia.blocks = (c->info.size + ClumpSize + (1<<ABlockLog) - 1) >> ABlockLog;
598 45ac814c 2007-10-29 rsc 			as.arena = ix->arenas[i];
599 45ac814c 2007-10-29 rsc 			as.aa = ia.addr;
600 45ac814c 2007-10-29 rsc 			as.stats = as.arena->memstats;
601 45ac814c 2007-10-29 rsc 			insertscore(c->info.score, &ia, IEDirty, &as);
602 45ac814c 2007-10-29 rsc 			qunlock(&ix->writing);
603 a0d146ed 2005-07-12 devnull 			trace(TraceLump, "writeiclump exit");
604 45ac814c 2007-10-29 rsc 			return ia.addr;
605 a0d146ed 2005-07-12 devnull 		}
606 a0d146ed 2005-07-12 devnull 	}
607 45ac814c 2007-10-29 rsc 	qunlock(&ix->writing);
608 a0d146ed 2005-07-12 devnull 
609 a0d146ed 2005-07-12 devnull 	seterr(EAdmin, "no space left in arenas");
610 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "writeiclump failed");
611 a0d146ed 2005-07-12 devnull 	return TWID64;
612 a0d146ed 2005-07-12 devnull }
613 a0d146ed 2005-07-12 devnull 
614 a0d146ed 2005-07-12 devnull /*
615 a0d146ed 2005-07-12 devnull  * convert an arena index to an relative arena address
616 a0d146ed 2005-07-12 devnull  */
617 a0d146ed 2005-07-12 devnull Arena*
618 a0d146ed 2005-07-12 devnull amapitoa(Index *ix, u64int a, u64int *aa)
619 a0d146ed 2005-07-12 devnull {
620 a0d146ed 2005-07-12 devnull 	int i, r, l, m;
621 a0d146ed 2005-07-12 devnull 
622 a0d146ed 2005-07-12 devnull 	l = 1;
623 a0d146ed 2005-07-12 devnull 	r = ix->narenas - 1;
624 a0d146ed 2005-07-12 devnull 	while(l <= r){
625 a0d146ed 2005-07-12 devnull 		m = (r + l) / 2;
626 a0d146ed 2005-07-12 devnull 		if(ix->amap[m].start <= a)
627 a0d146ed 2005-07-12 devnull 			l = m + 1;
628 a0d146ed 2005-07-12 devnull 		else
629 a0d146ed 2005-07-12 devnull 			r = m - 1;
630 a0d146ed 2005-07-12 devnull 	}
631 a0d146ed 2005-07-12 devnull 	l--;
632 a0d146ed 2005-07-12 devnull 
633 a0d146ed 2005-07-12 devnull 	if(a > ix->amap[l].stop){
634 a0d146ed 2005-07-12 devnull for(i=0; i<ix->narenas; i++)
635 a0d146ed 2005-07-12 devnull 	print("arena %d: %llux - %llux\n", i, ix->amap[i].start, ix->amap[i].stop);
636 a0d146ed 2005-07-12 devnull print("want arena %d for %llux\n", l, a);
637 a0d146ed 2005-07-12 devnull 		seterr(ECrash, "unmapped address passed to amapitoa");
638 a0d146ed 2005-07-12 devnull 		return nil;
639 a0d146ed 2005-07-12 devnull 	}
640 a0d146ed 2005-07-12 devnull 
641 a0d146ed 2005-07-12 devnull 	if(ix->arenas[l] == nil){
642 a0d146ed 2005-07-12 devnull 		seterr(ECrash, "unmapped arena selected in amapitoa");
643 a0d146ed 2005-07-12 devnull 		return nil;
644 a0d146ed 2005-07-12 devnull 	}
645 a0d146ed 2005-07-12 devnull 	*aa = a - ix->amap[l].start;
646 a0d146ed 2005-07-12 devnull 	return ix->arenas[l];
647 a0d146ed 2005-07-12 devnull }
648 a0d146ed 2005-07-12 devnull 
649 7a400ee9 2007-09-25 rsc /*
650 7a400ee9 2007-09-25 rsc  * convert an arena index to the bounds of the containing arena group.
651 7a400ee9 2007-09-25 rsc  */
652 7a400ee9 2007-09-25 rsc Arena*
653 7a400ee9 2007-09-25 rsc amapitoag(Index *ix, u64int a, u64int *gstart, u64int *glimit, int *g)
654 7a400ee9 2007-09-25 rsc {
655 7a400ee9 2007-09-25 rsc 	u64int aa;
656 7a400ee9 2007-09-25 rsc 	Arena *arena;
657 fa325e9b 2020-01-10 cross 
658 7a400ee9 2007-09-25 rsc 	arena = amapitoa(ix, a, &aa);
659 7a400ee9 2007-09-25 rsc 	if(arena == nil)
660 7a400ee9 2007-09-25 rsc 		return nil;
661 7a400ee9 2007-09-25 rsc 	if(arenatog(arena, aa, gstart, glimit, g) < 0)
662 7a400ee9 2007-09-25 rsc 		return nil;
663 7a400ee9 2007-09-25 rsc 	*gstart += a - aa;
664 7a400ee9 2007-09-25 rsc 	*glimit += a - aa;
665 7a400ee9 2007-09-25 rsc 	return arena;
666 7a400ee9 2007-09-25 rsc }
667 7a400ee9 2007-09-25 rsc 
668 a0d146ed 2005-07-12 devnull int
669 a0d146ed 2005-07-12 devnull iaddrcmp(IAddr *ia1, IAddr *ia2)
670 a0d146ed 2005-07-12 devnull {
671 a0d146ed 2005-07-12 devnull 	return ia1->type != ia2->type
672 a0d146ed 2005-07-12 devnull 		|| ia1->size != ia2->size
673 a0d146ed 2005-07-12 devnull 		|| ia1->blocks != ia2->blocks
674 a0d146ed 2005-07-12 devnull 		|| ia1->addr != ia2->addr;
675 a0d146ed 2005-07-12 devnull }
676 a0d146ed 2005-07-12 devnull 
677 a0d146ed 2005-07-12 devnull /*
678 a0d146ed 2005-07-12 devnull  * lookup the score in the partition
679 a0d146ed 2005-07-12 devnull  *
680 a0d146ed 2005-07-12 devnull  * nothing needs to be explicitly locked:
681 a0d146ed 2005-07-12 devnull  * only static parts of ix are used, and
682 a0d146ed 2005-07-12 devnull  * the bucket is locked by the DBlock lock.
683 a0d146ed 2005-07-12 devnull  */
684 a0d146ed 2005-07-12 devnull int
685 a0d146ed 2005-07-12 devnull loadientry(Index *ix, u8int *score, int type, IEntry *ie)
686 a0d146ed 2005-07-12 devnull {
687 a0d146ed 2005-07-12 devnull 	ISect *is;
688 a0d146ed 2005-07-12 devnull 	DBlock *b;
689 a0d146ed 2005-07-12 devnull 	IBucket ib;
690 a0d146ed 2005-07-12 devnull 	u32int buck;
691 a0d146ed 2005-07-12 devnull 	int h, ok;
692 a0d146ed 2005-07-12 devnull 
693 a0d146ed 2005-07-12 devnull 	ok = -1;
694 a0d146ed 2005-07-12 devnull 
695 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "loadientry enter");
696 a0d146ed 2005-07-12 devnull 
697 a0d146ed 2005-07-12 devnull 	/*
698 a0d146ed 2005-07-12 devnull 	qlock(&stats.lock);
699 a0d146ed 2005-07-12 devnull 	stats.indexreads++;
700 a0d146ed 2005-07-12 devnull 	qunlock(&stats.lock);
701 a0d146ed 2005-07-12 devnull 	*/
702 a0d146ed 2005-07-12 devnull 
703 a0d146ed 2005-07-12 devnull 	if(!inbloomfilter(mainindex->bloom, score)){
704 a0d146ed 2005-07-12 devnull 		trace(TraceLump, "loadientry bloomhit");
705 a0d146ed 2005-07-12 devnull 		return -1;
706 a0d146ed 2005-07-12 devnull 	}
707 a0d146ed 2005-07-12 devnull 
708 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "loadientry loadibucket");
709 a0d146ed 2005-07-12 devnull 	b = loadibucket(ix, score, &is, &buck, &ib);
710 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "loadientry loadedibucket");
711 a0d146ed 2005-07-12 devnull 	if(b == nil)
712 a0d146ed 2005-07-12 devnull 		return -1;
713 a0d146ed 2005-07-12 devnull 
714 a0d146ed 2005-07-12 devnull 	if(okibucket(&ib, is) < 0){
715 a0d146ed 2005-07-12 devnull 		trace(TraceLump, "loadientry badbucket");
716 a0d146ed 2005-07-12 devnull 		goto out;
717 a0d146ed 2005-07-12 devnull 	}
718 a0d146ed 2005-07-12 devnull 
719 a0d146ed 2005-07-12 devnull 	h = bucklook(score, type, ib.data, ib.n);
720 a0d146ed 2005-07-12 devnull 	if(h & 1){
721 a0d146ed 2005-07-12 devnull 		h ^= 1;
722 a0d146ed 2005-07-12 devnull 		trace(TraceLump, "loadientry found");
723 a0d146ed 2005-07-12 devnull 		unpackientry(ie, &ib.data[h]);
724 a0d146ed 2005-07-12 devnull 		ok = 0;
725 a0d146ed 2005-07-12 devnull 		goto out;
726 a0d146ed 2005-07-12 devnull 	}
727 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "loadientry notfound");
728 a0d146ed 2005-07-12 devnull 	addstat(StatBloomFalseMiss, 1);
729 a0d146ed 2005-07-12 devnull out:
730 a0d146ed 2005-07-12 devnull 	putdblock(b);
731 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "loadientry exit");
732 a0d146ed 2005-07-12 devnull 	return ok;
733 a0d146ed 2005-07-12 devnull }
734 a0d146ed 2005-07-12 devnull 
735 a0d146ed 2005-07-12 devnull int
736 a0d146ed 2005-07-12 devnull okibucket(IBucket *ib, ISect *is)
737 a0d146ed 2005-07-12 devnull {
738 a0d146ed 2005-07-12 devnull 	if(ib->n <= is->buckmax)
739 a0d146ed 2005-07-12 devnull 		return 0;
740 a0d146ed 2005-07-12 devnull 
741 a0d146ed 2005-07-12 devnull 	seterr(EICorrupt, "corrupted disk index bucket: n=%ud max=%ud, range=[%lud,%lud)",
742 a0d146ed 2005-07-12 devnull 		ib->n, is->buckmax, is->start, is->stop);
743 a0d146ed 2005-07-12 devnull 	return -1;
744 a0d146ed 2005-07-12 devnull }
745 a0d146ed 2005-07-12 devnull 
746 a0d146ed 2005-07-12 devnull /*
747 a0d146ed 2005-07-12 devnull  * look for score within data;
748 a0d146ed 2005-07-12 devnull  * return 1 | byte index of matching index,
749 a0d146ed 2005-07-12 devnull  * or 0 | index of least element > score
750 a0d146ed 2005-07-12 devnull  */
751 a0d146ed 2005-07-12 devnull int
752 a0d146ed 2005-07-12 devnull bucklook(u8int *score, int otype, u8int *data, int n)
753 a0d146ed 2005-07-12 devnull {
754 a0d146ed 2005-07-12 devnull 	int i, r, l, m, h, c, cc, type;
755 a0d146ed 2005-07-12 devnull 
756 27d28098 2007-04-21 devnull 	if(otype == -1)
757 27d28098 2007-04-21 devnull 		type = -1;
758 27d28098 2007-04-21 devnull 	else
759 27d28098 2007-04-21 devnull 		type = vttodisktype(otype);
760 a0d146ed 2005-07-12 devnull 	l = 0;
761 a0d146ed 2005-07-12 devnull 	r = n - 1;
762 a0d146ed 2005-07-12 devnull 	while(l <= r){
763 a0d146ed 2005-07-12 devnull 		m = (r + l) >> 1;
764 a0d146ed 2005-07-12 devnull 		h = m * IEntrySize;
765 a0d146ed 2005-07-12 devnull 		for(i = 0; i < VtScoreSize; i++){
766 a0d146ed 2005-07-12 devnull 			c = score[i];
767 a0d146ed 2005-07-12 devnull 			cc = data[h + i];
768 a0d146ed 2005-07-12 devnull 			if(c != cc){
769 a0d146ed 2005-07-12 devnull 				if(c > cc)
770 a0d146ed 2005-07-12 devnull 					l = m + 1;
771 a0d146ed 2005-07-12 devnull 				else
772 a0d146ed 2005-07-12 devnull 					r = m - 1;
773 a0d146ed 2005-07-12 devnull 				goto cont;
774 a0d146ed 2005-07-12 devnull 			}
775 a0d146ed 2005-07-12 devnull 		}
776 a0d146ed 2005-07-12 devnull 		cc = data[h + IEntryTypeOff];
777 27d28098 2007-04-21 devnull 		if(type != cc && type != -1){
778 a0d146ed 2005-07-12 devnull 			if(type > cc)
779 a0d146ed 2005-07-12 devnull 				l = m + 1;
780 a0d146ed 2005-07-12 devnull 			else
781 a0d146ed 2005-07-12 devnull 				r = m - 1;
782 a0d146ed 2005-07-12 devnull 			goto cont;
783 a0d146ed 2005-07-12 devnull 		}
784 a0d146ed 2005-07-12 devnull 		return h | 1;
785 a0d146ed 2005-07-12 devnull 	cont:;
786 a0d146ed 2005-07-12 devnull 	}
787 a0d146ed 2005-07-12 devnull 
788 a0d146ed 2005-07-12 devnull 	return l * IEntrySize;
789 a0d146ed 2005-07-12 devnull }
790 a0d146ed 2005-07-12 devnull 
791 a0d146ed 2005-07-12 devnull /*
792 a0d146ed 2005-07-12 devnull  * compare two IEntries; consistent with bucklook
793 a0d146ed 2005-07-12 devnull  */
794 a0d146ed 2005-07-12 devnull int
795 a0d146ed 2005-07-12 devnull ientrycmp(const void *vie1, const void *vie2)
796 a0d146ed 2005-07-12 devnull {
797 a0d146ed 2005-07-12 devnull 	u8int *ie1, *ie2;
798 a0d146ed 2005-07-12 devnull 	int i, v1, v2;
799 a0d146ed 2005-07-12 devnull 
800 a0d146ed 2005-07-12 devnull 	ie1 = (u8int*)vie1;
801 a0d146ed 2005-07-12 devnull 	ie2 = (u8int*)vie2;
802 a0d146ed 2005-07-12 devnull 	for(i = 0; i < VtScoreSize; i++){
803 a0d146ed 2005-07-12 devnull 		v1 = ie1[i];
804 a0d146ed 2005-07-12 devnull 		v2 = ie2[i];
805 a0d146ed 2005-07-12 devnull 		if(v1 != v2){
806 a0d146ed 2005-07-12 devnull 			if(v1 < v2)
807 a0d146ed 2005-07-12 devnull 				return -1;
808 a0d146ed 2005-07-12 devnull 			return 1;
809 a0d146ed 2005-07-12 devnull 		}
810 a0d146ed 2005-07-12 devnull 	}
811 a0d146ed 2005-07-12 devnull 	v1 = ie1[IEntryTypeOff];
812 a0d146ed 2005-07-12 devnull 	v2 = ie2[IEntryTypeOff];
813 a0d146ed 2005-07-12 devnull 	if(v1 != v2){
814 a0d146ed 2005-07-12 devnull 		if(v1 < v2)
815 a0d146ed 2005-07-12 devnull 			return -1;
816 a0d146ed 2005-07-12 devnull 		return 1;
817 a0d146ed 2005-07-12 devnull 	}
818 a0d146ed 2005-07-12 devnull 	return 0;
819 a0d146ed 2005-07-12 devnull }
820 a0d146ed 2005-07-12 devnull 
821 a0d146ed 2005-07-12 devnull /*
822 a0d146ed 2005-07-12 devnull  * find the number of the index section holding bucket #buck
823 a0d146ed 2005-07-12 devnull  */
824 a0d146ed 2005-07-12 devnull int
825 a0d146ed 2005-07-12 devnull indexsect0(Index *ix, u32int buck)
826 a0d146ed 2005-07-12 devnull {
827 a0d146ed 2005-07-12 devnull 	int r, l, m;
828 a0d146ed 2005-07-12 devnull 
829 a0d146ed 2005-07-12 devnull 	l = 1;
830 a0d146ed 2005-07-12 devnull 	r = ix->nsects - 1;
831 a0d146ed 2005-07-12 devnull 	while(l <= r){
832 a0d146ed 2005-07-12 devnull 		m = (r + l) >> 1;
833 a0d146ed 2005-07-12 devnull 		if(ix->sects[m]->start <= buck)
834 a0d146ed 2005-07-12 devnull 			l = m + 1;
835 a0d146ed 2005-07-12 devnull 		else
836 a0d146ed 2005-07-12 devnull 			r = m - 1;
837 a0d146ed 2005-07-12 devnull 	}
838 a0d146ed 2005-07-12 devnull 	return l - 1;
839 a0d146ed 2005-07-12 devnull }
840 a0d146ed 2005-07-12 devnull 
841 a0d146ed 2005-07-12 devnull /*
842 a0d146ed 2005-07-12 devnull  * load the index block at bucket #buck
843 a0d146ed 2005-07-12 devnull  */
844 a0d146ed 2005-07-12 devnull static DBlock*
845 a0d146ed 2005-07-12 devnull loadibucket0(Index *ix, u32int buck, ISect **pis, u32int *pbuck, IBucket *ib, int mode)
846 a0d146ed 2005-07-12 devnull {
847 a0d146ed 2005-07-12 devnull 	ISect *is;
848 a0d146ed 2005-07-12 devnull 	DBlock *b;
849 a0d146ed 2005-07-12 devnull 
850 a0d146ed 2005-07-12 devnull 	is = ix->sects[indexsect0(ix, buck)];
851 a0d146ed 2005-07-12 devnull 	if(buck < is->start || is->stop <= buck){
852 a0d146ed 2005-07-12 devnull 		seterr(EAdmin, "index lookup out of range: %ud not found in index\n", buck);
853 a0d146ed 2005-07-12 devnull 		return nil;
854 a0d146ed 2005-07-12 devnull 	}
855 a0d146ed 2005-07-12 devnull 
856 a0d146ed 2005-07-12 devnull 	buck -= is->start;
857 a0d146ed 2005-07-12 devnull 	if((b = getdblock(is->part, is->blockbase + ((u64int)buck << is->blocklog), mode)) == nil)
858 a0d146ed 2005-07-12 devnull 		return nil;
859 a0d146ed 2005-07-12 devnull 
860 a0d146ed 2005-07-12 devnull 	if(pis)
861 a0d146ed 2005-07-12 devnull 		*pis = is;
862 a0d146ed 2005-07-12 devnull 	if(pbuck)
863 a0d146ed 2005-07-12 devnull 		*pbuck = buck;
864 a0d146ed 2005-07-12 devnull 	if(ib)
865 a0d146ed 2005-07-12 devnull 		unpackibucket(ib, b->data, is->bucketmagic);
866 a0d146ed 2005-07-12 devnull 	return b;
867 a0d146ed 2005-07-12 devnull }
868 a0d146ed 2005-07-12 devnull 
869 a0d146ed 2005-07-12 devnull /*
870 a0d146ed 2005-07-12 devnull  * find the number of the index section holding score
871 a0d146ed 2005-07-12 devnull  */
872 28b49df3 2006-07-18 devnull int
873 a0d146ed 2005-07-12 devnull indexsect1(Index *ix, u8int *score)
874 a0d146ed 2005-07-12 devnull {
875 a0d146ed 2005-07-12 devnull 	return indexsect0(ix, hashbits(score, 32) / ix->div);
876 a0d146ed 2005-07-12 devnull }
877 a0d146ed 2005-07-12 devnull 
878 a0d146ed 2005-07-12 devnull /*
879 a0d146ed 2005-07-12 devnull  * load the index block responsible for score.
880 a0d146ed 2005-07-12 devnull  */
881 a0d146ed 2005-07-12 devnull static DBlock*
882 a0d146ed 2005-07-12 devnull loadibucket1(Index *ix, u8int *score, ISect **pis, u32int *pbuck, IBucket *ib)
883 a0d146ed 2005-07-12 devnull {
884 a0d146ed 2005-07-12 devnull 	return loadibucket0(ix, hashbits(score, 32)/ix->div, pis, pbuck, ib, OREAD);
885 a0d146ed 2005-07-12 devnull }
886 a0d146ed 2005-07-12 devnull 
887 a0d146ed 2005-07-12 devnull int
888 a0d146ed 2005-07-12 devnull indexsect(Index *ix, u8int *score)
889 a0d146ed 2005-07-12 devnull {
890 a0d146ed 2005-07-12 devnull 	return indexsect1(ix, score);
891 a0d146ed 2005-07-12 devnull }
892 a0d146ed 2005-07-12 devnull 
893 a0d146ed 2005-07-12 devnull DBlock*
894 a0d146ed 2005-07-12 devnull loadibucket(Index *ix, u8int *score, ISect **pis, u32int *pbuck, IBucket *ib)
895 a0d146ed 2005-07-12 devnull {
896 a0d146ed 2005-07-12 devnull 	return loadibucket1(ix, score, pis, pbuck, ib);
897 a0d146ed 2005-07-12 devnull }