Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * dshash.c
4 : : * Concurrent hash tables backed by dynamic shared memory areas.
5 : : *
6 : : * This is an open hashing hash table, with a linked list at each table
7 : : * entry. It supports dynamic resizing, as required to prevent the linked
8 : : * lists from growing too long on average. Currently, only growing is
9 : : * supported: the hash table never becomes smaller.
10 : : *
11 : : * To deal with concurrency, it has a fixed size set of partitions, each of
12 : : * which is independently locked. Each bucket maps to a partition; so insert,
13 : : * find and iterate operations normally only acquire one lock. Therefore,
14 : : * good concurrency is achieved whenever such operations don't collide at the
15 : : * lock partition level. However, when a resize operation begins, all
16 : : * partition locks must be acquired simultaneously for a brief period. This
17 : : * is only expected to happen a small number of times until a stable size is
18 : : * found, since growth is geometric.
19 : : *
20 : : * Future versions may support iterators and incremental resizing; for now
21 : : * the implementation is minimalist.
22 : : *
23 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
24 : : * Portions Copyright (c) 1994, Regents of the University of California
25 : : *
26 : : * IDENTIFICATION
27 : : * src/backend/lib/dshash.c
28 : : *
29 : : *-------------------------------------------------------------------------
30 : : */
31 : :
32 : : #include "postgres.h"
33 : :
34 : : #include <limits.h>
35 : :
36 : : #include "common/hashfn.h"
37 : : #include "lib/dshash.h"
38 : : #include "storage/lwlock.h"
39 : : #include "utils/dsa.h"
40 : :
41 : : /*
42 : : * An item in the hash table. This wraps the user's entry object in an
43 : : * envelop that holds a pointer back to the bucket and a pointer to the next
44 : : * item in the bucket.
45 : : */
46 : : struct dshash_table_item
47 : : {
48 : : /* The next item in the same bucket. */
49 : : dsa_pointer next;
50 : : /* The hashed key, to avoid having to recompute it. */
51 : : dshash_hash hash;
52 : : /* The user's entry object follows here. See ENTRY_FROM_ITEM(item). */
53 : : };
54 : :
55 : : /*
56 : : * The number of partitions for locking purposes. This is set to match
57 : : * NUM_BUFFER_PARTITIONS for now, on the basis that whatever's good enough for
58 : : * the buffer pool must be good enough for any other purpose. This could
59 : : * become a runtime parameter in future.
60 : : */
61 : : #define DSHASH_NUM_PARTITIONS_LOG2 7
62 : : #define DSHASH_NUM_PARTITIONS (1 << DSHASH_NUM_PARTITIONS_LOG2)
63 : :
64 : : /* A magic value used to identify our hash tables. */
65 : : #define DSHASH_MAGIC 0x75ff6a20
66 : :
67 : : /*
68 : : * Tracking information for each lock partition. Initially, each partition
69 : : * corresponds to one bucket, but each time the hash table grows, the buckets
70 : : * covered by each partition split so the number of buckets covered doubles.
71 : : *
72 : : * We might want to add padding here so that each partition is on a different
73 : : * cache line, but doing so would bloat this structure considerably.
74 : : */
75 : : typedef struct dshash_partition
76 : : {
77 : : LWLock lock; /* Protects all buckets in this partition. */
78 : : size_t count; /* # of items in this partition's buckets */
79 : : } dshash_partition;
80 : :
81 : : /*
82 : : * The head object for a hash table. This will be stored in dynamic shared
83 : : * memory.
84 : : */
85 : : typedef struct dshash_table_control
86 : : {
87 : : dshash_table_handle handle;
88 : : uint32 magic;
89 : : dshash_partition partitions[DSHASH_NUM_PARTITIONS];
90 : : int lwlock_tranche_id;
91 : :
92 : : /*
93 : : * The following members are written to only when ALL partitions locks are
94 : : * held. They can be read when any one partition lock is held.
95 : : */
96 : :
97 : : /* Number of buckets expressed as power of 2 (8 = 256 buckets). */
98 : : size_t size_log2; /* log2(number of buckets) */
99 : : dsa_pointer buckets; /* current bucket array */
100 : : } dshash_table_control;
101 : :
102 : : /*
103 : : * Per-backend state for a dynamic hash table.
104 : : */
105 : : struct dshash_table
106 : : {
107 : : dsa_area *area; /* Backing dynamic shared memory area. */
108 : : dshash_parameters params; /* Parameters. */
109 : : void *arg; /* User-supplied data pointer. */
110 : : dshash_table_control *control; /* Control object in DSM. */
111 : : dsa_pointer *buckets; /* Current bucket pointers in DSM. */
112 : : size_t size_log2; /* log2(number of buckets) */
113 : : };
114 : :
115 : : /* Given a pointer to an item, find the entry (user data) it holds. */
116 : : #define ENTRY_FROM_ITEM(item) \
117 : : ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))
118 : :
119 : : /* Given a pointer to an entry, find the item that holds it. */
120 : : #define ITEM_FROM_ENTRY(entry) \
121 : : ((dshash_table_item *)((char *)(entry) - \
122 : : MAXALIGN(sizeof(dshash_table_item))))
123 : :
124 : : /* How many resize operations (bucket splits) have there been? */
125 : : #define NUM_SPLITS(size_log2) \
126 : : (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)
127 : :
128 : : /* How many buckets are there in a given size? */
129 : : #define NUM_BUCKETS(size_log2) \
130 : : (((size_t) 1) << (size_log2))
131 : :
132 : : /* How many buckets are there in each partition at a given size? */
133 : : #define BUCKETS_PER_PARTITION(size_log2) \
134 : : (((size_t) 1) << NUM_SPLITS(size_log2))
135 : :
136 : : /* Max entries before we need to grow. Half + quarter = 75% load factor. */
137 : : #define MAX_COUNT_PER_PARTITION(hash_table) \
138 : : (BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
139 : : BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)
140 : :
141 : : /* Choose partition based on the highest order bits of the hash. */
142 : : #define PARTITION_FOR_HASH(hash) \
143 : : (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))
144 : :
145 : : /*
146 : : * Find the bucket index for a given hash and table size. Each time the table
147 : : * doubles in size, the appropriate bucket for a given hash value doubles and
148 : : * possibly adds one, depending on the newly revealed bit, so that all buckets
149 : : * are split.
150 : : */
151 : : #define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2) \
152 : : (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))
153 : :
154 : : /* The index of the first bucket in a given partition. */
155 : : #define BUCKET_INDEX_FOR_PARTITION(partition, size_log2) \
156 : : ((partition) << NUM_SPLITS(size_log2))
157 : :
158 : : /* Choose partition based on bucket index. */
159 : : #define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2) \
160 : : ((bucket_idx) >> NUM_SPLITS(size_log2))
161 : :
162 : : /* The head of the active bucket for a given hash value (lvalue). */
163 : : #define BUCKET_FOR_HASH(hash_table, hash) \
164 : : (hash_table->buckets[ \
165 : : BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, \
166 : : hash_table->size_log2)])
167 : :
168 : : static void delete_item(dshash_table *hash_table,
169 : : dshash_table_item *item);
170 : : static bool resize(dshash_table *hash_table, size_t new_size_log2,
171 : : int flags);
172 : : static inline void ensure_valid_bucket_pointers(dshash_table *hash_table);
173 : : static inline dshash_table_item *find_in_bucket(dshash_table *hash_table,
174 : : const void *key,
175 : : dsa_pointer item_pointer);
176 : : static void insert_item_into_bucket(dshash_table *hash_table,
177 : : dsa_pointer item_pointer,
178 : : dshash_table_item *item,
179 : : dsa_pointer *bucket);
180 : : static dshash_table_item *insert_into_bucket(dshash_table *hash_table,
181 : : const void *key,
182 : : dsa_pointer *bucket,
183 : : int flags);
184 : : static bool delete_key_from_bucket(dshash_table *hash_table,
185 : : const void *key,
186 : : dsa_pointer *bucket_head);
187 : : static bool delete_item_from_bucket(dshash_table *hash_table,
188 : : dshash_table_item *item,
189 : : dsa_pointer *bucket_head);
190 : : static inline dshash_hash hash_key(dshash_table *hash_table, const void *key);
191 : : static inline bool equal_keys(dshash_table *hash_table,
192 : : const void *a, const void *b);
193 : : static inline void copy_key(dshash_table *hash_table, void *dest,
194 : : const void *src);
195 : :
196 : : #define PARTITION_LOCK(hash_table, i) \
197 : : (&(hash_table)->control->partitions[(i)].lock)
198 : :
199 : : #define ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table) \
200 : : Assert(!LWLockAnyHeldByMe(&(hash_table)->control->partitions[0].lock, \
201 : : DSHASH_NUM_PARTITIONS, sizeof(dshash_partition)))
202 : :
203 : : /*
204 : : * Create a new hash table backed by the given dynamic shared area, with the
205 : : * given parameters. The returned object is allocated in backend-local memory
206 : : * using the current MemoryContext. 'arg' will be passed through to the
207 : : * compare, hash, and copy functions.
208 : : */
209 : : dshash_table *
210 : 1613 : dshash_create(dsa_area *area, const dshash_parameters *params, void *arg)
211 : : {
212 : : dshash_table *hash_table;
213 : : dsa_pointer control;
214 : :
215 : : /* Allocate the backend-local object representing the hash table. */
216 : 1613 : hash_table = palloc_object(dshash_table);
217 : :
218 : : /* Allocate the control object in shared memory. */
219 : 1613 : control = dsa_allocate(area, sizeof(dshash_table_control));
220 : :
221 : : /* Set up the local and shared hash table structs. */
222 : 1613 : hash_table->area = area;
223 : 1613 : hash_table->params = *params;
224 : 1613 : hash_table->arg = arg;
225 : 1613 : hash_table->control = dsa_get_address(area, control);
226 : 1613 : hash_table->control->handle = control;
227 : 1613 : hash_table->control->magic = DSHASH_MAGIC;
228 : 1613 : hash_table->control->lwlock_tranche_id = params->tranche_id;
229 : :
230 : : /* Set up the array of lock partitions. */
231 : : {
232 : 1613 : dshash_partition *partitions = hash_table->control->partitions;
233 : 1613 : int tranche_id = hash_table->control->lwlock_tranche_id;
234 : : int i;
235 : :
236 [ + + ]: 208077 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
237 : : {
238 : 206464 : LWLockInitialize(&partitions[i].lock, tranche_id);
239 : 206464 : partitions[i].count = 0;
240 : : }
241 : : }
242 : :
243 : : /*
244 : : * Set up the initial array of buckets. Our initial size is the same as
245 : : * the number of partitions.
246 : : */
247 : 1613 : hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
248 : 3226 : hash_table->control->buckets =
249 : 1613 : dsa_allocate_extended(area,
250 : : sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
251 : : DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
252 [ - + ]: 1613 : if (!DsaPointerIsValid(hash_table->control->buckets))
253 : : {
254 : 0 : dsa_free(area, control);
255 [ # # ]: 0 : ereport(ERROR,
256 : : (errcode(ERRCODE_OUT_OF_MEMORY),
257 : : errmsg("out of memory"),
258 : : errdetail("Failed on DSA request of size %zu.",
259 : : sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
260 : : }
261 : 3226 : hash_table->buckets = dsa_get_address(area,
262 : 1613 : hash_table->control->buckets);
263 : 1613 : hash_table->size_log2 = hash_table->control->size_log2;
264 : :
265 : 1613 : return hash_table;
266 : : }
267 : :
268 : : /*
269 : : * Attach to an existing hash table using a handle. The returned object is
270 : : * allocated in backend-local memory using the current MemoryContext. 'arg'
271 : : * will be passed through to the compare and hash functions.
272 : : */
273 : : dshash_table *
274 : 29562 : dshash_attach(dsa_area *area, const dshash_parameters *params,
275 : : dshash_table_handle handle, void *arg)
276 : : {
277 : : dshash_table *hash_table;
278 : : dsa_pointer control;
279 : :
280 : : /* Allocate the backend-local object representing the hash table. */
281 : 29562 : hash_table = palloc_object(dshash_table);
282 : :
283 : : /* Find the control object in shared memory. */
284 : 29562 : control = handle;
285 : :
286 : : /* Set up the local hash table struct. */
287 : 29562 : hash_table->area = area;
288 : 29562 : hash_table->params = *params;
289 : 29562 : hash_table->arg = arg;
290 : 29562 : hash_table->control = dsa_get_address(area, control);
291 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
292 : :
293 : : /*
294 : : * These will later be set to the correct values by
295 : : * ensure_valid_bucket_pointers(), at which time we'll be holding a
296 : : * partition lock for interlocking against concurrent resizing.
297 : : */
298 : 29562 : hash_table->buckets = NULL;
299 : 29562 : hash_table->size_log2 = 0;
300 : :
301 : 29562 : return hash_table;
302 : : }
303 : :
304 : : /*
305 : : * Detach from a hash table. This frees backend-local resources associated
306 : : * with the hash table, but the hash table will continue to exist until it is
307 : : * either explicitly destroyed (by a backend that is still attached to it), or
308 : : * the area that backs it is returned to the operating system.
309 : : */
310 : : void
311 : 30655 : dshash_detach(dshash_table *hash_table)
312 : : {
313 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
314 : :
315 : : /* The hash table may have been destroyed. Just free local memory. */
316 : 30655 : pfree(hash_table);
317 : 30655 : }
318 : :
319 : : /*
320 : : * Destroy a hash table, returning all memory to the area. The caller must be
321 : : * certain that no other backend will attempt to access the hash table before
322 : : * calling this function. Other backend must explicitly call dshash_detach to
323 : : * free up backend-local memory associated with the hash table. The backend
324 : : * that calls dshash_destroy must not call dshash_detach.
325 : : */
326 : : void
327 : 0 : dshash_destroy(dshash_table *hash_table)
328 : : {
329 : : size_t size;
330 : : size_t i;
331 : :
332 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
333 : 0 : ensure_valid_bucket_pointers(hash_table);
334 : :
335 : : /* Free all the entries. */
336 : 0 : size = NUM_BUCKETS(hash_table->size_log2);
337 [ # # ]: 0 : for (i = 0; i < size; ++i)
338 : : {
339 : 0 : dsa_pointer item_pointer = hash_table->buckets[i];
340 : :
341 [ # # ]: 0 : while (DsaPointerIsValid(item_pointer))
342 : : {
343 : : dshash_table_item *item;
344 : : dsa_pointer next_item_pointer;
345 : :
346 : 0 : item = dsa_get_address(hash_table->area, item_pointer);
347 : 0 : next_item_pointer = item->next;
348 : 0 : dsa_free(hash_table->area, item_pointer);
349 : 0 : item_pointer = next_item_pointer;
350 : : }
351 : : }
352 : :
353 : : /*
354 : : * Vandalize the control block to help catch programming errors where
355 : : * other backends access the memory formerly occupied by this hash table.
356 : : */
357 : 0 : hash_table->control->magic = 0;
358 : :
359 : : /* Free the active table and control object. */
360 : 0 : dsa_free(hash_table->area, hash_table->control->buckets);
361 : 0 : dsa_free(hash_table->area, hash_table->control->handle);
362 : :
363 : 0 : pfree(hash_table);
364 : 0 : }
365 : :
366 : : /*
367 : : * Get the DSA area used by this hash table.
368 : : */
369 : : dsa_area *
370 : 0 : dshash_get_dsa_area(dshash_table *hash_table)
371 : : {
372 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
373 : :
374 : 0 : return hash_table->area;
375 : : }
376 : :
377 : : /*
378 : : * Get a handle that can be used by other processes to attach to this hash
379 : : * table.
380 : : */
381 : : dshash_table_handle
382 : 1613 : dshash_get_hash_table_handle(dshash_table *hash_table)
383 : : {
384 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
385 : :
386 : 1613 : return hash_table->control->handle;
387 : : }
388 : :
389 : : /*
390 : : * Look up an entry, given a key. Returns a pointer to an entry if one can be
391 : : * found with the given key. Returns NULL if the key is not found. If a
392 : : * non-NULL value is returned, the entry is locked and must be released by
393 : : * calling dshash_release_lock. If an error is raised before
394 : : * dshash_release_lock is called, the lock will be released automatically, but
395 : : * the caller must take care to ensure that the entry is not left corrupted.
396 : : * The lock mode is either shared or exclusive depending on 'exclusive'.
397 : : *
398 : : * The caller must not hold a lock already.
399 : : *
400 : : * Note that the lock held is in fact an LWLock, so interrupts will be held on
401 : : * return from this function, and not resumed until dshash_release_lock is
402 : : * called. It is a very good idea for the caller to release the lock quickly.
403 : : */
404 : : void *
405 : 1403229 : dshash_find(dshash_table *hash_table, const void *key, bool exclusive)
406 : : {
407 : : dshash_hash hash;
408 : : size_t partition;
409 : : dshash_table_item *item;
410 : :
411 : 1403229 : hash = hash_key(hash_table, key);
412 : 1403229 : partition = PARTITION_FOR_HASH(hash);
413 : :
414 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
415 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
416 : :
417 : 1403229 : LWLockAcquire(PARTITION_LOCK(hash_table, partition),
418 : 1403229 : exclusive ? LW_EXCLUSIVE : LW_SHARED);
419 : 1403229 : ensure_valid_bucket_pointers(hash_table);
420 : :
421 : : /* Search the active bucket. */
422 : 1403229 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
423 : :
424 [ + + ]: 1403229 : if (!item)
425 : : {
426 : : /* Not found. */
427 : 287145 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
428 : 287145 : return NULL;
429 : : }
430 : : else
431 : : {
432 : : /* The caller will free the lock by calling dshash_release_lock. */
433 : 1116084 : return ENTRY_FROM_ITEM(item);
434 : : }
435 : : }
436 : :
437 : : /*
438 : : * Find an existing entry in a dshash_table, or insert a new one.
439 : : *
440 : : * DSHASH_INSERT_NO_OOM causes this function to return NULL when no memory is
441 : : * available for the new entry. Otherwise, such allocations will result in
442 : : * an ERROR.
443 : : *
444 : : * Any entry returned by this function is exclusively locked, and the caller
445 : : * must release that lock using dshash_release_lock. Notes above dshash_find()
446 : : * regarding locking and error handling equally apply here.
447 : : *
448 : : * On return, *found is set to true if an existing entry was found in the
449 : : * hash table, and otherwise false.
450 : : *
451 : : */
452 : : void *
453 : 401814 : dshash_find_or_insert_extended(dshash_table *hash_table,
454 : : const void *key,
455 : : bool *found,
456 : : int flags)
457 : : {
458 : : dshash_hash hash;
459 : : size_t partition_index;
460 : : dshash_partition *partition;
461 : : dshash_table_item *item;
462 : :
463 : 401814 : hash = hash_key(hash_table, key);
464 : 401814 : partition_index = PARTITION_FOR_HASH(hash);
465 : 401814 : partition = &hash_table->control->partitions[partition_index];
466 : :
467 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
468 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
469 : :
470 : 405503 : restart:
471 : 405503 : LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
472 : : LW_EXCLUSIVE);
473 : 405503 : ensure_valid_bucket_pointers(hash_table);
474 : :
475 : : /* Search the active bucket. */
476 : 405503 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
477 : :
478 [ + + ]: 405503 : if (item)
479 : 291 : *found = true;
480 : : else
481 : : {
482 : 405212 : *found = false;
483 : :
484 : : /* Check if we are getting too full. */
485 [ + + ]: 405212 : if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
486 : : {
487 : : /*
488 : : * The load factor (= keys / buckets) for all buckets protected by
489 : : * this partition is > 0.75. Presumably the same applies
490 : : * generally across the whole hash table (though we don't attempt
491 : : * to track that directly to avoid contention on some kind of
492 : : * central counter; we just assume that this partition is
493 : : * representative). This is a good time to resize.
494 : : *
495 : : * Give up our existing lock first, because resizing needs to
496 : : * reacquire all the locks in the right order to avoid deadlocks.
497 : : */
498 : 3689 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
499 [ - + ]: 3689 : if (!resize(hash_table, hash_table->size_log2 + 1, flags))
500 : : {
501 : : Assert((flags & DSHASH_INSERT_NO_OOM) != 0);
502 : 0 : return NULL;
503 : : }
504 : :
505 : 3689 : goto restart;
506 : : }
507 : :
508 : : /* Finally we can try to insert the new item. */
509 : 401523 : item = insert_into_bucket(hash_table, key,
510 : 401523 : &BUCKET_FOR_HASH(hash_table, hash),
511 : : flags);
512 [ - + ]: 401523 : if (item == NULL)
513 : : {
514 : : Assert((flags & DSHASH_INSERT_NO_OOM) != 0);
515 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
516 : 0 : return NULL;
517 : : }
518 : 401523 : item->hash = hash;
519 : : /* Adjust per-lock-partition counter for load factor knowledge. */
520 : 401523 : ++partition->count;
521 : : }
522 : :
523 : : /* The caller must release the lock with dshash_release_lock. */
524 : 401814 : return ENTRY_FROM_ITEM(item);
525 : : }
526 : :
527 : : /*
528 : : * Remove an entry by key. Returns true if the key was found and the
529 : : * corresponding entry was removed.
530 : : *
531 : : * To delete an entry that you already have a pointer to, see
532 : : * dshash_delete_entry.
533 : : */
534 : : bool
535 : 293 : dshash_delete_key(dshash_table *hash_table, const void *key)
536 : : {
537 : : dshash_hash hash;
538 : : size_t partition;
539 : : bool found;
540 : :
541 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
542 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
543 : :
544 : 293 : hash = hash_key(hash_table, key);
545 : 293 : partition = PARTITION_FOR_HASH(hash);
546 : :
547 : 293 : LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
548 : 293 : ensure_valid_bucket_pointers(hash_table);
549 : :
550 [ + + ]: 293 : if (delete_key_from_bucket(hash_table, key,
551 : 293 : &BUCKET_FOR_HASH(hash_table, hash)))
552 : : {
553 : : Assert(hash_table->control->partitions[partition].count > 0);
554 : 145 : found = true;
555 : 145 : --hash_table->control->partitions[partition].count;
556 : : }
557 : : else
558 : 148 : found = false;
559 : :
560 : 293 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
561 : :
562 : 293 : return found;
563 : : }
564 : :
565 : : /*
566 : : * Remove an entry. The entry must already be exclusively locked, and must
567 : : * have been obtained by dshash_find or dshash_find_or_insert. Note that this
568 : : * function releases the lock just like dshash_release_lock.
569 : : *
570 : : * To delete an entry by key, see dshash_delete_key.
571 : : */
572 : : void
573 : 68194 : dshash_delete_entry(dshash_table *hash_table, void *entry)
574 : : {
575 : 68194 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
576 : 68194 : size_t partition = PARTITION_FOR_HASH(item->hash);
577 : :
578 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
579 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
580 : : LW_EXCLUSIVE));
581 : :
582 : 68194 : delete_item(hash_table, item);
583 : 68194 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
584 : 68194 : }
585 : :
586 : : /*
587 : : * Unlock an entry which was locked by dshash_find or dshash_find_or_insert.
588 : : */
589 : : void
590 : 1449703 : dshash_release_lock(dshash_table *hash_table, void *entry)
591 : : {
592 : 1449703 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
593 : 1449703 : size_t partition_index = PARTITION_FOR_HASH(item->hash);
594 : :
595 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
596 : :
597 : 1449703 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
598 : 1449703 : }
599 : :
600 : : /*
601 : : * A compare function that forwards to memcmp.
602 : : */
603 : : int
604 : 678 : dshash_memcmp(const void *a, const void *b, size_t size, void *arg)
605 : : {
606 : 678 : return memcmp(a, b, size);
607 : : }
608 : :
609 : : /*
610 : : * A hash function that forwards to tag_hash.
611 : : */
612 : : dshash_hash
613 : 1220 : dshash_memhash(const void *v, size_t size, void *arg)
614 : : {
615 : 1220 : return tag_hash(v, size);
616 : : }
617 : :
618 : : /*
619 : : * A copy function that forwards to memcpy.
620 : : */
621 : : void
622 : 401482 : dshash_memcpy(void *dest, const void *src, size_t size, void *arg)
623 : : {
624 : 401482 : (void) memcpy(dest, src, size);
625 : 401482 : }
626 : :
627 : : /*
628 : : * A compare function that forwards to strcmp.
629 : : */
630 : : int
631 : 224 : dshash_strcmp(const void *a, const void *b, size_t size, void *arg)
632 : : {
633 : : Assert(strlen((const char *) a) < size);
634 : : Assert(strlen((const char *) b) < size);
635 : :
636 : 224 : return strcmp((const char *) a, (const char *) b);
637 : : }
638 : :
639 : : /*
640 : : * A hash function that forwards to string_hash.
641 : : */
642 : : dshash_hash
643 : 270 : dshash_strhash(const void *v, size_t size, void *arg)
644 : : {
645 : : Assert(strlen((const char *) v) < size);
646 : :
647 : 270 : return string_hash((const char *) v, size);
648 : : }
649 : :
650 : : /*
651 : : * A copy function that forwards to strcpy.
652 : : */
653 : : void
654 : 41 : dshash_strcpy(void *dest, const void *src, size_t size, void *arg)
655 : : {
656 : : Assert(strlen((const char *) src) < size);
657 : :
658 : 41 : (void) strcpy((char *) dest, (const char *) src);
659 : 41 : }
660 : :
661 : : /*
662 : : * Sequentially scan through dshash table and return all the elements one by
663 : : * one, return NULL when all elements have been returned.
664 : : *
665 : : * dshash_seq_term needs to be called when a scan finished. The caller may
666 : : * delete returned elements midst of a scan by using dshash_delete_current()
667 : : * if exclusive = true.
668 : : */
669 : : void
670 : 1187 : dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table,
671 : : bool exclusive)
672 : : {
673 : 1187 : status->hash_table = hash_table;
674 : 1187 : status->curbucket = 0;
675 : 1187 : status->nbuckets = 0;
676 : 1187 : status->curitem = NULL;
677 : 1187 : status->pnextitem = InvalidDsaPointer;
678 : 1187 : status->curpartition = -1;
679 : 1187 : status->exclusive = exclusive;
680 : 1187 : }
681 : :
682 : : /*
683 : : * Returns the next element.
684 : : *
685 : : * Returned elements are locked and the caller may not release the lock. It is
686 : : * released by future calls to dshash_seq_next() or dshash_seq_term().
687 : : */
688 : : void *
689 : 318443 : dshash_seq_next(dshash_seq_status *status)
690 : : {
691 : : dsa_pointer next_item_pointer;
692 : :
693 : : /*
694 : : * Not yet holding any partition locks. Need to determine the size of the
695 : : * hash table, it could have been resized since we were looking last.
696 : : * Since we iterate in partition order, we can start by unconditionally
697 : : * lock partition 0.
698 : : *
699 : : * Once we hold the lock, no resizing can happen until the scan ends. So
700 : : * we don't need to repeatedly call ensure_valid_bucket_pointers().
701 : : */
702 [ + + ]: 318443 : if (status->curpartition == -1)
703 : : {
704 : : Assert(status->curbucket == 0);
705 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(status->hash_table);
706 : :
707 : 1187 : status->curpartition = 0;
708 : :
709 : 1187 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
710 : : status->curpartition),
711 : 1187 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
712 : :
713 : 1187 : ensure_valid_bucket_pointers(status->hash_table);
714 : :
715 : 1187 : status->nbuckets =
716 : 1187 : NUM_BUCKETS(status->hash_table->control->size_log2);
717 : 1187 : next_item_pointer = status->hash_table->buckets[status->curbucket];
718 : : }
719 : : else
720 : 317256 : next_item_pointer = status->pnextitem;
721 : :
722 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(status->hash_table,
723 : : status->curpartition),
724 : : status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
725 : :
726 : : /* Move to the next bucket if we finished the current bucket */
727 [ + + ]: 2011336 : while (!DsaPointerIsValid(next_item_pointer))
728 : : {
729 : : int next_partition;
730 : :
731 [ + + ]: 1694080 : if (++status->curbucket >= status->nbuckets)
732 : : {
733 : : /* all buckets have been scanned. finish. */
734 : 1187 : return NULL;
735 : : }
736 : :
737 : : /* Check if move to the next partition */
738 : 1692893 : next_partition =
739 : 1692893 : PARTITION_FOR_BUCKET_INDEX(status->curbucket,
740 : : status->hash_table->size_log2);
741 : :
742 [ + + ]: 1692893 : if (status->curpartition != next_partition)
743 : : {
744 : : /*
745 : : * Move to the next partition. Lock the next partition then
746 : : * release the current, not in the reverse order to avoid
747 : : * concurrent resizing. Avoid dead lock by taking lock in the
748 : : * same order with resize().
749 : : */
750 : 150749 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
751 : : next_partition),
752 : 150749 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
753 : 150749 : LWLockRelease(PARTITION_LOCK(status->hash_table,
754 : : status->curpartition));
755 : 150749 : status->curpartition = next_partition;
756 : : }
757 : :
758 : 1692893 : next_item_pointer = status->hash_table->buckets[status->curbucket];
759 : : }
760 : :
761 : 317256 : status->curitem =
762 : 317256 : dsa_get_address(status->hash_table->area, next_item_pointer);
763 : :
764 : : /*
765 : : * The caller may delete the item. Store the next item in case of
766 : : * deletion.
767 : : */
768 : 317256 : status->pnextitem = status->curitem->next;
769 : :
770 : 317256 : return ENTRY_FROM_ITEM(status->curitem);
771 : : }
772 : :
773 : : /*
774 : : * Terminates the seqscan and release all locks.
775 : : *
776 : : * Needs to be called after finishing or when exiting a seqscan.
777 : : */
778 : : void
779 : 1187 : dshash_seq_term(dshash_seq_status *status)
780 : : {
781 [ + - ]: 1187 : if (status->curpartition >= 0)
782 : 1187 : LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
783 : 1187 : }
784 : :
785 : : /*
786 : : * Remove the current entry of the seq scan.
787 : : */
788 : : void
789 : 6099 : dshash_delete_current(dshash_seq_status *status)
790 : : {
791 : 6099 : dshash_table *hash_table = status->hash_table;
792 : 6099 : dshash_table_item *item = status->curitem;
793 : : size_t partition PG_USED_FOR_ASSERTS_ONLY;
794 : :
795 : 6099 : partition = PARTITION_FOR_HASH(item->hash);
796 : :
797 : : Assert(status->exclusive);
798 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
799 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
800 : : LW_EXCLUSIVE));
801 : :
802 : 6099 : delete_item(hash_table, item);
803 : 6099 : }
804 : :
805 : : /*
806 : : * Print debugging information about the internal state of the hash table to
807 : : * stderr. The caller must hold no partition locks.
808 : : */
809 : : void
810 : 0 : dshash_dump(dshash_table *hash_table)
811 : : {
812 : : size_t i;
813 : : size_t j;
814 : :
815 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
816 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
817 : :
818 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
819 : : {
820 : : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
821 : 0 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
822 : : }
823 : :
824 : 0 : ensure_valid_bucket_pointers(hash_table);
825 : :
826 : 0 : fprintf(stderr,
827 : 0 : "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
828 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
829 : : {
830 : 0 : dshash_partition *partition = &hash_table->control->partitions[i];
831 : 0 : size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
832 : 0 : size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
833 : :
834 : 0 : fprintf(stderr, " partition %zu\n", i);
835 : 0 : fprintf(stderr,
836 : : " active buckets (key count = %zu)\n", partition->count);
837 : :
838 [ # # ]: 0 : for (j = begin; j < end; ++j)
839 : : {
840 : 0 : size_t count = 0;
841 : 0 : dsa_pointer bucket = hash_table->buckets[j];
842 : :
843 [ # # ]: 0 : while (DsaPointerIsValid(bucket))
844 : : {
845 : : dshash_table_item *item;
846 : :
847 : 0 : item = dsa_get_address(hash_table->area, bucket);
848 : :
849 : 0 : bucket = item->next;
850 : 0 : ++count;
851 : : }
852 : 0 : fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
853 : : }
854 : : }
855 : :
856 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
857 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, i));
858 : 0 : }
859 : :
860 : : /*
861 : : * Delete a locked item to which we have a pointer.
862 : : */
863 : : static void
864 : 74293 : delete_item(dshash_table *hash_table, dshash_table_item *item)
865 : : {
866 : 74293 : size_t hash = item->hash;
867 : 74293 : size_t partition = PARTITION_FOR_HASH(hash);
868 : :
869 : : Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
870 : :
871 [ + - ]: 74293 : if (delete_item_from_bucket(hash_table, item,
872 : 74293 : &BUCKET_FOR_HASH(hash_table, hash)))
873 : : {
874 : : Assert(hash_table->control->partitions[partition].count > 0);
875 : 74293 : --hash_table->control->partitions[partition].count;
876 : : }
877 : : else
878 : : {
879 : : Assert(false);
880 : : }
881 : 74293 : }
882 : :
883 : : /*
884 : : * Grow the hash table if necessary to the requested number of buckets. The
885 : : * requested size must be double some previously observed size.
886 : : *
887 : : * If an out-of-memory condition is observed, this function returns false if
888 : : * flags includes DSHASH_INSERT_NO_OOM, and otherwise throws an ERROR. In all
889 : : * other cases, it returns true.
890 : : *
891 : : * Must be called without any partition lock held.
892 : : */
893 : : static bool
894 : 3689 : resize(dshash_table *hash_table, size_t new_size_log2, int flags)
895 : : {
896 : : dsa_pointer old_buckets;
897 : : dsa_pointer new_buckets_shared;
898 : : dsa_pointer *new_buckets;
899 : : size_t size;
900 : 3689 : size_t new_size = ((size_t) 1) << new_size_log2;
901 : : size_t i;
902 : 3689 : int dsa_flags = DSA_ALLOC_HUGE | DSA_ALLOC_ZERO;
903 : :
904 : : /*
905 : : * Acquire the locks for all lock partitions. This is expensive, but we
906 : : * shouldn't have to do it many times.
907 : : */
908 [ + + ]: 475881 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
909 : : {
910 : : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
911 : :
912 : 472192 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
913 [ + + - + ]: 472192 : if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
914 : : {
915 : : /*
916 : : * Another backend has already increased the size; we can avoid
917 : : * obtaining all the locks and return early.
918 : : */
919 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, 0));
920 : 0 : return true;
921 : : }
922 : : }
923 : :
924 : : Assert(new_size_log2 == hash_table->control->size_log2 + 1);
925 : :
926 : : /* Allocate the space for the new table. */
927 [ + + ]: 3689 : if (flags & DSHASH_INSERT_NO_OOM)
928 : 564 : dsa_flags |= DSA_ALLOC_NO_OOM;
929 : : new_buckets_shared =
930 : 3689 : dsa_allocate_extended(hash_table->area,
931 : : sizeof(dsa_pointer) * new_size,
932 : : dsa_flags);
933 : :
934 : : /* If DSHASH_INSERT_NO_OOM was specified, allocation may have failed. */
935 [ - + ]: 3689 : if (!DsaPointerIsValid(new_buckets_shared))
936 : : {
937 : : /* Release all the locks and return without resizing. */
938 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
939 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, i));
940 : 0 : return false;
941 : : }
942 : :
943 : : /*
944 : : * We've allocated the new bucket array; all that remains to do now is to
945 : : * reinsert all items, which amounts to adjusting all the pointers.
946 : : */
947 : 3689 : new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
948 : 3689 : size = ((size_t) 1) << hash_table->control->size_log2;
949 [ + + ]: 1678569 : for (i = 0; i < size; ++i)
950 : : {
951 : 1674880 : dsa_pointer item_pointer = hash_table->buckets[i];
952 : :
953 [ + + ]: 1783641 : while (DsaPointerIsValid(item_pointer))
954 : : {
955 : : dshash_table_item *item;
956 : : dsa_pointer next_item_pointer;
957 : :
958 : 108761 : item = dsa_get_address(hash_table->area, item_pointer);
959 : 108761 : next_item_pointer = item->next;
960 : 108761 : insert_item_into_bucket(hash_table, item_pointer, item,
961 : 108761 : &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
962 : : new_size_log2)]);
963 : 108761 : item_pointer = next_item_pointer;
964 : : }
965 : : }
966 : :
967 : : /* Swap the hash table into place and free the old one. */
968 : 3689 : old_buckets = hash_table->control->buckets;
969 : 3689 : hash_table->control->buckets = new_buckets_shared;
970 : 3689 : hash_table->control->size_log2 = new_size_log2;
971 : 3689 : hash_table->buckets = new_buckets;
972 : 3689 : dsa_free(hash_table->area, old_buckets);
973 : :
974 : : /* Release all the locks. */
975 [ + + ]: 475881 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
976 : 472192 : LWLockRelease(PARTITION_LOCK(hash_table, i));
977 : :
978 : 3689 : return true;
979 : : }
980 : :
981 : : /*
982 : : * Make sure that our backend-local bucket pointers are up to date. The
983 : : * caller must have locked one lock partition, which prevents resize() from
984 : : * running concurrently.
985 : : */
986 : : static inline void
987 : 1810212 : ensure_valid_bucket_pointers(dshash_table *hash_table)
988 : : {
989 [ + + ]: 1810212 : if (hash_table->size_log2 != hash_table->control->size_log2)
990 : : {
991 : 59232 : hash_table->buckets = dsa_get_address(hash_table->area,
992 : 29616 : hash_table->control->buckets);
993 : 29616 : hash_table->size_log2 = hash_table->control->size_log2;
994 : : }
995 : 1810212 : }
996 : :
997 : : /*
998 : : * Scan a locked bucket for a match, using the provided compare function.
999 : : */
1000 : : static inline dshash_table_item *
1001 : 1808732 : find_in_bucket(dshash_table *hash_table, const void *key,
1002 : : dsa_pointer item_pointer)
1003 : : {
1004 [ + + ]: 2078386 : while (DsaPointerIsValid(item_pointer))
1005 : : {
1006 : : dshash_table_item *item;
1007 : :
1008 : 1386029 : item = dsa_get_address(hash_table->area, item_pointer);
1009 [ + + ]: 1386029 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
1010 : 1116375 : return item;
1011 : 269654 : item_pointer = item->next;
1012 : : }
1013 : 692357 : return NULL;
1014 : : }
1015 : :
1016 : : /*
1017 : : * Insert an already-allocated item into a bucket.
1018 : : */
1019 : : static void
1020 : 510284 : insert_item_into_bucket(dshash_table *hash_table,
1021 : : dsa_pointer item_pointer,
1022 : : dshash_table_item *item,
1023 : : dsa_pointer *bucket)
1024 : : {
1025 : : Assert(item == dsa_get_address(hash_table->area, item_pointer));
1026 : :
1027 : 510284 : item->next = *bucket;
1028 : 510284 : *bucket = item_pointer;
1029 : 510284 : }
1030 : :
1031 : : /*
1032 : : * Allocate space for an entry with the given key and insert it into the
1033 : : * provided bucket. Returns NULL if out of memory and DSHASH_INSERT_NO_OOM
1034 : : * was specified in flags.
1035 : : */
1036 : : static dshash_table_item *
1037 : 401523 : insert_into_bucket(dshash_table *hash_table,
1038 : : const void *key,
1039 : : dsa_pointer *bucket,
1040 : : int flags)
1041 : : {
1042 : : dsa_pointer item_pointer;
1043 : : dshash_table_item *item;
1044 : : int dsa_flags;
1045 : :
1046 : 401523 : dsa_flags = (flags & DSHASH_INSERT_NO_OOM) ? DSA_ALLOC_NO_OOM : 0;
1047 : 401523 : item_pointer = dsa_allocate_extended(hash_table->area,
1048 : 401523 : hash_table->params.entry_size +
1049 : : MAXALIGN(sizeof(dshash_table_item)),
1050 : : dsa_flags);
1051 [ - + ]: 401523 : if (!DsaPointerIsValid(item_pointer))
1052 : 0 : return NULL;
1053 : 401523 : item = dsa_get_address(hash_table->area, item_pointer);
1054 : 401523 : copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
1055 : 401523 : insert_item_into_bucket(hash_table, item_pointer, item, bucket);
1056 : 401523 : return item;
1057 : : }
1058 : :
1059 : : /*
1060 : : * Search a bucket for a matching key and delete it.
1061 : : */
1062 : : static bool
1063 : 293 : delete_key_from_bucket(dshash_table *hash_table,
1064 : : const void *key,
1065 : : dsa_pointer *bucket_head)
1066 : : {
1067 [ + + ]: 293 : while (DsaPointerIsValid(*bucket_head))
1068 : : {
1069 : : dshash_table_item *item;
1070 : :
1071 : 145 : item = dsa_get_address(hash_table->area, *bucket_head);
1072 : :
1073 [ + - ]: 145 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
1074 : : {
1075 : : dsa_pointer next;
1076 : :
1077 : 145 : next = item->next;
1078 : 145 : dsa_free(hash_table->area, *bucket_head);
1079 : 145 : *bucket_head = next;
1080 : :
1081 : 145 : return true;
1082 : : }
1083 : 0 : bucket_head = &item->next;
1084 : : }
1085 : 148 : return false;
1086 : : }
1087 : :
1088 : : /*
1089 : : * Delete the specified item from the bucket.
1090 : : */
1091 : : static bool
1092 : 74293 : delete_item_from_bucket(dshash_table *hash_table,
1093 : : dshash_table_item *item,
1094 : : dsa_pointer *bucket_head)
1095 : : {
1096 [ + - ]: 74950 : while (DsaPointerIsValid(*bucket_head))
1097 : : {
1098 : : dshash_table_item *bucket_item;
1099 : :
1100 : 74950 : bucket_item = dsa_get_address(hash_table->area, *bucket_head);
1101 : :
1102 [ + + ]: 74950 : if (bucket_item == item)
1103 : : {
1104 : : dsa_pointer next;
1105 : :
1106 : 74293 : next = item->next;
1107 : 74293 : dsa_free(hash_table->area, *bucket_head);
1108 : 74293 : *bucket_head = next;
1109 : 74293 : return true;
1110 : : }
1111 : 657 : bucket_head = &bucket_item->next;
1112 : : }
1113 : 0 : return false;
1114 : : }
1115 : :
1116 : : /*
1117 : : * Compute the hash value for a key.
1118 : : */
1119 : : static inline dshash_hash
1120 : 1805336 : hash_key(dshash_table *hash_table, const void *key)
1121 : : {
1122 : 1805336 : return hash_table->params.hash_function(key,
1123 : : hash_table->params.key_size,
1124 : : hash_table->arg);
1125 : : }
1126 : :
1127 : : /*
1128 : : * Check whether two keys compare equal.
1129 : : */
1130 : : static inline bool
1131 : 1386174 : equal_keys(dshash_table *hash_table, const void *a, const void *b)
1132 : : {
1133 : 1386174 : return hash_table->params.compare_function(a, b,
1134 : : hash_table->params.key_size,
1135 : 1386174 : hash_table->arg) == 0;
1136 : : }
1137 : :
1138 : : /*
1139 : : * Copy a key.
1140 : : */
1141 : : static inline void
1142 : 401523 : copy_key(dshash_table *hash_table, void *dest, const void *src)
1143 : : {
1144 : 401523 : hash_table->params.copy_function(dest, src,
1145 : : hash_table->params.key_size,
1146 : : hash_table->arg);
1147 : 401523 : }
|
