git.ozlabs.org Git - ccan/blob - ccan/tdb2/test/layout.c

   1 /* TDB tools to create various canned database layouts. */
   2 #include "layout.h"
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <assert.h>
   6 #include <err.h>
   7 #include "logging.h"
   8
   9 struct tdb_layout *new_tdb_layout(const char *filename)
  10 {
  11         struct tdb_layout *layout = malloc(sizeof(*layout));
  12         layout->filename = filename;
  13         layout->num_elems = 0;
  14         layout->elem = NULL;
  15         return layout;
  16 }
  17
  18 static void add(struct tdb_layout *layout, union tdb_layout_elem elem)
  19 {
  20         layout->elem = realloc(layout->elem,
  21                                sizeof(layout->elem[0])
  22                                * (layout->num_elems+1));
  23         layout->elem[layout->num_elems++] = elem;
  24 }
  25
  26 void tdb_layout_add_zone(struct tdb_layout *layout,
  27                          unsigned int zone_bits,
  28                          bool fill_prev)
  29 {
  30         union tdb_layout_elem elem;
  31         if (fill_prev)
  32                 tdb_layout_add_free(layout, 0);
  33         elem.base.type = ZONE;
  34         elem.zone.zone_bits = zone_bits;
  35         add(layout, elem);
  36 }
  37
  38 void tdb_layout_add_free(struct tdb_layout *layout, tdb_len_t len)
  39 {
  40         union tdb_layout_elem elem;
  41         elem.base.type = FREE;
  42         elem.free.len = len;
  43         add(layout, elem);
  44 }
  45
  46 static struct tdb_data dup_key(struct tdb_data key)
  47 {
  48         struct tdb_data ret;
  49         ret.dsize = key.dsize;
  50         ret.dptr = malloc(ret.dsize);
  51         memcpy(ret.dptr, key.dptr, ret.dsize);
  52         return ret;
  53 }
  54
  55 void tdb_layout_add_used(struct tdb_layout *layout,
  56                          TDB_DATA key, TDB_DATA data,
  57                          tdb_len_t extra)
  58 {
  59         union tdb_layout_elem elem;
  60         elem.base.type = DATA;
  61         elem.used.key = dup_key(key);
  62         elem.used.data = dup_key(data);
  63         elem.used.extra = extra;
  64         add(layout, elem);
  65 }
  66
  67 static tdb_len_t free_record_len(tdb_len_t len)
  68 {
  69         return sizeof(struct tdb_used_record) + len;
  70 }
  71
  72 static tdb_len_t data_record_len(struct tle_used *used)
  73 {
  74         tdb_len_t len;
  75         len = sizeof(struct tdb_used_record)
  76                 + used->key.dsize + used->data.dsize + used->extra;
  77         assert(len >= sizeof(struct tdb_free_record));
  78         return len;
  79 }
  80
  81 static tdb_len_t hashtable_len(struct tle_hashtable *htable)
  82 {
  83         return sizeof(struct tdb_used_record)
  84                 + (sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS)
  85                 + htable->extra;
  86 }
  87
  88 static tdb_len_t zone_header_len(struct tle_zone *zone)
  89 {
  90         return sizeof(struct free_zone_header)
  91                 + sizeof(tdb_off_t) * (BUCKETS_FOR_ZONE(zone->zone_bits)+1);
  92 }
  93
  94 static void set_free_record(void *mem, tdb_len_t len)
  95 {
  96         /* We do all the work in add_to_freetable */
  97 }
  98
  99 static void set_data_record(void *mem, struct tdb_context *tdb,
 100                             struct tle_zone *last_zone,
 101                             struct tle_used *used)
 102 {
 103         struct tdb_used_record *u = mem;
 104
 105         set_header(tdb, u, used->key.dsize, used->data.dsize,
 106                    used->key.dsize + used->data.dsize + used->extra,
 107                    tdb_hash(tdb, used->key.dptr, used->key.dsize),
 108                    last_zone->zone_bits);
 109         memcpy(u + 1, used->key.dptr, used->key.dsize);
 110         memcpy((char *)(u + 1) + used->key.dsize,
 111                used->data.dptr, used->data.dsize);
 112 }
 113
 114 static void set_hashtable(void *mem, struct tdb_context *tdb,
 115                           struct tle_zone *last_zone,
 116                           struct tle_hashtable *htable)
 117 {
 118         struct tdb_used_record *u = mem;
 119         tdb_len_t len = sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS;
 120
 121         set_header(tdb, u, 0, len, len + htable->extra, 0,
 122                    last_zone->zone_bits);
 123         memset(u + 1, 0, len);
 124 }
 125
 126 static void set_zone(void *mem, struct tdb_context *tdb,
 127                      struct tle_zone *zone)
 128 {
 129         struct free_zone_header *fz = mem;
 130         memset(fz, 0, zone_header_len(zone));
 131         fz->zone_bits = zone->zone_bits;
 132 }
 133
 134 static void add_to_freetable(struct tdb_context *tdb,
 135                              struct tle_zone *last_zone,
 136                              tdb_off_t eoff,
 137                              tdb_off_t elen)
 138 {
 139         add_free_record(tdb, last_zone->zone_bits, eoff,
 140                         sizeof(struct tdb_used_record) + elen);
 141 }
 142
 143 static tdb_off_t hbucket_off(tdb_off_t group_start, unsigned ingroup)
 144 {
 145         return group_start
 146                 + (ingroup % (1 << TDB_HASH_GROUP_BITS)) * sizeof(tdb_off_t);
 147 }
 148
 149 /* Get bits from a value. */
 150 static uint32_t bits(uint64_t val, unsigned start, unsigned num)
 151 {
 152         assert(num <= 32);
 153         return (val >> start) & ((1U << num) - 1);
 154 }
 155
 156 /* We take bits from the top: that way we can lock whole sections of the hash
 157  * by using lock ranges. */
 158 static uint32_t use_bits(uint64_t h, unsigned num, unsigned *used)
 159 {
 160         *used += num;
 161         return bits(h, 64 - *used, num);
 162 }
 163
 164 static tdb_off_t encode_offset(tdb_off_t new_off, unsigned bucket,
 165                                uint64_t h)
 166 {
 167         return bucket
 168                 | new_off
 169                 | ((uint64_t)bits(h, 64 - TDB_OFF_UPPER_STEAL_EXTRA,
 170                                   TDB_OFF_UPPER_STEAL_EXTRA)
 171                    << TDB_OFF_HASH_EXTRA_BIT);
 172 }
 173
 174 /* FIXME: Our hash table handling here is primitive: we don't expand! */
 175 static void add_to_hashtable(struct tdb_context *tdb,
 176                              tdb_off_t eoff,
 177                              struct tdb_data key)
 178 {
 179         uint64_t h = tdb_hash(tdb, key.dptr, key.dsize);
 180         tdb_off_t b_off, group_start;
 181         unsigned i, group, in_group;
 182         unsigned used = 0;
 183
 184         group = use_bits(h, TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS, &used);
 185         in_group = use_bits(h, TDB_HASH_GROUP_BITS, &used);
 186
 187         group_start = offsetof(struct tdb_header, hashtable)
 188                 + group * (sizeof(tdb_off_t) << TDB_HASH_GROUP_BITS);
 189
 190         for (i = 0; i < (1 << TDB_HASH_GROUP_BITS); i++) {
 191                 unsigned bucket = (in_group + i) % (1 << TDB_HASH_GROUP_BITS);
 192
 193                 b_off = hbucket_off(group_start, bucket);
 194                 if (tdb_read_off(tdb, b_off) == 0) {
 195                         tdb_write_off(tdb, b_off,
 196                                       encode_offset(eoff, bucket, h));
 197                         return;
 198                 }
 199         }
 200         abort();
 201 }
 202
 203 /* FIXME: Support TDB_CONVERT */
 204 struct tdb_context *tdb_layout_get(struct tdb_layout *layout)
 205 {
 206         unsigned int i;
 207         tdb_off_t off, len;
 208         tdb_len_t zone_left;
 209         char *mem;
 210         struct tdb_context *tdb;
 211         struct tle_zone *last_zone = NULL;
 212
 213         assert(layout->elem[0].base.type == ZONE);
 214
 215         zone_left = 0;
 216         off = sizeof(struct tdb_header);
 217
 218         /* First pass of layout: calc lengths */
 219         for (i = 0; i < layout->num_elems; i++) {
 220                 union tdb_layout_elem *e = &layout->elem[i];
 221                 e->base.off = off;
 222                 switch (e->base.type) {
 223                 case ZONE:
 224                         assert(zone_left == 0);
 225                         len = zone_header_len(&e->zone);
 226                         zone_left = 1ULL << e->zone.zone_bits;
 227                         break;
 228                 case FREE:
 229                         if (e->free.len == 0)
 230                                 e->free.len = zone_left
 231                                         - sizeof(struct tdb_used_record);
 232                         len = free_record_len(e->free.len);
 233                         break;
 234                 case DATA:
 235                         len = data_record_len(&e->used);
 236                         break;
 237                 case HASHTABLE:
 238                         len = hashtable_len(&e->hashtable);
 239                         break;
 240                 }
 241                 off += len;
 242                 assert(zone_left >= len);
 243                 zone_left -= len;
 244         }
 245
 246         /* Fill final zone with free record. */
 247         if (zone_left != 0) {
 248                 tdb_layout_add_free(layout,
 249                                     zone_left
 250                                     - sizeof(struct tdb_used_record));
 251                 layout->elem[layout->num_elems-1].base.off = off;
 252                 off += zone_left;
 253         }
 254
 255         mem = malloc(off+1);
 256         /* Now populate our header, cribbing from a real TDB header. */
 257         tdb = tdb_open(NULL, TDB_INTERNAL, O_RDWR, 0, &tap_log_attr);
 258         memcpy(mem, tdb->map_ptr, sizeof(struct tdb_header));
 259
 260         /* Mug the tdb we have to make it use this. */
 261         free(tdb->map_ptr);
 262         tdb->map_ptr = mem;
 263         tdb->map_size = off+1;
 264
 265         for (i = 0; i < layout->num_elems; i++) {
 266                 union tdb_layout_elem *e = &layout->elem[i];
 267                 switch (e->base.type) {
 268                 case ZONE:
 269                         set_zone(mem + e->base.off, tdb, &e->zone);
 270                         last_zone = &e->zone;
 271                         break;
 272                 case FREE:
 273                         set_free_record(mem + e->base.off, e->free.len);
 274                         break;
 275                 case DATA:
 276                         set_data_record(mem + e->base.off, tdb, last_zone,
 277                                         &e->used);
 278                         break;
 279                 case HASHTABLE:
 280                         set_hashtable(mem + e->base.off, tdb, last_zone,
 281                                       &e->hashtable);
 282                         break;
 283                 }
 284         }
 285
 286         /* Now fill the free and hash tables. */
 287         for (i = 0; i < layout->num_elems; i++) {
 288                 union tdb_layout_elem *e = &layout->elem[i];
 289                 switch (e->base.type) {
 290                 case ZONE:
 291                         last_zone = &e->zone;
 292                         break;
 293                 case FREE:
 294                         add_to_freetable(tdb, last_zone,
 295                                          e->base.off, e->free.len);
 296                         break;
 297                 case DATA:
 298                         add_to_hashtable(tdb, e->base.off, e->used.key);
 299                         break;
 300                 default:
 301                         break;
 302                 }
 303         }
 304
 305         /* Write tailer. */
 306         ((uint8_t *)tdb->map_ptr)[tdb->map_size-1] = last_zone->zone_bits;
 307
 308         /* Get physical if they asked for it. */
 309         if (layout->filename) {
 310                 int fd = open(layout->filename, O_WRONLY|O_TRUNC|O_CREAT,
 311                               0600);
 312                 if (fd < 0)
 313                         err(1, "opening %s for writing", layout->filename);
 314                 write(fd, tdb->map_ptr, tdb->map_size);
 315                 close(fd);
 316                 tdb_close(tdb);
 317                 /* NOMMAP is for lockcheck. */
 318                 tdb = tdb_open(layout->filename, TDB_NOMMAP, O_RDWR, 0,
 319                                &tap_log_attr);
 320         }
 321         return tdb;
 322 }