defs.h (10644B)
1 /* In a table with n slots (i.e., the table has room for n key-value pairs), 2 * the allocated table data consists of n metadata bytes followed by n/PAGE_LEN 3 * pages, where a page consists of PAGE_LEN keys followed by PAGE_LEN values. 4 * A meta byte is either EMPTY, TOMBSTONE, or the most significant hash byte of 5 * the key stored in the corresponding slot (roughly speaking; see hash1). When 6 * scanning the dict, we use SIMD to probe PROBE_LEN cells at once. Thus, the 7 * dict size n is always at least MAX(PROBE_LEN, PAGE_LEN). Actually, we also 8 * require the dict size to be at least R_CACHE_LINE_SIZE, so that the meta 9 * bytes occupy a whole number of cache lines, and so that pages are 10 * cache-aligned in the case where KSIZE * PAGE_LEN and VSIZE * PAGE_LEN 11 * are both multiples of R_CACHE_LINE_SIZE. */ 12 13 /* TODO: At some point, we should replace SSE2 with AVX2... or should we? 14 * Longer probe vectors means higher chance of conflicts within one probe 15 * vector, so maybe SSE2 is actually better. Before replacing SSE2 with AVX2, 16 * be sure to benchmark and do some statistical analysis. */ 17 #if defined(__GNUC__) && defined(R_HAVE_SSE2) 18 #include "../../simd.h" 19 #define USE_SIMD 1 20 #define PROBE_LEN 16u 21 #define PROBE_LEN_BITS 4u 22 #else 23 #define PROBE_LEN 8u 24 #define PROBE_LEN_BITS 3u 25 #endif 26 27 #define EMPTY 0u /* Must be 0. */ 28 #define TOMBSTONE 1u 29 #define MIN_HASH1 2u 30 31 #define ACCESS 0 32 #define INSERT 1 33 #define DELETE 2 34 35 static inline u8 36 TABLE_METHOD(hash1)(u64 h, u8 b) { 37 u64 h1 = h >> 56; 38 if (h1 < MIN_HASH1) h1 += MIN_HASH1; 39 return h1; 40 } 41 42 static inline bool 43 TABLE_METHOD(exceeds_lf)(u64 n, u8 b) { 44 /* Note that the math here is 64-bit to avoid overflow. */ 45 return TABLE_LF_DEN * n > TABLE_LF_NUM * (U64_C(1) << b); 46 } 47 48 static int 49 TABLE_METHOD(alloc_and_align)(void **mem, void **data, u8 b TABLE_SPEC_PARAM) { 50 usize len = USIZE_C(1) << b; 51 /* XXX: We assume KSIZE and VSIZE are small, so computing bytes_per_slot 52 * shouldn't overflow. */ 53 usize bytes_per_slot = 1u + TABLE_KSIZE + TABLE_VSIZE; 54 if (r_mul_will_overflow_(len, bytes_per_slot)) goto fail; 55 usize data_size = len * bytes_per_slot; 56 if (data_size > USIZE_MAX - (R_CACHE_LINE_SIZE - 1)) goto fail; 57 usize mem_size = (R_CACHE_LINE_SIZE - 1) + data_size; 58 *mem = TABLE_ALLOCZ(mem_size); 59 if (!*mem) goto fail; 60 *data = (void *)(((uptr)*mem + (R_CACHE_LINE_SIZE - 1)) 61 & -(uptr)R_CACHE_LINE_SIZE); 62 return 0; 63 64 fail: 65 errno = ENOMEM; 66 return -1; 67 } 68 69 /* grow_insert is a version of scan specialized for inserting while growing. 70 * See the comments in scan for explanation. */ 71 static void 72 TABLE_METHOD(grow_insert)(u8 b, u8 *meta, u8 *pages, void *k, void *v, u64 h TABLE_SPEC_PARAM) { 73 usize mvi_mask = (USIZE_C(1) << (b - PROBE_LEN_BITS)) - 1u; 74 75 usize h0 = h & mvi_mask; 76 u8 h1 = TABLE_METHOD(hash1)(h, b); 77 78 #ifdef USE_SIMD 79 v16u8 vempty = v16u8_fill(EMPTY); 80 #endif 81 82 usize insert_slot; 83 84 for (usize mvi = h0, jump = 1;; mvi = (mvi + jump) & mvi_mask, jump++) { 85 usize i = mvi * PROBE_LEN; 86 87 #ifdef USE_SIMD 88 v16u8 vmeta; memcpy(&vmeta, meta+i, sizeof vmeta); 89 u16 m0 = v16u8_msb(v16u8_cmpeq(vmeta, vempty)); 90 if (m0 != 0) { 91 insert_slot = i + r_ctz16(m0); 92 break; 93 } 94 #else 95 u64 vmeta = r_readl64(meta+i); 96 int j0 = r_rzb64(vmeta); 97 if (j0 != 8) { 98 insert_slot = i + j0; 99 break; 100 } 101 #endif 102 } 103 104 meta[insert_slot] = h1; 105 usize page_slot = insert_slot % TABLE_PAGE_LEN; 106 u8 *page = pages + (insert_slot - page_slot) * (TABLE_KSIZE + TABLE_VSIZE); 107 memcpy(page + page_slot * TABLE_KSIZE, k, TABLE_KSIZE); 108 memcpy(page + TABLE_PAGE_LEN * TABLE_KSIZE + page_slot * TABLE_VSIZE, v, TABLE_VSIZE); 109 } 110 111 static int 112 TABLE_METHOD(grow)(RTable *t TABLE_SPEC_PARAM) { 113 u8 oldb = t->b; 114 usize oldlen = USIZE_C(1) << oldb; 115 void *oldmem = t->mem; 116 u8 *oldmeta = t->data; 117 u8 *oldpages = (u8 *)t->data + oldlen; 118 119 u8 newb = oldb + 1; 120 ASSERT(newb < USIZE_BITS); 121 usize newlen = USIZE_C(1) << newb; 122 void *newmem, *newdata; 123 if (TABLE_METHOD(alloc_and_align)(&newmem, &newdata, newb TABLE_SPEC) < 0) 124 return -1; 125 u8 *newmeta = newdata; 126 u8 *newpages = (u8 *)newdata + newlen; 127 128 /* Rehash. */ 129 for (usize slot = 0; slot < oldlen; slot++) { 130 if (oldmeta[slot] < MIN_HASH1) continue; 131 usize page_slot = slot % TABLE_PAGE_LEN; 132 u8 *page = oldpages + (slot - page_slot) * (TABLE_KSIZE + TABLE_VSIZE); 133 void *k = page + page_slot * TABLE_KSIZE; 134 void *v = page + TABLE_PAGE_LEN * TABLE_KSIZE + page_slot * TABLE_VSIZE; 135 u64 h = TABLE_HASH(k, t->seed, TABLE_KSIZE); 136 TABLE_METHOD(grow_insert)(newb, newmeta, newpages, k, v, h TABLE_SPEC); 137 } 138 139 TABLE_FREE(oldmem); 140 141 t->b = newb; 142 t->ntombs = 0; 143 t->mem = newmem; 144 t->data = newdata; 145 146 return 0; 147 } 148 149 /* scan is inline, so that the mode argument becomes constant in all uses. */ 150 static inline int 151 TABLE_METHOD(scan)(RTable *t, void **v, void *k, u64 h, int mode TABLE_SPEC_PARAM) { 152 u8 *meta = t->data; 153 u8 *pages = (u8 *)t->data + (USIZE_C(1) << t->b); 154 155 usize mvi_mask = (USIZE_C(1) << (t->b - PROBE_LEN_BITS)) - 1u; 156 157 usize h0 = h & mvi_mask; 158 u8 h1 = TABLE_METHOD(hash1)(h, t->b); 159 160 #ifdef USE_SIMD 161 v16u8 vh1 = v16u8_fill(h1); 162 v16u8 vempty = v16u8_fill(EMPTY); 163 #else 164 u64 vh1; memset(&vh1, h1, sizeof vh1); 165 #endif 166 167 /* These variables should get optimized away when mode != INSERT. */ 168 bool insert_slot_found = false; 169 usize insert_slot; 170 bool insert_replacing_tomb; 171 172 /* mvi is the metadata vector index (where each metadata vector is a 173 * u8[PROBE_LEN]), and i is the corresponding index in the meta table. 174 * Note that mvi is increased quadratically. */ 175 for (usize mvi = h0, jump = 1;; mvi = (mvi + jump) & mvi_mask, jump++) { 176 usize i = mvi * PROBE_LEN; 177 178 /* We must load the metadata vector as little endian, so that low bits 179 * in the vector represent earlier slots in the table and hence 180 * ctz/rzb gives us earlier slots first. In the SIMD case, we know 181 * we're on x86, so a memcpy suffices. In the portable case, we use 182 * readl64, which does a byte swap on big endian machines. */ 183 #ifdef USE_SIMD 184 v16u8 vmeta; memcpy(&vmeta, meta+i, sizeof vmeta); 185 /* m is a bit array indicating where vmeta equals h1. Thus, ctz(m) is 186 * the least j such that meta[j] == h1 (provided m != 0). */ 187 for (u16 m = v16u8_msb(v16u8_cmpeq(vmeta, vh1)); m != 0; m &= m - 1) { 188 int j = r_ctz16(m); 189 #else 190 u64 vmeta = r_readl64(meta+i); 191 /* Initially, z has 0x00 exactly where vmeta has h1. Thus, we can use 192 * rzb64 on z to find the indices j of h1 in vmeta. After each 193 * iteration, we mask in an arbitrary bit into the jth byte so that 194 * the next iteration gets a different j. */ 195 u64 z = vmeta ^ vh1; 196 for (int j = r_rzb64(z); j != 8; z |= U64_C(1)<<(8*j), j = r_rzb64(z)) { 197 #endif 198 usize slot = i + j; 199 usize page_slot = slot % TABLE_PAGE_LEN; 200 u8 *page = pages + (slot - page_slot) * (TABLE_KSIZE + TABLE_VSIZE); 201 if likely (TABLE_EQ(page + page_slot * TABLE_KSIZE, k, TABLE_KSIZE)) { 202 if (mode == DELETE) { 203 /* If the probe vector contains an empty slot, then we 204 * don't need to insert a tombstone, and fewer tombstones 205 * means lower load factor. */ 206 #ifdef USE_SIMD 207 if (v16u8_msb(v16u8_cmpeq(vmeta, vempty)) != 0) { 208 #else 209 if (r_rzb64(vmeta) != 8) { 210 #endif 211 meta[slot] = EMPTY; 212 } else { 213 meta[slot] = TOMBSTONE; 214 t->ntombs += 1; 215 } 216 t->count -= 1; 217 } 218 *v = page + TABLE_PAGE_LEN * TABLE_KSIZE + page_slot * TABLE_VSIZE; 219 return 1; 220 } 221 } 222 223 /* The key is not in this probe vector. Search for an empty slot to 224 * determine if we need to check more probe vectors. */ 225 #ifdef USE_SIMD 226 u16 m0 = v16u8_msb(v16u8_cmpeq(vmeta, vempty)); 227 #else 228 int j0 = r_rzb64(vmeta); 229 #endif 230 231 /* When inserting, we need to remember the first empty slot or 232 * tombstone seen in case we don't find an existing slot with the 233 * given key. We prioritize replacing tombstones to decrease the 234 * load factor. */ 235 if (mode == INSERT && !insert_slot_found) { 236 #ifdef USE_SIMD 237 v16u8 vtomb = v16u8_fill(TOMBSTONE); 238 u16 m1 = v16u8_msb(v16u8_cmpeq(vmeta, vtomb)); 239 if (m1 != 0) { 240 insert_slot_found = true; 241 insert_slot = i + r_ctz16(m1); 242 insert_replacing_tomb = true; 243 } else if (m0 != 0) { 244 insert_slot_found = true; 245 insert_slot = i + r_ctz16(m0); 246 insert_replacing_tomb = false; 247 break; 248 } 249 #else 250 u64 vtomb; memset(&vtomb, TOMBSTONE, sizeof vtomb); 251 int j1 = r_rzb64(vmeta ^ vtomb); 252 if (j1 != 8) { 253 insert_slot_found = true; 254 insert_slot = i + j1; 255 insert_replacing_tomb = true; 256 } else if (j0 != 8) { 257 insert_slot_found = true; 258 insert_slot = i + j0; 259 insert_replacing_tomb = false; 260 break; 261 } 262 #endif 263 } 264 265 #ifdef USE_SIMD 266 if (m0 != 0) break; 267 #else 268 if (j0 != 8) break; 269 #endif 270 } 271 272 if (mode == INSERT) { 273 /* The key wasn't found, so insert in the first available slot found 274 * along the probe sequence. */ 275 ASSERT(insert_slot_found); 276 t->count += 1; 277 if (insert_replacing_tomb) t->ntombs -= 1; 278 meta[insert_slot] = h1; 279 usize page_slot = insert_slot % TABLE_PAGE_LEN; 280 u8 *page = pages + (insert_slot - page_slot) * (TABLE_KSIZE + TABLE_VSIZE); 281 memcpy(page + page_slot * TABLE_KSIZE, k, TABLE_KSIZE); 282 *v = page + TABLE_PAGE_LEN * TABLE_KSIZE + page_slot * TABLE_VSIZE; 283 } 284 285 return 0; 286 } 287 288 int 289 TABLE_METHOD(init)(RTable *t, usize hint TABLE_SPEC_PARAM) { 290 memset(t, 0, sizeof *t); 291 292 /* Impose maximum on hint to prevent overflow and the following while 293 * loop from being infinite. See exceeds_lf. */ 294 hint = MIN(hint, (U64_MAX / TABLE_LF_DEN) >> 1); 295 u8 b = MAX(R_CACHE_LINE_BITS, PROBE_LEN_BITS); 296 b = MAX(b, TABLE_PAGE_LEN_BITS); 297 while (TABLE_METHOD(exceeds_lf)(hint, b)) b += 1; 298 ASSERT(b < USIZE_BITS); 299 t->b = b; 300 301 if (TABLE_METHOD(alloc_and_align)(&t->mem, &t->data, b TABLE_SPEC) < 0) 302 return -1; 303 304 t->seed = r_prand64(); 305 306 return 0; 307 } 308 309 int 310 TABLE_METHOD(acc)(RTable *t, void **v, void *k, u64 h TABLE_SPEC_PARAM) { 311 return TABLE_METHOD(scan)(t, v, k, h, ACCESS TABLE_SPEC); 312 } 313 314 int 315 TABLE_METHOD(ins)(RTable *t, void **v, void *k, u64 h TABLE_SPEC_PARAM) { 316 if (TABLE_METHOD(exceeds_lf)(t->count + t->ntombs, t->b)) { 317 if (TABLE_METHOD(grow)(t TABLE_SPEC) < 0) return -1; 318 } 319 return TABLE_METHOD(scan)(t, v, k, h, INSERT TABLE_SPEC); 320 } 321 322 int 323 TABLE_METHOD(del)(RTable *t, void **v, void *k, u64 h TABLE_SPEC_PARAM) { 324 return TABLE_METHOD(scan)(t, v, k, h, DELETE TABLE_SPEC); 325 } 326 327 void 328 TABLE_METHOD(clr)(RTable *t TABLE_SPEC_PARAM) { 329 memset(t->data, EMPTY, USIZE_C(1) << t->b); 330 t->count = 0; 331 t->ntombs = 0; 332 333 /* Re-seed to prevent some attacks. */ 334 t->seed = r_prand64(); 335 } 336 337 #undef DELETE 338 #undef INSERT 339 #undef ACCESS 340 #undef MIN_HASH1 341 #undef TOMBSTONE 342 #undef EMPTY 343 #undef PROBE_LEN_BITS 344 #undef PROBE_LEN 345 #undef USE_SIMD