"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3-blkcache.h" (5 Jan 2016, 14465 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "xdelta3-blkcache.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.0.11_vs_3.1.0.

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