File: nad.c

package info (click to toggle)
libhsync 0.5.7-1.2
  • links: PTS
  • area: main
  • in suites: woody
  • size: 1,060 kB
  • ctags: 543
  • sloc: sh: 7,944; ansic: 5,413; makefile: 154
file content (398 lines) | stat: -rw-r--r-- 13,023 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
/*=                                     -*- c-file-style: "bsd" -*-
 * rproxy -- dynamic caching and delta update in HTTP
 * $Id: nad.c,v 1.21 2000/08/13 10:44:19 mbp Exp $
 * 
 * Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

                                        /*
                                         | Hearts and thoughts they
                                         | fade, fade away.
                                         */


/*=
 * GENERATE NEW SIGNATURES AND DIFFERENCE STREAM
 *
 * Here's a diagram of the encoding process:
 *
 *                            /------- OLD SIGNATURE
 *                           v
 * UPSTREAM -raw-+-----> SEARCH ------> chunked -> DOWNSTREAM
 *               \                        ^
 *                > --- NEW SIGNATURE ---'
 *
 * Before the process starts, we read and hold in memory an
 * hs_sumset_t containing checksums of the old version of the file.
 * We want to read in the new file, and generate a chunked stream
 * describing differences from the old version.  Also, we generate a
 * checksum (not shown) of the entire file from upstream, which is
 * passed into the chunked stream as an extra check against mistakes
 * while encoding the file.
 *
 * All of this has to be pipelined.  This means that we start sending
 * data as soon as we can, rather than waiting until we've seen the
 * whole file: it might be arbitrarily big, or take a long time to
 * come down.  However, we need a certain amount of elbow-room to
 * generate signatures and find matches: in fact, we need a block of
 * readahead for both of them.
 *
 * The whole algorithm is done in a kind of non-blocking way: we
 * process as much input as is available on each iteration, and then
 * return to the caller so they can do something else if they wish.
 *
 * It's important to understand the relationship between
 * signature-generation and match-finding.  I think of them as train
 * cars bumping into each other: they're both using the same map_ptr
 * region and so are coupled, but they don't move in lock step.  So
 * there are separate cursors in the nad_job for all of them.  Each
 * time we map some input data, we process as much of each as
 * possible.
 *
 * The block sizes for old and new signatures may be different.
 * New signatures are always generated aligned on block boundaries,
 * and there's no point doing rolling checksums for them, since we
 * always know exactly where they're going to be.  We need to generate
 * an md4sum for each block.
 *
 * In the search checksums, rolling signatures are crucially important
 * -- these are meant to be cheap to calculate.  If we think we
 * matched on the weak rolling checksum, then we calculate the strong
 * (md4) checksum and see if it matches.  If we find a match, then we
 * emit a COPY command, advance the cursor and restart the rolling
 * checksum.
 *
 * (Calculating the new and search checksums independently is a little
 * inefficient when the block lengths are the same and they're
 * perfectly aligned: we're calculating the signature twice for the
 * same data.  Having the two files exactly the same is not uncommon,
 * but still it's OK to waste a little time in this version.  We might
 * in the future detect that they're the same and just echo back the
 * same signature, but that's an optimization.)
 *
 * This file doesn't know about the wire encoding format: it just says
 * something when it has a match, literal, or signature data, and
 * emit.c et al actually send it out.
 *
 * There are special cases when we're approaching the end of the
 * file.  The final signature must be generated over the (possibly)
 * short block at the end.  The search must be prepared to match that
 * short block, or if it doesn't match then to emit it as literal
 * data.
 *
 * At the same time, we also calculate a whole-file md4 checksum,
 * which the decoder is likely to use as proof that the server is not
 * mentally competent.
 *
 * Perhaps mapptr is not quite the right interface to use here, though
 * it's pretty close.  It's kind of arguable whether this function
 * should call for more input or vice versa.  If it calls for input,
 * then perhaps it should call through a callback function.  Still,
 * for the time being almost everyone will want to just use plain IO,
 * so there's no immediate reason to complicate it.
 */

