1 a0d146ed 2005-07-12 devnull #include "stdinc.h"
2 a0d146ed 2005-07-12 devnull #include "dat.h"
3 a0d146ed 2005-07-12 devnull #include "fns.h"
4 a0d146ed 2005-07-12 devnull #include <bio.h>
6 a0d146ed 2005-07-12 devnull typedef struct IEBuck IEBuck;
7 a0d146ed 2005-07-12 devnull typedef struct IEBucks IEBucks;
11 a0d146ed 2005-07-12 devnull ClumpChunks = 32*1024
14 a0d146ed 2005-07-12 devnull struct IEBuck
16 a0d146ed 2005-07-12 devnull u32int head; /* head of chain of chunks on the disk */
17 a0d146ed 2005-07-12 devnull u32int used; /* usage of the last chunk */
18 a0d146ed 2005-07-12 devnull u64int total; /* total number of bytes in this bucket */
19 a0d146ed 2005-07-12 devnull u8int *buf; /* chunk of entries for this bucket */
22 a0d146ed 2005-07-12 devnull struct IEBucks
24 a0d146ed 2005-07-12 devnull Part *part;
25 a0d146ed 2005-07-12 devnull u64int off; /* offset for writing data in the partition */
26 a0d146ed 2005-07-12 devnull u32int chunks; /* total chunks written to fd */
27 a0d146ed 2005-07-12 devnull u64int max; /* max bytes entered in any one bucket */
28 a0d146ed 2005-07-12 devnull int bits; /* number of bits in initial bucket sort */
29 a0d146ed 2005-07-12 devnull int nbucks; /* 1 << bits, the number of buckets */
30 a0d146ed 2005-07-12 devnull u32int size; /* bytes in each of the buckets chunks */
31 a0d146ed 2005-07-12 devnull u32int usable; /* amount usable for IEntry data */
32 a0d146ed 2005-07-12 devnull u8int *buf; /* buffer for all chunks */
33 a0d146ed 2005-07-12 devnull u8int *xbuf;
34 a0d146ed 2005-07-12 devnull IEBuck *bucks;
37 a0d146ed 2005-07-12 devnull #define U32GET(p) (((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
38 a0d146ed 2005-07-12 devnull #define U32PUT(p,v) (p)[0]=(v)>>24;(p)[1]=(v)>>16;(p)[2]=(v)>>8;(p)[3]=(v)
40 a0d146ed 2005-07-12 devnull static IEBucks *initiebucks(Part *part, int bits, u32int size);
41 a0d146ed 2005-07-12 devnull static int flushiebuck(IEBucks *ib, int b, int reset);
42 a0d146ed 2005-07-12 devnull static int flushiebucks(IEBucks *ib);
43 a0d146ed 2005-07-12 devnull static u32int sortiebuck(IEBucks *ib, int b);
44 a0d146ed 2005-07-12 devnull static u64int sortiebucks(IEBucks *ib);
45 a0d146ed 2005-07-12 devnull static int sprayientry(IEBucks *ib, IEntry *ie);
46 a0d146ed 2005-07-12 devnull static u32int readarenainfo(IEBucks *ib, Arena *arena, u64int a, Bloom *b);
47 a0d146ed 2005-07-12 devnull static u32int readiebuck(IEBucks *ib, int b);
48 a0d146ed 2005-07-12 devnull static void freeiebucks(IEBucks *ib);
51 a0d146ed 2005-07-12 devnull * build a sorted file with all IEntries which should be in ix.
52 a0d146ed 2005-07-12 devnull * assumes the arenas' directories are up to date.
53 a0d146ed 2005-07-12 devnull * reads each, converts the entries to index entries,
54 a0d146ed 2005-07-12 devnull * and sorts them.
57 a0d146ed 2005-07-12 devnull sortrawientries(Index *ix, Part *tmp, u64int *base, Bloom *bloom)
59 a0d146ed 2005-07-12 devnull IEBucks *ib;
60 a0d146ed 2005-07-12 devnull u64int clumps, sorted;
61 a0d146ed 2005-07-12 devnull u32int n;
62 a0d146ed 2005-07-12 devnull int i, ok;
64 a0d146ed 2005-07-12 devnull //ZZZ should allow configuration of bits, bucket size
65 a0d146ed 2005-07-12 devnull ib = initiebucks(tmp, 8, 64*1024);
66 a0d146ed 2005-07-12 devnull if(ib == nil){
67 a0d146ed 2005-07-12 devnull seterr(EOk, "can't create sorting buckets: %r");
68 a0d146ed 2005-07-12 devnull return TWID64;
71 a0d146ed 2005-07-12 devnull clumps = 0;
72 a0d146ed 2005-07-12 devnull fprint(2, "constructing entry list\n");
73 a0d146ed 2005-07-12 devnull for(i = 0; i < ix->narenas; i++){
74 a0d146ed 2005-07-12 devnull n = readarenainfo(ib, ix->arenas[i], ix->amap[i].start, bloom);
75 a0d146ed 2005-07-12 devnull if(n == TWID32){
79 a0d146ed 2005-07-12 devnull clumps += n;
81 a0d146ed 2005-07-12 devnull fprint(2, "sorting %lld entries\n", clumps);
82 a0d146ed 2005-07-12 devnull if(ok == 0){
83 a0d146ed 2005-07-12 devnull sorted = sortiebucks(ib);
84 a0d146ed 2005-07-12 devnull *base = (u64int)ib->chunks * ib->size;
85 a0d146ed 2005-07-12 devnull if(sorted != clumps){
86 a0d146ed 2005-07-12 devnull fprint(2, "sorting messed up: clumps=%lld sorted=%lld\n", clumps, sorted);
90 a0d146ed 2005-07-12 devnull freeiebucks(ib);
91 a0d146ed 2005-07-12 devnull if(ok < 0)
92 a0d146ed 2005-07-12 devnull return TWID64;
93 a0d146ed 2005-07-12 devnull return clumps;
96 a0d146ed 2005-07-12 devnull #define CHECK(cis) if(((ulong*)cis)[-4] != 0xA110C09) xabort();
99 a0d146ed 2005-07-12 devnull xabort(void)
108 a0d146ed 2005-07-12 devnull * read in all of the arena's clump directory,
109 a0d146ed 2005-07-12 devnull * convert to IEntry format, and bucket sort based
110 a0d146ed 2005-07-12 devnull * on the first few bits.
112 a0d146ed 2005-07-12 devnull static u32int
113 a0d146ed 2005-07-12 devnull readarenainfo(IEBucks *ib, Arena *arena, u64int a, Bloom *b)
115 a0d146ed 2005-07-12 devnull IEntry ie;
116 a0d146ed 2005-07-12 devnull ClumpInfo *ci, *cis;
117 a0d146ed 2005-07-12 devnull u32int clump;
118 a0d146ed 2005-07-12 devnull int i, n, ok, nskip;
119 a0d146ed 2005-07-12 devnull // static Biobuf bout;
121 a0d146ed 2005-07-12 devnull //ZZZ remove fprint?
122 a0d146ed 2005-07-12 devnull //fprint(2, "ra %s %d %d\n", arena->name, arena->memstats.clumps, arena->diskstats.clumps);
123 a0d146ed 2005-07-12 devnull if(arena->memstats.clumps)
124 a0d146ed 2005-07-12 devnull fprint(2, "\tarena %s: %d entries\n", arena->name, arena->memstats.clumps);
126 a0d146ed 2005-07-12 devnull fprint(2, "[%s] ", arena->name);
128 a0d146ed 2005-07-12 devnull cis = MKN(ClumpInfo, ClumpChunks);
130 a0d146ed 2005-07-12 devnull nskip = 0;
131 a0d146ed 2005-07-12 devnull memset(&ie, 0, sizeof(IEntry));
132 a0d146ed 2005-07-12 devnull // Binit(&bout, 1, OWRITE);
133 a0d146ed 2005-07-12 devnull for(clump = 0; clump < arena->memstats.clumps; clump += n){
134 a0d146ed 2005-07-12 devnull n = ClumpChunks;
135 a0d146ed 2005-07-12 devnull if(n > arena->memstats.clumps - clump)
136 a0d146ed 2005-07-12 devnull n = arena->memstats.clumps - clump;
137 a0d146ed 2005-07-12 devnull if(readclumpinfos(arena, clump, cis, n) != n){
138 a0d146ed 2005-07-12 devnull seterr(EOk, "arena directory read failed: %r");
139 a0d146ed 2005-07-12 devnull ok = -1;
143 a0d146ed 2005-07-12 devnull for(i = 0; i < n; i++){
144 a0d146ed 2005-07-12 devnull ci = &cis[i];
145 a0d146ed 2005-07-12 devnull ie.ia.type = ci->type;
146 a0d146ed 2005-07-12 devnull ie.ia.size = ci->uncsize;
147 a0d146ed 2005-07-12 devnull ie.ia.addr = a;
148 a0d146ed 2005-07-12 devnull a += ci->size + ClumpSize;
149 a0d146ed 2005-07-12 devnull ie.ia.blocks = (ci->size + ClumpSize + (1 << ABlockLog) - 1) >> ABlockLog;
150 a0d146ed 2005-07-12 devnull scorecp(ie.score, ci->score);
151 a0d146ed 2005-07-12 devnull // Bprint(&bout, "%22lld %V %3d %5d\n",
152 a0d146ed 2005-07-12 devnull // ie.ia.addr, ie.score, ie.ia.type, ie.ia.size);
153 a0d146ed 2005-07-12 devnull if(ci->type == VtCorruptType){
154 a0d146ed 2005-07-12 devnull // print("! %V %22lld %3d %5d %3d\n",
155 a0d146ed 2005-07-12 devnull // ie.score, ie.ia.addr, ie.ia.type, ie.ia.size, ie.ia.blocks);
156 a0d146ed 2005-07-12 devnull nskip++;
158 a0d146ed 2005-07-12 devnull sprayientry(ib, &ie);
159 a0d146ed 2005-07-12 devnull markbloomfilter(b, ie.score);
162 a0d146ed 2005-07-12 devnull // Bterm(&bout);
163 a0d146ed 2005-07-12 devnull free(cis);
164 a0d146ed 2005-07-12 devnull if(ok < 0)
165 a0d146ed 2005-07-12 devnull return TWID32;
166 a0d146ed 2005-07-12 devnull return clump - nskip;
170 a0d146ed 2005-07-12 devnull * initialize the external bucket sorting data structures
172 a0d146ed 2005-07-12 devnull static IEBucks*
173 a0d146ed 2005-07-12 devnull initiebucks(Part *part, int bits, u32int size)
175 a0d146ed 2005-07-12 devnull IEBucks *ib;
178 a0d146ed 2005-07-12 devnull ib = MKZ(IEBucks);
179 a0d146ed 2005-07-12 devnull if(ib == nil){
180 a0d146ed 2005-07-12 devnull seterr(EOk, "out of memory");
181 a0d146ed 2005-07-12 devnull return nil;
183 a0d146ed 2005-07-12 devnull ib->bits = bits;
184 a0d146ed 2005-07-12 devnull ib->nbucks = 1 << bits;
185 a0d146ed 2005-07-12 devnull ib->size = size;
186 a0d146ed 2005-07-12 devnull ib->usable = (size - U32Size) / IEntrySize * IEntrySize;
187 a0d146ed 2005-07-12 devnull ib->bucks = MKNZ(IEBuck, ib->nbucks);
188 a0d146ed 2005-07-12 devnull if(ib->bucks == nil){
189 a0d146ed 2005-07-12 devnull seterr(EOk, "out of memory allocation sorting buckets");
190 a0d146ed 2005-07-12 devnull freeiebucks(ib);
191 a0d146ed 2005-07-12 devnull return nil;
193 a0d146ed 2005-07-12 devnull ib->xbuf = MKN(u8int, size * ((1 << bits)+1));
194 d67cd5c3 2005-07-19 devnull ib->buf = (u8int*)(((uintptr)ib->xbuf+size-1)&~(uintptr)(size-1));
195 a0d146ed 2005-07-12 devnull if(ib->buf == nil){
196 a0d146ed 2005-07-12 devnull seterr(EOk, "out of memory allocating sorting buckets' buffers");
197 a0d146ed 2005-07-12 devnull freeiebucks(ib);
198 a0d146ed 2005-07-12 devnull return nil;
200 a0d146ed 2005-07-12 devnull for(i = 0; i < ib->nbucks; i++){
201 a0d146ed 2005-07-12 devnull ib->bucks[i].head = TWID32;
202 a0d146ed 2005-07-12 devnull ib->bucks[i].buf = &ib->buf[i * size];
204 a0d146ed 2005-07-12 devnull ib->part = part;
205 a0d146ed 2005-07-12 devnull return ib;
208 a0d146ed 2005-07-12 devnull static void
209 a0d146ed 2005-07-12 devnull freeiebucks(IEBucks *ib)
211 a0d146ed 2005-07-12 devnull if(ib == nil)
213 a0d146ed 2005-07-12 devnull free(ib->bucks);
214 a0d146ed 2005-07-12 devnull free(ib->buf);
215 a0d146ed 2005-07-12 devnull free(ib);
219 a0d146ed 2005-07-12 devnull * initial sort: put the entry into the correct bucket
221 a0d146ed 2005-07-12 devnull static int
222 a0d146ed 2005-07-12 devnull sprayientry(IEBucks *ib, IEntry *ie)
224 a0d146ed 2005-07-12 devnull u32int n;
227 a0d146ed 2005-07-12 devnull b = hashbits(ie->score, ib->bits);
228 a0d146ed 2005-07-12 devnull n = ib->bucks[b].used;
229 a0d146ed 2005-07-12 devnull if(n + IEntrySize > ib->usable){
230 a0d146ed 2005-07-12 devnull /* should be flushed below, but if flush fails, this can happen */
231 a0d146ed 2005-07-12 devnull seterr(EOk, "out of space in bucket");
232 a0d146ed 2005-07-12 devnull return -1;
234 a0d146ed 2005-07-12 devnull packientry(ie, &ib->bucks[b].buf[n]);
235 a0d146ed 2005-07-12 devnull n += IEntrySize;
236 a0d146ed 2005-07-12 devnull ib->bucks[b].used = n;
237 a0d146ed 2005-07-12 devnull if(n + IEntrySize <= ib->usable)
238 a0d146ed 2005-07-12 devnull return 0;
239 a0d146ed 2005-07-12 devnull return flushiebuck(ib, b, 1);
243 a0d146ed 2005-07-12 devnull * finish sorting:
244 a0d146ed 2005-07-12 devnull * for each bucket, read it in and sort it
245 a0d146ed 2005-07-12 devnull * write out the the final file
247 a0d146ed 2005-07-12 devnull static u64int
248 a0d146ed 2005-07-12 devnull sortiebucks(IEBucks *ib)
250 a0d146ed 2005-07-12 devnull u64int tot;
251 a0d146ed 2005-07-12 devnull u32int n;
254 a0d146ed 2005-07-12 devnull if(flushiebucks(ib) < 0)
255 a0d146ed 2005-07-12 devnull return TWID64;
256 a0d146ed 2005-07-12 devnull for(i = 0; i < ib->nbucks; i++)
257 a0d146ed 2005-07-12 devnull ib->bucks[i].buf = nil;
258 a0d146ed 2005-07-12 devnull ib->off = (u64int)ib->chunks * ib->size;
259 a0d146ed 2005-07-12 devnull free(ib->xbuf);
261 a0d146ed 2005-07-12 devnull fprint(2, "ib->max = %lld\n", ib->max);
262 a0d146ed 2005-07-12 devnull fprint(2, "ib->chunks = %ud\n", ib->chunks);
264 a0d146ed 2005-07-12 devnull ib->buf = MKN(u8int, ib->max + U32Size);
265 a0d146ed 2005-07-12 devnull if(ib->buf == nil){
266 a0d146ed 2005-07-12 devnull seterr(EOk, "out of memory allocating final sorting buffer; try more buckets");
267 a0d146ed 2005-07-12 devnull return TWID64;
269 a0d146ed 2005-07-12 devnull tot = 0;
270 a0d146ed 2005-07-12 devnull for(i = 0; i < ib->nbucks; i++){
271 a0d146ed 2005-07-12 devnull n = sortiebuck(ib, i);
272 a0d146ed 2005-07-12 devnull if(n == TWID32)
273 a0d146ed 2005-07-12 devnull return TWID64;
274 a0d146ed 2005-07-12 devnull if(n != ib->bucks[i].total/IEntrySize)
275 a0d146ed 2005-07-12 devnull fprint(2, "bucket %d changed count %d => %d\n",
276 a0d146ed 2005-07-12 devnull i, (int)(ib->bucks[i].total/IEntrySize), n);
277 a0d146ed 2005-07-12 devnull tot += n;
279 a0d146ed 2005-07-12 devnull return tot;
280 a0d146ed 2005-07-12 devnull return 0;
284 a0d146ed 2005-07-12 devnull * sort from bucket b of ib into the output file to
286 a0d146ed 2005-07-12 devnull static u32int
287 a0d146ed 2005-07-12 devnull sortiebuck(IEBucks *ib, int b)
289 a0d146ed 2005-07-12 devnull u32int n;
291 a0d146ed 2005-07-12 devnull n = readiebuck(ib, b);
292 a0d146ed 2005-07-12 devnull if(n == TWID32)
293 a0d146ed 2005-07-12 devnull return TWID32;
294 a0d146ed 2005-07-12 devnull qsort(ib->buf, n, IEntrySize, ientrycmp);
295 d67cd5c3 2005-07-19 devnull if(writepart(ib->part, ib->off, ib->buf, n*IEntrySize) < 0){
296 a0d146ed 2005-07-12 devnull seterr(EOk, "can't write sorted bucket: %r");
297 a0d146ed 2005-07-12 devnull return TWID32;
299 a0d146ed 2005-07-12 devnull ib->off += n * IEntrySize;
300 a0d146ed 2005-07-12 devnull return n;
304 a0d146ed 2005-07-12 devnull * write out a single bucket
306 a0d146ed 2005-07-12 devnull static int
307 a0d146ed 2005-07-12 devnull flushiebuck(IEBucks *ib, int b, int reset)
309 a0d146ed 2005-07-12 devnull u32int n;
311 a0d146ed 2005-07-12 devnull if(ib->bucks[b].used == 0)
312 a0d146ed 2005-07-12 devnull return 0;
313 a0d146ed 2005-07-12 devnull n = ib->bucks[b].used;
314 a0d146ed 2005-07-12 devnull U32PUT(&ib->bucks[b].buf[n], ib->bucks[b].head);
315 a0d146ed 2005-07-12 devnull n += U32Size;
316 a0d146ed 2005-07-12 devnull USED(n);
317 a0d146ed 2005-07-12 devnull if(writepart(ib->part, (u64int)ib->chunks * ib->size, ib->bucks[b].buf, ib->size) < 0){
318 a0d146ed 2005-07-12 devnull seterr(EOk, "can't write sorting bucket to file: %r");
319 a0d146ed 2005-07-12 devnull xabort();
320 a0d146ed 2005-07-12 devnull return -1;
322 a0d146ed 2005-07-12 devnull ib->bucks[b].head = ib->chunks++;
323 a0d146ed 2005-07-12 devnull ib->bucks[b].total += ib->bucks[b].used;
324 a0d146ed 2005-07-12 devnull if(reset)
325 a0d146ed 2005-07-12 devnull ib->bucks[b].used = 0;
326 a0d146ed 2005-07-12 devnull return 0;
330 a0d146ed 2005-07-12 devnull * write out all of the buckets, and compute
331 a0d146ed 2005-07-12 devnull * the maximum size of any bucket
333 a0d146ed 2005-07-12 devnull static int
334 a0d146ed 2005-07-12 devnull flushiebucks(IEBucks *ib)
338 a0d146ed 2005-07-12 devnull for(i = 0; i < ib->nbucks; i++){
339 a0d146ed 2005-07-12 devnull if(flushiebuck(ib, i, 0) < 0)
340 a0d146ed 2005-07-12 devnull return -1;
341 a0d146ed 2005-07-12 devnull if(ib->bucks[i].total > ib->max)
342 a0d146ed 2005-07-12 devnull ib->max = ib->bucks[i].total;
344 a0d146ed 2005-07-12 devnull return 0;
348 a0d146ed 2005-07-12 devnull * read in the chained buffers for bucket b,
349 a0d146ed 2005-07-12 devnull * and return it's total number of IEntries
351 a0d146ed 2005-07-12 devnull static u32int
352 a0d146ed 2005-07-12 devnull readiebuck(IEBucks *ib, int b)
354 a0d146ed 2005-07-12 devnull u32int head, m, n;
356 a0d146ed 2005-07-12 devnull head = ib->bucks[b].head;
358 a0d146ed 2005-07-12 devnull m = ib->bucks[b].used;
359 a0d146ed 2005-07-12 devnull if(m == 0)
360 a0d146ed 2005-07-12 devnull m = ib->usable;
361 a0d146ed 2005-07-12 devnull // if(ib->bucks[b].total)
362 a0d146ed 2005-07-12 devnull // fprint(2, "\tbucket %d: %d entries\n", b, ib->bucks[b].total/IEntrySize);
363 a0d146ed 2005-07-12 devnull while(head != TWID32){
364 d67cd5c3 2005-07-19 devnull if(readpart(ib->part, (u64int)head * ib->size, &ib->buf[n], m+U32Size) < 0){
365 a0d146ed 2005-07-12 devnull seterr(EOk, "can't read index sort bucket: %r");
366 a0d146ed 2005-07-12 devnull return TWID32;
369 a0d146ed 2005-07-12 devnull head = U32GET(&ib->buf[n]);
370 a0d146ed 2005-07-12 devnull m = ib->usable;
372 a0d146ed 2005-07-12 devnull if(n != ib->bucks[b].total)
373 a0d146ed 2005-07-12 devnull fprint(2, "\tbucket %d: expected %d entries, got %d\n",
374 a0d146ed 2005-07-12 devnull b, (int)ib->bucks[b].total/IEntrySize, n/IEntrySize);
375 a0d146ed 2005-07-12 devnull return n / IEntrySize;