src/repopage.c

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