src/repopage.c

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