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