1 /* TDB tools to create various canned database layouts. */
9 struct tdb_layout
*new_tdb_layout(void)
11 struct tdb_layout
*layout
= malloc(sizeof(*layout
));
12 layout
->num_elems
= 0;
17 static void add(struct tdb_layout
*layout
, union tdb_layout_elem elem
)
19 layout
->elem
= realloc(layout
->elem
,
20 sizeof(layout
->elem
[0])
21 * (layout
->num_elems
+1));
22 layout
->elem
[layout
->num_elems
++] = elem
;
25 void tdb_layout_add_freetable(struct tdb_layout
*layout
)
27 union tdb_layout_elem elem
;
28 elem
.base
.type
= FREETABLE
;
32 void tdb_layout_add_free(struct tdb_layout
*layout
, tdb_len_t len
,
35 union tdb_layout_elem elem
;
36 elem
.base
.type
= FREE
;
38 elem
.free
.ftable_num
= ftable
;
42 void tdb_layout_add_capability(struct tdb_layout
*layout
,
49 union tdb_layout_elem elem
;
50 elem
.base
.type
= CAPABILITY
;
51 elem
.capability
.type
= type
;
53 elem
.capability
.type
|= TDB_CAP_NOWRITE
;
55 elem
.capability
.type
|= TDB_CAP_NOOPEN
;
57 elem
.capability
.type
|= TDB_CAP_NOCHECK
;
58 elem
.capability
.extra
= extra
;
62 static struct tdb_data
dup_key(struct tdb_data key
)
65 ret
.dsize
= key
.dsize
;
66 ret
.dptr
= malloc(ret
.dsize
);
67 memcpy(ret
.dptr
, key
.dptr
, ret
.dsize
);
71 void tdb_layout_add_used(struct tdb_layout
*layout
,
72 TDB_DATA key
, TDB_DATA data
,
75 union tdb_layout_elem elem
;
76 elem
.base
.type
= DATA
;
77 elem
.used
.key
= dup_key(key
);
78 elem
.used
.data
= dup_key(data
);
79 elem
.used
.extra
= extra
;
83 static tdb_len_t
free_record_len(tdb_len_t len
)
85 return sizeof(struct tdb_used_record
) + len
;
88 static tdb_len_t
data_record_len(struct tle_used
*used
)
91 len
= sizeof(struct tdb_used_record
)
92 + used
->key
.dsize
+ used
->data
.dsize
+ used
->extra
;
93 assert(len
>= sizeof(struct tdb_free_record
));
97 static tdb_len_t
hashtable_len(struct tle_hashtable
*htable
)
99 return sizeof(struct tdb_used_record
)
100 + (sizeof(tdb_off_t
) << TDB_SUBLEVEL_HASH_BITS
)
104 static tdb_len_t
capability_len(struct tle_capability
*cap
)
106 return sizeof(struct tdb_capability
) + cap
->extra
;
109 static tdb_len_t
freetable_len(struct tle_freetable
*ftable
)
111 return sizeof(struct tdb_freetable
);
114 static void set_free_record(void *mem
, tdb_len_t len
)
116 /* We do all the work in add_to_freetable */
119 static void add_zero_pad(struct tdb_used_record
*u
, size_t len
, size_t extra
)
122 ((char *)(u
+ 1))[len
] = '\0';
125 static void set_data_record(void *mem
, struct tdb_context
*tdb
,
126 struct tle_used
*used
)
128 struct tdb_used_record
*u
= mem
;
130 set_header(tdb
, u
, TDB_USED_MAGIC
, used
->key
.dsize
, used
->data
.dsize
,
131 used
->key
.dsize
+ used
->data
.dsize
+ used
->extra
,
132 tdb_hash(tdb
, used
->key
.dptr
, used
->key
.dsize
));
133 memcpy(u
+ 1, used
->key
.dptr
, used
->key
.dsize
);
134 memcpy((char *)(u
+ 1) + used
->key
.dsize
,
135 used
->data
.dptr
, used
->data
.dsize
);
136 add_zero_pad(u
, used
->key
.dsize
+ used
->data
.dsize
, used
->extra
);
139 static void set_hashtable(void *mem
, struct tdb_context
*tdb
,
140 struct tle_hashtable
*htable
)
142 struct tdb_used_record
*u
= mem
;
143 tdb_len_t len
= sizeof(tdb_off_t
) << TDB_SUBLEVEL_HASH_BITS
;
145 set_header(tdb
, u
, TDB_HTABLE_MAGIC
, 0, len
, len
+ htable
->extra
, 0);
146 memset(u
+ 1, 0, len
);
147 add_zero_pad(u
, len
, htable
->extra
);
150 static void set_capability(void *mem
, struct tdb_context
*tdb
,
151 struct tle_capability
*cap
, struct tdb_header
*hdr
,
154 struct tdb_capability
*c
= mem
;
155 tdb_len_t len
= sizeof(*c
) - sizeof(struct tdb_used_record
) + cap
->extra
;
159 set_header(tdb
, &c
->hdr
, TDB_CAP_MAGIC
, 0, len
, len
, 0);
161 /* Append to capability list. */
163 hdr
->capabilities
= cap
->base
.off
;
165 c
= (struct tdb_capability
*)((char *)hdr
+ last_cap
);
166 c
->next
= cap
->base
.off
;
170 static void set_freetable(void *mem
, struct tdb_context
*tdb
,
171 struct tle_freetable
*freetable
, struct tdb_header
*hdr
,
172 tdb_off_t last_ftable
)
174 struct tdb_freetable
*ftable
= mem
;
175 memset(ftable
, 0, sizeof(*ftable
));
176 set_header(tdb
, &ftable
->hdr
, TDB_FTABLE_MAGIC
, 0,
177 sizeof(*ftable
) - sizeof(ftable
->hdr
),
178 sizeof(*ftable
) - sizeof(ftable
->hdr
), 0);
181 ftable
= (struct tdb_freetable
*)((char *)hdr
+ last_ftable
);
182 ftable
->next
= freetable
->base
.off
;
184 hdr
->free_table
= freetable
->base
.off
;
188 static void add_to_freetable(struct tdb_context
*tdb
,
192 struct tle_freetable
*freetable
)
194 tdb
->tdb2
.ftable_off
= freetable
->base
.off
;
195 tdb
->tdb2
.ftable
= ftable
;
196 add_free_record(tdb
, eoff
, sizeof(struct tdb_used_record
) + elen
,
197 TDB_LOCK_WAIT
, false);
200 static tdb_off_t
hbucket_off(tdb_off_t group_start
, unsigned ingroup
)
203 + (ingroup
% (1 << TDB_HASH_GROUP_BITS
)) * sizeof(tdb_off_t
);
206 /* Get bits from a value. */
207 static uint32_t bits(uint64_t val
, unsigned start
, unsigned num
)
210 return (val
>> start
) & ((1U << num
) - 1);
213 /* We take bits from the top: that way we can lock whole sections of the hash
214 * by using lock ranges. */
215 static uint32_t use_bits(uint64_t h
, unsigned num
, unsigned *used
)
218 return bits(h
, 64 - *used
, num
);
221 static tdb_off_t
encode_offset(tdb_off_t new_off
, unsigned bucket
,
226 | ((uint64_t)bits(h
, 64 - TDB_OFF_UPPER_STEAL_EXTRA
,
227 TDB_OFF_UPPER_STEAL_EXTRA
)
228 << TDB_OFF_HASH_EXTRA_BIT
);
231 /* FIXME: Our hash table handling here is primitive: we don't expand! */
232 static void add_to_hashtable(struct tdb_context
*tdb
,
236 uint64_t h
= tdb_hash(tdb
, key
.dptr
, key
.dsize
);
237 tdb_off_t b_off
, group_start
;
238 unsigned i
, group
, in_group
;
241 group
= use_bits(h
, TDB_TOPLEVEL_HASH_BITS
-TDB_HASH_GROUP_BITS
, &used
);
242 in_group
= use_bits(h
, TDB_HASH_GROUP_BITS
, &used
);
244 group_start
= offsetof(struct tdb_header
, hashtable
)
245 + group
* (sizeof(tdb_off_t
) << TDB_HASH_GROUP_BITS
);
247 for (i
= 0; i
< (1 << TDB_HASH_GROUP_BITS
); i
++) {
248 unsigned bucket
= (in_group
+ i
) % (1 << TDB_HASH_GROUP_BITS
);
250 b_off
= hbucket_off(group_start
, bucket
);
251 if (tdb_read_off(tdb
, b_off
) == 0) {
252 tdb_write_off(tdb
, b_off
,
253 encode_offset(eoff
, in_group
, h
));
260 static struct tle_freetable
*find_ftable(struct tdb_layout
*layout
, unsigned num
)
264 for (i
= 0; i
< layout
->num_elems
; i
++) {
265 if (layout
->elem
[i
].base
.type
!= FREETABLE
)
268 return &layout
->elem
[i
].ftable
;
274 /* FIXME: Support TDB_CONVERT */
275 struct tdb_context
*tdb_layout_get(struct tdb_layout
*layout
,
276 void (*freefn
)(void *),
277 union tdb_attribute
*attr
)
280 tdb_off_t off
, len
, last_ftable
, last_cap
;
282 struct tdb_context
*tdb
;
284 off
= sizeof(struct tdb_header
);
286 /* First pass of layout: calc lengths */
287 for (i
= 0; i
< layout
->num_elems
; i
++) {
288 union tdb_layout_elem
*e
= &layout
->elem
[i
];
290 switch (e
->base
.type
) {
292 len
= freetable_len(&e
->ftable
);
295 len
= free_record_len(e
->free
.len
);
298 len
= data_record_len(&e
->used
);
301 len
= hashtable_len(&e
->hashtable
);
304 len
= capability_len(&e
->capability
);
313 /* Fill with some weird pattern. */
314 memset(mem
, 0x99, off
);
315 /* Now populate our header, cribbing from a real TDB header. */
316 tdb
= tdb_open(NULL
, TDB_INTERNAL
, O_RDWR
, 0, attr
);
317 memcpy(mem
, tdb
->file
->map_ptr
, sizeof(struct tdb_header
));
319 /* Mug the tdb we have to make it use this. */
320 freefn(tdb
->file
->map_ptr
);
321 tdb
->file
->map_ptr
= mem
;
322 tdb
->file
->map_size
= off
;
326 for (i
= 0; i
< layout
->num_elems
; i
++) {
327 union tdb_layout_elem
*e
= &layout
->elem
[i
];
328 switch (e
->base
.type
) {
330 set_freetable(mem
+ e
->base
.off
, tdb
, &e
->ftable
,
331 (struct tdb_header
*)mem
, last_ftable
);
332 last_ftable
= e
->base
.off
;
335 set_free_record(mem
+ e
->base
.off
, e
->free
.len
);
338 set_data_record(mem
+ e
->base
.off
, tdb
, &e
->used
);
341 set_hashtable(mem
+ e
->base
.off
, tdb
, &e
->hashtable
);
344 set_capability(mem
+ e
->base
.off
, tdb
, &e
->capability
,
345 (struct tdb_header
*)mem
, last_cap
);
346 last_cap
= e
->base
.off
;
350 /* Must have a free table! */
353 /* Now fill the free and hash tables. */
354 for (i
= 0; i
< layout
->num_elems
; i
++) {
355 union tdb_layout_elem
*e
= &layout
->elem
[i
];
356 switch (e
->base
.type
) {
358 add_to_freetable(tdb
, e
->base
.off
, e
->free
.len
,
360 find_ftable(layout
, e
->free
.ftable_num
));
363 add_to_hashtable(tdb
, e
->base
.off
, e
->used
.key
);
370 tdb
->tdb2
.ftable_off
= find_ftable(layout
, 0)->base
.off
;
374 void tdb_layout_write(struct tdb_layout
*layout
, void (*freefn
)(void *),
375 union tdb_attribute
*attr
, const char *filename
)
377 struct tdb_context
*tdb
= tdb_layout_get(layout
, freefn
, attr
);
380 fd
= open(filename
, O_WRONLY
|O_TRUNC
|O_CREAT
, 0600);
382 err(1, "opening %s for writing", filename
);
383 if (write(fd
, tdb
->file
->map_ptr
, tdb
->file
->map_size
)
384 != tdb
->file
->map_size
)
385 err(1, "writing %s", filename
);
390 void tdb_layout_free(struct tdb_layout
*layout
)
394 for (i
= 0; i
< layout
->num_elems
; i
++) {
395 if (layout
->elem
[i
].base
.type
== DATA
) {
396 free(layout
->elem
[i
].used
.key
.dptr
);
397 free(layout
->elem
[i
].used
.data
.dptr
);