1 files changed, 209 insertions, 0 deletions
diff --git a/lib/impl.h b/lib/impl.h
new file mode 100644
index 0000000..47a05ca
--- /dev/null
+++ b/lib/impl.h
@@ -0,0 +1,209 @@
+// SPDX-License-Identifier: LGPL-3.0-or-later
+
+#pragma once
+#include "internal.h"
+
+#ifdef FUZZING
+#define HKVS_SLAB_BLOCK ((size_t)16)
+#else
+#define HKVS_SLAB_BLOCK ((size_t)4096)
+#endif
+
+#define HKVS_REWRITE_THRESHOLD ((size_t)8192)
+
+#define HKVS_SLAB_FREEPTRS ((size_t)8)
+
+#define HKVS_N_SLABS ((uint8_t)40)
+
+#define HKVS_MARK_MAX_SMALL ((uint8_t)249)
+#define HKVS_MARK_EXT ((uint8_t)255)
+#define HKVS_MARK_SLAB ((uint8_t)254)
+
+#define HKVS_IX_ENTRY ((size_t)16)
+#define HKVS_IX_KEY_SIZE ((size_t)16)
+#define HKVS_IX_MAX_DISP ((size_t)6)
+#define HKVS_IX_SIZE(bits) ((uint64_t)HKVS_IX_ENTRY << (bits))
+
+#define HKVS_PSIZE_HEADER ((size_t)64)
+#define HKVS_PARAM_HEADER_MAGIC ((size_t)0)
+#define HKVS_PARAM_HEADER_VERSION ((size_t)8)
+/*
+ * header {
+ *     magic: u64,
+ *     version: u64,
+ *     app_id: u64,
+ *     app_ver: u64,
+ *     pad: [u64; 4],
+ * }
+ */
+
+#define HKVS_POFF_SLAB HKVS_PSIZE_HEADER
+#define HKVS_PSIZE_SLAB ((size_t)32)
+#define HKVS_PARAM_SLAB_FI ((size_t)0)
+#define HKVS_PARAM_SLAB_ALLOC ((size_t)8)
+#define HKVS_PARAM_SLAB_FREE ((size_t)16)
+/*
+ * slab {
+ *     fi: u64,
+ *     alloc_count: u64,
+ *     free: u64,
+ *     pad: u64,
+ * }
+ */
+
+#define HKVS_POFF_TABLE ((size_t)(HKVS_POFF_SLAB + HKVS_N_SLABS * HKVS_PSIZE_SLAB))
+#define HKVS_PSIZE_TABLE ((size_t)64)
+#define HKVS_PARAM_TABLE_ELTSZ ((size_t)32)
+#define HKVS_PARAM_TABLE_KEYSZ ((size_t)34)
+#define HKVS_PARAM_TABLE_IXBIT ((size_t)35)
+#define HKVS_PARAM_TABLE_ID ((size_t)36)
+#define HKVS_PARAM_TABLE_IXFI ((size_t)40)
+#define HKVS_PARAM_TABLE_IXKEY ((size_t)48)
+/* table {
+ *     slab;
+ *     elt_size: u16,
+ *     key_size: u8,
+ *     ix_bits: u8,
+ *     id: u32,
+ *     ix_fi: u64,
+ *     ix_key: [u64; 2],
+ * }
+ */
+
+typedef struct hkvs_slab hkvs_slab;
+struct hkvs_slab {
+	char *param;
+	char *addr;
+	size_t map_size;
+	size_t elt_size;
+};
+
+typedef struct hkvs_table hkvs_table;
+struct hkvs_table {
+	hkvs_slab slab;
+	char *ix;
+	size_t ix_size;
+};
+
+typedef struct hkvs_extfile hkvs_extfile;
+struct hkvs_extfile {
+	uint64_t fi;
+	char *addr;
+	size_t size;
+	uint32_t gen;
+};
+
+struct hkvs {
+	hkvs_io *io;
+
+	char *root_param;
+	size_t root_param_size;
+
+	hkvs_table **tables;
+	size_t n_tables;
+	size_t alloc_tables;
+
+	hkvs_extfile *extfiles;
+	size_t n_extfiles;
+	size_t alloc_extfiles;
+	uint32_t extfile_gen;
+
+	hkvs_slab slabs[HKVS_N_SLABS];
+};
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_extfile_create(hkvs *c, uint64_t *pfi, char **paddr, size_t size, bool pin);
+
+HKVS_INTERNAL HKVS_MUSTCHECK bool hkvs_extfile_find(hkvs *c, uint64_t fi, size_t *pslot);
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_extfile_open(hkvs *c, uint64_t fi, size_t *pslot, size_t want_size);
+
+HKVS_INTERNAL void hkvs_extfile_close(hkvs *c, size_t slot);
+
+HKVS_INLINE void hkvs_extfile_pin(hkvs *c, hkvs_extfile *f) {
+	f->gen = c->extfile_gen;
+}
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_resize_param(hkvs *c);
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_slab_init(hkvs_slab *s, hkvs_io *io, char *param, size_t elt_size);
+
+HKVS_INLINE void hkvs_slab_destroy(hkvs_slab *s, hkvs_io *io) {
+	uint64_t fi = hkvs_read_u64(s->param);
+	if(fi) {
+		io->close(io, fi, s->addr, s->map_size);
+	}
+}
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_slab_alloc(hkvs *c, hkvs_slab *s, size_t *pi);
+
+HKVS_INTERNAL void hkvs_slab_discard(hkvs_slab *s, size_t id);
+
+HKVS_INLINE HKVS_PURE size_t hkvs_slab_size(hkvs_slab *s) {
+	uint64_t r = hkvs_read_u64(s->param + HKVS_PARAM_SLAB_ALLOC);
+	hkvs_assume(r <= SIZE_MAX / 2);
+	return (size_t)r;
+}
+
+HKVS_INLINE char *hkvs_slab_mark_at(hkvs_slab *s, size_t i) {
+	hkvs_assume(i <= SIZE_MAX / 2);
+	hkvs_assume(i < hkvs_slab_size(s));
+	size_t j = i & ~(HKVS_SLAB_BLOCK - 1);
+	return s->addr + j * s->elt_size + i;
+}
+
+HKVS_INLINE char *hkvs_slab_at(hkvs_slab *s, size_t i) {
+	hkvs_assume(i <= SIZE_MAX / 2);
+	hkvs_assume(i < hkvs_slab_size(s));
+	size_t j = i & ~(HKVS_SLAB_BLOCK - 1);
+	return s->addr + i * s->elt_size + j + HKVS_SLAB_BLOCK;
+}
+
+HKVS_INLINE uint8_t hkvs_slab_mark(hkvs_slab *s, size_t i) {
+	return hkvs_read_u8(hkvs_slab_mark_at(s, i));
+}
+
+HKVS_INLINE void hkvs_slab_set_mark(hkvs_slab *s, size_t i, uint8_t v) {
+	hkvs_write_u8(hkvs_slab_mark_at(s, i), v);
+}
+
+HKVS_INTERNAL HKVS_CONST uint8_t hkvs_slab_for_size(size_t data_size);
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_table_new(hkvs_table **t, hkvs_io *io, char *param);
+
+HKVS_INLINE HKVS_PURE uint32_t hkvs_table__id(hkvs_table *t) {
+	return hkvs_read_u32(t->slab.param + HKVS_PARAM_TABLE_ID);
+}
+
+HKVS_INLINE HKVS_PURE uint8_t hkvs_table__key_size(hkvs_table *t) {
+	return hkvs_read_u8(t->slab.param + HKVS_PARAM_TABLE_KEYSZ);
+}
+
+HKVS_INLINE uint8_t hkvs_table__inl_size(hkvs_table *t) {
+	size_t r = t->slab.elt_size;
+	size_t key_size = hkvs_table__key_size(t);
+	hkvs_assume(key_size <= r);
+	r -= key_size;
+	if(r > 248) r = 248;
+	return (uint8_t)r;
+}
+
+HKVS_INLINE HKVS_PURE uint8_t hkvs_table__ix_bits(hkvs_table *t) {
+	return hkvs_read_u8(t->slab.param + HKVS_PARAM_TABLE_IXBIT);
+}
+
+HKVS_INLINE HKVS_PURE const char *hkvs_table__ix_key(hkvs_table *t) {
+	return t->slab.param + HKVS_PARAM_TABLE_IXKEY;
+}
+
+HKVS_INTERNAL int hkvs_record__value(hkvs *c, hkvs_table *t, size_t id, char *key, size_t key_size, int notfound, char **pvalue, size_t *psize);
+
+HKVS_INLINE void hkvs_table_free(hkvs_table *t, hkvs_io *io) {
+	hkvs_slab_destroy(&t->slab, io);
+	uint64_t ix_fi = hkvs_read_u64(t->slab.param + HKVS_PARAM_TABLE_IXFI);
+	io->close(io, ix_fi, t->ix, t->ix_size);
+	free(t);
+}
+
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_ix_build(hkvs_table *t, hkvs_io *io);
+HKVS_INTERNAL HKVS_MUSTCHECK int hkvs_ix_add(hkvs *c, hkvs_table *t, size_t id);
+HKVS_INTERNAL void hkvs_ix_remove(hkvs_table *t, size_t id);