librsync  2.0.2
scoop.c
Go to the documentation of this file.
1 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2  *
3  * librsync -- the library for network deltas
4  *
5  * Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * as published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, write to the Free Software
19  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20  */
21 
22  /*=
23  | To walk on water you've gotta sink
24  | in the ice.
25  | -- Shihad, `The General Electric'.
26  */
27 
28 /** \file scoop.c This file deals with readahead from caller-supplied buffers.
29  *
30  * Many functions require a certain minimum amount of input to do their
31  * processing. For example, to calculate a strong checksum of a block we need
32  * at least a block of input.
33  *
34  * Since we put the buffers completely under the control of the caller, we
35  * can't count on ever getting this much data all in one go. We can't simply
36  * wait, because the caller might have a smaller buffer than we require and so
37  * we'll never get it. For the same reason we must always accept all the data
38  * we're given.
39  *
40  * So, stream input data that's required for readahead is put into a special
41  * buffer, from which the caller can then read. It's essentially like an
42  * internal pipe, which on any given read request may or may not be able to
43  * actually supply the data.
44  *
45  * As a future optimization, we might try to take data directly from the input
46  * buffer if there's already enough there.
47  *
48  * \todo We probably know a maximum amount of data that can be scooped up, so
49  * we could just avoid dynamic allocation. However that can't be fixed at
50  * compile time, because when generating a delta it needs to be large enough to
51  * hold one full block. Perhaps we can set it up when the job is allocated? It
52  * would be kind of nice to not do any memory allocation after startup, as
53  * bzlib does this. */
54 
55 #include "config.h"
56 
57 #include <assert.h>
58 #include <stdlib.h>
59 #include <stdio.h>
60 #include <string.h>
61 
62 #include "librsync.h"
63 #include "job.h"
64 #include "stream.h"
65 #include "trace.h"
66 #include "util.h"
67 
68 /** Try to accept a from the input buffer to get LEN bytes in the scoop. */
69 void rs_scoop_input(rs_job_t *job, size_t len)
70 {
71  rs_buffers_t *stream = job->stream;
72  size_t tocopy;
73 
74  assert(len > job->scoop_avail);
75 
76  if (job->scoop_alloc < len) {
77  /* Need to allocate a larger scoop. */
78  rs_byte_t *newbuf;
79  size_t newsize;
80  for (newsize = 64; newsize < len; newsize <<= 1) ;
81  newbuf = rs_alloc(newsize, "scoop buffer");
82  if (job->scoop_avail)
83  memcpy(newbuf, job->scoop_next, job->scoop_avail);
84  if (job->scoop_buf)
85  free(job->scoop_buf);
86  job->scoop_buf = job->scoop_next = newbuf;
87  rs_trace("resized scoop buffer to " FMT_SIZE " bytes from " FMT_SIZE "",
88  newsize, job->scoop_alloc);
89  job->scoop_alloc = newsize;
90  } else if (job->scoop_buf != job->scoop_next) {
91  /* Move existing data to the front of the scoop. */
92  rs_trace("moving scoop " FMT_SIZE " bytes to reuse " FMT_SIZE " bytes",
93  job->scoop_avail, (size_t)(job->scoop_next - job->scoop_buf));
94  memmove(job->scoop_buf, job->scoop_next, job->scoop_avail);
95  job->scoop_next = job->scoop_buf;
96  }
97  /* take as much input as is available, to give up to LEN bytes in the
98  scoop. */
99  tocopy = len - job->scoop_avail;
100  if (tocopy > stream->avail_in)
101  tocopy = stream->avail_in;
102  assert(tocopy + job->scoop_avail <= job->scoop_alloc);
103 
104  memcpy(job->scoop_next + job->scoop_avail, stream->next_in, tocopy);
105  rs_trace("accepted " FMT_SIZE " bytes from input to scoop", tocopy);
106  job->scoop_avail += tocopy;
107  stream->next_in += tocopy;
108  stream->avail_in -= tocopy;
109 }
110 
111 /** Advance the input cursor forward \p len bytes.
112  *
113  * This is used after doing readahead, when you decide you want to keep it. \p
114  * len must be no more than the amount of available data, so you can't cheat.
115  *
116  * So when creating a delta, we require one block of readahead. But after
117  * examining that block, we might decide to advance over all of it (if there is
118  * a match), or just one byte (if not). */
119 void rs_scoop_advance(rs_job_t *job, size_t len)
120 {
121  rs_buffers_t *stream = job->stream;
122 
123  /* It never makes sense to advance over a mixture of bytes from the scoop
124  and input, because you couldn't possibly have looked at them all at the
125  same time. */
126  if (job->scoop_avail) {
127  /* reading from the scoop buffer */
128  rs_trace("advance over " FMT_SIZE " bytes from scoop", len);
129  assert(len <= job->scoop_avail);
130  job->scoop_avail -= len;
131  job->scoop_next += len;
132  } else {
133  rs_trace("advance over " FMT_SIZE " bytes from input buffer", len);
134  assert(len <= stream->avail_in);
135  stream->avail_in -= len;
136  stream->next_in += len;
137  }
138 }
139 
140 /** Read from scoop without advancing.
141  *
142  * Ask for LEN bytes of input from the stream. If that much data is available,
143  * then return a pointer to it in PTR, advance the stream input pointer over
144  * the data, and return RS_DONE. If there's not enough data, then accept
145  * whatever is there into a buffer, advance over it, and return RS_BLOCKED.
146  *
147  * The data is not actually removed from the input, so this function lets you
148  * do readahead. If you want to keep any of the data, you should also call
149  * rs_scoop_advance() to skip over it. */
150 rs_result rs_scoop_readahead(rs_job_t *job, size_t len, void **ptr)
151 {
152  rs_buffers_t *stream = job->stream;
153  rs_job_check(job);
154 
155  if (!job->scoop_avail && stream->avail_in >= len) {
156  /* The scoop is empty and there's enough data in the input. */
157  *ptr = stream->next_in;
158  rs_trace("got " FMT_SIZE " bytes direct from input", len);
159  return RS_DONE;
160  } else if (job->scoop_avail < len && stream->avail_in) {
161  /* There is not enough data in the scoop. */
162  rs_trace("scoop has less than " FMT_SIZE " bytes, scooping from "
163  FMT_SIZE " input bytes", len, stream->avail_in);
164  rs_scoop_input(job, len);
165  }
166  if (job->scoop_avail >= len) {
167  /* There is enough data in the scoop now. */
168  rs_trace("scoop has at least " FMT_SIZE " bytes, this is enough",
169  job->scoop_avail);
170  *ptr = job->scoop_next;
171  return RS_DONE;
172  } else if (stream->eof_in) {
173  /* Not enough input data and at EOF. */
174  rs_trace("reached end of input stream");
175  return RS_INPUT_ENDED;
176  } else {
177  /* Not enough input data yet. */
178  rs_trace("blocked with insufficient input data");
179  return RS_BLOCKED;
180  }
181 }
182 
183 /** Read LEN bytes if possible, and remove them from the input scoop.
184  *
185  * \param ptr will be updated to point to a read-only buffer holding the data,
186  * if enough is available.
187  *
188  * \return RS_DONE if there was enough data, RS_BLOCKED if there was not enough
189  * data yet, or RS_INPUT_ENDED if there was not enough data and at EOF. */
190 rs_result rs_scoop_read(rs_job_t *job, size_t len, void **ptr)
191 {
192  rs_result result;
193 
194  result = rs_scoop_readahead(job, len, ptr);
195  if (result == RS_DONE)
196  rs_scoop_advance(job, len);
197  return result;
198 }
199 
200 /** Read whatever data remains in the input stream.
201  *
202  * \param *len will be updated to the length of the available data.
203  *
204  * \param **ptr will point at the available data.
205  *
206  * \return RS_DONE if there was data, RS_INPUT_ENDED if there was no data and
207  * at EOF, RS_BLOCKED if there was no data and not at EOF. */
208 rs_result rs_scoop_read_rest(rs_job_t *job, size_t *len, void **ptr)
209 {
210  rs_buffers_t *stream = job->stream;
211 
212  *len = job->scoop_avail + stream->avail_in;
213  if (*len)
214  return rs_scoop_read(job, *len, ptr);
215  else if (stream->eof_in)
216  return RS_INPUT_ENDED;
217  else
218  return RS_BLOCKED;
219 }
220 
221 /** Return the total number of bytes available including the scoop and input
222  * buffer. */
224 {
225  return job->scoop_avail + job->stream->avail_in;
226 }
Description of input and output buffers.
Definition: librsync.h:300
logging functions.
rs_result rs_scoop_read_rest(rs_job_t *job, size_t *len, void **ptr)
Read whatever data remains in the input stream.
Definition: scoop.c:208
size_t rs_scoop_total_avail(rs_job_t *job)
Return the total number of bytes available including the scoop and input buffer.
Definition: scoop.c:223
void rs_scoop_input(rs_job_t *job, size_t len)
Try to accept a from the input buffer to get LEN bytes in the scoop.
Definition: scoop.c:69
size_t avail_in
Number of bytes available at next_in.
Definition: librsync.h:314
Public header for librsync.
char * next_in
Next input byte.
Definition: librsync.h:306
rs_result
Return codes from nonblocking rsync operations.
Definition: librsync.h:161
Unexpected end of input file, perhaps due to a truncated file or dropped network connection.
Definition: librsync.h:171
Blocked waiting for more data.
Definition: librsync.h:163
rs_result rs_scoop_read(rs_job_t *job, size_t len, void **ptr)
Read LEN bytes if possible, and remove them from the input scoop.
Definition: scoop.c:190
rs_byte_t * scoop_buf
Buffer of data in the scoop.
Definition: job.h:77
int eof_in
True if there is no more data after this.
Definition: librsync.h:317
Completed successfully.
Definition: librsync.h:162
rs_result rs_scoop_readahead(rs_job_t *job, size_t len, void **ptr)
Read from scoop without advancing.
Definition: scoop.c:150
void rs_scoop_advance(rs_job_t *job, size_t len)
Advance the input cursor forward len bytes.
Definition: scoop.c:119
of this structure are private.
Definition: job.h:26