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