src/repopage.c

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