1 a0d146ed 2005-07-12 devnull /*
  2 28b49df3 2006-07-18 devnull  * Rebuild the index from scratch, in place.
  3 a0d146ed 2005-07-12 devnull  */
  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"
  7 a0d146ed 2005-07-12 devnull 
  8 28b49df3 2006-07-18 devnull enum
  9 a0d146ed 2005-07-12 devnull {
 10 28b49df3 2006-07-18 devnull 	MinBufSize = 64*1024,
 11 28b49df3 2006-07-18 devnull 	MaxBufSize = 4*1024*1024,
 12 28b49df3 2006-07-18 devnull };
 13 a0d146ed 2005-07-12 devnull 
 14 ac5a97e6 2008-07-04 rsc typedef struct IEntryBuf IEntryBuf;
 15 ac5a97e6 2008-07-04 rsc struct IEntryBuf 
 16 ac5a97e6 2008-07-04 rsc {
 17 ac5a97e6 2008-07-04 rsc 	IEntry ie[100];
 18 ac5a97e6 2008-07-04 rsc 	int nie;
 19 ac5a97e6 2008-07-04 rsc };
 20 ac5a97e6 2008-07-04 rsc 
 21 ac5a97e6 2008-07-04 rsc typedef struct ScoreBuf ScoreBuf;
 22 ac5a97e6 2008-07-04 rsc struct ScoreBuf
 23 ac5a97e6 2008-07-04 rsc {
 24 ac5a97e6 2008-07-04 rsc 	uchar score[100][VtScoreSize];
 25 ac5a97e6 2008-07-04 rsc 	int nscore;
 26 ac5a97e6 2008-07-04 rsc };
 27 ac5a97e6 2008-07-04 rsc 
 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;
 34 a0d146ed 2005-07-12 devnull 
 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;
 41 a0d146ed 2005-07-12 devnull 
 42 28b49df3 2006-07-18 devnull u64int	arenaentries;
 43 28b49df3 2006-07-18 devnull u64int	skipentries;
 44 28b49df3 2006-07-18 devnull u64int	indexentries;
 45 a0d146ed 2005-07-12 devnull 
 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*);
 49 a0d146ed 2005-07-12 devnull 
 50 a0d146ed 2005-07-12 devnull void
 51 a0d146ed 2005-07-12 devnull usage(void)
 52 a0d146ed 2005-07-12 devnull {
 53 45ac814c 2007-10-29 rsc 	fprint(2, "usage: buildindex [-bd] [-i isect]... [-M imem] venti.conf\n");
 54 28b49df3 2006-07-18 devnull 	threadexitsall("usage");
 55 a0d146ed 2005-07-12 devnull }
 56 a0d146ed 2005-07-12 devnull 
 57 a0d146ed 2005-07-12 devnull void
 58 a0d146ed 2005-07-12 devnull threadmain(int argc, char *argv[])
 59 a0d146ed 2005-07-12 devnull {
 60 28b49df3 2006-07-18 devnull 	int fd, i, napart;
 61 28b49df3 2006-07-18 devnull 	u32int bcmem, imem;
 62 28b49df3 2006-07-18 devnull 	Config conf;
 63 28b49df3 2006-07-18 devnull 	Part *p;
 64 28b49df3 2006-07-18 devnull 	
 65 23fb2edb 2005-07-24 devnull 	ventifmtinstall();
 66 28b49df3 2006-07-18 devnull 	imem = 256*1024*1024;
 67 a0d146ed 2005-07-12 devnull 	ARGBEGIN{
 68 28b49df3 2006-07-18 devnull 	case 'b':
 69 28b49df3 2006-07-18 devnull 		bloom = 1;
 70 a0d146ed 2005-07-12 devnull 		break;
 71 45ac814c 2007-10-29 rsc 	case 'd':	/* debugging - make sure to run all 3 passes */
 72 45ac814c 2007-10-29 rsc 		dumb = 1;
 73 45ac814c 2007-10-29 rsc 		break;
 74 28b49df3 2006-07-18 devnull 	case 'i':
 75 28b49df3 2006-07-18 devnull 		isect = vtrealloc(isect, (nisect+1)*sizeof(isect[0]));
 76 28b49df3 2006-07-18 devnull 		isect[nisect++] = EARGF(usage());
 77 a0d146ed 2005-07-12 devnull 		break;
 78 28b49df3 2006-07-18 devnull 	case 'M':
 79 28b49df3 2006-07-18 devnull 		imem = unittoull(EARGF(usage()));
 80 28b49df3 2006-07-18 devnull 		break;
 81 a0d146ed 2005-07-12 devnull 	default:
 82 a0d146ed 2005-07-12 devnull 		usage();
 83 a0d146ed 2005-07-12 devnull 		break;
 84 a0d146ed 2005-07-12 devnull 	}ARGEND
 85 1d53bf4a 2007-05-03 devnull 
 86 28b49df3 2006-07-18 devnull 	if(argc != 1)
 87 a0d146ed 2005-07-12 devnull 		usage();
 88 a0d146ed 2005-07-12 devnull 
 89 a0d146ed 2005-07-12 devnull 	if(initventi(argv[0], &conf) < 0)
 90 a0d146ed 2005-07-12 devnull 		sysfatal("can't init venti: %r");
 91 28b49df3 2006-07-18 devnull 	ix = mainindex;
 92 28b49df3 2006-07-18 devnull 	if(nisect == 0 && ix->bloom)
 93 28b49df3 2006-07-18 devnull 		bloom = 1;
 94 28b49df3 2006-07-18 devnull 	if(bloom && ix->bloom && resetbloom(ix->bloom) < 0)
 95 28b49df3 2006-07-18 devnull 		sysfatal("loadbloom: %r");
 96 28b49df3 2006-07-18 devnull 	if(bloom && !ix->bloom)
 97 28b49df3 2006-07-18 devnull 		sysfatal("-b specified but no bloom filter");
 98 28b49df3 2006-07-18 devnull 	if(!bloom)
 99 28b49df3 2006-07-18 devnull 		ix->bloom = nil;
100 28b49df3 2006-07-18 devnull 	isectmem = imem/ix->nsects;
101 a0d146ed 2005-07-12 devnull 
102 28b49df3 2006-07-18 devnull 	/*
103 28b49df3 2006-07-18 devnull 	 * safety first - only need read access to arenas
104 28b49df3 2006-07-18 devnull 	 */
105 28b49df3 2006-07-18 devnull 	p = nil;
106 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->narenas; i++){
107 28b49df3 2006-07-18 devnull 		if(ix->arenas[i]->part != p){
108 28b49df3 2006-07-18 devnull 			p = ix->arenas[i]->part;
109 28b49df3 2006-07-18 devnull 			if((fd = open(p->filename, OREAD)) < 0)
110 28b49df3 2006-07-18 devnull 				sysfatal("cannot reopen %s: %r", p->filename);
111 28b49df3 2006-07-18 devnull 			dup(fd, p->fd);
112 28b49df3 2006-07-18 devnull 			close(fd);
113 28b49df3 2006-07-18 devnull 		}
114 28b49df3 2006-07-18 devnull 	}
115 28b49df3 2006-07-18 devnull 	
116 28b49df3 2006-07-18 devnull 	/*
117 28b49df3 2006-07-18 devnull 	 * need a block for every arena
118 28b49df3 2006-07-18 devnull 	 */
119 28b49df3 2006-07-18 devnull 	bcmem = maxblocksize * (mainindex->narenas + 16);
120 a0d146ed 2005-07-12 devnull 	if(0) fprint(2, "initialize %d bytes of disk block cache\n", bcmem);
121 a0d146ed 2005-07-12 devnull 	initdcache(bcmem);
122 28b49df3 2006-07-18 devnull 	
123 28b49df3 2006-07-18 devnull 	totalclumps = 0;
124 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->narenas; i++)
125 28b49df3 2006-07-18 devnull 		totalclumps += ix->arenas[i]->diskstats.clumps;
126 28b49df3 2006-07-18 devnull 	
127 28b49df3 2006-07-18 devnull 	totalbuckets = 0;
128 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->nsects; i++)
129 28b49df3 2006-07-18 devnull 		totalbuckets += ix->sects[i]->blocks;
130 28b49df3 2006-07-18 devnull 	fprint(2, "%,lld clumps, %,lld buckets\n", totalclumps, totalbuckets);
131 a0d146ed 2005-07-12 devnull 
132 28b49df3 2006-07-18 devnull 	/* start index procs */
133 28b49df3 2006-07-18 devnull 	fprint(2, "%T read index\n");
134 ac5a97e6 2008-07-04 rsc 	isectdonechan = chancreate(sizeof(void*), 1);
135 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->nsects; i++){
136 7e452401 2007-04-27 devnull 		if(shouldprocess(ix->sects[i])){
137 ac5a97e6 2008-07-04 rsc 			ix->sects[i]->writechan = chancreate(sizeof(IEntryBuf), 1);
138 7e452401 2007-04-27 devnull 			vtproc(isectproc, ix->sects[i]);
139 7e452401 2007-04-27 devnull 		}
140 28b49df3 2006-07-18 devnull 	}
141 28b49df3 2006-07-18 devnull 	
142 28b49df3 2006-07-18 devnull 	for(i=0; i<nisect; i++)
143 28b49df3 2006-07-18 devnull 		if(isect[i])
144 28b49df3 2006-07-18 devnull 			fprint(2, "warning: did not find index section %s\n", isect[i]);
145 a0d146ed 2005-07-12 devnull 
146 28b49df3 2006-07-18 devnull 	/* start arena procs */
147 28b49df3 2006-07-18 devnull 	p = nil;
148 28b49df3 2006-07-18 devnull 	napart = 0;
149 28b49df3 2006-07-18 devnull 	arenadonechan = chancreate(sizeof(void*), 0);
150 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->narenas; i++){
151 28b49df3 2006-07-18 devnull 		if(ix->arenas[i]->part != p){
152 28b49df3 2006-07-18 devnull 			p = ix->arenas[i]->part;
153 28b49df3 2006-07-18 devnull 			vtproc(arenapartproc, p);
154 28b49df3 2006-07-18 devnull 			napart++;
155 28b49df3 2006-07-18 devnull 		}
156 28b49df3 2006-07-18 devnull 	}
157 a0d146ed 2005-07-12 devnull 
158 28b49df3 2006-07-18 devnull 	/* wait for arena procs to finish */
159 28b49df3 2006-07-18 devnull 	for(i=0; i<napart; i++)
160 28b49df3 2006-07-18 devnull 		recvp(arenadonechan);
161 a0d146ed 2005-07-12 devnull 
162 28b49df3 2006-07-18 devnull 	/* tell index procs to finish */
163 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->nsects; i++)
164 28b49df3 2006-07-18 devnull 		if(ix->sects[i]->writechan)
165 28b49df3 2006-07-18 devnull 			send(ix->sects[i]->writechan, nil);
166 28b49df3 2006-07-18 devnull 
167 28b49df3 2006-07-18 devnull 	/* wait for index procs to finish */
168 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->nsects; i++)
169 28b49df3 2006-07-18 devnull 		if(ix->sects[i]->writechan)
170 28b49df3 2006-07-18 devnull 			recvp(isectdonechan);
171 28b49df3 2006-07-18 devnull 
172 28b49df3 2006-07-18 devnull 	if(ix->bloom && writebloom(ix->bloom) < 0)
173 28b49df3 2006-07-18 devnull 		fprint(2, "writing bloom filter: %r\n");
174 28b49df3 2006-07-18 devnull 
175 28b49df3 2006-07-18 devnull 	fprint(2, "%T done arenaentries=%,lld indexed=%,lld (nskip=%,lld)\n", 
176 28b49df3 2006-07-18 devnull 		arenaentries, indexentries, skipentries);
177 28b49df3 2006-07-18 devnull 	threadexitsall(nil);
178 28b49df3 2006-07-18 devnull }
179 28b49df3 2006-07-18 devnull 
180 28b49df3 2006-07-18 devnull static int
181 28b49df3 2006-07-18 devnull shouldprocess(ISect *is)
182 28b49df3 2006-07-18 devnull {
183 28b49df3 2006-07-18 devnull 	int i;
184 a0d146ed 2005-07-12 devnull 	
185 28b49df3 2006-07-18 devnull 	if(nisect == 0)
186 28b49df3 2006-07-18 devnull 		return 1;
187 d4daacde 2005-07-24 devnull 
188 28b49df3 2006-07-18 devnull 	for(i=0; i<nisect; i++)
189 28b49df3 2006-07-18 devnull 		if(isect[i] && strcmp(isect[i], is->name) == 0){
190 28b49df3 2006-07-18 devnull 			isect[i] = nil;
191 28b49df3 2006-07-18 devnull 			return 1;
192 28b49df3 2006-07-18 devnull 		}
193 28b49df3 2006-07-18 devnull 	return 0;
194 28b49df3 2006-07-18 devnull }
195 28b49df3 2006-07-18 devnull 
196 28b49df3 2006-07-18 devnull static void
197 28b49df3 2006-07-18 devnull add(u64int *a, u64int n)
198 28b49df3 2006-07-18 devnull {
199 28b49df3 2006-07-18 devnull 	static Lock l;
200 28b49df3 2006-07-18 devnull 	
201 28b49df3 2006-07-18 devnull 	lock(&l);
202 28b49df3 2006-07-18 devnull 	*a += n;
203 28b49df3 2006-07-18 devnull 	unlock(&l);
204 28b49df3 2006-07-18 devnull }
205 28b49df3 2006-07-18 devnull 
206 28b49df3 2006-07-18 devnull /*
207 28b49df3 2006-07-18 devnull  * Read through an arena partition and send each of its IEntries
208 28b49df3 2006-07-18 devnull  * to the appropriate index section.  When finished, send on
209 28b49df3 2006-07-18 devnull  * arenadonechan.
210 28b49df3 2006-07-18 devnull  */
211 28b49df3 2006-07-18 devnull enum
212 28b49df3 2006-07-18 devnull {
213 28b49df3 2006-07-18 devnull 	ClumpChunks = 32*1024,
214 28b49df3 2006-07-18 devnull };
215 28b49df3 2006-07-18 devnull static void
216 28b49df3 2006-07-18 devnull arenapartproc(void *v)
217 28b49df3 2006-07-18 devnull {
218 28b49df3 2006-07-18 devnull 	int i, j, n, nskip, x;
219 28b49df3 2006-07-18 devnull 	u32int clump;
220 28b49df3 2006-07-18 devnull 	u64int addr, tot;
221 28b49df3 2006-07-18 devnull 	Arena *a;
222 28b49df3 2006-07-18 devnull 	ClumpInfo *ci, *cis;
223 28b49df3 2006-07-18 devnull 	IEntry ie;
224 28b49df3 2006-07-18 devnull 	Part *p;
225 ac5a97e6 2008-07-04 rsc 	IEntryBuf *buf, *b;
226 ac5a97e6 2008-07-04 rsc 	uchar *score;
227 ac5a97e6 2008-07-04 rsc 	ScoreBuf sb;
228 28b49df3 2006-07-18 devnull 	
229 28b49df3 2006-07-18 devnull 	p = v;
230 28b49df3 2006-07-18 devnull 	threadsetname("arenaproc %s", p->name);
231 ac5a97e6 2008-07-04 rsc 	buf = MKNZ(IEntryBuf, ix->nsects);
232 28b49df3 2006-07-18 devnull 
233 28b49df3 2006-07-18 devnull 	nskip = 0;
234 28b49df3 2006-07-18 devnull 	tot = 0;
235 ac5a97e6 2008-07-04 rsc 	sb.nscore = 0;
236 28b49df3 2006-07-18 devnull 	cis = MKN(ClumpInfo, ClumpChunks);
237 28b49df3 2006-07-18 devnull 	for(i=0; i<ix->narenas; i++){
238 28b49df3 2006-07-18 devnull 		a = ix->arenas[i];
239 28b49df3 2006-07-18 devnull 		if(a->part != p)
240 28b49df3 2006-07-18 devnull 			continue;
241 28b49df3 2006-07-18 devnull 		if(a->memstats.clumps)
242 28b49df3 2006-07-18 devnull 			fprint(2, "%T arena %s: %d entries\n", 
243 28b49df3 2006-07-18 devnull 				a->name, a->memstats.clumps);
244 45ac814c 2007-10-29 rsc 		/*
245 45ac814c 2007-10-29 rsc 		 * Running the loop backwards accesses the 
246 45ac814c 2007-10-29 rsc 		 * clump info blocks forwards, since they are
247 45ac814c 2007-10-29 rsc 		 * stored in reverse order at the end of the arena.
248 45ac814c 2007-10-29 rsc 		 * This speeds things slightly.
249 45ac814c 2007-10-29 rsc 		 */
250 45ac814c 2007-10-29 rsc 		addr = ix->amap[i].start + a->memstats.used;
251 45ac814c 2007-10-29 rsc 		for(clump=a->memstats.clumps; clump > 0; clump-=n){
252 28b49df3 2006-07-18 devnull 			n = ClumpChunks;
253 45ac814c 2007-10-29 rsc 			if(n > clump)
254 45ac814c 2007-10-29 rsc 				n = clump;
255 45ac814c 2007-10-29 rsc 			if(readclumpinfos(a, clump-n, cis, n) != n){
256 28b49df3 2006-07-18 devnull 				fprint(2, "%T arena %s: directory read: %r\n", a->name);
257 28b49df3 2006-07-18 devnull 				errors = 1;
258 28b49df3 2006-07-18 devnull 				break;
259 28b49df3 2006-07-18 devnull 			}
260 45ac814c 2007-10-29 rsc 			for(j=n-1; j>=0; j--){
261 28b49df3 2006-07-18 devnull 				ci = &cis[j];
262 28b49df3 2006-07-18 devnull 				ie.ia.type = ci->type;
263 28b49df3 2006-07-18 devnull 				ie.ia.size = ci->uncsize;
264 45ac814c 2007-10-29 rsc 				addr -= ci->size + ClumpSize;
265 28b49df3 2006-07-18 devnull 				ie.ia.addr = addr;
266 28b49df3 2006-07-18 devnull 				ie.ia.blocks = (ci->size + ClumpSize + (1<<ABlockLog)-1) >> ABlockLog;
267 28b49df3 2006-07-18 devnull 				scorecp(ie.score, ci->score);
268 28b49df3 2006-07-18 devnull 				if(ci->type == VtCorruptType)
269 28b49df3 2006-07-18 devnull 					nskip++;
270 28b49df3 2006-07-18 devnull 				else{
271 28b49df3 2006-07-18 devnull 					tot++;
272 28b49df3 2006-07-18 devnull 					x = indexsect(ix, ie.score);
273 28b49df3 2006-07-18 devnull 					assert(0 <= x && x < ix->nsects);
274 ac5a97e6 2008-07-04 rsc 					if(ix->sects[x]->writechan) {
275 ac5a97e6 2008-07-04 rsc 						b = &buf[x];
276 ac5a97e6 2008-07-04 rsc 						b->ie[b->nie] = ie;
277 ac5a97e6 2008-07-04 rsc 						b->nie++;
278 ac5a97e6 2008-07-04 rsc 						if(b->nie == nelem(b->ie)) {
279 ac5a97e6 2008-07-04 rsc 							send(ix->sects[x]->writechan, b);
280 ac5a97e6 2008-07-04 rsc 							b->nie = 0;
281 ac5a97e6 2008-07-04 rsc 						}
282 ac5a97e6 2008-07-04 rsc 					}
283 ac5a97e6 2008-07-04 rsc 					if(ix->bloom) {
284 ac5a97e6 2008-07-04 rsc 						score = sb.score[sb.nscore++];
285 ac5a97e6 2008-07-04 rsc 						scorecp(score, ie.score);
286 ac5a97e6 2008-07-04 rsc 						if(sb.nscore == nelem(sb.score)) {
287 ac5a97e6 2008-07-04 rsc 							markbloomfiltern(ix->bloom, sb.score, sb.nscore);
288 ac5a97e6 2008-07-04 rsc 							sb.nscore = 0;
289 ac5a97e6 2008-07-04 rsc 						}
290 ac5a97e6 2008-07-04 rsc 					}
291 28b49df3 2006-07-18 devnull 				}
292 28b49df3 2006-07-18 devnull 			}
293 28b49df3 2006-07-18 devnull 		}
294 45ac814c 2007-10-29 rsc 		if(addr != ix->amap[i].start)
295 45ac814c 2007-10-29 rsc 			fprint(2, "%T arena %s: clump miscalculation %lld != %lld\n", a->name, addr, ix->amap[i].start);
296 28b49df3 2006-07-18 devnull 	}
297 28b49df3 2006-07-18 devnull 	add(&arenaentries, tot);
298 28b49df3 2006-07-18 devnull 	add(&skipentries, nskip);
299 ac5a97e6 2008-07-04 rsc 	
300 ac5a97e6 2008-07-04 rsc 	for(i=0; i<ix->nsects; i++)
301 ac5a97e6 2008-07-04 rsc 		if(ix->sects[i]->writechan && buf[i].nie > 0)
302 ac5a97e6 2008-07-04 rsc 			send(ix->sects[i]->writechan, &buf[i]);
303 ac5a97e6 2008-07-04 rsc 	free(buf);
304 ac5a97e6 2008-07-04 rsc 	free(cis);
305 ac5a97e6 2008-07-04 rsc 	if(ix->bloom && sb.nscore > 0)
306 ac5a97e6 2008-07-04 rsc 		markbloomfiltern(ix->bloom, sb.score, sb.nscore);
307 28b49df3 2006-07-18 devnull 	sendp(arenadonechan, p);
308 28b49df3 2006-07-18 devnull }
309 28b49df3 2006-07-18 devnull 
310 28b49df3 2006-07-18 devnull /*
311 28b49df3 2006-07-18 devnull  * Convert score into relative bucket number in isect.
312 28b49df3 2006-07-18 devnull  * Can pass a packed ientry instead of score - score is first.
313 28b49df3 2006-07-18 devnull  */
314 28b49df3 2006-07-18 devnull static u32int
315 28b49df3 2006-07-18 devnull score2bucket(ISect *is, uchar *score)
316 28b49df3 2006-07-18 devnull {
317 28b49df3 2006-07-18 devnull 	u32int b;
318 28b49df3 2006-07-18 devnull 	
319 28b49df3 2006-07-18 devnull 	b = hashbits(score, 32)/ix->div;
320 6b9887c7 2007-05-03 devnull 	if(b < is->start || b >= is->stop){
321 6b9887c7 2007-05-03 devnull 		fprint(2, "score2bucket: score=%V div=%d b=%ud start=%ud stop=%ud\n",
322 6b9887c7 2007-05-03 devnull 			score, ix->div, b, is->start, is->stop);
323 6b9887c7 2007-05-03 devnull 	}
324 28b49df3 2006-07-18 devnull 	assert(is->start <= b && b < is->stop);
325 28b49df3 2006-07-18 devnull 	return b - is->start;
326 28b49df3 2006-07-18 devnull }
327 28b49df3 2006-07-18 devnull 
328 28b49df3 2006-07-18 devnull /*
329 28b49df3 2006-07-18 devnull  * Convert offset in index section to bucket number.
330 28b49df3 2006-07-18 devnull  */
331 28b49df3 2006-07-18 devnull static u32int
332 28b49df3 2006-07-18 devnull offset2bucket(ISect *is, u64int offset)
333 28b49df3 2006-07-18 devnull {
334 28b49df3 2006-07-18 devnull 	u32int b;
335 28b49df3 2006-07-18 devnull 	
336 28b49df3 2006-07-18 devnull 	assert(is->blockbase <= offset);
337 28b49df3 2006-07-18 devnull 	offset -= is->blockbase;
338 28b49df3 2006-07-18 devnull 	b = offset/is->blocksize;
339 28b49df3 2006-07-18 devnull 	assert(b < is->stop-is->start);
340 28b49df3 2006-07-18 devnull 	return b;
341 28b49df3 2006-07-18 devnull }
342 28b49df3 2006-07-18 devnull 
343 28b49df3 2006-07-18 devnull /*
344 28b49df3 2006-07-18 devnull  * Convert bucket number to offset.
345 28b49df3 2006-07-18 devnull  */
346 28b49df3 2006-07-18 devnull static u64int
347 28b49df3 2006-07-18 devnull bucket2offset(ISect *is, u32int b)
348 28b49df3 2006-07-18 devnull {
349 28b49df3 2006-07-18 devnull 	assert(b <= is->stop-is->start);
350 28b49df3 2006-07-18 devnull 	return is->blockbase + (u64int)b*is->blocksize;
351 28b49df3 2006-07-18 devnull }
352 28b49df3 2006-07-18 devnull 
353 28b49df3 2006-07-18 devnull /* 
354 28b49df3 2006-07-18 devnull  * IEntry buffers to hold initial round of spraying.
355 28b49df3 2006-07-18 devnull  */
356 28b49df3 2006-07-18 devnull typedef struct Buf Buf;
357 28b49df3 2006-07-18 devnull struct Buf
358 28b49df3 2006-07-18 devnull {
359 28b49df3 2006-07-18 devnull 	Part *part;			/* partition being written */
360 28b49df3 2006-07-18 devnull 	uchar *bp;		/* current block */
361 28b49df3 2006-07-18 devnull 	uchar *ep;		/* end of block */
362 28b49df3 2006-07-18 devnull 	uchar *wp;		/* write position in block */
363 28b49df3 2006-07-18 devnull 	u64int boffset;		/* start offset */
364 28b49df3 2006-07-18 devnull 	u64int woffset;		/* next write offset */
365 28b49df3 2006-07-18 devnull 	u64int eoffset;		/* end offset */
366 28b49df3 2006-07-18 devnull 	u32int nentry;		/* number of entries written */
367 28b49df3 2006-07-18 devnull };
368 28b49df3 2006-07-18 devnull 
369 28b49df3 2006-07-18 devnull static void
370 28b49df3 2006-07-18 devnull bflush(Buf *buf)
371 28b49df3 2006-07-18 devnull {
372 28b49df3 2006-07-18 devnull 	u32int bufsize;
373 28b49df3 2006-07-18 devnull 	
374 28b49df3 2006-07-18 devnull 	if(buf->woffset >= buf->eoffset)
375 1d53bf4a 2007-05-03 devnull 		sysfatal("buf index chunk overflow - need bigger index");
376 28b49df3 2006-07-18 devnull 	bufsize = buf->ep - buf->bp;
377 28b49df3 2006-07-18 devnull 	if(writepart(buf->part, buf->woffset, buf->bp, bufsize) < 0){
378 28b49df3 2006-07-18 devnull 		fprint(2, "write %s: %r\n", buf->part->name);
379 28b49df3 2006-07-18 devnull 		errors = 1;
380 28b49df3 2006-07-18 devnull 	}
381 28b49df3 2006-07-18 devnull 	buf->woffset += bufsize;
382 28b49df3 2006-07-18 devnull 	memset(buf->bp, 0, bufsize);
383 28b49df3 2006-07-18 devnull 	buf->wp = buf->bp;
384 28b49df3 2006-07-18 devnull }
385 28b49df3 2006-07-18 devnull 
386 28b49df3 2006-07-18 devnull static void
387 28b49df3 2006-07-18 devnull bwrite(Buf *buf, IEntry *ie)
388 28b49df3 2006-07-18 devnull {
389 28b49df3 2006-07-18 devnull 	if(buf->wp+IEntrySize > buf->ep)
390 28b49df3 2006-07-18 devnull 		bflush(buf);
391 28b49df3 2006-07-18 devnull 	assert(buf->bp <= buf->wp && buf->wp < buf->ep);
392 28b49df3 2006-07-18 devnull 	packientry(ie, buf->wp);
393 28b49df3 2006-07-18 devnull 	buf->wp += IEntrySize;
394 28b49df3 2006-07-18 devnull 	assert(buf->bp <= buf->wp && buf->wp <= buf->ep);
395 28b49df3 2006-07-18 devnull 	buf->nentry++;
396 28b49df3 2006-07-18 devnull }
397 28b49df3 2006-07-18 devnull 
398 28b49df3 2006-07-18 devnull /*
399 28b49df3 2006-07-18 devnull  * Minibuffer.  In-memory data structure holds our place
400 28b49df3 2006-07-18 devnull  * in the buffer but has no block data.  We are writing and
401 28b49df3 2006-07-18 devnull  * reading the minibuffers at the same time.  (Careful!)
402 28b49df3 2006-07-18 devnull  */
403 28b49df3 2006-07-18 devnull typedef struct Minibuf Minibuf;
404 28b49df3 2006-07-18 devnull struct Minibuf
405 28b49df3 2006-07-18 devnull {
406 28b49df3 2006-07-18 devnull 	u64int boffset;		/* start offset */
407 28b49df3 2006-07-18 devnull 	u64int roffset;		/* read offset */
408 28b49df3 2006-07-18 devnull 	u64int woffset;		/* write offset */
409 28b49df3 2006-07-18 devnull 	u64int eoffset;		/* end offset */
410 28b49df3 2006-07-18 devnull 	u32int nentry;		/* # entries left to read */
411 28b49df3 2006-07-18 devnull 	u32int nwentry;	/* # entries written */
412 28b49df3 2006-07-18 devnull };
413 28b49df3 2006-07-18 devnull 
414 28b49df3 2006-07-18 devnull /*
415 28b49df3 2006-07-18 devnull  * Index entry pool.  Used when trying to shuffle around 
416 28b49df3 2006-07-18 devnull  * the entries in a big buffer into the corresponding M minibuffers.
417 28b49df3 2006-07-18 devnull  * Sized to hold M*EntriesPerBlock entries, so that there will always
418 28b49df3 2006-07-18 devnull  * either be room in the pool for another block worth of entries
419 28b49df3 2006-07-18 devnull  * or there will be an entire block worth of sorted entries to 
420 28b49df3 2006-07-18 devnull  * write out.
421 28b49df3 2006-07-18 devnull  */
422 28b49df3 2006-07-18 devnull typedef struct IEntryLink IEntryLink;
423 28b49df3 2006-07-18 devnull typedef struct IPool IPool;
424 28b49df3 2006-07-18 devnull 
425 28b49df3 2006-07-18 devnull struct IEntryLink
426 28b49df3 2006-07-18 devnull {
427 28b49df3 2006-07-18 devnull 	uchar ie[IEntrySize];		/* raw IEntry */
428 28b49df3 2006-07-18 devnull 	IEntryLink *next;		/* next in chain */
429 28b49df3 2006-07-18 devnull };
430 28b49df3 2006-07-18 devnull 
431 28b49df3 2006-07-18 devnull struct IPool
432 28b49df3 2006-07-18 devnull {
433 28b49df3 2006-07-18 devnull 	ISect *isect;
434 28b49df3 2006-07-18 devnull 	u32int buck0;			/* first bucket in pool */
435 28b49df3 2006-07-18 devnull 	u32int mbufbuckets;	/* buckets per minibuf */
436 28b49df3 2006-07-18 devnull 	IEntryLink *entry;		/* all IEntryLinks */
437 28b49df3 2006-07-18 devnull 	u32int nentry;			/* # of IEntryLinks */
438 28b49df3 2006-07-18 devnull 	IEntryLink *free;		/* free list */
439 28b49df3 2006-07-18 devnull 	u32int nfree;			/* # on free list */
440 28b49df3 2006-07-18 devnull 	Minibuf *mbuf;			/* all minibufs */
441 28b49df3 2006-07-18 devnull 	u32int nmbuf;			/* # of minibufs */
442 28b49df3 2006-07-18 devnull 	IEntryLink **mlist;		/* lists for each minibuf */
443 28b49df3 2006-07-18 devnull 	u32int *mcount;		/* # on each mlist[i] */
444 28b49df3 2006-07-18 devnull 	u32int bufsize;			/* block buffer size */
445 28b49df3 2006-07-18 devnull 	uchar *rbuf;			/* read buffer */
446 28b49df3 2006-07-18 devnull 	uchar *wbuf;			/* write buffer */
447 28b49df3 2006-07-18 devnull 	u32int epbuf;			/* entries per block buffer */
448 28b49df3 2006-07-18 devnull };
449 28b49df3 2006-07-18 devnull 
450 28b49df3 2006-07-18 devnull /*
451 28b49df3 2006-07-18 devnull static int
452 28b49df3 2006-07-18 devnull countsokay(IPool *p)
453 28b49df3 2006-07-18 devnull {
454 28b49df3 2006-07-18 devnull 	int i;
455 28b49df3 2006-07-18 devnull 	u64int n;
456 28b49df3 2006-07-18 devnull 	
457 28b49df3 2006-07-18 devnull 	n = 0;
458 28b49df3 2006-07-18 devnull 	for(i=0; i<p->nmbuf; i++)
459 28b49df3 2006-07-18 devnull 		n += p->mcount[i];
460 28b49df3 2006-07-18 devnull 	n += p->nfree;
461 28b49df3 2006-07-18 devnull 	if(n != p->nentry){
462 28b49df3 2006-07-18 devnull 		print("free %ud:", p->nfree);
463 28b49df3 2006-07-18 devnull 		for(i=0; i<p->nmbuf; i++)
464 28b49df3 2006-07-18 devnull 			print(" %ud", p->mcount[i]);
465 28b49df3 2006-07-18 devnull 		print(" = %lld nentry: %ud\n", n, p->nentry);
466 28b49df3 2006-07-18 devnull 	}
467 28b49df3 2006-07-18 devnull 	return n == p->nentry;
468 28b49df3 2006-07-18 devnull }
469 28b49df3 2006-07-18 devnull */
470 28b49df3 2006-07-18 devnull 
471 28b49df3 2006-07-18 devnull static IPool*
472 28b49df3 2006-07-18 devnull mkipool(ISect *isect, Minibuf *mbuf, u32int nmbuf, 
473 28b49df3 2006-07-18 devnull 	u32int mbufbuckets, u32int bufsize)
474 28b49df3 2006-07-18 devnull {
475 28b49df3 2006-07-18 devnull 	u32int i, nentry;
476 28b49df3 2006-07-18 devnull 	uchar *data;
477 28b49df3 2006-07-18 devnull 	IPool *p;
478 28b49df3 2006-07-18 devnull 	IEntryLink *l;
479 28b49df3 2006-07-18 devnull 	
480 28b49df3 2006-07-18 devnull 	nentry = (nmbuf+1)*bufsize / IEntrySize;
481 28b49df3 2006-07-18 devnull 	p = ezmalloc(sizeof(IPool)
482 28b49df3 2006-07-18 devnull 		+nentry*sizeof(IEntry)
483 28b49df3 2006-07-18 devnull 		+nmbuf*sizeof(IEntryLink*)
484 28b49df3 2006-07-18 devnull 		+nmbuf*sizeof(u32int)
485 28b49df3 2006-07-18 devnull 		+3*bufsize);
486 28b49df3 2006-07-18 devnull 	
487 28b49df3 2006-07-18 devnull 	p->isect = isect;
488 28b49df3 2006-07-18 devnull 	p->mbufbuckets = mbufbuckets;
489 28b49df3 2006-07-18 devnull 	p->bufsize = bufsize;
490 28b49df3 2006-07-18 devnull 	p->entry = (IEntryLink*)(p+1);
491 28b49df3 2006-07-18 devnull 	p->nentry = nentry;
492 28b49df3 2006-07-18 devnull 	p->mlist = (IEntryLink**)(p->entry+nentry);
493 28b49df3 2006-07-18 devnull 	p->mcount = (u32int*)(p->mlist+nmbuf);
494 28b49df3 2006-07-18 devnull 	p->nmbuf = nmbuf;
495 28b49df3 2006-07-18 devnull 	p->mbuf = mbuf;
496 28b49df3 2006-07-18 devnull 	data = (uchar*)(p->mcount+nmbuf);
497 e6b0276e 2006-11-06 devnull 	data += bufsize - (uintptr)data%bufsize;
498 28b49df3 2006-07-18 devnull 	p->rbuf = data;
499 28b49df3 2006-07-18 devnull 	p->wbuf = data+bufsize;
500 28b49df3 2006-07-18 devnull 	p->epbuf = bufsize/IEntrySize;
501 28b49df3 2006-07-18 devnull 
502 28b49df3 2006-07-18 devnull 	for(i=0; i<p->nentry; i++){
503 28b49df3 2006-07-18 devnull 		l = &p->entry[i];
504 28b49df3 2006-07-18 devnull 		l->next = p->free;
505 28b49df3 2006-07-18 devnull 		p->free = l;
506 28b49df3 2006-07-18 devnull 		p->nfree++;
507 28b49df3 2006-07-18 devnull 	}
508 28b49df3 2006-07-18 devnull 	return p;
509 a0d146ed 2005-07-12 devnull }
510 28b49df3 2006-07-18 devnull 
511 28b49df3 2006-07-18 devnull /* 
512 28b49df3 2006-07-18 devnull  * Add the index entry ie to the pool p.
513 28b49df3 2006-07-18 devnull  * Caller must know there is room.
514 28b49df3 2006-07-18 devnull  */
515 28b49df3 2006-07-18 devnull static void
516 28b49df3 2006-07-18 devnull ipoolinsert(IPool *p, uchar *ie)
517 28b49df3 2006-07-18 devnull {
518 28b49df3 2006-07-18 devnull 	u32int buck, x;
519 28b49df3 2006-07-18 devnull 	IEntryLink *l;
520 28b49df3 2006-07-18 devnull 
521 28b49df3 2006-07-18 devnull 	assert(p->free != nil);
522 28b49df3 2006-07-18 devnull 
523 28b49df3 2006-07-18 devnull 	buck = score2bucket(p->isect, ie);
524 28b49df3 2006-07-18 devnull 	x = (buck-p->buck0) / p->mbufbuckets;
525 28b49df3 2006-07-18 devnull 	if(x >= p->nmbuf){
526 28b49df3 2006-07-18 devnull 		fprint(2, "buck=%ud mbufbucket=%ud x=%ud\n",
527 28b49df3 2006-07-18 devnull 			buck, p->mbufbuckets, x);
528 28b49df3 2006-07-18 devnull 	}
529 28b49df3 2006-07-18 devnull 	assert(x < p->nmbuf);
530 28b49df3 2006-07-18 devnull 
531 28b49df3 2006-07-18 devnull 	l = p->free;
532 28b49df3 2006-07-18 devnull 	p->free = l->next;
533 28b49df3 2006-07-18 devnull 	p->nfree--;
534 28b49df3 2006-07-18 devnull 	memmove(l->ie, ie, IEntrySize);
535 28b49df3 2006-07-18 devnull 	l->next = p->mlist[x];
536 28b49df3 2006-07-18 devnull 	p->mlist[x] = l;
537 28b49df3 2006-07-18 devnull 	p->mcount[x]++;
538 28b49df3 2006-07-18 devnull }	
539 28b49df3 2006-07-18 devnull 
540 28b49df3 2006-07-18 devnull /*
541 28b49df3 2006-07-18 devnull  * Pull out a block containing as many
542 28b49df3 2006-07-18 devnull  * entries as possible for minibuffer x.
543 28b49df3 2006-07-18 devnull  */
544 28b49df3 2006-07-18 devnull static u32int
545 28b49df3 2006-07-18 devnull ipoolgetbuf(IPool *p, u32int x)
546 28b49df3 2006-07-18 devnull {
547 28b49df3 2006-07-18 devnull 	uchar *bp, *ep, *wp;
548 28b49df3 2006-07-18 devnull 	IEntryLink *l;
549 28b49df3 2006-07-18 devnull 	u32int n;
550 28b49df3 2006-07-18 devnull 	
551 28b49df3 2006-07-18 devnull 	bp = p->wbuf;
552 28b49df3 2006-07-18 devnull 	ep = p->wbuf + p->bufsize;
553 28b49df3 2006-07-18 devnull 	n = 0;
554 28b49df3 2006-07-18 devnull 	assert(x < p->nmbuf);
555 28b49df3 2006-07-18 devnull 	for(wp=bp; wp+IEntrySize<=ep && p->mlist[x]; wp+=IEntrySize){
556 28b49df3 2006-07-18 devnull 		l = p->mlist[x];
557 28b49df3 2006-07-18 devnull 		p->mlist[x] = l->next;
558 28b49df3 2006-07-18 devnull 		p->mcount[x]--;
559 28b49df3 2006-07-18 devnull 		memmove(wp, l->ie, IEntrySize);
560 28b49df3 2006-07-18 devnull 		l->next = p->free;
561 28b49df3 2006-07-18 devnull 		p->free = l;
562 28b49df3 2006-07-18 devnull 		p->nfree++;
563 28b49df3 2006-07-18 devnull 		n++;
564 28b49df3 2006-07-18 devnull 	}
565 28b49df3 2006-07-18 devnull 	memset(wp, 0, ep-wp);
566 28b49df3 2006-07-18 devnull 	return n;
567 28b49df3 2006-07-18 devnull }
568 28b49df3 2006-07-18 devnull 
569 28b49df3 2006-07-18 devnull /*
570 28b49df3 2006-07-18 devnull  * Read a block worth of entries from the minibuf
571 28b49df3 2006-07-18 devnull  * into the pool.  Caller must know there is room.
572 28b49df3 2006-07-18 devnull  */
573 28b49df3 2006-07-18 devnull static void
574 28b49df3 2006-07-18 devnull ipoolloadblock(IPool *p, Minibuf *mb)
575 28b49df3 2006-07-18 devnull {
576 28b49df3 2006-07-18 devnull 	u32int i, n;
577 28b49df3 2006-07-18 devnull 	
578 28b49df3 2006-07-18 devnull 	assert(mb->nentry > 0);
579 28b49df3 2006-07-18 devnull 	assert(mb->roffset >= mb->woffset);
580 28b49df3 2006-07-18 devnull 	assert(mb->roffset < mb->eoffset);
581 28b49df3 2006-07-18 devnull 
582 28b49df3 2006-07-18 devnull 	n = p->bufsize/IEntrySize;
583 28b49df3 2006-07-18 devnull 	if(n > mb->nentry)
584 28b49df3 2006-07-18 devnull 		n = mb->nentry;
585 28b49df3 2006-07-18 devnull 	if(readpart(p->isect->part, mb->roffset, p->rbuf, p->bufsize) < 0)
586 28b49df3 2006-07-18 devnull 		fprint(2, "readpart %s: %r\n", p->isect->part->name);
587 28b49df3 2006-07-18 devnull 	else{
588 28b49df3 2006-07-18 devnull 		for(i=0; i<n; i++)
589 28b49df3 2006-07-18 devnull 			ipoolinsert(p, p->rbuf+i*IEntrySize);
590 28b49df3 2006-07-18 devnull 	}
591 28b49df3 2006-07-18 devnull 	mb->nentry -= n;
592 28b49df3 2006-07-18 devnull 	mb->roffset += p->bufsize;
593 28b49df3 2006-07-18 devnull }
594 28b49df3 2006-07-18 devnull 
595 28b49df3 2006-07-18 devnull /*
596 28b49df3 2006-07-18 devnull  * Write out a block worth of entries to minibuffer x.
597 28b49df3 2006-07-18 devnull  * If necessary, pick up the data there before overwriting it.
598 28b49df3 2006-07-18 devnull  */
599 28b49df3 2006-07-18 devnull static void
600 28b49df3 2006-07-18 devnull ipoolflush0(IPool *pool, u32int x)
601 28b49df3 2006-07-18 devnull {
602 28b49df3 2006-07-18 devnull 	u32int bufsize;
603 28b49df3 2006-07-18 devnull 	Minibuf *mb;
604 28b49df3 2006-07-18 devnull 	
605 28b49df3 2006-07-18 devnull 	mb = pool->mbuf+x;
606 28b49df3 2006-07-18 devnull 	bufsize = pool->bufsize;
607 28b49df3 2006-07-18 devnull 	mb->nwentry += ipoolgetbuf(pool, x);
608 28b49df3 2006-07-18 devnull 	if(mb->nentry > 0 && mb->roffset == mb->woffset){
609 28b49df3 2006-07-18 devnull 		assert(pool->nfree >= pool->bufsize/IEntrySize);
610 28b49df3 2006-07-18 devnull 		/*
611 28b49df3 2006-07-18 devnull 		 * There will be room in the pool -- we just 
612 28b49df3 2006-07-18 devnull 		 * removed a block worth.
613 28b49df3 2006-07-18 devnull 		 */
614 28b49df3 2006-07-18 devnull 		ipoolloadblock(pool, mb);
615 28b49df3 2006-07-18 devnull 	}
616 28b49df3 2006-07-18 devnull 	if(writepart(pool->isect->part, mb->woffset, pool->wbuf, bufsize) < 0)
617 28b49df3 2006-07-18 devnull 		fprint(2, "writepart %s: %r\n", pool->isect->part->name);
618 28b49df3 2006-07-18 devnull 	mb->woffset += bufsize;
619 28b49df3 2006-07-18 devnull }
620 28b49df3 2006-07-18 devnull 
621 28b49df3 2006-07-18 devnull /*
622 28b49df3 2006-07-18 devnull  * Write out some full block of entries.
623 28b49df3 2006-07-18 devnull  * (There must be one -- the pool is almost full!)
624 28b49df3 2006-07-18 devnull  */
625 28b49df3 2006-07-18 devnull static void
626 28b49df3 2006-07-18 devnull ipoolflush1(IPool *pool)
627 28b49df3 2006-07-18 devnull {
628 28b49df3 2006-07-18 devnull 	u32int i;
629 28b49df3 2006-07-18 devnull 
630 28b49df3 2006-07-18 devnull 	assert(pool->nfree <= pool->epbuf);
631 28b49df3 2006-07-18 devnull 
632 28b49df3 2006-07-18 devnull 	for(i=0; i<pool->nmbuf; i++){
633 28b49df3 2006-07-18 devnull 		if(pool->mcount[i] >= pool->epbuf){
634 28b49df3 2006-07-18 devnull 			ipoolflush0(pool, i);
635 28b49df3 2006-07-18 devnull 			return;
636 28b49df3 2006-07-18 devnull 		}
637 28b49df3 2006-07-18 devnull 	}
638 28b49df3 2006-07-18 devnull 	/* can't be reached - someone must be full */
639 28b49df3 2006-07-18 devnull 	sysfatal("ipoolflush1");
640 28b49df3 2006-07-18 devnull }
641 28b49df3 2006-07-18 devnull 
642 28b49df3 2006-07-18 devnull /*
643 28b49df3 2006-07-18 devnull  * Flush all the entries in the pool out to disk.
644 28b49df3 2006-07-18 devnull  * Nothing more to read from disk.
645 28b49df3 2006-07-18 devnull  */
646 28b49df3 2006-07-18 devnull static void
647 28b49df3 2006-07-18 devnull ipoolflush(IPool *pool)
648 28b49df3 2006-07-18 devnull {
649 28b49df3 2006-07-18 devnull 	u32int i;
650 28b49df3 2006-07-18 devnull 	
651 28b49df3 2006-07-18 devnull 	for(i=0; i<pool->nmbuf; i++)
652 28b49df3 2006-07-18 devnull 		while(pool->mlist[i])
653 28b49df3 2006-07-18 devnull 			ipoolflush0(pool, i);
654 28b49df3 2006-07-18 devnull 	assert(pool->nfree == pool->nentry);
655 28b49df3 2006-07-18 devnull }
656 28b49df3 2006-07-18 devnull 
657 28b49df3 2006-07-18 devnull /*
658 28b49df3 2006-07-18 devnull  * Third pass.  Pick up each minibuffer from disk into
659 28b49df3 2006-07-18 devnull  * memory and then write out the buckets.
660 28b49df3 2006-07-18 devnull  */
661 28b49df3 2006-07-18 devnull 
662 28b49df3 2006-07-18 devnull /*
663 28b49df3 2006-07-18 devnull  * Compare two packed index entries.  
664 28b49df3 2006-07-18 devnull  * Usual ordering except break ties by putting higher
665 28b49df3 2006-07-18 devnull  * index addresses first (assumes have duplicates
666 28b49df3 2006-07-18 devnull  * due to corruption in the lower addresses).
667 28b49df3 2006-07-18 devnull  */
668 28b49df3 2006-07-18 devnull static int
669 28b49df3 2006-07-18 devnull ientrycmpaddr(const void *va, const void *vb)
670 28b49df3 2006-07-18 devnull {
671 28b49df3 2006-07-18 devnull 	int i;
672 28b49df3 2006-07-18 devnull 	uchar *a, *b;
673 28b49df3 2006-07-18 devnull 	
674 28b49df3 2006-07-18 devnull 	a = (uchar*)va;
675 28b49df3 2006-07-18 devnull 	b = (uchar*)vb;
676 28b49df3 2006-07-18 devnull 	i = ientrycmp(a, b);
677 28b49df3 2006-07-18 devnull 	if(i)
678 28b49df3 2006-07-18 devnull 		return i;
679 28b49df3 2006-07-18 devnull 	return -memcmp(a+IEntryAddrOff, b+IEntryAddrOff, 8);
680 28b49df3 2006-07-18 devnull }
681 28b49df3 2006-07-18 devnull 
682 28b49df3 2006-07-18 devnull static void
683 28b49df3 2006-07-18 devnull zerorange(Part *p, u64int o, u64int e)
684 28b49df3 2006-07-18 devnull {
685 28b49df3 2006-07-18 devnull 	static uchar zero[MaxIoSize];
686 28b49df3 2006-07-18 devnull 	u32int n;
687 28b49df3 2006-07-18 devnull 	
688 28b49df3 2006-07-18 devnull 	for(; o<e; o+=n){
689 28b49df3 2006-07-18 devnull 		n = sizeof zero;
690 28b49df3 2006-07-18 devnull 		if(o+n > e)
691 28b49df3 2006-07-18 devnull 			n = e-o;
692 28b49df3 2006-07-18 devnull 		if(writepart(p, o, zero, n) < 0)
693 28b49df3 2006-07-18 devnull 			fprint(2, "writepart %s: %r\n", p->name);
694 28b49df3 2006-07-18 devnull 	}
695 28b49df3 2006-07-18 devnull }
696 28b49df3 2006-07-18 devnull 
697 28b49df3 2006-07-18 devnull /*
698 28b49df3 2006-07-18 devnull  * Load a minibuffer into memory and write out the 
699 28b49df3 2006-07-18 devnull  * corresponding buckets.
700 28b49df3 2006-07-18 devnull  */
701 28b49df3 2006-07-18 devnull static void
702 28b49df3 2006-07-18 devnull sortminibuffer(ISect *is, Minibuf *mb, uchar *buf, u32int nbuf, u32int bufsize)
703 28b49df3 2006-07-18 devnull {
704 28b49df3 2006-07-18 devnull 	uchar *buckdata, *p, *q, *ep;
705 28b49df3 2006-07-18 devnull 	u32int b, lastb, memsize, n;
706 28b49df3 2006-07-18 devnull 	u64int o;
707 28b49df3 2006-07-18 devnull 	IBucket ib;
708 28b49df3 2006-07-18 devnull 	Part *part;
709 28b49df3 2006-07-18 devnull 	
710 28b49df3 2006-07-18 devnull 	part = is->part;
711 28b49df3 2006-07-18 devnull 	buckdata = emalloc(is->blocksize);
712 28b49df3 2006-07-18 devnull 	
713 28b49df3 2006-07-18 devnull 	if(mb->nwentry == 0)
714 28b49df3 2006-07-18 devnull 		return;
715 28b49df3 2006-07-18 devnull 
716 28b49df3 2006-07-18 devnull 	/*
717 28b49df3 2006-07-18 devnull 	 * read entire buffer.
718 28b49df3 2006-07-18 devnull 	 */
719 28b49df3 2006-07-18 devnull 	assert(mb->nwentry*IEntrySize <= mb->woffset-mb->boffset);
720 28b49df3 2006-07-18 devnull 	assert(mb->woffset-mb->boffset <= nbuf);
721 28b49df3 2006-07-18 devnull 	if(readpart(part, mb->boffset, buf, mb->woffset-mb->boffset) < 0){
722 28b49df3 2006-07-18 devnull 		fprint(2, "readpart %s: %r\n", part->name);
723 28b49df3 2006-07-18 devnull 		errors = 1;
724 28b49df3 2006-07-18 devnull 		return;
725 28b49df3 2006-07-18 devnull 	}
726 28b49df3 2006-07-18 devnull 	assert(*(uint*)buf != 0xa5a5a5a5);
727 28b49df3 2006-07-18 devnull 	
728 28b49df3 2006-07-18 devnull 	/*
729 28b49df3 2006-07-18 devnull 	 * remove fragmentation due to IEntrySize
730 28b49df3 2006-07-18 devnull 	 * not evenly dividing Bufsize
731 28b49df3 2006-07-18 devnull 	 */
732 28b49df3 2006-07-18 devnull 	memsize = (bufsize/IEntrySize)*IEntrySize;
733 28b49df3 2006-07-18 devnull 	for(o=mb->boffset, p=q=buf; o<mb->woffset; o+=bufsize){
734 28b49df3 2006-07-18 devnull 		memmove(p, q, memsize);
735 28b49df3 2006-07-18 devnull 		p += memsize;
736 28b49df3 2006-07-18 devnull 		q += bufsize;
737 28b49df3 2006-07-18 devnull 	}
738 28b49df3 2006-07-18 devnull 	ep = buf + mb->nwentry*IEntrySize;
739 28b49df3 2006-07-18 devnull 	assert(ep <= buf+nbuf);
740 28b49df3 2006-07-18 devnull 
741 28b49df3 2006-07-18 devnull 	/* 
742 28b49df3 2006-07-18 devnull 	 * sort entries
743 28b49df3 2006-07-18 devnull 	 */
744 28b49df3 2006-07-18 devnull 	qsort(buf, mb->nwentry, IEntrySize, ientrycmpaddr);
745 28b49df3 2006-07-18 devnull 
746 28b49df3 2006-07-18 devnull 	/*
747 28b49df3 2006-07-18 devnull 	 * write buckets out
748 28b49df3 2006-07-18 devnull 	 */
749 28b49df3 2006-07-18 devnull 	n = 0;
750 28b49df3 2006-07-18 devnull 	lastb = offset2bucket(is, mb->boffset);
751 28b49df3 2006-07-18 devnull 	for(p=buf; p<ep; p=q){
752 28b49df3 2006-07-18 devnull 		b = score2bucket(is, p);
753 28b49df3 2006-07-18 devnull 		for(q=p; q<ep && score2bucket(is, q)==b; q+=IEntrySize)
754 28b49df3 2006-07-18 devnull 			;
755 28b49df3 2006-07-18 devnull 		if(lastb+1 < b && zero)
756 28b49df3 2006-07-18 devnull 			zerorange(part, bucket2offset(is, lastb+1), bucket2offset(is, b));
757 28b49df3 2006-07-18 devnull 		if(IBucketSize+(q-p) > is->blocksize)
758 28b49df3 2006-07-18 devnull 			sysfatal("bucket overflow - make index bigger");
759 28b49df3 2006-07-18 devnull 		memmove(buckdata+IBucketSize, p, q-p);
760 28b49df3 2006-07-18 devnull 		ib.n = (q-p)/IEntrySize;
761 28b49df3 2006-07-18 devnull 		n += ib.n;
762 28b49df3 2006-07-18 devnull 		packibucket(&ib, buckdata, is->bucketmagic);
763 28b49df3 2006-07-18 devnull 		if(writepart(part, bucket2offset(is, b), buckdata, is->blocksize) < 0)
764 28b49df3 2006-07-18 devnull 			fprint(2, "write %s: %r\n", part->name);
765 28b49df3 2006-07-18 devnull 		lastb = b;
766 28b49df3 2006-07-18 devnull 	}
767 28b49df3 2006-07-18 devnull 	if(lastb+1 < is->stop-is->start && zero)
768 28b49df3 2006-07-18 devnull 		zerorange(part, bucket2offset(is, lastb+1), bucket2offset(is, is->stop - is->start));
769 28b49df3 2006-07-18 devnull 
770 28b49df3 2006-07-18 devnull 	if(n != mb->nwentry)
771 28b49df3 2006-07-18 devnull 		fprint(2, "sortminibuffer bug: n=%ud nwentry=%ud have=%ld\n", n, mb->nwentry, (ep-buf)/IEntrySize);
772 28b49df3 2006-07-18 devnull 
773 28b49df3 2006-07-18 devnull 	free(buckdata);
774 28b49df3 2006-07-18 devnull }
775 28b49df3 2006-07-18 devnull 
776 28b49df3 2006-07-18 devnull static void
777 28b49df3 2006-07-18 devnull isectproc(void *v)
778 28b49df3 2006-07-18 devnull {
779 28b49df3 2006-07-18 devnull 	u32int buck, bufbuckets, bufsize, epbuf, i, j;
780 28b49df3 2006-07-18 devnull 	u32int mbufbuckets, n, nbucket, nn, space;
781 28b49df3 2006-07-18 devnull 	u32int nbuf, nminibuf, xminiclump, prod;
782 28b49df3 2006-07-18 devnull 	u64int blocksize, offset, xclump;
783 28b49df3 2006-07-18 devnull 	uchar *data, *p;
784 28b49df3 2006-07-18 devnull 	Buf *buf;
785 28b49df3 2006-07-18 devnull 	IEntry ie;
786 ac5a97e6 2008-07-04 rsc 	IEntryBuf ieb;
787 28b49df3 2006-07-18 devnull 	IPool *ipool;
788 28b49df3 2006-07-18 devnull 	ISect *is;
789 28b49df3 2006-07-18 devnull 	Minibuf *mbuf, *mb;
790 28b49df3 2006-07-18 devnull 	
791 28b49df3 2006-07-18 devnull 	is = v;
792 28b49df3 2006-07-18 devnull 	blocksize = is->blocksize;
793 28b49df3 2006-07-18 devnull 	nbucket = is->stop - is->start;
794 28b49df3 2006-07-18 devnull 
795 28b49df3 2006-07-18 devnull 	/*
796 28b49df3 2006-07-18 devnull 	 * Three passes:
797 28b49df3 2006-07-18 devnull 	 *	pass 1 - write index entries from arenas into 
798 28b49df3 2006-07-18 devnull 	 *		large sequential sections on index disk.
799 28b49df3 2006-07-18 devnull 	 *		requires nbuf * bufsize memory.
800 28b49df3 2006-07-18 devnull 	 *
801 28b49df3 2006-07-18 devnull 	 *	pass 2 - split each section into minibufs.
802 28b49df3 2006-07-18 devnull 	 *		requires nminibuf * bufsize memory.
803 28b49df3 2006-07-18 devnull 	 *
804 28b49df3 2006-07-18 devnull 	 *	pass 3 - read each minibuf into memory and
805 28b49df3 2006-07-18 devnull 	 *		write buckets out. 
806 28b49df3 2006-07-18 devnull 	 *		requires entries/minibuf * IEntrySize memory.
807 28b49df3 2006-07-18 devnull 	 * 
808 28b49df3 2006-07-18 devnull 	 * The larger we set bufsize the less seeking hurts us.
809 28b49df3 2006-07-18 devnull 	 * 
810 28b49df3 2006-07-18 devnull 	 * The fewer sections and minibufs we have, the less
811 28b49df3 2006-07-18 devnull 	 * seeking hurts us.
812 28b49df3 2006-07-18 devnull 	 * 
813 28b49df3 2006-07-18 devnull 	 * The fewer sections and minibufs we have, the 
814 28b49df3 2006-07-18 devnull 	 * more entries we end up with in each minibuf
815 28b49df3 2006-07-18 devnull 	 * at the end.  
816 28b49df3 2006-07-18 devnull 	 *
817 28b49df3 2006-07-18 devnull 	 * Shoot for using half our memory to hold each
818 28b49df3 2006-07-18 devnull 	 * minibuf.  The chance of a random distribution 
819 28b49df3 2006-07-18 devnull 	 * getting off by 2x is quite low.  
820 28b49df3 2006-07-18 devnull 	 *
821 28b49df3 2006-07-18 devnull 	 * Once that is decided, figure out the smallest 
822 28b49df3 2006-07-18 devnull 	 * nminibuf and nsection/biggest bufsize we can use
823 28b49df3 2006-07-18 devnull 	 * and still fit in the memory constraints.
824 28b49df3 2006-07-18 devnull 	 */
825 28b49df3 2006-07-18 devnull 	
826 28b49df3 2006-07-18 devnull 	/* expected number of clump index entries we'll see */
827 28b49df3 2006-07-18 devnull 	xclump = nbucket * (double)totalclumps/totalbuckets;
828 28b49df3 2006-07-18 devnull 	
829 28b49df3 2006-07-18 devnull 	/* number of clumps we want to see in a minibuf */
830 28b49df3 2006-07-18 devnull 	xminiclump = isectmem/2/IEntrySize;
831 28b49df3 2006-07-18 devnull 	
832 28b49df3 2006-07-18 devnull 	/* total number of minibufs we need */
833 1d53bf4a 2007-05-03 devnull 	prod = (xclump+xminiclump-1) / xminiclump;
834 28b49df3 2006-07-18 devnull 	
835 28b49df3 2006-07-18 devnull 	/* if possible, skip second pass */
836 28b49df3 2006-07-18 devnull 	if(!dumb && prod*MinBufSize < isectmem){
837 28b49df3 2006-07-18 devnull 		nbuf = prod;
838 28b49df3 2006-07-18 devnull 		nminibuf = 1;
839 28b49df3 2006-07-18 devnull 	}else{
840 28b49df3 2006-07-18 devnull 		/* otherwise use nsection = sqrt(nmini) */
841 28b49df3 2006-07-18 devnull 		for(nbuf=1; nbuf*nbuf<prod; nbuf++)
842 28b49df3 2006-07-18 devnull 			;
843 28b49df3 2006-07-18 devnull 		if(nbuf*MinBufSize > isectmem)
844 28b49df3 2006-07-18 devnull 			sysfatal("not enough memory");
845 28b49df3 2006-07-18 devnull 		nminibuf = nbuf;
846 28b49df3 2006-07-18 devnull 	}
847 28b49df3 2006-07-18 devnull 	/* size buffer to use extra memory */
848 28b49df3 2006-07-18 devnull 	bufsize = MinBufSize;
849 28b49df3 2006-07-18 devnull 	while(bufsize*2*nbuf <= isectmem && bufsize < MaxBufSize)
850 28b49df3 2006-07-18 devnull 		bufsize *= 2;
851 28b49df3 2006-07-18 devnull 	data = emalloc(nbuf*bufsize);
852 28b49df3 2006-07-18 devnull 	epbuf = bufsize/IEntrySize;
853 28b49df3 2006-07-18 devnull 	fprint(2, "%T %s: %,ud buckets, %,ud groups, %,ud minigroups, %,ud buffer\n",
854 28b49df3 2006-07-18 devnull 		is->part->name, nbucket, nbuf, nminibuf, bufsize);
855 28b49df3 2006-07-18 devnull 	/*
856 28b49df3 2006-07-18 devnull 	 * Accept index entries from arena procs.
857 28b49df3 2006-07-18 devnull 	 */
858 28b49df3 2006-07-18 devnull 	buf = MKNZ(Buf, nbuf);
859 28b49df3 2006-07-18 devnull 	p = data;
860 28b49df3 2006-07-18 devnull 	offset = is->blockbase;
861 28b49df3 2006-07-18 devnull 	bufbuckets = (nbucket+nbuf-1)/nbuf;
862 28b49df3 2006-07-18 devnull 	for(i=0; i<nbuf; i++){
863 28b49df3 2006-07-18 devnull 		buf[i].part = is->part;
864 28b49df3 2006-07-18 devnull 		buf[i].bp = p;
865 28b49df3 2006-07-18 devnull 		buf[i].wp = p;
866 28b49df3 2006-07-18 devnull 		p += bufsize;
867 28b49df3 2006-07-18 devnull 		buf[i].ep = p;
868 28b49df3 2006-07-18 devnull 		buf[i].boffset = offset;
869 28b49df3 2006-07-18 devnull 		buf[i].woffset = offset;
870 28b49df3 2006-07-18 devnull 		if(i < nbuf-1){
871 28b49df3 2006-07-18 devnull 			offset += bufbuckets*blocksize;
872 28b49df3 2006-07-18 devnull 			buf[i].eoffset = offset;
873 28b49df3 2006-07-18 devnull 		}else{
874 28b49df3 2006-07-18 devnull 			offset = is->blockbase + nbucket*blocksize;
875 28b49df3 2006-07-18 devnull 			buf[i].eoffset = offset;
876 28b49df3 2006-07-18 devnull 		}
877 28b49df3 2006-07-18 devnull 	}
878 28b49df3 2006-07-18 devnull 	assert(p == data+nbuf*bufsize);
879 28b49df3 2006-07-18 devnull 
880 28b49df3 2006-07-18 devnull 	n = 0;
881 ac5a97e6 2008-07-04 rsc 	while(recv(is->writechan, &ieb) == 1){
882 ac5a97e6 2008-07-04 rsc 		if(ieb.nie == 0)
883 28b49df3 2006-07-18 devnull 			break;
884 ac5a97e6 2008-07-04 rsc 		for(j=0; j<ieb.nie; j++){
885 ac5a97e6 2008-07-04 rsc 			ie = ieb.ie[j];
886 ac5a97e6 2008-07-04 rsc 			buck = score2bucket(is, ie.score);
887 ac5a97e6 2008-07-04 rsc 			i = buck/bufbuckets;
888 ac5a97e6 2008-07-04 rsc 			assert(i < nbuf);
889 ac5a97e6 2008-07-04 rsc 			bwrite(&buf[i], &ie);
890 ac5a97e6 2008-07-04 rsc 			n++;
891 ac5a97e6 2008-07-04 rsc 		}
892 28b49df3 2006-07-18 devnull 	}
893 28b49df3 2006-07-18 devnull 	add(&indexentries, n);
894 28b49df3 2006-07-18 devnull 	
895 28b49df3 2006-07-18 devnull 	nn = 0;
896 28b49df3 2006-07-18 devnull 	for(i=0; i<nbuf; i++){
897 28b49df3 2006-07-18 devnull 		bflush(&buf[i]);
898 28b49df3 2006-07-18 devnull 		buf[i].bp = nil;
899 28b49df3 2006-07-18 devnull 		buf[i].ep = nil;
900 28b49df3 2006-07-18 devnull 		buf[i].wp = nil;
901 28b49df3 2006-07-18 devnull 		nn += buf[i].nentry;
902 28b49df3 2006-07-18 devnull 	}
903 28b49df3 2006-07-18 devnull 	if(n != nn)
904 28b49df3 2006-07-18 devnull 		fprint(2, "isectproc bug: n=%ud nn=%ud\n", n, nn);
905 28b49df3 2006-07-18 devnull 		
906 28b49df3 2006-07-18 devnull 	free(data);
907 28b49df3 2006-07-18 devnull 
908 28b49df3 2006-07-18 devnull 	fprint(2, "%T %s: reordering\n", is->part->name);
909 28b49df3 2006-07-18 devnull 	
910 28b49df3 2006-07-18 devnull 	/*
911 28b49df3 2006-07-18 devnull 	 * Rearrange entries into minibuffers and then
912 28b49df3 2006-07-18 devnull 	 * split each minibuffer into buckets.
913 1d53bf4a 2007-05-03 devnull 	 * The minibuffer must be sized so that it is 
914 1d53bf4a 2007-05-03 devnull 	 * a multiple of blocksize -- ipoolloadblock assumes
915 1d53bf4a 2007-05-03 devnull 	 * that each minibuf starts aligned on a blocksize
916 1d53bf4a 2007-05-03 devnull 	 * boundary.
917 28b49df3 2006-07-18 devnull 	 */
918 28b49df3 2006-07-18 devnull 	mbuf = MKN(Minibuf, nminibuf);
919 28b49df3 2006-07-18 devnull 	mbufbuckets = (bufbuckets+nminibuf-1)/nminibuf;
920 1d53bf4a 2007-05-03 devnull 	while(mbufbuckets*blocksize % bufsize)
921 1d53bf4a 2007-05-03 devnull 		mbufbuckets++;
922 28b49df3 2006-07-18 devnull 	for(i=0; i<nbuf; i++){
923 28b49df3 2006-07-18 devnull 		/*
924 28b49df3 2006-07-18 devnull 		 * Set up descriptors.
925 28b49df3 2006-07-18 devnull 		 */
926 28b49df3 2006-07-18 devnull 		n = buf[i].nentry;
927 28b49df3 2006-07-18 devnull 		nn = 0;
928 28b49df3 2006-07-18 devnull 		offset = buf[i].boffset;
929 28b49df3 2006-07-18 devnull 		memset(mbuf, 0, nminibuf*sizeof(mbuf[0]));
930 28b49df3 2006-07-18 devnull 		for(j=0; j<nminibuf; j++){
931 28b49df3 2006-07-18 devnull 			mb = &mbuf[j];
932 28b49df3 2006-07-18 devnull 			mb->boffset = offset;
933 1d53bf4a 2007-05-03 devnull 			offset += mbufbuckets*blocksize;
934 1d53bf4a 2007-05-03 devnull 			if(offset > buf[i].eoffset)
935 1d53bf4a 2007-05-03 devnull 				offset = buf[i].eoffset;
936 1d53bf4a 2007-05-03 devnull 			mb->eoffset = offset;
937 28b49df3 2006-07-18 devnull 			mb->roffset = mb->boffset;
938 28b49df3 2006-07-18 devnull 			mb->woffset = mb->boffset;
939 28b49df3 2006-07-18 devnull 			mb->nentry = epbuf * (mb->eoffset - mb->boffset)/bufsize;
940 28b49df3 2006-07-18 devnull 			if(mb->nentry > buf[i].nentry)
941 28b49df3 2006-07-18 devnull 				mb->nentry = buf[i].nentry;
942 28b49df3 2006-07-18 devnull 			buf[i].nentry -= mb->nentry;
943 28b49df3 2006-07-18 devnull 			nn += mb->nentry;
944 28b49df3 2006-07-18 devnull 		}
945 28b49df3 2006-07-18 devnull 		if(n != nn)
946 28b49df3 2006-07-18 devnull 			fprint(2, "isectproc bug2: n=%ud nn=%ud (i=%d)\n", n, nn, i);;
947 28b49df3 2006-07-18 devnull 		/*
948 28b49df3 2006-07-18 devnull 		 * Rearrange.
949 28b49df3 2006-07-18 devnull 		 */
950 28b49df3 2006-07-18 devnull 		if(!dumb && nminibuf == 1){
951 28b49df3 2006-07-18 devnull 			mbuf[0].nwentry = mbuf[0].nentry;
952 28b49df3 2006-07-18 devnull 			mbuf[0].woffset = buf[i].woffset;
953 28b49df3 2006-07-18 devnull 		}else{
954 28b49df3 2006-07-18 devnull 			ipool = mkipool(is, mbuf, nminibuf, mbufbuckets, bufsize);
955 28b49df3 2006-07-18 devnull 			ipool->buck0 = bufbuckets*i;
956 28b49df3 2006-07-18 devnull 			for(j=0; j<nminibuf; j++){
957 28b49df3 2006-07-18 devnull 				mb = &mbuf[j];
958 28b49df3 2006-07-18 devnull 				while(mb->nentry > 0){
959 28b49df3 2006-07-18 devnull 					if(ipool->nfree < epbuf){
960 28b49df3 2006-07-18 devnull 						ipoolflush1(ipool);
961 28b49df3 2006-07-18 devnull 						/* ipoolflush1 might change mb->nentry */	
962 28b49df3 2006-07-18 devnull 						continue;
963 28b49df3 2006-07-18 devnull 					}
964 28b49df3 2006-07-18 devnull 					assert(ipool->nfree >= epbuf);
965 28b49df3 2006-07-18 devnull 					ipoolloadblock(ipool, mb);
966 28b49df3 2006-07-18 devnull 				}
967 28b49df3 2006-07-18 devnull 			}
968 28b49df3 2006-07-18 devnull 			ipoolflush(ipool);
969 28b49df3 2006-07-18 devnull 			nn = 0;
970 28b49df3 2006-07-18 devnull 			for(j=0; j<nminibuf; j++)
971 28b49df3 2006-07-18 devnull 				nn += mbuf[j].nwentry;
972 28b49df3 2006-07-18 devnull 			if(n != nn)
973 28b49df3 2006-07-18 devnull 				fprint(2, "isectproc bug3: n=%ud nn=%ud (i=%d)\n", n, nn, i);
974 28b49df3 2006-07-18 devnull 			free(ipool);
975 28b49df3 2006-07-18 devnull 		}
976 28b49df3 2006-07-18 devnull 
977 28b49df3 2006-07-18 devnull 		/*
978 28b49df3 2006-07-18 devnull 		 * Make buckets.
979 28b49df3 2006-07-18 devnull 		 */
980 28b49df3 2006-07-18 devnull 		space = 0;
981 28b49df3 2006-07-18 devnull 		for(j=0; j<nminibuf; j++)
982 28b49df3 2006-07-18 devnull 			if(space < mbuf[j].woffset - mbuf[j].boffset)
983 28b49df3 2006-07-18 devnull 				space = mbuf[j].woffset - mbuf[j].boffset;
984 28b49df3 2006-07-18 devnull 
985 28b49df3 2006-07-18 devnull 		data = emalloc(space);
986 28b49df3 2006-07-18 devnull 		for(j=0; j<nminibuf; j++){
987 28b49df3 2006-07-18 devnull 			mb = &mbuf[j];
988 28b49df3 2006-07-18 devnull 			sortminibuffer(is, mb, data, space, bufsize);
989 28b49df3 2006-07-18 devnull 		}
990 28b49df3 2006-07-18 devnull 		free(data);
991 28b49df3 2006-07-18 devnull 	}
992 28b49df3 2006-07-18 devnull 		
993 28b49df3 2006-07-18 devnull 	sendp(isectdonechan, is);
994 28b49df3 2006-07-18 devnull }
995 28b49df3 2006-07-18 devnull 
996 28b49df3 2006-07-18 devnull 
997 28b49df3 2006-07-18 devnull