1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
2 7a4ee46d 2003-11-23 devnull #include "dat.h"
3 7a4ee46d 2003-11-23 devnull #include "fns.h"
5 7a4ee46d 2003-11-23 devnull typedef struct IEBuck IEBuck;
6 7a4ee46d 2003-11-23 devnull typedef struct IEBucks IEBucks;
10 7a4ee46d 2003-11-23 devnull ClumpChunks = 32*1024
13 7a4ee46d 2003-11-23 devnull struct IEBuck
15 7a4ee46d 2003-11-23 devnull u32int head; /* head of chain of chunks on the disk */
16 7a4ee46d 2003-11-23 devnull u32int used; /* usage of the last chunk */
17 7a4ee46d 2003-11-23 devnull u64int total; /* total number of bytes in this bucket */
18 7a4ee46d 2003-11-23 devnull u8int *buf; /* chunk of entries for this bucket */
21 7a4ee46d 2003-11-23 devnull struct IEBucks
23 7a4ee46d 2003-11-23 devnull Part *part;
24 7a4ee46d 2003-11-23 devnull u64int off; /* offset for writing data in the partition */
25 7a4ee46d 2003-11-23 devnull u32int chunks; /* total chunks written to fd */
26 7a4ee46d 2003-11-23 devnull u64int max; /* max bytes entered in any one bucket */
27 7a4ee46d 2003-11-23 devnull int bits; /* number of bits in initial bucket sort */
28 7a4ee46d 2003-11-23 devnull int nbucks; /* 1 << bits, the number of buckets */
29 7a4ee46d 2003-11-23 devnull u32int size; /* bytes in each of the buckets chunks */
30 7a4ee46d 2003-11-23 devnull u32int usable; /* amount usable for IEntry data */
31 7a4ee46d 2003-11-23 devnull u8int *buf; /* buffer for all chunks */
32 7a4ee46d 2003-11-23 devnull IEBuck *bucks;
35 7a4ee46d 2003-11-23 devnull #define U32GET(p) (((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
36 7a4ee46d 2003-11-23 devnull #define U32PUT(p,v) (p)[0]=(v)>>24;(p)[1]=(v)>>16;(p)[2]=(v)>>8;(p)[3]=(v)
38 7a4ee46d 2003-11-23 devnull static IEBucks *initiebucks(Part *part, int bits, u32int size);
39 7a4ee46d 2003-11-23 devnull static int flushiebuck(IEBucks *ib, int b, int reset);
40 7a4ee46d 2003-11-23 devnull static int flushiebucks(IEBucks *ib);
41 7a4ee46d 2003-11-23 devnull static u32int sortiebuck(IEBucks *ib, int b);
42 7a4ee46d 2003-11-23 devnull static u64int sortiebucks(IEBucks *ib);
43 7a4ee46d 2003-11-23 devnull static int sprayientry(IEBucks *ib, IEntry *ie);
44 7a4ee46d 2003-11-23 devnull static u32int readarenainfo(IEBucks *ib, Arena *arena, u64int a);
45 7a4ee46d 2003-11-23 devnull static u32int readiebuck(IEBucks *ib, int b);
46 7a4ee46d 2003-11-23 devnull static void freeiebucks(IEBucks *ib);
49 7a4ee46d 2003-11-23 devnull * build a sorted file with all Ientries which should be in ix.
50 7a4ee46d 2003-11-23 devnull * assumes the arenas' directories are up to date.
51 7a4ee46d 2003-11-23 devnull * reads each, converts the entries to index entries,
52 7a4ee46d 2003-11-23 devnull * and sorts them.
55 7a4ee46d 2003-11-23 devnull sortrawientries(Index *ix, Part *tmp, u64int *base)
57 7a4ee46d 2003-11-23 devnull IEBucks *ib;
58 7a4ee46d 2003-11-23 devnull u64int clumps, sorted;
59 7a4ee46d 2003-11-23 devnull u32int n;
60 7a4ee46d 2003-11-23 devnull int i, ok;
62 7a4ee46d 2003-11-23 devnull //ZZZ should allow configuration of bits, bucket size
63 7a4ee46d 2003-11-23 devnull ib = initiebucks(tmp, 8, 64*1024);
64 7a4ee46d 2003-11-23 devnull if(ib == nil){
65 7a4ee46d 2003-11-23 devnull seterr(EOk, "can't create sorting buckets: %r");
66 7a4ee46d 2003-11-23 devnull return TWID64;
69 7a4ee46d 2003-11-23 devnull clumps = 0;
70 7a4ee46d 2003-11-23 devnull for(i = 0; i < ix->narenas; i++){
71 7a4ee46d 2003-11-23 devnull n = readarenainfo(ib, ix->arenas[i], ix->amap[i].start);
72 7a4ee46d 2003-11-23 devnull if(n == TWID32){
76 7a4ee46d 2003-11-23 devnull clumps += n;
78 7a4ee46d 2003-11-23 devnull fprint(2, "got %lld clumps - starting sort\n", clumps);
80 7a4ee46d 2003-11-23 devnull sorted = sortiebucks(ib);
81 7a4ee46d 2003-11-23 devnull *base = (u64int)ib->chunks * ib->size;
82 7a4ee46d 2003-11-23 devnull if(sorted != clumps){
83 7a4ee46d 2003-11-23 devnull fprint(2, "sorting messed up: clumps=%lld sorted=%lld\n", clumps, sorted);
87 7a4ee46d 2003-11-23 devnull freeiebucks(ib);
88 7a4ee46d 2003-11-23 devnull if(ok < 0)
89 7a4ee46d 2003-11-23 devnull return TWID64;
90 7a4ee46d 2003-11-23 devnull return clumps;
94 7a4ee46d 2003-11-23 devnull * read in all of the arena's clump directory,
95 7a4ee46d 2003-11-23 devnull * convert to IEntry format, and bucket sort based
96 7a4ee46d 2003-11-23 devnull * on the first few bits.
98 7a4ee46d 2003-11-23 devnull static u32int
99 7a4ee46d 2003-11-23 devnull readarenainfo(IEBucks *ib, Arena *arena, u64int a)
101 7a4ee46d 2003-11-23 devnull IEntry ie;
102 7a4ee46d 2003-11-23 devnull ClumpInfo *ci, *cis;
103 7a4ee46d 2003-11-23 devnull u32int clump;
104 7a4ee46d 2003-11-23 devnull int i, n, ok;
106 7a4ee46d 2003-11-23 devnull //ZZZ remove fprint?
107 7a4ee46d 2003-11-23 devnull if(arena->clumps)
108 7a4ee46d 2003-11-23 devnull fprint(2, "reading directory for arena=%s with %d entries\n", arena->name, arena->clumps);
110 7a4ee46d 2003-11-23 devnull cis = MKN(ClumpInfo, ClumpChunks);
112 7a4ee46d 2003-11-23 devnull memset(&ie, 0, sizeof(IEntry));
113 7a4ee46d 2003-11-23 devnull for(clump = 0; clump < arena->clumps; clump += n){
114 7a4ee46d 2003-11-23 devnull n = ClumpChunks;
115 7a4ee46d 2003-11-23 devnull if(n > arena->clumps - clump)
116 7a4ee46d 2003-11-23 devnull n = arena->clumps - clump;
117 7a4ee46d 2003-11-23 devnull if(readclumpinfos(arena, clump, cis, n) != n){
118 7a4ee46d 2003-11-23 devnull seterr(EOk, "arena directory read failed: %r");
119 7a4ee46d 2003-11-23 devnull ok = -1;
123 7a4ee46d 2003-11-23 devnull for(i = 0; i < n; i++){
124 7a4ee46d 2003-11-23 devnull ci = &cis[i];
125 7a4ee46d 2003-11-23 devnull ie.ia.type = ci->type;
126 7a4ee46d 2003-11-23 devnull ie.ia.size = ci->uncsize;
127 7a4ee46d 2003-11-23 devnull ie.ia.addr = a;
128 7a4ee46d 2003-11-23 devnull a += ci->size + ClumpSize;
129 7a4ee46d 2003-11-23 devnull ie.ia.blocks = (ci->size + ClumpSize + (1 << ABlockLog) - 1) >> ABlockLog;
130 7a4ee46d 2003-11-23 devnull scorecp(ie.score, ci->score);
131 7a4ee46d 2003-11-23 devnull sprayientry(ib, &ie);
134 7a4ee46d 2003-11-23 devnull free(cis);
135 7a4ee46d 2003-11-23 devnull if(ok < 0)
136 7a4ee46d 2003-11-23 devnull return TWID32;
137 7a4ee46d 2003-11-23 devnull return clump;
141 7a4ee46d 2003-11-23 devnull * initialize the external bucket sorting data structures
143 7a4ee46d 2003-11-23 devnull static IEBucks*
144 7a4ee46d 2003-11-23 devnull initiebucks(Part *part, int bits, u32int size)
146 7a4ee46d 2003-11-23 devnull IEBucks *ib;
149 7a4ee46d 2003-11-23 devnull ib = MKZ(IEBucks);
150 7a4ee46d 2003-11-23 devnull if(ib == nil){
151 7a4ee46d 2003-11-23 devnull seterr(EOk, "out of memory");
152 7a4ee46d 2003-11-23 devnull return nil;
154 7a4ee46d 2003-11-23 devnull ib->bits = bits;
155 7a4ee46d 2003-11-23 devnull ib->nbucks = 1 << bits;
156 7a4ee46d 2003-11-23 devnull ib->size = size;
157 7a4ee46d 2003-11-23 devnull ib->usable = (size - U32Size) / IEntrySize * IEntrySize;
158 7a4ee46d 2003-11-23 devnull ib->bucks = MKNZ(IEBuck, ib->nbucks);
159 7a4ee46d 2003-11-23 devnull if(ib->bucks == nil){
160 7a4ee46d 2003-11-23 devnull seterr(EOk, "out of memory allocation sorting buckets");
161 7a4ee46d 2003-11-23 devnull freeiebucks(ib);
162 7a4ee46d 2003-11-23 devnull return nil;
164 7a4ee46d 2003-11-23 devnull ib->buf = MKN(u8int, size * (1 << bits));
165 7a4ee46d 2003-11-23 devnull if(ib->buf == nil){
166 7a4ee46d 2003-11-23 devnull seterr(EOk, "out of memory allocating sorting buckets' buffers");
167 7a4ee46d 2003-11-23 devnull freeiebucks(ib);
168 7a4ee46d 2003-11-23 devnull return nil;
170 7a4ee46d 2003-11-23 devnull for(i = 0; i < ib->nbucks; i++){
171 7a4ee46d 2003-11-23 devnull ib->bucks[i].head = TWID32;
172 7a4ee46d 2003-11-23 devnull ib->bucks[i].buf = &ib->buf[i * size];
174 7a4ee46d 2003-11-23 devnull ib->part = part;
175 7a4ee46d 2003-11-23 devnull return ib;
178 7a4ee46d 2003-11-23 devnull static void
179 7a4ee46d 2003-11-23 devnull freeiebucks(IEBucks *ib)
181 7a4ee46d 2003-11-23 devnull if(ib == nil)
183 7a4ee46d 2003-11-23 devnull free(ib->bucks);
184 7a4ee46d 2003-11-23 devnull free(ib->buf);
185 7a4ee46d 2003-11-23 devnull free(ib);
189 7a4ee46d 2003-11-23 devnull * initial sort: put the entry into the correct bucket
191 7a4ee46d 2003-11-23 devnull static int
192 7a4ee46d 2003-11-23 devnull sprayientry(IEBucks *ib, IEntry *ie)
194 7a4ee46d 2003-11-23 devnull u32int n;
197 7a4ee46d 2003-11-23 devnull b = hashbits(ie->score, ib->bits);
198 7a4ee46d 2003-11-23 devnull n = ib->bucks[b].used;
199 7a4ee46d 2003-11-23 devnull packientry(ie, &ib->bucks[b].buf[n]);
200 7a4ee46d 2003-11-23 devnull n += IEntrySize;
201 7a4ee46d 2003-11-23 devnull ib->bucks[b].used = n;
202 7a4ee46d 2003-11-23 devnull if(n + IEntrySize <= ib->usable)
203 7a4ee46d 2003-11-23 devnull return 0;
204 7a4ee46d 2003-11-23 devnull return flushiebuck(ib, b, 1);
208 7a4ee46d 2003-11-23 devnull * finish sorting:
209 7a4ee46d 2003-11-23 devnull * for each bucket, read it in and sort it
210 7a4ee46d 2003-11-23 devnull * write out the the final file
212 7a4ee46d 2003-11-23 devnull static u64int
213 7a4ee46d 2003-11-23 devnull sortiebucks(IEBucks *ib)
215 7a4ee46d 2003-11-23 devnull u64int tot;
216 7a4ee46d 2003-11-23 devnull u32int n;
219 7a4ee46d 2003-11-23 devnull if(flushiebucks(ib) < 0)
220 7a4ee46d 2003-11-23 devnull return TWID64;
221 7a4ee46d 2003-11-23 devnull for(i = 0; i < ib->nbucks; i++)
222 7a4ee46d 2003-11-23 devnull ib->bucks[i].buf = nil;
223 7a4ee46d 2003-11-23 devnull ib->off = (u64int)ib->chunks * ib->size;
224 7a4ee46d 2003-11-23 devnull free(ib->buf);
225 7a4ee46d 2003-11-23 devnull fprint(2, "ib->max = %lld\n", ib->max);
226 7a4ee46d 2003-11-23 devnull fprint(2, "ib->chunks = %ud\n", ib->chunks);
227 7a4ee46d 2003-11-23 devnull ib->buf = MKN(u8int, ib->max + U32Size);
228 7a4ee46d 2003-11-23 devnull if(ib->buf == nil){
229 7a4ee46d 2003-11-23 devnull seterr(EOk, "out of memory allocating final sorting buffer; try more buckets");
230 7a4ee46d 2003-11-23 devnull return TWID64;
232 7a4ee46d 2003-11-23 devnull tot = 0;
233 7a4ee46d 2003-11-23 devnull for(i = 0; i < ib->nbucks; i++){
234 7a4ee46d 2003-11-23 devnull n = sortiebuck(ib, i);
235 7a4ee46d 2003-11-23 devnull if(n == TWID32)
236 7a4ee46d 2003-11-23 devnull return TWID64;
237 7a4ee46d 2003-11-23 devnull tot += n;
239 7a4ee46d 2003-11-23 devnull return tot;
240 7a4ee46d 2003-11-23 devnull return 0;
244 7a4ee46d 2003-11-23 devnull * sort from bucket b of ib into the output file to
246 7a4ee46d 2003-11-23 devnull static u32int
247 7a4ee46d 2003-11-23 devnull sortiebuck(IEBucks *ib, int b)
249 7a4ee46d 2003-11-23 devnull u32int n;
251 7a4ee46d 2003-11-23 devnull n = readiebuck(ib, b);
252 7a4ee46d 2003-11-23 devnull if(n == TWID32)
253 7a4ee46d 2003-11-23 devnull return TWID32;
254 7a4ee46d 2003-11-23 devnull qsort(ib->buf, n, IEntrySize, ientrycmp);
255 7a4ee46d 2003-11-23 devnull if(writepart(ib->part, ib->off, ib->buf, n * IEntrySize) < 0){
256 7a4ee46d 2003-11-23 devnull seterr(EOk, "can't write sorted bucket: %r");
257 7a4ee46d 2003-11-23 devnull return TWID32;
259 7a4ee46d 2003-11-23 devnull ib->off += n * IEntrySize;
260 7a4ee46d 2003-11-23 devnull return n;
264 7a4ee46d 2003-11-23 devnull * write out a single bucket
266 7a4ee46d 2003-11-23 devnull static int
267 7a4ee46d 2003-11-23 devnull flushiebuck(IEBucks *ib, int b, int reset)
269 7a4ee46d 2003-11-23 devnull u32int n;
271 7a4ee46d 2003-11-23 devnull if(ib->bucks[b].used == 0)
272 7a4ee46d 2003-11-23 devnull return 0;
273 7a4ee46d 2003-11-23 devnull n = ib->bucks[b].used;
274 7a4ee46d 2003-11-23 devnull U32PUT(&ib->bucks[b].buf[n], ib->bucks[b].head);
275 7a4ee46d 2003-11-23 devnull n += U32Size;
276 7a4ee46d 2003-11-23 devnull if(writepart(ib->part, (u64int)ib->chunks * ib->size, ib->bucks[b].buf, n) < 0){
277 7a4ee46d 2003-11-23 devnull seterr(EOk, "can't write sorting bucket to file: %r");
278 7a4ee46d 2003-11-23 devnull return -1;
280 7a4ee46d 2003-11-23 devnull ib->bucks[b].head = ib->chunks++;
281 7a4ee46d 2003-11-23 devnull ib->bucks[b].total += ib->bucks[b].used;
282 7a4ee46d 2003-11-23 devnull if(reset)
283 7a4ee46d 2003-11-23 devnull ib->bucks[b].used = 0;
284 7a4ee46d 2003-11-23 devnull return 0;
288 7a4ee46d 2003-11-23 devnull * write out all of the buckets, and compute
289 7a4ee46d 2003-11-23 devnull * the maximum size of any bucket
291 7a4ee46d 2003-11-23 devnull static int
292 7a4ee46d 2003-11-23 devnull flushiebucks(IEBucks *ib)
296 7a4ee46d 2003-11-23 devnull for(i = 0; i < ib->nbucks; i++){
297 7a4ee46d 2003-11-23 devnull if(flushiebuck(ib, i, 0) < 0)
298 7a4ee46d 2003-11-23 devnull return -1;
299 7a4ee46d 2003-11-23 devnull if(ib->bucks[i].total > ib->max)
300 7a4ee46d 2003-11-23 devnull ib->max = ib->bucks[i].total;
302 7a4ee46d 2003-11-23 devnull return 0;
306 7a4ee46d 2003-11-23 devnull * read in the chained buffers for bucket b,
307 7a4ee46d 2003-11-23 devnull * and return it's total number of IEntries
309 7a4ee46d 2003-11-23 devnull static u32int
310 7a4ee46d 2003-11-23 devnull readiebuck(IEBucks *ib, int b)
312 7a4ee46d 2003-11-23 devnull u32int head, n, m;
314 7a4ee46d 2003-11-23 devnull head = ib->bucks[b].head;
316 7a4ee46d 2003-11-23 devnull m = ib->bucks[b].used;
317 7a4ee46d 2003-11-23 devnull if(m == 0)
318 7a4ee46d 2003-11-23 devnull m = ib->usable;
319 7a4ee46d 2003-11-23 devnull fprint(2, "%d total = %lld\n", b, ib->bucks[b].total);
320 7a4ee46d 2003-11-23 devnull while(head != TWID32){
321 7a4ee46d 2003-11-23 devnull if(readpart(ib->part, (u64int)head * ib->size, &ib->buf[n], m + U32Size) < 0){
322 7a4ee46d 2003-11-23 devnull fprint(2, "n = %ud\n", n);
323 7a4ee46d 2003-11-23 devnull seterr(EOk, "can't read index sort bucket: %r");
324 7a4ee46d 2003-11-23 devnull return TWID32;
327 7a4ee46d 2003-11-23 devnull head = U32GET(&ib->buf[n]);
328 7a4ee46d 2003-11-23 devnull m = ib->usable;
330 7a4ee46d 2003-11-23 devnull fprint(2, "n = %ud\n", n);
331 7a4ee46d 2003-11-23 devnull return n / IEntrySize;
