dedup

deduplicating backup program
git clone git://git.2f30.org/dedup
Log | Files | Refs | README | LICENSE

commit 54776ab6b2b26aea19f77b7876e80cff4b602913
parent 3d79ba2671de814d94474dce3765be64a982cc5a
Author: sin <sin@2f30.org>
Date:   Thu, 25 Apr 2019 13:05:40 +0100

Rewrite dedup from scratch

The new design provides 3 abstractions.

 * The snapshot layer
 * The block layer
 * The chunker interface

The snapshot layer manages snapshots.  A snapshot is a collection of
block hashes.  Each snapshot is a separate file in <repo>/archive/.
The name of the snapshot file is selected by the user.

The block layer is composed of 3 sub-layers.

  * Generic layer
  * Compression layer
  * Storage layer

The generic layer provides the top-level block interface and deals
with user provided buffers.  When a write goes through the generic
layer it is passed down to the compression layer which compresses the
payload, prepends a compression descriptor and passes it down to the
storage layer.

The storage layer hashes the payload and prepends a storage
descriptor.  The final buffer is written to the storage file.  The
storage layer also maintains a cache of hashes which is used to
determine if a block exists in the storage or not.

The chunker interface is basically unchanged.

Diffstat:
MMakefile | 115++++++++++++++-----------------------------------------------------------------
MREADME | 25++++++++-----------------
MTODO | 1-
Abcompress.c | 260+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dblake2bp-ref.c | 359-------------------------------------------------------------------------------
Dblake2s-ref.c | 367-------------------------------------------------------------------------------
Dblake2sp-ref.c | 359-------------------------------------------------------------------------------
Ablock.c | 114+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ablock.h | 34++++++++++++++++++++++++++++++++++
Abstorage.c | 564+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Mchunker.c | 174++++++++++++++++++++++++++++++++++++++++++++-----------------------------------
Achunker.h | 8++++++++
Dcompress-lz4.c | 54------------------------------------------------------
Dcompress-none.c | 41-----------------------------------------
Dcompress-snappy.c | 54------------------------------------------------------
Dcompress.c | 112-------------------------------------------------------------------------------
Mconfig.h | 11+++++++----
Mconfig.mk | 5+++--
Ddedup.h | 233-------------------------------------------------------------------------------
Ddup-check.1 | 25-------------------------
Ddup-check.c | 157-------------------------------------------------------------------------------
Ddup-info.1 | 37-------------------------------------
Ddup-info.c | 141-------------------------------------------------------------------------------
Mdup-init.1 | 6+++---
Mdup-init.c | 83+++++++++++++++----------------------------------------------------------------
Ddup-list.1 | 25-------------------------
Ddup-list.c | 113-------------------------------------------------------------------------------
Ddup-migrate | 28----------------------------
Ddup-migrate.1 | 26--------------------------
Mdup-pack.1 | 20++++++++++----------
Mdup-pack.c | 228++++++++++++++++++-------------------------------------------------------------
Mdup-unpack.1 | 17++++++++---------
Mdup-unpack.c | 170++++++++++++++++++++++++++++++++++---------------------------------------------
Dhash-blake2b.c | 26--------------------------
Dhash-blake2bp.c | 26--------------------------
Dhash-blake2s.c | 26--------------------------
Dhash-blake2sp.c | 26--------------------------
Dhash.c | 94-------------------------------------------------------------------------------
Dicache.c | 114-------------------------------------------------------------------------------
Aqueue.h | 534+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asnap.c | 249+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asnap.h | 8++++++++
Dtypes.c | 192-------------------------------------------------------------------------------
Dutils.c | 288-------------------------------------------------------------------------------
44 files changed, 2063 insertions(+), 3486 deletions(-)

