1 /* Cumulus: Efficient Filesystem Backup to the Cloud
2 * Copyright (C) 2008 The Cumulus Developers
3 * See the AUTHORS file for a list of contributors.
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 /* Allow for sub-file incremental backups: if only a portion of a file changes,
21 * allow the new data to be written out, and the old data to simply be
22 * referenced from the new metadata log. */
27 #include <arpa/inet.h>
30 #include "third_party/chunk.h"
31 #include "third_party/sha1.h"
41 Subfile::Subfile(LocalDb *localdb)
42 : db(localdb), checksums_loaded(false), new_block_summary_valid(false)
48 for (size_t i = 0; i < block_list.size(); i++) {
49 delete[] block_list[i].chunks;
55 void Subfile::free_analysis()
57 if (new_block_summary_valid)
58 delete[] new_block_summary.chunks;
60 new_block_summary_valid = false;
63 void Subfile::load_old_blocks(const list<ObjectReference> &blocks)
65 for (list<ObjectReference>::const_iterator i = blocks.begin();
66 i != blocks.end(); ++i) {
70 ObjectReference base = i->base();
71 if (old_blocks.find(base) == old_blocks.end()) {
72 old_blocks.insert(base);
79 /* Actually load chunk signatures from the database, and index them in memory.
80 * This should only be called once per segment. */
81 void Subfile::index_chunks(ObjectReference ref)
83 string refstr = ref.to_string();
85 if (!db->IsAvailable(ref))
88 /* Look for checksums for this block in the database. They may not exist,
89 * in which case simply return without error. */
93 if (!db->LoadChunkSignatures(ref, (void **)&packed_sigs, &len, &algorithm))
95 if (algorithm != get_algorithm()) {
100 int block_id = block_list.size();
102 block_summary summary;
103 summary.ref = ref.base();
104 summary.num_chunks = len / (2 + HASH_SIZE);
105 summary.chunks = new chunk_info[summary.num_chunks];
108 for (int i = 0; i < summary.num_chunks; i++) {
109 char *packed_info = &packed_sigs[i * (2 + HASH_SIZE)];
110 memcpy(summary.chunks[i].hash, &packed_info[2], HASH_SIZE);
113 memcpy(&chunk_len, &packed_info[0], 2);
114 summary.chunks[i].len = ntohs(chunk_len);
115 summary.chunks[i].offset = block_start;
116 block_start += summary.chunks[i].len;
118 chunk_index[string(summary.chunks[i].hash, HASH_SIZE)]
119 = make_pair(block_id, i);
122 block_list.push_back(summary);
126 /* Signatures can be loaded lazily; this method should be called before any
127 * actual access to the chunk signatures is required, to ensure the data has
128 * actually been loaded. */
129 void Subfile::ensure_signatures_loaded()
131 if (checksums_loaded)
134 for (set<ObjectReference>::iterator i = old_blocks.begin();
135 i != old_blocks.end(); ++i) {
139 checksums_loaded = true;
142 void Subfile::analyze_new_block(const char *buf, size_t len)
146 int max_chunks = chunk_compute_max_num_breaks(len);
150 size_t *breakpoints = new size_t[max_chunks];
151 int num_breakpoints = chunk_compute_breaks(buf, len, breakpoints);
153 if (num_breakpoints == 0) {
154 delete[] breakpoints;
158 new_block_summary.num_chunks = num_breakpoints;
159 new_block_summary.chunks = new chunk_info[num_breakpoints];
162 for (int i = 0; i < num_breakpoints; i++) {
163 new_block_summary.chunks[i].offset = block_start;
164 new_block_summary.chunks[i].len = breakpoints[i] - block_start + 1;
165 block_start = breakpoints[i] + 1;
168 hash.process(&buf[new_block_summary.chunks[i].offset],
169 new_block_summary.chunks[i].len);
170 assert(hash.checksum_size() == (size_t)HASH_SIZE);
171 memcpy(new_block_summary.chunks[i].hash, hash.checksum(), HASH_SIZE);
174 new_block_summary_valid = true;
175 delete[] breakpoints;
178 void Subfile::store_block_signatures(ObjectReference ref, block_summary summary)
180 int n = summary.num_chunks;
181 char *packed = (char *)malloc(n * (2 + HASH_SIZE));
183 for (int i = 0; i < n; i++) {
184 assert(summary.chunks[i].len >= 0 && summary.chunks[i].len <= 0xffff);
185 uint16_t len = htons(summary.chunks[i].len);
186 char *packed_info = &packed[i * (2 + HASH_SIZE)];
187 memcpy(&packed_info[0], &len, 2);
188 memcpy(&packed_info[2], summary.chunks[i].hash, HASH_SIZE);
191 db->StoreChunkSignatures(ref, packed, n * (2 + HASH_SIZE),
197 void Subfile::store_analyzed_signatures(ObjectReference ref)
199 if (analyzed_len >= 16384)
200 store_block_signatures(ref, new_block_summary);
203 /* Compute an incremental representation of the most recent block analyzed. */
204 enum subfile_item_type { SUBFILE_COPY, SUBFILE_NEW };
206 struct subfile_item {
207 subfile_item_type type;
209 // For type SUBFILE_COPY
212 // For type SUBFILE_NEW
213 int src_offset, dst_offset;
215 char hash[Subfile::HASH_SIZE];
218 /* Compute an incremental representation of the data last analyzed. A list of
219 * references will be returned corresponding to the data. If new data must be
220 * written out to the backup, it will be written out via the LbsObject
221 * provided, to the provided TarSegmentStore. */
222 list<ObjectReference> Subfile::create_incremental(TarSegmentStore *tss,
226 assert(new_block_summary_valid);
227 bool matched_old = false;
230 list<subfile_item> items;
231 list<ObjectReference> refs;
233 ensure_signatures_loaded();
235 assert(new_block_summary.num_chunks > 0);
237 for (int i = 0; i < new_block_summary.num_chunks; i++) {
238 map<string, pair<int, int> >::iterator m
239 = chunk_index.find(string(new_block_summary.chunks[i].hash,
242 struct subfile_item item;
243 if (m == chunk_index.end()) {
244 item.type = SUBFILE_NEW;
245 item.src_offset = new_block_summary.chunks[i].offset;
246 item.dst_offset = new_data;
247 item.len = new_block_summary.chunks[i].len;
248 memcpy(item.hash, new_block_summary.chunks[i].hash, HASH_SIZE);
249 new_data += item.len;
251 struct chunk_info &old_chunk
252 = block_list[m->second.first].chunks[m->second.second];
253 item.type = SUBFILE_COPY;
254 item.ref = block_list[m->second.first].ref;
255 item.ref.set_range(old_chunk.offset, old_chunk.len);
259 items.push_back(item);
262 // No data was matched. The entire block can be written out as is into a
263 // new object, and the new_block_summary used to save chunk signatures.
265 o->set_age(block_age);
266 o->set_data(analyzed_buf, analyzed_len, NULL);
268 ObjectReference ref = o->get_ref();
269 store_analyzed_signatures(ref);
275 // Otherwise, construct a new block containing all literal data needed (if
276 // any exists), write it out, and construct the appropriate list of
278 list<subfile_item>::iterator i;
280 char *literal_buf = new char[new_data];
281 for (i = items.begin(); i != items.end(); ++i) {
282 if (i->type == SUBFILE_NEW) {
283 memcpy(&literal_buf[i->dst_offset],
284 &analyzed_buf[i->src_offset], i->len);
288 SHA1Checksum block_hash;
289 block_hash.process(literal_buf, new_data);
290 string block_csum = block_hash.checksum_str();
292 o->set_group("data");
293 o->set_data(literal_buf, new_data, NULL);
295 ObjectReference ref = o->get_ref();
296 for (i = items.begin(); i != items.end(); ++i) {
297 if (i->type == SUBFILE_NEW) {
299 i->ref.set_range(i->dst_offset, i->len);
303 //db->StoreObject(ref, 0.0);
305 block_summary summary;
307 summary.num_chunks = 0;
308 summary.chunks = new chunk_info[items.size()];
309 for (i = items.begin(); i != items.end(); ++i) {
310 if (i->type == SUBFILE_NEW) {
311 chunk_info &info = summary.chunks[summary.num_chunks];
312 memcpy(info.hash, i->hash, HASH_SIZE);
313 info.offset = i->dst_offset;
315 summary.num_chunks++;
319 store_block_signatures(ref, summary);
321 delete[] summary.chunks;
322 delete[] literal_buf;
328 for (i = items.begin(); i != items.end(); ++i) {
329 string refstr = i->ref.to_string();
330 if (!ref.merge(i->ref)) {
335 assert(!ref.is_null());