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