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