Initial libdcache implementation

8 files changed, 418 insertions, 0 deletions

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 <stdint.h>
+#include <string.h>
+#include <errno.h>
+
+#include <skalibs/uint64.h>
+#include <skalibs/alloc.h>
+#include <skalibs/tai.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltree.h>
+
+#include <s6-dns/dcache.h>
+
+#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 <skalibs/alloc.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avltree.h>
+
+#include <s6-dns/dcache.h>
+
+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 <stdint.h>
+#include <string.h>
+
+#include <skalibs/uint64.h>
+#include <skalibs/tai.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avltree.h>
+
+#include <s6-dns/dcache.h>
+
+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 <stdint.h>
+#include <string.h>
+#include <errno.h>
+
+#include <skalibs/posixishard.h>
+#include <skalibs/uint16.h>
+#include <skalibs/uint64.h>
+#include <skalibs/buffer.h>
+#include <skalibs/tai.h>
+#include <skalibs/djbunix.h>
+
+#include <s6-dns/dcache.h>
+
+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 <stdint.h>
+#include <stdio.h>
+
+#include <skalibs/posixplz.h>
+#include <skalibs/uint16.h>
+#include <skalibs/uint64.h>
+#include <skalibs/buffer.h>
+#include <skalibs/stralloc.h>
+#include <skalibs/tai.h>
+#include <skalibs/djbunix.h>
+#include <skalibs/skamisc.h>
+#include <skalibs/gensetdyn.h>
+
+#include <s6-dns/dcache.h>
+
+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 <stdint.h>
+
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avltree.h>
+
+#include <s6-dns/dcache.h>
+
+#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 <stdint.h>
+
+#include <skalibs/uint64.h>
+#include <skalibs/tai.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avltree.h>
+
+#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