X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ftest%2Flayout.c;h=3049d3214e62736ec95ddbe979cafe7784034593;hp=f0a2b897e38032b17b8d00b3efe2cfdded708ebd;hb=dfae76fd82d4bbd8989264dadc2c3c9cde7e5af7;hpb=cb399d268c839dd75a59678268f3ba666147cc20;ds=sidebyside

diff --git a/ccan/tdb2/test/layout.c b/ccan/tdb2/test/layout.c
index f0a2b897..3049d321 100644
--- a/ccan/tdb2/test/layout.c
+++ b/ccan/tdb2/test/layout.c
@@ -3,13 +3,15 @@
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
+#include <err.h>
+#include "logging.h"
 
-struct tdb_layout *new_tdb_layout(void)
+struct tdb_layout *new_tdb_layout(const char *filename)
 {
 	struct tdb_layout *layout = malloc(sizeof(*layout));
+	layout->filename = filename;
 	layout->num_elems = 0;
 	layout->elem = NULL;
-	layout->ftable = layout->htable = -1;
 	return layout;
 }
 
@@ -21,11 +23,20 @@ static void add(struct tdb_layout *layout, union tdb_layout_elem elem)
 	layout->elem[layout->num_elems++] = elem;
 }
 
-void tdb_layout_add_free(struct tdb_layout *layout, tdb_len_t len)
+void tdb_layout_add_freelist(struct tdb_layout *layout)
+{
+	union tdb_layout_elem elem;
+	elem.base.type = FREELIST;
+	add(layout, elem);
+}
+
+void tdb_layout_add_free(struct tdb_layout *layout, tdb_len_t len,
+			 unsigned flist)
 {
 	union tdb_layout_elem elem;
 	elem.base.type = FREE;
 	elem.free.len = len;
+	elem.free.flist_num = flist;
 	add(layout, elem);
 }
 
@@ -50,36 +61,6 @@ void tdb_layout_add_used(struct tdb_layout *layout,
 	add(layout, elem);
 }
 