diff --git a/Makefile b/Makefile @@ -1,143 +1,68 @@ include config.mk -VERSION = 1.0 -PREFIX = /usr/local -MANPREFIX = $(PREFIX)/man -BIN = dup-check dup-info dup-init dup-list dup-pack dup-unpack -SCRIPTS = dup-migrate - -MAN = \ - dup-check.1 \ - dup-info.1 \ - dup-init.1 \ - dup-list.1 \ - dup-migrate.1 \ - dup-pack.1 \ - dup-unpack.1 \ +BIN = dup-init dup-pack dup-unpack + +MAN = dup-init.1 dup-pack.1 dup-unpack.1 HDR = \ arg.h \ blake2-impl.h \ blake2.h \ + block.h \ + chunker.h \ config.h \ - dedup.h \ + queue.h \ + snap.h \ tree.h \ -SRC = \ - $(HDR) \ - blake2b-ref.c \ - blake2bp-ref.c \ - blake2s-ref.c \ - blake2sp-ref.c \ - chunker.c \ - compress-lz4.c \ - compress-none.c \ - compress-snappy.c \ - compress.c \ - dup-check.c \ - dup-info.c \ - dup-init.c \ - dup-list.c \ - dup-pack.c \ - dup-unpack.c \ - hash-blake2b.c \ - hash-blake2bp.c \ - hash-blake2s.c \ - hash-blake2sp.c \ - hash.c \ - icache.c \ - pack.c \ - types.c \ - unpack.c \ - utils.c \ - COMMOBJ = \ + bcompress.o \ blake2b-ref.o \ - blake2bp-ref.o \ - blake2s-ref.o \ - blake2sp-ref.o \ + block.o \ + bstorage.o \ chunker.o \ - compress-lz4.o \ - compress-none.o \ - compress-snappy.o \ - compress.o \ - hash-blake2b.o \ - hash-blake2bp.o \ - hash-blake2s.o \ - hash-blake2sp.o \ - hash.o \ - icache.o \ pack.o \ - types.o \ + snap.o \ unpack.o \ - utils.o \ -DCHECKOBJ = $(COMMOBJ) dup-check.o -DINFOOBJ = $(COMMOBJ) dup-info.o DINITOBJ = $(COMMOBJ) dup-init.o -DLISTOBJ = $(COMMOBJ) dup-list.o DPACKOBJ = $(COMMOBJ) dup-pack.o DUNPACKOBJ = $(COMMOBJ) dup-unpack.o -DISTFILES = \ - $(MAN) \ - $(SRC) \ - $(SCRIPTS) \ - CHANGELOG \ - LICENSE \ - Makefile \ - README \ - config.mk \ - -CFLAGS = -g -O2 -Wall $(OPENMPCFLAGS) -CPPFLAGS = -I/usr/local/include -D_FILE_OFFSET_BITS=64 -LDFLAGS = -L/usr/local/lib -LDLIBS = -llz4 -lsnappy $(OPENMPLDLIBS) +CPPFLAGS = -D_FILE_OFFSET_BITS=64 +LDLIBS = -llz4 -lsnappy all: $(BIN) -$(DCHECKOBJ) $(DINFOOBJ) $(DINITOBJ) $(DLISTOBJ) $(DPACKOBJ) $(DUNPACKOBJ): $(HDR) +$(DINITOBJ) $(DPACKOBJ) $(DUNPACKOBJ): $(HDR) clean: - rm -f $(DCHECKOBJ) $(DINFOOBJ) $(DINITOBJ) $(DLISTOBJ) $(DPACKOBJ) $(DUNPACKOBJ) $(BIN) dedup-$(VERSION).tar.gz + rm -f $(DINITOBJ) $(DPACKOBJ) $(DUNPACKOBJ) $(BIN) + rm -rf dedup-$(VERSION) dedup-$(VERSION).tar.gz install: all mkdir -p $(DESTDIR)$(PREFIX)/bin cp -f $(BIN) $(DESTDIR)$(PREFIX)/bin - cp -f $(SCRIPTS) $(DESTDIR)$(PREFIX)/bin mkdir -p $(DESTDIR)$(MANPREFIX)/man1 cp -f $(MAN) $(DESTDIR)$(MANPREFIX)/man1 uninstall: - cd $(DESTDIR)$(PREFIX)/bin && rm -f $(BIN) $(SCRIPTS) + cd $(DESTDIR)$(PREFIX)/bin && rm -f $(BIN) cd $(DESTDIR)$(MANPREFIX)/man1 && rm -f $(MAN) -dist: +dist: clean mkdir -p dedup-$(VERSION) - cp $(DISTFILES) dedup-$(VERSION) - tar -cf dedup-$(VERSION).tar dedup-$(VERSION) - gzip dedup-$(VERSION).tar - rm -rf dedup-$(VERSION) - -.PHONY: all clean install uninstall dist + cp `find . -maxdepth 1 -type f` dedup-$(VERSION) + tar -cf - dedup-$(VERSION) | gzip > dedup-$(VERSION).tar.gz .SUFFIXES: .c .o .c.o: $(CC) $(CPPFLAGS) $(CFLAGS) -c $< -dup-check: $(DCHECKOBJ) - $(CC) -o $@ $(DCHECKOBJ) $(LDFLAGS) $(LDLIBS) - -dup-info: $(DINFOOBJ) - $(CC) -o $@ $(DINFOOBJ) $(LDFLAGS) $(LDLIBS) - dup-init: $(DINITOBJ) $(CC) -o $@ $(DINITOBJ) $(LDFLAGS) $(LDLIBS) -dup-list: $(DLISTOBJ) - $(CC) -o $@ $(DLISTOBJ) $(LDFLAGS) $(LDLIBS) - dup-pack: $(DPACKOBJ) $(CC) -o $@ $(DPACKOBJ) $(LDFLAGS) $(LDLIBS) diff --git a/README b/README @@ -6,32 +6,25 @@ dedup is a simple data deduplication program. Getting started =============== -To use dedup you have to first initialize the repository. +To use dedup you have to first initialize the repository: dup-init repo -This will create .{snapshots,store} files in the repo directory. The -store file contains all the unique blocks. The snapshots file -contains all the revisions of files that have been deduplicated. +dup-init(1) will create a storage file and an archive directory inside +the repository. The storage file contains all the unique blocks of +the repository. The archive directory contains the snapshots. dedup only handles a single file at a time, so using tar is advised. For example, to dedup a directory tree you can invoke dup-pack(1) as follows: - tar -c ~/dir | dup-pack -m "$(date)" repo + tar -c ~/dir | dup-pack -r repo foo -The -m flag is used to attach an arbitrary message to the snapshot. +This will create a new snapshot called foo under repo/archive/. -To list all known revisions run: +To extract a snapshot: - dup-list repo - -You will get a list of hashes. Each hash corresponds to a single file -(in this case, a tar archive). - -To extract a file from the deduplicated store run: - - dup-unpack <hash> repo > snapshot.tar + dup-unpack -r repo foo > dir.tar Portability =========== @@ -41,9 +34,7 @@ dedup works on Linux, *BSD, macOS and possibly other UNIX-like systems. Dependencies ============ - - liblz4 - snappy - - libgomp (optional, see config.mk) Contact ======= diff --git a/TODO b/TODO @@ -1,4 +1,3 @@ Use a ring buffer in the chunker (avoid memmove() call) Create a library archive out of the blake2b files and link with it pledge/unveil support -Create libdedup diff --git a/bcompress.c b/bcompress.c @@ -0,0 +1,260 @@ +/* Compression layer implementation */ +#include <sys/types.h> +#include <sys/stat.h> + +#include <assert.h> +#include <fcntl.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include <snappy-c.h> + +#include "block.h" + +#define CDNONETYPE 0x200 +#define CDSNAPPYTYPE 0x201 +#define CDSIZE (8 + 8) + +extern int pack(unsigned char *dst, char *fmt, ...); +extern int unpack(unsigned char *src, char *fmt, ...); + +static int bccreat(struct bctx *bctx, char *path, int mode, struct bparam *bpar); +static int bcopen(struct bctx *bctx, char *path, int flags, int mode, struct bparam *bpar); +static int bcput(struct bctx *bctx, void *buf, size_t n, unsigned char *md); +static int bcget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n); +static int bcsync(struct bctx *bctx); +static int bcclose(struct bctx *bctx); + +static struct bops bops = { + .creat = bccreat, + .open = bcopen, + .put = bcput, + .get = bcget, + .sync = bcsync, + .close = bcclose, +}; + +struct cctx { + uint64_t type; +}; + +/* Compression descriptor */ +struct cd { + uint64_t type; + uint64_t size; +}; + +/* Read compression descriptor */ +static int +unpackcd(void *buf, struct cd *cd) +{ + int n; + + n = unpack(buf, "qq", + &cd->type, + &cd->size); + + assert(n == CDSIZE); + return n; +} + +/* Write compression descriptor */ +static int +packcd(void *buf, struct cd *cd) +{ + int n; + + n = pack(buf, "qq", + cd->type, + cd->size); + + assert(n == CDSIZE); + return n; +} + +static int +bccreat(struct bctx *bctx, char *path, int mode, struct bparam *bpar) +{ + struct cctx *cctx; + struct bops *bops; + int type; + + if (strcmp(bpar->calgo, "none") == 0) + type = CDNONETYPE; + else if (strcmp(bpar->calgo, "snappy") == 0) + type = CDSNAPPYTYPE; + else + return -1; + + bctx->cctx = calloc(1, sizeof(struct cctx)); + if (bctx->cctx == NULL) + return -1; + cctx = bctx->cctx; + cctx->type = type; + + bops = bstorageops(); + if (bops->creat(bctx, path, mode, bpar) < 0) { + free(cctx); + return -1; + } + return 0; +} + +static int +bcopen(struct bctx *bctx, char *path, int flags, int mode, struct bparam *bpar) +{ + struct cctx *cctx; + struct bops *bops; + + bctx->cctx = calloc(1, sizeof(struct cctx)); + if (bctx->cctx == NULL) + return -1; + cctx = bctx->cctx; + + bops = bstorageops(); + if (bops->open(bctx, path, flags, mode, bpar) < 0) { + free(cctx); + return -1; + } + + if (strcmp(bpar->calgo, "none") == 0) + cctx->type = CDNONETYPE; + else if (strcmp(bpar->calgo, "snappy") == 0) + cctx->type = CDSNAPPYTYPE; + else { + bops->close(bctx); + return -1; + } + return 0; +} + +static int +bcput(struct bctx *bctx, void *buf, size_t n, unsigned char *md) +{ + struct cctx *cctx; + struct bops *bops; + struct cd cd; + char *cbuf; + size_t cn; + + cctx = bctx->cctx; + switch (cctx->type) { + case CDNONETYPE: + cn = n; + cbuf = malloc(CDSIZE + cn); + if (cbuf == NULL) + return -1; + memcpy(&cbuf[CDSIZE], buf, cn); + break; + case CDSNAPPYTYPE: + cn = snappy_max_compressed_length(n); + cbuf = malloc(CDSIZE + cn); + if (cbuf == NULL) + return -1; + if (snappy_compress(buf, n, &cbuf[CDSIZE], &cn) != SNAPPY_OK) { + free(cbuf); + return -1; + } + break; + default: + return -1; + } + + /* Prepend compression descriptor */ + cd.type = cctx->type; + cd.size = cn; + packcd(cbuf, &cd); + + bops = bstorageops(); + if (bops->put(bctx, cbuf, CDSIZE + cn, md) < 0) { + free(cbuf); + return -1; + } + + free(cbuf); + return cd.size; +} + +static int +bcget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n) +{ + struct bops *bops; + struct cd cd; + char *cbuf; + size_t cn, un, size; + + size = *n; + cn = snappy_max_compressed_length(size); + if (cn > size) + size = cn; + size += CDSIZE; + cbuf = malloc(size); + if (cbuf == NULL) + return -1; + + bops = bstorageops(); + if (bops->get(bctx, md, cbuf, &size) < 0) { + free(cbuf); + return -1; + } + + unpackcd(cbuf, &cd); + switch (cd.type) { + case CDNONETYPE: + un = cd.size; + if (*n < un) { + free(cbuf); + return -1; + } + memcpy(buf, &cbuf[CDSIZE], un); + break; + case CDSNAPPYTYPE: + if (snappy_uncompressed_length(&cbuf[CDSIZE], cd.size, + &un) != SNAPPY_OK || *n < un) { + free(cbuf); + return -1; + } + + if (snappy_uncompress(&cbuf[CDSIZE], cd.size, buf, + &un) != SNAPPY_OK) { + free(cbuf); + return -1; + } + break; + default: + free(cbuf); + return -1; + } + + free(cbuf); + *n = un; + return 0; +} + +static int +bcsync(struct bctx *bctx) +{ + struct bops *bops = bstorageops(); + + return bops->sync(bctx); +} + +static int +bcclose(struct bctx *bctx) +{ + struct cctx *cctx = bctx->cctx; + struct bops *bops; + + free(cctx); + bops = bstorageops(); + return bops->close(bctx); +} + +struct bops * +bcompressops(void) +{ + return &bops; +} diff --git a/blake2bp-ref.c b/blake2bp-ref.c @@ -1,359 +0,0 @@ -/* - BLAKE2 reference source code package - reference C implementations - - Copyright 2012, Samuel Neves <sneves@dei.uc.pt>. You may use this under the - terms of the CC0, the OpenSSL Licence, or the Apache Public License 2.0, at - your option. The terms of these licenses can be found at: - - - CC0 1.0 Universal : http://creativecommons.org/publicdomain/zero/1.0 - - OpenSSL license : https://www.openssl.org/source/license.html - - Apache 2.0 : http://www.apache.org/licenses/LICENSE-2.0 - - More information about the BLAKE2 hash function can be found at - https://blake2.net. -*/ - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <stdint.h> - -#if defined(_OPENMP) -#include <omp.h> -#endif - -#include "blake2.h" -#include "blake2-impl.h" - -#define PARALLELISM_DEGREE 4 - -/* - blake2b_init_param defaults to setting the expecting output length - from the digest_length parameter block field. - - In some cases, however, we do not want this, as the output length - of these instances is given by inner_length instead. -*/ -static int blake2bp_init_leaf_param( blake2b_state *S, const blake2b_param *P ) -{ - int err = blake2b_init_param(S, P); - S->outlen = P->inner_length; - return err; -} - -static int blake2bp_init_leaf( blake2b_state *S, size_t outlen, size_t keylen, uint64_t offset ) -{ - blake2b_param P[1]; - P->digest_length = (uint8_t)outlen; - P->key_length = (uint8_t)keylen; - P->fanout = PARALLELISM_DEGREE; - P->depth = 2; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, offset ); - store32( &P->xof_length, 0 ); - P->node_depth = 0; - P->inner_length = BLAKE2B_OUTBYTES; - memset( P->reserved, 0, sizeof( P->reserved ) ); - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - return blake2bp_init_leaf_param( S, P ); -} - -static int blake2bp_init_root( blake2b_state *S, size_t outlen, size_t keylen ) -{ - blake2b_param P[1]; - P->digest_length = (uint8_t)outlen; - P->key_length = (uint8_t)keylen; - P->fanout = PARALLELISM_DEGREE; - P->depth = 2; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, 0 ); - store32( &P->xof_length, 0 ); - P->node_depth = 1; - P->inner_length = BLAKE2B_OUTBYTES; - memset( P->reserved, 0, sizeof( P->reserved ) ); - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - return blake2b_init_param( S, P ); -} - - -int blake2bp_init( blake2bp_state *S, size_t outlen ) -{ - size_t i; - - if( !outlen || outlen > BLAKE2B_OUTBYTES ) return -1; - - memset( S->buf, 0, sizeof( S->buf ) ); - S->buflen = 0; - S->outlen = outlen; - - if( blake2bp_init_root( S->R, outlen, 0 ) < 0 ) - return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2bp_init_leaf( S->S[i], outlen, 0, i ) < 0 ) return -1; - - S->R->last_node = 1; - S->S[PARALLELISM_DEGREE - 1]->last_node = 1; - return 0; -} - -int blake2bp_init_key( blake2bp_state *S, size_t outlen, const void *key, size_t keylen ) -{ - size_t i; - - if( !outlen || outlen > BLAKE2B_OUTBYTES ) return -1; - - if( !key || !keylen || keylen > BLAKE2B_KEYBYTES ) return -1; - - memset( S->buf, 0, sizeof( S->buf ) ); - S->buflen = 0; - S->outlen = outlen; - - if( blake2bp_init_root( S->R, outlen, keylen ) < 0 ) - return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2bp_init_leaf( S->S[i], outlen, keylen, i ) < 0 ) return -1; - - S->R->last_node = 1; - S->S[PARALLELISM_DEGREE - 1]->last_node = 1; - { - uint8_t block[BLAKE2B_BLOCKBYTES]; - memset( block, 0, BLAKE2B_BLOCKBYTES ); - memcpy( block, key, keylen ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2b_update( S->S[i], block, BLAKE2B_BLOCKBYTES ); - - secure_zero_memory( block, BLAKE2B_BLOCKBYTES ); /* Burn the key from stack */ - } - return 0; -} - - -int blake2bp_update( blake2bp_state *S, const void *pin, size_t inlen ) -{ - const unsigned char * in = (const unsigned char *)pin; - size_t left = S->buflen; - size_t fill = sizeof( S->buf ) - left; - size_t i; - - if( left && inlen >= fill ) - { - memcpy( S->buf + left, in, fill ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2b_update( S->S[i], S->buf + i * BLAKE2B_BLOCKBYTES, BLAKE2B_BLOCKBYTES ); - - in += fill; - inlen -= fill; - left = 0; - } - -#if defined(_OPENMP) - #pragma omp parallel shared(S), num_threads(PARALLELISM_DEGREE) -#else - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) -#endif - { -#if defined(_OPENMP) - size_t i = omp_get_thread_num(); -#endif - size_t inlen__ = inlen; - const unsigned char *in__ = ( const unsigned char * )in; - in__ += i * BLAKE2B_BLOCKBYTES; - - while( inlen__ >= PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES ) - { - blake2b_update( S->S[i], in__, BLAKE2B_BLOCKBYTES ); - in__ += PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES; - inlen__ -= PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES; - } - } - - in += inlen - inlen % ( PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES ); - inlen %= PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES; - - if( inlen > 0 ) - memcpy( S->buf + left, in, inlen ); - - S->buflen = left + inlen; - return 0; -} - -int blake2bp_final( blake2bp_state *S, void *out, size_t outlen ) -{ - uint8_t hash[PARALLELISM_DEGREE][BLAKE2B_OUTBYTES]; - size_t i; - - if(out == NULL || outlen < S->outlen) { - return -1; - } - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - { - if( S->buflen > i * BLAKE2B_BLOCKBYTES ) - { - size_t left = S->buflen - i * BLAKE2B_BLOCKBYTES; - - if( left > BLAKE2B_BLOCKBYTES ) left = BLAKE2B_BLOCKBYTES; - - blake2b_update( S->S[i], S->buf + i * BLAKE2B_BLOCKBYTES, left ); - } - - blake2b_final( S->S[i], hash[i], BLAKE2B_OUTBYTES ); - } - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2b_update( S->R, hash[i], BLAKE2B_OUTBYTES ); - - return blake2b_final( S->R, out, S->outlen ); -} - -int blake2bp( void *out, size_t outlen, const void *in, size_t inlen, const void *key, size_t keylen ) -{ - uint8_t hash[PARALLELISM_DEGREE][BLAKE2B_OUTBYTES]; - blake2b_state S[PARALLELISM_DEGREE][1]; - blake2b_state FS[1]; - size_t i; - - /* Verify parameters */ - if ( NULL == in && inlen > 0 ) return -1; - - if ( NULL == out ) return -1; - - if( NULL == key && keylen > 0 ) return -1; - - if( !outlen || outlen > BLAKE2B_OUTBYTES ) return -1; - - if( keylen > BLAKE2B_KEYBYTES ) return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2bp_init_leaf( S[i], outlen, keylen, i ) < 0 ) return -1; - - S[PARALLELISM_DEGREE - 1]->last_node = 1; /* mark last node */ - - if( keylen > 0 ) - { - uint8_t block[BLAKE2B_BLOCKBYTES]; - memset( block, 0, BLAKE2B_BLOCKBYTES ); - memcpy( block, key, keylen ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2b_update( S[i], block, BLAKE2B_BLOCKBYTES ); - - secure_zero_memory( block, BLAKE2B_BLOCKBYTES ); /* Burn the key from stack */ - } - -#if defined(_OPENMP) - #pragma omp parallel shared(S,hash), num_threads(PARALLELISM_DEGREE) -#else - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) -#endif - { -#if defined(_OPENMP) - size_t i = omp_get_thread_num(); -#endif - size_t inlen__ = inlen; - const unsigned char *in__ = ( const unsigned char * )in; - in__ += i * BLAKE2B_BLOCKBYTES; - - while( inlen__ >= PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES ) - { - blake2b_update( S[i], in__, BLAKE2B_BLOCKBYTES ); - in__ += PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES; - inlen__ -= PARALLELISM_DEGREE * BLAKE2B_BLOCKBYTES; - } - - if( inlen__ > i * BLAKE2B_BLOCKBYTES ) - { - const size_t left = inlen__ - i * BLAKE2B_BLOCKBYTES; - const size_t len = left <= BLAKE2B_BLOCKBYTES ? left : BLAKE2B_BLOCKBYTES; - blake2b_update( S[i], in__, len ); - } - - blake2b_final( S[i], hash[i], BLAKE2B_OUTBYTES ); - } - - if( blake2bp_init_root( FS, outlen, keylen ) < 0 ) - return -1; - - FS->last_node = 1; /* Mark as last node */ - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2b_update( FS, hash[i], BLAKE2B_OUTBYTES ); - - return blake2b_final( FS, out, outlen );; -} - -#if defined(BLAKE2BP_SELFTEST) -#include <string.h> -#include "blake2-kat.h" -int main( void ) -{ - uint8_t key[BLAKE2B_KEYBYTES]; - uint8_t buf[BLAKE2_KAT_LENGTH]; - size_t i, step; - - for( i = 0; i < BLAKE2B_KEYBYTES; ++i ) - key[i] = ( uint8_t )i; - - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - buf[i] = ( uint8_t )i; - - /* Test simple API */ - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - { - uint8_t hash[BLAKE2B_OUTBYTES]; - blake2bp( hash, BLAKE2B_OUTBYTES, buf, i, key, BLAKE2B_KEYBYTES ); - - if( 0 != memcmp( hash, blake2bp_keyed_kat[i], BLAKE2B_OUTBYTES ) ) - { - goto fail; - } - } - - /* Test streaming API */ - for(step = 1; step < BLAKE2B_BLOCKBYTES; ++step) { - for (i = 0; i < BLAKE2_KAT_LENGTH; ++i) { - uint8_t hash[BLAKE2B_OUTBYTES]; - blake2bp_state S; - uint8_t * p = buf; - size_t mlen = i; - int err = 0; - - if( (err = blake2bp_init_key(&S, BLAKE2B_OUTBYTES, key, BLAKE2B_KEYBYTES)) < 0 ) { - goto fail; - } - - while (mlen >= step) { - if ( (err = blake2bp_update(&S, p, step)) < 0 ) { - goto fail; - } - mlen -= step; - p += step; - } - if ( (err = blake2bp_update(&S, p, mlen)) < 0) { - goto fail; - } - if ( (err = blake2bp_final(&S, hash, BLAKE2B_OUTBYTES)) < 0) { - goto fail; - } - - if (0 != memcmp(hash, blake2bp_keyed_kat[i], BLAKE2B_OUTBYTES)) { - goto fail; - } - } - } - - puts( "ok" ); - return 0; -fail: - puts("error"); - return -1; -} -#endif diff --git a/blake2s-ref.c b/blake2s-ref.c @@ -1,367 +0,0 @@ -/* - BLAKE2 reference source code package - reference C implementations - - Copyright 2012, Samuel Neves <sneves@dei.uc.pt>. You may use this under the - terms of the CC0, the OpenSSL Licence, or the Apache Public License 2.0, at - your option. The terms of these licenses can be found at: - - - CC0 1.0 Universal : http://creativecommons.org/publicdomain/zero/1.0 - - OpenSSL license : https://www.openssl.org/source/license.html - - Apache 2.0 : http://www.apache.org/licenses/LICENSE-2.0 - - More information about the BLAKE2 hash function can be found at - https://blake2.net. -*/ - -#include <stdint.h> -#include <string.h> -#include <stdio.h> - -#include "blake2.h" -#include "blake2-impl.h" - -static const uint32_t blake2s_IV[8] = -{ - 0x6A09E667UL, 0xBB67AE85UL, 0x3C6EF372UL, 0xA54FF53AUL, - 0x510E527FUL, 0x9B05688CUL, 0x1F83D9ABUL, 0x5BE0CD19UL -}; - -static const uint8_t blake2s_sigma[10][16] = -{ - { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } , - { 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 } , - { 11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 } , - { 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 } , - { 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 } , - { 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 } , - { 12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 } , - { 13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 } , - { 6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 } , - { 10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13 , 0 } , -}; - -static void blake2s_set_lastnode( blake2s_state *S ) -{ - S->f[1] = (uint32_t)-1; -} - -/* Some helper functions, not necessarily useful */ -static int blake2s_is_lastblock( const blake2s_state *S ) -{ - return S->f[0] != 0; -} - -static void blake2s_set_lastblock( blake2s_state *S ) -{ - if( S->last_node ) blake2s_set_lastnode( S ); - - S->f[0] = (uint32_t)-1; -} - -static void blake2s_increment_counter( blake2s_state *S, const uint32_t inc ) -{ - S->t[0] += inc; - S->t[1] += ( S->t[0] < inc ); -} - -static void blake2s_init0( blake2s_state *S ) -{ - size_t i; - memset( S, 0, sizeof( blake2s_state ) ); - - for( i = 0; i < 8; ++i ) S->h[i] = blake2s_IV[i]; -} - -/* init2 xors IV with input parameter block */ -int blake2s_init_param( blake2s_state *S, const blake2s_param *P ) -{ - const unsigned char *p = ( const unsigned char * )( P ); - size_t i; - - blake2s_init0( S ); - - /* IV XOR ParamBlock */ - for( i = 0; i < 8; ++i ) - S->h[i] ^= load32( &p[i * 4] ); - - S->outlen = P->digest_length; - return 0; -} - - -/* Sequential blake2s initialization */ -int blake2s_init( blake2s_state *S, size_t outlen ) -{ - blake2s_param P[1]; - - /* Move interval verification here? */ - if ( ( !outlen ) || ( outlen > BLAKE2S_OUTBYTES ) ) return -1; - - P->digest_length = (uint8_t)outlen; - P->key_length = 0; - P->fanout = 1; - P->depth = 1; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, 0 ); - store16( &P->xof_length, 0 ); - P->node_depth = 0; - P->inner_length = 0; - /* memset(P->reserved, 0, sizeof(P->reserved) ); */ - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - return blake2s_init_param( S, P ); -} - -int blake2s_init_key( blake2s_state *S, size_t outlen, const void *key, size_t keylen ) -{ - blake2s_param P[1]; - - if ( ( !outlen ) || ( outlen > BLAKE2S_OUTBYTES ) ) return -1; - - if ( !key || !keylen || keylen > BLAKE2S_KEYBYTES ) return -1; - - P->digest_length = (uint8_t)outlen; - P->key_length = (uint8_t)keylen; - P->fanout = 1; - P->depth = 1; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, 0 ); - store16( &P->xof_length, 0 ); - P->node_depth = 0; - P->inner_length = 0; - /* memset(P->reserved, 0, sizeof(P->reserved) ); */ - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - - if( blake2s_init_param( S, P ) < 0 ) return -1; - - { - uint8_t block[BLAKE2S_BLOCKBYTES]; - memset( block, 0, BLAKE2S_BLOCKBYTES ); - memcpy( block, key, keylen ); - blake2s_update( S, block, BLAKE2S_BLOCKBYTES ); - secure_zero_memory( block, BLAKE2S_BLOCKBYTES ); /* Burn the key from stack */ - } - return 0; -} - -#define G(r,i,a,b,c,d) \ - do { \ - a = a + b + m[blake2s_sigma[r][2*i+0]]; \ - d = rotr32(d ^ a, 16); \ - c = c + d; \ - b = rotr32(b ^ c, 12); \ - a = a + b + m[blake2s_sigma[r][2*i+1]]; \ - d = rotr32(d ^ a, 8); \ - c = c + d; \ - b = rotr32(b ^ c, 7); \ - } while(0) - -#define ROUND(r) \ - do { \ - G(r,0,v[ 0],v[ 4],v[ 8],v[12]); \ - G(r,1,v[ 1],v[ 5],v[ 9],v[13]); \ - G(r,2,v[ 2],v[ 6],v[10],v[14]); \ - G(r,3,v[ 3],v[ 7],v[11],v[15]); \ - G(r,4,v[ 0],v[ 5],v[10],v[15]); \ - G(r,5,v[ 1],v[ 6],v[11],v[12]); \ - G(r,6,v[ 2],v[ 7],v[ 8],v[13]); \ - G(r,7,v[ 3],v[ 4],v[ 9],v[14]); \ - } while(0) - -static void blake2s_compress( blake2s_state *S, const uint8_t in[BLAKE2S_BLOCKBYTES] ) -{ - uint32_t m[16]; - uint32_t v[16]; - size_t i; - - for( i = 0; i < 16; ++i ) { - m[i] = load32( in + i * sizeof( m[i] ) ); - } - - for( i = 0; i < 8; ++i ) { - v[i] = S->h[i]; - } - - v[ 8] = blake2s_IV[0]; - v[ 9] = blake2s_IV[1]; - v[10] = blake2s_IV[2]; - v[11] = blake2s_IV[3]; - v[12] = S->t[0] ^ blake2s_IV[4]; - v[13] = S->t[1] ^ blake2s_IV[5]; - v[14] = S->f[0] ^ blake2s_IV[6]; - v[15] = S->f[1] ^ blake2s_IV[7]; - - ROUND( 0 ); - ROUND( 1 ); - ROUND( 2 ); - ROUND( 3 ); - ROUND( 4 ); - ROUND( 5 ); - ROUND( 6 ); - ROUND( 7 ); - ROUND( 8 ); - ROUND( 9 ); - - for( i = 0; i < 8; ++i ) { - S->h[i] = S->h[i] ^ v[i] ^ v[i + 8]; - } -} - -#undef G -#undef ROUND - -int blake2s_update( blake2s_state *S, const void *pin, size_t inlen ) -{ - const unsigned char * in = (const unsigned char *)pin; - if( inlen > 0 ) - { - size_t left = S->buflen; - size_t fill = BLAKE2S_BLOCKBYTES - left; - if( inlen > fill ) - { - S->buflen = 0; - memcpy( S->buf + left, in, fill ); /* Fill buffer */ - blake2s_increment_counter( S, BLAKE2S_BLOCKBYTES ); - blake2s_compress( S, S->buf ); /* Compress */ - in += fill; inlen -= fill; - while(inlen > BLAKE2S_BLOCKBYTES) { - blake2s_increment_counter(S, BLAKE2S_BLOCKBYTES); - blake2s_compress( S, in ); - in += BLAKE2S_BLOCKBYTES; - inlen -= BLAKE2S_BLOCKBYTES; - } - } - memcpy( S->buf + S->buflen, in, inlen ); - S->buflen += inlen; - } - return 0; -} - -int blake2s_final( blake2s_state *S, void *out, size_t outlen ) -{ - uint8_t buffer[BLAKE2S_OUTBYTES] = {0}; - size_t i; - - if( out == NULL || outlen < S->outlen ) - return -1; - - if( blake2s_is_lastblock( S ) ) - return -1; - - blake2s_increment_counter( S, ( uint32_t )S->buflen ); - blake2s_set_lastblock( S ); - memset( S->buf + S->buflen, 0, BLAKE2S_BLOCKBYTES - S->buflen ); /* Padding */ - blake2s_compress( S, S->buf ); - - for( i = 0; i < 8; ++i ) /* Output full hash to temp buffer */ - store32( buffer + sizeof( S->h[i] ) * i, S->h[i] ); - - memcpy( out, buffer, outlen ); - secure_zero_memory(buffer, sizeof(buffer)); - return 0; -} - -int blake2s( void *out, size_t outlen, const void *in, size_t inlen, const void *key, size_t keylen ) -{ - blake2s_state S[1]; - - /* Verify parameters */ - if ( NULL == in && inlen > 0 ) return -1; - - if ( NULL == out ) return -1; - - if ( NULL == key && keylen > 0) return -1; - - if( !outlen || outlen > BLAKE2S_OUTBYTES ) return -1; - - if( keylen > BLAKE2S_KEYBYTES ) return -1; - - if( keylen > 0 ) - { - if( blake2s_init_key( S, outlen, key, keylen ) < 0 ) return -1; - } - else - { - if( blake2s_init( S, outlen ) < 0 ) return -1; - } - - blake2s_update( S, ( const uint8_t * )in, inlen ); - blake2s_final( S, out, outlen ); - return 0; -} - -#if defined(SUPERCOP) -int crypto_hash( unsigned char *out, unsigned char *in, unsigned long long inlen ) -{ - return blake2s( out, BLAKE2S_OUTBYTES, in, inlen, NULL, 0 ); -} -#endif - -#if defined(BLAKE2S_SELFTEST) -#include <string.h> -#include "blake2-kat.h" -int main( void ) -{ - uint8_t key[BLAKE2S_KEYBYTES]; - uint8_t buf[BLAKE2_KAT_LENGTH]; - size_t i, step; - - for( i = 0; i < BLAKE2S_KEYBYTES; ++i ) - key[i] = ( uint8_t )i; - - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - buf[i] = ( uint8_t )i; - - /* Test simple API */ - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - { - uint8_t hash[BLAKE2S_OUTBYTES]; - blake2s( hash, BLAKE2S_OUTBYTES, buf, i, key, BLAKE2S_KEYBYTES ); - - if( 0 != memcmp( hash, blake2s_keyed_kat[i], BLAKE2S_OUTBYTES ) ) - { - goto fail; - } - } - - /* Test streaming API */ - for(step = 1; step < BLAKE2S_BLOCKBYTES; ++step) { - for (i = 0; i < BLAKE2_KAT_LENGTH; ++i) { - uint8_t hash[BLAKE2S_OUTBYTES]; - blake2s_state S; - uint8_t * p = buf; - size_t mlen = i; - int err = 0; - - if( (err = blake2s_init_key(&S, BLAKE2S_OUTBYTES, key, BLAKE2S_KEYBYTES)) < 0 ) { - goto fail; - } - - while (mlen >= step) { - if ( (err = blake2s_update(&S, p, step)) < 0 ) { - goto fail; - } - mlen -= step; - p += step; - } - if ( (err = blake2s_update(&S, p, mlen)) < 0) { - goto fail; - } - if ( (err = blake2s_final(&S, hash, BLAKE2S_OUTBYTES)) < 0) { - goto fail; - } - - if (0 != memcmp(hash, blake2s_keyed_kat[i], BLAKE2S_OUTBYTES)) { - goto fail; - } - } - } - - puts( "ok" ); - return 0; -fail: - puts("error"); - return -1; -} -#endif diff --git a/blake2sp-ref.c b/blake2sp-ref.c @@ -1,359 +0,0 @@ -/* - BLAKE2 reference source code package - reference C implementations - - Copyright 2012, Samuel Neves <sneves@dei.uc.pt>. You may use this under the - terms of the CC0, the OpenSSL Licence, or the Apache Public License 2.0, at - your option. The terms of these licenses can be found at: - - - CC0 1.0 Universal : http://creativecommons.org/publicdomain/zero/1.0 - - OpenSSL license : https://www.openssl.org/source/license.html - - Apache 2.0 : http://www.apache.org/licenses/LICENSE-2.0 - - More information about the BLAKE2 hash function can be found at - https://blake2.net. -*/ - -#include <stdlib.h> -#include <string.h> -#include <stdio.h> - -#if defined(_OPENMP) -#include <omp.h> -#endif - -#include "blake2.h" -#include "blake2-impl.h" - -#define PARALLELISM_DEGREE 8 - -/* - blake2sp_init_param defaults to setting the expecting output length - from the digest_length parameter block field. - - In some cases, however, we do not want this, as the output length - of these instances is given by inner_length instead. -*/ -static int blake2sp_init_leaf_param( blake2s_state *S, const blake2s_param *P ) -{ - int err = blake2s_init_param(S, P); - S->outlen = P->inner_length; - return err; -} - -static int blake2sp_init_leaf( blake2s_state *S, size_t outlen, size_t keylen, uint64_t offset ) -{ - blake2s_param P[1]; - P->digest_length = (uint8_t)outlen; - P->key_length = (uint8_t)keylen; - P->fanout = PARALLELISM_DEGREE; - P->depth = 2; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, offset ); - store16( &P->xof_length, 0 ); - P->node_depth = 0; - P->inner_length = BLAKE2S_OUTBYTES; - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - return blake2sp_init_leaf_param( S, P ); -} - -static int blake2sp_init_root( blake2s_state *S, size_t outlen, size_t keylen ) -{ - blake2s_param P[1]; - P->digest_length = (uint8_t)outlen; - P->key_length = (uint8_t)keylen; - P->fanout = PARALLELISM_DEGREE; - P->depth = 2; - store32( &P->leaf_length, 0 ); - store32( &P->node_offset, 0 ); - store16( &P->xof_length, 0 ); - P->node_depth = 1; - P->inner_length = BLAKE2S_OUTBYTES; - memset( P->salt, 0, sizeof( P->salt ) ); - memset( P->personal, 0, sizeof( P->personal ) ); - return blake2s_init_param( S, P ); -} - - -int blake2sp_init( blake2sp_state *S, size_t outlen ) -{ - size_t i; - - if( !outlen || outlen > BLAKE2S_OUTBYTES ) return -1; - - memset( S->buf, 0, sizeof( S->buf ) ); - S->buflen = 0; - S->outlen = outlen; - - if( blake2sp_init_root( S->R, outlen, 0 ) < 0 ) - return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2sp_init_leaf( S->S[i], outlen, 0, i ) < 0 ) return -1; - - S->R->last_node = 1; - S->S[PARALLELISM_DEGREE - 1]->last_node = 1; - return 0; -} - -int blake2sp_init_key( blake2sp_state *S, size_t outlen, const void *key, size_t keylen ) -{ - size_t i; - - if( !outlen || outlen > BLAKE2S_OUTBYTES ) return -1; - - if( !key || !keylen || keylen > BLAKE2S_KEYBYTES ) return -1; - - memset( S->buf, 0, sizeof( S->buf ) ); - S->buflen = 0; - S->outlen = outlen; - - if( blake2sp_init_root( S->R, outlen, keylen ) < 0 ) - return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2sp_init_leaf( S->S[i], outlen, keylen, i ) < 0 ) return -1; - - S->R->last_node = 1; - S->S[PARALLELISM_DEGREE - 1]->last_node = 1; - { - uint8_t block[BLAKE2S_BLOCKBYTES]; - memset( block, 0, BLAKE2S_BLOCKBYTES ); - memcpy( block, key, keylen ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2s_update( S->S[i], block, BLAKE2S_BLOCKBYTES ); - - secure_zero_memory( block, BLAKE2S_BLOCKBYTES ); /* Burn the key from stack */ - } - return 0; -} - - -int blake2sp_update( blake2sp_state *S, const void *pin, size_t inlen ) -{ - const unsigned char * in = (const unsigned char *)pin; - size_t left = S->buflen; - size_t fill = sizeof( S->buf ) - left; - size_t i; - - if( left && inlen >= fill ) - { - memcpy( S->buf + left, in, fill ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2s_update( S->S[i], S->buf + i * BLAKE2S_BLOCKBYTES, BLAKE2S_BLOCKBYTES ); - - in += fill; - inlen -= fill; - left = 0; - } - -#if defined(_OPENMP) - #pragma omp parallel shared(S), num_threads(PARALLELISM_DEGREE) -#else - for( i = 0; i < PARALLELISM_DEGREE; ++i ) -#endif - { -#if defined(_OPENMP) - size_t i = omp_get_thread_num(); -#endif - size_t inlen__ = inlen; - const unsigned char *in__ = ( const unsigned char * )in; - in__ += i * BLAKE2S_BLOCKBYTES; - - while( inlen__ >= PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES ) - { - blake2s_update( S->S[i], in__, BLAKE2S_BLOCKBYTES ); - in__ += PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES; - inlen__ -= PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES; - } - } - - in += inlen - inlen % ( PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES ); - inlen %= PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES; - - if( inlen > 0 ) - memcpy( S->buf + left, in, inlen ); - - S->buflen = left + inlen; - return 0; -} - - -int blake2sp_final( blake2sp_state *S, void *out, size_t outlen ) -{ - uint8_t hash[PARALLELISM_DEGREE][BLAKE2S_OUTBYTES]; - size_t i; - - if(out == NULL || outlen < S->outlen) { - return -1; - } - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - { - if( S->buflen > i * BLAKE2S_BLOCKBYTES ) - { - size_t left = S->buflen - i * BLAKE2S_BLOCKBYTES; - - if( left > BLAKE2S_BLOCKBYTES ) left = BLAKE2S_BLOCKBYTES; - - blake2s_update( S->S[i], S->buf + i * BLAKE2S_BLOCKBYTES, left ); - } - - blake2s_final( S->S[i], hash[i], BLAKE2S_OUTBYTES ); - } - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2s_update( S->R, hash[i], BLAKE2S_OUTBYTES ); - - return blake2s_final( S->R, out, S->outlen ); -} - - -int blake2sp( void *out, size_t outlen, const void *in, size_t inlen, const void *key, size_t keylen ) -{ - uint8_t hash[PARALLELISM_DEGREE][BLAKE2S_OUTBYTES]; - blake2s_state S[PARALLELISM_DEGREE][1]; - blake2s_state FS[1]; - size_t i; - - /* Verify parameters */ - if ( NULL == in && inlen > 0 ) return -1; - - if ( NULL == out ) return -1; - - if ( NULL == key && keylen > 0) return -1; - - if( !outlen || outlen > BLAKE2S_OUTBYTES ) return -1; - - if( keylen > BLAKE2S_KEYBYTES ) return -1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - if( blake2sp_init_leaf( S[i], outlen, keylen, i ) < 0 ) return -1; - - S[PARALLELISM_DEGREE - 1]->last_node = 1; /* mark last node */ - - if( keylen > 0 ) - { - uint8_t block[BLAKE2S_BLOCKBYTES]; - memset( block, 0, BLAKE2S_BLOCKBYTES ); - memcpy( block, key, keylen ); - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2s_update( S[i], block, BLAKE2S_BLOCKBYTES ); - - secure_zero_memory( block, BLAKE2S_BLOCKBYTES ); /* Burn the key from stack */ - } - -#if defined(_OPENMP) - #pragma omp parallel shared(S,hash), num_threads(PARALLELISM_DEGREE) -#else - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) -#endif - { -#if defined(_OPENMP) - size_t i = omp_get_thread_num(); -#endif - size_t inlen__ = inlen; - const unsigned char *in__ = ( const unsigned char * )in; - in__ += i * BLAKE2S_BLOCKBYTES; - - while( inlen__ >= PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES ) - { - blake2s_update( S[i], in__, BLAKE2S_BLOCKBYTES ); - in__ += PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES; - inlen__ -= PARALLELISM_DEGREE * BLAKE2S_BLOCKBYTES; - } - - if( inlen__ > i * BLAKE2S_BLOCKBYTES ) - { - const size_t left = inlen__ - i * BLAKE2S_BLOCKBYTES; - const size_t len = left <= BLAKE2S_BLOCKBYTES ? left : BLAKE2S_BLOCKBYTES; - blake2s_update( S[i], in__, len ); - } - - blake2s_final( S[i], hash[i], BLAKE2S_OUTBYTES ); - } - - if( blake2sp_init_root( FS, outlen, keylen ) < 0 ) - return -1; - - FS->last_node = 1; - - for( i = 0; i < PARALLELISM_DEGREE; ++i ) - blake2s_update( FS, hash[i], BLAKE2S_OUTBYTES ); - - return blake2s_final( FS, out, outlen ); -} - - - -#if defined(BLAKE2SP_SELFTEST) -#include <string.h> -#include "blake2-kat.h" -int main( void ) -{ - uint8_t key[BLAKE2S_KEYBYTES]; - uint8_t buf[BLAKE2_KAT_LENGTH]; - size_t i, step; - - for( i = 0; i < BLAKE2S_KEYBYTES; ++i ) - key[i] = ( uint8_t )i; - - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - buf[i] = ( uint8_t )i; - - /* Test simple API */ - for( i = 0; i < BLAKE2_KAT_LENGTH; ++i ) - { - uint8_t hash[BLAKE2S_OUTBYTES]; - blake2sp( hash, BLAKE2S_OUTBYTES, buf, i, key, BLAKE2S_KEYBYTES ); - - if( 0 != memcmp( hash, blake2sp_keyed_kat[i], BLAKE2S_OUTBYTES ) ) - { - goto fail; - } - } - - /* Test streaming API */ - for(step = 1; step < BLAKE2S_BLOCKBYTES; ++step) { - for (i = 0; i < BLAKE2_KAT_LENGTH; ++i) { - uint8_t hash[BLAKE2S_OUTBYTES]; - blake2sp_state S; - uint8_t * p = buf; - size_t mlen = i; - int err = 0; - - if( (err = blake2sp_init_key(&S, BLAKE2S_OUTBYTES, key, BLAKE2S_KEYBYTES)) < 0 ) { - goto fail; - } - - while (mlen >= step) { - if ( (err = blake2sp_update(&S, p, step)) < 0 ) { - goto fail; - } - mlen -= step; - p += step; - } - if ( (err = blake2sp_update(&S, p, mlen)) < 0) { - goto fail; - } - if ( (err = blake2sp_final(&S, hash, BLAKE2S_OUTBYTES)) < 0) { - goto fail; - } - - if (0 != memcmp(hash, blake2sp_keyed_kat[i], BLAKE2S_OUTBYTES)) { - goto fail; - } - } - } - - puts( "ok" ); - return 0; -fail: - puts("error"); - return -1; -} -#endif diff --git a/block.c b/block.c @@ -0,0 +1,114 @@ +#include <sys/types.h> +#include <sys/stat.h> + +#include <fcntl.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "block.h" + +int +bcreat(char *path, int mode, struct bparam *bpar, struct bctx **bctx) +{ + struct bops *bops; + + if (path == NULL || bctx == NULL) + return -1; + + if (bpar == NULL) + bpar = bparamdef(); + + *bctx = calloc(1, sizeof(**bctx)); + if (*bctx == NULL) + return -1; + + bops = bcompressops(); + if (bops->creat(*bctx, path, mode, bpar) < 0) { + free(*bctx); + return -1; + } + return 0; +} + +int +bopen(char *path, int flags, int mode, struct bparam *bpar, struct bctx **bctx) +{ + struct bops *bops; + + if (path == NULL || bpar == NULL || bctx == NULL) + return -1; + + *bctx = calloc(1, sizeof(**bctx)); + if (*bctx == NULL) + return -1; + + bops = bcompressops(); + if (bops->open(*bctx, path, flags, mode, bpar) < 0) { + free(*bctx); + return -1; + } + return 0; +} + +int +bput(struct bctx *bctx, void *buf, size_t n, unsigned char *md) +{ + struct bops *bops; + + if (bctx == NULL || buf == NULL || n == 0 || md == NULL) + return -1; + + bops = bcompressops(); + return bops->put(bctx, buf, n, md); +} + +int +bget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n) +{ + struct bops *bops; + + if (bctx == NULL || md == NULL || buf == NULL || n == NULL) + return -1; + + bops = bcompressops(); + return bops->get(bctx, md, buf, n); +} + +int +bsync(struct bctx *bctx) +{ + struct bops *bops; + + if (bctx == NULL) + return -1; + + bops = bcompressops(); + return bops->sync(bctx); +} + +int +bclose(struct bctx *bctx) +{ + struct bops *bops; + int r; + + if (bctx == NULL) + return -1; + + if (bsync(bctx) < 0) + return -1; + bops = bcompressops(); + r = bops->close(bctx); + free(bctx); + return r; +} + +struct bparam * +bparamdef(void) +{ + static struct bparam bpar = { .calgo = "snappy", .halgo = "blake2b" }; + + return &bpar; +} diff --git a/block.h b/block.h @@ -0,0 +1,34 @@ +struct bctx { + void *rctx; /* raw layer context */ + void *cctx; /* compression layer context */ + void *sctx; /* storage layer context */ +}; + +struct bparam { + char *calgo; + char *halgo; +}; + +struct bops { + int (*creat)(struct bctx *bctx, char *path, int mode, struct bparam *bpar); + int (*open)(struct bctx *bctx, char *path, int flags, int mode, struct bparam *bpar); + int (*put)(struct bctx *bctx, void *buf, size_t n, unsigned char *md); + int (*get)(struct bctx *bctx, unsigned char *md, void *buf, size_t *n); + int (*sync)(struct bctx *bctx); + int (*close)(struct bctx *bctx); +}; + +/* block.c */ +extern int bcreat(char *path, int mode, struct bparam *bpar, struct bctx **bctx); +extern int bopen(char *path, int flags, int mode, struct bparam *bpar, struct bctx **bctx); +extern int bput(struct bctx *bctx, void *buf, size_t n, unsigned char *md); +extern int bget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n); +extern int bsync(struct bctx *bctx); +extern int bclose(struct bctx *bctx); +struct bparam *bparamdef(void); + +/* bcompress.c */ +extern struct bops *bcompressops(void); + +/* bstorage.c */ +extern struct bops *bstorageops(void); diff --git a/bstorage.c b/bstorage.c @@ -0,0 +1,564 @@ +/* + * Storage layer implementation using a single backing file. + * The file format is as follows: + * + * [storage header] + * [storage descriptor 0] + * [data] + * [storage descriptor 1] + * [data] + * ... + */ +#include <sys/types.h> +#include <sys/stat.h> + +#include <assert.h> +#include <fcntl.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "blake2.h" +#include "block.h" +#include "config.h" +#include "tree.h" + +#define VMIN 0 +#define VMAJ 1 + +#define VMINMASK 0xff +#define VMAJSHIFT 8 +#define VMAJMASK 0xff + +#define HALGOSHIFT 19 +#define HALGOMASK 0x7 +#define CALGOSHIFT 16 +#define CALGOMASK 0x7 + +#define BHDRSIZE 16 + +#define BDTYPE 0x100 +#define BDSIZE (8 + 8 + 8 + (MDSIZE)) + +#define CSNAPPYTYPE 0 +#define HBLAKE2BTYPE 0 + +extern int pack(unsigned char *dst, char *fmt, ...); +extern int unpack(unsigned char *src, char *fmt, ...); + +static int bscreat(struct bctx *bctx, char *path, int mode, struct bparam *bpar); +static int bsopen(struct bctx *bctx, char *path, int flags, int mode, struct bparam *bpar); +static int bsput(struct bctx *bctx, void *buf, size_t n, unsigned char *md); +static int bsget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n); +static int bssync(struct bctx *bctx); +static int bsclose(struct bctx *bctx); + +static struct bops bops = { + .creat = bscreat, + .open = bsopen, + .put = bsput, + .get = bsget, + .sync = bssync, + .close = bsclose, +}; + +/* Block header structure */ +struct bhdr { + uint64_t flags; + uint64_t nent; +}; + +/* Block descriptor */ +struct bd { + uint64_t type; + uint64_t offset; + uint64_t size; + unsigned char md[MDSIZE]; + RB_ENTRY(bd) entry; +}; +RB_HEAD(bdcache, bd); + +struct sctx { + struct bdcache bdcache; + struct bhdr bhdr; + int fd; + int rdonly; +}; + +static char *ctbl[] = { + "snappy", + NULL, +}; + +static char *htbl[] = { + "blake2b", + NULL, +}; + +static int +bd_cmp(struct bd *b1, struct bd *b2) +{ + int r; + + r = memcmp(b1->md, b2->md, MDSIZE); + if (r > 0) + return 1; + else if (r < 0) + return -1; + return 0; +} +static RB_PROTOTYPE(bdcache, bd, entry, bd_cmp) +static RB_GENERATE(bdcache, bd, entry, bd_cmp) + +static int +bhash(void *buf, size_t n, unsigned char *md) +{ + blake2b_state ctx; + + if (blake2b_init(&ctx, MDSIZE) < 0) + return -1; + if (blake2b_update(&ctx, buf, n) < 0) + return -1; + return blake2b_final(&ctx, md, MDSIZE); +} + +static ssize_t +xread(int fd, void *buf, size_t nbytes) +{ + unsigned char *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = read(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; + } + return total; +} + +static ssize_t +xwrite(int fd, void *buf, size_t nbytes) +{ + unsigned char *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = write(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; + } + return total; +} + +/* Read block header */ +static int +unpackbhdr(int fd, struct bhdr *bhdr) +{ + unsigned char buf[BHDRSIZE]; + int n; + + if (xread(fd, buf, sizeof(buf)) != sizeof(buf)) + return -1; + + n = unpack(buf, "qq", + &bhdr->flags, + &bhdr->nent); + + assert(n == sizeof(buf)); + return n; +} + +/* Write block header */ +static int +packbhdr(int fd, struct bhdr *bhdr) +{ + unsigned char buf[BHDRSIZE]; + int n; + + n = pack(buf, "qq", + bhdr->flags, + bhdr->nent); + + assert(n == BHDRSIZE); + if (xwrite(fd, buf, n) != n) + return -1; + return n; +} + +/* Read block descriptor */ +static int +unpackbd(int fd, struct bd *bd) +{ + unsigned char buf[BDSIZE]; + char fmt[BUFSIZ]; + int n; + + if (xread(fd, buf, sizeof(buf)) != sizeof(buf)) + return -1; + + snprintf(fmt, sizeof(fmt), "qqq'%d", MDSIZE); + n = unpack(buf, fmt, + &bd->type, + &bd->offset, + &bd->size, + bd->md); + + assert(n == BDSIZE); + return n; +} + +/* Write block descriptor */ +static int +packbd(int fd, struct bd *bd) +{ + unsigned char buf[BDSIZE]; + char fmt[BUFSIZ]; + int n; + + snprintf(fmt, sizeof(fmt), "qqq'%d", MDSIZE); + n = pack(buf, fmt, + bd->type, + bd->offset, + bd->size, + bd->md); + + assert(n == BDSIZE); + if (xwrite(fd, buf, n) != n) + return -1; + return n; +} + +/* Insert block descriptor to cache */ +static int +loadbd(struct sctx *sctx) +{ + struct bd *bd; + + bd = calloc(1, sizeof(*bd)); + if (bd == NULL) + return -1; + + if (unpackbd(sctx->fd, bd) < 0) { + free(bd); + return -1; + } + + if (bd->type != BDTYPE) { + free(bd); + return -1; + } + + /* Move to the next block descriptor */ + if (lseek(sctx->fd, bd->size, SEEK_CUR) < 0) { + free(bd); + return -1; + } + + RB_INSERT(bdcache, &sctx->bdcache, bd); + return 0; +} + +/* Initialize block descriptor cache */ +static int +initbdcache(struct sctx *sctx) +{ + struct bhdr *bhdr; + uint64_t i; + + bhdr = &sctx->bhdr; + for (i = 0; i < bhdr->nent; i++) { + struct bd *bd, *tmp; + + if (loadbd(sctx) == 0) + continue; + + /* Cleanup */ + RB_FOREACH_SAFE(bd, bdcache, &sctx->bdcache, tmp) { + RB_REMOVE(bdcache, &sctx->bdcache, bd); + free(bd); + } + return -1; + } + return 0; +} + +/* Create a new store */ +static int +bscreat(struct bctx *bctx, char *path, int mode, struct bparam *bpar) +{ + struct sctx *sctx; + struct bhdr *bhdr; + char **algo; + int fd; + + fd = open(path, O_RDWR | O_CREAT | O_EXCL, mode); + if (fd < 0) + return -1; + + bctx->sctx = calloc(1, sizeof(struct sctx)); + if (bctx->sctx == NULL) { + close(fd); + return -1; + } + + sctx = bctx->sctx; + RB_INIT(&sctx->bdcache); + bhdr = &sctx->bhdr; + bhdr->flags = (VMAJ << VMAJSHIFT) | VMIN; + + /* Set compression algorithm */ + for (algo = ctbl; algo; algo++) { + if (strcmp(*algo, bpar->calgo) == 0) { + uint64_t v; + + v = algo - ctbl; + bhdr->flags |= v << CALGOSHIFT; + break; + } + } + if (algo == NULL) { + free(sctx); + close(fd); + return -1; + } + + /* Set hash algorithm */ + for (algo = htbl; algo; algo++) { + if (strcmp(*algo, bpar->halgo) == 0) { + uint64_t v; + + v = algo - htbl; + bhdr->flags |= v << HALGOSHIFT; + break; + } + } + if (algo == NULL) { + free(sctx); + close(fd); + return -1; + } + + bhdr->nent = 0; + sctx->fd = fd; + + if (packbhdr(fd, bhdr) < 0) { + free(sctx); + close(fd); + return -1; + } + return 0; +} + +/* Open an existing store */ +static int +bsopen(struct bctx *bctx, char *path, int flags, int mode, struct bparam *bpar) +{ + struct sctx *sctx; + struct bhdr *bhdr; + char **algo; + int fd, calgo, halgo; + + fd = open(path, flags, mode); + if (fd < 0) + return -1; + + bctx->sctx = calloc(1, sizeof(struct sctx)); + if (bctx->sctx == NULL) { + close(fd); + return -1; + } + + sctx = bctx->sctx; + RB_INIT(&sctx->bdcache); + bhdr = &sctx->bhdr; + if (unpackbhdr(fd, bhdr) < 0) { + free(sctx); + close(fd); + return -1; + } + + /* If the major version is different, the format is incompatible */ + if (((bhdr->flags >> VMAJSHIFT) & VMAJMASK) != VMAJ) { + free(sctx); + close(fd); + return -1; + } + + /* Get compression algorithm */ + calgo = (bhdr->flags >> CALGOSHIFT) & CALGOMASK; + for (algo = ctbl; algo; algo++) { + uint64_t v = algo - ctbl; + + if (v == calgo) { + bpar->calgo = ctbl[v]; + break; + } + } + if (algo == NULL) { + free(sctx); + close(fd); + return -1; + } + + /* Get hash algorithm */ + halgo = (bhdr->flags >> CALGOSHIFT) & CALGOMASK; + for (algo = htbl; algo; algo++) { + uint64_t v = algo - htbl; + + if (v == halgo) { + bpar->halgo = htbl[v]; + break; + } + } + if (algo == NULL) { + free(sctx); + close(fd); + return -1; + } + + sctx->fd = fd; + sctx->rdonly = flags == O_RDONLY; + + if (initbdcache(sctx) < 0) { + free(sctx); + close(fd); + return -1; + } + return 0; +} + +/* Write a new block */ +static int +bsput(struct bctx *bctx, void *buf, size_t n, unsigned char *md) +{ + struct sctx *sctx; + struct bhdr *bhdr; + struct bd key, *bd; + off_t offs; + + sctx = bctx->sctx; + + if (bhash(buf, n, key.md) < 0) + return -1; + + bd = RB_FIND(bdcache, &sctx->bdcache, &key); + if (bd != NULL) { + memcpy(md, bd->md, MDSIZE); + return 0; + } + + offs = lseek(sctx->fd, 0, SEEK_END); + if (offs < 0) + return -1; + + bd = calloc(1, sizeof(*bd)); + if (bd == NULL) + return -1; + bd->type = BDTYPE; + bd->offset = offs + BDSIZE; + bd->size = n; + memcpy(bd->md, key.md, MDSIZE); + + if (packbd(sctx->fd, bd) < 0) { + free(bd); + return -1; + } + + if (xwrite(sctx->fd, buf, n) != n) { + ftruncate(sctx->fd, offs); + free(bd); + return -1; + } + + bhdr = &sctx->bhdr; + bhdr->nent++; + RB_INSERT(bdcache, &sctx->bdcache, bd); + memcpy(md, bd->md, MDSIZE); + return bd->size; +} + +/* Read a block */ +static int +bsget(struct bctx *bctx, unsigned char *md, void *buf, size_t *n) +{ + struct sctx *sctx; + struct bd key, *bd; + + sctx = bctx->sctx; + + /* Lookup block in the cache */ + memcpy(key.md, md, MDSIZE); + bd = RB_FIND(bdcache, &sctx->bdcache, &key); + if (bd == NULL) + return -1; + + if (*n < bd->size) + return -1; + + if (lseek(sctx->fd, bd->offset, SEEK_SET) < 0) + return -1; + if (xread(sctx->fd, buf, bd->size) != bd->size) + return -1; + *n = bd->size; + return 0; +} + +static int +bssync(struct bctx *bctx) +{ + struct sctx *sctx; + struct bhdr *bhdr; + + sctx = bctx->sctx; + if (sctx->rdonly) + return 0; + + if (lseek(sctx->fd, 0, SEEK_SET) < 0) + return -1; + bhdr = &sctx->bhdr; + if (packbhdr(sctx->fd, bhdr) < 0) + return -1; + fsync(sctx->fd); + return 0; +} + +static int +bsclose(struct bctx *bctx) +{ + struct sctx *sctx; + struct bd *bd, *tmp; + int r; + + if (bssync(bctx) < 0) + return -1; + + sctx = bctx->sctx; + RB_FOREACH_SAFE(bd, bdcache, &sctx->bdcache, tmp) { + RB_REMOVE(bdcache, &sctx->bdcache, bd); + free(bd); + } + + r = close(sctx->fd); + free(sctx); + return r; +} + +struct bops * +bstorageops(void) +{ + return &bops; +} diff --git a/chunker.c b/chunker.c @@ -1,24 +1,20 @@ -#include <err.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> -#include "blake2.h" -#include "dedup.h" - #define ROTL(x, y) (((x) << (y)) | ((x) >> (32 - (y)))) struct chunker { - uint8_t *buf; + unsigned char *buf; int fd; - size_t rpos; - size_t wpos; - size_t min_size; - size_t max_size; + size_t rp; + size_t wp; + size_t minsize; + size_t maxsize; size_t mask; - size_t win_size; + size_t winsize; }; /* @@ -30,7 +26,7 @@ struct chunker { * exactly 50% chance that a XOR operation would flip all the bits in * the hash. */ -static const uint32_t buz[] = { +static const uint32_t buztbl[] = { 0xbc9fa594,0x30a8f827,0xced627a7,0xdb46a745,0xcfa4a9e8,0x77cccb59,0xddb66276,0x3adc532f, 0xfe8b67d3,0x8155b59e,0x0c893666,0x1d757009,0x17394ee4,0x85d94c07,0xcacd52da,0x076c6f79, 0xead0a798,0x6c7ccb4a,0x2639a1b8,0x3aa5ae32,0x3e6218d2,0xb290d980,0xa5149521,0x4b426119, @@ -65,36 +61,55 @@ static const uint32_t buz[] = { 0x8dfd4d53,0xc4d0c087,0x31dfb5ca,0xa44589b5,0x6b637e2e,0x663f6b45,0xd2d8baa0,0x1dac7e4c }; +static ssize_t +xread(int fd, void *buf, size_t nbytes) +{ + unsigned char *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = read(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; + } + return total; +} + /* Buzhash: https://en.wikipedia.org/wiki/Rolling_hash#Cyclic_polynomial */ static inline uint32_t -buzh_init(uint8_t *buf, size_t size) +hinit(unsigned char *buf, size_t size) { uint32_t sum; size_t i; for (i = 1, sum = 0; i < size; i++, buf++) - sum ^= ROTL(buz[*buf], (size - i) % 32); - - return sum ^ buz[*buf]; + sum ^= ROTL(buztbl[*buf], (size - i) % 32); + return sum ^ buztbl[*buf]; } static inline uint32_t -buzh_update(uint32_t sum, uint8_t out, uint8_t in, size_t size) +hupdate(uint32_t sum, unsigned char out, unsigned char in, size_t size) { - return ROTL(sum, 1) ^ ROTL(buz[out], size % 32) ^ buz[in]; + return ROTL(sum, 1) ^ ROTL(buztbl[out], size % 32) ^ buztbl[in]; } static size_t -get_chunk_size(struct chunker *chunker) +cgetsize(struct chunker *c) { - size_t max_chunk_size, win_size, i; + size_t maxcsize, winsize, i; uint32_t sum; - uint8_t *bp; + unsigned char *bp; - max_chunk_size = chunker->wpos - chunker->rpos; - win_size = chunker->win_size; - if (max_chunk_size < win_size) - return max_chunk_size; + maxcsize = c->wp - c->rp; + winsize = c->winsize; + if (maxcsize < winsize) + return maxcsize; /* * To achieve better deduplication, we chunk blocks based on a @@ -104,93 +119,96 @@ get_chunk_size(struct chunker *chunker) * When the rolling hash matches a given pattern the block is chunked * at the end of that window. */ - bp = &chunker->buf[chunker->rpos]; - sum = buzh_init(bp, win_size); - for (i = 0; i < max_chunk_size - win_size; i++) { - size_t chunk_size = i + win_size; + bp = &c->buf[c->rp]; + sum = hinit(bp, winsize); + for (i = 0; i < maxcsize - winsize; i++) { + size_t csize = i + winsize; if (i > 0) { - uint8_t out = bp[i - 1]; - uint8_t in = bp[chunk_size - 1]; + unsigned char out = bp[i - 1]; + unsigned char in = bp[csize - 1]; - sum = buzh_update(sum, out, in, win_size); + sum = hupdate(sum, out, in, winsize); } - if (chunk_size < chunker->min_size) + if (csize < c->minsize) continue; - if ((sum & chunker->mask) == 0) - return chunk_size; + if ((sum & c->mask) == 0) + return csize; } - return max_chunk_size; + return maxcsize; } struct chunker * -alloc_chunker(int fd, size_t min_size, size_t max_size, - size_t mask, size_t win_size) +copen(int fd, size_t minsize, size_t maxsize, + size_t mask, size_t winsize) { - struct chunker *chunker; + struct chunker *c; - chunker = calloc(1, sizeof(*chunker)); - if (chunker == NULL) - err(1, "calloc"); - - chunker->buf = calloc(1, max_size); - if (chunker->buf == NULL) - err(1, "calloc"); + c = calloc(1, sizeof(*c)); + if (c == NULL) + return NULL; - chunker->fd = fd; - chunker->min_size = min_size; - chunker->max_size = max_size; - chunker->mask = mask; - chunker->win_size = win_size; + c->buf = calloc(1, maxsize); + if (c->buf == NULL) { + free(c); + return NULL; + } - return chunker; + c->fd = fd; + c->minsize = minsize; + c->maxsize = maxsize; + c->mask = mask; + c->winsize = winsize; + return c; } -void -free_chunker(struct chunker *chunker) +int +cclose(struct chunker *c) { - free(chunker->buf); - free(chunker); + free(c->buf); + free(c); + return 0; } ssize_t -fill_chunker(struct chunker *chunker) +cfill(struct chunker *c) { - uint8_t *bp; + unsigned char *bp; ssize_t n; - bp = &chunker->buf[chunker->wpos]; - n = xread(chunker->fd, bp, chunker->max_size - chunker->wpos); - chunker->wpos += n; - return chunker->wpos; + bp = &c->buf[c->wp]; + n = xread(c->fd, bp, c->maxsize - c->wp); + c->wp += n; + return c->wp; } -uint8_t * -get_chunk(struct chunker *chunker, size_t *chunk_size) +void * +cget(struct chunker *c, size_t *csize) { - uint8_t *bp; + unsigned char *bp; - if (chunker->rpos == chunker->wpos) { - *chunk_size = 0; + if (c->rp == c->wp) { + *csize = 0; return NULL; } - bp = &chunker->buf[chunker->rpos]; - *chunk_size = get_chunk_size(chunker); - chunker->rpos += *chunk_size; + bp = &c->buf[c->rp]; + *csize = cgetsize(c); + c->rp += *csize; return bp; } -void -drain_chunker(struct chunker *chunker) +int +cdrain(struct chunker *c) { - uint8_t *src, *dst; - - src = &chunker->buf[chunker->rpos]; - dst = chunker->buf; - memmove(dst, src, chunker->wpos - chunker->rpos); - chunker->wpos -= chunker->rpos; - chunker->rpos = 0; + unsigned char *src, *dst; + + src = &c->buf[c->rp]; + dst = c->buf; + memmove(dst, src, c->wp - c->rp); + c->wp -= c->rp; + c->rp = 0; + return c->wp; } diff --git a/chunker.h b/chunker.h @@ -0,0 +1,8 @@ +struct chunker; + +extern struct chunker *copen(int fd, size_t minsize, size_t maxsize, + size_t mask, size_t winsize); +extern int cclose(struct chunker *c); +extern ssize_t cfill(struct chunker *c); +extern void *cget(struct chunker *c, size_t *csize); +extern int cdrain(struct chunker *c); diff --git a/compress-lz4.c b/compress-lz4.c @@ -1,54 +0,0 @@ -#include <sys/types.h> - -#include <err.h> -#include <stdint.h> -#include <string.h> - -#include <lz4.h> - -#include "blake2.h" -#include "dedup.h" - -int -lz4_init(struct compr_ctx *ctx) -{ - return 0; -} - -size_t -lz4_size(struct compr_ctx *ctx, size_t n) -{ - return LZ4_compressBound(n); -} - -size_t -lz4_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - int n; - - n = LZ4_compress_default((char *)in, (char *)out, insize, - outsize); - if (n < 0) - errx(1, "LZ4_compress_default failed"); - return n; -} - -size_t -lz4_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - int n; - - n = LZ4_decompress_safe((char *)in, (char *)out, insize, - outsize); - if (n < 0) - errx(1, "LZ4_decompress_safe failed"); - return n; -} - -int -lz4_final(struct compr_ctx *ctx) -{ - return 0; -} diff --git a/compress-none.c b/compress-none.c @@ -1,41 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" - -int -none_init(struct compr_ctx *ctx) -{ - return 0; -} - -size_t -none_size(struct compr_ctx *ctx, size_t n) -{ - return n; -} - -size_t -none_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - memcpy(out, in, insize); - return insize; -} - -size_t -none_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - memcpy(out, in, insize); - return insize; -} - -int -none_final(struct compr_ctx *ctx) -{ - return 0; -} diff --git a/compress-snappy.c b/compress-snappy.c @@ -1,54 +0,0 @@ -#include <sys/types.h> - -#include <err.h> -#include <stdint.h> -#include <string.h> - -#include <snappy-c.h> - -#include "blake2.h" -#include "dedup.h" - -int -snappy_init(struct compr_ctx *ctx) -{ - return 0; -} - -size_t -snappy_size(struct compr_ctx *ctx, size_t n) -{ - return snappy_max_compressed_length(n); -} - -size_t -snappy_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - size_t n = outsize; - snappy_status ret; - - ret = snappy_compress((char *)in, insize, (char *)out, &n); - if (ret != SNAPPY_OK) - errx(1, "snappy_compress failed: %d", ret); - return n; -} - -size_t -snappy_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - size_t n = outsize; - snappy_status ret; - - ret = snappy_uncompress((char *)in, insize, (char *)out, &n); - if (ret != SNAPPY_OK) - errx(1, "snappy_uncompress failed: %d", ret); - return n; -} - -int -snappy_final(struct compr_ctx *ctx) -{ - return 0; -} diff --git a/compress.c b/compress.c @@ -1,112 +0,0 @@ -#include <sys/types.h> - -#include <err.h> -#include <stdint.h> -#include <stdio.h> -#include <string.h> -#include <strings.h> - -#include "blake2.h" -#include "dedup.h" - -static struct compr_ops { - int (*init)(struct compr_ctx *ctx); - size_t (*size)(struct compr_ctx *ctx, size_t n); - size_t (*compr)(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); - size_t (*decompr)(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); - int (*final)(struct compr_ctx *ctx); -} comprs[NR_COMPRS] = { - { - .init = none_init, - .size = none_size, - .compr = none_compr, - .decompr = none_decompr, - .final = none_final, - }, - { - .init = lz4_init, - .size = lz4_size, - .compr = lz4_compr, - .decompr = lz4_decompr, - .final = lz4_final, - }, - { - .init = snappy_init, - .size = snappy_size, - .compr = snappy_compr, - .decompr = snappy_decompr, - .final = snappy_final, - }, -}; - -static char *algomap[NR_COMPRS] = { - [COMPR_NONE] = "none", - [COMPR_LZ4] = "lz4", - [COMPR_SNAPPY] = "snappy", -}; - -int -compr_init(struct compr_ctx *ctx, int type) -{ - if (type < 0 || type >= NR_COMPRS) - return -1; - - ctx->ops = &comprs[type]; - return (*ctx->ops->init)(ctx); -} - -int -compr_size(struct compr_ctx *ctx, size_t n) -{ - return (*ctx->ops->size)(ctx, n); -} - -size_t -compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - return (*ctx->ops->compr)(ctx, in, out, insize, outsize); -} - -size_t -decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize) -{ - return (*ctx->ops->decompr)(ctx, in, out, insize, outsize); -} - -int -compr_final(struct compr_ctx *ctx) -{ - return (*ctx->ops->final)(ctx); -} - -int -compr_name2type(char *name) -{ - size_t i; - - for (i = 0; i < NR_COMPRS; i++) - if (strcasecmp(algomap[i], name) == 0) - return i; - return -1; -} - -char * -compr_type2name(int type) -{ - if (type < 0 || type >= NR_HASHES) - return NULL; - return algomap[type]; -} - -void -compr_list(int fd) -{ - size_t i; - - for (i = 0; i < NR_COMPRS; i++) - dprintf(fd, "%s\n", algomap[i]); -} diff --git a/config.h b/config.h @@ -1,5 +1,8 @@ -#define BLKSIZE_AVG ((size_t)(1ul << 21)) -#define BLKSIZE_MIN ((size_t)524288) -#define BLKSIZE_MAX ((size_t)8388608) -#define HASHMASK_BITS (BLKSIZE_AVG - 1) +#define ARCHIVEPATH "archive" +#define STORAGEPATH "storage" +#define MDSIZE 32 +#define BSIZEAVG ((size_t)(1ul << 21)) +#define BSIZEMIN ((size_t)524288) +#define BSIZEMAX ((size_t)8388608) +#define HMASKBITS (BSIZEAVG - 1) #define WINSIZE ((size_t)4095) diff --git a/config.mk b/config.mk @@ -1,2 +1,3 @@ -#OPENMPCFLAGS = -fopenmp -#OPENMPLDLIBS = -lgomp +VERSION = 1.0 +PREFIX = /usr/local +MANPREFIX = $(PREFIX)/man diff --git a/dedup.h b/dedup.h @@ -1,233 +0,0 @@ -#include "config.h" - -#define SNAPSF ".snapshots" -#define STOREF ".store" - -/* - * These are the actual sizes of the structs in the - * file format itself. The types are serialized/deserialized - * using the helpers from types.c. Any modification made to - * the structs below will need to be reflected here and in types.c. - */ -#define MSG_SIZE 256 -#define MD_SIZE 32 - -#define SNAP_HDR_SIZE 104 -#define BLK_HDR_SIZE 16 -#define BLK_DESC_SIZE (MD_SIZE + 16) -#define SNAPSHOT_SIZE (8 + MSG_SIZE + MD_SIZE + 8) - -/* file format version */ -#define VER_MIN 2 -#define VER_MAJ 0 - -/* snapshot header and block header flags */ -#define VER_MIN_MASK 0xff -#define VER_MAJ_SHIFT 8 -#define VER_MAJ_MASK 0xff - -/* block header flags */ -#define HASH_ALGO_SHIFT 19 -#define HASH_ALGO_MASK 0x7 /* max 8 hash algos */ -#define COMPR_ALGO_SHIFT 16 -#define COMPR_ALGO_MASK 0x7 /* max 8 compression algos */ - -enum { - WALK_CONTINUE, - WALK_STOP -}; - -enum compr_algo { - COMPR_NONE, - COMPR_LZ4, - COMPR_SNAPPY, - NR_COMPRS, -}; - -enum hash_algo { - HASH_BLAKE2B, - HASH_BLAKE2BP, - HASH_BLAKE2S, - HASH_BLAKE2SP, - NR_HASHES, -}; - -struct chunker; -struct icache; - -struct stats { - uint64_t orig_size; /* original store size */ - uint64_t compr_size; /* compressed store size */ - uint64_t dedup_size; /* deduplicated store size */ - uint64_t min_blk_size; - uint64_t max_blk_size; - uint64_t nr_blks; /* number of unique blocks */ - uint64_t reserved[4]; -}; - -struct snap_hdr { - uint64_t flags; - uint64_t size; /* size of snapshots file */ - uint64_t nr_snaps; - struct stats st; -}; - -struct blk_hdr { - uint64_t flags; - uint64_t size; /* size of store file */ -}; - -struct blk_desc { - uint8_t md[MD_SIZE]; /* hash of block */ - uint64_t offset; /* offset into store file */ - uint64_t size; /* size of block */ -}; - -struct snap { - uint64_t size; /* size of snapshot (including block descriptors) */ - uint8_t msg[MSG_SIZE]; /* arbitrary message attached to snapshot */ - uint8_t md[MD_SIZE]; /* hash of snapshot (hash of all block descriptor hashes) */ - uint64_t nr_blk_descs; - struct blk_desc blk_desc[]; -}; - -struct compr_ctx { - struct compr_ops *ops; -}; - -struct hash_ctx { - union { - blake2b_state blake2b_ctx; - blake2bp_state blake2bp_ctx; - blake2s_state blake2s_ctx; - blake2sp_state blake2sp_ctx; - } u; - struct hash_ops *ops; -}; - -/* dedup.c */ -extern int verbose; - -/* chunker.c */ -struct chunker *alloc_chunker(int fd, size_t min_size, size_t max_size, - size_t mask, size_t win_size); -void free_chunker(struct chunker *chunker); -ssize_t fill_chunker(struct chunker *chunker); -uint8_t *get_chunk(struct chunker *chunker, size_t *chunk_size); -void drain_chunker(struct chunker *chunker); - -/* compress-none.c */ -int none_init(struct compr_ctx *ctx); -size_t none_size(struct compr_ctx *ctx, size_t n); -size_t none_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -size_t none_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -int none_final(struct compr_ctx *ctx); - -/* compress-lz4.c */ -int lz4_init(struct compr_ctx *ctx); -size_t lz4_size(struct compr_ctx *ctx, size_t n); -size_t lz4_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -size_t lz4_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -int lz4_final(struct compr_ctx *ctx); - -/* compress-snappy.c */ -int snappy_init(struct compr_ctx *ctx); -size_t snappy_size(struct compr_ctx *ctx, size_t n); -size_t snappy_compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -size_t snappy_decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -int snappy_final(struct compr_ctx *ctx); - -/* compress.c */ -int compr_init(struct compr_ctx *ctx, int type); -int compr_size(struct compr_ctx *ctx, size_t n); -size_t compr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -size_t decompr(struct compr_ctx *ctx, const void *in, void *out, - size_t insize, size_t outsize); -int compr_final(struct compr_ctx *ctx); -int compr_name2type(char *name); -char *compr_type2name(int type); -void compr_list(int fd); - -/* hash-blake2b.c */ -int blake2bi(struct hash_ctx *ctx, size_t n); -int blake2bu(struct hash_ctx *ctx, const void *buf, size_t n); -int blake2bf(struct hash_ctx *ctx, void *buf, size_t n); - -/* hash-blake2bp.c */ -int blake2bpi(struct hash_ctx *ctx, size_t n); -int blake2bpu(struct hash_ctx *ctx, const void *buf, size_t n); -int blake2bpf(struct hash_ctx *ctx, void *buf, size_t n); - -/* hash-blake2s.c */ -int blake2si(struct hash_ctx *ctx, size_t n); -int blake2su(struct hash_ctx *ctx, const void *buf, size_t n); -int blake2sf(struct hash_ctx *ctx, void *buf, size_t n); - -/* hash-blake2sp.c */ -int blake2spi(struct hash_ctx *ctx, size_t n); -int blake2spu(struct hash_ctx *ctx, const void *buf, size_t n); -int blake2spf(struct hash_ctx *ctx, void *buf, size_t n); - -/* hash.c */ -int hash_init(struct hash_ctx *ctx, int type, size_t n); -int hash_update(struct hash_ctx *ctx, const void *buf, size_t n); -int hash_final(struct hash_ctx *ctx, void *buf, size_t n); -int hash_name2type(char *name); -char *hash_type2name(int type); -void hash_list(int fd); - -/* icache.c */ -struct icache *alloc_icache(void); -void free_icache(struct icache *icache); -void insert_icache(struct icache *icache, struct blk_desc *desc); -int lookup_icache(struct icache *icache, struct blk_desc *desc); -void icache_stats(struct icache *icache, unsigned long long *hits, - unsigned long long *misses); - -/* pack.c */ -int pack(unsigned char *dst, char *fmt, ...); - -/* unpack.c */ -int unpack(unsigned char *src, char *fmt, ...); - -/* types.c */ -void read_snap_hdr(int fd, struct snap_hdr *hdr); -void write_snap_hdr(int fd, struct snap_hdr *hdr); -void read_blk_hdr(int fd, struct blk_hdr *hdr); -void write_blk_hdr(int fd, struct blk_hdr *hdr); -void read_blk_desc(int fd, struct blk_desc *desc); -void write_blk_desc(int fd, struct blk_desc *desc); -void read_snap(int fd, struct snap *snap); -void read_snap_descs(int fd, struct snap *snap); -void write_snap(int fd, struct snap *snap); -void write_snap_blk_descs(int fd, struct snap *snap); - -/* utils.c */ -void str2bin(char *s, uint8_t *d); -off_t xlseek(int fd, off_t offset, int whence); -ssize_t xread(int fd, void *buf, size_t nbytes); -ssize_t xwrite(int fd, const void *buf, size_t nbytes); -void init_blk_hdr(struct blk_hdr *hdr, int compr_algo, int hash_algo); -void init_snap_hdr(struct snap_hdr *hdr); -void load_blk_hdr(int fd, struct blk_hdr *hdr, int *compr_algo, int *hash_algo); -void load_snap_hdr(int fd, struct snap_hdr *hdr); -struct snap *alloc_snap(void); -void free_snap(struct snap *snap); -struct snap *grow_snap(struct snap *snap, uint64_t nr_blk_descs); -void append_snap(int fd, struct snap_hdr *hdr, struct snap *snap); -void hash_snap(struct snap *snap, uint8_t *md, int hash_algo); -void walk_snap(int fd, struct snap_hdr *hdr, - int (*fn)(struct snap *, void *), void *arg); -uint8_t *alloc_buf(size_t size); -void free_buf(uint8_t *buf); -void read_blk(int fd, uint8_t *buf, struct blk_desc *blk_desc); -void append_blk(int fd, struct blk_hdr *hdr, uint8_t *buf, - struct blk_desc *blk_desc); -void hash_blk(uint8_t *buf, size_t size, uint8_t *md, int hash_algo); diff --git a/dup-check.1 b/dup-check.1 @@ -1,25 +0,0 @@ -.Dd April 18, 2019 -.Dt DUP-CHECK 1 -.Os -.Sh NAME -.Nm dup-check -.Nd Perform consistency checks on a dedup repo -.Sh SYNOPSIS -.Nm dup-check -.Op Fl v -.Op repo -.Sh DESCRIPTION -.Nm -performs consistency checks on a dedup repo. -If no -.Ar repo -is specified, then the current directory -is assumed to be the repository. -.Sh OPTIONS -.Bl -tag -width "-v" -.It Fl v -Enable verbose mode. -.El -.Sh AUTHORS -.An Dimitris Papastamos Aq Mt sin@2f30.org , -.An z3bra Aq Mt contactatz3bradotorg . diff --git a/dup-check.c b/dup-check.c @@ -1,157 +0,0 @@ -#include <sys/types.h> -#include <sys/stat.h> -#include <sys/file.h> - -#include <err.h> -#include <fcntl.h> -#include <stdio.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -#include "arg.h" -#include "blake2.h" -#include "dedup.h" - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; - -int verbose; -char *argv0; - -static void -print_md(FILE *fp, uint8_t *md, size_t size) -{ - size_t i; - - for (i = 0; i < size; i++) - fprintf(fp, "%02x", md[i]); -} - -/* - * Hash every block referenced by the given snapshot - * and compare its hash with the one stored in the corresponding - * block descriptor. - */ -static int -check_snap(struct snap *snap, void *arg) -{ - struct compr_ctx ctx; - uint8_t *buf; - int *ret = arg; - uint64_t i; - - if (verbose > 0) { - fprintf(stderr, "Checking snapshot: "); - print_md(stderr, snap->md, sizeof(snap->md)); - fputc('\n', stderr); - } - - if (compr_init(&ctx, compr_algo) < 0) - errx(1, "compr_init failed"); - buf = alloc_buf(compr_size(&ctx, BLKSIZE_MAX)); - for (i = 0; i < snap->nr_blk_descs; i++) { - uint8_t md[MD_SIZE]; - struct blk_desc *blk_desc; - - blk_desc = &snap->blk_desc[i]; - read_blk(sfd, buf, blk_desc); - hash_blk(buf, blk_desc->size, md, hash_algo); - - if (memcmp(blk_desc->md, md, sizeof(blk_desc->md)) == 0) - continue; - - fprintf(stderr, "Block hash mismatch\n"); - fprintf(stderr, " Expected hash: "); - print_md(stderr, blk_desc->md, sizeof(blk_desc->md)); - fputc('\n', stderr); - fprintf(stderr, " Actual hash: "); - print_md(stderr, md, sizeof(md)); - fputc('\n', stderr); - fprintf(stderr, " Offset: %llu\n", - (unsigned long long)blk_desc->offset); - fprintf(stderr, " Size: %llu\n", - (unsigned long long)blk_desc->size); - *ret = -1; - } - free_buf(buf); - compr_final(&ctx); - return WALK_CONTINUE; -} - -static void -init(void) -{ - ifd = open(SNAPSF, O_RDONLY, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, O_RDONLY, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - xlseek(ifd, 0, SEEK_SET); - load_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - load_blk_hdr(sfd, &blk_hdr, &compr_algo, &hash_algo); -} - -static void -term(void) -{ - close(ifd); - close(sfd); -} - -static void -usage(void) -{ - fprintf(stderr, "usage: %s [-v] [repo]\n", argv0); - exit(1); -} - -int -main(int argc, char *argv[]) -{ - char *repo = NULL; - int ret; - - ARGBEGIN { - case 'v': - verbose++; - break; - default: - usage(); - } ARGEND - - switch (argc) { - case 0: - repo = "."; - break; - case 1: - repo = argv[0]; - break; - default: - usage(); - }; - - if (chdir(repo) < 0) - err(1, "chdir: %s", repo); - - init(); - ret = 0; - walk_snap(ifd, &snap_hdr, check_snap, &ret); - if (ret != 0) - errx(1, "%s or %s is corrupted", SNAPSF, STOREF); - term(); - return 0; -} diff --git a/dup-info.1 b/dup-info.1 @@ -1,37 +0,0 @@ -.Dd April 18, 2019 -.Dt DUP-INFO 1 -.Os -.Sh NAME -.Nm dup-info -.Nd Print information about a dedup repository -.Sh SYNOPSIS -.Nm dup-info -.Op Fl tv -.Op repo -.Sh DESCRIPTION -.Nm -prints information about a dedup repository. -If no -.Ar repo -is specified, then the current directory -is assumed to be the repository. -.Sh OPTIONS -.Bl -tag -width "-v" -.It Fl t -Enable terse mode. -The output fields are as follows: -.br -[original dataset size] -[compressed dataset size] -[deduplicated dataset size] -[deduplication ratio] -[min block size] -[average block size] -[max block size] -[number of unique blocks] -.It Fl v -Enable verbose mode. -.El -.Sh AUTHORS -.An Dimitris Papastamos Aq Mt sin@2f30.org , -.An z3bra Aq Mt contactatz3bradotorg . diff --git a/dup-info.c b/dup-info.c @@ -1,141 +0,0 @@ -#include <sys/types.h> -#include <sys/stat.h> -#include <sys/file.h> - -#include <err.h> -#include <fcntl.h> -#include <stdio.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -#include "arg.h" -#include "blake2.h" -#include "dedup.h" - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; - -int verbose; -char *argv0; - -static void -print_info(int tflag) -{ - struct stats *st = &snap_hdr.st; - - if (verbose > 0) { - fprintf(stderr, "Compression algorithm: %s\n", - compr_type2name(compr_algo)); - fprintf(stderr, "Hash algorithm: %s\n", - hash_type2name(hash_algo)); - } - - if (st->nr_blks == 0) - return; - - if (!tflag) { - fprintf(stderr, "Original size: %llu bytes\n", - (unsigned long long)st->orig_size); - fprintf(stderr, "Compressed size: %llu bytes\n", - (unsigned long long)st->compr_size); - fprintf(stderr, "Deduplicated size: %llu bytes\n", - (unsigned long long)st->dedup_size); - fprintf(stderr, "Deduplication ratio: %.2f\n", - (double)st->orig_size / st->dedup_size); - fprintf(stderr, "Min/avg/max block size: %llu/%llu/%llu bytes\n", - (unsigned long long)st->min_blk_size, - (unsigned long long)st->dedup_size / st->nr_blks, - (unsigned long long)st->max_blk_size); - fprintf(stderr, "Number of unique blocks: %llu\n", - (unsigned long long)st->nr_blks); - } else { - /* terse mode */ - fprintf(stderr, "%llu %llu %llu %.2f %llu %llu %llu %llu\n", - (unsigned long long)st->orig_size, - (unsigned long long)st->compr_size, - (unsigned long long)st->dedup_size, - (double)st->orig_size / st->dedup_size, - (unsigned long long)st->min_blk_size, - (unsigned long long)st->dedup_size / st->nr_blks, - (unsigned long long)st->max_blk_size, - (unsigned long long)st->nr_blks); - } -} - -static void -init(void) -{ - ifd = open(SNAPSF, O_RDONLY, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, O_RDONLY, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - xlseek(ifd, 0, SEEK_SET); - load_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - load_blk_hdr(sfd, &blk_hdr, &compr_algo, &hash_algo); -} - -static void -term(void) -{ - close(ifd); - close(sfd); -} - -static void -usage(void) -{ - fprintf(stderr, "usage: %s [-tv] [repo]\n", argv0); - exit(1); -} - -int -main(int argc, char *argv[]) -{ - char *repo = NULL; - int tflag = 0; - - ARGBEGIN { - case 't': - tflag = 1; - break; - case 'v': - verbose++; - break; - default: - usage(); - } ARGEND - - switch (argc) { - case 0: - repo = "."; - break; - case 1: - repo = argv[0]; - break; - default: - usage(); - }; - - if (chdir(repo) < 0) - err(1, "chdir: %s", repo); - - init(); - print_info(tflag); - term(); - return 0; -} diff --git a/dup-init.1 b/dup-init.1 @@ -24,15 +24,15 @@ Enable verbose mode. .It Fl H Ar hash The cryptographic hash function used to identify unique blocks in the store. -The supported hash functions are blake2b, blake2bp, blake2s and blake2sp. +The supported hash functions are blake2b. This flag only has an effect when initializing the repository. By default blake2b is used. .It Fl Z Ar compressor The compressor function used to compress the blocks in the store. -The supported compressor functions are none, lz4 and snappy. +The supported compressor functions are none and snappy. This flag only has an effect when initializing the repository. -By default lz4 is used. +By default snappy is used. .El .Sh AUTHORS .An Dimitris Papastamos Aq Mt sin@2f30.org , diff --git a/dup-init.c b/dup-init.c @@ -1,67 +1,21 @@ #include <sys/types.h> #include <sys/stat.h> -#include <sys/file.h> #include <err.h> #include <fcntl.h> #include <stdio.h> -#include <stdint.h> #include <stdlib.h> -#include <string.h> #include <unistd.h> #include "arg.h" -#include "blake2.h" -#include "dedup.h" - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; +#include "config.h" +#include "block.h" +#include "snap.h" int verbose; char *argv0; static void -init(void) -{ - int flags; - - flags = O_RDWR | O_CREAT | O_EXCL; - ifd = open(SNAPSF, flags, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, flags, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - init_snap_hdr(&snap_hdr); - init_blk_hdr(&blk_hdr, compr_algo, hash_algo); -} - -static void -term(void) -{ - xlseek(ifd, 0, SEEK_SET); - write_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - write_blk_hdr(sfd, &blk_hdr); - - fsync(ifd); - fsync(sfd); - - close(ifd); - close(sfd); -} - -static void usage(void) { fprintf(stderr, "usage: %s [-v] [-H hash] [-Z compressor] [repo]\n", argv0); @@ -71,29 +25,19 @@ usage(void) int main(int argc, char *argv[]) { - char *hash_name = NULL, *compr_name = NULL; + struct bctx *bctx; /* block context */ + struct bparam bpar; char *repo; + bpar.calgo = bparamdef()->calgo; + bpar.halgo = bparamdef()->halgo; + ARGBEGIN { case 'H': - hash_name = EARGF(usage()); - if (strcmp(hash_name, "?") == 0) { - hash_list(STDERR_FILENO); - return 0; - } - hash_algo = hash_name2type(hash_name); - if (hash_algo < 0) - errx(1, "unknown hash: %s", hash_name); + bpar.halgo = EARGF(usage()); break; case 'Z': - compr_name = EARGF(usage()); - if (strcmp(compr_name, "?") == 0) { - compr_list(STDERR_FILENO); - return 0; - } - compr_algo = compr_name2type(compr_name); - if (compr_algo < 0) - errx(1, "unknown compressor: %s", compr_name); + bpar.calgo = EARGF(usage()); break; case 'v': verbose++; @@ -117,7 +61,10 @@ main(int argc, char *argv[]) if (chdir(repo) < 0) err(1, "chdir: %s", repo); - init(); - term(); + mkdir(ARCHIVEPATH, 0700); + if (bcreat(STORAGEPATH, 0600, &bpar, &bctx) < 0) + errx(1, "bcreat: failed"); + if (bclose(bctx) < 0) + errx(1, "bclose: failed"); return 0; } diff --git a/dup-list.1 b/dup-list.1 @@ -1,25 +0,0 @@ -.Dd April 18, 2019 -.Dt DUP-LIST 1 -.Os -.Sh NAME -.Nm dup-list -.Nd List snapshots from a dedup repository -.Sh SYNOPSIS -.Nm dup-list -.Op Fl v -.Op repo -.Sh DESCRIPTION -.Nm -lists snapshots from a dedup repository. -If no -.Ar repo -is specified, then the current directory -is assumed to be the repository. -.Sh OPTIONS -.Bl -tag -width "-v" -.It Fl v -Enable verbose mode. -.El -.Sh AUTHORS -.An Dimitris Papastamos Aq Mt sin@2f30.org , -.An z3bra Aq Mt contactatz3bradotorg . diff --git a/dup-list.c b/dup-list.c @@ -1,113 +0,0 @@ -#include <sys/types.h> -#include <sys/stat.h> -#include <sys/file.h> - -#include <err.h> -#include <fcntl.h> -#include <stdio.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -#include "arg.h" -#include "blake2.h" -#include "dedup.h" - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; - -int verbose; -char *argv0; - -static void -print_md(FILE *fp, uint8_t *md, size_t size) -{ - size_t i; - - for (i = 0; i < size; i++) - fprintf(fp, "%02x", md[i]); -} - -static int -list(struct snap *snap, void *arg) -{ - print_md(stdout, snap->md, sizeof(snap->md)); - if (snap->msg[0] != '\0') - printf("\t%s\n", snap->msg); - else - putchar('\n'); - return WALK_CONTINUE; -} - -static void -init(void) -{ - ifd = open(SNAPSF, O_RDONLY, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, O_RDONLY, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - xlseek(ifd, 0, SEEK_SET); - load_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - load_blk_hdr(sfd, &blk_hdr, &compr_algo, &hash_algo); -} - -static void -term(void) -{ - close(ifd); - close(sfd); -} - -static void -usage(void) -{ - fprintf(stderr, "usage: %s [-v] [repo]\n", argv0); - exit(1); -} - -int -main(int argc, char *argv[]) -{ - char *repo = NULL; - - ARGBEGIN { - case 'v': - verbose++; - break; - default: - usage(); - } ARGEND - - switch (argc) { - case 0: - repo = "."; - break; - case 1: - repo = argv[0]; - break; - default: - usage(); - }; - - if (chdir(repo) < 0) - err(1, "chdir: %s", repo); - - init(); - walk_snap(ifd, &snap_hdr, list, NULL); - term(); - return 0; -} diff --git a/dup-migrate b/dup-migrate @@ -1,28 +0,0 @@ -#!/bin/sh -# -# Migrate an old dedup repo to a new one. -# This is useful when there is an ABI break -# in the deduplication repository file format. - -set -e - -usage() -{ - echo usage: dup-migrate old-repo new-repo >&2 - exit 1 -} - -if [ ! "$#" -eq 2 ] -then - usage -fi - -oldrepo="$1" -newrepo="$2" - -dup-init "$newrepo" -dup-list-old "$oldrepo" | awk '{print $1}' | while read id -do - dup-unpack-old "$id" "$oldrepo" | dup-pack "$newrepo" -done -sync diff --git a/dup-migrate.1 b/dup-migrate.1 @@ -1,26 +0,0 @@ -.Dd April 18, 2019 -.Dt DUP-MIGRATE 1 -.Os -.Sh NAME -.Nm dup-migrate -.Nd Migrate a dedup repository -.Sh SYNOPSIS -.Nm dup-migrate -.Ar old-repo -.Ar new-repo -.Sh DESCRIPTION -.Nm -migrates the -.Ar old-repo -to the -.Ar new-repo . -The -.Nm -script requires that the dup-list-old and -dup-unpack-old binaries are in the PATH. -These should be the most up to date binaries -that can operate on the -.Ar old-repo . -.Sh AUTHORS -.An Dimitris Papastamos Aq Mt sin@2f30.org , -.An z3bra Aq Mt contactatz3bradotorg . diff --git a/dup-pack.1 b/dup-pack.1 @@ -1,4 +1,4 @@ -.Dd April 18, 2019 +.Dd April 25, 2019 .Dt DUP-PACK 1 .Os .Sh NAME @@ -7,15 +7,14 @@ .Sh SYNOPSIS .Nm dup-pack .Op Fl v -.Op Fl m Ar message -.Op repo +.Op Fl r Ar repo +.Ar name .Sh DESCRIPTION .Nm deduplicates data from stdin. -If no -.Ar repo -is specified, then the current directory -is assumed to be the repository. +It creates a snapshot with the given +.Ar name +and stores it in the repository. .Pp .Nm does not track any file metadata so to deduplicate @@ -24,11 +23,12 @@ directory trees, an archival tool like should be used and piped into .Nm . .Sh OPTIONS -.Bl -tag -width "-m message" +.Bl -tag -width "-r repo" +.It Fl r Ar repo +Set repository directory. +By default the current working directory is used. .It Fl v Enable verbose mode. -.It Fl m Ar message -Attach a descriptive message to the snapshot. .El .Sh AUTHORS .An Dimitris Papastamos Aq Mt sin@2f30.org , diff --git a/dup-pack.c b/dup-pack.c @@ -1,202 +1,73 @@ #include <sys/types.h> #include <sys/stat.h> -#include <sys/file.h> #include <err.h> #include <fcntl.h> +#include <limits.h> #include <stdio.h> -#include <stdint.h> #include <stdlib.h> -#include <string.h> -#include <unistd.h> #include "arg.h" -#include "blake2.h" -#include "dedup.h" - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static struct icache *icache; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; +#include "block.h" +#include "chunker.h" +#include "config.h" +#include "snap.h" int verbose; char *argv0; -static void -dedup_chunk(struct snap *snap, uint8_t *chunkp, size_t chunk_size) -{ - uint8_t md[MD_SIZE]; - struct blk_desc blk_desc; - struct compr_ctx ctx; - uint8_t *compr_buf; - size_t n, csize; - - if (compr_init(&ctx, compr_algo) < 0) - errx(1, "compr_init failed"); - csize = compr_size(&ctx, BLKSIZE_MAX); - compr_buf = alloc_buf(csize); - - n = compr(&ctx, chunkp, compr_buf, chunk_size, csize); - hash_blk(compr_buf, n, md, hash_algo); - - snap_hdr.st.orig_size += chunk_size; - snap_hdr.st.compr_size += n; - - memcpy(blk_desc.md, md, sizeof(blk_desc.md)); - if (lookup_icache(icache, &blk_desc) < 0) { - blk_desc.offset = blk_hdr.size; - blk_desc.size = n; - - snap->blk_desc[snap->nr_blk_descs++] = blk_desc; - append_blk(sfd, &blk_hdr, compr_buf, &blk_desc); - - insert_icache(icache, &blk_desc); - - snap_hdr.st.dedup_size += blk_desc.size; - snap_hdr.st.nr_blks++; - - if (blk_desc.size > snap_hdr.st.max_blk_size) - snap_hdr.st.max_blk_size = blk_desc.size; - if (blk_desc.size < snap_hdr.st.min_blk_size) - snap_hdr.st.min_blk_size = blk_desc.size; - } else { - snap->blk_desc[snap->nr_blk_descs++] = blk_desc; - } - - free(compr_buf); - compr_final(&ctx); -} - -static void -dedup(int fd, char *msg) +static int +pack(struct sctx *sctx, struct bctx *bctx) { - struct snap *snap; - struct chunker *chunker; + struct chunker *c; - snap = alloc_snap(); - chunker = alloc_chunker(fd, BLKSIZE_MIN, BLKSIZE_MAX, - HASHMASK_BITS, WINSIZE); + if ((c = copen(0, BSIZEMIN, BSIZEMAX, HMASKBITS, WINSIZE)) == NULL) + return -1; - while (fill_chunker(chunker) > 0) { - uint8_t *chunkp; - size_t chunk_size; - - chunkp = get_chunk(chunker, &chunk_size); - snap = grow_snap(snap, snap->nr_blk_descs + 1); - dedup_chunk(snap, chunkp, chunk_size); - drain_chunker(chunker); - } + while (cfill(c) > 0) { + unsigned char md[MDSIZE]; + void *buf; + size_t n; - if (snap->nr_blk_descs > 0) { - if (msg != NULL) { - size_t size; - - size = strlen(msg) + 1; - if (size > sizeof(snap->msg)) - size = sizeof(snap->msg); - memcpy(snap->msg, msg, size); - snap->msg[size - 1] = '\0'; + buf = cget(c, &n); + if (bput(bctx, buf, n, md) < 0) { + cclose(c); + return -1; } - hash_snap(snap, snap->md, hash_algo); - append_snap(ifd, &snap_hdr, snap); - - if (verbose > 0) { - unsigned long long hits, misses; - double hitratio; - icache_stats(icache, &hits, &misses); - hitratio = (double)hits / (hits + misses); - fprintf(stderr, "Index cache hit percentage: %.2f%%\n", - 100 * hitratio); + if (sput(sctx, md) < 0) { + cclose(c); + return -1; } - } - - free_chunker(chunker); - free_snap(snap); -} -static int -build_icache(struct snap *snap, void *arg) -{ - struct compr_ctx ctx; - uint8_t *buf; - uint64_t i; - - if (compr_init(&ctx, compr_algo) < 0) - errx(1, "compr_init failed"); - buf = alloc_buf(compr_size(&ctx, BLKSIZE_MAX)); - for (i = 0; i < snap->nr_blk_descs; i++) { - struct blk_desc *blk_desc; - - blk_desc = &snap->blk_desc[i]; - insert_icache(icache, blk_desc); + if (cdrain(c) < 0) { + cclose(c); + return -1; + } } - free(buf); - compr_final(&ctx); - return WALK_CONTINUE; -} - -static void -init(void) -{ - ifd = open(SNAPSF, O_RDWR, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, O_RDWR, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - - xlseek(ifd, 0, SEEK_SET); - load_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - load_blk_hdr(sfd, &blk_hdr, &compr_algo, &hash_algo); - - icache = alloc_icache(); - walk_snap(ifd, &snap_hdr, build_icache, NULL); -} - -static void -term(void) -{ - xlseek(ifd, 0, SEEK_SET); - write_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - write_blk_hdr(sfd, &blk_hdr); - - fsync(ifd); - fsync(sfd); - - close(ifd); - close(sfd); - - free_icache(icache); + return cclose(c); } static void usage(void) { - fprintf(stderr, "usage: %s [-v] [-m message] [repo]\n", argv0); + fprintf(stderr, "usage: %s [-v] [-r repo] name\n", argv0); exit(1); } int main(int argc, char *argv[]) { - char *repo, *msg = NULL; + char path[PATH_MAX]; + struct sctx *sctx; + struct bctx *bctx; + struct bparam bparam; + char *repo = "."; ARGBEGIN { - case 'm': - msg = EARGF(usage()); - break; + case 'r': + repo = EARGF(usage()); + break; case 'v': verbose++; break; @@ -204,22 +75,23 @@ main(int argc, char *argv[]) usage(); } ARGEND - switch (argc) { - case 0: - repo = "."; - break; - case 1: - repo = argv[0]; - break; - default: + if (argc != 1) usage(); - }; - if (chdir(repo) < 0) - err(1, "chdir: %s", repo); + snprintf(path, sizeof(path), "%s/archive/%s", repo, argv[0]); + if (screat(path, 0600, &sctx) < 0) + errx(1, "screat: %s: failed", path); + + snprintf(path, sizeof(path), "%s/storage", repo); + if (bopen(path, O_RDWR, 0600, &bparam, &bctx) <0) + errx(1, "bopen: %s: failed", path); + + if (pack(sctx, bctx) < 0) + errx(1, "pack: failed"); - init(); - dedup(STDIN_FILENO, msg); - term(); + if (bclose(bctx) < 0) + errx(1, "bclose: failed"); + if (sclose(sctx) < 0) + errx(1, "sclose: failed"); return 0; } diff --git a/dup-unpack.1 b/dup-unpack.1 @@ -1,4 +1,4 @@ -.Dd April 18, 2019 +.Dd April 25, 2019 .Dt DUP-UNPACK 1 .Os .Sh NAME @@ -7,19 +7,18 @@ .Sh SYNOPSIS .Nm dup-unpack .Op Fl v -.Ar id -.Op repo +.Op Fl r Ar repo +.Ar name .Sh DESCRIPTION .Nm extracts the snapshot specified by -.Ar id +.Ar name from the dedup repository and writes the data to stdout. -If no -.Ar repo -is specified, then the current directory -is assumed to be the repository. .Sh OPTIONS -.Bl -tag -width "-v" +.Bl -tag -width "-r repo" +.It Fl r Ar repo +Set repository directory. +By default the current working directory is used. .It Fl v Enable verbose mode. .El diff --git a/dup-unpack.c b/dup-unpack.c @@ -1,109 +1,89 @@ #include <sys/types.h> #include <sys/stat.h> -#include <sys/file.h> #include <err.h> #include <fcntl.h> +#include <limits.h> #include <stdio.h> -#include <stdint.h> #include <stdlib.h> -#include <string.h> #include <unistd.h> #include "arg.h" -#include "blake2.h" -#include "dedup.h" - -struct extract_args { - uint8_t *md; - int fd; - int ret; -}; - -static struct snap_hdr snap_hdr; -static struct blk_hdr blk_hdr; -static int ifd; -static int sfd; -static int hash_algo = HASH_BLAKE2B; -static int compr_algo = COMPR_LZ4; +#include "block.h" +#include "config.h" +#include "snap.h" int verbose; char *argv0; -static int -extract(struct snap *snap, void *arg) +static ssize_t +xwrite(int fd, void *buf, size_t nbytes) { - uint8_t *buf[2]; - struct extract_args *args = arg; - struct compr_ctx ctx; - uint64_t i; - - if (memcmp(snap->md, args->md, sizeof(snap->md)) != 0) - return WALK_CONTINUE; - - if (compr_init(&ctx, compr_algo) < 0) - errx(1, "compr_init failed"); - buf[0] = alloc_buf(BLKSIZE_MAX); - buf[1] = alloc_buf(compr_size(&ctx, BLKSIZE_MAX)); - for (i = 0; i < snap->nr_blk_descs; i++) { - struct blk_desc *blk_desc; - size_t blksize; - - blk_desc = &snap->blk_desc[i]; - read_blk(sfd, buf[1], blk_desc); - blksize = decompr(&ctx, buf[1], buf[0], blk_desc->size, BLKSIZE_MAX); - xwrite(args->fd, buf[0], blksize); + unsigned char *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = write(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; } - free_buf(buf[1]); - free_buf(buf[0]); - compr_final(&ctx); - args->ret = 0; - return WALK_STOP; -} - -static void -init(void) -{ - ifd = open(SNAPSF, O_RDONLY, 0600); - if (ifd < 0) - err(1, "open %s", SNAPSF); - - sfd = open(STOREF, O_RDONLY, 0600); - if (sfd < 0) - err(1, "open %s", STOREF); - - if (flock(ifd, LOCK_NB | LOCK_EX) < 0 || - flock(sfd, LOCK_NB | LOCK_EX) < 0) - err(1, "flock"); - - xlseek(ifd, 0, SEEK_SET); - load_snap_hdr(ifd, &snap_hdr); - xlseek(sfd, 0, SEEK_SET); - load_blk_hdr(sfd, &blk_hdr, &compr_algo, &hash_algo); + return total; } -static void -term(void) +static int +unpack(struct sctx *sctx, struct bctx *bctx) { - close(ifd); - close(sfd); + unsigned char md[MDSIZE]; + void *buf; + int sn; + + buf = malloc(BSIZEMAX); + if (buf == NULL) + return -1; + while ((sn = sget(sctx, md)) == MDSIZE) { + size_t n = BSIZEMAX; + + if (bget(bctx, md, buf, &n) < 0) { + free(buf); + return -1; + } + if (xwrite(1, buf, n) != n) { + free(buf); + return -1; + } + } + free(buf); + if (sn < 0) + return -1; + return 0; } static void usage(void) { - fprintf(stderr, "usage: %s [-v] id [repo]\n", argv0); + fprintf(stderr, "usage: %s [-v] [-r repo] name\n", argv0); exit(1); } int main(int argc, char *argv[]) { - uint8_t md[MD_SIZE]; - char *repo, *id = NULL; - struct extract_args args; + char path[PATH_MAX]; + struct sctx *sctx; + struct bctx *bctx; + struct bparam bparam; + char *repo = "."; ARGBEGIN { + case 'r': + repo = EARGF(usage()); + break; case 'v': verbose++; break; @@ -111,30 +91,24 @@ main(int argc, char *argv[]) usage(); } ARGEND - switch (argc) { - case 1: - id = argv[0]; - repo = "."; - break; - case 2: - id = argv[0]; - repo = argv[1]; - break; - default: + if (argc != 1) usage(); - }; - - if (chdir(repo) < 0) - err(1, "chdir: %s", repo); - - init(); - str2bin(id, md); - args.md = md; - args.fd = STDOUT_FILENO; - args.ret = -1; - walk_snap(ifd, &snap_hdr, extract, &args); - if (args.ret != 0) - errx(1, "unknown snapshot: %s", id); - term(); + + snprintf(path, sizeof(path), "%s/archive/%s", repo, argv[0]); + if (sopen(path, O_RDONLY, 0600, &sctx) < 0) + errx(1, "sopen: %s: failed", path); + + snprintf(path, sizeof(path), "%s/storage", repo); + if (bopen(path, O_RDONLY, 0600, &bparam, &bctx) <0) + errx(1, "bopen: %s: failed", path); + + if (unpack(sctx, bctx) < 0) + errx(1, "dedup: failed"); + + if (bclose(bctx) < 0) + errx(1, "bclose: failed"); + if (sclose(sctx) < 0) + errx(1, "sclose: failed"); + return 0; } diff --git a/hash-blake2b.c b/hash-blake2b.c @@ -1,26 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" - -int -blake2bi(struct hash_ctx *ctx, size_t n) -{ - return blake2b_init(&ctx->u.blake2b_ctx, n); -} - -int -blake2bu(struct hash_ctx *ctx, const void *buf, size_t n) -{ - return blake2b_update(&ctx->u.blake2b_ctx, buf, n); -} - -int -blake2bf(struct hash_ctx *ctx, void *buf, size_t n) -{ - return blake2b_final(&ctx->u.blake2b_ctx, buf, n); -} diff --git a/hash-blake2bp.c b/hash-blake2bp.c @@ -1,26 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" - -int -blake2bpi(struct hash_ctx *ctx, size_t n) -{ - return blake2bp_init(&ctx->u.blake2bp_ctx, n); -} - -int -blake2bpu(struct hash_ctx *ctx, const void *buf, size_t n) -{ - return blake2bp_update(&ctx->u.blake2bp_ctx, buf, n); -} - -int -blake2bpf(struct hash_ctx *ctx, void *buf, size_t n) -{ - return blake2bp_final(&ctx->u.blake2bp_ctx, buf, n); -} diff --git a/hash-blake2s.c b/hash-blake2s.c @@ -1,26 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" - -int -blake2si(struct hash_ctx *ctx, size_t n) -{ - return blake2s_init(&ctx->u.blake2s_ctx, n); -} - -int -blake2su(struct hash_ctx *ctx, const void *buf, size_t n) -{ - return blake2s_update(&ctx->u.blake2s_ctx, buf, n); -} - -int -blake2sf(struct hash_ctx *ctx, void *buf, size_t n) -{ - return blake2s_final(&ctx->u.blake2s_ctx, buf, n); -} diff --git a/hash-blake2sp.c b/hash-blake2sp.c @@ -1,26 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" - -int -blake2spi(struct hash_ctx *ctx, size_t n) -{ - return blake2sp_init(&ctx->u.blake2sp_ctx, n); -} - -int -blake2spu(struct hash_ctx *ctx, const void *buf, size_t n) -{ - return blake2sp_update(&ctx->u.blake2sp_ctx, buf, n); -} - -int -blake2spf(struct hash_ctx *ctx, void *buf, size_t n) -{ - return blake2sp_final(&ctx->u.blake2sp_ctx, buf, n); -} diff --git a/hash.c b/hash.c @@ -1,94 +0,0 @@ -#include <sys/types.h> - -#include <stdint.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <strings.h> - -#include "blake2.h" -#include "dedup.h" - -static struct hash_ops { - int (*init)(struct hash_ctx *ctx, size_t n); - int (*update)(struct hash_ctx *ctx, const void *buf, size_t n); - int (*final)(struct hash_ctx *ctx, void *buf, size_t n); -} hashes[NR_HASHES] = { - { - .init = blake2bi, - .update = blake2bu, - .final = blake2bf, - }, - { - .init = blake2bpi, - .update = blake2bpu, - .final = blake2bpf, - }, - { - .init = blake2si, - .update = blake2su, - .final = blake2sf, - }, - { - .init = blake2spi, - .update = blake2spu, - .final = blake2spf, - }, -}; - -static char *algomap[NR_HASHES] = { - [HASH_BLAKE2B] = "blake2b", - [HASH_BLAKE2BP] = "blake2bp", - [HASH_BLAKE2S] = "blake2s", - [HASH_BLAKE2SP] = "blake2sp", -}; - -int -hash_init(struct hash_ctx *ctx, int type, size_t n) -{ - if (type < 0 || type >= NR_HASHES) - return -1; - - ctx->ops = &hashes[type]; - return (*ctx->ops->init)(ctx, n); -} - -int -hash_update(struct hash_ctx *ctx, const void *buf, size_t n) -{ - return (*ctx->ops->update)(ctx, buf, n); -} - -int -hash_final(struct hash_ctx *ctx, void *buf, size_t n) -{ - return (*ctx->ops->final)(ctx, buf, n); -} - -int -hash_name2type(char *name) -{ - size_t i; - - for (i = 0; i < NR_HASHES; i++) - if (strcasecmp(algomap[i], name) == 0) - return i; - return -1; -} - -char * -hash_type2name(int type) -{ - if (type < 0 || type >= NR_HASHES) - return NULL; - return algomap[type]; -} - -void -hash_list(int fd) -{ - size_t i; - - for (i = 0; i < NR_HASHES; i++) - dprintf(fd, "%s\n", algomap[i]); -} diff --git a/icache.c b/icache.c @@ -1,114 +0,0 @@ -#include <sys/types.h> - -#include <err.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#include "blake2.h" -#include "dedup.h" -#include "tree.h" - -struct node { - struct blk_desc desc; - RB_ENTRY(node) e; -}; -RB_HEAD(icache_head, node); - -struct icache { - struct icache_head nodes; - unsigned long long hits; - unsigned long long misses; -}; - -static int -node_cmp(struct node *e1, struct node *e2) -{ - int r; - - r = memcmp(e1->desc.md, e2->desc.md, sizeof(e1->desc.md)); - if (r > 0) - return 1; - else if (r < 0) - return -1; - return 0; -} -static RB_PROTOTYPE(icache_head, node, e, node_cmp); -static RB_GENERATE(icache_head, node, e, node_cmp); - -static struct node * -alloc_node(struct blk_desc *desc) -{ - struct node *node; - - node = calloc(1, sizeof(*node)); - if (node == NULL) - err(1, "calloc"); - node->desc = *desc; - return node; -} - -static void -free_node(struct node *node) -{ - free(node); -} - -struct icache * -alloc_icache(void) -{ - struct icache *icache; - - icache = calloc(1, sizeof(*icache)); - if (icache == NULL) - err(1, "calloc"); - RB_INIT(&icache->nodes); - return icache; -} - -void -free_icache(struct icache *icache) -{ - struct node *node, *tmp; - - RB_FOREACH_SAFE(node, icache_head, &icache->nodes, tmp) { - RB_REMOVE(icache_head, &icache->nodes, node); - free_node(node); - } - free(icache); -} - -void -insert_icache(struct icache *icache, struct blk_desc *desc) -{ - struct node *node; - - node = alloc_node(desc); - if (RB_INSERT(icache_head, &icache->nodes, node) != NULL) - free_node(node); -} - -int -lookup_icache(struct icache *icache, struct blk_desc *desc) -{ - struct node *node, key; - - key.desc = *desc; - node = RB_FIND(icache_head, &icache->nodes, &key); - if (node != NULL) { - icache->hits++; - *desc = node->desc; - return 0; - } - icache->misses++; - return -1; -} - -void -icache_stats(struct icache *icache, unsigned long long *hits, - unsigned long long *misses) -{ - *hits = icache->hits; - *misses = icache->misses; -} - diff --git a/queue.h b/queue.h @@ -0,0 +1,534 @@ +/* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */ +/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +/* + * This file defines five types of data structures: singly-linked lists, + * lists, simple queues, tail queues and XOR simple queues. + * + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A simple queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * An XOR simple queue is used in the same way as a regular simple queue. + * The difference is that the head structure also includes a "cookie" that + * is XOR'd with the queue pointer (first, last or next) to generate the + * real pointer value. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) +#define _Q_INVALID ((void *)-1) +#define _Q_INVALIDATE(a) (a) = _Q_INVALID +#else +#define _Q_INVALIDATE(a) +#endif + +/* + * Singly-linked List definitions. + */ +#define SLIST_HEAD(name, type) \ +struct name { \ + struct type *slh_first; /* first element */ \ +} + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ +struct { \ + struct type *sle_next; /* next element */ \ +} + +/* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for((var) = SLIST_FIRST(head); \ + (var) != SLIST_END(head); \ + (var) = SLIST_NEXT(var, field)) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST(head); \ + (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked List functions. + */ +#define SLIST_INIT(head) { \ + SLIST_FIRST(head) = SLIST_END(head); \ +} + +#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ + (elm)->field.sle_next = (slistelm)->field.sle_next; \ + (slistelm)->field.sle_next = (elm); \ +} while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) do { \ + (elm)->field.sle_next = (head)->slh_first; \ + (head)->slh_first = (elm); \ +} while (0) + +#define SLIST_REMOVE_AFTER(elm, field) do { \ + (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE_HEAD(head, field) do { \ + (head)->slh_first = (head)->slh_first->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE(head, elm, type, field) do { \ + if ((head)->slh_first == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = \ + curelm->field.sle_next->field.sle_next; \ + } \ + _Q_INVALIDATE((elm)->field.sle_next); \ +} while (0) + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ +struct name { \ + struct type *lh_first; /* first element */ \ +} + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ +struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ +} + +/* + * List access methods. + */ +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_FOREACH(var, head, field) \ + for((var) = LIST_FIRST(head); \ + (var)!= LIST_END(head); \ + (var) = LIST_NEXT(var, field)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST(head); \ + (var) && ((tvar) = LIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * List functions. + */ +#define LIST_INIT(head) do { \ + LIST_FIRST(head) = LIST_END(head); \ +} while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ + (listelm)->field.le_next->field.le_prev = \ + &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + (elm)->field.le_next = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &(elm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.le_next = (head)->lh_first) != NULL) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ +} while (0) + +#define LIST_REMOVE(elm, field) do { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +#define LIST_REPLACE(elm, elm2, field) do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = \ + &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +/* + * Simple queue definitions. + */ +#define SIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ +} + +#define SIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define SIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqe_next; /* next element */ \ +} + +/* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for((var) = SIMPLEQ_FIRST(head); \ + (var) != SIMPLEQ_END(head); \ + (var) = SIMPLEQ_NEXT(var, field)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SIMPLEQ_FIRST(head); \ + (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Simple queue functions. + */ +#define SIMPLEQ_INIT(head) do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ +} while (0) + +#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ +} while (0) + +#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ + == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +#define SIMPLEQ_CONCAT(head1, head2) do { \ + if (!SIMPLEQ_EMPTY((head2))) { \ + *(head1)->sqh_last = (head2)->sqh_first; \ + (head1)->sqh_last = (head2)->sqh_last; \ + SIMPLEQ_INIT((head2)); \ + } \ +} while (0) + +/* + * XOR Simple queue definitions. + */ +#define XSIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqx_first; /* first element */ \ + struct type **sqx_last; /* addr of last next element */ \ + unsigned long sqx_cookie; \ +} + +#define XSIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqx_next; /* next element */ \ +} + +/* + * XOR Simple queue access methods. + */ +#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \ + (unsigned long)(ptr))) +#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) +#define XSIMPLEQ_END(head) NULL +#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) +#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) + + +#define XSIMPLEQ_FOREACH(var, head, field) \ + for ((var) = XSIMPLEQ_FIRST(head); \ + (var) != XSIMPLEQ_END(head); \ + (var) = XSIMPLEQ_NEXT(head, var, field)) + +#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = XSIMPLEQ_FIRST(head); \ + (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \ + (var) = (tvar)) + +/* + * XOR Simple queue functions. + */ +#define XSIMPLEQ_INIT(head) do { \ + arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \ + (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ +} while (0) + +#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqx_next = (head)->sqx_first) == \ + XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ + (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \ +} while (0) + +#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \ + *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ +} while (0) + +#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \ + XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ + (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \ +} while (0) + +#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqx_first = XSIMPLEQ_XOR(head, \ + (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ +} while (0) + +#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \ + (elm)->field.sqx_next)->field.sqx_next) \ + == XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = \ + XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ +} while (0) + + +/* + * Tail queue definitions. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * Tail queue access methods. + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) NULL +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) +/* XXX */ +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_EMPTY(head) \ + (TAILQ_FIRST(head) == TAILQ_END(head)) + +#define TAILQ_FOREACH(var, head, field) \ + for((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_NEXT(var, field)) + +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) + + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_PREV(var, headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_PREV(var, headname, field), 1); \ + (var) = (tvar)) + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) do { \ + (head)->tqh_first = NULL; \ + (head)->tqh_last = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ + (head)->tqh_first->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.tqe_next = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if (((elm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +#define TAILQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ + (elm2)->field.tqe_next->field.tqe_prev = \ + &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +#define TAILQ_CONCAT(head1, head2, field) do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ +} while (0) + +#endif /* !_SYS_QUEUE_H_ */ diff --git a/snap.c b/snap.c @@ -0,0 +1,249 @@ +/* Snapshot archive implementation */ +#include <sys/types.h> +#include <sys/stat.h> + +#include <fcntl.h> +#include <limits.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "config.h" +#include "queue.h" +#include "snap.h" + +extern int pack(unsigned char *dst, char *fmt, ...); +extern int unpack(unsigned char *src, char *fmt, ...); + +struct mdnode { + unsigned char md[MDSIZE]; + SLIST_ENTRY(mdnode) e; +}; + +struct sctx { + SLIST_HEAD(mdhead, mdnode) mdhead; + struct mdnode *mdnext; + int fd; + int rdonly; +}; + +static ssize_t +xread(int fd, void *buf, size_t nbytes) +{ + uint8_t *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = read(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; + } + return total; +} + +static ssize_t +xwrite(int fd, void *buf, size_t nbytes) +{ + uint8_t *bp = buf; + ssize_t total = 0; + + while (nbytes > 0) { + ssize_t n; + + n = write(fd, &bp[total], nbytes); + if (n < 0) + return -1; + else if (n == 0) + return total; + total += n; + nbytes -= n; + } + return total; +} + +static int +loadmd(struct sctx *sctx) +{ + struct mdnode *mdnode; + + mdnode = calloc(1, sizeof(*mdnode)); + if (mdnode == NULL) + return -1; + if (xread(sctx->fd, mdnode->md, MDSIZE) != MDSIZE) { + free(mdnode); + return -1; + } + SLIST_INSERT_HEAD(&sctx->mdhead, mdnode, e); + return 0; +} + +static int +initmdhead(struct sctx *sctx) +{ + struct stat st; + uint64_t i, n; + + if (fstat(sctx->fd, &st) < 0) + return -1; + n = st.st_size / MDSIZE; + for (i = 0; i < n; i++) { + if (loadmd(sctx) == 0) + continue; + + /* Cleanup */ + while (!SLIST_EMPTY(&sctx->mdhead)) { + struct mdnode *mdnode; + + mdnode = SLIST_FIRST(&sctx->mdhead); + SLIST_REMOVE(&sctx->mdhead, mdnode, mdnode, e); + free(mdnode); + } + return -1; + } + return 0; +} + +int +screat(char *path, int mode, struct sctx **sctx) +{ + int fd; + + if (path == NULL || sctx == NULL) + return -1; + + fd = open(path, O_RDWR | O_CREAT | O_EXCL, mode); + if (fd < 0) + return -1; + + *sctx = calloc(1, sizeof(**sctx)); + if (*sctx == NULL) { + close(fd); + return -1; + } + SLIST_INIT(&(*sctx)->mdhead); + (*sctx)->mdnext = NULL; + (*sctx)->fd = fd; + return 0; +} + +int +sopen(char *path, int flags, int mode, struct sctx **sctx) +{ + int fd; + + if (path == NULL || sctx == NULL) + return -1; + + fd = open(path, flags, mode); + if (fd < 0) + return -1; + + *sctx = calloc(1, sizeof(*sctx)); + if (*sctx == NULL) { + close(fd); + return -1; + } + + SLIST_INIT(&(*sctx)->mdhead); + (*sctx)->mdnext = NULL; + (*sctx)->fd = fd; + (*sctx)->rdonly = flags == O_RDONLY; + + if (initmdhead(*sctx) < 0) { + free(*sctx); + close(fd); + return -1; + } + return 0; +} + +int +sget(struct sctx *sctx, unsigned char *md) +{ + struct mdnode *mdnode; + + if (sctx == NULL || md == NULL) + return -1; + + mdnode = sctx->mdnext; + if (mdnode == NULL) + mdnode = SLIST_FIRST(&sctx->mdhead); + else + mdnode = SLIST_NEXT(mdnode, e); + sctx->mdnext = mdnode; + if (mdnode != NULL) { + memcpy(md, mdnode->md, MDSIZE); + return MDSIZE; + } + return 0; +} + +int +sput(struct sctx *sctx, unsigned char *md) +{ + struct mdnode *mdnode; + + if (sctx == NULL || md == NULL) + return -1; + + mdnode = calloc(1, sizeof(*mdnode)); + if (mdnode == NULL) + return -1; + memcpy(mdnode->md, md, MDSIZE); + SLIST_INSERT_HEAD(&sctx->mdhead, mdnode, e); + return 0; +} + +int +ssync(struct sctx *sctx) +{ + struct mdnode *mdnode; + + if (sctx == NULL) + return -1; + + if (sctx->rdonly) + return 0; + + if (lseek(sctx->fd, 0, SEEK_SET) < 0) + return -1; + SLIST_FOREACH(mdnode, &sctx->mdhead, e) { + if (xwrite(sctx->fd, mdnode->md, MDSIZE) != MDSIZE) + return -1; + } + fsync(sctx->fd); + return 0; +} + +int +sclose(struct sctx *sctx) +{ + int r; + + if (sctx == NULL) + return -1; + + if (ssync(sctx) < 0) + return -1; + + /* Cleanup */ + while (!SLIST_EMPTY(&sctx->mdhead)) { + struct mdnode *mdnode; + + mdnode = SLIST_FIRST(&sctx->mdhead); + SLIST_REMOVE(&sctx->mdhead, mdnode, mdnode, e); + free(mdnode); + } + + r = close(sctx->fd); + free(sctx); + return r; +} diff --git a/snap.h b/snap.h @@ -0,0 +1,8 @@ +struct sctx; + +extern int screat(char *path, int mode, struct sctx **sctx); +extern int sopen(char *path, int flags, int mode, struct sctx **sctx); +extern int sget(struct sctx *sctx, unsigned char *md); +extern int sput(struct sctx *sctx, unsigned char *md); +extern int ssync(struct sctx *sctx); +extern int sclose(struct sctx *sctx); diff --git a/types.c b/types.c @@ -1,192 +0,0 @@ -#include <sys/types.h> - -#include <assert.h> -#include <err.h> -#include <stdio.h> -#include <stdint.h> -#include <stdlib.h> - -#include "blake2.h" -#include "dedup.h" - -void -read_snap_hdr(int fd, struct snap_hdr *hdr) -{ - uint8_t buf[SNAP_HDR_SIZE]; - int n; - - if (xread(fd, buf, sizeof(buf)) == 0) - errx(1, "%s: unexpected EOF", __func__); - - n = unpack(buf, "qqq", - &hdr->flags, - &hdr->size, - &hdr->nr_snaps); - - n += unpack(&buf[n], "qqqqqq", - &hdr->st.orig_size, - &hdr->st.compr_size, - &hdr->st.dedup_size, - &hdr->st.min_blk_size, - &hdr->st.max_blk_size, - &hdr->st.nr_blks); - - n += unpack(&buf[n], "qqqq", - &hdr->st.reserved[0], - &hdr->st.reserved[1], - &hdr->st.reserved[2], - &hdr->st.reserved[3]); - - assert(n == SNAP_HDR_SIZE); -} - -void -write_snap_hdr(int fd, struct snap_hdr *hdr) -{ - uint8_t buf[SNAP_HDR_SIZE]; - int n; - - n = pack(buf, "qqq", - hdr->flags, - hdr->size, - hdr->nr_snaps); - - n += pack(&buf[n], "qqqqqq", - hdr->st.orig_size, - hdr->st.compr_size, - hdr->st.dedup_size, - hdr->st.min_blk_size, - hdr->st.max_blk_size, - hdr->st.nr_blks); - - n += pack(&buf[n], "qqqq", - hdr->st.reserved[0], - hdr->st.reserved[1], - hdr->st.reserved[2], - hdr->st.reserved[3]); - - assert(n == SNAP_HDR_SIZE); - xwrite(fd, buf, n); -} - -void -read_blk_hdr(int fd, struct blk_hdr *hdr) -{ - uint8_t buf[BLK_HDR_SIZE]; - int n; - - if (xread(fd, buf, sizeof(buf)) == 0) - errx(1, "%s: unexpected EOF", __func__); - - n = unpack(buf, "qq", - &hdr->flags, - &hdr->size); - - assert(n == BLK_HDR_SIZE); -} - -void -write_blk_hdr(int fd, struct blk_hdr *hdr) -{ - uint8_t buf[BLK_HDR_SIZE]; - int n; - - n = pack(buf, "qq", - hdr->flags, - hdr->size); - - assert(n == BLK_HDR_SIZE); - xwrite(fd, buf, n); -} - -void -read_blk_desc(int fd, struct blk_desc *desc) -{ - uint8_t buf[BLK_DESC_SIZE]; - char fmt[BUFSIZ]; - int n; - - if (xread(fd, buf, sizeof(buf)) == 0) - errx(1, "%s: unexpected EOF", __func__); - - snprintf(fmt, sizeof(fmt), "'%dqq", MD_SIZE); - n = unpack(buf, fmt, - desc->md, - &desc->offset, - &desc->size); - - assert(n == BLK_DESC_SIZE); -} - -void -write_blk_desc(int fd, struct blk_desc *desc) -{ - uint8_t buf[BLK_DESC_SIZE]; - char fmt[BUFSIZ]; - int n; - - snprintf(fmt, sizeof(fmt), "'%dqq", MD_SIZE); - n = pack(buf, fmt, - desc->md, - desc->offset, - desc->size); - - assert(n == BLK_DESC_SIZE); - xwrite(fd, buf, n); -} - -void -read_snap(int fd, struct snap *snap) -{ - uint8_t buf[SNAPSHOT_SIZE]; - char fmt[BUFSIZ]; - int n; - - if (xread(fd, buf, sizeof(buf)) == 0) - errx(1, "%s: unexpected EOF", __func__); - - snprintf(fmt, sizeof(fmt), "q'%d'%dq", MSG_SIZE, MD_SIZE); - n = unpack(buf, fmt, - &snap->size, - snap->msg, - snap->md, - &snap->nr_blk_descs); - - assert(n == SNAPSHOT_SIZE); -}; - -void -read_snap_descs(int fd, struct snap *snap) -{ - uint64_t i; - - for (i = 0; i < snap->nr_blk_descs; i++) - read_blk_desc(fd, &snap->blk_desc[i]); -} - -void -write_snap(int fd, struct snap *snap) -{ - uint8_t buf[SNAPSHOT_SIZE]; - char fmt[BUFSIZ]; - int n; - - snprintf(fmt, sizeof(fmt), "q'%d'%dq", MSG_SIZE, MD_SIZE); - n = pack(buf, fmt, - snap->size, - snap->msg, - snap->md, - snap->nr_blk_descs); - - assert(n == SNAPSHOT_SIZE); - xwrite(fd, buf, n); -} - -void -write_snap_blk_descs(int fd, struct snap *snap) -{ - uint64_t i; - - for (i = 0; i < snap->nr_blk_descs; i++) - write_blk_desc(fd, &snap->blk_desc[i]); -} diff --git a/utils.c b/utils.c @@ -1,288 +0,0 @@ -#include <sys/types.h> - -#include <err.h> -#include <stdint.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -#include "blake2.h" -#include "dedup.h" - -static void -match_ver(uint64_t v) -{ - uint8_t maj, min; - - min = v & VER_MIN_MASK; - maj = (v >> VER_MAJ_SHIFT) & VER_MAJ_MASK; - if (maj == VER_MAJ && min == VER_MIN) - return; - errx(1, "format version mismatch: expected %u.%u but got %u.%u", - VER_MAJ, VER_MIN, maj, min); -} - -void -str2bin(char *s, uint8_t *d) -{ - size_t i, size = strlen(s) / 2; - - for (i = 0; i < size; i++, s += 2) - sscanf(s, "%2hhx", &d[i]); -} - -off_t -xlseek(int fd, off_t offset, int whence) -{ - off_t ret; - - ret = lseek(fd, offset, whence); - if (ret < 0) - err(1, "lseek"); - return ret; -} - -ssize_t -xread(int fd, void *buf, size_t nbytes) -{ - uint8_t *bp = buf; - ssize_t total = 0; - - while (nbytes > 0) { - ssize_t n; - - n = read(fd, &bp[total], nbytes); - if (n < 0) - err(1, "read"); - else if (n == 0) - return total; - total += n; - nbytes -= n; - } - return total; -} - -ssize_t -xwrite(int fd, const void *buf, size_t nbytes) -{ - const uint8_t *bp = buf; - ssize_t total = 0; - - while (nbytes > 0) { - ssize_t n; - - n = write(fd, &bp[total], nbytes); - if (n < 0) - err(1, "write"); - else if (n == 0) - return total; - total += n; - nbytes -= n; - } - return total; -} - -void -init_blk_hdr(struct blk_hdr *hdr, int compr_algo, int hash_algo) -{ - hdr->flags = (VER_MAJ << VER_MAJ_SHIFT) | VER_MIN; - hdr->flags |= compr_algo << COMPR_ALGO_SHIFT; - hdr->flags |= hash_algo << HASH_ALGO_SHIFT; - hdr->size = BLK_HDR_SIZE; -} - -void -init_snap_hdr(struct snap_hdr *hdr) -{ - hdr->flags = (VER_MAJ << VER_MAJ_SHIFT) | VER_MIN; - hdr->size = SNAP_HDR_SIZE; - hdr->st.min_blk_size = UINT64_MAX; -} - -void -load_blk_hdr(int fd, struct blk_hdr *hdr, int *compr_algo, int *hash_algo) -{ - uint64_t v; - - read_blk_hdr(fd, hdr); - match_ver(hdr->flags); - - v = hdr->flags >> COMPR_ALGO_SHIFT; - v &= COMPR_ALGO_MASK; - *compr_algo = v; - - if (*compr_algo < 0 || *compr_algo >= NR_COMPRS) - errx(1, "unsupported compression algorithm: %d", *compr_algo); - - v = hdr->flags >> HASH_ALGO_SHIFT; - v &= HASH_ALGO_MASK; - *hash_algo = v; - - if (*hash_algo < 0 || *hash_algo >= NR_HASHES) - errx(1, "unsupported hash algorithm: %d", *hash_algo); -} - -void -load_snap_hdr(int fd, struct snap_hdr *hdr) -{ - read_snap_hdr(fd, hdr); - match_ver(hdr->flags); -} - -struct snap * -alloc_snap(void) -{ - struct snap *snap; - - snap = calloc(1, sizeof(*snap)); - if (snap == NULL) - err(1, "%s", __func__); - return snap; -} - -void -free_snap(struct snap *snap) -{ - free(snap); -} - -struct snap * -grow_snap(struct snap *snap, uint64_t nr_blk_descs) -{ - size_t size; - - if (nr_blk_descs > SIZE_MAX / sizeof(snap->blk_desc[0])) - errx(1, "%s: overflow", __func__); - size = nr_blk_descs * sizeof(snap->blk_desc[0]); - - if (size > SIZE_MAX - sizeof(*snap)) - errx(1, "%s: overflow", __func__); - size += sizeof(*snap); - - snap = realloc(snap, size); - if (snap == NULL) - err(1, "%s", __func__); - return snap; -} - -void -append_snap(int fd, struct snap_hdr *hdr, struct snap *snap) -{ - if (snap->nr_blk_descs > UINT64_MAX / BLK_DESC_SIZE) - errx(1, "%s: overflow", __func__); - snap->size = snap->nr_blk_descs * BLK_DESC_SIZE; - - if (snap->size > UINT64_MAX - SNAPSHOT_SIZE) - errx(1, "%s: overflow", __func__); - snap->size += SNAPSHOT_SIZE; - - xlseek(fd, hdr->size, SEEK_SET); - write_snap(fd, snap); - write_snap_blk_descs(fd, snap); - - if (hdr->size > UINT64_MAX - snap->size) - errx(1, "%s: overflow", __func__); - hdr->size += snap->size; - - if (hdr->nr_snaps > UINT64_MAX - 1) - errx(1, "%s: overflow", __func__); - hdr->nr_snaps++; -} - -/* - * The snapshot hash is calculated over the - * hash of its block descriptors. - */ -void -hash_snap(struct snap *snap, uint8_t *md, int hash_algo) -{ - struct hash_ctx ctx; - uint64_t i; - - if (hash_init(&ctx, hash_algo, MD_SIZE) < 0) - errx(1, "hash_init failed"); - for (i = 0; i < snap->nr_blk_descs; i++) { - struct blk_desc *blk_desc; - - blk_desc = &snap->blk_desc[i]; - hash_update(&ctx, blk_desc->md, sizeof(blk_desc->md)); - } - hash_final(&ctx, md, MD_SIZE); -} - -/* Walk through all snapshots and call fn() on each one */ -void -walk_snap(int fd, struct snap_hdr *hdr, - int (*fn)(struct snap *, void *), void *arg) -{ - uint64_t i; - - xlseek(fd, SNAP_HDR_SIZE, SEEK_SET); - for (i = 0; i < hdr->nr_snaps; i++) { - struct snap *snap; - int ret; - - snap = alloc_snap(); - read_snap(fd, snap); - snap = grow_snap(snap, snap->nr_blk_descs); - read_snap_descs(fd, snap); - - ret = (*fn)(snap, arg); - free_snap(snap); - if (ret == WALK_STOP) - break; - } -} - -uint8_t * -alloc_buf(size_t size) -{ - void *p; - - p = calloc(1, size); - if (p == NULL) - err(1, "%s", __func__); - return p; -} - -void -free_buf(uint8_t *buf) -{ - free(buf); -} - -void -read_blk(int fd, uint8_t *buf, struct blk_desc *blk_desc) -{ - ssize_t n; - - xlseek(fd, blk_desc->offset, SEEK_SET); - n = xread(fd, buf, blk_desc->size); - if (n == 0) - errx(1, "%s: unexpected EOF", __func__); - if (n != blk_desc->size) - errx(1, "%s: short read", __func__); -} - -void -append_blk(int fd, struct blk_hdr *hdr, uint8_t *buf, struct blk_desc *blk_desc) -{ - xlseek(fd, hdr->size, SEEK_SET); - xwrite(fd, buf, blk_desc->size); - - if (hdr->size > UINT64_MAX - blk_desc->size) - errx(1, "%s: overflow", __func__); - hdr->size += blk_desc->size; -} - -void -hash_blk(uint8_t *buf, size_t size, uint8_t *md, int hash_algo) -{ - struct hash_ctx ctx; - - if (hash_init(&ctx, hash_algo, MD_SIZE) < 0) - errx(1, "hash_init failed"); - hash_update(&ctx, buf, size); - hash_final(&ctx, md, MD_SIZE); -}