1 /*
2 * Copyright (c) 2007-2012, Novell Inc.
3 *
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
6 */
7
8 /*
9 * repopage.c
10 *
11 * Paging and compression functions for the vertical repository data.
12 * Vertical data is grouped by key, normal data is grouped by solvable.
13 * This makes searching for a string in vertical data fast as there's
14 * no need to skip over data if keys we're not interested in.
15 *
16 * The vertical data is split into pages, each page is compressed with a fast
17 * compression algorithm. These pages are read in on demand, not recently used
18 * pages automatically get dropped.
19 */
20
21 #define _XOPEN_SOURCE 500
22
23 #include <sys/types.h>
24 #include <stdint.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <unistd.h>
29 #include <assert.h>
30 #include <fcntl.h>
31 #include <time.h>
32
33 #ifdef _WIN32
34 #include <windows.h>
35 #include <fileapi.h>
36 #include <io.h>
37 #endif
38
39 #include "repo.h"
40 #include "repopage.h"
41
42
43
44 #define BLOCK_SIZE (65536*1)
45 #if BLOCK_SIZE <= 65536
46 typedef uint16_t Ref;
47 #else
48 typedef uint32_t Ref;
49 #endif
50
51 /*
52 The format is tailored for fast decompression (i.e. only byte based),
53 and skewed to ASCII content (highest bit often not set):
54
55 a 0LLLLLLL
56 - self-describing ASCII character hex L
57 b 100lllll <l+1 bytes>
58 - literal run of length l+1
59 c 101oolll <8o>
60 - back ref of length l+2, at offset -(o+1) (o < 1 << 10)
61 d 110lllll <8o>
62 - back ref of length l+2+8, at offset -(o+1) (o < 1 << 8)
63 e 1110llll <8o> <8o>
64 - back ref of length l+3, at offset -(o+1) (o < 1 << 16)
65 f1 1111llll <8l> <8o> <8o>
66 - back ref, length l+19 (l < 1<<12), offset -(o+1) (o < 1<<16)
67 f2 11110lll <8l> <8o> <8o>
68 - back ref, length l+19 (l < 1<<11), offset -(o+1) (o < 1<<16)
69 g 11111lll <8l> <8o> <8o> <8o>
70 - back ref, length l+5 (l < 1<<11), offset -(o+1) (o < 1<<24)
71
72 Generally for a literal of length L we need L+1 bytes, hence it is
73 better to encode also very short backrefs (2 chars) as backrefs if
74 their offset is small, as that only needs two bytes. Except if we
75 already have a literal run, in that case it's better to append there,
76 instead of breaking it for a backref. So given a potential backref
77 at offset O, length L the strategy is as follows:
78
79 L < 2 : encode as 1-literal
80 L == 2, O > 1024 : encode as 1-literal
81 L == 2, have already literals: encode as 1-literal
82 O = O - 1
83 L >= 2, L <= 9, O < 1024 : encode as c
84 L >= 10, L <= 41, O < 256 : encode as d
85 else we have either O >= 1024, or L >= 42:
86 L < 3 : encode as 1-literal
87 L >= 3, L <= 18, O < 65536 : encode as e
88 L >= 19, L <= 4095+18, O < 65536 : encode as f
89 else we have either L >= 4096+18 or O >= 65536.
90 O >= 65536: encode as 1-literal, too bad
91 (with the current block size this can't happen)
92 L >= 4096+18, so reduce to 4095+18 : encode as f
93 */
94
95
96 static unsigned int
compress_buf(const unsigned char * in,unsigned int in_len,unsigned char * out,unsigned int out_len)97 compress_buf(const unsigned char *in, unsigned int in_len,
98 unsigned char *out, unsigned int out_len)
99 {
100 unsigned int oo = 0; /* out-offset */
101 unsigned int io = 0; /* in-offset */
102 #define HS (65536)
103 Ref htab[HS];
104 Ref hnext[BLOCK_SIZE];
105 unsigned int litofs = 0;
106 memset(htab, -1, sizeof (htab));
107 memset(hnext, -1, sizeof (hnext));
108 while (io + 2 < in_len)
109 {
110 /* Search for a match of the string starting at IN, we have at
111 least three characters. */
112 unsigned int hval = in[io] | in[io + 1] << 8 | in[io + 2] << 16;
113 unsigned int try, mlen, mofs, tries;
114 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
115 hval = hval & (HS - 1);
116 try = htab[hval];
117 hnext[io] = htab[hval];
118 htab[hval] = io;
119 mlen = 0;
120 mofs = 0;
121
122 for (tries = 0; try != -1 && tries < 12; tries++)
123 {
124 if (try < io
125 && in[try] == in[io] && in[try + 1] == in[io + 1])
126 {
127 mlen = 2;
128 mofs = (io - try) - 1;
129 break;
130 }
131 try = hnext[try];
132 }
133 for (; try != -1 && tries < 12; tries++)
134 {
135 /* assert(mlen >= 2); */
136 /* assert(io + mlen < in_len); */
137 /* Try a match starting from [io] with the strings at [try].
138 That's only sensible if TRY actually is before IO (can happen
139 with uninit hash table). If we have a previous match already
140 we're only going to take the new one if it's longer, hence
141 check the potentially last character. */
142 if (try < io && in[try + mlen] == in[io + mlen])
143 {
144 unsigned int this_len, this_ofs;
145 if (memcmp(in + try, in + io, mlen))
146 goto no_match;
147 this_len = mlen + 1;
148 /* Now try extending the match by more characters. */
149 for (;
150 io + this_len < in_len
151 && in[try + this_len] == in[io + this_len]; this_len++)
152 ;
153 #if 0
154 unsigned int testi;
155 for (testi = 0; testi < this_len; testi++)
156 assert(in[try + testi] == in[io + testi]);
157 #endif
158 this_ofs = (io - try) - 1;
159 /*if (this_ofs > 65535)
160 goto no_match; */
161 #if 0
162 assert(this_len >= 2);
163 assert(this_len >= mlen);
164 assert(this_len > mlen || (this_len == mlen && this_ofs > mofs));
165 #endif
166 mlen = this_len, mofs = this_ofs;
167 /* If our match extends up to the end of input, no next
168 match can become better. This is not just an
169 optimization, it establishes a loop invariant
170 (io + mlen < in_len). */
171 if (io + mlen >= in_len)
172 goto match_done;
173 }
174 no_match:
175 try = hnext[try];
176 /*if (io - try - 1 >= 65536)
177 break;*/
178 }
179
180 match_done:
181 if (mlen)
182 {
183 /*fprintf(stderr, "%d %d\n", mlen, mofs);*/
184 if (mlen == 2 && (litofs || mofs >= 1024))
185 mlen = 0;
186 /*else if (mofs >= 65536)
187 mlen = 0;*/
188 else if (mofs >= 65536)
189 {
190 if (mlen >= 2048 + 5)
191 mlen = 2047 + 5;
192 else if (mlen < 5)
193 mlen = 0;
194 }
195 else if (mlen < 3)
196 mlen = 0;
197 /*else if (mlen >= 4096 + 19)
198 mlen = 4095 + 19;*/
199 else if (mlen >= 2048 + 19)
200 mlen = 2047 + 19;
201 /* Skip this match if the next character would deliver a better one,
202 but only do this if we have the chance to really extend the
203 length (i.e. our current length isn't yet the (conservative)
204 maximum). */
205 if (mlen && mlen < (2048 + 5) && io + 3 < in_len)
206 {
207 unsigned int hval =
208 in[io + 1] | in[io + 2] << 8 | in[io + 3] << 16;
209 unsigned int try;
210 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
211 hval = hval & (HS - 1);
212 try = htab[hval];
213 if (try < io + 1
214 && in[try] == in[io + 1] && in[try + 1] == in[io + 2])
215 {
216 unsigned int this_len;
217 this_len = 2;
218 for (;
219 io + 1 + this_len < in_len
220 && in[try + this_len] == in[io + 1 + this_len];
221 this_len++)
222 ;
223 if (this_len >= mlen)
224 mlen = 0;
225 }
226 }
227 }
228 if (!mlen)
229 {
230 if (!litofs)
231 litofs = io + 1;
232 io++;
233 }
234 else
235 {
236 if (litofs)
237 {
238 unsigned litlen;
239 litofs--;
240 litlen = io - litofs;
241 /* fprintf(stderr, "lit: %d\n", litlen); */
242 while (litlen)
243 {
244 unsigned int easy_sz;
245 /* Emit everything we can as self-describers. As soon as
246 we hit a byte we can't emit as such we're going to emit
247 a length descriptor anyway, so we can as well include
248 bytes < 0x80 which might follow afterwards in that run. */
249 for (easy_sz = 0;
250 easy_sz < litlen && in[litofs + easy_sz] < 0x80;
251 easy_sz++)
252 ;
253 if (easy_sz)
254 {
255 if (oo + easy_sz >= out_len)
256 return 0;
257 memcpy(out + oo, in + litofs, easy_sz);
258 litofs += easy_sz;
259 oo += easy_sz;
260 litlen -= easy_sz;
261 if (!litlen)
262 break;
263 }
264 if (litlen <= 32)
265 {
266 if (oo + 1 + litlen >= out_len)
267 return 0;
268 out[oo++] = 0x80 | (litlen - 1);
269 while (litlen--)
270 out[oo++] = in[litofs++];
271 break;
272 }
273 else
274 {
275 /* Literal length > 32, so chunk it. */
276 if (oo + 1 + 32 >= out_len)
277 return 0;
278 out[oo++] = 0x80 | 31;
279 memcpy(out + oo, in + litofs, 32);
280 oo += 32;
281 litofs += 32;
282 litlen -= 32;
283 }
284 }
285 litofs = 0;
286 }
287
288 /* fprintf(stderr, "ref: %d @ %d\n", mlen, mofs); */
289
290 if (mlen >= 2 && mlen <= 9 && mofs < 1024)
291 {
292 if (oo + 2 >= out_len)
293 return 0;
294 out[oo++] = 0xa0 | ((mofs & 0x300) >> 5) | (mlen - 2);
295 out[oo++] = mofs & 0xff;
296 }
297 else if (mlen >= 10 && mlen <= 41 && mofs < 256)
298 {
299 if (oo + 2 >= out_len)
300 return 0;
301 out[oo++] = 0xc0 | (mlen - 10);
302 out[oo++] = mofs;
303 }
304 else if (mofs >= 65536)
305 {
306 assert(mlen >= 5 && mlen < 2048 + 5);
307 if (oo + 5 >= out_len)
308 return 0;
309 out[oo++] = 0xf8 | ((mlen - 5) >> 8);
310 out[oo++] = (mlen - 5) & 0xff;
311 out[oo++] = mofs & 0xff;
312 out[oo++] = (mofs >> 8) & 0xff;
313 out[oo++] = mofs >> 16;
314 }
315 else if (mlen >= 3 && mlen <= 18)
316 {
317 assert(mofs < 65536);
318 if (oo + 3 >= out_len)
319 return 0;
320 out[oo++] = 0xe0 | (mlen - 3);
321 out[oo++] = mofs & 0xff;
322 out[oo++] = mofs >> 8;
323 }
324 else
325 {
326 assert(mlen >= 19 && mlen <= 4095 + 19 && mofs < 65536);
327 if (oo + 4 >= out_len)
328 return 0;
329 out[oo++] = 0xf0 | ((mlen - 19) >> 8);
330 out[oo++] = (mlen - 19) & 0xff;
331 out[oo++] = mofs & 0xff;
332 out[oo++] = mofs >> 8;
333 }
334 /* Insert the hashes for the compressed run [io..io+mlen-1].
335 For [io] we have it already done at the start of the loop.
336 So it's from [io+1..io+mlen-1], and we need three chars per
337 hash, so the accessed characters will be [io+1..io+mlen-1+2],
338 ergo io+mlen+1 < in_len. */
339 mlen--;
340 io++;
341 while (mlen--)
342 {
343 if (io + 2 < in_len)
344 {
345 unsigned int hval =
346 in[io] | in[io + 1] << 8 | in[io + 2] << 16;
347 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
348 hval = hval & (HS - 1);
349 hnext[io] = htab[hval];
350 htab[hval] = io;
351 }
352 io++;
353 };
354 }
355 }
356 /* We might have some characters left. */
357 if (io < in_len && !litofs)
358 litofs = io + 1;
359 io = in_len;
360 if (litofs)
361 {
362 unsigned litlen;
363 litofs--;
364 litlen = io - litofs;
365 /* fprintf(stderr, "lit: %d\n", litlen); */
366 while (litlen)
367 {
368 unsigned int easy_sz;
369 /* Emit everything we can as self-describers. As soon as we hit a
370 byte we can't emit as such we're going to emit a length
371 descriptor anyway, so we can as well include bytes < 0x80 which
372 might follow afterwards in that run. */
373 for (easy_sz = 0; easy_sz < litlen && in[litofs + easy_sz] < 0x80;
374 easy_sz++)
375 ;
376 if (easy_sz)
377 {
378 if (oo + easy_sz >= out_len)
379 return 0;
380 memcpy(out + oo, in + litofs, easy_sz);
381 litofs += easy_sz;
382 oo += easy_sz;
383 litlen -= easy_sz;
384 if (!litlen)
385 break;
386 }
387 if (litlen <= 32)
388 {
389 if (oo + 1 + litlen >= out_len)
390 return 0;
391 out[oo++] = 0x80 | (litlen - 1);
392 while (litlen--)
393 out[oo++] = in[litofs++];
394 break;
395 }
396 else
397 {
398 /* Literal length > 32, so chunk it. */
399 if (oo + 1 + 32 >= out_len)
400 return 0;
401 out[oo++] = 0x80 | 31;
402 memcpy(out + oo, in + litofs, 32);
403 oo += 32;
404 litofs += 32;
405 litlen -= 32;
406 }
407 }
408 }
409 return oo;
410 }
411
412 static unsigned int
unchecked_decompress_buf(const unsigned char * in,unsigned int in_len,unsigned char * out,unsigned int out_len)413 unchecked_decompress_buf(const unsigned char *in, unsigned int in_len,
414 unsigned char *out,
415 unsigned int out_len __attribute__((unused)))
416 {
417 unsigned char *orig_out = out;
418 const unsigned char *in_end = in + in_len;
419 while (in < in_end)
420 {
421 unsigned int first = *in++;
422 int o;
423 switch (first >> 4)
424 {
425 default:
426 /* This default case can't happen, but GCCs VRP is not strong
427 enough to see this, so make this explicitely not fall to
428 the end of the switch, so that we don't have to initialize
429 o above. */
430 continue;
431 case 0: case 1:
432 case 2: case 3:
433 case 4: case 5:
434 case 6: case 7:
435 /* a 0LLLLLLL */
436 /* fprintf (stderr, "lit: 1\n"); */
437 *out++ = first;
438 continue;
439 case 8: case 9:
440 /* b 100lllll <l+1 bytes> */
441 {
442 unsigned int l = first & 31;
443 /* fprintf (stderr, "lit: %d\n", l); */
444 do
445 *out++ = *in++;
446 while (l--);
447 continue;
448 }
449 case 10: case 11:
450 /* c 101oolll <8o> */
451 {
452 o = first & (3 << 3);
453 o = (o << 5) | *in++;
454 first = (first & 7) + 2;
455 break;
456 }
457 case 12: case 13:
458 /* d 110lllll <8o> */
459 {
460 o = *in++;
461 first = (first & 31) + 10;
462 break;
463 }
464 case 14:
465 /* e 1110llll <8o> <8o> */
466 {
467 o = in[0] | (in[1] << 8);
468 in += 2;
469 first = first & 31;
470 first += 3;
471 break;
472 }
473 case 15:
474 /* f1 1111llll <8o> <8o> <8l> */
475 /* f2 11110lll <8o> <8o> <8l> */
476 /* g 11111lll <8o> <8o> <8o> <8l> */
477 {
478 first = first & 15;
479 if (first >= 8)
480 {
481 first = (((first - 8) << 8) | in[0]) + 5;
482 o = in[1] | (in[2] << 8) | (in[3] << 16);
483 in += 4;
484 }
485 else
486 {
487 first = ((first << 8) | in[0]) + 19;
488 o = in[1] | (in[2] << 8);
489 in += 3;
490 }
491 break;
492 }
493 }
494 /* fprintf(stderr, "ref: %d @ %d\n", first, o); */
495 o++;
496 o = -o;
497 #if 0
498 /* We know that first will not be zero, and this loop structure is
499 better optimizable. */
500 do
501 {
502 *out = *(out - o);
503 out++;
504 }
505 while (--first);
506 #else
507 switch (first)
508 {
509 case 18: *out = *(out + o); out++;
510 case 17: *out = *(out + o); out++;
511 case 16: *out = *(out + o); out++;
512 case 15: *out = *(out + o); out++;
513 case 14: *out = *(out + o); out++;
514 case 13: *out = *(out + o); out++;
515 case 12: *out = *(out + o); out++;
516 case 11: *out = *(out + o); out++;
517 case 10: *out = *(out + o); out++;
518 case 9: *out = *(out + o); out++;
519 case 8: *out = *(out + o); out++;
520 case 7: *out = *(out + o); out++;
521 case 6: *out = *(out + o); out++;
522 case 5: *out = *(out + o); out++;
523 case 4: *out = *(out + o); out++;
524 case 3: *out = *(out + o); out++;
525 case 2: *out = *(out + o); out++;
526 case 1: *out = *(out + o); out++;
527 case 0: break;
528 default:
529 /* Duff duff :-) */
530 switch (first & 15)
531 {
532 do
533 {
534 case 0: *out = *(out + o); out++;
535 case 15: *out = *(out + o); out++;
536 case 14: *out = *(out + o); out++;
537 case 13: *out = *(out + o); out++;
538 case 12: *out = *(out + o); out++;
539 case 11: *out = *(out + o); out++;
540 case 10: *out = *(out + o); out++;
541 case 9: *out = *(out + o); out++;
542 case 8: *out = *(out + o); out++;
543 case 7: *out = *(out + o); out++;
544 case 6: *out = *(out + o); out++;
545 case 5: *out = *(out + o); out++;
546 case 4: *out = *(out + o); out++;
547 case 3: *out = *(out + o); out++;
548 case 2: *out = *(out + o); out++;
549 case 1: *out = *(out + o); out++;
550 }
551 while ((int)(first -= 16) > 0);
552 }
553 break;
554 }
555 #endif
556 }
557 return out - orig_out;
558 }
559
560 /**********************************************************************/
561
repopagestore_init(Repopagestore * store)562 void repopagestore_init(Repopagestore *store)
563 {
564 memset(store, 0, sizeof(*store));
565 store->pagefd = -1;
566 }
567
repopagestore_free(Repopagestore * store)568 void repopagestore_free(Repopagestore *store)
569 {
570 store->blob_store = solv_free(store->blob_store);
571 store->file_pages = solv_free(store->file_pages);
572 store->mapped_at = solv_free(store->mapped_at);
573 store->mapped = solv_free(store->mapped);
574 if (store->pagefd != -1)
575 close(store->pagefd);
576 store->pagefd = -1;
577 }
578
579
580 /**********************************************************************/
581
582 unsigned char *
repopagestore_load_page_range(Repopagestore * store,unsigned int pstart,unsigned int pend)583 repopagestore_load_page_range(Repopagestore *store, unsigned int pstart, unsigned int pend)
584 {
585 /* Make sure all pages from PSTART to PEND (inclusive) are loaded,
586 and are consecutive. Return a pointer to the mapping of PSTART. */
587 unsigned char buf[REPOPAGE_BLOBSIZE];
588 unsigned int i, best, pnum;
589
590 if (pstart == pend)
591 {
592 /* Quick check in case the requested page is already mapped */
593 if (store->mapped_at[pstart] != -1)
594 return store->blob_store + store->mapped_at[pstart];
595 }
596 else
597 {
598 /* Quick check in case all pages are already mapped and consecutive. */
599 for (pnum = pstart; pnum <= pend; pnum++)
600 if (store->mapped_at[pnum] == -1
601 || (pnum > pstart
602 && store->mapped_at[pnum]
603 != store->mapped_at[pnum-1] + REPOPAGE_BLOBSIZE))
604 break;
605 if (pnum > pend)
606 return store->blob_store + store->mapped_at[pstart];
607 }
608
609 if (store->pagefd == -1 || !store->file_pages)
610 return 0; /* no backing file */
611
612 #ifdef DEBUG_PAGING
613 fprintf(stderr, "PAGE: want %d pages starting at %d\n", pend - pstart + 1, pstart);
614 #endif
615
616 /* Ensure that we can map the numbers of pages we need at all. */
617 if (pend - pstart + 1 > store->nmapped)
618 {
619 unsigned int oldcan = store->nmapped;
620 store->nmapped = pend - pstart + 1;
621 if (store->nmapped < 4)
622 store->nmapped = 4;
623 store->mapped = solv_realloc2(store->mapped, store->nmapped, sizeof(store->mapped[0]));
624 for (i = oldcan; i < store->nmapped; i++)
625 store->mapped[i] = -1;
626 store->blob_store = solv_realloc2(store->blob_store, store->nmapped, REPOPAGE_BLOBSIZE);
627 #ifdef DEBUG_PAGING
628 fprintf(stderr, "PAGE: can map %d pages\n", store->nmapped);
629 #endif
630 }
631
632 if (store->mapped_at[pstart] != -1)
633 {
634 /* assume forward search */
635 best = store->mapped_at[pstart] / REPOPAGE_BLOBSIZE;
636 if (best + (pend - pstart) >= store->nmapped)
637 best = 0;
638 }
639 else if (store->mapped_at[pend] != -1)
640 {
641 /* assume backward search */
642 best = store->mapped_at[pend] / REPOPAGE_BLOBSIZE;
643 if (best < pend - pstart)
644 best = store->nmapped - 1;
645 best -= pend - pstart;
646 }
647 else
648 {
649 /* choose some "random" location to avoid thrashing */
650 best = (pstart + store->rr_counter++) % (store->nmapped - pend + pstart);
651 }
652
653 /* So we want to map our pages from [best] to [best+pend-pstart].
654 Use a very simple strategy, which doesn't make the best use of
655 our resources, but works. Throw away all pages in that range
656 (even ours) then copy around ours or read them in. */
657 for (i = best, pnum = pstart; pnum <= pend; i++, pnum++)
658 {
659 unsigned int pnum_mapped_at;
660 unsigned int oldpnum = store->mapped[i];
661 if (oldpnum != -1)
662 {
663 if (oldpnum == pnum)
664 continue; /* already have the correct page */
665 /* Evict this page. */
666 #ifdef DEBUG_PAGING
667 fprintf(stderr, "PAGE: evict page %d from %d\n", oldpnum, i);
668 #endif
669 store->mapped[i] = -1;
670 store->mapped_at[oldpnum] = -1;
671 }
672 /* check if we can copy the correct content (before it gets evicted) */
673 pnum_mapped_at = store->mapped_at[pnum];
674 if (pnum_mapped_at != -1 && pnum_mapped_at != i * REPOPAGE_BLOBSIZE)
675 {
676 void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
677 #ifdef DEBUG_PAGING
678 fprintf(stderr, "PAGECOPY: %d from %d to %d\n", pnum, pnum_mapped_at / REPOPAGE_BLOBSIZE, i);
679 #endif
680 memcpy(dest, store->blob_store + pnum_mapped_at, REPOPAGE_BLOBSIZE);
681 store->mapped[pnum_mapped_at / REPOPAGE_BLOBSIZE] = -1;
682 store->mapped[i] = pnum;
683 store->mapped_at[pnum] = i * REPOPAGE_BLOBSIZE;
684 }
685 }
686
687 /* Everything is free now. Read in or copy the pages we want. */
688 for (i = best, pnum = pstart; pnum <= pend; i++, pnum++)
689 {
690 void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
691 if (store->mapped_at[pnum] != -1)
692 {
693 unsigned int pnum_mapped_at = store->mapped_at[pnum];
694 if (pnum_mapped_at != i * REPOPAGE_BLOBSIZE)
695 {
696 #ifdef DEBUG_PAGING
697 fprintf(stderr, "PAGECOPY: %d from %d to %d\n", pnum, pnum_mapped_at / REPOPAGE_BLOBSIZE, i);
698 #endif
699 /* Still mapped somewhere else, so just copy it from there. */
700 memcpy(dest, store->blob_store + pnum_mapped_at, REPOPAGE_BLOBSIZE);
701 store->mapped[pnum_mapped_at / REPOPAGE_BLOBSIZE] = -1;
702 }
703 }
704 else
705 {
706 Attrblobpage *p = store->file_pages + pnum;
707 unsigned int in_len = p->page_size;
708 unsigned int compressed = in_len & 1;
709 in_len >>= 1;
710 #ifdef DEBUG_PAGING
711 fprintf(stderr, "PAGEIN: %d to %d", pnum, i);
712 #endif
713 #ifndef _WIN32
714 if (pread(store->pagefd, compressed ? buf : dest, in_len, store->file_offset + p->page_offset) != in_len)
715 {
716 perror("mapping pread");
717 return 0;
718 }
719 #else
720 DWORD read_len;
721 OVERLAPPED ovlp = {0};
722 ovlp.Offset = store->file_offset + p->page_offset;
723 if (!ReadFile((HANDLE) _get_osfhandle(store->pagefd), compressed ? buf : dest, in_len, &read_len, &ovlp) || read_len != in_len)
724 {
725 perror("mapping ReadFile");
726 return 0;
727 }
728 #endif
729 if (compressed)
730 {
731 unsigned int out_len;
732 out_len = unchecked_decompress_buf(buf, in_len, dest, REPOPAGE_BLOBSIZE);
733 if (out_len != REPOPAGE_BLOBSIZE && pnum < store->num_pages - 1)
734 {
735 #ifdef DEBUG_PAGING
736 fprintf(stderr, "can't decompress\n");
737 #endif
738 return 0;
739 }
740 #ifdef DEBUG_PAGING
741 fprintf(stderr, " (expand %d to %d)", in_len, out_len);
742 #endif
743 }
744 #ifdef DEBUG_PAGING
745 fprintf(stderr, "\n");
746 #endif
747 }
748 store->mapped_at[pnum] = i * REPOPAGE_BLOBSIZE;
749 store->mapped[i] = pnum;
750 }
751 return store->blob_store + best * REPOPAGE_BLOBSIZE;
752 }
753
754 unsigned int
repopagestore_compress_page(unsigned char * page,unsigned int len,unsigned char * cpage,unsigned int max)755 repopagestore_compress_page(unsigned char *page, unsigned int len, unsigned char *cpage, unsigned int max)
756 {
757 return compress_buf(page, len, cpage, max);
758 }
759
760 #define SOLV_ERROR_EOF 3
761 #define SOLV_ERROR_CORRUPT 6
762
763 static inline unsigned int
read_u32(FILE * fp)764 read_u32(FILE *fp)
765 {
766 int c, i;
767 unsigned int x = 0;
768
769 for (i = 0; i < 4; i++)
770 {
771 c = getc(fp);
772 if (c == EOF)
773 return 0;
774 x = (x << 8) | c;
775 }
776 return x;
777 }
778
779 /* Try to either setup on-demand paging (using FP as backing
780 file), or in case that doesn't work (FP not seekable) slurps in
781 all pages and deactivates paging. */
782 int
repopagestore_read_or_setup_pages(Repopagestore * store,FILE * fp,unsigned int pagesz,unsigned int blobsz)783 repopagestore_read_or_setup_pages(Repopagestore *store, FILE *fp, unsigned int pagesz, unsigned int blobsz)
784 {
785 unsigned int npages;
786 unsigned int i;
787 unsigned int can_seek;
788 unsigned int cur_page_ofs;
789 unsigned char buf[REPOPAGE_BLOBSIZE];
790
791 if (pagesz != REPOPAGE_BLOBSIZE)
792 {
793 /* We could handle this by slurping in everything. */
794 return SOLV_ERROR_CORRUPT;
795 }
796 can_seek = 1;
797 if ((store->file_offset = ftell(fp)) < 0)
798 can_seek = 0;
799 clearerr(fp);
800 if (can_seek)
801 store->pagefd = dup(fileno(fp));
802 if (store->pagefd == -1)
803 can_seek = 0;
804 else
805 solv_setcloexec(store->pagefd, 1);
806
807 #ifdef DEBUG_PAGING
808 fprintf(stderr, "can %sseek\n", can_seek ? "" : "NOT ");
809 #endif
810 npages = (blobsz + REPOPAGE_BLOBSIZE - 1) / REPOPAGE_BLOBSIZE;
811
812 store->num_pages = npages;
813 store->mapped_at = solv_malloc2(npages, sizeof(*store->mapped_at));
814
815 /* If we can't seek on our input we have to slurp in everything.
816 * Otherwise set up file_pages containing offest/length of the
817 * pages */
818 if (can_seek)
819 store->file_pages = solv_malloc2(npages, sizeof(*store->file_pages));
820 else
821 store->blob_store = solv_malloc2(npages, REPOPAGE_BLOBSIZE);
822 cur_page_ofs = 0;
823 for (i = 0; i < npages; i++)
824 {
825 unsigned int in_len = read_u32(fp);
826 unsigned int compressed = in_len & 1;
827 in_len >>= 1;
828 #ifdef DEBUG_PAGING
829 fprintf(stderr, "page %d: len %d (%scompressed)\n",
830 i, in_len, compressed ? "" : "not ");
831 #endif
832 if (can_seek)
833 {
834 Attrblobpage *p = store->file_pages + i;
835 cur_page_ofs += 4;
836 store->mapped_at[i] = -1; /* not mapped yet */
837 p->page_offset = cur_page_ofs;
838 p->page_size = in_len * 2 + compressed;
839 if (fseek(fp, in_len, SEEK_CUR) < 0)
840 {
841 /* We can't fall back to non-seeking behaviour as we already
842 read over some data pages without storing them away. */
843 close(store->pagefd);
844 store->pagefd = -1;
845 return SOLV_ERROR_EOF;
846 }
847 cur_page_ofs += in_len;
848 }
849 else
850 {
851 unsigned int out_len;
852 void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
853 store->mapped_at[i] = i * REPOPAGE_BLOBSIZE;
854 /* We can't seek, so suck everything in. */
855 if (fread(compressed ? buf : dest, in_len, 1, fp) != 1)
856 {
857 perror("fread");
858 return SOLV_ERROR_EOF;
859 }
860 if (compressed)
861 {
862 out_len = unchecked_decompress_buf(buf, in_len, dest, REPOPAGE_BLOBSIZE);
863 if (out_len != REPOPAGE_BLOBSIZE && i < npages - 1)
864 {
865 return SOLV_ERROR_CORRUPT;
866 }
867 }
868 }
869 }
870 return 0;
871 }
872
873 void
repopagestore_disable_paging(Repopagestore * store)874 repopagestore_disable_paging(Repopagestore *store)
875 {
876 if (store->num_pages)
877 repopagestore_load_page_range(store, 0, store->num_pages - 1);
878 }
879
880 #ifdef STANDALONE
881
882 static void
transfer_file(FILE * from,FILE * to,int compress)883 transfer_file(FILE * from, FILE * to, int compress)
884 {
885 unsigned char inb[BLOCK_SIZE];
886 unsigned char outb[BLOCK_SIZE];
887 while (!feof (from) && !ferror (from))
888 {
889 unsigned int in_len, out_len;
890 if (compress)
891 {
892 in_len = fread(inb, 1, BLOCK_SIZE, from);
893 if (in_len)
894 {
895 unsigned char *b = outb;
896 out_len = compress_buf(inb, in_len, outb, sizeof (outb));
897 if (!out_len)
898 b = inb, out_len = in_len;
899 if (fwrite(&out_len, sizeof (out_len), 1, to) != 1)
900 {
901 perror("write size");
902 exit (1);
903 }
904 if (fwrite(b, out_len, 1, to) != 1)
905 {
906 perror("write data");
907 exit (1);
908 }
909 }
910 }
911 else
912 {
913 if (fread(&in_len, sizeof(in_len), 1, from) != 1)
914 {
915 if (feof(from))
916 return;
917 perror("can't read size");
918 exit(1);
919 }
920 if (fread(inb, in_len, 1, from) != 1)
921 {
922 perror("can't read data");
923 exit(1);
924 }
925 out_len =
926 unchecked_decompress_buf(inb, in_len, outb, sizeof(outb));
927 if (fwrite(outb, out_len, 1, to) != 1)
928 {
929 perror("can't write output");
930 exit(1);
931 }
932 }
933 }
934 }
935
936 /* Just for benchmarking purposes. */
937 static void
dumb_memcpy(void * dest,const void * src,unsigned int len)938 dumb_memcpy(void *dest, const void *src, unsigned int len)
939 {
940 char *d = dest;
941 const char *s = src;
942 while (len--)
943 *d++ = *s++;
944 }
945
946 static void
benchmark(FILE * from)947 benchmark(FILE * from)
948 {
949 unsigned char inb[BLOCK_SIZE];
950 unsigned char outb[BLOCK_SIZE];
951 unsigned int in_len = fread(inb, 1, BLOCK_SIZE, from);
952 unsigned int out_len;
953 if (!in_len)
954 {
955 perror("can't read from input");
956 exit(1);
957 }
958
959 unsigned int calib_loop;
960 unsigned int per_loop;
961 unsigned int i, j;
962 clock_t start, end;
963 float seconds;
964
965 #if 0
966 calib_loop = 1;
967 per_loop = 0;
968 start = clock();
969 while ((clock() - start) < CLOCKS_PER_SEC / 4)
970 {
971 calib_loop *= 2;
972 for (i = 0; i < calib_loop; i++)
973 dumb_memcpy(outb, inb, in_len);
974 per_loop += calib_loop;
975 }
976
977 fprintf(stderr, "memcpy:\nCalibrated to %d iterations per loop\n",
978 per_loop);
979
980 start = clock();
981 for (i = 0; i < 10; i++)
982 for (j = 0; j < per_loop; j++)
983 dumb_memcpy(outb, inb, in_len);
984 end = clock();
985 seconds = (end - start) / (float) CLOCKS_PER_SEC;
986 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
987 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
988 #endif
989
990 calib_loop = 1;
991 per_loop = 0;
992 start = clock();
993 while ((clock() - start) < CLOCKS_PER_SEC / 4)
994 {
995 calib_loop *= 2;
996 for (i = 0; i < calib_loop; i++)
997 compress_buf(inb, in_len, outb, sizeof(outb));
998 per_loop += calib_loop;
999 }
1000
1001 fprintf(stderr, "compression:\nCalibrated to %d iterations per loop\n",
1002 per_loop);
1003
1004 start = clock();
1005 for (i = 0; i < 10; i++)
1006 for (j = 0; j < per_loop; j++)
1007 compress_buf(inb, in_len, outb, sizeof(outb));
1008 end = clock();
1009 seconds = (end - start) / (float) CLOCKS_PER_SEC;
1010 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
1011 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
1012
1013 out_len = compress_buf(inb, in_len, outb, sizeof(outb));
1014
1015 calib_loop = 1;
1016 per_loop = 0;
1017 start = clock();
1018 while ((clock() - start) < CLOCKS_PER_SEC / 4)
1019 {
1020 calib_loop *= 2;
1021 for (i = 0; i < calib_loop; i++)
1022 unchecked_decompress_buf(outb, out_len, inb, sizeof(inb));
1023 per_loop += calib_loop;
1024 }
1025
1026 fprintf(stderr, "decompression:\nCalibrated to %d iterations per loop\n",
1027 per_loop);
1028
1029 start = clock();
1030 for (i = 0; i < 10; i++)
1031 for (j = 0; j < per_loop; j++)
1032 unchecked_decompress_buf(outb, out_len, inb, sizeof(inb));
1033 end = clock();
1034 seconds = (end - start) / (float) CLOCKS_PER_SEC;
1035 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
1036 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
1037 }
1038
1039 int
main(int argc,char * argv[])1040 main(int argc, char *argv[])
1041 {
1042 int compress = 1;
1043 if (argc > 1 && !strcmp(argv[1], "-d"))
1044 compress = 0;
1045 if (argc > 1 && !strcmp(argv[1], "-b"))
1046 benchmark(stdin);
1047 else
1048 transfer_file(stdin, stdout, compress);
1049 return 0;
1050 }
1051
1052 #endif
1053
1054