From d4350788eea01f04b464d382d74ee0f391a78398 Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Mon, 25 Nov 2019 13:03:37 +0000 Subject: Initial libdcache implementation --- src/caches/dcache_add.c | 110 ++++++++++++++++++++++++++++++++++++++++++++ src/caches/dcache_free.c | 23 +++++++++ src/caches/dcache_init.c | 55 ++++++++++++++++++++++ src/caches/dcache_load.c | 81 ++++++++++++++++++++++++++++++++ src/caches/dcache_save.c | 73 +++++++++++++++++++++++++++++ src/caches/dcache_search.c | 17 +++++++ src/caches/deps-lib/dcache | 6 +++ src/include/s6-dns/dcache.h | 53 +++++++++++++++++++++ 8 files changed, 418 insertions(+) create mode 100644 src/caches/dcache_add.c create mode 100644 src/caches/dcache_free.c create mode 100644 src/caches/dcache_init.c create mode 100644 src/caches/dcache_load.c create mode 100644 src/caches/dcache_save.c create mode 100644 src/caches/dcache_search.c create mode 100644 src/caches/deps-lib/dcache create mode 100644 src/include/s6-dns/dcache.h (limited to 'src') diff --git a/src/caches/dcache_add.c b/src/caches/dcache_add.c new file mode 100644 index 0000000..a534f7a --- /dev/null +++ b/src/caches/dcache_add.c @@ -0,0 +1,110 @@ +/* ISC license. */ + +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include + +#define DNODE(z, i) GENSETDYN_P(dcache_node_t, &(z)->storage, i) +#define DCACHE_NODE_OVERHEAD (32 + sizeof(dcache_node_t) + 3 * sizeof(avlnode)) + +static void uniquify (avltree const *tree, tain_t *stamp) +{ + static tain_t const nano = { .sec = TAI_ZERO, .nano = 1 } ; + uint32_t dummy ; + while (avltree_search(tree, stamp, &dummy)) + tain_add(stamp, stamp, &nano) ; +} + +static void dcache_delete (dcache_t *z, uint32_t i) +{ + dcache_node_t *y = DNODE(z, i) ; + avltree_delete(&z->by_expire, &y->expire) ; + avltree_delete(&z->by_entry, &y->entry) ; + avltree_delete(&z->by_key, &y->key) ; + alloc_free(y->key.s) ; + z->size -= DCACHE_NODE_OVERHEAD + y->key.len + y->datalen ; + gensetdyn_delete(&z->storage, i) ; +} + +static inline void dcache_gc_by_entry (dcache_t *z, uint64_t max) +{ + while (z->size > max) + { + uint32_t oldest ; + if (!avltree_min(&z->by_entry, &oldest)) break ; + dcache_delete(z, oldest) ; + } +} + +static inline void dcache_gc_by_expire (dcache_t *z, tain_t const *stamp) +{ + for (;;) + { + uint32_t i ; + if (!avltree_min(&z->by_expire, &i)) break ; + if (tain_less(stamp, &DNODE(z, i)->expire)) break ; + dcache_delete(z, i) ; + } +} + +static inline int dcache_add_node (dcache_t *z, dcache_node_t const *node) +{ + uint32_t i ; + dcache_node_t *y ; + if (!gensetdyn_new(&z->storage, &i)) return 0 ; + y = DNODE(z, i) ; *y = *node ; + uniquify(&z->by_entry, &y->entry) ; + uniquify(&z->by_expire, &y->expire) ; + if (!avltree_insert(&z->by_key, i)) goto err1 ; + if (!avltree_insert(&z->by_entry, i)) goto err2 ; + if (!avltree_insert(&z->by_expire, i)) goto err3 ; + return 1 ; + + err3: + avltree_delete(&z->by_entry, &y->entry) ; + err2: + avltree_delete(&z->by_key, &y->key) ; + err1: + gensetdyn_delete(&z->storage, i) ; + return 0 ; +} + +static inline int dcache_add_unbounded (dcache_t *z, char const *key, uint16_t keylen, char const *data, uint16_t datalen, tain_t const *expire, tain_t const *stamp) +{ + uint32_t len = keylen + datalen ; + dcache_node_t y = { .key = { .s = alloc(len) } } ; + if (!y.key.s) return 0 ; + memcpy(y.key.s, key, keylen) ; + memcpy(y.key.s + keylen, data, datalen) ; + y.key.len = keylen ; + y.datalen = datalen ; + y.entry = *stamp ; + y.expire = *expire ; + if (!dcache_add_node(z, &y)) + { + alloc_free(y.key.s) ; + return 0 ; + } + z->size += DCACHE_NODE_OVERHEAD + len ; + z->motion += DCACHE_NODE_OVERHEAD + len ; + return 1 ; +} + + +int dcache_add (dcache_t *z, uint64_t max, char const *key, uint16_t keylen, char const *data, uint16_t datalen, tain_t const *expire, tain_t const *stamp) +{ + uint64_t size = DCACHE_NODE_OVERHEAD + keylen + datalen ; + if (size > max) return (errno = EINVAL, 0) ; + if (z->size > max - size) dcache_gc_by_expire(z, stamp) ; + if (z->size > max - size) dcache_gc_by_entry(z, max - size) ; + return dcache_add_unbounded(z, key, keylen, data, datalen, expire, stamp) ; +} diff --git a/src/caches/dcache_free.c b/src/caches/dcache_free.c new file mode 100644 index 0000000..7937332 --- /dev/null +++ b/src/caches/dcache_free.c @@ -0,0 +1,23 @@ +/* ISC license. */ + +#include +#include +#include + +#include + +static dcache_t const dcache_zero = DCACHE_ZERO ; + +static void dcache_node_free (void *p) +{ + alloc_free(((dcache_node_t *)p)->key.s) ; +} + +void dcache_free (dcache_t *z) +{ + avltree_free(&z->by_expire) ; + avltree_free(&z->by_entry) ; + avltree_free(&z->by_key) ; + gensetdyn_deepfree(&z->storage, &dcache_node_free) ; + *z = dcache_zero ; +} diff --git a/src/caches/dcache_init.c b/src/caches/dcache_init.c new file mode 100644 index 0000000..93a069c --- /dev/null +++ b/src/caches/dcache_init.c @@ -0,0 +1,55 @@ +/* ISC license. */ + +#include +#include + +#include +#include +#include +#include + +#include + +static int key_cmp (void const *a, void const *b, void *x) +{ + dcache_key_t const *ka = a ; + dcache_key_t const *kb = b ; + if (ka->len < kb->len) return -1 ; + if (kb->len < ka->len) return 1 ; + (void)x ; + return memcmp(ka->s, kb->s, ka->len) ; +} + +static int tain_cmp (void const *a, void const *b, void *x) +{ + tain_t const *ta = a ; + tain_t const *tb = b ; + (void)x ; + return tain_less(ta, tb) ? -1 : tain_less(tb, ta) ; +} + +static void *key_dtok (uint32_t d, void *x) +{ + return &GENSETDYN_P(dcache_node_t, (gensetdyn *)x, d)->key ; +} + +static void *entry_dtok (uint32_t d, void *x) +{ + return &GENSETDYN_P(dcache_node_t, (gensetdyn *)x, d)->entry ; +} + +static void *expire_dtok (uint32_t d, void *x) +{ + return &GENSETDYN_P(dcache_node_t, (gensetdyn *)x, d)->expire ; +} + + +void dcache_init (dcache_t *z, uint64_t max) +{ + gensetdyn_init(&z->storage, sizeof(dcache_node_t), max >> 9, 3, 8) ; + avltree_init(&z->by_key, max >> 9, 3, 8, &key_dtok, &key_cmp, &z->storage) ; + avltree_init(&z->by_entry, max >> 9, 3, 8, &entry_dtok, &tain_cmp, &z->storage) ; + avltree_init(&z->by_expire, max >> 9, 3, 8, &expire_dtok, &tain_cmp, &z->storage) ; + z->size = 0 ; + z->motion = 0 ; +} diff --git a/src/caches/dcache_load.c b/src/caches/dcache_load.c new file mode 100644 index 0000000..8f9383f --- /dev/null +++ b/src/caches/dcache_load.c @@ -0,0 +1,81 @@ +/* ISC license. */ + +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include + +static inline int dcache_load_node (dcache_t *z, uint64_t max, buffer *b) +{ + tain_t entry = { .nano = 0 } ; + tain_t expire = { .nano = 0 } ; + uint16_t keylen ; + uint16_t datalen ; + char pack[TAI_PACK * 2 + 4] ; + ssize_t r = buffer_get(b, pack, TAI_PACK * 2 + 4) ; + if (!r) return 0 ; + if (r < TAI_PACK * 2 + 4) return -1 ; + tai_unpack(pack, tain_secp(&entry)) ; + tai_unpack(pack + TAI_PACK, tain_secp(&expire)) ; + uint16_unpack_big(pack + TAI_PACK * 2, &keylen) ; + uint16_unpack_big(pack + TAI_PACK * 2 + 2, &datalen) ; + { + uint32_t len = (uint32_t)keylen + (uint32_t)datalen ; + char blob[len+1] ; /* 128 kB max, it's ok */ + r = buffer_get(b, blob, len+1) ; + if (!r) return (errno = EPIPE, -1) ; + if (r < len) return -1 ; + if (blob[len]) return (errno = EPROTO, -1) ; + if (!dcache_add(z, max, blob, keylen, blob + keylen, datalen, &expire, &entry)) return -1 ; + } + return 1 ; +} + +static inline int dcache_load_from_buffer (dcache_t *z, uint64_t max, buffer *b) +{ + { + char banner[sizeof(DCACHE_MAGIC) - 1] ; + char pack[8] ; + if (buffer_get(b, banner, sizeof(DCACHE_MAGIC) - 1) < sizeof(DCACHE_MAGIC) - 1) + return 0 ; + if (memcmp(banner, DCACHE_MAGIC, sizeof(DCACHE_MAGIC) - 1)) return 0 ; + if (buffer_get(b, pack, 8) < 8) return 0 ; + uint64_unpack_big(pack, &z->size) ; + if (buffer_get(b, pack, 8) < 8) return 0 ; + uint64_unpack_big(pack, &z->motion) ; + } + for (;;) + { + int r = dcache_load_node(z, max, b) ; + if (r < 0) return 0 ; + if (!r) break ; + } + return 1 ; +} + +#define N 8192 + +int dcache_load (dcache_t *z, uint64_t max, char const *file) +{ + char buf[N] ; + buffer b ; + int fd = open_readb(file) ; + if (fd == -1) return 0 ; + buffer_init(&b, &buffer_read, fd, buf, N) ; + if (!dcache_load_from_buffer(z, max, &b)) goto err ; + fd_close(fd) ; + return 1 ; + + err: + dcache_free(z) ; + fd_close(fd) ; + return 0 ; +} diff --git a/src/caches/dcache_save.c b/src/caches/dcache_save.c new file mode 100644 index 0000000..1ef35f0 --- /dev/null +++ b/src/caches/dcache_save.c @@ -0,0 +1,73 @@ +/* ISC license. */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +static int write_node_iter (char *data, void *aux) +{ + dcache_node_t *y = (dcache_node_t *)data ; + buffer *b = aux ; + char pack[TAI_PACK * 2 + 4] ; + tai_pack(pack, tain_secp(&y->entry)) ; + tai_pack(pack + TAI_PACK, tain_secp(&y->expire)) ; + uint16_pack(pack + TAI_PACK * 2, y->key.len) ; + uint16_pack(pack + TAI_PACK * 2 + 2, y->datalen) ; + if (buffer_put(b, pack, TAI_PACK * 2 + 4) == -1) return 0 ; + if (buffer_put(b, y->key.s, y->key.len + y->datalen) == -1) return 0 ; + if (buffer_put(b, "", 1) == -1) return 0 ; + return 1 ; +} + +static inline int dcache_save_to_buffer (dcache_t const *z, buffer *b) +{ + char pack[16] ; + if (buffer_puts(b, DCACHE_MAGIC) == -1) return 0 ; + uint64_pack_big(pack, z->size) ; + uint64_pack_big(pack + 8, z->motion) ; + if (buffer_put(b, pack, 16) < 16) return 0 ; + + /* XXX: can gensetdyn_iter blow up the stack if z->storage is huge? */ + if (gensetdyn_iter_nocancel((gensetdyn *)&z->storage, gensetdyn_n(&z->storage), &write_node_iter, b) < gensetdyn_n(&z->storage)) return 0 ; + + return buffer_flush(b) ; +} + +#define N 8192 + +int dcache_save (dcache_t const *z, char const *file) +{ + stralloc sa = STRALLOC_ZERO ; + int fd ; + buffer b ; + char buf[N] ; + if (!stralloc_cats(&sa, file)) return 0 ; + if (!sauniquename(&sa) || !stralloc_0(&sa)) goto err0 ; + fd = open_excl(sa.s) ; + if (fd == -1) goto err0 ; + buffer_init(&b, &buffer_write, fd, buf, N) ; + if (!dcache_save_to_buffer(z, &b)) goto err2 ; + fd_close(fd) ; + if (rename(sa.s, file) == -1) goto err1 ; + stralloc_free(&sa) ; + return 1 ; + + err2: + fd_close(fd) ; + err1: + unlink_void(sa.s) ; + err0: + stralloc_free(&sa) ; + return 0 ; +} diff --git a/src/caches/dcache_search.c b/src/caches/dcache_search.c new file mode 100644 index 0000000..0c1894a --- /dev/null +++ b/src/caches/dcache_search.c @@ -0,0 +1,17 @@ +/* ISC license. */ + +#include + +#include +#include + +#include + +#define DNODE(z, i) GENSETDYN_P(dcache_node_t, &(z)->storage, i) + +dcache_node_t *dcache_search (dcache_t *z, char const *key, uint16_t keylen) +{ + uint32_t i ; + dcache_key_t k = { .s = (char *)key, .len = keylen } ; + return avltree_search(&z->by_key, &k, &i) ? DNODE(z, i) : 0 ; +} diff --git a/src/caches/deps-lib/dcache b/src/caches/deps-lib/dcache new file mode 100644 index 0000000..d842e17 --- /dev/null +++ b/src/caches/deps-lib/dcache @@ -0,0 +1,6 @@ +dcache_add.o +dcache_free.o +dcache_init.o +dcache_load.o +dcache_save.o +dcache_search.o diff --git a/src/include/s6-dns/dcache.h b/src/include/s6-dns/dcache.h new file mode 100644 index 0000000..59e78c0 --- /dev/null +++ b/src/include/s6-dns/dcache.h @@ -0,0 +1,53 @@ +/* ISC license. */ + +#ifndef S6DNS_DCACHE_H +#define S6DNS_DCACHE_H + +#include + +#include +#include +#include +#include + +#define DCACHE_MAGIC "--DCACHE--\n" + +typedef struct dcache_key_s dcache_key_t, *dcache_key_t_ref ; +struct dcache_key_s +{ + char *s ; + uint16_t len ; +} ; + +typedef struct dcache_node_s dcache_node_t, *dcache_node_t_ref ; +struct dcache_node_s +{ + dcache_key_t key ; + uint16_t datalen ; + tain_t entry ; + tain_t expire ; +} ; + +typedef struct dcache_s dcache_t, *dcache_t_ref ; +struct dcache_s +{ + gensetdyn storage ; /* dcache_node_t */ + avltree by_key ; + avltree by_entry ; + avltree by_expire ; + uint64_t size ; + uint64_t motion ; +} ; +#define DCACHE_ZERO { .storage = GENSETDYN_ZERO, .by_key = AVLTREE_ZERO, .by_entry = AVLTREE_ZERO, .by_expire = AVLTREE_ZERO, .size = 0, .motion = 0 } + +extern void dcache_init (dcache_t *, uint64_t) ; +extern dcache_node_t *dcache_search (dcache_t *, char const *, uint16_t) ; +extern int dcache_add (dcache_t *, uint64_t, char const *, uint16_t, char const *, uint16_t, tain_t const *, tain_t const *) ; +#define dcache_add_g(d, max, key, keylen, data, datalen, expire) dcache_add(d, max, key, keylen, data, datalen, (expire), &STAMP) +extern void dcache_free (dcache_t *) ; + +extern int dcache_save (dcache_t const *, char const *) ; +extern int dcache_load (dcache_t *, uint64_t, char const *) ; + + +#endif -- cgit v1.2.3