$treeview $search $mathjax $extrastylesheet
librsync
2.0.2
$projectbrief
|
$projectbrief
|
$searchbox |
00001 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 * 00003 * librsync -- the library for network deltas 00004 * 00005 * Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net> 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public License 00009 * as published by the Free Software Foundation; either version 2.1 of 00010 * the License, or (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, but 00013 * WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 * Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public 00018 * License along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 */ 00021 00022 /*= 00023 | To walk on water you've gotta sink 00024 | in the ice. 00025 | -- Shihad, `The General Electric'. 00026 */ 00027 00028 /** \file scoop.c This file deals with readahead from caller-supplied buffers. 00029 * 00030 * Many functions require a certain minimum amount of input to do their 00031 * processing. For example, to calculate a strong checksum of a block we need 00032 * at least a block of input. 00033 * 00034 * Since we put the buffers completely under the control of the caller, we 00035 * can't count on ever getting this much data all in one go. We can't simply 00036 * wait, because the caller might have a smaller buffer than we require and so 00037 * we'll never get it. For the same reason we must always accept all the data 00038 * we're given. 00039 * 00040 * So, stream input data that's required for readahead is put into a special 00041 * buffer, from which the caller can then read. It's essentially like an 00042 * internal pipe, which on any given read request may or may not be able to 00043 * actually supply the data. 00044 * 00045 * As a future optimization, we might try to take data directly from the input 00046 * buffer if there's already enough there. 00047 * 00048 * \todo We probably know a maximum amount of data that can be scooped up, so 00049 * we could just avoid dynamic allocation. However that can't be fixed at 00050 * compile time, because when generating a delta it needs to be large enough to 00051 * hold one full block. Perhaps we can set it up when the job is allocated? It 00052 * would be kind of nice to not do any memory allocation after startup, as 00053 * bzlib does this. */ 00054 00055 #include "config.h" 00056 00057 #include <assert.h> 00058 #include <stdlib.h> 00059 #include <stdio.h> 00060 #include <string.h> 00061 00062 #include "librsync.h" 00063 #include "job.h" 00064 #include "stream.h" 00065 #include "trace.h" 00066 #include "util.h" 00067 00068 /** Try to accept a from the input buffer to get LEN bytes in the scoop. */ 00069 void rs_scoop_input(rs_job_t *job, size_t len) 00070 { 00071 rs_buffers_t *stream = job->stream; 00072 size_t tocopy; 00073 00074 assert(len > job->scoop_avail); 00075 00076 if (job->scoop_alloc < len) { 00077 /* Need to allocate a larger scoop. */ 00078 rs_byte_t *newbuf; 00079 size_t newsize; 00080 for (newsize = 64; newsize < len; newsize <<= 1) ; 00081 newbuf = rs_alloc(newsize, "scoop buffer"); 00082 if (job->scoop_avail) 00083 memcpy(newbuf, job->scoop_next, job->scoop_avail); 00084 if (job->scoop_buf) 00085 free(job->scoop_buf); 00086 job->scoop_buf = job->scoop_next = newbuf; 00087 rs_trace("resized scoop buffer to " FMT_SIZE " bytes from " FMT_SIZE "", 00088 newsize, job->scoop_alloc); 00089 job->scoop_alloc = newsize; 00090 } else if (job->scoop_buf != job->scoop_next) { 00091 /* Move existing data to the front of the scoop. */ 00092 rs_trace("moving scoop " FMT_SIZE " bytes to reuse " FMT_SIZE " bytes", 00093 job->scoop_avail, (size_t)(job->scoop_next - job->scoop_buf)); 00094 memmove(job->scoop_buf, job->scoop_next, job->scoop_avail); 00095 job->scoop_next = job->scoop_buf; 00096 } 00097 /* take as much input as is available, to give up to LEN bytes in the 00098 scoop. */ 00099 tocopy = len - job->scoop_avail; 00100 if (tocopy > stream->avail_in) 00101 tocopy = stream->avail_in; 00102 assert(tocopy + job->scoop_avail <= job->scoop_alloc); 00103 00104 memcpy(job->scoop_next + job->scoop_avail, stream->next_in, tocopy); 00105 rs_trace("accepted " FMT_SIZE " bytes from input to scoop", tocopy); 00106 job->scoop_avail += tocopy; 00107 stream->next_in += tocopy; 00108 stream->avail_in -= tocopy; 00109 } 00110 00111 /** Advance the input cursor forward \p len bytes. 00112 * 00113 * This is used after doing readahead, when you decide you want to keep it. \p 00114 * len must be no more than the amount of available data, so you can't cheat. 00115 * 00116 * So when creating a delta, we require one block of readahead. But after 00117 * examining that block, we might decide to advance over all of it (if there is 00118 * a match), or just one byte (if not). */ 00119 void rs_scoop_advance(rs_job_t *job, size_t len) 00120 { 00121 rs_buffers_t *stream = job->stream; 00122 00123 /* It never makes sense to advance over a mixture of bytes from the scoop 00124 and input, because you couldn't possibly have looked at them all at the 00125 same time. */ 00126 if (job->scoop_avail) { 00127 /* reading from the scoop buffer */ 00128 rs_trace("advance over " FMT_SIZE " bytes from scoop", len); 00129 assert(len <= job->scoop_avail); 00130 job->scoop_avail -= len; 00131 job->scoop_next += len; 00132 } else { 00133 rs_trace("advance over " FMT_SIZE " bytes from input buffer", len); 00134 assert(len <= stream->avail_in); 00135 stream->avail_in -= len; 00136 stream->next_in += len; 00137 } 00138 } 00139 00140 /** Read from scoop without advancing. 00141 * 00142 * Ask for LEN bytes of input from the stream. If that much data is available, 00143 * then return a pointer to it in PTR, advance the stream input pointer over 00144 * the data, and return RS_DONE. If there's not enough data, then accept 00145 * whatever is there into a buffer, advance over it, and return RS_BLOCKED. 00146 * 00147 * The data is not actually removed from the input, so this function lets you 00148 * do readahead. If you want to keep any of the data, you should also call 00149 * rs_scoop_advance() to skip over it. */ 00150 rs_result rs_scoop_readahead(rs_job_t *job, size_t len, void **ptr) 00151 { 00152 rs_buffers_t *stream = job->stream; 00153 rs_job_check(job); 00154 00155 if (!job->scoop_avail && stream->avail_in >= len) { 00156 /* The scoop is empty and there's enough data in the input. */ 00157 *ptr = stream->next_in; 00158 rs_trace("got " FMT_SIZE " bytes direct from input", len); 00159 return RS_DONE; 00160 } else if (job->scoop_avail < len && stream->avail_in) { 00161 /* There is not enough data in the scoop. */ 00162 rs_trace("scoop has less than " FMT_SIZE " bytes, scooping from " 00163 FMT_SIZE " input bytes", len, stream->avail_in); 00164 rs_scoop_input(job, len); 00165 } 00166 if (job->scoop_avail >= len) { 00167 /* There is enough data in the scoop now. */ 00168 rs_trace("scoop has at least " FMT_SIZE " bytes, this is enough", 00169 job->scoop_avail); 00170 *ptr = job->scoop_next; 00171 return RS_DONE; 00172 } else if (stream->eof_in) { 00173 /* Not enough input data and at EOF. */ 00174 rs_trace("reached end of input stream"); 00175 return RS_INPUT_ENDED; 00176 } else { 00177 /* Not enough input data yet. */ 00178 rs_trace("blocked with insufficient input data"); 00179 return RS_BLOCKED; 00180 } 00181 } 00182 00183 /** Read LEN bytes if possible, and remove them from the input scoop. 00184 * 00185 * \param ptr will be updated to point to a read-only buffer holding the data, 00186 * if enough is available. 00187 * 00188 * \return RS_DONE if there was enough data, RS_BLOCKED if there was not enough 00189 * data yet, or RS_INPUT_ENDED if there was not enough data and at EOF. */ 00190 rs_result rs_scoop_read(rs_job_t *job, size_t len, void **ptr) 00191 { 00192 rs_result result; 00193 00194 result = rs_scoop_readahead(job, len, ptr); 00195 if (result == RS_DONE) 00196 rs_scoop_advance(job, len); 00197 return result; 00198 } 00199 00200 /** Read whatever data remains in the input stream. 00201 * 00202 * \param *len will be updated to the length of the available data. 00203 * 00204 * \param **ptr will point at the available data. 00205 * 00206 * \return RS_DONE if there was data, RS_INPUT_ENDED if there was no data and 00207 * at EOF, RS_BLOCKED if there was no data and not at EOF. */ 00208 rs_result rs_scoop_read_rest(rs_job_t *job, size_t *len, void **ptr) 00209 { 00210 rs_buffers_t *stream = job->stream; 00211 00212 *len = job->scoop_avail + stream->avail_in; 00213 if (*len) 00214 return rs_scoop_read(job, *len, ptr); 00215 else if (stream->eof_in) 00216 return RS_INPUT_ENDED; 00217 else 00218 return RS_BLOCKED; 00219 } 00220 00221 /** Return the total number of bytes available including the scoop and input 00222 * buffer. */ 00223 size_t rs_scoop_total_avail(rs_job_t *job) 00224 { 00225 return job->scoop_avail + job->stream->avail_in; 00226 }