path: root/lib/slab.c

// 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;
}