1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
  2 7a4ee46d 2003-11-23 devnull #include "dat.h"
  3 7a4ee46d 2003-11-23 devnull #include "fns.h"
  4 7a4ee46d 2003-11-23 devnull 
  5 7a4ee46d 2003-11-23 devnull static int	bucklook(u8int *score, int type, u8int *data, int n);
  6 7a4ee46d 2003-11-23 devnull static int	writebucket(ISect *is, u32int buck, IBucket *ib, DBlock *b);
  7 7a4ee46d 2003-11-23 devnull static int	okibucket(IBucket *ib, ISect *is);
  8 7a4ee46d 2003-11-23 devnull static ISect	*initisect1(ISect *is);
  9 7a4ee46d 2003-11-23 devnull 
 10 7a4ee46d 2003-11-23 devnull //static QLock	indexlock;	//ZZZ
 11 7a4ee46d 2003-11-23 devnull 
 12 7a4ee46d 2003-11-23 devnull static char IndexMagic[] = "venti index configuration";
 13 7a4ee46d 2003-11-23 devnull 
 14 7a4ee46d 2003-11-23 devnull Index*
 15 7a4ee46d 2003-11-23 devnull initindex(char *name, ISect **sects, int n)
 16 7a4ee46d 2003-11-23 devnull {
 17 7a4ee46d 2003-11-23 devnull 	IFile f;
 18 7a4ee46d 2003-11-23 devnull 	Index *ix;
 19 7a4ee46d 2003-11-23 devnull 	ISect *is;
 20 7a4ee46d 2003-11-23 devnull 	u32int last, blocksize, tabsize;
 21 7a4ee46d 2003-11-23 devnull 	int i;
 22 7a4ee46d 2003-11-23 devnull 
 23 7a4ee46d 2003-11-23 devnull 	if(n <= 0){
 24 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "no index sections to initialize index");
 25 7a4ee46d 2003-11-23 devnull 		return nil;
 26 7a4ee46d 2003-11-23 devnull 	}
 27 7a4ee46d 2003-11-23 devnull 	ix = MKZ(Index);
 28 7a4ee46d 2003-11-23 devnull 	if(ix == nil){
 29 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "can't initialize index: out of memory");
 30 7a4ee46d 2003-11-23 devnull 		freeindex(ix);
 31 7a4ee46d 2003-11-23 devnull 		return nil;
 32 7a4ee46d 2003-11-23 devnull 	}
 33 7a4ee46d 2003-11-23 devnull 
 34 7a4ee46d 2003-11-23 devnull 	tabsize = sects[0]->tabsize;
 35 7a4ee46d 2003-11-23 devnull 	if(partifile(&f, sects[0]->part, sects[0]->tabbase, tabsize) < 0)
 36 7a4ee46d 2003-11-23 devnull 		return nil;
 37 7a4ee46d 2003-11-23 devnull 	if(parseindex(&f, ix) < 0){
 38 7a4ee46d 2003-11-23 devnull 		freeifile(&f);
 39 7a4ee46d 2003-11-23 devnull 		freeindex(ix);
 40 7a4ee46d 2003-11-23 devnull 		return nil;
 41 7a4ee46d 2003-11-23 devnull 	}
 42 7a4ee46d 2003-11-23 devnull 	freeifile(&f);
 43 7a4ee46d 2003-11-23 devnull 	if(namecmp(ix->name, name) != 0){
 44 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "mismatched index name: found %s expected %s", ix->name, name);
 45 7a4ee46d 2003-11-23 devnull 		return nil;
 46 7a4ee46d 2003-11-23 devnull 	}
 47 7a4ee46d 2003-11-23 devnull 	if(ix->nsects != n){
 48 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "mismatched number index sections: found %d expected %d", n, ix->nsects);
 49 7a4ee46d 2003-11-23 devnull 		freeindex(ix);
 50 7a4ee46d 2003-11-23 devnull 		return nil;
 51 7a4ee46d 2003-11-23 devnull 	}
 52 7a4ee46d 2003-11-23 devnull 	ix->sects = sects;
 53 7a4ee46d 2003-11-23 devnull 	last = 0;
 54 7a4ee46d 2003-11-23 devnull 	blocksize = ix->blocksize;
 55 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < ix->nsects; i++){
 56 7a4ee46d 2003-11-23 devnull 		is = sects[i];
 57 7a4ee46d 2003-11-23 devnull 		if(namecmp(ix->name, is->index) != 0
 58 7a4ee46d 2003-11-23 devnull 		|| is->blocksize != blocksize
 59 7a4ee46d 2003-11-23 devnull 		|| is->tabsize != tabsize
 60 7a4ee46d 2003-11-23 devnull 		|| namecmp(is->name, ix->smap[i].name) != 0
 61 7a4ee46d 2003-11-23 devnull 		|| is->start != ix->smap[i].start
 62 7a4ee46d 2003-11-23 devnull 		|| is->stop != ix->smap[i].stop
 63 7a4ee46d 2003-11-23 devnull 		|| last != is->start
 64 7a4ee46d 2003-11-23 devnull 		|| is->start > is->stop){
 65 7a4ee46d 2003-11-23 devnull 			seterr(ECorrupt, "inconsistent index sections in %s", ix->name);
 66 7a4ee46d 2003-11-23 devnull 			freeindex(ix);
 67 7a4ee46d 2003-11-23 devnull 			return nil;
 68 7a4ee46d 2003-11-23 devnull 		}
 69 7a4ee46d 2003-11-23 devnull 		last = is->stop;
 70 7a4ee46d 2003-11-23 devnull 	}
 71 7a4ee46d 2003-11-23 devnull 	ix->tabsize = tabsize;
 72 7a4ee46d 2003-11-23 devnull 	ix->buckets = last;
 73 7a4ee46d 2003-11-23 devnull 
 74 7a4ee46d 2003-11-23 devnull 	ix->div = (((u64int)1 << 32) + last - 1) / last;
 75 7a4ee46d 2003-11-23 devnull 	last = (((u64int)1 << 32) - 1) / ix->div + 1;
 76 7a4ee46d 2003-11-23 devnull 	if(last != ix->buckets){
 77 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "inconsistent math for buckets in %s", ix->name);
 78 7a4ee46d 2003-11-23 devnull 		freeindex(ix);
 79 7a4ee46d 2003-11-23 devnull 		return nil;
 80 7a4ee46d 2003-11-23 devnull 	}
 81 7a4ee46d 2003-11-23 devnull 
 82 7a4ee46d 2003-11-23 devnull 	ix->arenas = MKNZ(Arena*, ix->narenas);
 83 7a4ee46d 2003-11-23 devnull 	if(maparenas(ix->amap, ix->arenas, ix->narenas, ix->name) < 0){
 84 7a4ee46d 2003-11-23 devnull 		freeindex(ix);
 85 7a4ee46d 2003-11-23 devnull 		return nil;
 86 7a4ee46d 2003-11-23 devnull 	}
 87 7a4ee46d 2003-11-23 devnull 	return ix;
 88 7a4ee46d 2003-11-23 devnull }
 89 7a4ee46d 2003-11-23 devnull 
 90 7a4ee46d 2003-11-23 devnull int
 91 7a4ee46d 2003-11-23 devnull wbindex(Index *ix)
 92 7a4ee46d 2003-11-23 devnull {
 93 7a4ee46d 2003-11-23 devnull 	Fmt f;
 94 7a4ee46d 2003-11-23 devnull 	ZBlock *b;
 95 7a4ee46d 2003-11-23 devnull 	int i;
 96 7a4ee46d 2003-11-23 devnull 
 97 7a4ee46d 2003-11-23 devnull 	if(ix->nsects == 0){
 98 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "no sections in index %s", ix->name);
 99 7a4ee46d 2003-11-23 devnull 		return -1;
100 7a4ee46d 2003-11-23 devnull 	}
101 7a4ee46d 2003-11-23 devnull 	b = alloczblock(ix->tabsize, 1);
102 7a4ee46d 2003-11-23 devnull 	if(b == nil){
103 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "can't write index configuration: out of memory");
104 7a4ee46d 2003-11-23 devnull 		return -1;
105 7a4ee46d 2003-11-23 devnull 	}
106 7a4ee46d 2003-11-23 devnull 	fmtzbinit(&f, b);
107 7a4ee46d 2003-11-23 devnull 	if(outputindex(&f, ix) < 0){
108 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "can't make index configuration: table storage too small %d", ix->tabsize);
109 7a4ee46d 2003-11-23 devnull 		freezblock(b);
110 7a4ee46d 2003-11-23 devnull 		return -1;
111 7a4ee46d 2003-11-23 devnull 	}
112 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < ix->nsects; i++){
113 7a4ee46d 2003-11-23 devnull 		if(writepart(ix->sects[i]->part, ix->sects[i]->tabbase, b->data, ix->tabsize) < 0){
114 7a4ee46d 2003-11-23 devnull 			seterr(EOk, "can't write index: %r");
115 7a4ee46d 2003-11-23 devnull 			freezblock(b);
116 7a4ee46d 2003-11-23 devnull 			return -1;
117 7a4ee46d 2003-11-23 devnull 		}
118 7a4ee46d 2003-11-23 devnull 	}
119 7a4ee46d 2003-11-23 devnull 	freezblock(b);
120 7a4ee46d 2003-11-23 devnull 
121 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < ix->nsects; i++)
122 7a4ee46d 2003-11-23 devnull 		if(wbisect(ix->sects[i]) < 0)
123 7a4ee46d 2003-11-23 devnull 			return -1;
124 7a4ee46d 2003-11-23 devnull 
125 7a4ee46d 2003-11-23 devnull 	return 0;
126 7a4ee46d 2003-11-23 devnull }
127 7a4ee46d 2003-11-23 devnull 
128 7a4ee46d 2003-11-23 devnull /*
129 7a4ee46d 2003-11-23 devnull  * index: IndexMagic '\n' version '\n' name '\n' blocksize '\n' sections arenas
130 7a4ee46d 2003-11-23 devnull  * version, blocksize: u32int
131 7a4ee46d 2003-11-23 devnull  * name: max. ANameSize string
132 7a4ee46d 2003-11-23 devnull  * sections, arenas: AMap
133 7a4ee46d 2003-11-23 devnull  */
134 7a4ee46d 2003-11-23 devnull int
135 7a4ee46d 2003-11-23 devnull outputindex(Fmt *f, Index *ix)
136 7a4ee46d 2003-11-23 devnull {
137 7a4ee46d 2003-11-23 devnull 	if(fmtprint(f, "%s\n%ud\n%s\n%ud\n", IndexMagic, ix->version, ix->name, ix->blocksize) < 0
138 7a4ee46d 2003-11-23 devnull 	|| outputamap(f, ix->smap, ix->nsects) < 0
139 7a4ee46d 2003-11-23 devnull 	|| outputamap(f, ix->amap, ix->narenas) < 0)
140 7a4ee46d 2003-11-23 devnull 		return -1;
141 7a4ee46d 2003-11-23 devnull 	return 0;
142 7a4ee46d 2003-11-23 devnull }
143 7a4ee46d 2003-11-23 devnull 
144 7a4ee46d 2003-11-23 devnull int
145 7a4ee46d 2003-11-23 devnull parseindex(IFile *f, Index *ix)
146 7a4ee46d 2003-11-23 devnull {
147 7a4ee46d 2003-11-23 devnull 	AMapN amn;
148 7a4ee46d 2003-11-23 devnull 	u32int v;
149 7a4ee46d 2003-11-23 devnull 	char *s;
150 7a4ee46d 2003-11-23 devnull 
151 7a4ee46d 2003-11-23 devnull 	/*
152 7a4ee46d 2003-11-23 devnull 	 * magic
153 7a4ee46d 2003-11-23 devnull 	 */
154 7a4ee46d 2003-11-23 devnull 	s = ifileline(f);
155 7a4ee46d 2003-11-23 devnull 	if(s == nil || strcmp(s, IndexMagic) != 0){
156 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "bad index magic for %s", f->name);
157 7a4ee46d 2003-11-23 devnull 		return -1;
158 7a4ee46d 2003-11-23 devnull 	}
159 7a4ee46d 2003-11-23 devnull 
160 7a4ee46d 2003-11-23 devnull 	/*
161 7a4ee46d 2003-11-23 devnull 	 * version
162 7a4ee46d 2003-11-23 devnull 	 */
163 7a4ee46d 2003-11-23 devnull 	if(ifileu32int(f, &v) < 0){
164 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "syntax error: bad version number in %s", f->name);
165 7a4ee46d 2003-11-23 devnull 		return -1;
166 7a4ee46d 2003-11-23 devnull 	}
167 7a4ee46d 2003-11-23 devnull 	ix->version = v;
168 7a4ee46d 2003-11-23 devnull 	if(ix->version != IndexVersion){
169 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "bad version number in %s", f->name);
170 7a4ee46d 2003-11-23 devnull 		return -1;
171 7a4ee46d 2003-11-23 devnull 	}
172 7a4ee46d 2003-11-23 devnull 
173 7a4ee46d 2003-11-23 devnull 	/*
174 7a4ee46d 2003-11-23 devnull 	 * name
175 7a4ee46d 2003-11-23 devnull 	 */
176 7a4ee46d 2003-11-23 devnull 	if(ifilename(f, ix->name) < 0){
177 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "syntax error: bad index name in %s", f->name);
178 7a4ee46d 2003-11-23 devnull 		return -1;
179 7a4ee46d 2003-11-23 devnull 	}
180 7a4ee46d 2003-11-23 devnull 
181 7a4ee46d 2003-11-23 devnull 	/*
182 7a4ee46d 2003-11-23 devnull 	 * block size
183 7a4ee46d 2003-11-23 devnull 	 */
184 7a4ee46d 2003-11-23 devnull 	if(ifileu32int(f, &v) < 0){
185 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "syntax error: bad version number in %s", f->name);
186 7a4ee46d 2003-11-23 devnull 		return -1;
187 7a4ee46d 2003-11-23 devnull 	}
188 7a4ee46d 2003-11-23 devnull 	ix->blocksize = v;
189 7a4ee46d 2003-11-23 devnull 
190 7a4ee46d 2003-11-23 devnull 	if(parseamap(f, &amn) < 0)
191 7a4ee46d 2003-11-23 devnull 		return -1;
192 7a4ee46d 2003-11-23 devnull 	ix->nsects = amn.n;
193 7a4ee46d 2003-11-23 devnull 	ix->smap = amn.map;
194 7a4ee46d 2003-11-23 devnull 
195 7a4ee46d 2003-11-23 devnull 	if(parseamap(f, &amn) < 0)
196 7a4ee46d 2003-11-23 devnull 		return -1;
197 7a4ee46d 2003-11-23 devnull 	ix->narenas = amn.n;
198 7a4ee46d 2003-11-23 devnull 	ix->amap = amn.map;
199 7a4ee46d 2003-11-23 devnull 
200 7a4ee46d 2003-11-23 devnull 	return 0;
201 7a4ee46d 2003-11-23 devnull }
202 7a4ee46d 2003-11-23 devnull 
203 7a4ee46d 2003-11-23 devnull /*
204 7a4ee46d 2003-11-23 devnull  * initialize an entirely new index
205 7a4ee46d 2003-11-23 devnull  */
206 7a4ee46d 2003-11-23 devnull Index *
207 7a4ee46d 2003-11-23 devnull newindex(char *name, ISect **sects, int n)
208 7a4ee46d 2003-11-23 devnull {
209 7a4ee46d 2003-11-23 devnull 	Index *ix;
210 7a4ee46d 2003-11-23 devnull 	AMap *smap;
211 7a4ee46d 2003-11-23 devnull 	u64int nb;
212 7a4ee46d 2003-11-23 devnull 	u32int div, ub, xb, start, stop, blocksize, tabsize;
213 7a4ee46d 2003-11-23 devnull 	int i, j;
214 7a4ee46d 2003-11-23 devnull 
215 7a4ee46d 2003-11-23 devnull 	if(n < 1){
216 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "creating index with no index sections");
217 7a4ee46d 2003-11-23 devnull 		return nil;
218 7a4ee46d 2003-11-23 devnull 	}
219 7a4ee46d 2003-11-23 devnull 
220 7a4ee46d 2003-11-23 devnull 	/*
221 7a4ee46d 2003-11-23 devnull 	 * compute the total buckets available in the index,
222 7a4ee46d 2003-11-23 devnull 	 * and the total buckets which are used.
223 7a4ee46d 2003-11-23 devnull 	 */
224 7a4ee46d 2003-11-23 devnull 	nb = 0;
225 7a4ee46d 2003-11-23 devnull 	blocksize = sects[0]->blocksize;
226 7a4ee46d 2003-11-23 devnull 	tabsize = sects[0]->tabsize;
227 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < n; i++){
228 7a4ee46d 2003-11-23 devnull 		if(sects[i]->start != 0 || sects[i]->stop != 0
229 7a4ee46d 2003-11-23 devnull 		|| sects[i]->index[0] != '\0'){
230 7a4ee46d 2003-11-23 devnull 			seterr(EOk, "creating new index using non-empty section %s", sects[i]->name);
231 7a4ee46d 2003-11-23 devnull 			return nil;
232 7a4ee46d 2003-11-23 devnull 		}
233 7a4ee46d 2003-11-23 devnull 		if(blocksize != sects[i]->blocksize){
234 7a4ee46d 2003-11-23 devnull 			seterr(EOk, "mismatched block sizes in index sections");
235 7a4ee46d 2003-11-23 devnull 			return nil;
236 7a4ee46d 2003-11-23 devnull 		}
237 7a4ee46d 2003-11-23 devnull 		if(tabsize != sects[i]->tabsize){
238 7a4ee46d 2003-11-23 devnull 			seterr(EOk, "mismatched config table sizes in index sections");
239 7a4ee46d 2003-11-23 devnull 			return nil;
240 7a4ee46d 2003-11-23 devnull 		}
241 7a4ee46d 2003-11-23 devnull 		nb += sects[i]->blocks;
242 7a4ee46d 2003-11-23 devnull 	}
243 7a4ee46d 2003-11-23 devnull 
244 7a4ee46d 2003-11-23 devnull 	/*
245 7a4ee46d 2003-11-23 devnull 	 * check for duplicate names
246 7a4ee46d 2003-11-23 devnull 	 */
247 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < n; i++){
248 7a4ee46d 2003-11-23 devnull 		for(j = i + 1; j < n; j++){
249 7a4ee46d 2003-11-23 devnull 			if(namecmp(sects[i]->name, sects[j]->name) == 0){
250 7a4ee46d 2003-11-23 devnull 				seterr(EOk, "duplicate section name %s for index %s", sects[i]->name, name);
251 7a4ee46d 2003-11-23 devnull 				return nil;
252 7a4ee46d 2003-11-23 devnull 			}
253 7a4ee46d 2003-11-23 devnull 		}
254 7a4ee46d 2003-11-23 devnull 	}
255 7a4ee46d 2003-11-23 devnull 
256 7a4ee46d 2003-11-23 devnull 	if(nb >= ((u64int)1 << 32)){
257 7a4ee46d 2003-11-23 devnull 		seterr(EBug, "index too large");
258 7a4ee46d 2003-11-23 devnull 		return nil;
259 7a4ee46d 2003-11-23 devnull 	}
260 7a4ee46d 2003-11-23 devnull 	div = (((u64int)1 << 32) + nb - 1) / nb;
261 7a4ee46d 2003-11-23 devnull 	ub = (((u64int)1 << 32) - 1) / div + 1;
262 7a4ee46d 2003-11-23 devnull 	if(div < 100){
263 7a4ee46d 2003-11-23 devnull 		seterr(EBug, "index divisor too coarse");
264 7a4ee46d 2003-11-23 devnull 		return nil;
265 7a4ee46d 2003-11-23 devnull 	}
266 7a4ee46d 2003-11-23 devnull 	if(ub > nb){
267 7a4ee46d 2003-11-23 devnull 		seterr(EBug, "index initialization math wrong");
268 7a4ee46d 2003-11-23 devnull 		return nil;
269 7a4ee46d 2003-11-23 devnull 	}
270 7a4ee46d 2003-11-23 devnull 
271 7a4ee46d 2003-11-23 devnull 	/*
272 7a4ee46d 2003-11-23 devnull 	 * initialize each of the index sections
273 7a4ee46d 2003-11-23 devnull 	 * and the section map table
274 7a4ee46d 2003-11-23 devnull 	 */
275 7a4ee46d 2003-11-23 devnull 	smap = MKNZ(AMap, n);
276 7a4ee46d 2003-11-23 devnull 	if(smap == nil){
277 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "can't create new index: out of memory");
278 7a4ee46d 2003-11-23 devnull 		return nil;
279 7a4ee46d 2003-11-23 devnull 	}
280 7a4ee46d 2003-11-23 devnull 	xb = nb - ub;
281 7a4ee46d 2003-11-23 devnull 	start = 0;
282 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < n; i++){
283 7a4ee46d 2003-11-23 devnull 		stop = start + sects[i]->blocks - xb / n;
284 7a4ee46d 2003-11-23 devnull 		if(i == n - 1)
285 7a4ee46d 2003-11-23 devnull 			stop = ub;
286 7a4ee46d 2003-11-23 devnull 		sects[i]->start = start;
287 7a4ee46d 2003-11-23 devnull 		sects[i]->stop = stop;
288 7a4ee46d 2003-11-23 devnull 		namecp(sects[i]->index, name);
289 7a4ee46d 2003-11-23 devnull 
290 7a4ee46d 2003-11-23 devnull 		smap[i].start = start;
291 7a4ee46d 2003-11-23 devnull 		smap[i].stop = stop;
292 7a4ee46d 2003-11-23 devnull 		namecp(smap[i].name, sects[i]->name);
293 7a4ee46d 2003-11-23 devnull 		start = stop;
294 7a4ee46d 2003-11-23 devnull 	}
295 7a4ee46d 2003-11-23 devnull 
296 7a4ee46d 2003-11-23 devnull 	/*
297 7a4ee46d 2003-11-23 devnull 	 * initialize the index itself
298 7a4ee46d 2003-11-23 devnull 	 */
299 7a4ee46d 2003-11-23 devnull 	ix = MKZ(Index);
300 7a4ee46d 2003-11-23 devnull 	if(ix == nil){
301 7a4ee46d 2003-11-23 devnull 		seterr(EOk, "can't create new index: out of memory");
302 7a4ee46d 2003-11-23 devnull 		free(smap);
303 7a4ee46d 2003-11-23 devnull 		return nil;
304 7a4ee46d 2003-11-23 devnull 	}
305 7a4ee46d 2003-11-23 devnull 	ix->version = IndexVersion;
306 7a4ee46d 2003-11-23 devnull 	namecp(ix->name, name);
307 7a4ee46d 2003-11-23 devnull 	ix->sects = sects;
308 7a4ee46d 2003-11-23 devnull 	ix->smap = smap;
309 7a4ee46d 2003-11-23 devnull 	ix->nsects = n;
310 7a4ee46d 2003-11-23 devnull 	ix->blocksize = blocksize;
311 7a4ee46d 2003-11-23 devnull 	ix->div = div;
312 7a4ee46d 2003-11-23 devnull 	ix->buckets = ub;
313 7a4ee46d 2003-11-23 devnull 	ix->tabsize = tabsize;
314 7a4ee46d 2003-11-23 devnull 	return ix;
315 7a4ee46d 2003-11-23 devnull }
316 7a4ee46d 2003-11-23 devnull 
317 7a4ee46d 2003-11-23 devnull ISect*
318 7a4ee46d 2003-11-23 devnull initisect(Part *part)
319 7a4ee46d 2003-11-23 devnull {
320 7a4ee46d 2003-11-23 devnull 	ISect *is;
321 7a4ee46d 2003-11-23 devnull 	ZBlock *b;
322 7a4ee46d 2003-11-23 devnull 	int ok;
323 7a4ee46d 2003-11-23 devnull 
324 7a4ee46d 2003-11-23 devnull 	b = alloczblock(HeadSize, 0);
325 7a4ee46d 2003-11-23 devnull 	if(b == nil || readpart(part, PartBlank, b->data, HeadSize) < 0){
326 7a4ee46d 2003-11-23 devnull 		seterr(EAdmin, "can't read index section header: %r");
327 7a4ee46d 2003-11-23 devnull 		return nil;
328 7a4ee46d 2003-11-23 devnull 	}
329 7a4ee46d 2003-11-23 devnull 
330 7a4ee46d 2003-11-23 devnull 	is = MKZ(ISect);
331 7a4ee46d 2003-11-23 devnull 	if(is == nil){
332 7a4ee46d 2003-11-23 devnull 		freezblock(b);
333 7a4ee46d 2003-11-23 devnull 		return nil;
334 7a4ee46d 2003-11-23 devnull 	}
335 7a4ee46d 2003-11-23 devnull 	is->part = part;
336 7a4ee46d 2003-11-23 devnull 	ok = unpackisect(is, b->data);
337 7a4ee46d 2003-11-23 devnull 	freezblock(b);
338 7a4ee46d 2003-11-23 devnull 	if(ok < 0){
339 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "corrupted index section header: %r");
340 7a4ee46d 2003-11-23 devnull 		freeisect(is);
341 7a4ee46d 2003-11-23 devnull 		return nil;
342 7a4ee46d 2003-11-23 devnull 	}
343 7a4ee46d 2003-11-23 devnull 
344 7a4ee46d 2003-11-23 devnull 	if(is->version != ISectVersion){
345 7a4ee46d 2003-11-23 devnull 		seterr(EAdmin, "unknown index section version %d", is->version);
346 7a4ee46d 2003-11-23 devnull 		freeisect(is);
347 7a4ee46d 2003-11-23 devnull 		return nil;
348 7a4ee46d 2003-11-23 devnull 	}
349 7a4ee46d 2003-11-23 devnull 
350 7a4ee46d 2003-11-23 devnull 	return initisect1(is);
351 7a4ee46d 2003-11-23 devnull }
352 7a4ee46d 2003-11-23 devnull 
353 7a4ee46d 2003-11-23 devnull ISect*
354 7a4ee46d 2003-11-23 devnull newisect(Part *part, char *name, u32int blocksize, u32int tabsize)
355 7a4ee46d 2003-11-23 devnull {
356 7a4ee46d 2003-11-23 devnull 	ISect *is;
357 7a4ee46d 2003-11-23 devnull 	u32int tabbase;
358 7a4ee46d 2003-11-23 devnull 
359 7a4ee46d 2003-11-23 devnull 	is = MKZ(ISect);
360 7a4ee46d 2003-11-23 devnull 	if(is == nil)
361 7a4ee46d 2003-11-23 devnull 		return nil;
362 7a4ee46d 2003-11-23 devnull 
363 7a4ee46d 2003-11-23 devnull 	namecp(is->name, name);
364 7a4ee46d 2003-11-23 devnull 	is->version = ISectVersion;
365 7a4ee46d 2003-11-23 devnull 	is->part = part;
366 7a4ee46d 2003-11-23 devnull 	is->blocksize = blocksize;
367 7a4ee46d 2003-11-23 devnull 	is->start = 0;
368 7a4ee46d 2003-11-23 devnull 	is->stop = 0;
369 7a4ee46d 2003-11-23 devnull 	tabbase = (PartBlank + HeadSize + blocksize - 1) & ~(blocksize - 1);
370 7a4ee46d 2003-11-23 devnull 	is->blockbase = (tabbase + tabsize + blocksize - 1) & ~(blocksize - 1);
371 7a4ee46d 2003-11-23 devnull 	is->blocks = is->part->size / blocksize - is->blockbase / blocksize;
372 7a4ee46d 2003-11-23 devnull 
373 7a4ee46d 2003-11-23 devnull 	is = initisect1(is);
374 7a4ee46d 2003-11-23 devnull 	if(is == nil)
375 7a4ee46d 2003-11-23 devnull 		return nil;
376 7a4ee46d 2003-11-23 devnull 
377 7a4ee46d 2003-11-23 devnull 	return is;
378 7a4ee46d 2003-11-23 devnull }
379 7a4ee46d 2003-11-23 devnull 
380 7a4ee46d 2003-11-23 devnull /*
381 7a4ee46d 2003-11-23 devnull  * initialize the computed paramaters for an index
382 7a4ee46d 2003-11-23 devnull  */
383 7a4ee46d 2003-11-23 devnull static ISect*
384 7a4ee46d 2003-11-23 devnull initisect1(ISect *is)
385 7a4ee46d 2003-11-23 devnull {
386 7a4ee46d 2003-11-23 devnull 	u64int v;
387 7a4ee46d 2003-11-23 devnull 
388 7a4ee46d 2003-11-23 devnull 	is->buckmax = (is->blocksize - IBucketSize) / IEntrySize;
389 7a4ee46d 2003-11-23 devnull 	is->blocklog = u64log2(is->blocksize);
390 7a4ee46d 2003-11-23 devnull 	if(is->blocksize != (1 << is->blocklog)){
391 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "illegal non-power-of-2 bucket size %d\n", is->blocksize);
392 7a4ee46d 2003-11-23 devnull 		freeisect(is);
393 7a4ee46d 2003-11-23 devnull 		return nil;
394 7a4ee46d 2003-11-23 devnull 	}
395 7a4ee46d 2003-11-23 devnull 	partblocksize(is->part, is->blocksize);
396 7a4ee46d 2003-11-23 devnull 	is->tabbase = (PartBlank + HeadSize + is->blocksize - 1) & ~(is->blocksize - 1);
397 7a4ee46d 2003-11-23 devnull 	if(is->tabbase >= is->blockbase){
398 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "index section config table overlaps bucket storage");
399 7a4ee46d 2003-11-23 devnull 		freeisect(is);
400 7a4ee46d 2003-11-23 devnull 		return nil;
401 7a4ee46d 2003-11-23 devnull 	}
402 7a4ee46d 2003-11-23 devnull 	is->tabsize = is->blockbase - is->tabbase;
403 7a4ee46d 2003-11-23 devnull 	v = is->part->size & ~(u64int)(is->blocksize - 1);
404 7a4ee46d 2003-11-23 devnull 	if(is->blockbase + (u64int)is->blocks * is->blocksize != v){
405 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "invalid blocks in index section %s", is->name);
406 7a4ee46d 2003-11-23 devnull //ZZZZZZZZZ
407 7a4ee46d 2003-11-23 devnull //		freeisect(is);
408 7a4ee46d 2003-11-23 devnull //		return nil;
409 7a4ee46d 2003-11-23 devnull 	}
410 7a4ee46d 2003-11-23 devnull 
411 7a4ee46d 2003-11-23 devnull 	if(is->stop - is->start > is->blocks){
412 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "index section overflows available space");
413 7a4ee46d 2003-11-23 devnull 		freeisect(is);
414 7a4ee46d 2003-11-23 devnull 		return nil;
415 7a4ee46d 2003-11-23 devnull 	}
416 7a4ee46d 2003-11-23 devnull 	if(is->start > is->stop){
417 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "invalid index section range");
418 7a4ee46d 2003-11-23 devnull 		freeisect(is);
419 7a4ee46d 2003-11-23 devnull 		return nil;
420 7a4ee46d 2003-11-23 devnull 	}
421 7a4ee46d 2003-11-23 devnull 
422 7a4ee46d 2003-11-23 devnull 	return is;
423 7a4ee46d 2003-11-23 devnull }
424 7a4ee46d 2003-11-23 devnull 
425 7a4ee46d 2003-11-23 devnull int
426 7a4ee46d 2003-11-23 devnull wbisect(ISect *is)
427 7a4ee46d 2003-11-23 devnull {
428 7a4ee46d 2003-11-23 devnull 	ZBlock *b;
429 7a4ee46d 2003-11-23 devnull 
430 7a4ee46d 2003-11-23 devnull 	b = alloczblock(HeadSize, 1);
431 7a4ee46d 2003-11-23 devnull 	if(b == nil)
432 7a4ee46d 2003-11-23 devnull //ZZZ set error?
433 7a4ee46d 2003-11-23 devnull 		return -1;
434 7a4ee46d 2003-11-23 devnull 
435 7a4ee46d 2003-11-23 devnull 	if(packisect(is, b->data) < 0){
436 7a4ee46d 2003-11-23 devnull 		seterr(ECorrupt, "can't make index section header: %r");
437 7a4ee46d 2003-11-23 devnull 		freezblock(b);
438 7a4ee46d 2003-11-23 devnull 		return -1;
439 7a4ee46d 2003-11-23 devnull 	}
440 7a4ee46d 2003-11-23 devnull 	if(writepart(is->part, PartBlank, b->data, HeadSize) < 0){
441 7a4ee46d 2003-11-23 devnull 		seterr(EAdmin, "can't write index section header: %r");
442 7a4ee46d 2003-11-23 devnull 		freezblock(b);
443 7a4ee46d 2003-11-23 devnull 		return -1;
444 7a4ee46d 2003-11-23 devnull 	}
445 7a4ee46d 2003-11-23 devnull 	freezblock(b);
446 7a4ee46d 2003-11-23 devnull 
447 7a4ee46d 2003-11-23 devnull 	return 0;
448 7a4ee46d 2003-11-23 devnull }
449 7a4ee46d 2003-11-23 devnull 
450 7a4ee46d 2003-11-23 devnull void
451 7a4ee46d 2003-11-23 devnull freeisect(ISect *is)
452 7a4ee46d 2003-11-23 devnull {
453 7a4ee46d 2003-11-23 devnull 	if(is == nil)
454 7a4ee46d 2003-11-23 devnull 		return;
455 7a4ee46d 2003-11-23 devnull 	free(is);
456 7a4ee46d 2003-11-23 devnull }
457 7a4ee46d 2003-11-23 devnull 
458 7a4ee46d 2003-11-23 devnull void
459 7a4ee46d 2003-11-23 devnull freeindex(Index *ix)
460 7a4ee46d 2003-11-23 devnull {
461 7a4ee46d 2003-11-23 devnull 	int i;
462 7a4ee46d 2003-11-23 devnull 
463 7a4ee46d 2003-11-23 devnull 	if(ix == nil)
464 7a4ee46d 2003-11-23 devnull 		return;
465 7a4ee46d 2003-11-23 devnull 	free(ix->amap);
466 7a4ee46d 2003-11-23 devnull 	free(ix->arenas);
467 7a4ee46d 2003-11-23 devnull 	if(ix->sects)
468 7a4ee46d 2003-11-23 devnull 		for(i = 0; i < ix->nsects; i++)
469 7a4ee46d 2003-11-23 devnull 			freeisect(ix->sects[i]);
470 7a4ee46d 2003-11-23 devnull 	free(ix->sects);
471 7a4ee46d 2003-11-23 devnull 	free(ix->smap);
472 7a4ee46d 2003-11-23 devnull 	free(ix);
473 7a4ee46d 2003-11-23 devnull }
474 7a4ee46d 2003-11-23 devnull 
475 7a4ee46d 2003-11-23 devnull /*
476 7a4ee46d 2003-11-23 devnull  * write a clump to an available arena in the index
477 7a4ee46d 2003-11-23 devnull  * and return the address of the clump within the index.
478 7a4ee46d 2003-11-23 devnull ZZZ question: should this distinguish between an arena
479 7a4ee46d 2003-11-23 devnull filling up and real errors writing the clump?
480 7a4ee46d 2003-11-23 devnull  */
481 7a4ee46d 2003-11-23 devnull u64int
482 7a4ee46d 2003-11-23 devnull writeiclump(Index *ix, Clump *c, u8int *clbuf)
483 7a4ee46d 2003-11-23 devnull {
484 7a4ee46d 2003-11-23 devnull 	u64int a;
485 7a4ee46d 2003-11-23 devnull 	int i;
486 7a4ee46d 2003-11-23 devnull 
487 7a4ee46d 2003-11-23 devnull 	for(i = ix->mapalloc; i < ix->narenas; i++){
488 7a4ee46d 2003-11-23 devnull 		a = writeaclump(ix->arenas[i], c, clbuf);
489 7a4ee46d 2003-11-23 devnull 		if(a != TWID64)
490 7a4ee46d 2003-11-23 devnull 			return a + ix->amap[i].start;
491 7a4ee46d 2003-11-23 devnull 	}
492 7a4ee46d 2003-11-23 devnull 
493 7a4ee46d 2003-11-23 devnull 	seterr(EAdmin, "no space left in arenas");
494 7a4ee46d 2003-11-23 devnull 	return -1;
495 7a4ee46d 2003-11-23 devnull }
496 7a4ee46d 2003-11-23 devnull 
497 7a4ee46d 2003-11-23 devnull /*
498 7a4ee46d 2003-11-23 devnull  * convert an arena index to an relative address address
499 7a4ee46d 2003-11-23 devnull  */
500 7a4ee46d 2003-11-23 devnull Arena*
501 7a4ee46d 2003-11-23 devnull amapitoa(Index *ix, u64int a, u64int *aa)
502 7a4ee46d 2003-11-23 devnull {
503 7a4ee46d 2003-11-23 devnull 	int i, r, l, m;
504 7a4ee46d 2003-11-23 devnull 
505 7a4ee46d 2003-11-23 devnull 	l = 1;
506 7a4ee46d 2003-11-23 devnull 	r = ix->narenas - 1;
507 7a4ee46d 2003-11-23 devnull 	while(l <= r){
508 7a4ee46d 2003-11-23 devnull 		m = (r + l) / 2;
509 7a4ee46d 2003-11-23 devnull 		if(ix->amap[m].start <= a)
510 7a4ee46d 2003-11-23 devnull 			l = m + 1;
511 7a4ee46d 2003-11-23 devnull 		else
512 7a4ee46d 2003-11-23 devnull 			r = m - 1;
513 7a4ee46d 2003-11-23 devnull 	}
514 7a4ee46d 2003-11-23 devnull 	l--;
515 7a4ee46d 2003-11-23 devnull 
516 7a4ee46d 2003-11-23 devnull 	if(a > ix->amap[l].stop){
517 7a4ee46d 2003-11-23 devnull for(i=0; i<ix->narenas; i++)
518 7a4ee46d 2003-11-23 devnull 	print("arena %d: %llux - %llux\n", i, ix->amap[i].start, ix->amap[i].stop);
519 7a4ee46d 2003-11-23 devnull print("want arena %d for %llux\n", l, a);
520 7a4ee46d 2003-11-23 devnull 		seterr(ECrash, "unmapped address passed to amapitoa");
521 7a4ee46d 2003-11-23 devnull 		return nil;
522 7a4ee46d 2003-11-23 devnull 	}
523 7a4ee46d 2003-11-23 devnull 
524 7a4ee46d 2003-11-23 devnull 	if(ix->arenas[l] == nil){
525 7a4ee46d 2003-11-23 devnull 		seterr(ECrash, "unmapped arena selected in amapitoa");
526 7a4ee46d 2003-11-23 devnull 		return nil;
527 7a4ee46d 2003-11-23 devnull 	}
528 7a4ee46d 2003-11-23 devnull 	*aa = a - ix->amap[l].start;
529 7a4ee46d 2003-11-23 devnull 	return ix->arenas[l];
530 7a4ee46d 2003-11-23 devnull }
531 7a4ee46d 2003-11-23 devnull 
532 7a4ee46d 2003-11-23 devnull int
533 7a4ee46d 2003-11-23 devnull iaddrcmp(IAddr *ia1, IAddr *ia2)
534 7a4ee46d 2003-11-23 devnull {
535 7a4ee46d 2003-11-23 devnull 	return ia1->type != ia2->type
536 7a4ee46d 2003-11-23 devnull 		|| ia1->size != ia2->size
537 7a4ee46d 2003-11-23 devnull 		|| ia1->blocks != ia2->blocks
538 7a4ee46d 2003-11-23 devnull 		|| ia1->addr != ia2->addr;
539 7a4ee46d 2003-11-23 devnull }
540 7a4ee46d 2003-11-23 devnull 
541 7a4ee46d 2003-11-23 devnull /*
542 7a4ee46d 2003-11-23 devnull  * lookup the score in the partition
543 7a4ee46d 2003-11-23 devnull  *
544 7a4ee46d 2003-11-23 devnull  * nothing needs to be explicitly locked:
545 7a4ee46d 2003-11-23 devnull  * only static parts of ix are used, and
546 7a4ee46d 2003-11-23 devnull  * the bucket is locked by the DBlock lock.
547 7a4ee46d 2003-11-23 devnull  */
548 7a4ee46d 2003-11-23 devnull int
549 7a4ee46d 2003-11-23 devnull loadientry(Index *ix, u8int *score, int type, IEntry *ie)
550 7a4ee46d 2003-11-23 devnull {
551 7a4ee46d 2003-11-23 devnull 	ISect *is;
552 7a4ee46d 2003-11-23 devnull 	DBlock *b;
553 7a4ee46d 2003-11-23 devnull 	IBucket ib;
554 7a4ee46d 2003-11-23 devnull 	u32int buck;
555 7a4ee46d 2003-11-23 devnull 	int h, ok;
556 7a4ee46d 2003-11-23 devnull 
557 7a4ee46d 2003-11-23 devnull fprint(2, "loadientry %V %d\n", score, type);
558 7a4ee46d 2003-11-23 devnull 	buck = hashbits(score, 32) / ix->div;
559 7a4ee46d 2003-11-23 devnull 	ok = -1;
560 7a4ee46d 2003-11-23 devnull 	for(;;){
561 7a4ee46d 2003-11-23 devnull 		qlock(&stats.lock);
562 7a4ee46d 2003-11-23 devnull 		stats.indexreads++;
563 7a4ee46d 2003-11-23 devnull 		qunlock(&stats.lock);
564 7a4ee46d 2003-11-23 devnull 		is = findisect(ix, buck);
565 7a4ee46d 2003-11-23 devnull 		if(is == nil){
566 7a4ee46d 2003-11-23 devnull 			seterr(EAdmin, "bad math in loadientry");
567 7a4ee46d 2003-11-23 devnull 			return -1;
568 7a4ee46d 2003-11-23 devnull 		}
569 7a4ee46d 2003-11-23 devnull 		buck -= is->start;
570 7a4ee46d 2003-11-23 devnull 		b = getdblock(is->part, is->blockbase + ((u64int)buck << is->blocklog), 1);
571 7a4ee46d 2003-11-23 devnull 		if(b == nil)
572 7a4ee46d 2003-11-23 devnull 			break;
573 7a4ee46d 2003-11-23 devnull 
574 7a4ee46d 2003-11-23 devnull 		unpackibucket(&ib, b->data);
575 7a4ee46d 2003-11-23 devnull 		if(okibucket(&ib, is) < 0)
576 7a4ee46d 2003-11-23 devnull 			break;
577 7a4ee46d 2003-11-23 devnull 
578 7a4ee46d 2003-11-23 devnull 		h = bucklook(score, type, ib.data, ib.n);
579 7a4ee46d 2003-11-23 devnull 		if(h & 1){
580 7a4ee46d 2003-11-23 devnull 			h ^= 1;
581 7a4ee46d 2003-11-23 devnull 			unpackientry(ie, &ib.data[h]);
582 7a4ee46d 2003-11-23 devnull 			ok = 0;
583 7a4ee46d 2003-11-23 devnull 			break;
584 7a4ee46d 2003-11-23 devnull 		}
585 7a4ee46d 2003-11-23 devnull 
586 7a4ee46d 2003-11-23 devnull 		break;
587 7a4ee46d 2003-11-23 devnull 	}
588 7a4ee46d 2003-11-23 devnull 	putdblock(b);
589 7a4ee46d 2003-11-23 devnull 	return ok;
590 7a4ee46d 2003-11-23 devnull }
591 7a4ee46d 2003-11-23 devnull 
592 7a4ee46d 2003-11-23 devnull /*
593 7a4ee46d 2003-11-23 devnull  * insert or update an index entry into the appropriate bucket
594 7a4ee46d 2003-11-23 devnull  */
595 7a4ee46d 2003-11-23 devnull int
596 7a4ee46d 2003-11-23 devnull storeientry(Index *ix, IEntry *ie)
597 7a4ee46d 2003-11-23 devnull {
598 7a4ee46d 2003-11-23 devnull 	ISect *is;
599 7a4ee46d 2003-11-23 devnull 	DBlock *b;
600 7a4ee46d 2003-11-23 devnull 	IBucket ib;
601 7a4ee46d 2003-11-23 devnull 	u32int buck;
602 7a4ee46d 2003-11-23 devnull 	int h, ok;
603 7a4ee46d 2003-11-23 devnull 
604 7a4ee46d 2003-11-23 devnull 	buck = hashbits(ie->score, 32) / ix->div;
605 7a4ee46d 2003-11-23 devnull 	ok = 0;
606 7a4ee46d 2003-11-23 devnull 	for(;;){
607 7a4ee46d 2003-11-23 devnull 		qlock(&stats.lock);
608 7a4ee46d 2003-11-23 devnull 		stats.indexwreads++;
609 7a4ee46d 2003-11-23 devnull 		qunlock(&stats.lock);
610 7a4ee46d 2003-11-23 devnull 		is = findisect(ix, buck);
611 7a4ee46d 2003-11-23 devnull 		if(is == nil){
612 7a4ee46d 2003-11-23 devnull 			seterr(EAdmin, "bad math in storeientry");
613 7a4ee46d 2003-11-23 devnull 			return -1;
614 7a4ee46d 2003-11-23 devnull 		}
615 7a4ee46d 2003-11-23 devnull 		buck -= is->start;
616 7a4ee46d 2003-11-23 devnull 		b = getdblock(is->part, is->blockbase + ((u64int)buck << is->blocklog), 1);
617 7a4ee46d 2003-11-23 devnull 		if(b == nil)
618 7a4ee46d 2003-11-23 devnull 			break;
619 7a4ee46d 2003-11-23 devnull 
620 7a4ee46d 2003-11-23 devnull 		unpackibucket(&ib, b->data);
621 7a4ee46d 2003-11-23 devnull 		if(okibucket(&ib, is) < 0)
622 7a4ee46d 2003-11-23 devnull 			break;
623 7a4ee46d 2003-11-23 devnull 
624 7a4ee46d 2003-11-23 devnull 		h = bucklook(ie->score, ie->ia.type, ib.data, ib.n);
625 7a4ee46d 2003-11-23 devnull 		if(h & 1){
626 7a4ee46d 2003-11-23 devnull 			h ^= 1;
627 7a4ee46d 2003-11-23 devnull 			packientry(ie, &ib.data[h]);
628 7a4ee46d 2003-11-23 devnull 			ok = writebucket(is, buck, &ib, b);
629 7a4ee46d 2003-11-23 devnull 			break;
630 7a4ee46d 2003-11-23 devnull 		}
631 7a4ee46d 2003-11-23 devnull 
632 7a4ee46d 2003-11-23 devnull 		if(ib.n < is->buckmax){
633 7a4ee46d 2003-11-23 devnull 			memmove(&ib.data[h + IEntrySize], &ib.data[h], ib.n * IEntrySize - h);
634 7a4ee46d 2003-11-23 devnull 			ib.n++;
635 7a4ee46d 2003-11-23 devnull 
636 7a4ee46d 2003-11-23 devnull 			packientry(ie, &ib.data[h]);
637 7a4ee46d 2003-11-23 devnull 			ok = writebucket(is, buck, &ib, b);
638 7a4ee46d 2003-11-23 devnull 			break;
639 7a4ee46d 2003-11-23 devnull 		}
640 7a4ee46d 2003-11-23 devnull 
641 7a4ee46d 2003-11-23 devnull 		break;
642 7a4ee46d 2003-11-23 devnull 	}
643 7a4ee46d 2003-11-23 devnull 
644 7a4ee46d 2003-11-23 devnull 	putdblock(b);
645 7a4ee46d 2003-11-23 devnull 	return ok;
646 7a4ee46d 2003-11-23 devnull }
647 7a4ee46d 2003-11-23 devnull 
648 7a4ee46d 2003-11-23 devnull static int
649 7a4ee46d 2003-11-23 devnull writebucket(ISect *is, u32int buck, IBucket *ib, DBlock *b)
650 7a4ee46d 2003-11-23 devnull {
651 7a4ee46d 2003-11-23 devnull 	if(buck >= is->blocks)
652 7a4ee46d 2003-11-23 devnull 		seterr(EAdmin, "index write out of bounds: %d >= %d\n",
653 7a4ee46d 2003-11-23 devnull 				buck, is->blocks);
654 7a4ee46d 2003-11-23 devnull 	qlock(&stats.lock);
655 7a4ee46d 2003-11-23 devnull 	stats.indexwrites++;
656 7a4ee46d 2003-11-23 devnull 	qunlock(&stats.lock);
657 7a4ee46d 2003-11-23 devnull 	packibucket(ib, b->data);
658 7a4ee46d 2003-11-23 devnull 	return writepart(is->part, is->blockbase + ((u64int)buck << is->blocklog), b->data, is->blocksize);
659 7a4ee46d 2003-11-23 devnull }
660 7a4ee46d 2003-11-23 devnull 
661 7a4ee46d 2003-11-23 devnull /*
662 7a4ee46d 2003-11-23 devnull  * find the number of the index section holding score
663 7a4ee46d 2003-11-23 devnull  */
664 7a4ee46d 2003-11-23 devnull int
665 7a4ee46d 2003-11-23 devnull indexsect(Index *ix, u8int *score)
666 7a4ee46d 2003-11-23 devnull {
667 7a4ee46d 2003-11-23 devnull 	u32int buck;
668 7a4ee46d 2003-11-23 devnull 	int r, l, m;
669 7a4ee46d 2003-11-23 devnull 
670 7a4ee46d 2003-11-23 devnull 	buck = hashbits(score, 32) / ix->div;
671 7a4ee46d 2003-11-23 devnull 	l = 1;
672 7a4ee46d 2003-11-23 devnull 	r = ix->nsects - 1;
673 7a4ee46d 2003-11-23 devnull 	while(l <= r){
674 7a4ee46d 2003-11-23 devnull 		m = (r + l) >> 1;
675 7a4ee46d 2003-11-23 devnull 		if(ix->sects[m]->start <= buck)
676 7a4ee46d 2003-11-23 devnull 			l = m + 1;
677 7a4ee46d 2003-11-23 devnull 		else
678 7a4ee46d 2003-11-23 devnull 			r = m - 1;
679 7a4ee46d 2003-11-23 devnull 	}
680 7a4ee46d 2003-11-23 devnull 	return l - 1;
681 7a4ee46d 2003-11-23 devnull }
682 7a4ee46d 2003-11-23 devnull 
683 7a4ee46d 2003-11-23 devnull /*
684 7a4ee46d 2003-11-23 devnull  * find the index section which holds buck
685 7a4ee46d 2003-11-23 devnull  */
686 7a4ee46d 2003-11-23 devnull ISect*
687 7a4ee46d 2003-11-23 devnull findisect(Index *ix, u32int buck)
688 7a4ee46d 2003-11-23 devnull {
689 7a4ee46d 2003-11-23 devnull 	ISect *is;
690 7a4ee46d 2003-11-23 devnull 	int r, l, m;
691 7a4ee46d 2003-11-23 devnull 
692 7a4ee46d 2003-11-23 devnull 	l = 1;
693 7a4ee46d 2003-11-23 devnull 	r = ix->nsects - 1;
694 7a4ee46d 2003-11-23 devnull 	while(l <= r){
695 7a4ee46d 2003-11-23 devnull 		m = (r + l) >> 1;
696 7a4ee46d 2003-11-23 devnull 		if(ix->sects[m]->start <= buck)
697 7a4ee46d 2003-11-23 devnull 			l = m + 1;
698 7a4ee46d 2003-11-23 devnull 		else
699 7a4ee46d 2003-11-23 devnull 			r = m - 1;
700 7a4ee46d 2003-11-23 devnull 	}
701 7a4ee46d 2003-11-23 devnull 	is = ix->sects[l - 1];
702 7a4ee46d 2003-11-23 devnull 	if(is->start <= buck && is->stop > buck)
703 7a4ee46d 2003-11-23 devnull 		return is;
704 7a4ee46d 2003-11-23 devnull 	return nil;
705 7a4ee46d 2003-11-23 devnull }
706 7a4ee46d 2003-11-23 devnull 
707 7a4ee46d 2003-11-23 devnull static int
708 7a4ee46d 2003-11-23 devnull okibucket(IBucket *ib, ISect *is)
709 7a4ee46d 2003-11-23 devnull {
710 7a4ee46d 2003-11-23 devnull 	if(ib->n <= is->buckmax && (ib->next == 0 || ib->next >= is->start && ib->next < is->stop))
711 7a4ee46d 2003-11-23 devnull 		return 0;
712 7a4ee46d 2003-11-23 devnull 
713 7a4ee46d 2003-11-23 devnull 	seterr(EICorrupt, "corrupted disk index bucket: n=%ud max=%ud, next=%lud range=[%lud,%lud)",
714 7a4ee46d 2003-11-23 devnull 		ib->n, is->buckmax, ib->next, is->start, is->stop);
715 7a4ee46d 2003-11-23 devnull 	return -1;
716 7a4ee46d 2003-11-23 devnull }
717 7a4ee46d 2003-11-23 devnull 
718 7a4ee46d 2003-11-23 devnull /*
719 7a4ee46d 2003-11-23 devnull  * look for score within data;
720 7a4ee46d 2003-11-23 devnull  * return 1 | byte index of matching index,
721 7a4ee46d 2003-11-23 devnull  * or 0 | index of least element > score
722 7a4ee46d 2003-11-23 devnull  */
723 7a4ee46d 2003-11-23 devnull static int
724 7a4ee46d 2003-11-23 devnull bucklook(u8int *score, int otype, u8int *data, int n)
725 7a4ee46d 2003-11-23 devnull {
726 7a4ee46d 2003-11-23 devnull 	int i, r, l, m, h, c, cc, type;
727 7a4ee46d 2003-11-23 devnull 
728 7a4ee46d 2003-11-23 devnull 	type = vttodisktype(otype);
729 7a4ee46d 2003-11-23 devnull fprint(2, "bucklook %V %d->%d %d\n", score, otype, type, n);
730 7a4ee46d 2003-11-23 devnull 	l = 0;
731 7a4ee46d 2003-11-23 devnull 	r = n - 1;
732 7a4ee46d 2003-11-23 devnull 	while(l <= r){
733 7a4ee46d 2003-11-23 devnull 		m = (r + l) >> 1;
734 7a4ee46d 2003-11-23 devnull 		h = m * IEntrySize;
735 7a4ee46d 2003-11-23 devnull fprint(2, "perhaps %V %d\n", data+h, data[h+IEntryTypeOff]);
736 7a4ee46d 2003-11-23 devnull 		for(i = 0; i < VtScoreSize; i++){
737 7a4ee46d 2003-11-23 devnull 			c = score[i];
738 7a4ee46d 2003-11-23 devnull 			cc = data[h + i];
739 7a4ee46d 2003-11-23 devnull 			if(c != cc){
740 7a4ee46d 2003-11-23 devnull 				if(c > cc)
741 7a4ee46d 2003-11-23 devnull 					l = m + 1;
742 7a4ee46d 2003-11-23 devnull 				else
743 7a4ee46d 2003-11-23 devnull 					r = m - 1;
744 7a4ee46d 2003-11-23 devnull 				goto cont;
745 7a4ee46d 2003-11-23 devnull 			}
746 7a4ee46d 2003-11-23 devnull 		}
747 7a4ee46d 2003-11-23 devnull 		cc = data[h + IEntryTypeOff];
748 7a4ee46d 2003-11-23 devnull 		if(type != cc){
749 7a4ee46d 2003-11-23 devnull 			if(type > cc)
750 7a4ee46d 2003-11-23 devnull 				l = m + 1;
751 7a4ee46d 2003-11-23 devnull 			else
752 7a4ee46d 2003-11-23 devnull 				r = m - 1;
753 7a4ee46d 2003-11-23 devnull 			goto cont;
754 7a4ee46d 2003-11-23 devnull 		}
755 7a4ee46d 2003-11-23 devnull 		return h | 1;
756 7a4ee46d 2003-11-23 devnull 	cont:;
757 7a4ee46d 2003-11-23 devnull 	}
758 7a4ee46d 2003-11-23 devnull 
759 7a4ee46d 2003-11-23 devnull 	return l * IEntrySize;
760 7a4ee46d 2003-11-23 devnull }
761 7a4ee46d 2003-11-23 devnull 
762 7a4ee46d 2003-11-23 devnull /*
763 7a4ee46d 2003-11-23 devnull  * compare two IEntries; consistent with bucklook
764 7a4ee46d 2003-11-23 devnull  */
765 7a4ee46d 2003-11-23 devnull int
766 7a4ee46d 2003-11-23 devnull ientrycmp(const void *vie1, const void *vie2)
767 7a4ee46d 2003-11-23 devnull {
768 7a4ee46d 2003-11-23 devnull 	u8int *ie1, *ie2;
769 7a4ee46d 2003-11-23 devnull 	int i, v1, v2;
770 7a4ee46d 2003-11-23 devnull 
771 7a4ee46d 2003-11-23 devnull 	ie1 = (u8int*)vie1;
772 7a4ee46d 2003-11-23 devnull 	ie2 = (u8int*)vie2;
773 7a4ee46d 2003-11-23 devnull 	for(i = 0; i < VtScoreSize; i++){
774 7a4ee46d 2003-11-23 devnull 		v1 = ie1[i];
775 7a4ee46d 2003-11-23 devnull 		v2 = ie2[i];
776 7a4ee46d 2003-11-23 devnull 		if(v1 != v2){
777 7a4ee46d 2003-11-23 devnull 			if(v1 < v2)
778 7a4ee46d 2003-11-23 devnull 				return -1;
779 7a4ee46d 2003-11-23 devnull 			return 0;
780 7a4ee46d 2003-11-23 devnull 		}
781 7a4ee46d 2003-11-23 devnull 	}
782 7a4ee46d 2003-11-23 devnull 	v1 = ie1[IEntryTypeOff];
783 7a4ee46d 2003-11-23 devnull 	v2 = ie2[IEntryTypeOff];
784 7a4ee46d 2003-11-23 devnull 	if(v1 != v2){
785 7a4ee46d 2003-11-23 devnull 		if(v1 < v2)
786 7a4ee46d 2003-11-23 devnull 			return -1;
787 7a4ee46d 2003-11-23 devnull 		return 0;
788 7a4ee46d 2003-11-23 devnull 	}
789 7a4ee46d 2003-11-23 devnull 	return -1;
790 7a4ee46d 2003-11-23 devnull }