2 28b49df3 2006-07-18 devnull * Rebuild the index from scratch, in place.
4 a0d146ed 2005-07-12 devnull #include "stdinc.h"
5 a0d146ed 2005-07-12 devnull #include "dat.h"
6 a0d146ed 2005-07-12 devnull #include "fns.h"
10 28b49df3 2006-07-18 devnull MinBufSize = 64*1024,
11 28b49df3 2006-07-18 devnull MaxBufSize = 4*1024*1024,
14 ac5a97e6 2008-07-04 rsc typedef struct IEntryBuf IEntryBuf;
15 fa325e9b 2020-01-10 cross struct IEntryBuf
17 ac5a97e6 2008-07-04 rsc IEntry ie[100];
21 ac5a97e6 2008-07-04 rsc typedef struct ScoreBuf ScoreBuf;
22 ac5a97e6 2008-07-04 rsc struct ScoreBuf
24 ac5a97e6 2008-07-04 rsc uchar score[100][VtScoreSize];
28 28b49df3 2006-07-18 devnull int dumb;
29 28b49df3 2006-07-18 devnull int errors;
30 28b49df3 2006-07-18 devnull char **isect;
31 28b49df3 2006-07-18 devnull int nisect;
32 28b49df3 2006-07-18 devnull int bloom;
33 28b49df3 2006-07-18 devnull int zero;
35 28b49df3 2006-07-18 devnull u32int isectmem;
36 28b49df3 2006-07-18 devnull u64int totalbuckets;
37 28b49df3 2006-07-18 devnull u64int totalclumps;
38 28b49df3 2006-07-18 devnull Channel *arenadonechan;
39 28b49df3 2006-07-18 devnull Channel *isectdonechan;
40 28b49df3 2006-07-18 devnull Index *ix;
42 28b49df3 2006-07-18 devnull u64int arenaentries;
43 28b49df3 2006-07-18 devnull u64int skipentries;
44 28b49df3 2006-07-18 devnull u64int indexentries;
46 28b49df3 2006-07-18 devnull static int shouldprocess(ISect*);
47 28b49df3 2006-07-18 devnull static void isectproc(void*);
48 28b49df3 2006-07-18 devnull static void arenapartproc(void*);
51 a0d146ed 2005-07-12 devnull usage(void)
53 9ee00732 2011-06-07 rsc fprint(2, "usage: buildindex [-bd] [-i isect]... [-M imem] venti.conf\n");
54 28b49df3 2006-07-18 devnull threadexitsall("usage");
58 a0d146ed 2005-07-12 devnull threadmain(int argc, char *argv[])
60 f5a8ea6f 2011-06-02 rsc int fd, i, napart, nfinish, maxdisks;
61 28b49df3 2006-07-18 devnull u32int bcmem, imem;
62 28b49df3 2006-07-18 devnull Config conf;
65 f5a8ea6f 2011-06-02 rsc maxdisks = 100000;
66 23fb2edb 2005-07-24 devnull ventifmtinstall();
67 28b49df3 2006-07-18 devnull imem = 256*1024*1024;
68 a0d146ed 2005-07-12 devnull ARGBEGIN{
69 28b49df3 2006-07-18 devnull case 'b':
70 28b49df3 2006-07-18 devnull bloom = 1;
72 45ac814c 2007-10-29 rsc case 'd': /* debugging - make sure to run all 3 passes */
75 28b49df3 2006-07-18 devnull case 'i':
76 28b49df3 2006-07-18 devnull isect = vtrealloc(isect, (nisect+1)*sizeof(isect[0]));
77 28b49df3 2006-07-18 devnull isect[nisect++] = EARGF(usage());
79 28b49df3 2006-07-18 devnull case 'M':
80 28b49df3 2006-07-18 devnull imem = unittoull(EARGF(usage()));
82 f5a8ea6f 2011-06-02 rsc case 'm': /* temporary - might go away */
83 f5a8ea6f 2011-06-02 rsc maxdisks = atoi(EARGF(usage()));
90 28b49df3 2006-07-18 devnull if(argc != 1)
93 a0d146ed 2005-07-12 devnull if(initventi(argv[0], &conf) < 0)
94 a0d146ed 2005-07-12 devnull sysfatal("can't init venti: %r");
95 28b49df3 2006-07-18 devnull ix = mainindex;
96 28b49df3 2006-07-18 devnull if(nisect == 0 && ix->bloom)
97 28b49df3 2006-07-18 devnull bloom = 1;
98 28b49df3 2006-07-18 devnull if(bloom && ix->bloom && resetbloom(ix->bloom) < 0)
99 28b49df3 2006-07-18 devnull sysfatal("loadbloom: %r");
100 28b49df3 2006-07-18 devnull if(bloom && !ix->bloom)
101 28b49df3 2006-07-18 devnull sysfatal("-b specified but no bloom filter");
102 28b49df3 2006-07-18 devnull if(!bloom)
103 28b49df3 2006-07-18 devnull ix->bloom = nil;
104 28b49df3 2006-07-18 devnull isectmem = imem/ix->nsects;
107 28b49df3 2006-07-18 devnull * safety first - only need read access to arenas
109 28b49df3 2006-07-18 devnull p = nil;
110 28b49df3 2006-07-18 devnull for(i=0; i<ix->narenas; i++){
111 28b49df3 2006-07-18 devnull if(ix->arenas[i]->part != p){
112 28b49df3 2006-07-18 devnull p = ix->arenas[i]->part;
113 28b49df3 2006-07-18 devnull if((fd = open(p->filename, OREAD)) < 0)
114 28b49df3 2006-07-18 devnull sysfatal("cannot reopen %s: %r", p->filename);
115 28b49df3 2006-07-18 devnull dup(fd, p->fd);
116 28b49df3 2006-07-18 devnull close(fd);
121 28b49df3 2006-07-18 devnull * need a block for every arena
123 28b49df3 2006-07-18 devnull bcmem = maxblocksize * (mainindex->narenas + 16);
124 a0d146ed 2005-07-12 devnull if(0) fprint(2, "initialize %d bytes of disk block cache\n", bcmem);
125 a0d146ed 2005-07-12 devnull initdcache(bcmem);
127 28b49df3 2006-07-18 devnull totalclumps = 0;
128 28b49df3 2006-07-18 devnull for(i=0; i<ix->narenas; i++)
129 28b49df3 2006-07-18 devnull totalclumps += ix->arenas[i]->diskstats.clumps;
131 28b49df3 2006-07-18 devnull totalbuckets = 0;
132 28b49df3 2006-07-18 devnull for(i=0; i<ix->nsects; i++)
133 28b49df3 2006-07-18 devnull totalbuckets += ix->sects[i]->blocks;
134 28b49df3 2006-07-18 devnull fprint(2, "%,lld clumps, %,lld buckets\n", totalclumps, totalbuckets);
136 28b49df3 2006-07-18 devnull /* start index procs */
137 28b49df3 2006-07-18 devnull fprint(2, "%T read index\n");
138 ac5a97e6 2008-07-04 rsc isectdonechan = chancreate(sizeof(void*), 1);
139 28b49df3 2006-07-18 devnull for(i=0; i<ix->nsects; i++){
140 7e452401 2007-04-27 devnull if(shouldprocess(ix->sects[i])){
141 ac5a97e6 2008-07-04 rsc ix->sects[i]->writechan = chancreate(sizeof(IEntryBuf), 1);
142 7e452401 2007-04-27 devnull vtproc(isectproc, ix->sects[i]);
146 28b49df3 2006-07-18 devnull for(i=0; i<nisect; i++)
147 28b49df3 2006-07-18 devnull if(isect[i])
148 28b49df3 2006-07-18 devnull fprint(2, "warning: did not find index section %s\n", isect[i]);
150 28b49df3 2006-07-18 devnull /* start arena procs */
151 28b49df3 2006-07-18 devnull p = nil;
152 28b49df3 2006-07-18 devnull napart = 0;
153 f5a8ea6f 2011-06-02 rsc nfinish = 0;
154 28b49df3 2006-07-18 devnull arenadonechan = chancreate(sizeof(void*), 0);
155 28b49df3 2006-07-18 devnull for(i=0; i<ix->narenas; i++){
156 28b49df3 2006-07-18 devnull if(ix->arenas[i]->part != p){
157 28b49df3 2006-07-18 devnull p = ix->arenas[i]->part;
158 28b49df3 2006-07-18 devnull vtproc(arenapartproc, p);
159 f5a8ea6f 2011-06-02 rsc if(++napart >= maxdisks){
160 f5a8ea6f 2011-06-02 rsc recvp(arenadonechan);
166 28b49df3 2006-07-18 devnull /* wait for arena procs to finish */
167 5c062149 2020-01-15 rsc for(; nfinish<napart; nfinish++)
168 28b49df3 2006-07-18 devnull recvp(arenadonechan);
170 28b49df3 2006-07-18 devnull /* tell index procs to finish */
171 28b49df3 2006-07-18 devnull for(i=0; i<ix->nsects; i++)
172 28b49df3 2006-07-18 devnull if(ix->sects[i]->writechan)
173 28b49df3 2006-07-18 devnull send(ix->sects[i]->writechan, nil);
175 28b49df3 2006-07-18 devnull /* wait for index procs to finish */
176 28b49df3 2006-07-18 devnull for(i=0; i<ix->nsects; i++)
177 28b49df3 2006-07-18 devnull if(ix->sects[i]->writechan)
178 28b49df3 2006-07-18 devnull recvp(isectdonechan);
180 28b49df3 2006-07-18 devnull if(ix->bloom && writebloom(ix->bloom) < 0)
181 28b49df3 2006-07-18 devnull fprint(2, "writing bloom filter: %r\n");
183 fa325e9b 2020-01-10 cross fprint(2, "%T done arenaentries=%,lld indexed=%,lld (nskip=%,lld)\n",
184 28b49df3 2006-07-18 devnull arenaentries, indexentries, skipentries);
185 28b49df3 2006-07-18 devnull threadexitsall(nil);
188 28b49df3 2006-07-18 devnull static int
189 28b49df3 2006-07-18 devnull shouldprocess(ISect *is)
193 28b49df3 2006-07-18 devnull if(nisect == 0)
194 28b49df3 2006-07-18 devnull return 1;
196 28b49df3 2006-07-18 devnull for(i=0; i<nisect; i++)
197 28b49df3 2006-07-18 devnull if(isect[i] && strcmp(isect[i], is->name) == 0){
198 28b49df3 2006-07-18 devnull isect[i] = nil;
199 28b49df3 2006-07-18 devnull return 1;
201 28b49df3 2006-07-18 devnull return 0;
204 28b49df3 2006-07-18 devnull static void
205 28b49df3 2006-07-18 devnull add(u64int *a, u64int n)
207 28b49df3 2006-07-18 devnull static Lock l;
209 28b49df3 2006-07-18 devnull lock(&l);
210 28b49df3 2006-07-18 devnull *a += n;
211 28b49df3 2006-07-18 devnull unlock(&l);
215 28b49df3 2006-07-18 devnull * Read through an arena partition and send each of its IEntries
216 28b49df3 2006-07-18 devnull * to the appropriate index section. When finished, send on
217 28b49df3 2006-07-18 devnull * arenadonechan.
221 28b49df3 2006-07-18 devnull ClumpChunks = 32*1024,
223 28b49df3 2006-07-18 devnull static void
224 28b49df3 2006-07-18 devnull arenapartproc(void *v)
226 28b49df3 2006-07-18 devnull int i, j, n, nskip, x;
227 28b49df3 2006-07-18 devnull u32int clump;
228 28b49df3 2006-07-18 devnull u64int addr, tot;
229 28b49df3 2006-07-18 devnull Arena *a;
230 28b49df3 2006-07-18 devnull ClumpInfo *ci, *cis;
231 28b49df3 2006-07-18 devnull IEntry ie;
232 28b49df3 2006-07-18 devnull Part *p;
233 ac5a97e6 2008-07-04 rsc IEntryBuf *buf, *b;
234 ac5a97e6 2008-07-04 rsc uchar *score;
235 ac5a97e6 2008-07-04 rsc ScoreBuf sb;
238 28b49df3 2006-07-18 devnull threadsetname("arenaproc %s", p->name);
239 ac5a97e6 2008-07-04 rsc buf = MKNZ(IEntryBuf, ix->nsects);
241 28b49df3 2006-07-18 devnull nskip = 0;
242 28b49df3 2006-07-18 devnull tot = 0;
243 ac5a97e6 2008-07-04 rsc sb.nscore = 0;
244 28b49df3 2006-07-18 devnull cis = MKN(ClumpInfo, ClumpChunks);
245 28b49df3 2006-07-18 devnull for(i=0; i<ix->narenas; i++){
246 28b49df3 2006-07-18 devnull a = ix->arenas[i];
247 28b49df3 2006-07-18 devnull if(a->part != p)
248 28b49df3 2006-07-18 devnull continue;
249 28b49df3 2006-07-18 devnull if(a->memstats.clumps)
250 fa325e9b 2020-01-10 cross fprint(2, "%T arena %s: %d entries\n",
251 28b49df3 2006-07-18 devnull a->name, a->memstats.clumps);
253 fa325e9b 2020-01-10 cross * Running the loop backwards accesses the
254 45ac814c 2007-10-29 rsc * clump info blocks forwards, since they are
255 45ac814c 2007-10-29 rsc * stored in reverse order at the end of the arena.
256 45ac814c 2007-10-29 rsc * This speeds things slightly.
258 45ac814c 2007-10-29 rsc addr = ix->amap[i].start + a->memstats.used;
259 45ac814c 2007-10-29 rsc for(clump=a->memstats.clumps; clump > 0; clump-=n){
260 28b49df3 2006-07-18 devnull n = ClumpChunks;
261 45ac814c 2007-10-29 rsc if(n > clump)
263 45ac814c 2007-10-29 rsc if(readclumpinfos(a, clump-n, cis, n) != n){
264 28b49df3 2006-07-18 devnull fprint(2, "%T arena %s: directory read: %r\n", a->name);
265 28b49df3 2006-07-18 devnull errors = 1;
268 45ac814c 2007-10-29 rsc for(j=n-1; j>=0; j--){
269 28b49df3 2006-07-18 devnull ci = &cis[j];
270 28b49df3 2006-07-18 devnull ie.ia.type = ci->type;
271 28b49df3 2006-07-18 devnull ie.ia.size = ci->uncsize;
272 45ac814c 2007-10-29 rsc addr -= ci->size + ClumpSize;
273 28b49df3 2006-07-18 devnull ie.ia.addr = addr;
274 28b49df3 2006-07-18 devnull ie.ia.blocks = (ci->size + ClumpSize + (1<<ABlockLog)-1) >> ABlockLog;
275 28b49df3 2006-07-18 devnull scorecp(ie.score, ci->score);
276 28b49df3 2006-07-18 devnull if(ci->type == VtCorruptType)
277 28b49df3 2006-07-18 devnull nskip++;
280 28b49df3 2006-07-18 devnull x = indexsect(ix, ie.score);
281 28b49df3 2006-07-18 devnull assert(0 <= x && x < ix->nsects);
282 ac5a97e6 2008-07-04 rsc if(ix->sects[x]->writechan) {
283 ac5a97e6 2008-07-04 rsc b = &buf[x];
284 ac5a97e6 2008-07-04 rsc b->ie[b->nie] = ie;
286 ac5a97e6 2008-07-04 rsc if(b->nie == nelem(b->ie)) {
287 ac5a97e6 2008-07-04 rsc send(ix->sects[x]->writechan, b);
291 ac5a97e6 2008-07-04 rsc if(ix->bloom) {
292 ac5a97e6 2008-07-04 rsc score = sb.score[sb.nscore++];
293 ac5a97e6 2008-07-04 rsc scorecp(score, ie.score);
294 ac5a97e6 2008-07-04 rsc if(sb.nscore == nelem(sb.score)) {
295 ac5a97e6 2008-07-04 rsc markbloomfiltern(ix->bloom, sb.score, sb.nscore);
296 ac5a97e6 2008-07-04 rsc sb.nscore = 0;
302 45ac814c 2007-10-29 rsc if(addr != ix->amap[i].start)
303 45ac814c 2007-10-29 rsc fprint(2, "%T arena %s: clump miscalculation %lld != %lld\n", a->name, addr, ix->amap[i].start);
305 28b49df3 2006-07-18 devnull add(&arenaentries, tot);
306 28b49df3 2006-07-18 devnull add(&skipentries, nskip);
308 ac5a97e6 2008-07-04 rsc for(i=0; i<ix->nsects; i++)
309 ac5a97e6 2008-07-04 rsc if(ix->sects[i]->writechan && buf[i].nie > 0)
310 ac5a97e6 2008-07-04 rsc send(ix->sects[i]->writechan, &buf[i]);
313 ac5a97e6 2008-07-04 rsc if(ix->bloom && sb.nscore > 0)
314 ac5a97e6 2008-07-04 rsc markbloomfiltern(ix->bloom, sb.score, sb.nscore);
315 28b49df3 2006-07-18 devnull sendp(arenadonechan, p);
319 28b49df3 2006-07-18 devnull * Convert score into relative bucket number in isect.
320 28b49df3 2006-07-18 devnull * Can pass a packed ientry instead of score - score is first.
322 28b49df3 2006-07-18 devnull static u32int
323 28b49df3 2006-07-18 devnull score2bucket(ISect *is, uchar *score)
325 28b49df3 2006-07-18 devnull u32int b;
327 28b49df3 2006-07-18 devnull b = hashbits(score, 32)/ix->div;
328 6b9887c7 2007-05-03 devnull if(b < is->start || b >= is->stop){
329 6b9887c7 2007-05-03 devnull fprint(2, "score2bucket: score=%V div=%d b=%ud start=%ud stop=%ud\n",
330 6b9887c7 2007-05-03 devnull score, ix->div, b, is->start, is->stop);
332 28b49df3 2006-07-18 devnull assert(is->start <= b && b < is->stop);
333 28b49df3 2006-07-18 devnull return b - is->start;
337 28b49df3 2006-07-18 devnull * Convert offset in index section to bucket number.
339 28b49df3 2006-07-18 devnull static u32int
340 28b49df3 2006-07-18 devnull offset2bucket(ISect *is, u64int offset)
342 28b49df3 2006-07-18 devnull u32int b;
344 28b49df3 2006-07-18 devnull assert(is->blockbase <= offset);
345 28b49df3 2006-07-18 devnull offset -= is->blockbase;
346 28b49df3 2006-07-18 devnull b = offset/is->blocksize;
347 28b49df3 2006-07-18 devnull assert(b < is->stop-is->start);
348 28b49df3 2006-07-18 devnull return b;
352 28b49df3 2006-07-18 devnull * Convert bucket number to offset.
354 28b49df3 2006-07-18 devnull static u64int
355 28b49df3 2006-07-18 devnull bucket2offset(ISect *is, u32int b)
357 28b49df3 2006-07-18 devnull assert(b <= is->stop-is->start);
358 28b49df3 2006-07-18 devnull return is->blockbase + (u64int)b*is->blocksize;
362 28b49df3 2006-07-18 devnull * IEntry buffers to hold initial round of spraying.
364 28b49df3 2006-07-18 devnull typedef struct Buf Buf;
365 28b49df3 2006-07-18 devnull struct Buf
367 28b49df3 2006-07-18 devnull Part *part; /* partition being written */
368 28b49df3 2006-07-18 devnull uchar *bp; /* current block */
369 28b49df3 2006-07-18 devnull uchar *ep; /* end of block */
370 28b49df3 2006-07-18 devnull uchar *wp; /* write position in block */
371 28b49df3 2006-07-18 devnull u64int boffset; /* start offset */
372 28b49df3 2006-07-18 devnull u64int woffset; /* next write offset */
373 28b49df3 2006-07-18 devnull u64int eoffset; /* end offset */
374 28b49df3 2006-07-18 devnull u32int nentry; /* number of entries written */
377 28b49df3 2006-07-18 devnull static void
378 28b49df3 2006-07-18 devnull bflush(Buf *buf)
380 28b49df3 2006-07-18 devnull u32int bufsize;
382 28b49df3 2006-07-18 devnull if(buf->woffset >= buf->eoffset)
383 1d53bf4a 2007-05-03 devnull sysfatal("buf index chunk overflow - need bigger index");
384 28b49df3 2006-07-18 devnull bufsize = buf->ep - buf->bp;
385 28b49df3 2006-07-18 devnull if(writepart(buf->part, buf->woffset, buf->bp, bufsize) < 0){
386 28b49df3 2006-07-18 devnull fprint(2, "write %s: %r\n", buf->part->name);
387 28b49df3 2006-07-18 devnull errors = 1;
389 28b49df3 2006-07-18 devnull buf->woffset += bufsize;
390 28b49df3 2006-07-18 devnull memset(buf->bp, 0, bufsize);
391 28b49df3 2006-07-18 devnull buf->wp = buf->bp;
394 28b49df3 2006-07-18 devnull static void
395 28b49df3 2006-07-18 devnull bwrite(Buf *buf, IEntry *ie)
397 28b49df3 2006-07-18 devnull if(buf->wp+IEntrySize > buf->ep)
398 28b49df3 2006-07-18 devnull bflush(buf);
399 28b49df3 2006-07-18 devnull assert(buf->bp <= buf->wp && buf->wp < buf->ep);
400 28b49df3 2006-07-18 devnull packientry(ie, buf->wp);
401 28b49df3 2006-07-18 devnull buf->wp += IEntrySize;
402 28b49df3 2006-07-18 devnull assert(buf->bp <= buf->wp && buf->wp <= buf->ep);
403 28b49df3 2006-07-18 devnull buf->nentry++;
407 28b49df3 2006-07-18 devnull * Minibuffer. In-memory data structure holds our place
408 28b49df3 2006-07-18 devnull * in the buffer but has no block data. We are writing and
409 28b49df3 2006-07-18 devnull * reading the minibuffers at the same time. (Careful!)
411 28b49df3 2006-07-18 devnull typedef struct Minibuf Minibuf;
412 28b49df3 2006-07-18 devnull struct Minibuf
414 28b49df3 2006-07-18 devnull u64int boffset; /* start offset */
415 28b49df3 2006-07-18 devnull u64int roffset; /* read offset */
416 28b49df3 2006-07-18 devnull u64int woffset; /* write offset */
417 28b49df3 2006-07-18 devnull u64int eoffset; /* end offset */
418 28b49df3 2006-07-18 devnull u32int nentry; /* # entries left to read */
419 28b49df3 2006-07-18 devnull u32int nwentry; /* # entries written */
423 fa325e9b 2020-01-10 cross * Index entry pool. Used when trying to shuffle around
424 28b49df3 2006-07-18 devnull * the entries in a big buffer into the corresponding M minibuffers.
425 28b49df3 2006-07-18 devnull * Sized to hold M*EntriesPerBlock entries, so that there will always
426 28b49df3 2006-07-18 devnull * either be room in the pool for another block worth of entries
427 fa325e9b 2020-01-10 cross * or there will be an entire block worth of sorted entries to
428 28b49df3 2006-07-18 devnull * write out.
430 28b49df3 2006-07-18 devnull typedef struct IEntryLink IEntryLink;
431 28b49df3 2006-07-18 devnull typedef struct IPool IPool;
433 28b49df3 2006-07-18 devnull struct IEntryLink
435 28b49df3 2006-07-18 devnull uchar ie[IEntrySize]; /* raw IEntry */
436 28b49df3 2006-07-18 devnull IEntryLink *next; /* next in chain */
439 28b49df3 2006-07-18 devnull struct IPool
441 28b49df3 2006-07-18 devnull ISect *isect;
442 28b49df3 2006-07-18 devnull u32int buck0; /* first bucket in pool */
443 28b49df3 2006-07-18 devnull u32int mbufbuckets; /* buckets per minibuf */
444 28b49df3 2006-07-18 devnull IEntryLink *entry; /* all IEntryLinks */
445 28b49df3 2006-07-18 devnull u32int nentry; /* # of IEntryLinks */
446 28b49df3 2006-07-18 devnull IEntryLink *free; /* free list */
447 28b49df3 2006-07-18 devnull u32int nfree; /* # on free list */
448 28b49df3 2006-07-18 devnull Minibuf *mbuf; /* all minibufs */
449 28b49df3 2006-07-18 devnull u32int nmbuf; /* # of minibufs */
450 28b49df3 2006-07-18 devnull IEntryLink **mlist; /* lists for each minibuf */
451 28b49df3 2006-07-18 devnull u32int *mcount; /* # on each mlist[i] */
452 28b49df3 2006-07-18 devnull u32int bufsize; /* block buffer size */
453 28b49df3 2006-07-18 devnull uchar *rbuf; /* read buffer */
454 28b49df3 2006-07-18 devnull uchar *wbuf; /* write buffer */
455 28b49df3 2006-07-18 devnull u32int epbuf; /* entries per block buffer */
459 28b49df3 2006-07-18 devnull static int
460 28b49df3 2006-07-18 devnull countsokay(IPool *p)
463 28b49df3 2006-07-18 devnull u64int n;
466 28b49df3 2006-07-18 devnull for(i=0; i<p->nmbuf; i++)
467 28b49df3 2006-07-18 devnull n += p->mcount[i];
468 28b49df3 2006-07-18 devnull n += p->nfree;
469 28b49df3 2006-07-18 devnull if(n != p->nentry){
470 28b49df3 2006-07-18 devnull print("free %ud:", p->nfree);
471 28b49df3 2006-07-18 devnull for(i=0; i<p->nmbuf; i++)
472 28b49df3 2006-07-18 devnull print(" %ud", p->mcount[i]);
473 28b49df3 2006-07-18 devnull print(" = %lld nentry: %ud\n", n, p->nentry);
475 28b49df3 2006-07-18 devnull return n == p->nentry;
479 28b49df3 2006-07-18 devnull static IPool*
480 fa325e9b 2020-01-10 cross mkipool(ISect *isect, Minibuf *mbuf, u32int nmbuf,
481 28b49df3 2006-07-18 devnull u32int mbufbuckets, u32int bufsize)
483 28b49df3 2006-07-18 devnull u32int i, nentry;
484 28b49df3 2006-07-18 devnull uchar *data;
485 28b49df3 2006-07-18 devnull IPool *p;
486 28b49df3 2006-07-18 devnull IEntryLink *l;
488 28b49df3 2006-07-18 devnull nentry = (nmbuf+1)*bufsize / IEntrySize;
489 28b49df3 2006-07-18 devnull p = ezmalloc(sizeof(IPool)
490 28b49df3 2006-07-18 devnull +nentry*sizeof(IEntry)
491 28b49df3 2006-07-18 devnull +nmbuf*sizeof(IEntryLink*)
492 28b49df3 2006-07-18 devnull +nmbuf*sizeof(u32int)
493 28b49df3 2006-07-18 devnull +3*bufsize);
495 28b49df3 2006-07-18 devnull p->isect = isect;
496 28b49df3 2006-07-18 devnull p->mbufbuckets = mbufbuckets;
497 28b49df3 2006-07-18 devnull p->bufsize = bufsize;
498 28b49df3 2006-07-18 devnull p->entry = (IEntryLink*)(p+1);
499 28b49df3 2006-07-18 devnull p->nentry = nentry;
500 28b49df3 2006-07-18 devnull p->mlist = (IEntryLink**)(p->entry+nentry);
501 28b49df3 2006-07-18 devnull p->mcount = (u32int*)(p->mlist+nmbuf);
502 28b49df3 2006-07-18 devnull p->nmbuf = nmbuf;
503 28b49df3 2006-07-18 devnull p->mbuf = mbuf;
504 28b49df3 2006-07-18 devnull data = (uchar*)(p->mcount+nmbuf);
505 e6b0276e 2006-11-06 devnull data += bufsize - (uintptr)data%bufsize;
506 28b49df3 2006-07-18 devnull p->rbuf = data;
507 28b49df3 2006-07-18 devnull p->wbuf = data+bufsize;
508 28b49df3 2006-07-18 devnull p->epbuf = bufsize/IEntrySize;
510 28b49df3 2006-07-18 devnull for(i=0; i<p->nentry; i++){
511 28b49df3 2006-07-18 devnull l = &p->entry[i];
512 28b49df3 2006-07-18 devnull l->next = p->free;
513 28b49df3 2006-07-18 devnull p->free = l;
514 28b49df3 2006-07-18 devnull p->nfree++;
516 28b49df3 2006-07-18 devnull return p;
520 28b49df3 2006-07-18 devnull * Add the index entry ie to the pool p.
521 28b49df3 2006-07-18 devnull * Caller must know there is room.
523 28b49df3 2006-07-18 devnull static void
524 28b49df3 2006-07-18 devnull ipoolinsert(IPool *p, uchar *ie)
526 28b49df3 2006-07-18 devnull u32int buck, x;
527 28b49df3 2006-07-18 devnull IEntryLink *l;
529 28b49df3 2006-07-18 devnull assert(p->free != nil);
531 28b49df3 2006-07-18 devnull buck = score2bucket(p->isect, ie);
532 28b49df3 2006-07-18 devnull x = (buck-p->buck0) / p->mbufbuckets;
533 28b49df3 2006-07-18 devnull if(x >= p->nmbuf){
534 28b49df3 2006-07-18 devnull fprint(2, "buck=%ud mbufbucket=%ud x=%ud\n",
535 28b49df3 2006-07-18 devnull buck, p->mbufbuckets, x);
537 28b49df3 2006-07-18 devnull assert(x < p->nmbuf);
539 28b49df3 2006-07-18 devnull l = p->free;
540 28b49df3 2006-07-18 devnull p->free = l->next;
541 28b49df3 2006-07-18 devnull p->nfree--;
542 28b49df3 2006-07-18 devnull memmove(l->ie, ie, IEntrySize);
543 28b49df3 2006-07-18 devnull l->next = p->mlist[x];
544 28b49df3 2006-07-18 devnull p->mlist[x] = l;
545 28b49df3 2006-07-18 devnull p->mcount[x]++;
549 28b49df3 2006-07-18 devnull * Pull out a block containing as many
550 28b49df3 2006-07-18 devnull * entries as possible for minibuffer x.
552 28b49df3 2006-07-18 devnull static u32int
553 28b49df3 2006-07-18 devnull ipoolgetbuf(IPool *p, u32int x)
555 28b49df3 2006-07-18 devnull uchar *bp, *ep, *wp;
556 28b49df3 2006-07-18 devnull IEntryLink *l;
557 28b49df3 2006-07-18 devnull u32int n;
559 28b49df3 2006-07-18 devnull bp = p->wbuf;
560 28b49df3 2006-07-18 devnull ep = p->wbuf + p->bufsize;
562 28b49df3 2006-07-18 devnull assert(x < p->nmbuf);
563 28b49df3 2006-07-18 devnull for(wp=bp; wp+IEntrySize<=ep && p->mlist[x]; wp+=IEntrySize){
564 28b49df3 2006-07-18 devnull l = p->mlist[x];
565 28b49df3 2006-07-18 devnull p->mlist[x] = l->next;
566 28b49df3 2006-07-18 devnull p->mcount[x]--;
567 28b49df3 2006-07-18 devnull memmove(wp, l->ie, IEntrySize);
568 28b49df3 2006-07-18 devnull l->next = p->free;
569 28b49df3 2006-07-18 devnull p->free = l;
570 28b49df3 2006-07-18 devnull p->nfree++;
573 28b49df3 2006-07-18 devnull memset(wp, 0, ep-wp);
574 28b49df3 2006-07-18 devnull return n;
578 28b49df3 2006-07-18 devnull * Read a block worth of entries from the minibuf
579 28b49df3 2006-07-18 devnull * into the pool. Caller must know there is room.
581 28b49df3 2006-07-18 devnull static void
582 28b49df3 2006-07-18 devnull ipoolloadblock(IPool *p, Minibuf *mb)
584 28b49df3 2006-07-18 devnull u32int i, n;
586 28b49df3 2006-07-18 devnull assert(mb->nentry > 0);
587 28b49df3 2006-07-18 devnull assert(mb->roffset >= mb->woffset);
588 28b49df3 2006-07-18 devnull assert(mb->roffset < mb->eoffset);
590 28b49df3 2006-07-18 devnull n = p->bufsize/IEntrySize;
591 28b49df3 2006-07-18 devnull if(n > mb->nentry)
592 28b49df3 2006-07-18 devnull n = mb->nentry;
593 28b49df3 2006-07-18 devnull if(readpart(p->isect->part, mb->roffset, p->rbuf, p->bufsize) < 0)
594 28b49df3 2006-07-18 devnull fprint(2, "readpart %s: %r\n", p->isect->part->name);
596 28b49df3 2006-07-18 devnull for(i=0; i<n; i++)
597 28b49df3 2006-07-18 devnull ipoolinsert(p, p->rbuf+i*IEntrySize);
599 28b49df3 2006-07-18 devnull mb->nentry -= n;
600 28b49df3 2006-07-18 devnull mb->roffset += p->bufsize;
604 28b49df3 2006-07-18 devnull * Write out a block worth of entries to minibuffer x.
605 28b49df3 2006-07-18 devnull * If necessary, pick up the data there before overwriting it.
607 28b49df3 2006-07-18 devnull static void
608 28b49df3 2006-07-18 devnull ipoolflush0(IPool *pool, u32int x)
610 28b49df3 2006-07-18 devnull u32int bufsize;
611 28b49df3 2006-07-18 devnull Minibuf *mb;
613 28b49df3 2006-07-18 devnull mb = pool->mbuf+x;
614 28b49df3 2006-07-18 devnull bufsize = pool->bufsize;
615 28b49df3 2006-07-18 devnull mb->nwentry += ipoolgetbuf(pool, x);
616 28b49df3 2006-07-18 devnull if(mb->nentry > 0 && mb->roffset == mb->woffset){
617 28b49df3 2006-07-18 devnull assert(pool->nfree >= pool->bufsize/IEntrySize);
619 fa325e9b 2020-01-10 cross * There will be room in the pool -- we just
620 28b49df3 2006-07-18 devnull * removed a block worth.
622 28b49df3 2006-07-18 devnull ipoolloadblock(pool, mb);
624 28b49df3 2006-07-18 devnull if(writepart(pool->isect->part, mb->woffset, pool->wbuf, bufsize) < 0)
625 28b49df3 2006-07-18 devnull fprint(2, "writepart %s: %r\n", pool->isect->part->name);
626 28b49df3 2006-07-18 devnull mb->woffset += bufsize;
630 28b49df3 2006-07-18 devnull * Write out some full block of entries.
631 28b49df3 2006-07-18 devnull * (There must be one -- the pool is almost full!)
633 28b49df3 2006-07-18 devnull static void
634 28b49df3 2006-07-18 devnull ipoolflush1(IPool *pool)
636 28b49df3 2006-07-18 devnull u32int i;
638 28b49df3 2006-07-18 devnull assert(pool->nfree <= pool->epbuf);
640 28b49df3 2006-07-18 devnull for(i=0; i<pool->nmbuf; i++){
641 28b49df3 2006-07-18 devnull if(pool->mcount[i] >= pool->epbuf){
642 28b49df3 2006-07-18 devnull ipoolflush0(pool, i);
646 28b49df3 2006-07-18 devnull /* can't be reached - someone must be full */
647 28b49df3 2006-07-18 devnull sysfatal("ipoolflush1");
651 28b49df3 2006-07-18 devnull * Flush all the entries in the pool out to disk.
652 28b49df3 2006-07-18 devnull * Nothing more to read from disk.
654 28b49df3 2006-07-18 devnull static void
655 28b49df3 2006-07-18 devnull ipoolflush(IPool *pool)
657 28b49df3 2006-07-18 devnull u32int i;
659 28b49df3 2006-07-18 devnull for(i=0; i<pool->nmbuf; i++)
660 28b49df3 2006-07-18 devnull while(pool->mlist[i])
661 28b49df3 2006-07-18 devnull ipoolflush0(pool, i);
662 28b49df3 2006-07-18 devnull assert(pool->nfree == pool->nentry);
666 28b49df3 2006-07-18 devnull * Third pass. Pick up each minibuffer from disk into
667 28b49df3 2006-07-18 devnull * memory and then write out the buckets.
671 fa325e9b 2020-01-10 cross * Compare two packed index entries.
672 28b49df3 2006-07-18 devnull * Usual ordering except break ties by putting higher
673 28b49df3 2006-07-18 devnull * index addresses first (assumes have duplicates
674 28b49df3 2006-07-18 devnull * due to corruption in the lower addresses).
676 28b49df3 2006-07-18 devnull static int
677 28b49df3 2006-07-18 devnull ientrycmpaddr(const void *va, const void *vb)
680 28b49df3 2006-07-18 devnull uchar *a, *b;
682 28b49df3 2006-07-18 devnull a = (uchar*)va;
683 28b49df3 2006-07-18 devnull b = (uchar*)vb;
684 28b49df3 2006-07-18 devnull i = ientrycmp(a, b);
686 28b49df3 2006-07-18 devnull return i;
687 28b49df3 2006-07-18 devnull return -memcmp(a+IEntryAddrOff, b+IEntryAddrOff, 8);
690 28b49df3 2006-07-18 devnull static void
691 28b49df3 2006-07-18 devnull zerorange(Part *p, u64int o, u64int e)
693 28b49df3 2006-07-18 devnull static uchar zero[MaxIoSize];
694 28b49df3 2006-07-18 devnull u32int n;
696 28b49df3 2006-07-18 devnull for(; o<e; o+=n){
697 28b49df3 2006-07-18 devnull n = sizeof zero;
698 28b49df3 2006-07-18 devnull if(o+n > e)
699 28b49df3 2006-07-18 devnull n = e-o;
700 28b49df3 2006-07-18 devnull if(writepart(p, o, zero, n) < 0)
701 28b49df3 2006-07-18 devnull fprint(2, "writepart %s: %r\n", p->name);
706 fa325e9b 2020-01-10 cross * Load a minibuffer into memory and write out the
707 28b49df3 2006-07-18 devnull * corresponding buckets.
709 28b49df3 2006-07-18 devnull static void
710 28b49df3 2006-07-18 devnull sortminibuffer(ISect *is, Minibuf *mb, uchar *buf, u32int nbuf, u32int bufsize)
712 28b49df3 2006-07-18 devnull uchar *buckdata, *p, *q, *ep;
713 28b49df3 2006-07-18 devnull u32int b, lastb, memsize, n;
714 28b49df3 2006-07-18 devnull u64int o;
715 28b49df3 2006-07-18 devnull IBucket ib;
716 28b49df3 2006-07-18 devnull Part *part;
718 28b49df3 2006-07-18 devnull part = is->part;
719 28b49df3 2006-07-18 devnull buckdata = emalloc(is->blocksize);
721 28b49df3 2006-07-18 devnull if(mb->nwentry == 0)
725 28b49df3 2006-07-18 devnull * read entire buffer.
727 28b49df3 2006-07-18 devnull assert(mb->nwentry*IEntrySize <= mb->woffset-mb->boffset);
728 28b49df3 2006-07-18 devnull assert(mb->woffset-mb->boffset <= nbuf);
729 28b49df3 2006-07-18 devnull if(readpart(part, mb->boffset, buf, mb->woffset-mb->boffset) < 0){
730 28b49df3 2006-07-18 devnull fprint(2, "readpart %s: %r\n", part->name);
731 28b49df3 2006-07-18 devnull errors = 1;
734 28b49df3 2006-07-18 devnull assert(*(uint*)buf != 0xa5a5a5a5);
737 28b49df3 2006-07-18 devnull * remove fragmentation due to IEntrySize
738 28b49df3 2006-07-18 devnull * not evenly dividing Bufsize
740 28b49df3 2006-07-18 devnull memsize = (bufsize/IEntrySize)*IEntrySize;
741 28b49df3 2006-07-18 devnull for(o=mb->boffset, p=q=buf; o<mb->woffset; o+=bufsize){
742 28b49df3 2006-07-18 devnull memmove(p, q, memsize);
743 28b49df3 2006-07-18 devnull p += memsize;
744 28b49df3 2006-07-18 devnull q += bufsize;
746 28b49df3 2006-07-18 devnull ep = buf + mb->nwentry*IEntrySize;
747 28b49df3 2006-07-18 devnull assert(ep <= buf+nbuf);
750 28b49df3 2006-07-18 devnull * sort entries
752 28b49df3 2006-07-18 devnull qsort(buf, mb->nwentry, IEntrySize, ientrycmpaddr);
755 28b49df3 2006-07-18 devnull * write buckets out
758 28b49df3 2006-07-18 devnull lastb = offset2bucket(is, mb->boffset);
759 28b49df3 2006-07-18 devnull for(p=buf; p<ep; p=q){
760 28b49df3 2006-07-18 devnull b = score2bucket(is, p);
761 28b49df3 2006-07-18 devnull for(q=p; q<ep && score2bucket(is, q)==b; q+=IEntrySize)
763 28b49df3 2006-07-18 devnull if(lastb+1 < b && zero)
764 28b49df3 2006-07-18 devnull zerorange(part, bucket2offset(is, lastb+1), bucket2offset(is, b));
765 28b49df3 2006-07-18 devnull if(IBucketSize+(q-p) > is->blocksize)
766 28b49df3 2006-07-18 devnull sysfatal("bucket overflow - make index bigger");
767 28b49df3 2006-07-18 devnull memmove(buckdata+IBucketSize, p, q-p);
768 28b49df3 2006-07-18 devnull ib.n = (q-p)/IEntrySize;
769 28b49df3 2006-07-18 devnull n += ib.n;
770 28b49df3 2006-07-18 devnull packibucket(&ib, buckdata, is->bucketmagic);
771 28b49df3 2006-07-18 devnull if(writepart(part, bucket2offset(is, b), buckdata, is->blocksize) < 0)
772 28b49df3 2006-07-18 devnull fprint(2, "write %s: %r\n", part->name);
773 28b49df3 2006-07-18 devnull lastb = b;
775 28b49df3 2006-07-18 devnull if(lastb+1 < is->stop-is->start && zero)
776 28b49df3 2006-07-18 devnull zerorange(part, bucket2offset(is, lastb+1), bucket2offset(is, is->stop - is->start));
778 28b49df3 2006-07-18 devnull if(n != mb->nwentry)
779 28b49df3 2006-07-18 devnull fprint(2, "sortminibuffer bug: n=%ud nwentry=%ud have=%ld\n", n, mb->nwentry, (ep-buf)/IEntrySize);
781 28b49df3 2006-07-18 devnull free(buckdata);
784 28b49df3 2006-07-18 devnull static void
785 28b49df3 2006-07-18 devnull isectproc(void *v)
787 28b49df3 2006-07-18 devnull u32int buck, bufbuckets, bufsize, epbuf, i, j;
788 28b49df3 2006-07-18 devnull u32int mbufbuckets, n, nbucket, nn, space;
789 28b49df3 2006-07-18 devnull u32int nbuf, nminibuf, xminiclump, prod;
790 28b49df3 2006-07-18 devnull u64int blocksize, offset, xclump;
791 28b49df3 2006-07-18 devnull uchar *data, *p;
792 28b49df3 2006-07-18 devnull Buf *buf;
793 28b49df3 2006-07-18 devnull IEntry ie;
794 ac5a97e6 2008-07-04 rsc IEntryBuf ieb;
795 28b49df3 2006-07-18 devnull IPool *ipool;
796 28b49df3 2006-07-18 devnull ISect *is;
797 28b49df3 2006-07-18 devnull Minibuf *mbuf, *mb;
800 28b49df3 2006-07-18 devnull blocksize = is->blocksize;
801 28b49df3 2006-07-18 devnull nbucket = is->stop - is->start;
804 28b49df3 2006-07-18 devnull * Three passes:
805 fa325e9b 2020-01-10 cross * pass 1 - write index entries from arenas into
806 28b49df3 2006-07-18 devnull * large sequential sections on index disk.
807 28b49df3 2006-07-18 devnull * requires nbuf * bufsize memory.
809 28b49df3 2006-07-18 devnull * pass 2 - split each section into minibufs.
810 28b49df3 2006-07-18 devnull * requires nminibuf * bufsize memory.
812 28b49df3 2006-07-18 devnull * pass 3 - read each minibuf into memory and
813 fa325e9b 2020-01-10 cross * write buckets out.
814 28b49df3 2006-07-18 devnull * requires entries/minibuf * IEntrySize memory.
816 28b49df3 2006-07-18 devnull * The larger we set bufsize the less seeking hurts us.
818 28b49df3 2006-07-18 devnull * The fewer sections and minibufs we have, the less
819 28b49df3 2006-07-18 devnull * seeking hurts us.
821 fa325e9b 2020-01-10 cross * The fewer sections and minibufs we have, the
822 28b49df3 2006-07-18 devnull * more entries we end up with in each minibuf
823 fa325e9b 2020-01-10 cross * at the end.
825 28b49df3 2006-07-18 devnull * Shoot for using half our memory to hold each
826 fa325e9b 2020-01-10 cross * minibuf. The chance of a random distribution
827 fa325e9b 2020-01-10 cross * getting off by 2x is quite low.
829 fa325e9b 2020-01-10 cross * Once that is decided, figure out the smallest
830 28b49df3 2006-07-18 devnull * nminibuf and nsection/biggest bufsize we can use
831 28b49df3 2006-07-18 devnull * and still fit in the memory constraints.
834 28b49df3 2006-07-18 devnull /* expected number of clump index entries we'll see */
835 28b49df3 2006-07-18 devnull xclump = nbucket * (double)totalclumps/totalbuckets;
837 28b49df3 2006-07-18 devnull /* number of clumps we want to see in a minibuf */
838 28b49df3 2006-07-18 devnull xminiclump = isectmem/2/IEntrySize;
840 28b49df3 2006-07-18 devnull /* total number of minibufs we need */
841 1d53bf4a 2007-05-03 devnull prod = (xclump+xminiclump-1) / xminiclump;
843 28b49df3 2006-07-18 devnull /* if possible, skip second pass */
844 28b49df3 2006-07-18 devnull if(!dumb && prod*MinBufSize < isectmem){
845 28b49df3 2006-07-18 devnull nbuf = prod;
846 28b49df3 2006-07-18 devnull nminibuf = 1;
848 28b49df3 2006-07-18 devnull /* otherwise use nsection = sqrt(nmini) */
849 28b49df3 2006-07-18 devnull for(nbuf=1; nbuf*nbuf<prod; nbuf++)
851 28b49df3 2006-07-18 devnull if(nbuf*MinBufSize > isectmem)
852 28b49df3 2006-07-18 devnull sysfatal("not enough memory");
853 28b49df3 2006-07-18 devnull nminibuf = nbuf;
855 f5a8ea6f 2011-06-02 rsc if (nbuf == 0) {
856 f5a8ea6f 2011-06-02 rsc fprint(2, "%s: brand-new index, no work to do\n", argv0);
857 f5a8ea6f 2011-06-02 rsc threadexitsall(nil);
860 28b49df3 2006-07-18 devnull /* size buffer to use extra memory */
861 28b49df3 2006-07-18 devnull bufsize = MinBufSize;
862 28b49df3 2006-07-18 devnull while(bufsize*2*nbuf <= isectmem && bufsize < MaxBufSize)
863 28b49df3 2006-07-18 devnull bufsize *= 2;
864 28b49df3 2006-07-18 devnull data = emalloc(nbuf*bufsize);
865 28b49df3 2006-07-18 devnull epbuf = bufsize/IEntrySize;
866 28b49df3 2006-07-18 devnull fprint(2, "%T %s: %,ud buckets, %,ud groups, %,ud minigroups, %,ud buffer\n",
867 28b49df3 2006-07-18 devnull is->part->name, nbucket, nbuf, nminibuf, bufsize);
869 28b49df3 2006-07-18 devnull * Accept index entries from arena procs.
871 28b49df3 2006-07-18 devnull buf = MKNZ(Buf, nbuf);
872 28b49df3 2006-07-18 devnull p = data;
873 28b49df3 2006-07-18 devnull offset = is->blockbase;
874 28b49df3 2006-07-18 devnull bufbuckets = (nbucket+nbuf-1)/nbuf;
875 28b49df3 2006-07-18 devnull for(i=0; i<nbuf; i++){
876 28b49df3 2006-07-18 devnull buf[i].part = is->part;
877 28b49df3 2006-07-18 devnull buf[i].bp = p;
878 28b49df3 2006-07-18 devnull buf[i].wp = p;
879 28b49df3 2006-07-18 devnull p += bufsize;
880 28b49df3 2006-07-18 devnull buf[i].ep = p;
881 28b49df3 2006-07-18 devnull buf[i].boffset = offset;
882 28b49df3 2006-07-18 devnull buf[i].woffset = offset;
883 28b49df3 2006-07-18 devnull if(i < nbuf-1){
884 28b49df3 2006-07-18 devnull offset += bufbuckets*blocksize;
885 28b49df3 2006-07-18 devnull buf[i].eoffset = offset;
887 28b49df3 2006-07-18 devnull offset = is->blockbase + nbucket*blocksize;
888 28b49df3 2006-07-18 devnull buf[i].eoffset = offset;
891 28b49df3 2006-07-18 devnull assert(p == data+nbuf*bufsize);
894 ac5a97e6 2008-07-04 rsc while(recv(is->writechan, &ieb) == 1){
895 ac5a97e6 2008-07-04 rsc if(ieb.nie == 0)
897 ac5a97e6 2008-07-04 rsc for(j=0; j<ieb.nie; j++){
898 ac5a97e6 2008-07-04 rsc ie = ieb.ie[j];
899 ac5a97e6 2008-07-04 rsc buck = score2bucket(is, ie.score);
900 ac5a97e6 2008-07-04 rsc i = buck/bufbuckets;
901 ac5a97e6 2008-07-04 rsc assert(i < nbuf);
902 ac5a97e6 2008-07-04 rsc bwrite(&buf[i], &ie);
906 28b49df3 2006-07-18 devnull add(&indexentries, n);
909 28b49df3 2006-07-18 devnull for(i=0; i<nbuf; i++){
910 28b49df3 2006-07-18 devnull bflush(&buf[i]);
911 28b49df3 2006-07-18 devnull buf[i].bp = nil;
912 28b49df3 2006-07-18 devnull buf[i].ep = nil;
913 28b49df3 2006-07-18 devnull buf[i].wp = nil;
914 28b49df3 2006-07-18 devnull nn += buf[i].nentry;
916 28b49df3 2006-07-18 devnull if(n != nn)
917 28b49df3 2006-07-18 devnull fprint(2, "isectproc bug: n=%ud nn=%ud\n", n, nn);
919 28b49df3 2006-07-18 devnull free(data);
921 28b49df3 2006-07-18 devnull fprint(2, "%T %s: reordering\n", is->part->name);
924 28b49df3 2006-07-18 devnull * Rearrange entries into minibuffers and then
925 28b49df3 2006-07-18 devnull * split each minibuffer into buckets.
926 fa325e9b 2020-01-10 cross * The minibuffer must be sized so that it is
927 1d53bf4a 2007-05-03 devnull * a multiple of blocksize -- ipoolloadblock assumes
928 1d53bf4a 2007-05-03 devnull * that each minibuf starts aligned on a blocksize
929 1d53bf4a 2007-05-03 devnull * boundary.
931 28b49df3 2006-07-18 devnull mbuf = MKN(Minibuf, nminibuf);
932 28b49df3 2006-07-18 devnull mbufbuckets = (bufbuckets+nminibuf-1)/nminibuf;
933 1d53bf4a 2007-05-03 devnull while(mbufbuckets*blocksize % bufsize)
934 1d53bf4a 2007-05-03 devnull mbufbuckets++;
935 28b49df3 2006-07-18 devnull for(i=0; i<nbuf; i++){
937 28b49df3 2006-07-18 devnull * Set up descriptors.
939 28b49df3 2006-07-18 devnull n = buf[i].nentry;
941 28b49df3 2006-07-18 devnull offset = buf[i].boffset;
942 28b49df3 2006-07-18 devnull memset(mbuf, 0, nminibuf*sizeof(mbuf[0]));
943 28b49df3 2006-07-18 devnull for(j=0; j<nminibuf; j++){
944 28b49df3 2006-07-18 devnull mb = &mbuf[j];
945 28b49df3 2006-07-18 devnull mb->boffset = offset;
946 1d53bf4a 2007-05-03 devnull offset += mbufbuckets*blocksize;
947 1d53bf4a 2007-05-03 devnull if(offset > buf[i].eoffset)
948 1d53bf4a 2007-05-03 devnull offset = buf[i].eoffset;
949 1d53bf4a 2007-05-03 devnull mb->eoffset = offset;
950 28b49df3 2006-07-18 devnull mb->roffset = mb->boffset;
951 28b49df3 2006-07-18 devnull mb->woffset = mb->boffset;
952 28b49df3 2006-07-18 devnull mb->nentry = epbuf * (mb->eoffset - mb->boffset)/bufsize;
953 28b49df3 2006-07-18 devnull if(mb->nentry > buf[i].nentry)
954 28b49df3 2006-07-18 devnull mb->nentry = buf[i].nentry;
955 28b49df3 2006-07-18 devnull buf[i].nentry -= mb->nentry;
956 28b49df3 2006-07-18 devnull nn += mb->nentry;
958 28b49df3 2006-07-18 devnull if(n != nn)
959 28b49df3 2006-07-18 devnull fprint(2, "isectproc bug2: n=%ud nn=%ud (i=%d)\n", n, nn, i);;
961 28b49df3 2006-07-18 devnull * Rearrange.
963 28b49df3 2006-07-18 devnull if(!dumb && nminibuf == 1){
964 28b49df3 2006-07-18 devnull mbuf[0].nwentry = mbuf[0].nentry;
965 28b49df3 2006-07-18 devnull mbuf[0].woffset = buf[i].woffset;
967 28b49df3 2006-07-18 devnull ipool = mkipool(is, mbuf, nminibuf, mbufbuckets, bufsize);
968 28b49df3 2006-07-18 devnull ipool->buck0 = bufbuckets*i;
969 28b49df3 2006-07-18 devnull for(j=0; j<nminibuf; j++){
970 28b49df3 2006-07-18 devnull mb = &mbuf[j];
971 28b49df3 2006-07-18 devnull while(mb->nentry > 0){
972 28b49df3 2006-07-18 devnull if(ipool->nfree < epbuf){
973 28b49df3 2006-07-18 devnull ipoolflush1(ipool);
974 fa325e9b 2020-01-10 cross /* ipoolflush1 might change mb->nentry */
975 28b49df3 2006-07-18 devnull continue;
977 28b49df3 2006-07-18 devnull assert(ipool->nfree >= epbuf);
978 28b49df3 2006-07-18 devnull ipoolloadblock(ipool, mb);
981 28b49df3 2006-07-18 devnull ipoolflush(ipool);
983 28b49df3 2006-07-18 devnull for(j=0; j<nminibuf; j++)
984 28b49df3 2006-07-18 devnull nn += mbuf[j].nwentry;
985 28b49df3 2006-07-18 devnull if(n != nn)
986 28b49df3 2006-07-18 devnull fprint(2, "isectproc bug3: n=%ud nn=%ud (i=%d)\n", n, nn, i);
987 28b49df3 2006-07-18 devnull free(ipool);
991 28b49df3 2006-07-18 devnull * Make buckets.
993 28b49df3 2006-07-18 devnull space = 0;
994 28b49df3 2006-07-18 devnull for(j=0; j<nminibuf; j++)
995 28b49df3 2006-07-18 devnull if(space < mbuf[j].woffset - mbuf[j].boffset)
996 28b49df3 2006-07-18 devnull space = mbuf[j].woffset - mbuf[j].boffset;
998 28b49df3 2006-07-18 devnull data = emalloc(space);
999 28b49df3 2006-07-18 devnull for(j=0; j<nminibuf; j++){
1000 28b49df3 2006-07-18 devnull mb = &mbuf[j];
1001 28b49df3 2006-07-18 devnull sortminibuffer(is, mb, data, space, bufsize);
1003 28b49df3 2006-07-18 devnull free(data);
1006 28b49df3 2006-07-18 devnull sendp(isectdonechan, is);
