Rewrite dedup from scratch - dedup - deduplicating backup program
HTML git clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/
DIR Log
DIR Files
DIR Refs
DIR Tags
DIR README
DIR LICENSE
---
DIR commit 54776ab6b2b26aea19f77b7876e80cff4b602913
DIR parent 3d79ba2671de814d94474dce3765be64a982cc5a
HTML 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:
M Makefile | 115 ++++++-------------------------
M README | 25 ++++++++-----------------
M TODO | 1 -
A bcompress.c | 260 +++++++++++++++++++++++++++++++
D blake2bp-ref.c | 359 -------------------------------
D blake2s-ref.c | 367 ------------------------------
D blake2sp-ref.c | 359 -------------------------------
A block.c | 114 +++++++++++++++++++++++++++++++
A block.h | 34 +++++++++++++++++++++++++++++++
A bstorage.c | 564 +++++++++++++++++++++++++++++++
M chunker.c | 174 +++++++++++++++++--------------
A chunker.h | 8 ++++++++
D compress-lz4.c | 54 -------------------------------
D compress-none.c | 41 -------------------------------
D compress-snappy.c | 54 -------------------------------
D compress.c | 112 -------------------------------
M config.h | 11 +++++++----
M config.mk | 5 +++--
D dedup.h | 233 -------------------------------
D dup-check.1 | 25 -------------------------
D dup-check.c | 157 -------------------------------
D dup-info.1 | 37 -------------------------------
D dup-info.c | 141 -------------------------------
M dup-init.1 | 6 +++---
M dup-init.c | 83 ++++++-------------------------
D dup-list.1 | 25 -------------------------
D dup-list.c | 113 -------------------------------
D dup-migrate | 28 ----------------------------
D dup-migrate.1 | 26 --------------------------
M dup-pack.1 | 20 ++++++++++----------
M dup-pack.c | 228 +++++++------------------------
M dup-unpack.1 | 17 ++++++++---------
M dup-unpack.c | 170 +++++++++++++------------------
D hash-blake2b.c | 26 --------------------------
D hash-blake2bp.c | 26 --------------------------
D hash-blake2s.c | 26 --------------------------
D hash-blake2sp.c | 26 --------------------------
D hash.c | 94 -------------------------------
D icache.c | 114 -------------------------------
A queue.h | 534 +++++++++++++++++++++++++++++++
A snap.c | 249 +++++++++++++++++++++++++++++++
A snap.h | 8 ++++++++
D types.c | 192 -------------------------------
D utils.c | 288 -------------------------------
44 files changed, 2063 insertions(+), 3486 deletions(-)
---
DIR 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)
DIR 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
=======
DIR 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
DIR 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;
+}
DIR 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
DIR 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
DIR 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
DIR 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;
+}
DIR 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);
DIR 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;
+}
DIR 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;
}
DIR 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);
DIR 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;
-}
DIR 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;
-}
DIR 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;
-}
DIR 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]);
-}
DIR 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)
DIR 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
DIR 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);
DIR 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 .
DIR 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;
-}
DIR 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 .
DIR 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;
-}
DIR 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 ,
DIR 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;
}
DIR 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 .
DIR 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;
-}
DIR 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
DIR 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 .
DIR 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 ,
DIR 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;
}
DIR 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
DIR 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;
}
DIR 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);
-}
DIR 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);
-}
DIR 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);
-}
DIR 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);
-}
DIR 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]);
-}
DIR 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;
-}
-
DIR 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_ */
DIR 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;
+}
DIR 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);
DIR 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]);
-}
DIR 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);
-}