/*
 * TODO: Check all return codes when writing.
 *
 * TODO: Send out literals through a literal buffer to make
 * transmission faster?  If we do this, then don't copy the data again
 * but just keep it mapped until we're finished with it.  Perhaps this
 * even points the way to a clean way to do non-blocking output as
 * well?
 *
 * TODO: Send out copy commands through a copy queue; I think the
 * design for this is already about as good as it can be.
 *
 * TODO: We should be nonblocking on output.  I'm not sure how clever
 * we have to be, though: is it enough just to queue up all the
 * output, or should we take the available output queue space into
 * account in deciding what to do?
 */


const int hs_encode_job_magic = 23452345;


#include "includes.h"
#include "mapptr.h" 
#include "nad_p.h"
#include "sum_p.h"
#include "command.h"
#include "emit.h"


static void
_hs_nad_filesum_begin(hs_encode_job_t *job)
{
    hs_mdfour_begin(&job->filesum);
}


static void
_hs_nad_sum_begin(hs_encode_job_t *job)
{
    job->sig_tmpbuf = hs_membuf_new();
    job->new_strong_len = DEFAULT_SUM_LENGTH;

    if (_hs_newsig_header(job->new_block_len,
                          hs_membuf_write,
                          job->sig_tmpbuf)
        < 0) {
        _hs_fatal("couldn't write newsig header!");
    }
}


/*
 * Start a new job of nad encoding.  After calling this, the return
 * value should be passed repeatedly to hs_encode_iter until all the
 * work is done.
 */
hs_encode_job_t *
hs_encode_begin(int in_fd, hs_write_fn_t write_fn, void *write_priv,
                hs_sumset_t *sums,
                hs_stats_t *stats,
                size_t new_block_len)
{
    hs_encode_job_t *job;
    int ret;

    job = _hs_alloc_struct(hs_encode_job_t);

    job->in_fd = in_fd;
    job->in_map = hs_map_file(in_fd);

    job->write_priv = write_priv;
    job->write_fn = write_fn;

    job->sums = sums;
    if (job->sums) {
        assert(job->sums->block_len > 0);
        job->search_block_len = job->sums->block_len;
    } else {
        /* We can read and process one byte at a time, because we can
         * never match.  Of course we hope mapptr will give us back
         * more data than that. */
        job->search_block_len = 1;
    }
    
    job->new_block_len = new_block_len;
    hs_bzero(stats, sizeof *stats);

    job->search_cursor = job->literal_cursor = 0;

    job->stats = stats;
    stats->op = "encode";
    stats->algorithm = "nad";
    
    job->rollsum = _hs_alloc_struct(hs_rollsum_t);

    _hs_trace("**** begin");

    hs_bzero(&job->copyq, sizeof job->copyq);

    _hs_nad_filesum_begin(job);

    if ((ret = _hs_littok_header(write_fn, write_priv)) < 0)
        _hs_fatal("couldn't write littok header!");

    _hs_nad_sum_begin(job);

    return job;
}


/*
 * Work out where we have to map to achieve something useful, and
 * return a pointer thereto.  Set MAP_LEN to the amount of available
 * data.
 */
static byte_t const *
_hs_nad_map(hs_encode_job_t *job)
{
    off_t            start, end, end2;

    /* once we've seen eof, we should never try to map any more
     * data. */
    assert(!job->seen_eof);

    /* Find the range we have to map that won't skip data that hasn't
     * been processed, but that allows us to accomplish something. */
    start = job->search_cursor;
    if (start > job->sum_cursor)
        start = job->sum_cursor;

    end = job->search_cursor + job->search_block_len;
    end2 = job->sum_cursor + job->new_block_len;

    _hs_trace("start(search=%ld, sum=%ld), end(search=%ld, sum=%ld)",
              (long) job->search_cursor, (long) job->sum_cursor,
              (long) end, (long) end2);

    /* We choose the earlier end, because that's the earliest place
     * that will allow us to get some useful work done.  Because the
     * blocks can be different it need not be the same as in the
     * previous condition. */
    if (end2 < end)
        end = end2;
    
    job->map_off = start;
    job->map_len = end - start;

    job->map_p = hs_map_ptr(job->in_map, job->map_off, &job->map_len,
                             &job->seen_eof);

    return job->map_p;
}


