Debian Codegraph @

src/backend/lib/dshash.c

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