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