1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
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);
|