-void tdb_layout_add_hashtable(struct tdb_layout *layout,
-			      unsigned int hash_bits,
-			      tdb_len_t extra)
-{
-	union tdb_layout_elem elem;
-	elem.base.type = HASHTABLE;
-	elem.hashtable.hash_bits = hash_bits;
-	elem.hashtable.extra = extra;
-	assert(layout->htable == -1U);
-	layout->htable = layout->num_elems;
-	add(layout, elem);
-}
-
-void tdb_layout_add_freetable(struct tdb_layout *layout,
-			      unsigned int num_zones,
-			      unsigned int zone_bits,
-			      unsigned int num_buckets,
-			      tdb_len_t extra)
-{
-	union tdb_layout_elem elem;
-	elem.base.type = FREETABLE;
-	elem.freetable.num_zones = num_zones;
-	elem.freetable.zone_bits = zone_bits;
-	elem.freetable.num_buckets = num_buckets;
-	elem.freetable.extra = extra;
-	assert(layout->ftable == -1U);
-	layout->ftable = layout->num_elems;
-	add(layout, elem);
-}
-
 static tdb_len_t free_record_len(tdb_len_t len)
 {
 	return sizeof(struct tdb_used_record) + len;
@@ -97,14 +78,13 @@ static tdb_len_t data_record_len(struct tle_used *used)
 static tdb_len_t hashtable_len(struct tle_hashtable *htable)
 {
 	return sizeof(struct tdb_used_record)
-		+ (sizeof(tdb_off_t) << htable->hash_bits);
+		+ (sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS)
+		+ htable->extra;
 }
 
-static tdb_len_t freetable_len(struct tle_freetable *ftable)
+static tdb_len_t freelist_len(struct tle_freelist *flist)
 {
-	return sizeof(struct tdb_used_record)
-		+ (sizeof(tdb_off_t) * ftable->num_zones
-		   * (ftable->num_buckets + 1));
+	return sizeof(struct tdb_freelist);
 }
 
 static void set_free_record(void *mem, tdb_len_t len)
@@ -117,9 +97,9 @@ static void set_data_record(void *mem, struct tdb_context *tdb,
 {
 	struct tdb_used_record *u = mem;
 
-	set_header(tdb, u, used->key.dsize, used->data.dsize,
-		   used->key.dsize + used->data.dsize + used->extra,
-		   tdb_hash(tdb, used->key.dptr, used->key.dsize));
+	set_used_header(tdb, u, used->key.dsize, used->data.dsize,
+			used->key.dsize + used->data.dsize + used->extra,
+			tdb_hash(tdb, used->key.dptr, used->key.dsize));
 	memcpy(u + 1, used->key.dptr, used->key.dsize);
 	memcpy((char *)(u + 1) + used->key.dsize,
 	       used->data.dptr, used->data.dsize);
@@ -129,108 +109,165 @@ static void set_hashtable(void *mem, struct tdb_context *tdb,
 			  struct tle_hashtable *htable)
 {
 	struct tdb_used_record *u = mem;
-	tdb_len_t len = sizeof(tdb_off_t) << htable->hash_bits;
+	tdb_len_t len = sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS;
 
-	set_header(tdb, u, 0, len, len + htable->extra, 0);
+	set_used_header(tdb, u, 0, len, len + htable->extra, 0);
 	memset(u + 1, 0, len);
 }
 
-static void set_freetable(void *mem, struct tdb_context *tdb,
-			  struct tle_freetable *ftable)
+static void set_freelist(void *mem, struct tdb_context *tdb,
+			 struct tle_freelist *freelist, struct tdb_header *hdr,
+			 tdb_off_t last_flist)
 {
-	struct tdb_used_record *u = mem;
-	tdb_len_t len = sizeof(tdb_off_t) * ftable->num_zones
-		* (ftable->num_buckets + 1);
-	set_header(tdb, u, 0, len, len + ftable->extra, 0);
-	memset(u + 1, 0, len);
+	struct tdb_freelist *flist = mem;
+	memset(flist, 0, sizeof(*flist));
+	set_used_header(tdb, &flist->hdr, 0,
+			sizeof(*flist) - sizeof(flist->hdr),
+			sizeof(*flist) - sizeof(flist->hdr), 1);
+
+	if (last_flist) {
+		flist = (struct tdb_freelist *)((char *)hdr + last_flist);
+		flist->next = freelist->base.off;
+	} else {
+		hdr->free_list = freelist->base.off;
+	}
 }
 
 static void add_to_freetable(struct tdb_context *tdb,
 			     tdb_off_t eoff,
-			     tdb_off_t elen)
+			     tdb_off_t elen,
+			     struct tle_freelist *freelist)
 {
+	tdb->flist_off = freelist->base.off;
 	add_free_record(tdb, eoff, sizeof(struct tdb_used_record) + elen);
 }
 
-static tdb_off_t hash_off(struct tdb_context *tdb, uint64_t list)
+static tdb_off_t hbucket_off(tdb_off_t group_start, unsigned ingroup)
+{
+	return group_start
+		+ (ingroup % (1 << TDB_HASH_GROUP_BITS)) * sizeof(tdb_off_t);
+}
+
+/* Get bits from a value. */
+static uint32_t bits(uint64_t val, unsigned start, unsigned num)
+{
+	assert(num <= 32);
+	return (val >> start) & ((1U << num) - 1);
+}
+
+/* We take bits from the top: that way we can lock whole sections of the hash
+ * by using lock ranges. */
+static uint32_t use_bits(uint64_t h, unsigned num, unsigned *used)
+{
+	*used += num;
+	return bits(h, 64 - *used, num);
+}
+
+static tdb_off_t encode_offset(tdb_off_t new_off, unsigned bucket,
+			       uint64_t h)
 {
-	return tdb->header.v.hash_off
-		+ ((list & ((1ULL << tdb->header.v.hash_bits) - 1))
-		   * sizeof(tdb_off_t));
+	return bucket
+		| new_off
+		| ((uint64_t)bits(h, 64 - TDB_OFF_UPPER_STEAL_EXTRA,
+				  TDB_OFF_UPPER_STEAL_EXTRA)
+		   << TDB_OFF_HASH_EXTRA_BIT);
 }
 
+/* FIXME: Our hash table handling here is primitive: we don't expand! */
 static void add_to_hashtable(struct tdb_context *tdb,
 			     tdb_off_t eoff,
 			     struct tdb_data key)
 {
-	uint64_t hash = tdb_hash(tdb, key.dptr, key.dsize);
-	tdb_off_t hoff;
+	uint64_t h = tdb_hash(tdb, key.dptr, key.dsize);
+	tdb_off_t b_off, group_start;
+	unsigned i, group, in_group;
+	unsigned used = 0;
+
+	group = use_bits(h, TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS, &used);
+	in_group = use_bits(h, TDB_HASH_GROUP_BITS, &used);
+
+	group_start = offsetof(struct tdb_header, hashtable)
+		+ group * (sizeof(tdb_off_t) << TDB_HASH_GROUP_BITS);
+
+	for (i = 0; i < (1 << TDB_HASH_GROUP_BITS); i++) {
+		unsigned bucket = (in_group + i) % (1 << TDB_HASH_GROUP_BITS);
+
+		b_off = hbucket_off(group_start, bucket);		
+		if (tdb_read_off(tdb, b_off) == 0) {
+			tdb_write_off(tdb, b_off,
+				      encode_offset(eoff, bucket, h));
+			return;
+		}
+	}
+	abort();
+}
 
-	while (tdb_read_off(tdb, hoff = hash_off(tdb, hash)) != 0)
-		hash++;
+static struct tle_freelist *find_flist(struct tdb_layout *layout, unsigned num)
+{
+	unsigned i;
 
-	tdb_write_off(tdb, hoff, eoff);
+	for (i = 0; i < layout->num_elems; i++) {
+		if (layout->elem[i].base.type != FREELIST)
+			continue;
+		if (num == 0)
+			return &layout->elem[i].flist;
+		num--;
+	}
+	abort();
 }
 
 /* FIXME: Support TDB_CONVERT */
 struct tdb_context *tdb_layout_get(struct tdb_layout *layout)
 {
 	unsigned int i;
-	tdb_off_t len;
-	struct tdb_header *hdr;
+	tdb_off_t off, len, last_flist;
 	char *mem;
 	struct tdb_context *tdb;
 
-	assert(layout->ftable != -1U);
-	assert(layout->htable != -1U);
-
-	len = sizeof(struct tdb_header);
+	off = sizeof(struct tdb_header);
 
 	/* First pass of layout: calc lengths */
 	for (i = 0; i < layout->num_elems; i++) {
 		union tdb_layout_elem *e = &layout->elem[i];
-		e->base.off = len;
+		e->base.off = off;
 		switch (e->base.type) {
+		case FREELIST:
+			len = freelist_len(&e->flist);
+			break;
 		case FREE:
-			len += free_record_len(e->free.len);
+			len = free_record_len(e->free.len);
 			break;
 		case DATA:
-			len += data_record_len(&e->used);
+			len = data_record_len(&e->used);
 			break;
 		case HASHTABLE:
-			len += hashtable_len(&e->hashtable);
-			break;
-		case FREETABLE:
-			len += freetable_len(&e->freetable);
+			len = hashtable_len(&e->hashtable);
 			break;
+		default:
+			abort();
 		}
+		off += len;
 	}
 
-	mem = malloc(len);
+	mem = malloc(off);
 	/* Now populate our header, cribbing from a real TDB header. */
-	tdb = tdb_open(NULL, TDB_INTERNAL, O_RDWR, 0, NULL);
-	hdr = (void *)mem;
-	*hdr = tdb->header;
-	hdr->v.generation++;
-	hdr->v.num_zones = layout->elem[layout->ftable].freetable.num_zones;
-	hdr->v.zone_bits = layout->elem[layout->ftable].freetable.zone_bits;
-	hdr->v.free_buckets
-		= layout->elem[layout->ftable].freetable.num_buckets;
-	hdr->v.free_off = layout->elem[layout->ftable].base.off
-		+ sizeof(struct tdb_used_record);
-	hdr->v.hash_bits = layout->elem[layout->htable].hashtable.hash_bits;
-	hdr->v.hash_off = layout->elem[layout->htable].base.off
-		+ sizeof(struct tdb_used_record);
+	tdb = tdb_open(NULL, TDB_INTERNAL, O_RDWR, 0, &tap_log_attr);
+	memcpy(mem, tdb->map_ptr, sizeof(struct tdb_header));
 
 	/* Mug the tdb we have to make it use this. */
 	free(tdb->map_ptr);
 	tdb->map_ptr = mem;
-	tdb->map_size = len;
-	header_changed(tdb);
+	tdb->map_size = off;
 
+	last_flist = 0;
 	for (i = 0; i < layout->num_elems; i++) {
 		union tdb_layout_elem *e = &layout->elem[i];
 		switch (e->base.type) {
+		case FREELIST:
+			set_freelist(mem + e->base.off, tdb, &e->flist,
+				     (struct tdb_header *)mem, last_flist);
+			last_flist = e->base.off;
+			break;
 		case FREE:
 			set_free_record(mem + e->base.off, e->free.len);
 			break;
@@ -240,18 +277,18 @@ struct tdb_context *tdb_layout_get(struct tdb_layout *layout)
 		case HASHTABLE:
 			set_hashtable(mem + e->base.off, tdb, &e->hashtable);
 			break;
-		case FREETABLE:
-			set_freetable(mem + e->base.off, tdb, &e->freetable);
-			break;
 		}
 	}
+	/* Must have a free list! */
+	assert(last_flist);
 
 	/* Now fill the free and hash tables. */
 	for (i = 0; i < layout->num_elems; i++) {
 		union tdb_layout_elem *e = &layout->elem[i];
 		switch (e->base.type) {
 		case FREE:
-			add_to_freetable(tdb, e->base.off, e->free.len);
+			add_to_freetable(tdb, e->base.off, e->free.len,
+					 find_flist(layout, e->free.flist_num));
 			break;
 		case DATA:
 			add_to_hashtable(tdb, e->base.off, e->used.key);
@@ -261,5 +298,22 @@ struct tdb_context *tdb_layout_get(struct tdb_layout *layout)
 		}
 	}
 
+	tdb->flist_off = find_flist(layout, 0)->base.off;
+
+	/* Get physical if they asked for it. */
+	if (layout->filename) {
+		int fd = open(layout->filename, O_WRONLY|O_TRUNC|O_CREAT,
+			      0600);
+		if (fd < 0)
+			err(1, "opening %s for writing", layout->filename);
+		if (write(fd, tdb->map_ptr, tdb->map_size) != tdb->map_size)
+			err(1, "writing %s", layout->filename);
+		close(fd);
+		tdb_close(tdb);
+		/* NOMMAP is for lockcheck. */
+		tdb = tdb_open(layout->filename, TDB_NOMMAP, O_RDWR, 0,
+			       &tap_log_attr);
+	}
+
 	return tdb;
 }