iChange cache consistency algorithm - dedup - deduplicating backup program Err bitreich.org 70 hgit clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ URL:git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ bitreich.org 70 1Log /scm/dedup/log.gph bitreich.org 70 1Files /scm/dedup/files.gph bitreich.org 70 1Refs /scm/dedup/refs.gph bitreich.org 70 1Tags /scm/dedup/tag bitreich.org 70 1README /scm/dedup/file/README.gph bitreich.org 70 1LICENSE /scm/dedup/file/LICENSE.gph bitreich.org 70 i--- Err bitreich.org 70 1commit df98cd4221d5e54c88d5ce172690c6cc7cb08235 /scm/dedup/commit/df98cd4221d5e54c88d5ce172690c6cc7cb08235.gph bitreich.org 70 1parent 13ea526261fd0d7821dbf271bd9ccd509ae4e6fd /scm/dedup/commit/13ea526261fd0d7821dbf271bd9ccd509ae4e6fd.gph bitreich.org 70 hAuthor: sin URL:mailto:sin@2f30.org bitreich.org 70 iDate: Tue, 5 Mar 2019 22:39:08 +0000 Err bitreich.org 70 i Err bitreich.org 70 iChange cache consistency algorithm Err bitreich.org 70 i Err bitreich.org 70 iInstead of doing complicated comparisons between snapshot blocks and Err bitreich.org 70 icache entries, just store the hash of all cache entries in the Err bitreich.org 70 isnapshot header. When the cache is loaded, the hash is calculated and Err bitreich.org 70 icompared against the one in the snapshot header. If they are Err bitreich.org 70 idifferent, a cache rebuild is triggered. Err bitreich.org 70 i Err bitreich.org 70 iDiffstat: Err bitreich.org 70 i M cache.c | 5 +++-- Err bitreich.org 70 i M dedup.c | 127 +++++++++---------------------- Err bitreich.org 70 i M dedup.h | 8 +++++--- Err bitreich.org 70 i M types.c | 14 ++++++++++---- Err bitreich.org 70 i Err bitreich.org 70 i4 files changed, 53 insertions(+), 101 deletions(-) Err bitreich.org 70 i--- Err bitreich.org 70 1diff --git a/cache.c b/cache.c /scm/dedup/file/cache.c.gph bitreich.org 70 i@@ -102,10 +102,11 @@ lookup_cache_entry(struct cache *cache, struct cache_entry *ent) Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i void Err bitreich.org 70 i-walk_cache(struct cache *cache, int (*fn)(struct cache_entry *)) Err bitreich.org 70 i+walk_cache(struct cache *cache, Err bitreich.org 70 i+ int (*fn)(struct cache_entry *, void *), void *arg) Err bitreich.org 70 i { Err bitreich.org 70 i struct cache_node *node; Err bitreich.org 70 i Err bitreich.org 70 i RB_FOREACH(node, cache_head, &cache->nodes) Err bitreich.org 70 i- (*fn)(&node->ent); Err bitreich.org 70 i+ (*fn)(&node->ent, arg); Err bitreich.org 70 i } Err bitreich.org 70 1diff --git a/dedup.c b/dedup.c /scm/dedup/file/dedup.c.gph bitreich.org 70 i@@ -37,7 +37,6 @@ static struct cache *cache; Err bitreich.org 70 i static int ifd; Err bitreich.org 70 i static int sfd; Err bitreich.org 70 i static int cfd; Err bitreich.org 70 i-static int cache_dirty; Err bitreich.org 70 i static unsigned long long cache_hits; Err bitreich.org 70 i static unsigned long long cache_misses; Err bitreich.org 70 i Err bitreich.org 70 i@@ -253,7 +252,6 @@ dedup_chunk(struct snapshot *snap, uint8_t *chunkp, size_t chunk_size) Err bitreich.org 70 i Err bitreich.org 70 i cache_entry.offset = blk_desc.offset; Err bitreich.org 70 i cache_entry.size = blk_desc.size; Err bitreich.org 70 i- cache_dirty = 1; Err bitreich.org 70 i add_cache_entry(cache, &cache_entry); Err bitreich.org 70 i cache_misses++; Err bitreich.org 70 i Err bitreich.org 70 i@@ -396,40 +394,10 @@ check_snap(struct snapshot *snap, void *arg) Err bitreich.org 70 i return WALK_CONTINUE; Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i-/* Err bitreich.org 70 i- * For each block descriptor within each snapshot, do a lookup Err bitreich.org 70 i- * of the block descriptor hash in the cache. If the lookup fails Err bitreich.org 70 i- * the cache is corrupted. The caller will rebuild the cache in Err bitreich.org 70 i- * that case. Err bitreich.org 70 i- */ Err bitreich.org 70 i-static int Err bitreich.org 70 i-check_cache_entry(struct snapshot *snap, void *arg) Err bitreich.org 70 i-{ Err bitreich.org 70 i- int *ret = arg; Err bitreich.org 70 i- uint64_t i; Err bitreich.org 70 i- Err bitreich.org 70 i- for (i = 0; i < snap->nr_blk_descs; i++) { Err bitreich.org 70 i- struct blk_desc *blk_desc; Err bitreich.org 70 i- struct cache_entry cache_entry; Err bitreich.org 70 i- Err bitreich.org 70 i- blk_desc = &snap->blk_desc[i]; Err bitreich.org 70 i- memcpy(&cache_entry.md, blk_desc->md, sizeof(cache_entry.md)); Err bitreich.org 70 i- if (lookup_cache_entry(cache, &cache_entry) < 0 || Err bitreich.org 70 i- cache_entry.offset != blk_desc->offset || Err bitreich.org 70 i- cache_entry.size != blk_desc->size) { Err bitreich.org 70 i- *ret = -1; Err bitreich.org 70 i- return WALK_STOP; Err bitreich.org 70 i- } Err bitreich.org 70 i- } Err bitreich.org 70 i- return WALK_CONTINUE; Err bitreich.org 70 i-} Err bitreich.org 70 i- Err bitreich.org 70 i static int Err bitreich.org 70 i reload_cache(struct snapshot *snap, void *arg) Err bitreich.org 70 i { Err bitreich.org 70 i- uint8_t md[MDSIZE]; Err bitreich.org 70 i uint8_t *buf; Err bitreich.org 70 i- SHA256_CTX ctx; Err bitreich.org 70 i uint64_t i; Err bitreich.org 70 i Err bitreich.org 70 i buf = alloc_buf(compr_size(BLKSIZE_MAX)); Err bitreich.org 70 i@@ -438,19 +406,12 @@ reload_cache(struct snapshot *snap, void *arg) Err bitreich.org 70 i struct blk_desc *blk_desc; Err bitreich.org 70 i Err bitreich.org 70 i blk_desc = &snap->blk_desc[i]; Err bitreich.org 70 i- read_blk(buf, blk_desc); Err bitreich.org 70 i- Err bitreich.org 70 i- SHA256_Init(&ctx); Err bitreich.org 70 i- SHA256_Update(&ctx, buf, blk_desc->size); Err bitreich.org 70 i- SHA256_Final(md, &ctx); Err bitreich.org 70 i- Err bitreich.org 70 i memcpy(cache_entry.md, blk_desc->md, sizeof(cache_entry.md)); Err bitreich.org 70 i cache_entry.offset = blk_desc->offset; Err bitreich.org 70 i cache_entry.size = blk_desc->size; Err bitreich.org 70 i add_cache_entry(cache, &cache_entry); Err bitreich.org 70 i } Err bitreich.org 70 i free(buf); Err bitreich.org 70 i- cache_dirty = 1; Err bitreich.org 70 i return WALK_CONTINUE; Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i@@ -500,77 +461,59 @@ match_ver(uint64_t v) Err bitreich.org 70 i VER_MAJ, VER_MIN, maj, min); Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i-static uint64_t Err bitreich.org 70 i-cache_nr_entries(void) Err bitreich.org 70 i+static void Err bitreich.org 70 i+hash_cache_entry_update(struct cache_entry *cache_entry, SHA256_CTX *ctx) Err bitreich.org 70 i { Err bitreich.org 70 i- struct stat sb; Err bitreich.org 70 i+ uint8_t buf[CACHE_ENTRY_SIZE]; Err bitreich.org 70 i+ char fmt[BUFSIZ]; Err bitreich.org 70 i+ int n; Err bitreich.org 70 i Err bitreich.org 70 i- if (fstat(cfd, &sb) < 0) Err bitreich.org 70 i- err(1, "fstat"); Err bitreich.org 70 i- return sb.st_size / CACHE_ENTRY_SIZE; Err bitreich.org 70 i+ snprintf(fmt, sizeof(fmt), "'%dqq", MDSIZE); Err bitreich.org 70 i+ n = pack(buf, fmt, cache_entry->md, cache_entry->offset, Err bitreich.org 70 i+ cache_entry->size); Err bitreich.org 70 i+ SHA256_Update(ctx, buf, n); Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i static void Err bitreich.org 70 i-check_cache(void) Err bitreich.org 70 i+load_cache(void) Err bitreich.org 70 i { Err bitreich.org 70 i- int ret; Err bitreich.org 70 i+ uint8_t md[MDSIZE]; Err bitreich.org 70 i+ struct stat sb; Err bitreich.org 70 i+ SHA256_CTX ctx; Err bitreich.org 70 i+ uint64_t nr_entries, i; Err bitreich.org 70 i Err bitreich.org 70 i- if (verbose > 0) Err bitreich.org 70 i- fprintf(stderr, "Checking cache\n"); Err bitreich.org 70 i+ if (fstat(cfd, &sb) < 0) Err bitreich.org 70 i+ err(1, "fstat"); Err bitreich.org 70 i+ nr_entries = sb.st_size / CACHE_ENTRY_SIZE; Err bitreich.org 70 i Err bitreich.org 70 i- if (cache_nr_entries() != snap_hdr.st.nr_blks) { Err bitreich.org 70 i- ret = -1; Err bitreich.org 70 i- } else { Err bitreich.org 70 i- xlseek(ifd, SNAP_HDR_SIZE, SEEK_SET); Err bitreich.org 70 i- ret = 0; Err bitreich.org 70 i- walk_snap(check_cache_entry, &ret); Err bitreich.org 70 i+ xlseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i+ SHA256_Init(&ctx); Err bitreich.org 70 i+ for (i = 0; i < nr_entries; i++) { Err bitreich.org 70 i+ struct cache_entry cache_entry; Err bitreich.org 70 i+ Err bitreich.org 70 i+ read_cache_entry(cfd, &cache_entry); Err bitreich.org 70 i+ hash_cache_entry_update(&cache_entry, &ctx); Err bitreich.org 70 i+ add_cache_entry(cache, &cache_entry); Err bitreich.org 70 i } Err bitreich.org 70 i+ SHA256_Final(md, &ctx); Err bitreich.org 70 i Err bitreich.org 70 i- if (ret != 0) { Err bitreich.org 70 i+ if (memcmp(snap_hdr.cache_md, md, sizeof(snap_hdr.cache_md)) != 0) { Err bitreich.org 70 i if (verbose > 0) Err bitreich.org 70 i fprintf(stderr, "Rebuilding cache\n"); Err bitreich.org 70 i- Err bitreich.org 70 i free_cache(cache); Err bitreich.org 70 i cache = alloc_cache(); Err bitreich.org 70 i- Err bitreich.org 70 i if (ftruncate(cfd, 0) < 0) Err bitreich.org 70 i err(1, "ftruncate"); Err bitreich.org 70 i- Err bitreich.org 70 i xlseek(ifd, SNAP_HDR_SIZE, SEEK_SET); Err bitreich.org 70 i xlseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i walk_snap(reload_cache, NULL); Err bitreich.org 70 i } Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i-static void Err bitreich.org 70 i-load_cache(void) Err bitreich.org 70 i-{ Err bitreich.org 70 i- uint64_t nr_entries; Err bitreich.org 70 i- uint64_t i; Err bitreich.org 70 i- Err bitreich.org 70 i- xlseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i- nr_entries = cache_nr_entries(); Err bitreich.org 70 i- if (nr_entries != snap_hdr.st.nr_blks) { Err bitreich.org 70 i- if (verbose > 0) Err bitreich.org 70 i- fprintf(stderr, "Rebuilding cache\n"); Err bitreich.org 70 i- if (ftruncate(cfd, 0) < 0) Err bitreich.org 70 i- err(1, "ftruncate"); Err bitreich.org 70 i- xlseek(ifd, SNAP_HDR_SIZE, SEEK_SET); Err bitreich.org 70 i- walk_snap(reload_cache, NULL); Err bitreich.org 70 i- return; Err bitreich.org 70 i- } Err bitreich.org 70 i- Err bitreich.org 70 i- for (i = 0; i < nr_entries; i++) { Err bitreich.org 70 i- struct cache_entry cache_entry; Err bitreich.org 70 i- Err bitreich.org 70 i- read_cache_entry(cfd, &cache_entry); Err bitreich.org 70 i- add_cache_entry(cache, &cache_entry); Err bitreich.org 70 i- } Err bitreich.org 70 i-} Err bitreich.org 70 i- Err bitreich.org 70 i static int Err bitreich.org 70 i-flush_cache(struct cache_entry *cache_entry) Err bitreich.org 70 i+flush_cache(struct cache_entry *cache_entry, void *arg) Err bitreich.org 70 i { Err bitreich.org 70 i+ hash_cache_entry_update(cache_entry, arg); Err bitreich.org 70 i write_cache_entry(cfd, cache_entry); Err bitreich.org 70 i return 0; Err bitreich.org 70 i } Err bitreich.org 70 i@@ -578,10 +521,12 @@ flush_cache(struct cache_entry *cache_entry) Err bitreich.org 70 i static void Err bitreich.org 70 i save_cache(void) Err bitreich.org 70 i { Err bitreich.org 70 i- if (cache_dirty) { Err bitreich.org 70 i- xlseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i- walk_cache(cache, flush_cache); Err bitreich.org 70 i- } Err bitreich.org 70 i+ SHA256_CTX ctx; Err bitreich.org 70 i+ Err bitreich.org 70 i+ SHA256_Init(&ctx); Err bitreich.org 70 i+ xlseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i+ walk_cache(cache, flush_cache, &ctx); Err bitreich.org 70 i+ SHA256_Final(snap_hdr.cache_md, &ctx); Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i static void Err bitreich.org 70 i@@ -784,8 +729,6 @@ main(int argc, char *argv[]) Err bitreich.org 70 i if (ret != 0) Err bitreich.org 70 i errx(1, "%s or %s is corrupted", SNAPSF, STOREF); Err bitreich.org 70 i Err bitreich.org 70 i- check_cache(); Err bitreich.org 70 i- Err bitreich.org 70 i term(); Err bitreich.org 70 i return 0; Err bitreich.org 70 i } Err bitreich.org 70 1diff --git a/dedup.h b/dedup.h /scm/dedup/file/dedup.h.gph bitreich.org 70 i@@ -6,7 +6,7 @@ Err bitreich.org 70 i * using the helpers from types.c. Any modification made to Err bitreich.org 70 i * the structs below will need to be reflected here and in types.c. Err bitreich.org 70 i */ Err bitreich.org 70 i-#define SNAP_HDR_SIZE 104 Err bitreich.org 70 i+#define SNAP_HDR_SIZE 136 Err bitreich.org 70 i #define BLK_HDR_SIZE 16 Err bitreich.org 70 i #define BLK_DESC_SIZE 48 Err bitreich.org 70 i #define SNAPSHOT_SIZE 304 Err bitreich.org 70 i@@ -16,7 +16,7 @@ Err bitreich.org 70 i #define MDSIZE 32 Err bitreich.org 70 i Err bitreich.org 70 i /* file format version */ Err bitreich.org 70 i-#define VER_MIN 2 Err bitreich.org 70 i+#define VER_MIN 3 Err bitreich.org 70 i #define VER_MAJ 0 Err bitreich.org 70 i Err bitreich.org 70 i #define VER_MIN_MASK 0xff Err bitreich.org 70 i@@ -43,6 +43,7 @@ struct snapshot_hdr { Err bitreich.org 70 i uint64_t flags; /* bottom 16 bits are maj/min version */ Err bitreich.org 70 i uint64_t size; /* size of snapshots file */ Err bitreich.org 70 i uint64_t nr_snapshots; Err bitreich.org 70 i+ uint8_t cache_md[MDSIZE]; Err bitreich.org 70 i struct stats st; Err bitreich.org 70 i }; Err bitreich.org 70 i Err bitreich.org 70 i@@ -82,7 +83,8 @@ struct cache *alloc_cache(void); Err bitreich.org 70 i void free_cache(struct cache *cache); Err bitreich.org 70 i void add_cache_entry(struct cache *cache, struct cache_entry *ent); Err bitreich.org 70 i int lookup_cache_entry(struct cache *cache, struct cache_entry *ent); Err bitreich.org 70 i-void walk_cache(struct cache *cache, int (*fn)(struct cache_entry *)); Err bitreich.org 70 i+void walk_cache(struct cache *cache, Err bitreich.org 70 i+ int (*fn)(struct cache_entry *, void *), void *arg); Err bitreich.org 70 i Err bitreich.org 70 i /* chunker.c */ Err bitreich.org 70 i struct chunker *alloc_chunker(int fd, size_t cap); Err bitreich.org 70 1diff --git a/types.c b/types.c /scm/dedup/file/types.c.gph bitreich.org 70 i@@ -10,15 +10,18 @@ void Err bitreich.org 70 i read_snap_hdr(int fd, struct snapshot_hdr *hdr) Err bitreich.org 70 i { Err bitreich.org 70 i uint8_t buf[SNAP_HDR_SIZE]; Err bitreich.org 70 i+ char fmt[BUFSIZ]; Err bitreich.org 70 i int n; Err bitreich.org 70 i Err bitreich.org 70 i if (xread(fd, buf, sizeof(buf)) == 0) Err bitreich.org 70 i errx(1, "read_snap_hdr: unexpected EOF"); Err bitreich.org 70 i Err bitreich.org 70 i- n = unpack(buf, "qqq", Err bitreich.org 70 i+ snprintf(fmt, sizeof(fmt), "qqq'%d", MDSIZE); Err bitreich.org 70 i+ n = unpack(buf, fmt, Err bitreich.org 70 i &hdr->flags, Err bitreich.org 70 i &hdr->size, Err bitreich.org 70 i- &hdr->nr_snapshots); Err bitreich.org 70 i+ &hdr->nr_snapshots, Err bitreich.org 70 i+ hdr->cache_md); Err bitreich.org 70 i Err bitreich.org 70 i n += unpack(&buf[n], "qqqqqq", Err bitreich.org 70 i &hdr->st.orig_size, Err bitreich.org 70 i@@ -41,12 +44,15 @@ void Err bitreich.org 70 i write_snap_hdr(int fd, struct snapshot_hdr *hdr) Err bitreich.org 70 i { Err bitreich.org 70 i uint8_t buf[SNAP_HDR_SIZE]; Err bitreich.org 70 i+ char fmt[BUFSIZ]; Err bitreich.org 70 i int n; Err bitreich.org 70 i Err bitreich.org 70 i- n = pack(buf, "qqq", Err bitreich.org 70 i+ snprintf(fmt, sizeof(fmt), "qqq'%d", MDSIZE); Err bitreich.org 70 i+ n = pack(buf, fmt, Err bitreich.org 70 i hdr->flags, Err bitreich.org 70 i hdr->size, Err bitreich.org 70 i- hdr->nr_snapshots); Err bitreich.org 70 i+ hdr->nr_snapshots, Err bitreich.org 70 i+ hdr->cache_md); Err bitreich.org 70 i Err bitreich.org 70 i n += pack(&buf[n], "qqqqqq", Err bitreich.org 70 i hdr->st.orig_size, Err bitreich.org 70 .