git.ozlabs.org Git - ccan/blob - ccan/tdb2/test/run-04-basichash.c

   1 #include <ccan/tdb2/tdb.c>
   2 #include <ccan/tdb2/free.c>
   3 #include <ccan/tdb2/lock.c>
   4 #include <ccan/tdb2/io.c>
   5 #include <ccan/tdb2/hash.c>
   6 #include <ccan/tdb2/transaction.c>
   7 #include <ccan/tdb2/check.c>
   8 #include <ccan/tap/tap.h>
   9 #include "logging.h"
  10
  11 /* We rig the hash so adjacent-numbered records always clash. */
  12 static uint64_t clash(const void *key, size_t len, uint64_t seed, void *priv)
  13 {
  14         return ((uint64_t)*(unsigned int *)key)
  15                 << (64 - TDB_TOPLEVEL_HASH_BITS - 1);
  16 }
  17
  18 int main(int argc, char *argv[])
  19 {
  20         unsigned int i, j;
  21         struct tdb_context *tdb;
  22         unsigned int v;
  23         struct tdb_used_record rec;
  24         struct tdb_data key = { (unsigned char *)&v, sizeof(v) };
  25         struct tdb_data dbuf = { (unsigned char *)&v, sizeof(v) };
  26         union tdb_attribute hattr = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
  27                                                 .hash_fn = clash } };
  28         int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_NOMMAP,
  29                         TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT,
  30                         TDB_NOMMAP|TDB_CONVERT,
  31         };
  32
  33         hattr.base.next = &tap_log_attr;
  34
  35         plan_tests(sizeof(flags) / sizeof(flags[0])
  36                    * (91 + (2 * ((1 << TDB_HASH_GROUP_BITS) - 1))) + 1);
  37         for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
  38                 struct hash_info h;
  39                 tdb_off_t new_off, off, subhash;
  40
  41                 tdb = tdb_open("run-04-basichash.tdb", flags[i],
  42                                O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
  43                 ok1(tdb);
  44                 if (!tdb)
  45                         continue;
  46
  47                 v = 0;
  48                 /* Should not find it. */
  49                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL) == 0);
  50                 /* Should have created correct hash. */
  51                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
  52                 /* Should have located space in group 0, bucket 0. */
  53                 ok1(h.group_start == offsetof(struct tdb_header, hashtable));
  54                 ok1(h.home_bucket == 0);
  55                 ok1(h.found_bucket == 0);
  56                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS);
  57
  58                 /* Should have lock on bucket 0 */
  59                 ok1(h.hlock_start == 0);
  60                 ok1(h.hlock_range ==
  61                     1ULL << (64-(TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS)));
  62                 ok1((tdb->flags & TDB_NOLOCK) || tdb->num_lockrecs == 1);
  63                 ok1((tdb->flags & TDB_NOLOCK)
  64                     || tdb->lockrecs[0].off == TDB_HASH_LOCK_START);
  65                 /* FIXME: Check lock length */
  66
  67                 /* Allocate a new record. */
  68                 new_off = alloc(tdb, key.dsize, dbuf.dsize, h.h,
  69                                 TDB_USED_MAGIC, false);
  70                 ok1(new_off != TDB_OFF_ERR);
  71
  72                 /* We should be able to add it now. */
  73                 ok1(add_to_hash(tdb, &h, new_off) == 0);
  74
  75                 /* Make sure we fill it in for later finding. */
  76                 off = new_off + sizeof(struct tdb_used_record);
  77                 ok1(!tdb->methods->write(tdb, off, key.dptr, key.dsize));
  78                 off += key.dsize;
  79                 ok1(!tdb->methods->write(tdb, off, dbuf.dptr, dbuf.dsize));
  80
  81                 /* We should be able to unlock that OK. */
  82                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
  83                                       F_WRLCK) == 0);
  84
  85                 /* Database should be consistent. */
  86                 ok1(tdb_check(tdb, NULL, NULL) == 0);
  87
  88                 /* Now, this should give a successful lookup. */
  89                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL)
  90                     == new_off);
  91                 /* Should have created correct hash. */
  92                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
  93                 /* Should have located space in group 0, bucket 0. */
  94                 ok1(h.group_start == offsetof(struct tdb_header, hashtable));
  95                 ok1(h.home_bucket == 0);
  96                 ok1(h.found_bucket == 0);
  97                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS);
  98
  99                 /* Should have lock on bucket 0 */
 100                 ok1(h.hlock_start == 0);
 101                 ok1(h.hlock_range ==
 102                     1ULL << (64-(TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS)));
 103                 ok1((tdb->flags & TDB_NOLOCK) || tdb->num_lockrecs == 1);
 104                 ok1((tdb->flags & TDB_NOLOCK)
 105                     || tdb->lockrecs[0].off == TDB_HASH_LOCK_START);
 106                 /* FIXME: Check lock length */
 107
 108                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 109                                       F_WRLCK) == 0);
 110
 111                 /* Database should be consistent. */
 112                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 113
 114                 /* Test expansion. */
 115                 v = 1;
 116                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 117                 /* Should have created correct hash. */
 118                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 119                 /* Should have located space in group 0, bucket 1. */
 120                 ok1(h.group_start == offsetof(struct tdb_header, hashtable));
 121                 ok1(h.home_bucket == 0);
 122                 ok1(h.found_bucket == 1);
 123                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS);
 124
 125                 /* Should have lock on bucket 0 */
 126                 ok1(h.hlock_start == 0);
 127                 ok1(h.hlock_range ==
 128                     1ULL << (64-(TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS)));
 129                 ok1((tdb->flags & TDB_NOLOCK) || tdb->num_lockrecs == 1);
 130                 ok1((tdb->flags & TDB_NOLOCK)
 131                     || tdb->lockrecs[0].off == TDB_HASH_LOCK_START);
 132                 /* FIXME: Check lock length */
 133
 134                 /* Make it expand 0'th bucket. */
 135                 ok1(expand_group(tdb, &h) == 0);
 136                 /* First one should be subhash, next should be empty. */
 137                 ok1(is_subhash(h.group[0]));
 138                 subhash = (h.group[0] & TDB_OFF_MASK);
 139                 for (j = 1; j < (1 << TDB_HASH_GROUP_BITS); j++)
 140                         ok1(h.group[j] == 0);
 141
 142                 ok1(tdb_write_convert(tdb, h.group_start,
 143                                       h.group, sizeof(h.group)) == 0);
 144                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 145                                       F_WRLCK) == 0);
 146
 147                 /* Should be happy with expansion. */
 148                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 149
 150                 /* Should be able to find it. */
 151                 v = 0;
 152                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL)
 153                     == new_off);
 154                 /* Should have created correct hash. */
 155                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 156                 /* Should have located space in expanded group 0, bucket 0. */
 157                 ok1(h.group_start == subhash + sizeof(struct tdb_used_record));
 158                 ok1(h.home_bucket == 0);
 159                 ok1(h.found_bucket == 0);
 160                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS
 161                     + TDB_SUBLEVEL_HASH_BITS);
 162
 163                 /* Should have lock on bucket 0 */
 164                 ok1(h.hlock_start == 0);
 165                 ok1(h.hlock_range ==
 166                     1ULL << (64-(TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS)));
 167                 ok1((tdb->flags & TDB_NOLOCK) || tdb->num_lockrecs == 1);
 168                 ok1((tdb->flags & TDB_NOLOCK)
 169                     || tdb->lockrecs[0].off == TDB_HASH_LOCK_START);
 170                 /* FIXME: Check lock length */
 171
 172                 /* Simple delete should work. */
 173                 ok1(delete_from_hash(tdb, &h) == 0);
 174                 ok1(add_free_record(tdb, new_off,
 175                                     sizeof(struct tdb_used_record)
 176                                     + rec_key_length(&rec)
 177                                     + rec_data_length(&rec)
 178                                     + rec_extra_padding(&rec)) == 0);
 179                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 180                                       F_WRLCK) == 0);
 181                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 182
 183                 /* Test second-level expansion: should expand 0th bucket. */
 184                 v = 0;
 185                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 186                 /* Should have created correct hash. */
 187                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 188                 /* Should have located space in group 0, bucket 0. */
 189                 ok1(h.group_start == subhash + sizeof(struct tdb_used_record));
 190                 ok1(h.home_bucket == 0);
 191                 ok1(h.found_bucket == 0);
 192                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS+TDB_SUBLEVEL_HASH_BITS);
 193
 194                 /* Should have lock on bucket 0 */
 195                 ok1(h.hlock_start == 0);
 196                 ok1(h.hlock_range ==
 197                     1ULL << (64-(TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS)));
 198                 ok1((tdb->flags & TDB_NOLOCK) || tdb->num_lockrecs == 1);
 199                 ok1((tdb->flags & TDB_NOLOCK)
 200                     || tdb->lockrecs[0].off == TDB_HASH_LOCK_START);
 201                 /* FIXME: Check lock length */
 202
 203                 ok1(expand_group(tdb, &h) == 0);
 204                 /* First one should be subhash, next should be empty. */
 205                 ok1(is_subhash(h.group[0]));
 206                 subhash = (h.group[0] & TDB_OFF_MASK);
 207                 for (j = 1; j < (1 << TDB_HASH_GROUP_BITS); j++)
 208                         ok1(h.group[j] == 0);
 209                 ok1(tdb_write_convert(tdb, h.group_start,
 210                                       h.group, sizeof(h.group)) == 0);
 211                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 212                                       F_WRLCK) == 0);
 213
 214                 /* Should be happy with expansion. */
 215                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 216
 217                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 218                 /* Should have created correct hash. */
 219                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 220                 /* Should have located space in group 0, bucket 0. */
 221                 ok1(h.group_start == subhash + sizeof(struct tdb_used_record));
 222                 ok1(h.home_bucket == 0);
 223                 ok1(h.found_bucket == 0);
 224                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS
 225                     + TDB_SUBLEVEL_HASH_BITS * 2);
 226
 227                 /* We should be able to add it now. */
 228                 /* Allocate a new record. */
 229                 new_off = alloc(tdb, key.dsize, dbuf.dsize, h.h,
 230                                 TDB_USED_MAGIC, false);
 231                 ok1(new_off != TDB_OFF_ERR);
 232                 ok1(add_to_hash(tdb, &h, new_off) == 0);
 233
 234                 /* Make sure we fill it in for later finding. */
 235                 off = new_off + sizeof(struct tdb_used_record);
 236                 ok1(!tdb->methods->write(tdb, off, key.dptr, key.dsize));
 237                 off += key.dsize;
 238                 ok1(!tdb->methods->write(tdb, off, dbuf.dptr, dbuf.dsize));
 239
 240                 /* We should be able to unlock that OK. */
 241                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 242                                       F_WRLCK) == 0);
 243
 244                 /* Database should be consistent. */
 245                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 246
 247                 /* Should be able to find it. */
 248                 v = 0;
 249                 ok1(find_and_lock(tdb, key, F_WRLCK, &h, &rec, NULL)
 250                     == new_off);
 251                 /* Should have created correct hash. */
 252                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 253                 /* Should have located space in expanded group 0, bucket 0. */
 254                 ok1(h.group_start == subhash + sizeof(struct tdb_used_record));
 255                 ok1(h.home_bucket == 0);
 256                 ok1(h.found_bucket == 0);
 257                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS
 258                     + TDB_SUBLEVEL_HASH_BITS * 2);
 259
 260                 tdb_close(tdb);
 261         }
 262
 263         ok1(tap_log_messages == 0);
 264         return exit_status();
 265 }