lib/tdb2/test/run-20-growhash.c

   1 #include "tdb2-source.h"
   2 #include "tap-interface.h"
   3 #include "logging.h"
   4
   5 static uint64_t myhash(const void *key, size_t len, uint64_t seed, void *priv)
   6 {
   7         return *(const uint64_t *)key;
   8 }
   9
  10 static void add_bits(uint64_t *val, unsigned new, unsigned new_bits,
  11                      unsigned *done)
  12 {
  13         *done += new_bits;
  14         *val |= ((uint64_t)new << (64 - *done));
  15 }
  16
  17 static uint64_t make_key(unsigned topgroup, unsigned topbucket,
  18                          unsigned subgroup1, unsigned subbucket1,
  19                          unsigned subgroup2, unsigned subbucket2)
  20 {
  21         uint64_t key = 0;
  22         unsigned done = 0;
  23
  24         add_bits(&key, topgroup, TDB_TOPLEVEL_HASH_BITS - TDB_HASH_GROUP_BITS,
  25                  &done);
  26         add_bits(&key, topbucket, TDB_HASH_GROUP_BITS, &done);
  27         add_bits(&key, subgroup1, TDB_SUBLEVEL_HASH_BITS - TDB_HASH_GROUP_BITS,
  28                  &done);
  29         add_bits(&key, subbucket1, TDB_HASH_GROUP_BITS, &done);
  30         add_bits(&key, subgroup2, TDB_SUBLEVEL_HASH_BITS - TDB_HASH_GROUP_BITS,
  31                  &done);
  32         add_bits(&key, subbucket2, TDB_HASH_GROUP_BITS, &done);
  33         return key;
  34 }
  35
  36 int main(int argc, char *argv[])
  37 {
  38         unsigned int i, j;
  39         struct tdb_context *tdb;
  40         uint64_t kdata;
  41         struct tdb_used_record rec;
  42         struct tdb_data key = { (unsigned char *)&kdata, sizeof(kdata) };
  43         struct tdb_data dbuf = { (unsigned char *)&kdata, sizeof(kdata) };
  44         union tdb_attribute hattr = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
  45                                                 .fn = myhash } };
  46         int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_NOMMAP,
  47                         TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT,
  48                         TDB_NOMMAP|TDB_CONVERT,
  49         };
  50
  51         hattr.base.next = &tap_log_attr;
  52
  53         plan_tests(sizeof(flags) / sizeof(flags[0])
  54                    * (9 + (20 + 2 * ((1 << TDB_HASH_GROUP_BITS) - 2))
  55                       * (1 << TDB_HASH_GROUP_BITS)) + 1);
  56         for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
  57                 struct hash_info h;
  58
  59                 tdb = tdb_open("run-20-growhash.tdb", flags[i],
  60                                O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
  61                 ok1(tdb);
  62                 if (!tdb)
  63                         continue;
  64
  65                 /* Fill a group. */
  66                 for (j = 0; j < (1 << TDB_HASH_GROUP_BITS); j++) {
  67                         kdata = make_key(0, j, 0, 0, 0, 0);
  68                         ok1(tdb_store(tdb, key, dbuf, TDB_INSERT) == 0);
  69                 }
  70                 ok1(tdb_check(tdb, NULL, NULL) == 0);
  71
  72                 /* Check first still exists. */
  73                 kdata = make_key(0, 0, 0, 0, 0, 0);
  74                 ok1(find_and_lock(tdb, key, F_RDLCK, &h, &rec, NULL) != 0);
  75                 /* Should have created correct hash. */
  76                 ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
  77                 /* Should have located space in group 0, bucket 0. */
  78                 ok1(h.group_start == offsetof(struct tdb_header, hashtable));
  79                 ok1(h.home_bucket == 0);
  80                 ok1(h.found_bucket == 0);
  81                 ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS);
  82                 /* Entire group should be full! */
  83                 for (j = 0; j < (1 << TDB_HASH_GROUP_BITS); j++)
  84                         ok1(h.group[j] != 0);
  85
  86                 ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
  87                                       F_RDLCK) == 0);
  88
  89                 /* Now, add one more to each should expand (that) bucket. */
  90                 for (j = 0; j < (1 << TDB_HASH_GROUP_BITS); j++) {
  91                         unsigned int k;
  92                         kdata = make_key(0, j, 0, 1, 0, 0);
  93                         ok1(tdb_store(tdb, key, dbuf, TDB_INSERT) == 0);
  94                         ok1(tdb_check(tdb, NULL, NULL) == 0);
  95
  96                         ok1(find_and_lock(tdb, key, F_RDLCK, &h, &rec, NULL));
  97                         /* Should have created correct hash. */
  98                         ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
  99                         /* Should have moved to subhash */
 100                         ok1(h.group_start >= sizeof(struct tdb_header));
 101                         ok1(h.home_bucket == 1);
 102                         ok1(h.found_bucket == 1);
 103                         ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS
 104                             + TDB_SUBLEVEL_HASH_BITS);
 105                         ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 106                                               F_RDLCK) == 0);
 107
 108                         /* Keep adding, make it expand again. */
 109                         for (k = 2; k < (1 << TDB_HASH_GROUP_BITS); k++) {
 110                                 kdata = make_key(0, j, 0, k, 0, 0);
 111                                 ok1(tdb_store(tdb, key, dbuf, TDB_INSERT) == 0);
 112                                 ok1(tdb_check(tdb, NULL, NULL) == 0);
 113                         }
 114
 115                         /* This should tip it over to sub-sub-hash. */
 116                         kdata = make_key(0, j, 0, 0, 0, 1);
 117                         ok1(tdb_store(tdb, key, dbuf, TDB_INSERT) == 0);
 118                         ok1(tdb_check(tdb, NULL, NULL) == 0);
 119
 120                         ok1(find_and_lock(tdb, key, F_RDLCK, &h, &rec, NULL));
 121                         /* Should have created correct hash. */
 122                         ok1(h.h == tdb_hash(tdb, key.dptr, key.dsize));
 123                         /* Should have moved to subhash */
 124                         ok1(h.group_start >= sizeof(struct tdb_header));
 125                         ok1(h.home_bucket == 1);
 126                         ok1(h.found_bucket == 1);
 127                         ok1(h.hash_used == TDB_TOPLEVEL_HASH_BITS
 128                             + TDB_SUBLEVEL_HASH_BITS + TDB_SUBLEVEL_HASH_BITS);
 129                         ok1(tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range,
 130                                               F_RDLCK) == 0);
 131                 }
 132                 tdb_close(tdb);
 133         }
 134
 135         ok1(tap_log_messages == 0);
 136         return exit_status();
 137 }