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

   1 #include "ntdb-source.h"
   2 #include "tap-interface.h"
   3 #include "logging.h"
   4
   5 /* We rig the hash so all records clash. */
   6 static uint32_t clash(const void *key, size_t len, uint32_t seed, void *priv)
   7 {
   8         return *((const unsigned int *)key) << 20;
   9 }
  10
  11 int main(int argc, char *argv[])
  12 {
  13         unsigned int i;
  14         struct ntdb_context *ntdb;
  15         unsigned int v;
  16         struct ntdb_used_record rec;
  17         NTDB_DATA key = { (unsigned char *)&v, sizeof(v) };
  18         NTDB_DATA dbuf = { (unsigned char *)&v, sizeof(v) };
  19         union ntdb_attribute hattr = { .hash = { .base = { NTDB_ATTRIBUTE_HASH },
  20                                                 .fn = clash } };
  21         int flags[] = { NTDB_INTERNAL, NTDB_DEFAULT, NTDB_NOMMAP,
  22                         NTDB_INTERNAL|NTDB_CONVERT, NTDB_CONVERT,
  23                         NTDB_NOMMAP|NTDB_CONVERT,
  24         };
  25
  26         hattr.base.next = &tap_log_attr;
  27
  28         plan_tests(sizeof(flags) / sizeof(flags[0]) * 137 + 1);
  29         for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
  30                 struct hash_info h;
  31                 ntdb_off_t new_off, new_off2, off;
  32
  33                 ntdb = ntdb_open("run-04-basichash.ntdb", flags[i]|MAYBE_NOSYNC,
  34                                  O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
  35                 ok1(ntdb);
  36                 if (!ntdb)
  37                         continue;
  38
  39                 v = 0;
  40                 /* Should not find it. */
  41                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
  42                 /* Should have created correct hash. */
  43                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
  44                 /* Should have located space in top table, bucket 0. */
  45                 ok1(h.table == NTDB_HASH_OFFSET);
  46                 ok1(h.table_size == (1 << ntdb->hash_bits));
  47                 ok1(h.bucket == 0);
  48                 ok1(h.old_val == 0);
  49
  50                 /* Should have lock on bucket 0 */
  51                 ok1(h.h == 0);
  52                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
  53                 ok1((ntdb->flags & NTDB_NOLOCK)
  54                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
  55                 /* FIXME: Check lock length */
  56
  57                 /* Allocate a new record. */
  58                 new_off = alloc(ntdb, key.dsize, dbuf.dsize,
  59                                 NTDB_USED_MAGIC, false);
  60                 ok1(!NTDB_OFF_IS_ERR(new_off));
  61
  62                 /* We should be able to add it now. */
  63                 ok1(add_to_hash(ntdb, &h, new_off) == 0);
  64
  65                 /* Make sure we fill it in for later finding. */
  66                 off = new_off + sizeof(struct ntdb_used_record);
  67                 ok1(!ntdb->io->twrite(ntdb, off, key.dptr, key.dsize));
  68                 off += key.dsize;
  69                 ok1(!ntdb->io->twrite(ntdb, off, dbuf.dptr, dbuf.dsize));
  70
  71                 /* We should be able to unlock that OK. */
  72                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
  73
  74                 /* Database should be consistent. */
  75                 ok1(ntdb_check(ntdb, NULL, NULL) == 0);
  76
  77                 /* Now, this should give a successful lookup. */
  78                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off);
  79                 /* Should have created correct hash. */
  80                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
  81                 /* Should have located it in top table, bucket 0. */
  82                 ok1(h.table == NTDB_HASH_OFFSET);
  83                 ok1(h.table_size == (1 << ntdb->hash_bits));
  84                 ok1(h.bucket == 0);
  85
  86                 /* Should have lock on bucket 0 */
  87                 ok1(h.h == 0);
  88                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
  89                 ok1((ntdb->flags & NTDB_NOLOCK)
  90                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
  91                 /* FIXME: Check lock length */
  92
  93                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
  94
  95                 /* Database should be consistent. */
  96                 ok1(ntdb_check(ntdb, NULL, NULL) == 0);
  97
  98                 /* Test expansion. */
  99                 v = 1;
 100                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 101                 /* Should have created correct hash. */
 102                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 103                 /* Should have located clash in toplevel bucket 0. */
 104                 ok1(h.table == NTDB_HASH_OFFSET);
 105                 ok1(h.table_size == (1 << ntdb->hash_bits));
 106                 ok1(h.bucket == 0);
 107                 ok1((h.old_val & NTDB_OFF_MASK) == new_off);
 108
 109                 /* Should have lock on bucket 0 */
 110                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 111                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 112                 ok1((ntdb->flags & NTDB_NOLOCK)
 113                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 114                 /* FIXME: Check lock length */
 115
 116                 new_off2 = alloc(ntdb, key.dsize, dbuf.dsize,
 117                                  NTDB_USED_MAGIC, false);
 118                 ok1(!NTDB_OFF_IS_ERR(new_off2));
 119
 120                 off = new_off2 + sizeof(struct ntdb_used_record);
 121                 ok1(!ntdb->io->twrite(ntdb, off, key.dptr, key.dsize));
 122                 off += key.dsize;
 123                 ok1(!ntdb->io->twrite(ntdb, off, dbuf.dptr, dbuf.dsize));
 124
 125                 /* We should be able to add it now. */
 126                 ok1(add_to_hash(ntdb, &h, new_off2) == 0);
 127                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 128
 129                 /* Should be happy with expansion. */
 130                 ok1(ntdb_check(ntdb, NULL, NULL) == 0);
 131
 132                 /* Should be able to find both. */
 133                 v = 1;
 134                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off2);
 135                 /* Should have created correct hash. */
 136                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 137                 /* Should have located space in chain. */
 138                 ok1(h.table > NTDB_HASH_OFFSET);
 139                 ok1(h.table_size == 2);
 140                 ok1(h.bucket == 1);
 141                 /* Should have lock on bucket 0 */
 142                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 143                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 144                 ok1((ntdb->flags & NTDB_NOLOCK)
 145                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 146                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 147
 148                 v = 0;
 149                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off);
 150                 /* Should have created correct hash. */
 151                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 152                 /* Should have located space in chain. */
 153                 ok1(h.table > NTDB_HASH_OFFSET);
 154                 ok1(h.table_size == 2);
 155                 ok1(h.bucket == 0);
 156
 157                 /* Should have lock on bucket 0 */
 158                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 159                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 160                 ok1((ntdb->flags & NTDB_NOLOCK)
 161                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 162                 /* FIXME: Check lock length */
 163
 164                 /* Simple delete should work. */
 165                 ok1(delete_from_hash(ntdb, &h) == 0);
 166                 ok1(add_free_record(ntdb, new_off,
 167                                     sizeof(struct ntdb_used_record)
 168                                     + rec_key_length(&rec)
 169                                     + rec_data_length(&rec)
 170                                     + rec_extra_padding(&rec),
 171                                     NTDB_LOCK_NOWAIT, false) == 0);
 172                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 173                 ok1(ntdb_check(ntdb, NULL, NULL) == 0);
 174
 175                 /* Should still be able to find other record. */
 176                 v = 1;
 177                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off2);
 178                 /* Should have created correct hash. */
 179                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 180                 /* Should have located space in chain. */
 181                 ok1(h.table > NTDB_HASH_OFFSET);
 182                 ok1(h.table_size == 2);
 183                 ok1(h.bucket == 1);
 184                 /* Should have lock on bucket 0 */
 185                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 186                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 187                 ok1((ntdb->flags & NTDB_NOLOCK)
 188                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 189                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 190
 191                 /* Now should find empty space. */
 192                 v = 0;
 193                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 194                 /* Should have created correct hash. */
 195                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 196                 /* Should have located space in chain, bucket 0. */
 197                 ok1(h.table > NTDB_HASH_OFFSET);
 198                 ok1(h.table_size == 2);
 199                 ok1(h.bucket == 0);
 200                 ok1(h.old_val == 0);
 201
 202                 /* Adding another record should work. */
 203                 v = 2;
 204                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 205                 /* Should have created correct hash. */
 206                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 207                 /* Should have located space in chain, bucket 0. */
 208                 ok1(h.table > NTDB_HASH_OFFSET);
 209                 ok1(h.table_size == 2);
 210                 ok1(h.bucket == 0);
 211                 ok1(h.old_val == 0);
 212
 213                 /* Should have lock on bucket 0 */
 214                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 215                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 216                 ok1((ntdb->flags & NTDB_NOLOCK)
 217                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 218
 219                 new_off = alloc(ntdb, key.dsize, dbuf.dsize,
 220                                 NTDB_USED_MAGIC, false);
 221                 ok1(!NTDB_OFF_IS_ERR(new_off2));
 222                 ok1(add_to_hash(ntdb, &h, new_off) == 0);
 223                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 224
 225                 off = new_off + sizeof(struct ntdb_used_record);
 226                 ok1(!ntdb->io->twrite(ntdb, off, key.dptr, key.dsize));
 227                 off += key.dsize;
 228                 ok1(!ntdb->io->twrite(ntdb, off, dbuf.dptr, dbuf.dsize));
 229
 230                 /* Adding another record should cause expansion. */
 231                 v = 3;
 232                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 233                 /* Should have created correct hash. */
 234                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 235                 /* Should not have located space in chain. */
 236                 ok1(h.table > NTDB_HASH_OFFSET);
 237                 ok1(h.table_size == 2);
 238                 ok1(h.bucket == 2);
 239                 ok1(h.old_val != 0);
 240
 241                 /* Should have lock on bucket 0 */
 242                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 243                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 244                 ok1((ntdb->flags & NTDB_NOLOCK)
 245                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 246
 247                 new_off = alloc(ntdb, key.dsize, dbuf.dsize,
 248                                 NTDB_USED_MAGIC, false);
 249                 ok1(!NTDB_OFF_IS_ERR(new_off2));
 250                 off = new_off + sizeof(struct ntdb_used_record);
 251                 ok1(!ntdb->io->twrite(ntdb, off, key.dptr, key.dsize));
 252                 off += key.dsize;
 253                 ok1(!ntdb->io->twrite(ntdb, off, dbuf.dptr, dbuf.dsize));
 254                 ok1(add_to_hash(ntdb, &h, new_off) == 0);
 255                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 256
 257                 /* Retrieve it and check. */
 258                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off);
 259                 /* Should have created correct hash. */
 260                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 261                 /* Should have appended to chain, bucket 2. */
 262                 ok1(h.table > NTDB_HASH_OFFSET);
 263                 ok1(h.table_size == 3);
 264                 ok1(h.bucket == 2);
 265
 266                 /* Should have lock on bucket 0 */
 267                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 268                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 269                 ok1((ntdb->flags & NTDB_NOLOCK)
 270                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 271                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 272
 273                 /* YA record: relocation. */
 274                 v = 4;
 275                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0);
 276                 /* Should have created correct hash. */
 277                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 278                 /* Should not have located space in chain. */
 279                 ok1(h.table > NTDB_HASH_OFFSET);
 280                 ok1(h.table_size == 3);
 281                 ok1(h.bucket == 3);
 282                 ok1(h.old_val != 0);
 283
 284                 /* Should have lock on bucket 0 */
 285                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 286                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 287                 ok1((ntdb->flags & NTDB_NOLOCK)
 288                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 289
 290                 new_off = alloc(ntdb, key.dsize, dbuf.dsize,
 291                                 NTDB_USED_MAGIC, false);
 292                 ok1(!NTDB_OFF_IS_ERR(new_off2));
 293                 off = new_off + sizeof(struct ntdb_used_record);
 294                 ok1(!ntdb->io->twrite(ntdb, off, key.dptr, key.dsize));
 295                 off += key.dsize;
 296                 ok1(!ntdb->io->twrite(ntdb, off, dbuf.dptr, dbuf.dsize));
 297                 ok1(add_to_hash(ntdb, &h, new_off) == 0);
 298                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 299
 300                 /* Retrieve it and check. */
 301                 ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off);
 302                 /* Should have created correct hash. */
 303                 ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize));
 304                 /* Should have appended to chain, bucket 2. */
 305                 ok1(h.table > NTDB_HASH_OFFSET);
 306                 ok1(h.table_size == 4);
 307                 ok1(h.bucket == 3);
 308
 309                 /* Should have lock on bucket 0 */
 310                 ok1((h.h & ((1 << ntdb->hash_bits)-1)) == 0);
 311                 ok1((ntdb->flags & NTDB_NOLOCK) || ntdb->file->num_lockrecs == 1);
 312                 ok1((ntdb->flags & NTDB_NOLOCK)
 313                     || ntdb->file->lockrecs[0].off == NTDB_HASH_LOCK_START);
 314                 ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0);
 315
 316                 ntdb_close(ntdb);
 317         }
 318
 319         ok1(tap_log_messages == 0);
 320         return exit_status();
 321 }