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 : 1596 : 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 : 1596 : hash_table = palloc_object(dshash_table);
217 : :
218 : : /* Allocate the control object in shared memory. */
219 : 1596 : control = dsa_allocate(area, sizeof(dshash_table_control));
220 : :
221 : : /* Set up the local and shared hash table structs. */
222 : 1596 : hash_table->area = area;
223 : 1596 : hash_table->params = *params;
224 : 1596 : hash_table->arg = arg;
225 : 1596 : hash_table->control = dsa_get_address(area, control);
226 : 1596 : hash_table->control->handle = control;
227 : 1596 : hash_table->control->magic = DSHASH_MAGIC;
228 : 1596 : hash_table->control->lwlock_tranche_id = params->tranche_id;
229 : :
230 : : /* Set up the array of lock partitions. */
231 : : {
232 : 1596 : dshash_partition *partitions = hash_table->control->partitions;
233 : 1596 : int tranche_id = hash_table->control->lwlock_tranche_id;
234 : : int i;
235 : :
236 [ + + ]: 205884 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
237 : : {
238 : 204288 : LWLockInitialize(&partitions[i].lock, tranche_id);
239 : 204288 : 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 : 1596 : hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
248 : 3192 : hash_table->control->buckets =
249 : 1596 : dsa_allocate_extended(area,
250 : : sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
251 : : DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
252 [ - + ]: 1596 : 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 : 3192 : hash_table->buckets = dsa_get_address(area,
262 : 1596 : hash_table->control->buckets);
263 : 1596 : hash_table->size_log2 = hash_table->control->size_log2;
264 : :
265 : 1596 : 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 : 29140 : 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 : 29140 : hash_table = palloc_object(dshash_table);
282 : :
283 : : /* Find the control object in shared memory. */
284 : 29140 : control = handle;
285 : :
286 : : /* Set up the local hash table struct. */
287 : 29140 : hash_table->area = area;
288 : 29140 : hash_table->params = *params;
289 : 29140 : hash_table->arg = arg;
290 : 29140 : 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 : 29140 : hash_table->buckets = NULL;
299 : 29140 : hash_table->size_log2 = 0;
300 : :
301 : 29140 : 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 : 30237 : 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 : 30237 : pfree(hash_table);
317 : 30237 : }
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 a handle that can be used by other processes to attach to this hash
368 : : * table.
369 : : */
370 : : dshash_table_handle
371 : 1596 : dshash_get_hash_table_handle(dshash_table *hash_table)
372 : : {
373 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
374 : :
375 : 1596 : return hash_table->control->handle;
376 : : }
377 : :
378 : : /*
379 : : * Look up an entry, given a key. Returns a pointer to an entry if one can be
380 : : * found with the given key. Returns NULL if the key is not found. If a
381 : : * non-NULL value is returned, the entry is locked and must be released by
382 : : * calling dshash_release_lock. If an error is raised before
383 : : * dshash_release_lock is called, the lock will be released automatically, but
384 : : * the caller must take care to ensure that the entry is not left corrupted.
385 : : * The lock mode is either shared or exclusive depending on 'exclusive'.
386 : : *
387 : : * The caller must not hold a lock already.
388 : : *
389 : : * Note that the lock held is in fact an LWLock, so interrupts will be held on
390 : : * return from this function, and not resumed until dshash_release_lock is
391 : : * called. It is a very good idea for the caller to release the lock quickly.
392 : : */
393 : : void *
394 : 1373675 : dshash_find(dshash_table *hash_table, const void *key, bool exclusive)
395 : : {
396 : : dshash_hash hash;
397 : : size_t partition;
398 : : dshash_table_item *item;
399 : :
400 : 1373675 : hash = hash_key(hash_table, key);
401 : 1373675 : partition = PARTITION_FOR_HASH(hash);
402 : :
403 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
404 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
405 : :
406 : 1373675 : LWLockAcquire(PARTITION_LOCK(hash_table, partition),
407 : 1373675 : exclusive ? LW_EXCLUSIVE : LW_SHARED);
408 : 1373675 : ensure_valid_bucket_pointers(hash_table);
409 : :
410 : : /* Search the active bucket. */
411 : 1373675 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
412 : :
413 [ + + ]: 1373675 : if (!item)
414 : : {
415 : : /* Not found. */
416 : 284567 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
417 : 284567 : return NULL;
418 : : }
419 : : else
420 : : {
421 : : /* The caller will free the lock by calling dshash_release_lock. */
422 : 1089108 : return ENTRY_FROM_ITEM(item);
423 : : }
424 : : }
425 : :
426 : : /*
427 : : * Find an existing entry in a dshash_table, or insert a new one.
428 : : *
429 : : * DSHASH_INSERT_NO_OOM causes this function to return NULL when no memory is
430 : : * available for the new entry. Otherwise, such allocations will result in
431 : : * an ERROR.
432 : : *
433 : : * Any entry returned by this function is exclusively locked, and the caller
434 : : * must release that lock using dshash_release_lock. Notes above dshash_find()
435 : : * regarding locking and error handling equally apply here.
436 : : *
437 : : * On return, *found is set to true if an existing entry was found in the
438 : : * hash table, and otherwise false.
439 : : *
440 : : */
441 : : void *
442 : 398363 : dshash_find_or_insert_extended(dshash_table *hash_table,
443 : : const void *key,
444 : : bool *found,
445 : : int flags)
446 : : {
447 : : dshash_hash hash;
448 : : size_t partition_index;
449 : : dshash_partition *partition;
450 : : dshash_table_item *item;
451 : :
452 : 398363 : hash = hash_key(hash_table, key);
453 : 398363 : partition_index = PARTITION_FOR_HASH(hash);
454 : 398363 : partition = &hash_table->control->partitions[partition_index];
455 : :
456 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
457 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
458 : :
459 : 402012 : restart:
460 : 402012 : LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
461 : : LW_EXCLUSIVE);
462 : 402012 : ensure_valid_bucket_pointers(hash_table);
463 : :
464 : : /* Search the active bucket. */
465 : 402012 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
466 : :
467 [ + + ]: 402012 : if (item)
468 : 272 : *found = true;
469 : : else
470 : : {
471 : 401740 : *found = false;
472 : :
473 : : /* Check if we are getting too full. */
474 [ + + ]: 401740 : if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
475 : : {
476 : : /*
477 : : * The load factor (= keys / buckets) for all buckets protected by
478 : : * this partition is > 0.75. Presumably the same applies
479 : : * generally across the whole hash table (though we don't attempt
480 : : * to track that directly to avoid contention on some kind of
481 : : * central counter; we just assume that this partition is
482 : : * representative). This is a good time to resize.
483 : : *
484 : : * Give up our existing lock first, because resizing needs to
485 : : * reacquire all the locks in the right order to avoid deadlocks.
486 : : */
487 : 3649 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
488 [ - + ]: 3649 : if (!resize(hash_table, hash_table->size_log2 + 1, flags))
489 : : {
490 : : Assert((flags & DSHASH_INSERT_NO_OOM) != 0);
491 : 0 : return NULL;
492 : : }
493 : :
494 : 3649 : goto restart;
495 : : }
496 : :
497 : : /* Finally we can try to insert the new item. */
498 : 398091 : item = insert_into_bucket(hash_table, key,
499 : 398091 : &BUCKET_FOR_HASH(hash_table, hash),
500 : : flags);
501 [ - + ]: 398091 : if (item == NULL)
502 : : {
503 : : Assert((flags & DSHASH_INSERT_NO_OOM) != 0);
504 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
505 : 0 : return NULL;
506 : : }
507 : 398091 : item->hash = hash;
508 : : /* Adjust per-lock-partition counter for load factor knowledge. */
509 : 398091 : ++partition->count;
510 : : }
511 : :
512 : : /* The caller must release the lock with dshash_release_lock. */
513 : 398363 : return ENTRY_FROM_ITEM(item);
514 : : }
515 : :
516 : : /*
517 : : * Remove an entry by key. Returns true if the key was found and the
518 : : * corresponding entry was removed.
519 : : *
520 : : * To delete an entry that you already have a pointer to, see
521 : : * dshash_delete_entry.
522 : : */
523 : : bool
524 : 297 : dshash_delete_key(dshash_table *hash_table, const void *key)
525 : : {
526 : : dshash_hash hash;
527 : : size_t partition;
528 : : bool found;
529 : :
530 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
531 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
532 : :
533 : 297 : hash = hash_key(hash_table, key);
534 : 297 : partition = PARTITION_FOR_HASH(hash);
535 : :
536 : 297 : LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
537 : 297 : ensure_valid_bucket_pointers(hash_table);
538 : :
539 [ + + ]: 297 : if (delete_key_from_bucket(hash_table, key,
540 : 297 : &BUCKET_FOR_HASH(hash_table, hash)))
541 : : {
542 : : Assert(hash_table->control->partitions[partition].count > 0);
543 : 143 : found = true;
544 : 143 : --hash_table->control->partitions[partition].count;
545 : : }
546 : : else
547 : 154 : found = false;
548 : :
549 : 297 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
550 : :
551 : 297 : return found;
552 : : }
553 : :
554 : : /*
555 : : * Remove an entry. The entry must already be exclusively locked, and must
556 : : * have been obtained by dshash_find or dshash_find_or_insert. Note that this
557 : : * function releases the lock just like dshash_release_lock.
558 : : *
559 : : * To delete an entry by key, see dshash_delete_key.
560 : : */
561 : : void
562 : 67625 : dshash_delete_entry(dshash_table *hash_table, void *entry)
563 : : {
564 : 67625 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
565 : 67625 : size_t partition = PARTITION_FOR_HASH(item->hash);
566 : :
567 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
568 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
569 : : LW_EXCLUSIVE));
570 : :
571 : 67625 : delete_item(hash_table, item);
572 : 67625 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
573 : 67625 : }
574 : :
575 : : /*
576 : : * Unlock an entry which was locked by dshash_find or dshash_find_or_insert.
577 : : */
578 : : void
579 : 1419845 : dshash_release_lock(dshash_table *hash_table, void *entry)
580 : : {
581 : 1419845 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
582 : 1419845 : size_t partition_index = PARTITION_FOR_HASH(item->hash);
583 : :
584 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
585 : :
586 : 1419845 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
587 : 1419845 : }
588 : :
589 : : /*
590 : : * A compare function that forwards to memcmp.
591 : : */
592 : : int
593 : 700 : dshash_memcmp(const void *a, const void *b, size_t size, void *arg)
594 : : {
595 : 700 : return memcmp(a, b, size);
596 : : }
597 : :
598 : : /*
599 : : * A hash function that forwards to tag_hash.
600 : : */
601 : : dshash_hash
602 : 1244 : dshash_memhash(const void *v, size_t size, void *arg)
603 : : {
604 : 1244 : return tag_hash(v, size);
605 : : }
606 : :
607 : : /*
608 : : * A copy function that forwards to memcpy.
609 : : */
610 : : void
611 : 398053 : dshash_memcpy(void *dest, const void *src, size_t size, void *arg)
612 : : {
613 : 398053 : (void) memcpy(dest, src, size);
614 : 398053 : }
615 : :
616 : : /*
617 : : * A compare function that forwards to strcmp.
618 : : */
619 : : int
620 : 202 : dshash_strcmp(const void *a, const void *b, size_t size, void *arg)
621 : : {
622 : : Assert(strlen((const char *) a) < size);
623 : : Assert(strlen((const char *) b) < size);
624 : :
625 : 202 : return strcmp((const char *) a, (const char *) b);
626 : : }
627 : :
628 : : /*
629 : : * A hash function that forwards to string_hash.
630 : : */
631 : : dshash_hash
632 : 245 : dshash_strhash(const void *v, size_t size, void *arg)
633 : : {
634 : : Assert(strlen((const char *) v) < size);
635 : :
636 : 245 : return string_hash((const char *) v, size);
637 : : }
638 : :
639 : : /*
640 : : * A copy function that forwards to strcpy.
641 : : */
642 : : void
643 : 38 : dshash_strcpy(void *dest, const void *src, size_t size, void *arg)
644 : : {
645 : : Assert(strlen((const char *) src) < size);
646 : :
647 : 38 : (void) strcpy((char *) dest, (const char *) src);
648 : 38 : }
649 : :
650 : : /*
651 : : * Sequentially scan through dshash table and return all the elements one by
652 : : * one, return NULL when all elements have been returned.
653 : : *
654 : : * dshash_seq_term needs to be called when a scan finished. The caller may
655 : : * delete returned elements midst of a scan by using dshash_delete_current()
656 : : * if exclusive = true.
657 : : */
658 : : void
659 : 1175 : dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table,
660 : : bool exclusive)
661 : : {
662 : 1175 : status->hash_table = hash_table;
663 : 1175 : status->curbucket = 0;
664 : 1175 : status->nbuckets = 0;
665 : 1175 : status->curitem = NULL;
666 : 1175 : status->pnextitem = InvalidDsaPointer;
667 : 1175 : status->curpartition = -1;
668 : 1175 : status->exclusive = exclusive;
669 : 1175 : }
670 : :
671 : : /*
672 : : * Returns the next element.
673 : : *
674 : : * Returned elements are locked and the caller may not release the lock. It is
675 : : * released by future calls to dshash_seq_next() or dshash_seq_term().
676 : : */
677 : : void *
678 : 313969 : dshash_seq_next(dshash_seq_status *status)
679 : : {
680 : : dsa_pointer next_item_pointer;
681 : :
682 : : /*
683 : : * Not yet holding any partition locks. Need to determine the size of the
684 : : * hash table, it could have been resized since we were looking last.
685 : : * Since we iterate in partition order, we can start by unconditionally
686 : : * lock partition 0.
687 : : *
688 : : * Once we hold the lock, no resizing can happen until the scan ends. So
689 : : * we don't need to repeatedly call ensure_valid_bucket_pointers().
690 : : */
691 [ + + ]: 313969 : if (status->curpartition == -1)
692 : : {
693 : : Assert(status->curbucket == 0);
694 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(status->hash_table);
695 : :
696 : 1175 : status->curpartition = 0;
697 : :
698 : 1175 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
699 : : status->curpartition),
700 : 1175 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
701 : :
702 : 1175 : ensure_valid_bucket_pointers(status->hash_table);
703 : :
704 : 1175 : status->nbuckets =
705 : 1175 : NUM_BUCKETS(status->hash_table->control->size_log2);
706 : 1175 : next_item_pointer = status->hash_table->buckets[status->curbucket];
707 : : }
708 : : else
709 : 312794 : next_item_pointer = status->pnextitem;
710 : :
711 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(status->hash_table,
712 : : status->curpartition),
713 : : status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
714 : :
715 : : /* Move to the next bucket if we finished the current bucket */
716 [ + + ]: 1970266 : while (!DsaPointerIsValid(next_item_pointer))
717 : : {
718 : : int next_partition;
719 : :
720 [ + + ]: 1657472 : if (++status->curbucket >= status->nbuckets)
721 : : {
722 : : /* all buckets have been scanned. finish. */
723 : 1175 : return NULL;
724 : : }
725 : :
726 : : /* Check if move to the next partition */
727 : 1656297 : next_partition =
728 : 1656297 : PARTITION_FOR_BUCKET_INDEX(status->curbucket,
729 : : status->hash_table->size_log2);
730 : :
731 [ + + ]: 1656297 : if (status->curpartition != next_partition)
732 : : {
733 : : /*
734 : : * Move to the next partition. Lock the next partition then
735 : : * release the current, not in the reverse order to avoid
736 : : * concurrent resizing. Avoid dead lock by taking lock in the
737 : : * same order with resize().
738 : : */
739 : 149225 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
740 : : next_partition),
741 : 149225 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
742 : 149225 : LWLockRelease(PARTITION_LOCK(status->hash_table,
743 : : status->curpartition));
744 : 149225 : status->curpartition = next_partition;
745 : : }
746 : :
747 : 1656297 : next_item_pointer = status->hash_table->buckets[status->curbucket];
748 : : }
749 : :
750 : 312794 : status->curitem =
751 : 312794 : dsa_get_address(status->hash_table->area, next_item_pointer);
752 : :
753 : : /*
754 : : * The caller may delete the item. Store the next item in case of
755 : : * deletion.
756 : : */
757 : 312794 : status->pnextitem = status->curitem->next;
758 : :
759 : 312794 : return ENTRY_FROM_ITEM(status->curitem);
760 : : }
761 : :
762 : : /*
763 : : * Terminates the seqscan and release all locks.
764 : : *
765 : : * Needs to be called after finishing or when exiting a seqscan.
766 : : */
767 : : void
768 : 1175 : dshash_seq_term(dshash_seq_status *status)
769 : : {
770 [ + - ]: 1175 : if (status->curpartition >= 0)
771 : 1175 : LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
772 : 1175 : }
773 : :
774 : : /*
775 : : * Remove the current entry of the seq scan.
776 : : */
777 : : void
778 : 5822 : dshash_delete_current(dshash_seq_status *status)
779 : : {
780 : 5822 : dshash_table *hash_table = status->hash_table;
781 : 5822 : dshash_table_item *item = status->curitem;
782 : : size_t partition PG_USED_FOR_ASSERTS_ONLY;
783 : :
784 : 5822 : partition = PARTITION_FOR_HASH(item->hash);
785 : :
786 : : Assert(status->exclusive);
787 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
788 : : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
789 : : LW_EXCLUSIVE));
790 : :
791 : 5822 : delete_item(hash_table, item);
792 : 5822 : }
793 : :
794 : : /*
795 : : * Print debugging information about the internal state of the hash table to
796 : : * stderr. The caller must hold no partition locks.
797 : : */
798 : : void
799 : 0 : dshash_dump(dshash_table *hash_table)
800 : : {
801 : : size_t i;
802 : : size_t j;
803 : :
804 : : Assert(hash_table->control->magic == DSHASH_MAGIC);
805 : : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
806 : :
807 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
808 : : {
809 : : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
810 : 0 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
811 : : }
812 : :
813 : 0 : ensure_valid_bucket_pointers(hash_table);
814 : :
815 : 0 : fprintf(stderr,
816 : 0 : "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
817 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
818 : : {
819 : 0 : dshash_partition *partition = &hash_table->control->partitions[i];
820 : 0 : size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
821 : 0 : size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
822 : :
823 : 0 : fprintf(stderr, " partition %zu\n", i);
824 : 0 : fprintf(stderr,
825 : : " active buckets (key count = %zu)\n", partition->count);
826 : :
827 [ # # ]: 0 : for (j = begin; j < end; ++j)
828 : : {
829 : 0 : size_t count = 0;
830 : 0 : dsa_pointer bucket = hash_table->buckets[j];
831 : :
832 [ # # ]: 0 : while (DsaPointerIsValid(bucket))
833 : : {
834 : : dshash_table_item *item;
835 : :
836 : 0 : item = dsa_get_address(hash_table->area, bucket);
837 : :
838 : 0 : bucket = item->next;
839 : 0 : ++count;
840 : : }
841 : 0 : fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
842 : : }
843 : : }
844 : :
845 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
846 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, i));
847 : 0 : }
848 : :
849 : : /*
850 : : * Delete a locked item to which we have a pointer.
851 : : */
852 : : static void
853 : 73447 : delete_item(dshash_table *hash_table, dshash_table_item *item)
854 : : {
855 : 73447 : size_t hash = item->hash;
856 : 73447 : size_t partition = PARTITION_FOR_HASH(hash);
857 : :
858 : : Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
859 : :
860 [ + - ]: 73447 : if (delete_item_from_bucket(hash_table, item,
861 : 73447 : &BUCKET_FOR_HASH(hash_table, hash)))
862 : : {
863 : : Assert(hash_table->control->partitions[partition].count > 0);
864 : 73447 : --hash_table->control->partitions[partition].count;
865 : : }
866 : : else
867 : : {
868 : : Assert(false);
869 : : }
870 : 73447 : }
871 : :
872 : : /*
873 : : * Grow the hash table if necessary to the requested number of buckets. The
874 : : * requested size must be double some previously observed size.
875 : : *
876 : : * If an out-of-memory condition is observed, this function returns false if
877 : : * flags includes DSHASH_INSERT_NO_OOM, and otherwise throws an ERROR. In all
878 : : * other cases, it returns true.
879 : : *
880 : : * Must be called without any partition lock held.
881 : : */
882 : : static bool
883 : 3649 : resize(dshash_table *hash_table, size_t new_size_log2, int flags)
884 : : {
885 : : dsa_pointer old_buckets;
886 : : dsa_pointer new_buckets_shared;
887 : : dsa_pointer *new_buckets;
888 : : size_t size;
889 : 3649 : size_t new_size = ((size_t) 1) << new_size_log2;
890 : : size_t i;
891 : 3649 : int dsa_flags = DSA_ALLOC_HUGE | DSA_ALLOC_ZERO;
892 : :
893 : : /*
894 : : * Acquire the locks for all lock partitions. This is expensive, but we
895 : : * shouldn't have to do it many times.
896 : : */
897 [ + + ]: 470721 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
898 : : {
899 : : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
900 : :
901 : 467072 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
902 [ + + - + ]: 467072 : if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
903 : : {
904 : : /*
905 : : * Another backend has already increased the size; we can avoid
906 : : * obtaining all the locks and return early.
907 : : */
908 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, 0));
909 : 0 : return true;
910 : : }
911 : : }
912 : :
913 : : Assert(new_size_log2 == hash_table->control->size_log2 + 1);
914 : :
915 : : /* Allocate the space for the new table. */
916 [ - + ]: 3649 : if (flags & DSHASH_INSERT_NO_OOM)
917 : 0 : dsa_flags |= DSA_ALLOC_NO_OOM;
918 : : new_buckets_shared =
919 : 3649 : dsa_allocate_extended(hash_table->area,
920 : : sizeof(dsa_pointer) * new_size,
921 : : dsa_flags);
922 : :
923 : : /* If DSHASH_INSERT_NO_OOM was specified, allocation may have failed. */
924 [ - + ]: 3649 : if (!DsaPointerIsValid(new_buckets_shared))
925 : : {
926 : : /* Release all the locks and return without resizing. */
927 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
928 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, i));
929 : 0 : return false;
930 : : }
931 : :
932 : : /*
933 : : * We've allocated the new bucket array; all that remains to do now is to
934 : : * reinsert all items, which amounts to adjusting all the pointers.
935 : : */
936 : 3649 : new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
937 : 3649 : size = ((size_t) 1) << hash_table->control->size_log2;
938 [ + + ]: 1662401 : for (i = 0; i < size; ++i)
939 : : {
940 : 1658752 : dsa_pointer item_pointer = hash_table->buckets[i];
941 : :
942 [ + + ]: 1766459 : while (DsaPointerIsValid(item_pointer))
943 : : {
944 : : dshash_table_item *item;
945 : : dsa_pointer next_item_pointer;
946 : :
947 : 107707 : item = dsa_get_address(hash_table->area, item_pointer);
948 : 107707 : next_item_pointer = item->next;
949 : 107707 : insert_item_into_bucket(hash_table, item_pointer, item,
950 : 107707 : &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
951 : : new_size_log2)]);
952 : 107707 : item_pointer = next_item_pointer;
953 : : }
954 : : }
955 : :
956 : : /* Swap the hash table into place and free the old one. */
957 : 3649 : old_buckets = hash_table->control->buckets;
958 : 3649 : hash_table->control->buckets = new_buckets_shared;
959 : 3649 : hash_table->control->size_log2 = new_size_log2;
960 : 3649 : hash_table->buckets = new_buckets;
961 : 3649 : dsa_free(hash_table->area, old_buckets);
962 : :
963 : : /* Release all the locks. */
964 [ + + ]: 470721 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
965 : 467072 : LWLockRelease(PARTITION_LOCK(hash_table, i));
966 : :
967 : 3649 : return true;
968 : : }
969 : :
970 : : /*
971 : : * Make sure that our backend-local bucket pointers are up to date. The
972 : : * caller must have locked one lock partition, which prevents resize() from
973 : : * running concurrently.
974 : : */
975 : : static inline void
976 : 1777159 : ensure_valid_bucket_pointers(dshash_table *hash_table)
977 : : {
978 [ + + ]: 1777159 : if (hash_table->size_log2 != hash_table->control->size_log2)
979 : : {
980 : 58304 : hash_table->buckets = dsa_get_address(hash_table->area,
981 : 29152 : hash_table->control->buckets);
982 : 29152 : hash_table->size_log2 = hash_table->control->size_log2;
983 : : }
984 : 1777159 : }
985 : :
986 : : /*
987 : : * Scan a locked bucket for a match, using the provided compare function.
988 : : */
989 : : static inline dshash_table_item *
990 : 1775687 : find_in_bucket(dshash_table *hash_table, const void *key,
991 : : dsa_pointer item_pointer)
992 : : {
993 [ + + ]: 2040370 : while (DsaPointerIsValid(item_pointer))
994 : : {
995 : : dshash_table_item *item;
996 : :
997 : 1354063 : item = dsa_get_address(hash_table->area, item_pointer);
998 [ + + ]: 1354063 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
999 : 1089380 : return item;
1000 : 264683 : item_pointer = item->next;
1001 : : }
1002 : 686307 : return NULL;
1003 : : }
1004 : :
1005 : : /*
1006 : : * Insert an already-allocated item into a bucket.
1007 : : */
1008 : : static void
1009 : 505798 : insert_item_into_bucket(dshash_table *hash_table,
1010 : : dsa_pointer item_pointer,
1011 : : dshash_table_item *item,
1012 : : dsa_pointer *bucket)
1013 : : {
1014 : : Assert(item == dsa_get_address(hash_table->area, item_pointer));
1015 : :
1016 : 505798 : item->next = *bucket;
1017 : 505798 : *bucket = item_pointer;
1018 : 505798 : }
1019 : :
1020 : : /*
1021 : : * Allocate space for an entry with the given key and insert it into the
1022 : : * provided bucket. Returns NULL if out of memory and DSHASH_INSERT_NO_OOM
1023 : : * was specified in flags.
1024 : : */
1025 : : static dshash_table_item *
1026 : 398091 : insert_into_bucket(dshash_table *hash_table,
1027 : : const void *key,
1028 : : dsa_pointer *bucket,
1029 : : int flags)
1030 : : {
1031 : : dsa_pointer item_pointer;
1032 : : dshash_table_item *item;
1033 : : int dsa_flags;
1034 : :
1035 : 398091 : dsa_flags = (flags & DSHASH_INSERT_NO_OOM) ? DSA_ALLOC_NO_OOM : 0;
1036 : 398091 : item_pointer = dsa_allocate_extended(hash_table->area,
1037 : 398091 : hash_table->params.entry_size +
1038 : : MAXALIGN(sizeof(dshash_table_item)),
1039 : : dsa_flags);
1040 [ - + ]: 398091 : if (!DsaPointerIsValid(item_pointer))
1041 : 0 : return NULL;
1042 : 398091 : item = dsa_get_address(hash_table->area, item_pointer);
1043 : 398091 : copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
1044 : 398091 : insert_item_into_bucket(hash_table, item_pointer, item, bucket);
1045 : 398091 : return item;
1046 : : }
1047 : :
1048 : : /*
1049 : : * Search a bucket for a matching key and delete it.
1050 : : */
1051 : : static bool
1052 : 297 : delete_key_from_bucket(dshash_table *hash_table,
1053 : : const void *key,
1054 : : dsa_pointer *bucket_head)
1055 : : {
1056 [ + + ]: 297 : while (DsaPointerIsValid(*bucket_head))
1057 : : {
1058 : : dshash_table_item *item;
1059 : :
1060 : 143 : item = dsa_get_address(hash_table->area, *bucket_head);
1061 : :
1062 [ + - ]: 143 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
1063 : : {
1064 : : dsa_pointer next;
1065 : :
1066 : 143 : next = item->next;
1067 : 143 : dsa_free(hash_table->area, *bucket_head);
1068 : 143 : *bucket_head = next;
1069 : :
1070 : 143 : return true;
1071 : : }
1072 : 0 : bucket_head = &item->next;
1073 : : }
1074 : 154 : return false;
1075 : : }
1076 : :
1077 : : /*
1078 : : * Delete the specified item from the bucket.
1079 : : */
1080 : : static bool
1081 : 73447 : delete_item_from_bucket(dshash_table *hash_table,
1082 : : dshash_table_item *item,
1083 : : dsa_pointer *bucket_head)
1084 : : {
1085 [ + - ]: 74119 : while (DsaPointerIsValid(*bucket_head))
1086 : : {
1087 : : dshash_table_item *bucket_item;
1088 : :
1089 : 74119 : bucket_item = dsa_get_address(hash_table->area, *bucket_head);
1090 : :
1091 [ + + ]: 74119 : if (bucket_item == item)
1092 : : {
1093 : : dsa_pointer next;
1094 : :
1095 : 73447 : next = item->next;
1096 : 73447 : dsa_free(hash_table->area, *bucket_head);
1097 : 73447 : *bucket_head = next;
1098 : 73447 : return true;
1099 : : }
1100 : 672 : bucket_head = &bucket_item->next;
1101 : : }
1102 : 0 : return false;
1103 : : }
1104 : :
1105 : : /*
1106 : : * Compute the hash value for a key.
1107 : : */
1108 : : static inline dshash_hash
1109 : 1772335 : hash_key(dshash_table *hash_table, const void *key)
1110 : : {
1111 : 1772335 : return hash_table->params.hash_function(key,
1112 : : hash_table->params.key_size,
1113 : : hash_table->arg);
1114 : : }
1115 : :
1116 : : /*
1117 : : * Check whether two keys compare equal.
1118 : : */
1119 : : static inline bool
1120 : 1354206 : equal_keys(dshash_table *hash_table, const void *a, const void *b)
1121 : : {
1122 : 1354206 : return hash_table->params.compare_function(a, b,
1123 : : hash_table->params.key_size,
1124 : 1354206 : hash_table->arg) == 0;
1125 : : }
1126 : :
1127 : : /*
1128 : : * Copy a key.
1129 : : */
1130 : : static inline void
1131 : 398091 : copy_key(dshash_table *hash_table, void *dest, const void *src)
1132 : : {
1133 : 398091 : hash_table->params.copy_function(dest, src,
1134 : : hash_table->params.key_size,
1135 : : hash_table->arg);
1136 : 398091 : }
|
