bstorage.c - dedup - deduplicating backup program
(HTM) git clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) Tags
(DIR) README
(DIR) LICENSE
---
bstorage.c (13644B)
---
1 /*
2 * Storage layer implementation using a single backing file.
3 * The file format is as follows:
4 *
5 * [block header]
6 * [block descriptor 0]
7 * [data]
8 * [block descriptor 1]
9 * [data]
10 * ...
11 */
12 #include <sys/types.h>
13 #include <sys/stat.h>
14
15 #include <assert.h>
16 #include <errno.h>
17 #include <fcntl.h>
18 #include <stdint.h>
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <strings.h>
23 #include <unistd.h>
24
25 #include "block.h"
26 #include "compat.h"
27 #include "config.h"
28 #include "misc.h"
29 #include "queue.h"
30 #include "tree.h"
31
32 /* block header constants */
33 #define BHDRMAGIC "DEDUPDIDUPDIDUP"
34 #define NBHDRMAGIC 16
35
36 #define VMIN 0
37 #define VMAJ 1
38 #define VMINMASK 0xff
39 #define VMAJSHIFT 8
40 #define VMAJMASK 0xff
41
42 #define BHDRSIZE (NBHDRMAGIC + 8 + 8)
43
44 /* block descriptor constants */
45 #define BDTYPE 0x100
46 #define BDSIZE (8 + 8 + 8 + 8 + (MDSIZE))
47
48 /* misc helpers */
49 extern int pack(unsigned char *, char *, ...);
50 extern int unpack(unsigned char *, char *, ...);
51
52 static int bscreat(struct bctx *, char *, int);
53 static int bsopen(struct bctx *, char *, int, int);
54 static int bsput(struct bctx *, void *, size_t, unsigned char *);
55 static int bsget(struct bctx *, unsigned char *, void *, size_t *);
56 static int bsrm(struct bctx *, unsigned char *);
57 static int bsgc(struct bctx *);
58 static int bssync(struct bctx *);
59 static int bsclose(struct bctx *);
60
61 static struct bops bops = {
62 .creat = bscreat,
63 .open = bsopen,
64 .put = bsput,
65 .get = bsget,
66 .rm = bsrm,
67 .gc = bsgc,
68 .sync = bssync,
69 .close = bsclose,
70 };
71
72 /* Block header structure */
73 struct bhdr {
74 char magic[NBHDRMAGIC]; /* magic number for file(1) */
75 uint64_t flags; /* version number */
76 uint64_t nbd; /* number of block descriptors */
77 };
78
79 /* Block descriptor */
80 struct bd {
81 uint16_t type; /* BDTYPE */
82 unsigned char reserved[6]; /* should be set to 0 when writing */
83 uint64_t offset; /* block offset */
84 uint64_t size; /* block size */
85 uint64_t refcnt; /* reference count of block, 0 if block is removed */
86 unsigned char md[MDSIZE]; /* hash of block */
87 RB_ENTRY(bd) rbe; /* bdcache link node */
88 SLIST_ENTRY(bd) sle; /* gchead link node */
89 };
90 RB_HEAD(bdcache, bd);
91
92 /* Storage layer context */
93 struct sctx {
94 struct bdcache bdcache; /* cache of block descriptors */
95 SLIST_HEAD(gchead, bd) gchead; /* list of all blocks with a zero refcount */
96 int fd; /* underlying storage file descriptor */
97 int rdonly; /* when set to 1, the bssync() operation is a no-op */
98 struct bhdr bhdr; /* block header */
99 };
100
101 static int
102 bd_cmp(struct bd *b1, struct bd *b2)
103 {
104 int r;
105
106 r = memcmp(b1->md, b2->md, MDSIZE);
107 if (r > 0)
108 return 1;
109 else if (r < 0)
110 return -1;
111 return 0;
112 }
113 static RB_PROTOTYPE(bdcache, bd, rbe, bd_cmp)
114 static RB_GENERATE(bdcache, bd, rbe, bd_cmp)
115
116 /* Unpack block header */
117 static int
118 unpackbhdr(unsigned char *buf, struct bhdr *bhdr)
119 {
120 char fmt[BUFSIZ];
121 int n;
122
123 snprintf(fmt, sizeof(fmt), "'%dqq", NBHDRMAGIC);
124 n = unpack(buf, fmt,
125 bhdr->magic,
126 &bhdr->flags,
127 &bhdr->nbd);
128
129 assert(n == BHDRSIZE);
130 return n;
131 }
132
133 /* Pack block header */
134 static int
135 packbhdr(unsigned char *buf, struct bhdr *bhdr)
136 {
137 char fmt[BUFSIZ];
138 int n;
139
140 snprintf(fmt, sizeof(fmt), "'%dqq", NBHDRMAGIC);
141 n = pack(buf, fmt,
142 bhdr->magic,
143 bhdr->flags,
144 bhdr->nbd);
145
146 assert(n == BHDRSIZE);
147 return n;
148 }
149
150 /* Unpack block descriptor */
151 static int
152 unpackbd(unsigned char *buf, struct bd *bd)
153 {
154 char fmt[BUFSIZ];
155 int n;
156
157 snprintf(fmt, sizeof(fmt), "s'6qqq'%d", MDSIZE);
158 n = unpack(buf, fmt,
159 &bd->type,
160 bd->reserved,
161 &bd->offset,
162 &bd->size,
163 &bd->refcnt,
164 bd->md);
165
166 assert(n == BDSIZE);
167 return n;
168 }
169
170 /* Write block descriptor */
171 static int
172 packbd(unsigned char *buf, struct bd *bd)
173 {
174 char fmt[BUFSIZ];
175 int n;
176
177 snprintf(fmt, sizeof(fmt), "s'6qqq'%d", MDSIZE);
178 n = pack(buf, fmt,
179 bd->type,
180 bd->reserved,
181 bd->offset,
182 bd->size,
183 bd->refcnt,
184 bd->md);
185
186 assert(n == BDSIZE);
187 return n;
188 }
189
190 /* Load block descriptor from file */
191 static int
192 loadbd(struct sctx *sctx)
193 {
194 unsigned char bdbuf[BDSIZE];
195 struct bd *bd;
196
197 bd = calloc(1, sizeof(*bd));
198 if (bd == NULL) {
199 seterr("calloc: out of memory");
200 return -1;
201 }
202
203 if (xread(sctx->fd, bdbuf, BDSIZE) != BDSIZE) {
204 free(bd);
205 seterr("failed to read block descriptor: %s",
206 strerror(errno));
207 return -1;
208 }
209 unpackbd(bdbuf, bd);
210
211 if (bd->type != BDTYPE) {
212 free(bd);
213 seterr("invalid block descriptor type: %d", bd->type);
214 return -1;
215 }
216
217 /* Move to the next block descriptor */
218 if (lseek(sctx->fd, bd->size, SEEK_CUR) < 0) {
219 free(bd);
220 seterr("lseek: %s", strerror(errno));
221 return -1;
222 }
223
224 /*
225 * When refcount is 0 the block has been removed.
226 * In that case, the block descriptor is still present
227 * in the file as it is used to locate the next block
228 * descriptor which could be live.
229 *
230 * The garbage collection list links together all block
231 * descriptors that have a reference count of 0.
232 * This is needed to implement the gc operation.
233 */
234 if (bd->refcnt > 0)
235 RB_INSERT(bdcache, &sctx->bdcache, bd);
236 else
237 SLIST_INSERT_HEAD(&sctx->gchead, bd, sle);
238 return 0;
239 }
240
241 /* Initialize block descriptor cache */
242 static int
243 initbdcache(struct sctx *sctx)
244 {
245 struct bhdr *bhdr;
246 uint64_t i;
247
248 bhdr = &sctx->bhdr;
249 for (i = 0; i < bhdr->nbd; i++) {
250 struct bd *bd, *tmp;
251
252 if (loadbd(sctx) == 0)
253 continue;
254
255 /* Free block descriptor cache */
256 RB_FOREACH_SAFE(bd, bdcache, &sctx->bdcache, tmp) {
257 RB_REMOVE(bdcache, &sctx->bdcache, bd);
258 free(bd);
259 }
260
261 /* Free garbage collector list */
262 while (!SLIST_EMPTY(&sctx->gchead)) {
263 bd = SLIST_FIRST(&sctx->gchead);
264 SLIST_REMOVE(&sctx->gchead, bd, bd, sle);
265 free(bd);
266 }
267 return -1;
268 }
269 return 0;
270 }
271
272 /* Create storage file */
273 static int
274 bscreat(struct bctx *bctx, char *path, int mode)
275 {
276 unsigned char bhdrbuf[BHDRSIZE];
277 struct sctx *sctx;
278 struct bhdr *bhdr;
279 int fd;
280
281 fd = open(path, O_RDWR | O_CREAT | O_EXCL, mode);
282 if (fd < 0) {
283 seterr("open: %s", strerror(errno));
284 return -1;
285 }
286
287 bctx->sctx = calloc(1, sizeof(struct sctx));
288 if (bctx->sctx == NULL) {
289 close(fd);
290 seterr("calloc: out of memory");
291 return -1;
292 }
293
294 sctx = bctx->sctx;
295 RB_INIT(&sctx->bdcache);
296 SLIST_INIT(&sctx->gchead);
297 sctx->fd = fd;
298
299 bhdr = &sctx->bhdr;
300 memcpy(bhdr->magic, BHDRMAGIC, NBHDRMAGIC);
301 bhdr->flags = (VMAJ << VMAJSHIFT) | VMIN;
302 bhdr->nbd = 0;
303
304 packbhdr(bhdrbuf, bhdr);
305 if (xwrite(fd, bhdrbuf, BHDRSIZE) != BHDRSIZE) {
306 free(sctx);
307 close(fd);
308 seterr("failed to write block header: %s", strerror(errno));
309 return -1;
310 }
311 return 0;
312 }
313
314 /* Open storage file */
315 static int
316 bsopen(struct bctx *bctx, char *path, int flags, int mode)
317 {
318 unsigned char bhdrbuf[BHDRSIZE];
319 struct sctx *sctx;
320 struct bhdr *bhdr;
321 int fd;
322
323 switch (flags) {
324 case B_READ:
325 flags = O_RDONLY;
326 break;
327 case B_RDWR:
328 flags = O_RDWR;
329 break;
330 default:
331 seterr("invalid params");
332 return -1;
333 }
334
335 fd = open(path, flags, mode);
336 if (fd < 0) {
337 seterr("open: %s", strerror(errno));
338 return -1;
339 }
340
341 bctx->sctx = calloc(1, sizeof(struct sctx));
342 if (bctx->sctx == NULL) {
343 close(fd);
344 seterr("calloc: out of memory");
345 return -1;
346 }
347
348 sctx = bctx->sctx;
349 RB_INIT(&sctx->bdcache);
350 SLIST_INIT(&sctx->gchead);
351 bhdr = &sctx->bhdr;
352
353 if (xread(fd, bhdrbuf, BHDRSIZE) != BHDRSIZE) {
354 free(sctx);
355 close(fd);
356 seterr("failed to read block header: %s", strerror(errno));
357 return -1;
358 }
359 unpackbhdr(bhdrbuf, bhdr);
360
361 if (memcmp(bhdr->magic, BHDRMAGIC, NBHDRMAGIC) != 0) {
362 free(sctx);
363 close(fd);
364 seterr("unknown block header magic");
365 return -1;
366 }
367
368 /* If the major version is different, the format is incompatible */
369 if (((bhdr->flags >> VMAJSHIFT) & VMAJMASK) != VMAJ) {
370 free(sctx);
371 close(fd);
372 seterr("block header version mismatch");
373 return -1;
374 }
375
376 sctx->fd = fd;
377 sctx->rdonly = flags == O_RDONLY;
378
379 if (initbdcache(sctx) < 0) {
380 free(sctx);
381 close(fd);
382 return -1;
383 }
384 return 0;
385 }
386
387 /* Write a block to the storage file */
388 static int
389 bsput(struct bctx *bctx, void *buf, size_t n, unsigned char *md)
390 {
391 unsigned char bdbuf[BDSIZE];
392 struct sctx *sctx;
393 struct bhdr *bhdr;
394 struct bd key, *bd;
395 off_t offs;
396
397 /*
398 * If the block is already present in the cache
399 * just increment the reference count and write back
400 * the block descriptor associated with that block.
401 */
402 sctx = bctx->sctx;
403 memcpy(key.md, md, MDSIZE);
404 bd = RB_FIND(bdcache, &sctx->bdcache, &key);
405 if (bd != NULL) {
406 off_t bdoffs;
407
408 bdoffs = bd->offset - BDSIZE;
409 if (lseek(sctx->fd, bdoffs, SEEK_SET) < 0) {
410 seterr("lseek: %s", strerror(errno));
411 return -1;
412 }
413
414 bd->refcnt++;
415 packbd(bdbuf, bd);
416 if (xwrite(sctx->fd, bdbuf, BDSIZE) != BDSIZE) {
417 bd->refcnt--;
418 seterr("failed to write block descriptor: %s",
419 strerror(errno));
420 return -1;
421 }
422
423 memcpy(md, bd->md, MDSIZE);
424 return 0;
425 }
426
427 /* New blocks are appended at the end of storage file */
428 offs = lseek(sctx->fd, 0, SEEK_END);
429 if (offs < 0) {
430 seterr("lseek: %s", strerror(errno));
431 return -1;
432 }
433
434 bd = calloc(1, sizeof(*bd));
435 if (bd == NULL) {
436 seterr("calloc: out of memory");
437 return -1;
438 }
439 bd->type = BDTYPE;
440 bd->offset = offs + BDSIZE;
441 bd->size = n;
442 bd->refcnt = 1;
443 memcpy(bd->md, key.md, MDSIZE);
444
445 packbd(bdbuf, bd);
446 if (xwrite(sctx->fd, bdbuf, BDSIZE) != BDSIZE) {
447 /* Shouldn't fail but if it does rewind storage file state */
448 ftruncate(sctx->fd, offs);
449 free(bd);
450 seterr("failed to write block descriptor: %s",
451 strerror(errno));
452 return -1;
453 }
454
455 if (xwrite(sctx->fd, buf, n) != n) {
456 /* Shouldn't fail but if it does rewind storage file state */
457 ftruncate(sctx->fd, offs);
458 free(bd);
459 seterr("failed to write block: %s", strerror(errno));
460 return -1;
461 }
462
463 /*
464 * Update block entry header.
465 * The header will be written to the storage file
466 * when bsclose() or bssync() is called.
467 */
468 bhdr = &sctx->bhdr;
469 bhdr->nbd++;
470
471 RB_INSERT(bdcache, &sctx->bdcache, bd);
472 memcpy(md, bd->md, MDSIZE);
473 return bd->size;
474 }
475
476 /* Read a block from the storage file */
477 static int
478 bsget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n)
479 {
480 struct sctx *sctx;
481 struct bd key, *bd;
482
483 sctx = bctx->sctx;
484 memcpy(key.md, md, MDSIZE);
485 bd = RB_FIND(bdcache, &sctx->bdcache, &key);
486 if (bd == NULL) {
487 seterr("block not found");
488 return -1;
489 }
490
491 if (*n < bd->size) {
492 seterr("buffer too small");
493 return -1;
494 }
495
496 if (lseek(sctx->fd, bd->offset, SEEK_SET) < 0) {
497 seterr("lseek: %s", strerror(errno));
498 return -1;
499 }
500 if (xread(sctx->fd, buf, bd->size) != bd->size) {
501 seterr("failed to read block: %s", strerror(errno));
502 return -1;
503 }
504 *n = bd->size;
505 return 0;
506 }
507
508 /* Remove a block with the given hash */
509 static int
510 bsrm(struct bctx *bctx, unsigned char *md)
511 {
512 unsigned char bdbuf[BDSIZE];
513 struct sctx *sctx;
514 struct bd key, *bd;
515 off_t bdoffs;
516
517 sctx = bctx->sctx;
518 memcpy(key.md, md, MDSIZE);
519 bd = RB_FIND(bdcache, &sctx->bdcache, &key);
520 if (bd == NULL) {
521 seterr("block not found");
522 return -1;
523 }
524
525 bdoffs = bd->offset - BDSIZE;
526 if (lseek(sctx->fd, bdoffs, SEEK_SET) < 0) {
527 seterr("lseek: %s", strerror(errno));
528 return -1;
529 }
530
531 bd->refcnt--;
532 packbd(bdbuf, bd);
533 if (xwrite(sctx->fd, bdbuf, BDSIZE) != BDSIZE) {
534 bd->refcnt++;
535 seterr("failed to write block descriptor: %s",
536 strerror(errno));
537 return -1;
538 }
539
540 /* This block is still referenced so just return */
541 if (bd->refcnt > 0)
542 return 0;
543
544 if (punchhole(sctx->fd, bd->offset, bd->size) < 0) {
545 /*
546 * Filesystem does not support hole punching.
547 * Restore reference count.
548 */
549 lseek(sctx->fd, bdoffs, SEEK_SET);
550 bd->refcnt++;
551 packbd(bdbuf, bd);
552 xwrite(sctx->fd, bdbuf, BDSIZE);
553 seterr("operation not supported");
554 return -1;
555 }
556
557 /*
558 * Remove block from block descriptor cache as this is no
559 * longer a valid block. Insert it into the garbage collector
560 * list instead.
561 */
562 RB_REMOVE(bdcache, &sctx->bdcache, bd);
563 SLIST_INSERT_HEAD(&sctx->gchead, bd, sle);
564 return 0;
565 }
566
567 /*
568 * Re-punch all holes in the storage file.
569 * This is needed when the storage file is copied from
570 * one system to another and back. The target system
571 * may not support hole punching so the holes will be
572 * filled with literal zeroes, negating the space saving
573 * effects.
574 */
575 static int
576 bsgc(struct bctx *bctx)
577 {
578 struct sctx *sctx;
579 struct bd *bd;
580
581 sctx = bctx->sctx;
582 SLIST_FOREACH(bd, &sctx->gchead, sle) {
583 assert(bd->refcnt == 0);
584 punchhole(sctx->fd, bd->offset, bd->size);
585 }
586 return 0;
587 }
588
589 /* Sync block header to storage file */
590 static int
591 bssync(struct bctx *bctx)
592 {
593 unsigned char bhdrbuf[BHDRSIZE];
594 struct sctx *sctx;
595 struct bhdr *bhdr;
596
597 sctx = bctx->sctx;
598 if (sctx->rdonly)
599 return 0;
600
601 if (lseek(sctx->fd, 0, SEEK_SET) < 0) {
602 seterr("lseek: %s", strerror(errno));
603 return -1;
604 }
605
606 bhdr = &sctx->bhdr;
607 packbhdr(bhdrbuf, bhdr);
608 if (xwrite(sctx->fd, bhdrbuf, BHDRSIZE) != BHDRSIZE) {
609 seterr("failed to write block header: %s", strerror(errno));
610 return -1;
611 }
612 fsync(sctx->fd);
613 return 0;
614 }
615
616 /* Close storage handle */
617 static int
618 bsclose(struct bctx *bctx)
619 {
620 struct sctx *sctx;
621 struct bd *bd, *tmp;
622 int r;
623
624 /* Free block descriptor cache */
625 sctx = bctx->sctx;
626 RB_FOREACH_SAFE(bd, bdcache, &sctx->bdcache, tmp) {
627 RB_REMOVE(bdcache, &sctx->bdcache, bd);
628 free(bd);
629 }
630
631 /* Free garbage collector list */
632 while (!SLIST_EMPTY(&sctx->gchead)) {
633 bd = SLIST_FIRST(&sctx->gchead);
634 SLIST_REMOVE(&sctx->gchead, bd, bd, sle);
635 free(bd);
636 }
637
638 r = close(sctx->fd);
639 free(sctx);
640 if (r < 0)
641 seterr("close: %s", strerror(errno));
642 return r;
643 }
644
645 struct bops *
646 bstorageops(void)
647 {
648 return &bops;
649 }