diff options
Diffstat (limited to 'lib/slab.c')
| -rw-r--r-- | lib/slab.c | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/lib/slab.c b/lib/slab.c new file mode 100644 index 0000000..2d2d8e1 --- /dev/null +++ b/lib/slab.c @@ -0,0 +1,199 @@ +// SPDX-License-Identifier: LGPL-3.0-or-later + +#include "impl.h" +#include <string.h> +#include <stdlib.h> + +static size_t hkvs_slab_size_to_count(size_t elt_size, size_t size) { + size_t block_size = (elt_size + 1) * HKVS_SLAB_BLOCK; + + size_t blocks = size / block_size; + size %= block_size; + size_t rest = 0; + if(size > HKVS_SLAB_BLOCK) { + rest = (size - HKVS_SLAB_BLOCK) / elt_size; + } + + return blocks * HKVS_SLAB_BLOCK + rest; +} + +static size_t hkvs_slab_count_to_size(size_t elt_size, size_t count) { + size_t size; + if(__builtin_mul_overflow(count, elt_size + 1, &size)) return SIZE_MAX; + if(__builtin_add_overflow(size, (-count) % HKVS_SLAB_BLOCK, &size)) return SIZE_MAX; + return size; +} + +int hkvs_slab_init(hkvs_slab *s, hkvs_io *io, char *param, size_t elt_size) { + s->param = param; + s->elt_size = elt_size; + + uint64_t fi = hkvs_read_u64(param + HKVS_PARAM_SLAB_FI); + if(fi == 0) { + s->addr = NULL; + s->map_size = 0; + return 0; + } + + int r = io->open(io, fi, &s->addr, &s->map_size); + if(r < 0) return r; + + uint64_t alloc_count = hkvs_read_u64(param + HKVS_PARAM_SLAB_ALLOC); + if(alloc_count > hkvs_slab_size_to_count(elt_size, s->map_size)) { + io->close(io, fi, s->addr, s->map_size); + return -EBADMSG; + } + + return 0; +} + +int hkvs_slab_alloc(hkvs *c, hkvs_slab *s, size_t *pi) { + size_t alloc_count = hkvs_slab_size(s); + + uint64_t at_64 = hkvs_read_u64(s->param + HKVS_PARAM_SLAB_FREE); + if(at_64 < alloc_count) { + size_t at = (size_t)at_64; + + char *p = hkvs_slab_at(s, at); + + for(size_t i = 1; i < HKVS_SLAB_FREEPTRS; i++) { + uint64_t v = hkvs_read_u64(p + i * 8); + if(v <= at) return -EBADMSG; + if(v < alloc_count) { + size_t id = (size_t)v; + hkvs_write_u64(p + i * 8, UINT64_MAX); + *pi = id; + return 0; + } + } + + at_64 = hkvs_read_u64(p); + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_FREE, at_64); + + *pi = at; + return 0; + } + + if(at_64 != UINT64_MAX) { + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_FREE, UINT64_MAX); + } + + size_t cap_count = hkvs_slab_size_to_count(s->elt_size, s->map_size); + hkvs_assume(alloc_count <= cap_count); + if(alloc_count == cap_count) { + size_t grow_count = cap_count + (cap_count >> 3) + 1; + size_t grow_size; + while(true) { + grow_size = hkvs_slab_count_to_size(s->elt_size, grow_count); + if(grow_size != 0) break; + size_t dec = (grow_count - cap_count) / 2; + if(dec == 0) return -EFBIG; + grow_count -= dec; + } + + hkvs_io *io = c->io; + uint64_t fi = hkvs_read_u64(s->param + HKVS_PARAM_SLAB_FI); + if(fi == 0) { + int r = io->create(io, &fi, &s->addr, grow_size); + if(r < 0) return r; + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_FI, fi); + } else { + int r = io->resize(io, fi, &s->addr, s->map_size, grow_size); + if(r < 0) return r; + } + s->map_size = grow_size; + } + + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_ALLOC, alloc_count + 1); + *pi = alloc_count; + return 0; +} + +void hkvs_slab_discard(hkvs_slab *s, size_t id) { + size_t alloc_count = hkvs_slab_size(s); + hkvs_assume(id < alloc_count); + if(id == alloc_count - 1) { + do { + alloc_count--; + } while(alloc_count > 0 && hkvs_slab_mark(s, alloc_count - 1) == 0); + + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_ALLOC, alloc_count); + return; + } + + hkvs_slab_set_mark(s, id, 0); + + uint64_t free_64 = hkvs_read_u64(s->param + HKVS_PARAM_SLAB_FREE); + if(id < free_64) { + hkvs_write_u64(s->param + HKVS_PARAM_SLAB_FREE, id); + char *p = hkvs_slab_at(s, id); + hkvs_write_u64(p, free_64); + for(size_t i = 1; i < HKVS_SLAB_FREEPTRS; i++) { + hkvs_write_u64(p + i * 8, UINT64_MAX); + } + return; + } + + char *p = hkvs_slab_at(s, (size_t)free_64); + uint64_t v = hkvs_read_u64(p + 8); + + if(v >= alloc_count) { + size_t i = 2; + while(true) { + v = hkvs_read_u64(p + i * 8); + if(v < alloc_count) break; + i++; + if(i == HKVS_SLAB_FREEPTRS) { + hkvs_write_u64(p + 8, id); + return; + } + } + while(v < id) { + hkvs_write_u64(p + (i - 1) * 8, v); + i++; + if(i == HKVS_SLAB_FREEPTRS) break; + v = hkvs_read_u64(p + i * 8); + } + hkvs_write_u64(p + (i - 1) * 8, id); + return; + } + + if(hkvs_read_u64(p + (HKVS_SLAB_FREEPTRS - 1) * 8) >= alloc_count) { + size_t i = 1; + while(v < id) { + i++; + v = hkvs_read_u64(p + i * 8); + } + uint64_t v2 = id; + while(true) { + hkvs_write_u64(p + i * 8, v2); + if(v >= alloc_count) break; + v2 = v; + i++; + v = hkvs_read_u64(p + i * 8); + } + return; + } + + if(v < id) { + uint64_t v2 = id; + id = (size_t)v; + size_t i = 2; + do { + v = hkvs_read_u64(p + i * 8); + if(v >= v2) break; + hkvs_write_u64(p + (i - 1) * 8, v); + i++; + } while(i < HKVS_SLAB_FREEPTRS); + hkvs_write_u64(p + (i - 1) * 8, v2); + } + + char *p2 = hkvs_slab_at(s, id); + memcpy(p2, p, HKVS_SLAB_FREEPTRS * 8); + + hkvs_write_u64(p, id); + for(size_t i = 1; i < HKVS_SLAB_FREEPTRS; i++) { + hkvs_write_u64(p + i * 8, UINT64_MAX); + } + return; +} |