satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007-2008, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * repopage.c 00010 * 00011 * Paging and compression functions for the vertical repository data. 00012 * Vertical data is grouped by key, normal data is grouped by solvable. 00013 * This makes searching for a string in vertical data fast as there's 00014 * no need to skip over data if keys we're not interested in. 00015 * 00016 * The vertical data is split into pages, each page is compressed with a fast 00017 * compression algorithm. These pages are read in on demand, not recently used 00018 * pages automatically get dropped. 00019 */ 00020 00021 #define _XOPEN_SOURCE 500 00022 00023 #include <sys/types.h> 00024 #include <stdio.h> 00025 #include <stdlib.h> 00026 #include <string.h> 00027 #include <unistd.h> 00028 #include <assert.h> 00029 #include <fcntl.h> 00030 #include <time.h> 00031 00032 #include "repo.h" 00033 #include "repopage.h" 00034 00035 00036 00037 #define BLOCK_SIZE (65536*1) 00038 #if BLOCK_SIZE <= 65536 00039 typedef __uint16_t Ref; 00040 #else 00041 typedef __uint32_t Ref; 00042 #endif 00043 00044 /* 00045 The format is tailored for fast decompression (i.e. only byte based), 00046 and skewed to ASCII content (highest bit often not set): 00047 00048 a 0LLLLLLL 00049 - self-describing ASCII character hex L 00050 b 100lllll <l+1 bytes> 00051 - literal run of length l+1 00052 c 101oolll <8o> 00053 - back ref of length l+2, at offset -(o+1) (o < 1 << 10) 00054 d 110lllll <8o> 00055 - back ref of length l+2+8, at offset -(o+1) (o < 1 << 8) 00056 e 1110llll <8o> <8o> 00057 - back ref of length l+3, at offset -(o+1) (o < 1 << 16) 00058 f1 1111llll <8l> <8o> <8o> 00059 - back ref, length l+19 (l < 1<<12), offset -(o+1) (o < 1<<16) 00060 f2 11110lll <8l> <8o> <8o> 00061 - back ref, length l+19 (l < 1<<11), offset -(o+1) (o < 1<<16) 00062 g 11111lll <8l> <8o> <8o> <8o> 00063 - back ref, length l+5 (l < 1<<11), offset -(o+1) (o < 1<<24) 00064 00065 Generally for a literal of length L we need L+1 bytes, hence it is 00066 better to encode also very short backrefs (2 chars) as backrefs if 00067 their offset is small, as that only needs two bytes. Except if we 00068 already have a literal run, in that case it's better to append there, 00069 instead of breaking it for a backref. So given a potential backref 00070 at offset O, length L the strategy is as follows: 00071 00072 L < 2 : encode as 1-literal 00073 L == 2, O > 1024 : encode as 1-literal 00074 L == 2, have already literals: encode as 1-literal 00075 O = O - 1 00076 L >= 2, L <= 9, O < 1024 : encode as c 00077 L >= 10, L <= 41, O < 256 : encode as d 00078 else we have either O >= 1024, or L >= 42: 00079 L < 3 : encode as 1-literal 00080 L >= 3, L <= 18, O < 65536 : encode as e 00081 L >= 19, L <= 4095+18, O < 65536 : encode as f 00082 else we have either L >= 4096+18 or O >= 65536. 00083 O >= 65536: encode as 1-literal, too bad 00084 (with the current block size this can't happen) 00085 L >= 4096+18, so reduce to 4095+18 : encode as f 00086 */ 00087 00088 00089 static unsigned int 00090 compress_buf(const unsigned char *in, unsigned int in_len, 00091 unsigned char *out, unsigned int out_len) 00092 { 00093 unsigned int oo = 0; //out-offset 00094 unsigned int io = 0; //in-offset 00095 #define HS (65536) 00096 Ref htab[HS]; 00097 Ref hnext[BLOCK_SIZE]; 00098 memset(htab, -1, sizeof (htab)); 00099 memset(hnext, -1, sizeof (hnext)); 00100 unsigned int litofs = 0; 00101 while (io + 2 < in_len) 00102 { 00103 /* Search for a match of the string starting at IN, we have at 00104 least three characters. */ 00105 unsigned int hval = in[io] | in[io + 1] << 8 | in[io + 2] << 16; 00106 unsigned int try, mlen, mofs, tries; 00107 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5; 00108 hval = hval & (HS - 1); 00109 try = htab[hval]; 00110 hnext[io] = htab[hval]; 00111 htab[hval] = io; 00112 mlen = 0; 00113 mofs = 0; 00114 00115 for (tries = 0; try != -1 && tries < 12; tries++) 00116 { 00117 if (try < io 00118 && in[try] == in[io] && in[try + 1] == in[io + 1]) 00119 { 00120 mlen = 2; 00121 mofs = (io - try) - 1; 00122 break; 00123 } 00124 try = hnext[try]; 00125 } 00126 for (; try != -1 && tries < 12; tries++) 00127 { 00128 //assert(mlen >= 2); 00129 //assert(io + mlen < in_len); 00130 /* Try a match starting from [io] with the strings at [try]. 00131 That's only sensible if TRY actually is before IO (can happen 00132 with uninit hash table). If we have a previous match already 00133 we're only going to take the new one if it's longer, hence 00134 check the potentially last character. */ 00135 if (try < io && in[try + mlen] == in[io + mlen]) 00136 { 00137 unsigned int this_len, this_ofs; 00138 if (memcmp(in + try, in + io, mlen)) 00139 goto no_match; 00140 this_len = mlen + 1; 00141 /* Now try extending the match by more characters. */ 00142 for (; 00143 io + this_len < in_len 00144 && in[try + this_len] == in[io + this_len]; this_len++) 00145 ; 00146 #if 0 00147 unsigned int testi; 00148 for (testi = 0; testi < this_len; testi++) 00149 assert(in[try + testi] == in[io + testi]); 00150 #endif 00151 this_ofs = (io - try) - 1; 00152 /*if (this_ofs > 65535) 00153 goto no_match; */ 00154 #if 0 00155 assert(this_len >= 2); 00156 assert(this_len >= mlen); 00157 assert(this_len > mlen || (this_len == mlen && this_ofs > mofs)); 00158 #endif 00159 mlen = this_len, mofs = this_ofs; 00160 /* If our match extends up to the end of input, no next 00161 match can become better. This is not just an 00162 optimization, it establishes a loop invariant 00163 (io + mlen < in_len). */ 00164 if (io + mlen >= in_len) 00165 goto match_done; 00166 } 00167 no_match: 00168 try = hnext[try]; 00169 /*if (io - try - 1 >= 65536) 00170 break;*/ 00171 } 00172 00173 match_done: 00174 if (mlen) 00175 { 00176 /*fprintf(stderr, "%d %d\n", mlen, mofs);*/ 00177 if (mlen == 2 && (litofs || mofs >= 1024)) 00178 mlen = 0; 00179 /*else if (mofs >= 65536) 00180 mlen = 0;*/ 00181 else if (mofs >= 65536) 00182 { 00183 if (mlen >= 2048 + 5) 00184 mlen = 2047 + 5; 00185 else if (mlen < 5) 00186 mlen = 0; 00187 } 00188 else if (mlen < 3) 00189 mlen = 0; 00190 /*else if (mlen >= 4096 + 19) 00191 mlen = 4095 + 19;*/ 00192 else if (mlen >= 2048 + 19) 00193 mlen = 2047 + 19; 00194 /* Skip this match if the next character would deliver a better one, 00195 but only do this if we have the chance to really extend the 00196 length (i.e. our current length isn't yet the (conservative) 00197 maximum). */ 00198 if (mlen && mlen < (2048 + 5) && io + 3 < in_len) 00199 { 00200 unsigned int hval = 00201 in[io + 1] | in[io + 2] << 8 | in[io + 3] << 16; 00202 unsigned int try; 00203 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5; 00204 hval = hval & (HS - 1); 00205 try = htab[hval]; 00206 if (try < io + 1 00207 && in[try] == in[io + 1] && in[try + 1] == in[io + 2]) 00208 { 00209 unsigned int this_len; 00210 this_len = 2; 00211 for (; 00212 io + 1 + this_len < in_len 00213 && in[try + this_len] == in[io + 1 + this_len]; 00214 this_len++) 00215 ; 00216 if (this_len >= mlen) 00217 mlen = 0; 00218 } 00219 } 00220 } 00221 if (!mlen) 00222 { 00223 if (!litofs) 00224 litofs = io + 1; 00225 io++; 00226 } 00227 else 00228 { 00229 if (litofs) 00230 { 00231 litofs--; 00232 unsigned litlen = io - litofs; 00233 //fprintf(stderr, "lit: %d\n", litlen); 00234 while (litlen) 00235 { 00236 unsigned int easy_sz; 00237 /* Emit everything we can as self-describers. As soon as 00238 we hit a byte we can't emit as such we're going to emit 00239 a length descriptor anyway, so we can as well include 00240 bytes < 0x80 which might follow afterwards in that run. */ 00241 for (easy_sz = 0; 00242 easy_sz < litlen && in[litofs + easy_sz] < 0x80; 00243 easy_sz++) 00244 ; 00245 if (easy_sz) 00246 { 00247 if (oo + easy_sz >= out_len) 00248 return 0; 00249 memcpy(out + oo, in + litofs, easy_sz); 00250 litofs += easy_sz; 00251 oo += easy_sz; 00252 litlen -= easy_sz; 00253 if (!litlen) 00254 break; 00255 } 00256 if (litlen <= 32) 00257 { 00258 if (oo + 1 + litlen >= out_len) 00259 return 0; 00260 out[oo++] = 0x80 | (litlen - 1); 00261 while (litlen--) 00262 out[oo++] = in[litofs++]; 00263 break; 00264 } 00265 else 00266 { 00267 /* Literal length > 32, so chunk it. */ 00268 if (oo + 1 + 32 >= out_len) 00269 return 0; 00270 out[oo++] = 0x80 | 31; 00271 memcpy(out + oo, in + litofs, 32); 00272 oo += 32; 00273 litofs += 32; 00274 litlen -= 32; 00275 } 00276 } 00277 litofs = 0; 00278 } 00279 00280 //fprintf(stderr, "ref: %d @ %d\n", mlen, mofs); 00281 00282 if (mlen >= 2 && mlen <= 9 && mofs < 1024) 00283 { 00284 if (oo + 2 >= out_len) 00285 return 0; 00286 out[oo++] = 0xa0 | ((mofs & 0x300) >> 5) | (mlen - 2); 00287 out[oo++] = mofs & 0xff; 00288 } 00289 else if (mlen >= 10 && mlen <= 41 && mofs < 256) 00290 { 00291 if (oo + 2 >= out_len) 00292 return 0; 00293 out[oo++] = 0xc0 | (mlen - 10); 00294 out[oo++] = mofs; 00295 } 00296 else if (mofs >= 65536) 00297 { 00298 assert(mlen >= 5 && mlen < 2048 + 5); 00299 if (oo + 5 >= out_len) 00300 return 0; 00301 out[oo++] = 0xf8 | ((mlen - 5) >> 8); 00302 out[oo++] = (mlen - 5) & 0xff; 00303 out[oo++] = mofs & 0xff; 00304 out[oo++] = (mofs >> 8) & 0xff; 00305 out[oo++] = mofs >> 16; 00306 } 00307 else if (mlen >= 3 && mlen <= 18) 00308 { 00309 assert(mofs < 65536); 00310 if (oo + 3 >= out_len) 00311 return 0; 00312 out[oo++] = 0xe0 | (mlen - 3); 00313 out[oo++] = mofs & 0xff; 00314 out[oo++] = mofs >> 8; 00315 } 00316 else 00317 { 00318 assert(mlen >= 19 && mlen <= 4095 + 19 && mofs < 65536); 00319 if (oo + 4 >= out_len) 00320 return 0; 00321 out[oo++] = 0xf0 | ((mlen - 19) >> 8); 00322 out[oo++] = (mlen - 19) & 0xff; 00323 out[oo++] = mofs & 0xff; 00324 out[oo++] = mofs >> 8; 00325 } 00326 /* Insert the hashes for the compressed run [io..io+mlen-1]. 00327 For [io] we have it already done at the start of the loop. 00328 So it's from [io+1..io+mlen-1], and we need three chars per 00329 hash, so the accessed characters will be [io+1..io+mlen-1+2], 00330 ergo io+mlen+1 < in_len. */ 00331 mlen--; 00332 io++; 00333 while (mlen--) 00334 { 00335 if (io + 2 < in_len) 00336 { 00337 unsigned int hval = 00338 in[io] | in[io + 1] << 8 | in[io + 2] << 16; 00339 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5; 00340 hval = hval & (HS - 1); 00341 hnext[io] = htab[hval]; 00342 htab[hval] = io; 00343 } 00344 io++; 00345 }; 00346 } 00347 } 00348 /* We might have some characters left. */ 00349 if (io < in_len && !litofs) 00350 litofs = io + 1; 00351 io = in_len; 00352 if (litofs) 00353 { 00354 litofs--; 00355 unsigned litlen = io - litofs; 00356 //fprintf(stderr, "lit: %d\n", litlen); 00357 while (litlen) 00358 { 00359 unsigned int easy_sz; 00360 /* Emit everything we can as self-describers. As soon as we hit a 00361 byte we can't emit as such we're going to emit a length 00362 descriptor anyway, so we can as well include bytes < 0x80 which 00363 might follow afterwards in that run. */ 00364 for (easy_sz = 0; easy_sz < litlen && in[litofs + easy_sz] < 0x80; 00365 easy_sz++) 00366 ; 00367 if (easy_sz) 00368 { 00369 if (oo + easy_sz >= out_len) 00370 return 0; 00371 memcpy(out + oo, in + litofs, easy_sz); 00372 litofs += easy_sz; 00373 oo += easy_sz; 00374 litlen -= easy_sz; 00375 if (!litlen) 00376 break; 00377 } 00378 if (litlen <= 32) 00379 { 00380 if (oo + 1 + litlen >= out_len) 00381 return 0; 00382 out[oo++] = 0x80 | (litlen - 1); 00383 while (litlen--) 00384 out[oo++] = in[litofs++]; 00385 break; 00386 } 00387 else 00388 { 00389 /* Literal length > 32, so chunk it. */ 00390 if (oo + 1 + 32 >= out_len) 00391 return 0; 00392 out[oo++] = 0x80 | 31; 00393 memcpy(out + oo, in + litofs, 32); 00394 oo += 32; 00395 litofs += 32; 00396 litlen -= 32; 00397 } 00398 } 00399 litofs = 0; 00400 } 00401 return oo; 00402 } 00403 00404 static unsigned int 00405 unchecked_decompress_buf(const unsigned char *in, unsigned int in_len, 00406 unsigned char *out, 00407 unsigned int out_len __attribute__((unused))) 00408 { 00409 unsigned char *orig_out = out; 00410 const unsigned char *in_end = in + in_len; 00411 while (in < in_end) 00412 { 00413 unsigned int first = *in++; 00414 int o; 00415 switch (first >> 4) 00416 { 00417 default: 00418 /* This default case can't happen, but GCCs VRP is not strong 00419 enough to see this, so make this explicitely not fall to 00420 the end of the switch, so that we don't have to initialize 00421 o above. */ 00422 continue; 00423 case 0: case 1: 00424 case 2: case 3: 00425 case 4: case 5: 00426 case 6: case 7: 00427 //a 0LLLLLLL 00428 //fprintf (stderr, "lit: 1\n"); 00429 *out++ = first; 00430 continue; 00431 case 8: case 9: 00432 //b 100lllll <l+1 bytes> 00433 { 00434 unsigned int l = first & 31; 00435 //fprintf (stderr, "lit: %d\n", l); 00436 do 00437 *out++ = *in++; 00438 while (l--); 00439 continue; 00440 } 00441 case 10: case 11: 00442 //c 101oolll <8o> 00443 { 00444 o = first & (3 << 3); 00445 o = (o << 5) | *in++; 00446 first = (first & 7) + 2; 00447 break; 00448 } 00449 case 12: case 13: 00450 //d 110lllll <8o> 00451 { 00452 o = *in++; 00453 first = (first & 31) + 10; 00454 break; 00455 } 00456 case 14: 00457 // e 1110llll <8o> <8o> 00458 { 00459 o = in[0] | (in[1] << 8); 00460 in += 2; 00461 first = first & 31; 00462 first += 3; 00463 break; 00464 } 00465 case 15: 00466 //f1 1111llll <8o> <8o> <8l> 00467 //f2 11110lll <8o> <8o> <8l> 00468 // g 11111lll <8o> <8o> <8o> <8l> 00469 { 00470 first = first & 15; 00471 if (first >= 8) 00472 { 00473 first = (((first - 8) << 8) | in[0]) + 5; 00474 o = in[1] | (in[2] << 8) | (in[3] << 16); 00475 in += 4; 00476 } 00477 else 00478 { 00479 first = ((first << 8) | in[0]) + 19; 00480 o = in[1] | (in[2] << 8); 00481 in += 3; 00482 } 00483 break; 00484 } 00485 } 00486 //fprintf(stderr, "ref: %d @ %d\n", first, o); 00487 o++; 00488 o = -o; 00489 #if 0 00490 /* We know that first will not be zero, and this loop structure is 00491 better optimizable. */ 00492 do 00493 { 00494 *out = *(out - o); 00495 out++; 00496 } 00497 while (--first); 00498 #else 00499 switch (first) 00500 { 00501 case 18: *out = *(out + o); out++; 00502 case 17: *out = *(out + o); out++; 00503 case 16: *out = *(out + o); out++; 00504 case 15: *out = *(out + o); out++; 00505 case 14: *out = *(out + o); out++; 00506 case 13: *out = *(out + o); out++; 00507 case 12: *out = *(out + o); out++; 00508 case 11: *out = *(out + o); out++; 00509 case 10: *out = *(out + o); out++; 00510 case 9: *out = *(out + o); out++; 00511 case 8: *out = *(out + o); out++; 00512 case 7: *out = *(out + o); out++; 00513 case 6: *out = *(out + o); out++; 00514 case 5: *out = *(out + o); out++; 00515 case 4: *out = *(out + o); out++; 00516 case 3: *out = *(out + o); out++; 00517 case 2: *out = *(out + o); out++; 00518 case 1: *out = *(out + o); out++; 00519 case 0: break; 00520 default: 00521 /* Duff duff :-) */ 00522 switch (first & 15) 00523 { 00524 do 00525 { 00526 case 0: *out = *(out + o); out++; 00527 case 15: *out = *(out + o); out++; 00528 case 14: *out = *(out + o); out++; 00529 case 13: *out = *(out + o); out++; 00530 case 12: *out = *(out + o); out++; 00531 case 11: *out = *(out + o); out++; 00532 case 10: *out = *(out + o); out++; 00533 case 9: *out = *(out + o); out++; 00534 case 8: *out = *(out + o); out++; 00535 case 7: *out = *(out + o); out++; 00536 case 6: *out = *(out + o); out++; 00537 case 5: *out = *(out + o); out++; 00538 case 4: *out = *(out + o); out++; 00539 case 3: *out = *(out + o); out++; 00540 case 2: *out = *(out + o); out++; 00541 case 1: *out = *(out + o); out++; 00542 } 00543 while ((int)(first -= 16) > 0); 00544 } 00545 break; 00546 } 00547 #endif 00548 } 00549 return out - orig_out; 00550 } 00551 00552 /**********************************************************************/ 00553 00554 void repopagestore_init(Repopagestore *store) 00555 { 00556 memset(store, 0, sizeof(*store)); 00557 store->pagefd = -1; 00558 } 00559 00560 void repopagestore_free(Repopagestore *store) 00561 { 00562 sat_free(store->blob_store); 00563 sat_free(store->pages); 00564 sat_free(store->mapped); 00565 if (store->pagefd != -1) 00566 close(store->pagefd); 00567 } 00568 00569 00570 /**********************************************************************/ 00571 00572 unsigned char * 00573 repopagestore_load_page_range(Repopagestore *store, unsigned int pstart, unsigned int pend) 00574 { 00575 /* Make sure all pages from PSTART to PEND (inclusive) are loaded, 00576 and are consecutive. Return a pointer to the mapping of PSTART. */ 00577 unsigned char buf[BLOB_PAGESIZE]; 00578 unsigned int i; 00579 00580 /* Quick check in case all pages are there already and consecutive. */ 00581 for (i = pstart; i <= pend; i++) 00582 if (store->pages[i].mapped_at == -1 00583 || (i > pstart 00584 && store->pages[i].mapped_at 00585 != store->pages[i-1].mapped_at + BLOB_PAGESIZE)) 00586 break; 00587 if (i > pend) 00588 return store->blob_store + store->pages[pstart].mapped_at; 00589 00590 if (store->pagefd == -1) 00591 return 0; 00592 00593 /* Ensure that we can map the numbers of pages we need at all. */ 00594 if (pend - pstart + 1 > store->ncanmap) 00595 { 00596 unsigned int oldcan = store->ncanmap; 00597 store->ncanmap = pend - pstart + 1; 00598 if (store->ncanmap < 4) 00599 store->ncanmap = 4; 00600 store->mapped = sat_realloc2(store->mapped, store->ncanmap, sizeof(store->mapped[0])); 00601 memset(store->mapped + oldcan, 0, (store->ncanmap - oldcan) * sizeof (store->mapped[0])); 00602 store->blob_store = sat_realloc2(store->blob_store, store->ncanmap, BLOB_PAGESIZE); 00603 #ifdef DEBUG_PAGING 00604 fprintf(stderr, "PAGE: can map %d pages\n", store->ncanmap); 00605 #endif 00606 } 00607 00608 /* Now search for "cheap" space in our store. Space is cheap if it's either 00609 free (very cheap) or contains pages we search for anyway. */ 00610 00611 /* Setup cost array. */ 00612 unsigned int cost[store->ncanmap]; 00613 for (i = 0; i < store->ncanmap; i++) 00614 { 00615 unsigned int pnum = store->mapped[i]; 00616 if (pnum == 0) 00617 cost[i] = 0; 00618 else 00619 { 00620 pnum--; 00621 Attrblobpage *p = store->pages + pnum; 00622 assert(p->mapped_at != -1); 00623 if (pnum >= pstart && pnum <= pend) 00624 cost[i] = 1; 00625 else 00626 cost[i] = 3; 00627 } 00628 } 00629 00630 /* And search for cheapest space. */ 00631 unsigned int best_cost = -1; 00632 unsigned int best = 0; 00633 unsigned int same_cost = 0; 00634 for (i = 0; i + pend - pstart < store->ncanmap; i++) 00635 { 00636 unsigned int c = cost[i]; 00637 unsigned int j; 00638 for (j = 0; j < pend - pstart + 1; j++) 00639 c += cost[i+j]; 00640 if (c < best_cost) 00641 best_cost = c, best = i; 00642 else if (c == best_cost) 00643 same_cost++; 00644 /* A null cost won't become better. */ 00645 if (c == 0) 00646 break; 00647 } 00648 /* If all places have the same cost we would thrash on slot 0. Avoid 00649 this by doing a round-robin strategy in this case. */ 00650 if (same_cost == store->ncanmap - pend + pstart - 1) 00651 best = store->rr_counter++ % (store->ncanmap - pend + pstart); 00652 00653 /* So we want to map our pages from [best] to [best+pend-pstart]. 00654 Use a very simple strategy, which doesn't make the best use of 00655 our resources, but works. Throw away all pages in that range 00656 (even ours) then copy around ours (in case they were outside the 00657 range) or read them in. */ 00658 for (i = best; i < best + pend - pstart + 1; i++) 00659 { 00660 unsigned int pnum = store->mapped[i]; 00661 if (pnum-- 00662 /* If this page is exactly at the right place already, 00663 no need to evict it. */ 00664 && pnum != pstart + i - best) 00665 { 00666 /* Evict this page. */ 00667 #ifdef DEBUG_PAGING 00668 fprintf(stderr, "PAGE: evict page %d from %d\n", pnum, i); 00669 #endif 00670 cost[i] = 0; 00671 store->mapped[i] = 0; 00672 store->pages[pnum].mapped_at = -1; 00673 } 00674 } 00675 00676 /* Everything is free now. Read in the pages we want. */ 00677 for (i = pstart; i <= pend; i++) 00678 { 00679 Attrblobpage *p = store->pages + i; 00680 unsigned int pnum = i - pstart + best; 00681 void *dest = store->blob_store + pnum * BLOB_PAGESIZE; 00682 if (p->mapped_at != -1) 00683 { 00684 if (p->mapped_at != pnum * BLOB_PAGESIZE) 00685 { 00686 #ifdef DEBUG_PAGING 00687 fprintf(stderr, "PAGECOPY: %d to %d\n", i, pnum); 00688 #endif 00689 /* Still mapped somewhere else, so just copy it from there. */ 00690 memcpy(dest, store->blob_store + p->mapped_at, BLOB_PAGESIZE); 00691 store->mapped[p->mapped_at / BLOB_PAGESIZE] = 0; 00692 } 00693 } 00694 else 00695 { 00696 unsigned int in_len = p->file_size; 00697 unsigned int compressed = in_len & 1; 00698 in_len >>= 1; 00699 #ifdef DEBUG_PAGING 00700 fprintf(stderr, "PAGEIN: %d to %d", i, pnum); 00701 #endif 00702 if (pread(store->pagefd, compressed ? buf : dest, in_len, p->file_offset) != in_len) 00703 { 00704 perror("mapping pread"); 00705 return 0; 00706 } 00707 if (compressed) 00708 { 00709 unsigned int out_len; 00710 out_len = unchecked_decompress_buf(buf, in_len, 00711 dest, BLOB_PAGESIZE); 00712 if (out_len != BLOB_PAGESIZE && i < store->num_pages - 1) 00713 { 00714 #ifdef DEBUG_PAGING 00715 fprintf(stderr, "can't decompress\n"); 00716 #endif 00717 return 0; 00718 } 00719 #ifdef DEBUG_PAGING 00720 fprintf(stderr, " (expand %d to %d)", in_len, out_len); 00721 #endif 00722 } 00723 #ifdef DEBUG_PAGING 00724 fprintf(stderr, "\n"); 00725 #endif 00726 } 00727 p->mapped_at = pnum * BLOB_PAGESIZE; 00728 store->mapped[pnum] = i + 1; 00729 } 00730 return store->blob_store + best * BLOB_PAGESIZE; 00731 } 00732 00733 unsigned int 00734 repopagestore_compress_page(unsigned char *page, unsigned int len, unsigned char *cpage, unsigned int max) 00735 { 00736 return compress_buf(page, len, cpage, max); 00737 } 00738 00739 #define SOLV_ERROR_EOF 3 00740 #define SOLV_ERROR_CORRUPT 6 00741 00742 static inline unsigned int 00743 read_u32(FILE *fp) 00744 { 00745 int c, i; 00746 unsigned int x = 0; 00747 00748 for (i = 0; i < 4; i++) 00749 { 00750 c = getc(fp); 00751 if (c == EOF) 00752 return 0; 00753 x = (x << 8) | c; 00754 } 00755 return x; 00756 } 00757 00758 /* Try to either setup on-demand paging (using FP as backing 00759 file), or in case that doesn't work (FP not seekable) slurps in 00760 all pages and deactivates paging. */ 00761 int 00762 repopagestore_read_or_setup_pages(Repopagestore *store, FILE *fp, unsigned int pagesz, unsigned int blobsz) 00763 { 00764 unsigned int npages; 00765 unsigned int i; 00766 unsigned int can_seek; 00767 long cur_file_ofs; 00768 unsigned char buf[BLOB_PAGESIZE]; 00769 00770 if (pagesz != BLOB_PAGESIZE) 00771 { 00772 /* We could handle this by slurping in everything. */ 00773 return SOLV_ERROR_CORRUPT; 00774 } 00775 can_seek = 1; 00776 if ((cur_file_ofs = ftell(fp)) < 0) 00777 can_seek = 0; 00778 clearerr(fp); 00779 if (can_seek) 00780 store->pagefd = dup(fileno(fp)); 00781 if (store->pagefd == -1) 00782 can_seek = 0; 00783 else 00784 fcntl(store->pagefd, F_SETFD, FD_CLOEXEC); 00785 00786 #ifdef DEBUG_PAGING 00787 fprintf(stderr, "can %sseek\n", can_seek ? "" : "NOT "); 00788 #endif 00789 npages = (blobsz + BLOB_PAGESIZE - 1) / BLOB_PAGESIZE; 00790 00791 store->num_pages = npages; 00792 store->pages = sat_malloc2(npages, sizeof(store->pages[0])); 00793 00794 /* If we can't seek on our input we have to slurp in everything. */ 00795 if (!can_seek) 00796 store->blob_store = sat_malloc2(npages, BLOB_PAGESIZE); 00797 for (i = 0; i < npages; i++) 00798 { 00799 unsigned int in_len = read_u32(fp); 00800 unsigned int compressed = in_len & 1; 00801 Attrblobpage *p = store->pages + i; 00802 in_len >>= 1; 00803 #ifdef DEBUG_PAGING 00804 fprintf(stderr, "page %d: len %d (%scompressed)\n", 00805 i, in_len, compressed ? "" : "not "); 00806 #endif 00807 if (can_seek) 00808 { 00809 cur_file_ofs += 4; 00810 p->mapped_at = -1; 00811 p->file_offset = cur_file_ofs; 00812 p->file_size = in_len * 2 + compressed; 00813 if (fseek(fp, in_len, SEEK_CUR) < 0) 00814 { 00815 /* We can't fall back to non-seeking behaviour as we already 00816 read over some data pages without storing them away. */ 00817 close(store->pagefd); 00818 store->pagefd = -1; 00819 return SOLV_ERROR_EOF; 00820 } 00821 cur_file_ofs += in_len; 00822 } 00823 else 00824 { 00825 unsigned int out_len; 00826 void *dest = store->blob_store + i * BLOB_PAGESIZE; 00827 p->mapped_at = i * BLOB_PAGESIZE; 00828 p->file_offset = 0; 00829 p->file_size = 0; 00830 /* We can't seek, so suck everything in. */ 00831 if (fread(compressed ? buf : dest, in_len, 1, fp) != 1) 00832 { 00833 perror("fread"); 00834 return SOLV_ERROR_EOF; 00835 } 00836 if (compressed) 00837 { 00838 out_len = unchecked_decompress_buf(buf, in_len, dest, BLOB_PAGESIZE); 00839 if (out_len != BLOB_PAGESIZE && i < npages - 1) 00840 { 00841 return SOLV_ERROR_CORRUPT; 00842 } 00843 } 00844 } 00845 } 00846 return 0; 00847 } 00848 00849 void 00850 repopagestore_disable_paging(Repopagestore *store) 00851 { 00852 if (store->num_pages) 00853 repopagestore_load_page_range(store, 0, store->num_pages - 1); 00854 } 00855 00856 #ifdef STANDALONE 00857 00858 static void 00859 transfer_file(FILE * from, FILE * to, int compress) 00860 { 00861 unsigned char inb[BLOCK_SIZE]; 00862 unsigned char outb[BLOCK_SIZE]; 00863 while (!feof (from) && !ferror (from)) 00864 { 00865 unsigned int in_len, out_len; 00866 if (compress) 00867 { 00868 in_len = fread(inb, 1, BLOCK_SIZE, from); 00869 if (in_len) 00870 { 00871 unsigned char *b = outb; 00872 out_len = compress_buf(inb, in_len, outb, sizeof (outb)); 00873 if (!out_len) 00874 b = inb, out_len = in_len; 00875 if (fwrite(&out_len, sizeof (out_len), 1, to) != 1) 00876 { 00877 perror("write size"); 00878 exit (1); 00879 } 00880 if (fwrite(b, out_len, 1, to) != 1) 00881 { 00882 perror("write data"); 00883 exit (1); 00884 } 00885 } 00886 } 00887 else 00888 { 00889 if (fread(&in_len, sizeof(in_len), 1, from) != 1) 00890 { 00891 if (feof(from)) 00892 return; 00893 perror("can't read size"); 00894 exit(1); 00895 } 00896 if (fread(inb, in_len, 1, from) != 1) 00897 { 00898 perror("can't read data"); 00899 exit(1); 00900 } 00901 out_len = 00902 unchecked_decompress_buf(inb, in_len, outb, sizeof(outb)); 00903 if (fwrite(outb, out_len, 1, to) != 1) 00904 { 00905 perror("can't write output"); 00906 exit(1); 00907 } 00908 } 00909 } 00910 } 00911 00912 /* Just for benchmarking purposes. */ 00913 static void 00914 dumb_memcpy(void *dest, const void *src, unsigned int len) 00915 { 00916 char *d = dest; 00917 const char *s = src; 00918 while (len--) 00919 *d++ = *s++; 00920 } 00921 00922 static void 00923 benchmark(FILE * from) 00924 { 00925 unsigned char inb[BLOCK_SIZE]; 00926 unsigned char outb[BLOCK_SIZE]; 00927 unsigned int in_len = fread(inb, 1, BLOCK_SIZE, from); 00928 unsigned int out_len; 00929 if (!in_len) 00930 { 00931 perror("can't read from input"); 00932 exit(1); 00933 } 00934 00935 unsigned int calib_loop; 00936 unsigned int per_loop; 00937 unsigned int i, j; 00938 clock_t start, end; 00939 float seconds; 00940 00941 #if 0 00942 calib_loop = 1; 00943 per_loop = 0; 00944 start = clock(); 00945 while ((clock() - start) < CLOCKS_PER_SEC / 4) 00946 { 00947 calib_loop *= 2; 00948 for (i = 0; i < calib_loop; i++) 00949 dumb_memcpy(outb, inb, in_len); 00950 per_loop += calib_loop; 00951 } 00952 00953 fprintf(stderr, "memcpy:\nCalibrated to %d iterations per loop\n", 00954 per_loop); 00955 00956 start = clock(); 00957 for (i = 0; i < 10; i++) 00958 for (j = 0; j < per_loop; j++) 00959 dumb_memcpy(outb, inb, in_len); 00960 end = clock(); 00961 seconds = (end - start) / (float) CLOCKS_PER_SEC; 00962 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds, 00963 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds)); 00964 #endif 00965 00966 calib_loop = 1; 00967 per_loop = 0; 00968 start = clock(); 00969 while ((clock() - start) < CLOCKS_PER_SEC / 4) 00970 { 00971 calib_loop *= 2; 00972 for (i = 0; i < calib_loop; i++) 00973 compress_buf(inb, in_len, outb, sizeof(outb)); 00974 per_loop += calib_loop; 00975 } 00976 00977 fprintf(stderr, "compression:\nCalibrated to %d iterations per loop\n", 00978 per_loop); 00979 00980 start = clock(); 00981 for (i = 0; i < 10; i++) 00982 for (j = 0; j < per_loop; j++) 00983 compress_buf(inb, in_len, outb, sizeof(outb)); 00984 end = clock(); 00985 seconds = (end - start) / (float) CLOCKS_PER_SEC; 00986 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds, 00987 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds)); 00988 00989 out_len = compress_buf(inb, in_len, outb, sizeof(outb)); 00990 00991 calib_loop = 1; 00992 per_loop = 0; 00993 start = clock(); 00994 while ((clock() - start) < CLOCKS_PER_SEC / 4) 00995 { 00996 calib_loop *= 2; 00997 for (i = 0; i < calib_loop; i++) 00998 unchecked_decompress_buf(outb, out_len, inb, sizeof(inb)); 00999 per_loop += calib_loop; 01000 } 01001 01002 fprintf(stderr, "decompression:\nCalibrated to %d iterations per loop\n", 01003 per_loop); 01004 01005 start = clock(); 01006 for (i = 0; i < 10; i++) 01007 for (j = 0; j < per_loop; j++) 01008 unchecked_decompress_buf(outb, out_len, inb, sizeof(inb)); 01009 end = clock(); 01010 seconds = (end - start) / (float) CLOCKS_PER_SEC; 01011 fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds, 01012 ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds)); 01013 } 01014 01015 int 01016 main(int argc, char *argv[]) 01017 { 01018 int compress = 1; 01019 if (argc > 1 && !strcmp(argv[1], "-d")) 01020 compress = 0; 01021 if (argc > 1 && !strcmp(argv[1], "-b")) 01022 benchmark(stdin); 01023 else 01024 transfer_file(stdin, stdout, compress); 01025 return 0; 01026 } 01027 01028 #endif 01029