xdelta3-blkcache.h

   1 /* xdelta 3 - delta compression tools and library
   2  * Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007,
   3  * 2008, 2009, 2010
   4  * Joshua P. MacDonald
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20
  21 /* TODO: This code is heavily revised from 3.0z but still needs major
  22  * refactoring. */
  23
  24 #include "xdelta3-internal.h"
  25
  26 typedef struct _main_blklru      main_blklru;
  27 typedef struct _main_blklru_list main_blklru_list;
  28
  29 struct _main_blklru_list
  30 {
  31   main_blklru_list  *next;
  32   main_blklru_list  *prev;
  33 };
  34
  35 struct _main_blklru
  36 {
  37   uint8_t          *blk;
  38   xoff_t            blkno;
  39   usize_t           size;
  40   main_blklru_list  link;
  41 };
  42
  43 #define MAX_LRU_SIZE 32U
  44 #define XD3_MINSRCWINSZ (XD3_ALLOCSIZE * MAX_LRU_SIZE)
  45 #define XD3_MAXSRCWINSZ (1ULL << 31)
  46
  47 XD3_MAKELIST(main_blklru_list,main_blklru,link);
  48
  49 static usize_t           lru_size = 0;
  50 static main_blklru      *lru = NULL;  /* array of lru_size elts */
  51 static main_blklru_list  lru_list;
  52 static int               do_src_fifo = 0;  /* set to avoid lru */
  53
  54 static int lru_hits   = 0;
  55 static int lru_misses = 0;
  56 static int lru_filled = 0;
  57
  58 static void main_lru_reset (void)
  59 {
  60   lru_size = 0;
  61   lru = NULL;
  62   do_src_fifo = 0;
  63   lru_hits   = 0;
  64   lru_misses = 0;
  65   lru_filled = 0;
  66 }
  67
  68 static void main_lru_cleanup (void)
  69 {
  70   if (lru != NULL)
  71     {
  72       main_buffree (lru[0].blk);
  73     }
  74
  75   main_free (lru);
  76   lru = NULL;
  77
  78   lru_hits = 0;
  79   lru_misses = 0;
  80   lru_filled = 0;
  81 }
  82
  83 /* This is called at different times for encoding and decoding.  The
  84  * encoder calls it immediately, the decoder delays until the
  85  * application header is received.  */
  86 static int
  87 main_set_source (xd3_stream *stream, xd3_cmd cmd,
  88                  main_file *sfile, xd3_source *source)
  89 {
  90   int ret = 0;
  91   usize_t i;
  92   xoff_t source_size = 0;
  93   usize_t blksize;
  94
  95   XD3_ASSERT (lru == NULL);
  96   XD3_ASSERT (stream->src == NULL);
  97   XD3_ASSERT (option_srcwinsz >= XD3_MINSRCWINSZ);
  98
  99   /* TODO: this code needs refactoring into FIFO, LRU, FAKE.  Yuck!
 100    * This is simplified from 3.0z which had issues with sizing the
 101    * source buffer memory allocation and the source blocksize. */
 102
 103   /* LRU-specific */
 104   main_blklru_list_init (& lru_list);
 105
 106   if (allow_fake_source)
 107     {
 108       /* TODO: refactor
 109        * TOOLS/recode-specific: Check "allow_fake_source" mode looks
 110        * broken now. */
 111       sfile->mode = XO_READ;
 112       sfile->realname = sfile->filename;
 113       sfile->nread = 0;
 114     }
 115   else
 116     {
 117       /* Either a regular file (possibly compressed) or a FIFO
 118        * (possibly compressed). */
 119       if ((ret = main_file_open (sfile, sfile->filename, XO_READ)))
 120         {
 121           return ret;
 122         }
 123
 124       /* If the file is regular we know it's size.  If the file turns
 125        * out to be externally compressed, size_known may change. */
 126       sfile->size_known = (main_file_stat (sfile, &source_size) == 0);
 127     }
 128
 129   /* Note: The API requires a power-of-two blocksize and srcwinsz
 130    * (-B).  The logic here will use a single block if the entire file
 131    * is known to fit into srcwinsz. */
 132   option_srcwinsz = xd3_pow2_roundup (option_srcwinsz);
 133
 134   /* Though called "lru", it is not LRU-specific.  We always allocate
 135    * a maximum number of source block buffers.  If the entire file
 136    * fits into srcwinsz, this buffer will stay as the only
 137    * (lru_size==1) source block.  Otherwise, we know that at least
 138    * option_srcwinsz bytes are available.  Split the source window
 139    * into buffers. */
 140   if ((lru = (main_blklru*) main_malloc (MAX_LRU_SIZE *
 141                                          sizeof (main_blklru))) == NULL)
 142     {
 143       ret = ENOMEM;
 144       return ret;
 145     }
 146
 147   memset (lru, 0, sizeof(lru[0]) * MAX_LRU_SIZE);
 148
 149   /* Allocate the entire buffer. */
 150   if ((lru[0].blk = (uint8_t*) main_bufalloc (option_srcwinsz)) == NULL)
 151     {
 152       ret = ENOMEM;
 153       return ret;
 154     }
 155
 156   /* Main calls main_getblk_func() once before xd3_set_source().  This
 157    * is the point at which external decompression may begin.  Set the
 158    * system for a single block. */
 159   lru_size = 1;
 160   lru[0].blkno = (xoff_t) -1;
 161   blksize = option_srcwinsz;
 162   main_blklru_list_push_back (& lru_list, & lru[0]);
 163   XD3_ASSERT (blksize != 0);
 164
 165   /* Initialize xd3_source. */
 166   source->blksize  = blksize;
 167   source->name     = sfile->filename;
 168   source->ioh      = sfile;
 169   source->curblkno = (xoff_t) -1;
 170   source->curblk   = NULL;
 171   source->max_winsize = option_srcwinsz;
 172
 173   if ((ret = main_getblk_func (stream, source, 0)) != 0)
 174     {
 175       XPR(NT "error reading source: %s: %s\n",
 176           sfile->filename,
 177           xd3_mainerror (ret));
 178       return ret;
 179     }
 180
 181   source->onblk = lru[0].size;  /* xd3 sets onblk */
 182
 183   /* If the file is smaller than a block, size is known. */
 184   if (!sfile->size_known && source->onblk < blksize)
 185     {
 186       source_size = source->onblk;
 187       sfile->size_known = 1;
 188     }
 189
 190   /* If the size is not known or is greater than the buffer size, we
 191    * split the buffer across MAX_LRU_SIZE blocks (already allocated in
 192    * "lru"). */
 193   if (!sfile->size_known || source_size > option_srcwinsz)
 194     {
 195       /* Modify block 0, change blocksize. */
 196       blksize = option_srcwinsz / MAX_LRU_SIZE;
 197       source->blksize = blksize;
 198       source->onblk = blksize;  /* xd3 sets onblk */
 199       /* Note: source->max_winsize is unchanged. */
 200       lru[0].size = blksize;
 201       lru_size = MAX_LRU_SIZE;
 202
 203       /* Setup rest of blocks. */
 204       for (i = 1; i < lru_size; i += 1)
 205         {
 206           lru[i].blk = lru[0].blk + (blksize * i);
 207           lru[i].blkno = i;
 208           lru[i].size = blksize;
 209           main_blklru_list_push_back (& lru_list, & lru[i]);
 210         }
 211     }
 212
 213   if (! sfile->size_known)
 214     {
 215       /* If the size is not know, we must use FIFO discipline. */
 216       do_src_fifo = 1;
 217     }
 218
 219   /* Call the appropriate set_source method, handle errors, print
 220    * verbose message, etc. */
 221   if (sfile->size_known)
 222     {
 223       ret = xd3_set_source_and_size (stream, source, source_size);
 224     }
 225   else
 226     {
 227       ret = xd3_set_source (stream, source);
 228     }
 229
 230   if (ret)
 231     {
 232       XPR(NT XD3_LIB_ERRMSG (stream, ret));
 233       return ret;
 234     }
 235
 236   XD3_ASSERT (stream->src == source);
 237   XD3_ASSERT (source->blksize == blksize);
 238
 239   if (option_verbose)
 240     {
 241       static shortbuf srcszbuf;
 242       static shortbuf srccntbuf;
 243       static shortbuf winszbuf;
 244       static shortbuf blkszbuf;
 245       static shortbuf nbufs;
 246
 247       if (sfile->size_known)
 248         {
 249           short_sprintf (srcszbuf, "source size %s [%"Q"u]",
 250                          main_format_bcnt (source_size, &srccntbuf),
 251                          source_size);
 252         }
 253       else
 254         {
 255           short_sprintf (srcszbuf, "%s", "source size unknown");
 256         }
 257
 258       nbufs.buf[0] = 0;
 259
 260       if (option_verbose > 1)
 261         {
 262           short_sprintf (nbufs, " #bufs %u", lru_size);
 263         }
 264
 265       XPR(NT "source %s %s blksize %s window %s%s%s\n",
 266           sfile->filename,
 267           srcszbuf.buf,
 268           main_format_bcnt (blksize, &blkszbuf),
 269           main_format_bcnt (option_srcwinsz, &winszbuf),
 270           nbufs.buf,
 271           do_src_fifo ? " (FIFO)" : "");
 272     }
 273
 274   return 0;
 275 }
 276
 277 static int
 278 main_getblk_lru (xd3_source *source, xoff_t blkno,
 279                  main_blklru** blrup, int *is_new)
 280 {
 281   main_blklru *blru = NULL;
 282   usize_t i;
 283
 284   (*is_new) = 0;
 285
 286   if (do_src_fifo)
 287     {
 288       /* Direct lookup assumes sequential scan w/o skipping blocks. */
 289       int idx = blkno % lru_size;
 290       blru = & lru[idx];
 291       if (blru->blkno == blkno)
 292         {
 293           (*blrup) = blru;
 294           return 0;
 295         }
 296       /* No going backwards in a sequential scan. */
 297       if (blru->blkno != (xoff_t) -1 && blru->blkno > blkno)
 298         {
 299           return XD3_TOOFARBACK;
 300         }
 301     }
 302   else
 303     {
 304       /* Sequential search through LRU. */
 305       for (i = 0; i < lru_size; i += 1)
 306         {
 307           blru = & lru[i];
 308           if (blru->blkno == blkno)
 309             {
 310               main_blklru_list_remove (blru);
 311               main_blklru_list_push_back (& lru_list, blru);
 312               (*blrup) = blru;
 313               return 0;
 314             }
 315         }
 316     }
 317
 318   if (do_src_fifo)
 319     {
 320       int idx = blkno % lru_size;
 321       blru = & lru[idx];
 322     }
 323   else
 324     {
 325       XD3_ASSERT (! main_blklru_list_empty (& lru_list));
 326       blru = main_blklru_list_pop_front (& lru_list);
 327       main_blklru_list_push_back (& lru_list, blru);
 328     }
 329
 330   lru_filled += 1;
 331   (*is_new) = 1;
 332   (*blrup) = blru;
 333   blru->blkno = -1;
 334   return 0;
 335 }
 336
 337 static int
 338 main_read_seek_source (xd3_stream *stream,
 339                        xd3_source *source,
 340                        xoff_t      blkno) {
 341   xoff_t pos = blkno * source->blksize;
 342   main_file *sfile = (main_file*) source->ioh;
 343   main_blklru *blru;
 344   int is_new;
 345   size_t nread = 0;
 346   int ret = 0;
 347
 348   if (!sfile->seek_failed)
 349     {
 350       ret = main_file_seek (sfile, pos);
 351
 352       if (ret == 0)
 353         {
 354           sfile->source_position = pos;
 355         }
 356     }
 357
 358   if (sfile->seek_failed || ret != 0)
 359     {
 360       /* For an unseekable file (or other seek error, does it
 361        * matter?) */
 362       if (sfile->source_position > pos)
 363         {
 364           /* Could assert !IS_ENCODE(), this shouldn't happen
 365            * because of do_src_fifo during encode. */
 366           if (!option_quiet)
 367             {
 368               XPR(NT "source can't seek backwards; requested block offset "
 369                   "%"Q"u source position is %"Q"u\n",
 370                   pos, sfile->source_position);
 371             }
 372
 373           sfile->seek_failed = 1;
 374           stream->msg = "non-seekable source: "
 375             "copy is too far back (try raising -B)";
 376           return XD3_TOOFARBACK;
 377         }
 378
 379       /* There's a chance here, that an genuine lseek error will cause
 380        * xdelta3 to shift into non-seekable mode, entering a degraded
 381        * condition.  */
 382       if (!sfile->seek_failed && option_verbose)
 383         {
 384           XPR(NT "source can't seek, will use FIFO for %s\n",
 385               sfile->filename);
 386
 387           if (option_verbose > 1)
 388             {
 389               XPR(NT "seek error at offset %"Q"u: %s\n",
 390                   pos, xd3_mainerror (ret));
 391             }
 392         }
 393
 394       sfile->seek_failed = 1;
 395
 396       if (option_verbose > 1 && pos != sfile->source_position)
 397         {
 398           XPR(NT "non-seekable source skipping %"Q"u bytes @ %"Q"u\n",
 399               pos - sfile->source_position,
 400               sfile->source_position);
 401         }
 402
 403       while (sfile->source_position < pos)
 404         {
 405           xoff_t skip_blkno;
 406           usize_t skip_offset;
 407
 408           xd3_blksize_div (sfile->source_position, source,
 409                            &skip_blkno, &skip_offset);
 410
 411           /* Read past unused data */
 412           XD3_ASSERT (pos - sfile->source_position >= source->blksize);
 413           XD3_ASSERT (skip_offset == 0);
 414
 415           if ((ret = main_getblk_lru (source, skip_blkno,
 416                                       & blru, & is_new)))
 417             {
 418               return ret;
 419             }
 420
 421           XD3_ASSERT (is_new);
 422           blru->blkno = skip_blkno;
 423
 424           if ((ret = main_read_primary_input (sfile,
 425                                               (uint8_t*) blru->blk,
 426                                               source->blksize,
 427                                               & nread)))
 428             {
 429               return ret;
 430             }
 431
 432           if (nread != source->blksize)
 433             {
 434               IF_DEBUG1 (DP(RINT "[getblk] short skip block nread = %zu\n",
 435                             nread));
 436               stream->msg = "non-seekable input is short";
 437               return XD3_INVALID_INPUT;
 438             }
 439
 440           sfile->source_position += nread;
 441           blru->size = nread;
 442
 443           IF_DEBUG1 (DP(RINT "[getblk] skip blkno %"Q"u size %u\n",
 444                         skip_blkno, blru->size));
 445
 446           XD3_ASSERT (sfile->source_position <= pos);
 447         }
 448     }
 449
 450   return 0;
 451 }
 452
 453 /* This is the callback for reading a block of source.  This function
 454  * is blocking and it implements a small LRU.
 455  *
 456  * Note that it is possible for main_input() to handle getblk requests
 457  * in a non-blocking manner.  If the callback is NULL then the caller
 458  * of xd3_*_input() must handle the XD3_GETSRCBLK return value and
 459  * fill the source in the same way.  See xd3_getblk for details.  To
 460  * see an example of non-blocking getblk, see xdelta-test.h. */
 461 static int
 462 main_getblk_func (xd3_stream *stream,
 463                   xd3_source *source,
 464                   xoff_t      blkno)
 465 {
 466   int ret = 0;
 467   xoff_t pos = blkno * source->blksize;
 468   main_file *sfile = (main_file*) source->ioh;
 469   main_blklru *blru;
 470   int is_new;
 471   int did_seek = 0;
 472   size_t nread = 0;
 473
 474   if (allow_fake_source)
 475     {
 476       source->curblkno = blkno;
 477       source->onblk    = 0;
 478       source->curblk   = lru[0].blk;
 479       lru[0].size = 0;
 480       return 0;
 481     }
 482
 483   if ((ret = main_getblk_lru (source, blkno, & blru, & is_new)))
 484     {
 485       return ret;
 486     }
 487
 488   if (!is_new)
 489     {
 490       source->curblkno = blkno;
 491       source->onblk    = blru->size;
 492       source->curblk   = blru->blk;
 493       lru_hits++;
 494       return 0;
 495     }
 496
 497   lru_misses += 1;
 498
 499   if (pos != sfile->source_position)
 500     {
 501       /* Only try to seek when the position is wrong.  This means the
 502        * decoder will fail when the source buffer is too small, but
 503        * only when the input is non-seekable. */
 504       if ((ret = main_read_seek_source (stream, source, blkno)))
 505         {
 506           return ret;
 507         }
 508
 509       /* Indicates that another call to main_getblk_lru() may be
 510        * needed */
 511       did_seek = 1;
 512     }
 513
 514   XD3_ASSERT (sfile->source_position == pos);
 515
 516   if (did_seek &&
 517       (ret = main_getblk_lru (source, blkno, & blru, & is_new)))
 518     {
 519       return ret;
 520     }
 521
 522   if ((ret = main_read_primary_input (sfile,
 523                                       (uint8_t*) blru->blk,
 524                                       source->blksize,
 525                                       & nread)))
 526     {
 527       return ret;
 528     }
 529
 530   /* Save the last block read, used to handle non-seekable files. */
 531   sfile->source_position = pos + nread;
 532
 533   if (option_verbose > 3)
 534     {
 535       if (blru->blkno != (xoff_t)-1)
 536         {
 537           if (blru->blkno != blkno)
 538             {
 539               XPR(NT "source block %"Q"u read %zu ejects %"Q"u (lru_hits=%u, "
 540                   "lru_misses=%u, lru_filled=%u)\n",
 541                   blkno, nread, blru->blkno, lru_hits, lru_misses, lru_filled);
 542             }
 543           else
 544             {
 545               XPR(NT "source block %"Q"u read %zu (lru_hits=%u, "
 546                   "lru_misses=%u, lru_filled=%u)\n",
 547                   blkno, nread, lru_hits, lru_misses, lru_filled);
 548             }
 549         }
 550       else
 551         {
 552           XPR(NT "source block %"Q"u read %zu (lru_hits=%u, lru_misses=%u, "
 553               "lru_filled=%u)\n", blkno, nread,
 554               lru_hits, lru_misses, lru_filled);
 555         }
 556     }
 557
 558   source->curblk   = blru->blk;
 559   source->curblkno = blkno;
 560   source->onblk    = nread;
 561   blru->size       = nread;
 562   blru->blkno      = blkno;
 563
 564   IF_DEBUG1 (DP(RINT "[main_getblk] blkno %"Q"u onblk %zu pos %"Q"u "
 565                 "srcpos %"Q"u\n",
 566                 blkno, nread, pos, sfile->source_position));
 567
 568   return 0;
 569 }