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