/*
 * Emit a literal command for the available data without doing any
 * searching.  We use this when we have no signature for the old file.
 */
static void
_hs_nad_baseless_iter(hs_encode_job_t *job)
{
    job->search_cursor = job->map_off + job->map_len;
    _hs_nad_flush_literal(job);
}


/*
 * Try to match at the current search cursor position.  If we find
 * one, then emit an appropriate copy command.  If not, emit a minimal
 * literal command and try again next time.
 */
static void
_hs_nad_sum_iter(hs_encode_job_t *job)
{
    byte_t const *p = job->map_p + job->sum_cursor - job->map_off;
    size_t avail = job->map_len - job->sum_cursor + job->map_off;

    while (avail >= job->new_block_len ||
           (job->seen_eof  && avail > 0)) {
        size_t  l;

        if (job->seen_eof)
            l = avail;
        else
            l = job->new_block_len;

        _hs_trace("do checksum @%ld+%ld", (long) job->sum_cursor,
                  (long) l);
        _hs_mksum_of_block(p, l, 
                           hs_membuf_write, job->sig_tmpbuf, 
                           job->new_strong_len);

        _hs_push_literal_buf(job->sig_tmpbuf,
                             job->write_fn, job->write_priv,
                             job->stats, op_kind_signature);

        p += l;
        job->sum_cursor += l;
        avail -= l;
    }
}



static void
_hs_nad_filesum_flush(hs_encode_job_t *job)
{
    byte_t             result[MD4_LENGTH];
#ifdef DO_HS_TRACE
    char               sum_hex[MD4_LENGTH * 3];
#endif

    hs_mdfour_result(&job->filesum, result);

#ifdef DO_HS_TRACE
    /* At the end, emit the whole thing */
    hs_hexify_buf(sum_hex, result, MD4_LENGTH);
    _hs_trace("flushing out filesum %s", sum_hex);
#endif

    _hs_emit_filesum(job->write_fn, job->write_priv,
                     result, MD4_LENGTH);
}



/*
 * Update the hash of the whole file to date, to be emitted at the
 * end to catch errors in the encode/decode algorithms.
 */
static void
_hs_nad_filesum_iter(hs_encode_job_t *job)
{
    byte_t const *p = job->map_p - job->map_off + job->filesum_cursor;
    size_t avail = job->map_len + job->map_off - job->filesum_cursor;
    
    hs_mdfour_update(&job->filesum, p, avail);

    job->filesum_cursor += avail;
}



hs_result_t
hs_encode_iter(hs_encode_job_t *job)
{
    /* Map some data.  We advance the map to the earliest point in the
     * datastream that anybody needs to see.
     *
     * Several things can happen here:
     *
     * If the stream is in blocking mode, then we'll read at least
     * enough data to run one of the coroutines.  If the stream is in
     * nonblocking mode, we might not get enough, in which case we'll
     * return and the caller will presumably call select(2).
     *
     * In either case, if we reach EOF we'll finish up processing
     * immediately.  */
    _hs_nad_map(job);

    /* We have essentially three coroutines to run here.  We know
     * their cursor position, so we can give each of them a pointer
     * and length for their data. */
    if (job->sums) {
        _hs_nad_search_iter(job);
    } else {
        _hs_nad_baseless_iter(job);
    }
    
    _hs_nad_sum_iter(job);
    _hs_nad_filesum_iter(job);

    /* TODO: When we have copy queues, we should flush them here
     * too. */
    _hs_nad_flush_literal(job);

    /* The problem here is that we might be near EOF, but mapptr won't
     * realize it has to do another read, and we won't know that we
     * should force it.  All we see is that we have not enough data to
     * do a full read.  What now? */

    if (job->seen_eof) {
        _hs_nad_filesum_flush(job);
        _hs_emit_eof(job->write_fn, job->write_priv, job->stats);
        return HS_DONE;
    } else {
        return HS_AGAIN;
    }
}