src/repopage.c

   1 /*
   2  * Copyright (c) 2007-2012, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * repopage.c
  10  *
  11  * Paging and compression functions for the vertical repository data.
  12  * Vertical data is grouped by key, normal data is grouped by solvable.
  13  * This makes searching for a string in vertical data fast as there's
  14  * no need to skip over data if keys we're not interested in.
  15  *
  16  * The vertical data is split into pages, each page is compressed with a fast
  17  * compression algorithm. These pages are read in on demand, not recently used
  18  * pages automatically get dropped.
  19  */
  20
  21 #define _XOPEN_SOURCE 500
  22
  23 #include <sys/types.h>
  24 #include <stdint.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <unistd.h>
  29 #include <assert.h>
  30 #include <fcntl.h>
  31 #include <time.h>
  32
  33 #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   store->blob_store = solv_free(store->blob_store);
 566   store->file_pages = solv_free(store->file_pages);
 567   store->mapped_at = solv_free(store->mapped_at);
 568   store->mapped = solv_free(store->mapped);
 569   if (store->pagefd != -1)
 570     close(store->pagefd);
 571   store->pagefd = -1;
 572 }
 573
 574
 575 /**********************************************************************/
 576
 577 unsigned char *
 578 repopagestore_load_page_range(Repopagestore *store, unsigned int pstart, unsigned int pend)
 579 {
 580 /* Make sure all pages from PSTART to PEND (inclusive) are loaded,
 581    and are consecutive.  Return a pointer to the mapping of PSTART.  */
 582   unsigned char buf[REPOPAGE_BLOBSIZE];
 583   unsigned int i, best, pnum;
 584
 585   if (pstart == pend)
 586     {
 587       /* Quick check in case the requested page is already mapped */
 588       if (store->mapped_at[pstart] != -1)
 589         return store->blob_store + store->mapped_at[pstart];
 590     }
 591   else
 592     {
 593       /* Quick check in case all pages are already mapped and consecutive.  */
 594       for (i = pstart; i <= pend; i++)
 595         if (store->mapped_at[i] == -1
 596             || (i > pstart
 597                 && store->mapped_at[i]
 598                    != store->mapped_at[i-1] + REPOPAGE_BLOBSIZE))
 599           break;
 600       if (i > pend)
 601         return store->blob_store + store->mapped_at[pstart];
 602     }
 603
 604   if (store->pagefd == -1 || !store->file_pages)
 605     return 0;   /* no backing file */
 606
 607 #ifdef DEBUG_PAGING
 608   fprintf(stderr, "PAGE: want %d pages starting at %d\n", pend - pstart + 1, pstart);
 609 #endif
 610
 611   /* Ensure that we can map the numbers of pages we need at all.  */
 612   if (pend - pstart + 1 > store->nmapped)
 613     {
 614       unsigned int oldcan = store->nmapped;
 615       store->nmapped = pend - pstart + 1;
 616       if (store->nmapped < 4)
 617         store->nmapped = 4;
 618       store->mapped = solv_realloc2(store->mapped, store->nmapped, sizeof(store->mapped[0]));
 619       memset(store->mapped + oldcan, 0, (store->nmapped - oldcan) * sizeof (store->mapped[0]));
 620       store->blob_store = solv_realloc2(store->blob_store, store->nmapped, REPOPAGE_BLOBSIZE);
 621 #ifdef DEBUG_PAGING
 622       fprintf(stderr, "PAGE: can map %d pages\n", store->nmapped);
 623 #endif
 624     }
 625
 626   if (store->mapped_at[pstart] != -1)
 627     {
 628       /* assume forward search */
 629       best = store->mapped_at[pstart] / REPOPAGE_BLOBSIZE;
 630       if (best + (pend - pstart) >= store->nmapped)
 631         best = 0;
 632     }
 633   else if (store->mapped_at[pend] != -1)
 634     {
 635       /* assume backward search */
 636       best = store->mapped_at[pend] / REPOPAGE_BLOBSIZE;
 637       if (best < pend - pstart)
 638         best = store->nmapped - 1;
 639       best -= pend - pstart;
 640     }
 641   else
 642     {
 643       /* choose some "random" location to avoid thrashing */
 644       best = (pstart + store->rr_counter++) % (store->nmapped - pend + pstart);
 645     }
 646
 647   /* So we want to map our pages from [best] to [best+pend-pstart].
 648      Use a very simple strategy, which doesn't make the best use of
 649      our resources, but works.  Throw away all pages in that range
 650      (even ours) then copy around ours or read them in.  */
 651   for (i = best, pnum = pstart; pnum <= pend; i++, pnum++)
 652     {
 653       unsigned int pnum_mapped_at;
 654       unsigned int oldpnum = store->mapped[i];
 655       if (oldpnum)
 656         {
 657           if (--oldpnum == pnum)
 658             continue;   /* already have the correct page */
 659           /* Evict this page.  */
 660 #ifdef DEBUG_PAGING
 661           fprintf(stderr, "PAGE: evict page %d from %d\n", oldpnum, i);
 662 #endif
 663           store->mapped[i] = 0;
 664           store->mapped_at[oldpnum] = -1;
 665         }
 666       /* check if we can copy the correct content (before it gets evicted) */
 667       pnum_mapped_at = store->mapped_at[pnum];
 668       if (pnum_mapped_at != -1 && pnum_mapped_at != i * REPOPAGE_BLOBSIZE)
 669         {
 670           void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
 671 #ifdef DEBUG_PAGING
 672           fprintf(stderr, "PAGECOPY: %d from %d to %d\n", pnum, pnum_mapped_at / REPOPAGE_BLOBSIZE, i);
 673 #endif
 674           memcpy(dest, store->blob_store + pnum_mapped_at, REPOPAGE_BLOBSIZE);
 675           store->mapped[pnum_mapped_at / REPOPAGE_BLOBSIZE] = 0;        /* slot is now empty */
 676           store->mapped[i] = pnum + 1;
 677           store->mapped_at[pnum] = i * REPOPAGE_BLOBSIZE;
 678         }
 679     }
 680
 681   /* Everything is free now.  Read in or copy the pages we want.  */
 682   for (i = best, pnum = pstart; pnum <= pend; i++, pnum++)
 683     {
 684       void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
 685       if (store->mapped_at[pnum] != -1)
 686         {
 687           unsigned int pnum_mapped_at = store->mapped_at[pnum];
 688           if (pnum_mapped_at != i * REPOPAGE_BLOBSIZE)
 689             {
 690 #ifdef DEBUG_PAGING
 691               fprintf(stderr, "PAGECOPY: %d from %d to %d\n", pnum, pnum_mapped_at / REPOPAGE_BLOBSIZE, i);
 692 #endif
 693               /* Still mapped somewhere else, so just copy it from there.  */
 694               memcpy(dest, store->blob_store + pnum_mapped_at, REPOPAGE_BLOBSIZE);
 695               store->mapped[pnum_mapped_at / REPOPAGE_BLOBSIZE] = 0;
 696             }
 697         }
 698       else
 699         {
 700           Attrblobpage *p = store->file_pages + pnum;
 701           unsigned int in_len = p->page_size;
 702           unsigned int compressed = in_len & 1;
 703           in_len >>= 1;
 704 #ifdef DEBUG_PAGING
 705           fprintf(stderr, "PAGEIN: %d to %d", pnum, i);
 706 #endif
 707           if (pread(store->pagefd, compressed ? buf : dest, in_len, store->file_offset + p->page_offset) != in_len)
 708             {
 709               perror("mapping pread");
 710               return 0;
 711             }
 712           if (compressed)
 713             {
 714               unsigned int out_len;
 715               out_len = unchecked_decompress_buf(buf, in_len, dest, REPOPAGE_BLOBSIZE);
 716               if (out_len != REPOPAGE_BLOBSIZE && pnum < store->num_pages - 1)
 717                 {
 718 #ifdef DEBUG_PAGING
 719                   fprintf(stderr, "can't decompress\n");
 720 #endif
 721                   return 0;
 722                 }
 723 #ifdef DEBUG_PAGING
 724               fprintf(stderr, " (expand %d to %d)", in_len, out_len);
 725 #endif
 726             }
 727 #ifdef DEBUG_PAGING
 728           fprintf(stderr, "\n");
 729 #endif
 730         }
 731       store->mapped_at[pnum] = i * REPOPAGE_BLOBSIZE;
 732       store->mapped[i] = pnum + 1;
 733     }
 734   return store->blob_store + best * REPOPAGE_BLOBSIZE;
 735 }
 736
 737 unsigned int
 738 repopagestore_compress_page(unsigned char *page, unsigned int len, unsigned char *cpage, unsigned int max)
 739 {
 740   return compress_buf(page, len, cpage, max);
 741 }
 742
 743 #define SOLV_ERROR_EOF          3
 744 #define SOLV_ERROR_CORRUPT      6
 745
 746 static inline unsigned int
 747 read_u32(FILE *fp)
 748 {
 749   int c, i;
 750   unsigned int x = 0;
 751
 752   for (i = 0; i < 4; i++)
 753     {
 754       c = getc(fp);
 755       if (c == EOF)
 756         return 0;
 757       x = (x << 8) | c;
 758     }
 759   return x;
 760 }
 761
 762 /* Try to either setup on-demand paging (using FP as backing
 763    file), or in case that doesn't work (FP not seekable) slurps in
 764    all pages and deactivates paging.  */
 765 int
 766 repopagestore_read_or_setup_pages(Repopagestore *store, FILE *fp, unsigned int pagesz, unsigned int blobsz)
 767 {
 768   unsigned int npages;
 769   unsigned int i;
 770   unsigned int can_seek;
 771   unsigned int cur_page_ofs;
 772   unsigned char buf[REPOPAGE_BLOBSIZE];
 773
 774   if (pagesz != REPOPAGE_BLOBSIZE)
 775     {
 776       /* We could handle this by slurping in everything.  */
 777       return SOLV_ERROR_CORRUPT;
 778     }
 779   can_seek = 1;
 780   if ((store->file_offset = ftell(fp)) < 0)
 781     can_seek = 0;
 782   clearerr(fp);
 783   if (can_seek)
 784     store->pagefd = dup(fileno(fp));
 785   if (store->pagefd == -1)
 786     can_seek = 0;
 787   else
 788     fcntl(store->pagefd, F_SETFD, FD_CLOEXEC);
 789
 790 #ifdef DEBUG_PAGING
 791   fprintf(stderr, "can %sseek\n", can_seek ? "" : "NOT ");
 792 #endif
 793   npages = (blobsz + REPOPAGE_BLOBSIZE - 1) / REPOPAGE_BLOBSIZE;
 794
 795   store->num_pages = npages;
 796   store->mapped_at = solv_malloc2(npages, sizeof(*store->mapped_at));
 797
 798   /* If we can't seek on our input we have to slurp in everything.
 799    * Otherwise set up file_pages containing offest/length of the
 800    * pages */
 801   if (can_seek)
 802     store->file_pages = solv_malloc2(npages, sizeof(*store->file_pages));
 803   else
 804     store->blob_store = solv_malloc2(npages, REPOPAGE_BLOBSIZE);
 805   cur_page_ofs = 0;
 806   for (i = 0; i < npages; i++)
 807     {
 808       unsigned int in_len = read_u32(fp);
 809       unsigned int compressed = in_len & 1;
 810       in_len >>= 1;
 811 #ifdef DEBUG_PAGING
 812       fprintf(stderr, "page %d: len %d (%scompressed)\n",
 813                i, in_len, compressed ? "" : "not ");
 814 #endif
 815       if (can_seek)
 816         {
 817           Attrblobpage *p = store->file_pages + i;
 818           cur_page_ofs += 4;
 819           store->mapped_at[i] = -1;     /* not mapped yet */
 820           p->page_offset = cur_page_ofs;
 821           p->page_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_page_ofs += in_len;
 831         }
 832       else
 833         {
 834           unsigned int out_len;
 835           void *dest = store->blob_store + i * REPOPAGE_BLOBSIZE;
 836           store->mapped_at[i] = i * REPOPAGE_BLOBSIZE;
 837           /* We can't seek, so suck everything in.  */
 838           if (fread(compressed ? buf : dest, in_len, 1, fp) != 1)
 839             {
 840               perror("fread");
 841               return SOLV_ERROR_EOF;
 842             }
 843           if (compressed)
 844             {
 845               out_len = unchecked_decompress_buf(buf, in_len, dest, REPOPAGE_BLOBSIZE);
 846               if (out_len != REPOPAGE_BLOBSIZE && i < npages - 1)
 847                 {
 848                   return SOLV_ERROR_CORRUPT;
 849                 }
 850             }
 851         }
 852     }
 853   return 0;
 854 }
 855
 856 void
 857 repopagestore_disable_paging(Repopagestore *store)
 858 {
 859   if (store->num_pages)
 860     repopagestore_load_page_range(store, 0, store->num_pages - 1);
 861 }
 862
 863 #ifdef STANDALONE
 864
 865 static void
 866 transfer_file(FILE * from, FILE * to, int compress)
 867 {
 868   unsigned char inb[BLOCK_SIZE];
 869   unsigned char outb[BLOCK_SIZE];
 870   while (!feof (from) && !ferror (from))
 871     {
 872       unsigned int in_len, out_len;
 873       if (compress)
 874         {
 875           in_len = fread(inb, 1, BLOCK_SIZE, from);
 876           if (in_len)
 877             {
 878               unsigned char *b = outb;
 879               out_len = compress_buf(inb, in_len, outb, sizeof (outb));
 880               if (!out_len)
 881                 b = inb, out_len = in_len;
 882               if (fwrite(&out_len, sizeof (out_len), 1, to) != 1)
 883                 {
 884                   perror("write size");
 885                   exit (1);
 886                 }
 887               if (fwrite(b, out_len, 1, to) != 1)
 888                 {
 889                   perror("write data");
 890                   exit (1);
 891                 }
 892             }
 893         }
 894       else
 895         {
 896           if (fread(&in_len, sizeof(in_len), 1, from) != 1)
 897             {
 898               if (feof(from))
 899                 return;
 900               perror("can't read size");
 901               exit(1);
 902             }
 903           if (fread(inb, in_len, 1, from) != 1)
 904             {
 905               perror("can't read data");
 906               exit(1);
 907             }
 908           out_len =
 909             unchecked_decompress_buf(inb, in_len, outb, sizeof(outb));
 910           if (fwrite(outb, out_len, 1, to) != 1)
 911             {
 912               perror("can't write output");
 913               exit(1);
 914             }
 915         }
 916     }
 917 }
 918
 919 /* Just for benchmarking purposes.  */
 920 static void
 921 dumb_memcpy(void *dest, const void *src, unsigned int len)
 922 {
 923   char *d = dest;
 924   const char *s = src;
 925   while (len--)
 926     *d++ = *s++;
 927 }
 928
 929 static void
 930 benchmark(FILE * from)
 931 {
 932   unsigned char inb[BLOCK_SIZE];
 933   unsigned char outb[BLOCK_SIZE];
 934   unsigned int in_len = fread(inb, 1, BLOCK_SIZE, from);
 935   unsigned int out_len;
 936   if (!in_len)
 937     {
 938       perror("can't read from input");
 939       exit(1);
 940     }
 941
 942   unsigned int calib_loop;
 943   unsigned int per_loop;
 944   unsigned int i, j;
 945   clock_t start, end;
 946   float seconds;
 947
 948 #if 0
 949   calib_loop = 1;
 950   per_loop = 0;
 951   start = clock();
 952   while ((clock() - start) < CLOCKS_PER_SEC / 4)
 953     {
 954       calib_loop *= 2;
 955       for (i = 0; i < calib_loop; i++)
 956         dumb_memcpy(outb, inb, in_len);
 957       per_loop += calib_loop;
 958     }
 959
 960   fprintf(stderr, "memcpy:\nCalibrated to %d iterations per loop\n",
 961            per_loop);
 962
 963   start = clock();
 964   for (i = 0; i < 10; i++)
 965     for (j = 0; j < per_loop; j++)
 966       dumb_memcpy(outb, inb, in_len);
 967   end = clock();
 968   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 969   fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 970            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 971 #endif
 972
 973   calib_loop = 1;
 974   per_loop = 0;
 975   start = clock();
 976   while ((clock() - start) < CLOCKS_PER_SEC / 4)
 977     {
 978       calib_loop *= 2;
 979       for (i = 0; i < calib_loop; i++)
 980         compress_buf(inb, in_len, outb, sizeof(outb));
 981       per_loop += calib_loop;
 982     }
 983
 984   fprintf(stderr, "compression:\nCalibrated to %d iterations per loop\n",
 985            per_loop);
 986
 987   start = clock();
 988   for (i = 0; i < 10; i++)
 989     for (j = 0; j < per_loop; j++)
 990       compress_buf(inb, in_len, outb, sizeof(outb));
 991   end = clock();
 992   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 993   fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 994            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 995
 996   out_len = compress_buf(inb, in_len, outb, sizeof(outb));
 997
 998   calib_loop = 1;
 999   per_loop = 0;
1000   start = clock();
1001   while ((clock() - start) < CLOCKS_PER_SEC / 4)
1002     {
1003       calib_loop *= 2;
1004       for (i = 0; i < calib_loop; i++)
1005         unchecked_decompress_buf(outb, out_len, inb, sizeof(inb));
1006       per_loop += calib_loop;
1007     }
1008
1009   fprintf(stderr, "decompression:\nCalibrated to %d iterations per loop\n",
1010            per_loop);
1011
1012   start = clock();
1013   for (i = 0; i < 10; i++)
1014     for (j = 0; j < per_loop; j++)
1015       unchecked_decompress_buf(outb, out_len, inb, sizeof(inb));
1016   end = clock();
1017   seconds = (end - start) / (float) CLOCKS_PER_SEC;
1018   fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
1019            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
1020 }
1021
1022 int
1023 main(int argc, char *argv[])
1024 {
1025   int compress = 1;
1026   if (argc > 1 && !strcmp(argv[1], "-d"))
1027     compress = 0;
1028   if (argc > 1 && !strcmp(argv[1], "-b"))
1029     benchmark(stdin);
1030   else
1031     transfer_file(stdin, stdout, compress);
1032   return 0;
1033 }
1034
1035 #endif
1036