Age Owner Branch data TLA 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-2024, 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 *
2427 andres@anarazel.de 206 :CBC 1087 : 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 : 1087 : hash_table = palloc(sizeof(dshash_table));
213 : :
214 : : /* Allocate the control object in shared memory. */
215 : 1087 : control = dsa_allocate(area, sizeof(dshash_table_control));
216 : :
217 : : /* Set up the local and shared hash table structs. */
218 : 1087 : hash_table->area = area;
219 : 1087 : hash_table->params = *params;
220 : 1087 : hash_table->arg = arg;
221 : 1087 : hash_table->control = dsa_get_address(area, control);
222 : 1087 : hash_table->control->handle = control;
223 : 1087 : hash_table->control->magic = DSHASH_MAGIC;
224 : 1087 : hash_table->control->lwlock_tranche_id = params->tranche_id;
225 : :
226 : : /* Set up the array of lock partitions. */
227 : : {
228 : 1087 : dshash_partition *partitions = hash_table->control->partitions;
229 : 1087 : int tranche_id = hash_table->control->lwlock_tranche_id;
230 : : int i;
231 : :
232 [ + + ]: 140223 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
233 : : {
234 : 139136 : LWLockInitialize(&partitions[i].lock, tranche_id);
235 : 139136 : 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 : 1087 : hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
244 : 2174 : hash_table->control->buckets =
2425 245 : 1087 : dsa_allocate_extended(area,
246 : : sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
247 : : DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
248 [ - + ]: 1087 : if (!DsaPointerIsValid(hash_table->control->buckets))
249 : : {
2425 andres@anarazel.de 250 :UBC 0 : dsa_free(area, control);
251 [ # # ]: 0 : 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 : : }
2427 andres@anarazel.de 257 :CBC 2174 : hash_table->buckets = dsa_get_address(area,
258 : 1087 : hash_table->control->buckets);
2400 259 : 1087 : hash_table->size_log2 = hash_table->control->size_log2;
260 : :
2427 261 : 1087 : 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 : 22314 : 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 : 22314 : hash_table = palloc(sizeof(dshash_table));
278 : :
279 : : /* Find the control object in shared memory. */
280 : 22314 : control = handle;
281 : :
282 : : /* Set up the local hash table struct. */
283 : 22314 : hash_table->area = area;
284 : 22314 : hash_table->params = *params;
285 : 22314 : hash_table->arg = arg;
286 : 22314 : hash_table->control = dsa_get_address(area, control);
287 [ - + ]: 22314 : 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 : : */
2400 294 : 22314 : hash_table->buckets = NULL;
295 : 22314 : hash_table->size_log2 = 0;
296 : :
2427 297 : 22314 : 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 : 21692 : dshash_detach(dshash_table *hash_table)
308 : : {
643 tmunro@postgresql.or 309 [ - + ]: 21692 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
310 : :
311 : : /* The hash table may have been destroyed. Just free local memory. */
2427 andres@anarazel.de 312 : 21692 : pfree(hash_table);
313 : 21692 : }
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
2427 andres@anarazel.de 323 :UBC 0 : dshash_destroy(dshash_table *hash_table)
324 : : {
325 : : size_t size;
326 : : size_t i;
327 : :
328 [ # # ]: 0 : Assert(hash_table->control->magic == DSHASH_MAGIC);
329 : 0 : ensure_valid_bucket_pointers(hash_table);
330 : :
331 : : /* Free all the entries. */
766 332 : 0 : size = NUM_BUCKETS(hash_table->size_log2);
2427 333 [ # # ]: 0 : for (i = 0; i < size; ++i)
334 : : {
335 : 0 : dsa_pointer item_pointer = hash_table->buckets[i];
336 : :
337 [ # # ]: 0 : while (DsaPointerIsValid(item_pointer))
338 : : {
339 : : dshash_table_item *item;
340 : : dsa_pointer next_item_pointer;
341 : :
342 : 0 : item = dsa_get_address(hash_table->area, item_pointer);
343 : 0 : next_item_pointer = item->next;
344 : 0 : dsa_free(hash_table->area, item_pointer);
345 : 0 : 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 : 0 : hash_table->control->magic = 0;
354 : :
355 : : /* Free the active table and control object. */
356 : 0 : dsa_free(hash_table->area, hash_table->control->buckets);
357 : 0 : dsa_free(hash_table->area, hash_table->control->handle);
358 : :
359 : 0 : pfree(hash_table);
360 : 0 : }
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
2427 andres@anarazel.de 367 :CBC 1087 : dshash_get_hash_table_handle(dshash_table *hash_table)
368 : : {
369 [ - + ]: 1087 : Assert(hash_table->control->magic == DSHASH_MAGIC);
370 : :
371 : 1087 : 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 : 884731 : 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 : 884731 : hash = hash_key(hash_table, key);
397 : 884731 : partition = PARTITION_FOR_HASH(hash);
398 : :
399 [ - + ]: 884731 : Assert(hash_table->control->magic == DSHASH_MAGIC);
643 tmunro@postgresql.or 400 [ - + ]: 884731 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
401 : :
2427 andres@anarazel.de 402 : 884731 : LWLockAcquire(PARTITION_LOCK(hash_table, partition),
403 : 884731 : exclusive ? LW_EXCLUSIVE : LW_SHARED);
404 : 884731 : ensure_valid_bucket_pointers(hash_table);
405 : :
406 : : /* Search the active bucket. */
407 : 884731 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
408 : :
409 [ + + ]: 884731 : if (!item)
410 : : {
411 : : /* Not found. */
412 : 172398 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
413 : 172398 : return NULL;
414 : : }
415 : : else
416 : : {
417 : : /* The caller will free the lock by calling dshash_release_lock. */
418 : 712333 : 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 : 243067 : 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 : 243067 : hash = hash_key(hash_table, key);
443 : 243067 : partition_index = PARTITION_FOR_HASH(hash);
444 : 243067 : partition = &hash_table->control->partitions[partition_index];
445 : :
446 [ - + ]: 243067 : Assert(hash_table->control->magic == DSHASH_MAGIC);
643 tmunro@postgresql.or 447 [ + - ]: 243067 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
448 : :
2427 andres@anarazel.de 449 : 243067 : restart:
450 : 245223 : LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
451 : : LW_EXCLUSIVE);
452 : 245223 : ensure_valid_bucket_pointers(hash_table);
453 : :
454 : : /* Search the active bucket. */
455 : 245223 : item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
456 : :
457 [ + + ]: 245223 : if (item)
458 : 136 : *found = true;
459 : : else
460 : : {
461 : 245087 : *found = false;
462 : :
463 : : /* Check if we are getting too full. */
464 [ + + ]: 245087 : 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 : 2156 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
478 : 2156 : resize(hash_table, hash_table->size_log2 + 1);
479 : :
480 : 2156 : goto restart;
481 : : }
482 : :
483 : : /* Finally we can try to insert the new item. */
484 : 242931 : item = insert_into_bucket(hash_table, key,
485 : 242931 : &BUCKET_FOR_HASH(hash_table, hash));
486 : 242931 : item->hash = hash;
487 : : /* Adjust per-lock-partition counter for load factor knowledge. */
488 : 242931 : ++partition->count;
489 : : }
490 : :
491 : : /* The caller must release the lock with dshash_release_lock. */
492 : 243067 : 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 : 128 : dshash_delete_key(dshash_table *hash_table, const void *key)
504 : : {
505 : : dshash_hash hash;
506 : : size_t partition;
507 : : bool found;
508 : :
509 [ - + ]: 128 : Assert(hash_table->control->magic == DSHASH_MAGIC);
643 tmunro@postgresql.or 510 [ - + ]: 128 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
511 : :
2427 andres@anarazel.de 512 : 128 : hash = hash_key(hash_table, key);
513 : 128 : partition = PARTITION_FOR_HASH(hash);
514 : :
515 : 128 : LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
516 : 128 : ensure_valid_bucket_pointers(hash_table);
517 : :
518 [ + + ]: 128 : if (delete_key_from_bucket(hash_table, key,
519 : 128 : &BUCKET_FOR_HASH(hash_table, hash)))
520 : : {
521 [ - + ]: 94 : Assert(hash_table->control->partitions[partition].count > 0);
522 : 94 : found = true;
523 : 94 : --hash_table->control->partitions[partition].count;
524 : : }
525 : : else
526 : 34 : found = false;
527 : :
528 : 128 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
529 : :
530 : 128 : 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 : 31130 : dshash_delete_entry(dshash_table *hash_table, void *entry)
542 : : {
543 : 31130 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
544 : 31130 : size_t partition = PARTITION_FOR_HASH(item->hash);
545 : :
546 [ - + ]: 31130 : Assert(hash_table->control->magic == DSHASH_MAGIC);
547 [ - + ]: 31130 : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
548 : : LW_EXCLUSIVE));
549 : :
550 : 31130 : delete_item(hash_table, item);
551 : 31130 : LWLockRelease(PARTITION_LOCK(hash_table, partition));
552 : 31130 : }
553 : :
554 : : /*
555 : : * Unlock an entry which was locked by dshash_find or dshash_find_or_insert.
556 : : */
557 : : void
558 : 924270 : dshash_release_lock(dshash_table *hash_table, void *entry)
559 : : {
560 : 924270 : dshash_table_item *item = ITEM_FROM_ENTRY(entry);
561 : 924270 : size_t partition_index = PARTITION_FOR_HASH(item->hash);
562 : :
563 [ - + ]: 924270 : Assert(hash_table->control->magic == DSHASH_MAGIC);
564 : :
565 : 924270 : LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
566 : 924270 : }
567 : :
568 : : /*
569 : : * A compare function that forwards to memcmp.
570 : : */
571 : : int
2425 572 : 730 : dshash_memcmp(const void *a, const void *b, size_t size, void *arg)
573 : : {
574 : 730 : return memcmp(a, b, size);
575 : : }
576 : :
577 : : /*
578 : : * A hash function that forwards to tag_hash.
579 : : */
580 : : dshash_hash
581 : 1133 : dshash_memhash(const void *v, size_t size, void *arg)
582 : : {
583 : 1133 : return tag_hash(v, size);
584 : : }
585 : :
586 : : /*
587 : : * A copy function that forwards to memcpy.
588 : : */
589 : : void
48 nathan@postgresql.or 590 :GNC 242924 : dshash_memcpy(void *dest, const void *src, size_t size, void *arg)
591 : : {
592 : 242924 : (void) memcpy(dest, src, size);
593 : 242924 : }
594 : :
595 : : /*
596 : : * A compare function that forwards to strcmp.
597 : : */
598 : : int
599 : 9 : dshash_strcmp(const void *a, const void *b, size_t size, void *arg)
600 : : {
601 [ - + ]: 9 : Assert(strlen((const char *) a) < size);
602 [ - + ]: 9 : Assert(strlen((const char *) b) < size);
603 : :
604 : 9 : 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 : 16 : dshash_strhash(const void *v, size_t size, void *arg)
612 : : {
613 [ - + ]: 16 : Assert(strlen((const char *) v) < size);
614 : :
615 : 16 : return string_hash((const char *) v, size);
616 : : }
617 : :
618 : : /*
619 : : * A copy function that forwards to strcpy.
620 : : */
621 : : void
622 : 7 : dshash_strcpy(void *dest, const void *src, size_t size, void *arg)
623 : : {
624 [ - + ]: 7 : Assert(strlen((const char *) src) < size);
625 : :
626 : 7 : (void) strcpy((char *) dest, (const char *) src);
627 : 7 : }
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
766 andres@anarazel.de 638 :CBC 819 : dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table,
639 : : bool exclusive)
640 : : {
641 : 819 : status->hash_table = hash_table;
642 : 819 : status->curbucket = 0;
643 : 819 : status->nbuckets = 0;
644 : 819 : status->curitem = NULL;
645 : 819 : status->pnextitem = InvalidDsaPointer;
646 : 819 : status->curpartition = -1;
647 : 819 : status->exclusive = exclusive;
648 : 819 : }
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 : 192969 : 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 : : */
741 670 [ + + ]: 192969 : if (status->curpartition == -1)
671 : : {
766 672 [ - + ]: 819 : Assert(status->curbucket == 0);
643 tmunro@postgresql.or 673 [ - + ]: 819 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(status->hash_table);
674 : :
741 andres@anarazel.de 675 : 819 : status->curpartition = 0;
676 : :
677 : 819 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
678 : : status->curpartition),
766 679 : 819 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
680 : :
681 : 819 : ensure_valid_bucket_pointers(status->hash_table);
682 : :
741 683 : 819 : status->nbuckets =
684 : 819 : NUM_BUCKETS(status->hash_table->control->size_log2);
766 685 : 819 : next_item_pointer = status->hash_table->buckets[status->curbucket];
686 : : }
687 : : else
688 : 192150 : next_item_pointer = status->pnextitem;
689 : :
690 [ - + ]: 192969 : 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 [ + + ]: 907542 : while (!DsaPointerIsValid(next_item_pointer))
696 : : {
697 : : int next_partition;
698 : :
699 [ + + ]: 715392 : if (++status->curbucket >= status->nbuckets)
700 : : {
701 : : /* all buckets have been scanned. finish. */
702 : 819 : return NULL;
703 : : }
704 : :
705 : : /* Check if move to the next partition */
706 : 714573 : next_partition =
707 : 714573 : PARTITION_FOR_BUCKET_INDEX(status->curbucket,
708 : : status->hash_table->size_log2);
709 : :
710 [ + + ]: 714573 : 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 : 104013 : LWLockAcquire(PARTITION_LOCK(status->hash_table,
719 : : next_partition),
720 : 104013 : status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
721 : 104013 : LWLockRelease(PARTITION_LOCK(status->hash_table,
722 : : status->curpartition));
723 : 104013 : status->curpartition = next_partition;
724 : : }
725 : :
726 : 714573 : next_item_pointer = status->hash_table->buckets[status->curbucket];
727 : : }
728 : :
729 : 192150 : status->curitem =
730 : 192150 : 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 : 192150 : status->pnextitem = status->curitem->next;
737 : :
738 : 192150 : 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 : 819 : dshash_seq_term(dshash_seq_status *status)
748 : : {
749 [ + - ]: 819 : if (status->curpartition >= 0)
750 : 819 : LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
751 : 819 : }
752 : :
753 : : /*
754 : : * Remove the current entry of the seq scan.
755 : : */
756 : : void
757 : 2044 : dshash_delete_current(dshash_seq_status *status)
758 : : {
759 : 2044 : dshash_table *hash_table = status->hash_table;
760 : 2044 : dshash_table_item *item = status->curitem;
761 : : size_t partition PG_USED_FOR_ASSERTS_ONLY;
762 : :
763 : 2044 : partition = PARTITION_FOR_HASH(item->hash);
764 : :
765 [ - + ]: 2044 : Assert(status->exclusive);
766 [ - + ]: 2044 : Assert(hash_table->control->magic == DSHASH_MAGIC);
767 [ - + ]: 2044 : Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
768 : : LW_EXCLUSIVE));
769 : :
770 : 2044 : delete_item(hash_table, item);
771 : 2044 : }
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
2427 andres@anarazel.de 778 :UBC 0 : dshash_dump(dshash_table *hash_table)
779 : : {
780 : : size_t i;
781 : : size_t j;
782 : :
783 [ # # ]: 0 : Assert(hash_table->control->magic == DSHASH_MAGIC);
643 tmunro@postgresql.or 784 [ # # ]: 0 : ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
785 : :
2427 andres@anarazel.de 786 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
787 : : {
788 [ # # ]: 0 : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
789 : 0 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
790 : : }
791 : :
792 : 0 : ensure_valid_bucket_pointers(hash_table);
793 : :
794 : 0 : fprintf(stderr,
795 : 0 : "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
796 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
797 : : {
798 : 0 : dshash_partition *partition = &hash_table->control->partitions[i];
799 : 0 : size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
800 : 0 : size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
801 : :
802 : 0 : fprintf(stderr, " partition %zu\n", i);
803 : 0 : fprintf(stderr,
804 : : " active buckets (key count = %zu)\n", partition->count);
805 : :
806 [ # # ]: 0 : for (j = begin; j < end; ++j)
807 : : {
808 : 0 : size_t count = 0;
809 : 0 : dsa_pointer bucket = hash_table->buckets[j];
810 : :
811 [ # # ]: 0 : while (DsaPointerIsValid(bucket))
812 : : {
813 : : dshash_table_item *item;
814 : :
815 : 0 : item = dsa_get_address(hash_table->area, bucket);
816 : :
817 : 0 : bucket = item->next;
818 : 0 : ++count;
819 : : }
820 : 0 : fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
821 : : }
822 : : }
823 : :
824 [ # # ]: 0 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
825 : 0 : LWLockRelease(PARTITION_LOCK(hash_table, i));
826 : 0 : }
827 : :
828 : : /*
829 : : * Delete a locked item to which we have a pointer.
830 : : */
831 : : static void
2427 andres@anarazel.de 832 :CBC 33174 : delete_item(dshash_table *hash_table, dshash_table_item *item)
833 : : {
834 : 33174 : size_t hash = item->hash;
835 : 33174 : size_t partition = PARTITION_FOR_HASH(hash);
836 : :
837 [ - + ]: 33174 : Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
838 : :
839 [ + - ]: 33174 : if (delete_item_from_bucket(hash_table, item,
840 : 33174 : &BUCKET_FOR_HASH(hash_table, hash)))
841 : : {
842 [ - + ]: 33174 : Assert(hash_table->control->partitions[partition].count > 0);
843 : 33174 : --hash_table->control->partitions[partition].count;
844 : : }
845 : : else
846 : : {
2427 andres@anarazel.de 847 :UBC 0 : Assert(false);
848 : : }
2427 andres@anarazel.de 849 :CBC 33174 : }
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 : 2156 : 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;
2415 tgl@sss.pgh.pa.us 864 : 2156 : 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 : : */
2427 andres@anarazel.de 871 [ + + ]: 278124 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
872 : : {
873 [ - + ]: 275968 : Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
874 : :
875 : 275968 : LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
876 [ + + - + ]: 275968 : 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 : : */
2427 andres@anarazel.de 882 :UBC 0 : LWLockRelease(PARTITION_LOCK(hash_table, 0));
883 : 0 : return;
884 : : }
885 : : }
886 : :
2427 andres@anarazel.de 887 [ - + ]:CBC 2156 : Assert(new_size_log2 == hash_table->control->size_log2 + 1);
888 : :
889 : : /* Allocate the space for the new table. */
890 : 2156 : new_buckets_shared = dsa_allocate0(hash_table->area,
891 : : sizeof(dsa_pointer) * new_size);
892 : 2156 : new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
893 : :
894 : : /*
895 : : * We've allocated the new bucket array; all that remains to do now is to
896 : : * reinsert all items, which amounts to adjusting all the pointers.
897 : : */
2415 tgl@sss.pgh.pa.us 898 : 2156 : size = ((size_t) 1) << hash_table->control->size_log2;
2427 andres@anarazel.de 899 [ + + ]: 701420 : for (i = 0; i < size; ++i)
900 : : {
901 : 699264 : dsa_pointer item_pointer = hash_table->buckets[i];
902 : :
903 [ + + ]: 759757 : while (DsaPointerIsValid(item_pointer))
904 : : {
905 : : dshash_table_item *item;
906 : : dsa_pointer next_item_pointer;
907 : :
908 : 60493 : item = dsa_get_address(hash_table->area, item_pointer);
909 : 60493 : next_item_pointer = item->next;
910 : 60493 : insert_item_into_bucket(hash_table, item_pointer, item,
911 : 60493 : &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
912 : : new_size_log2)]);
913 : 60493 : item_pointer = next_item_pointer;
914 : : }
915 : : }
916 : :
917 : : /* Swap the hash table into place and free the old one. */
918 : 2156 : old_buckets = hash_table->control->buckets;
919 : 2156 : hash_table->control->buckets = new_buckets_shared;
920 : 2156 : hash_table->control->size_log2 = new_size_log2;
921 : 2156 : hash_table->buckets = new_buckets;
922 : 2156 : dsa_free(hash_table->area, old_buckets);
923 : :
924 : : /* Release all the locks. */
925 [ + + ]: 278124 : for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
926 : 275968 : LWLockRelease(PARTITION_LOCK(hash_table, i));
927 : : }
928 : :
929 : : /*
930 : : * Make sure that our backend-local bucket pointers are up to date. The
931 : : * caller must have locked one lock partition, which prevents resize() from
932 : : * running concurrently.
933 : : */
934 : : static inline void
935 : 1130901 : ensure_valid_bucket_pointers(dshash_table *hash_table)
936 : : {
937 [ + + ]: 1130901 : if (hash_table->size_log2 != hash_table->control->size_log2)
938 : : {
939 : 38680 : hash_table->buckets = dsa_get_address(hash_table->area,
940 : 19340 : hash_table->control->buckets);
941 : 19340 : hash_table->size_log2 = hash_table->control->size_log2;
942 : : }
943 : 1130901 : }
944 : :
945 : : /*
946 : : * Scan a locked bucket for a match, using the provided compare function.
947 : : */
948 : : static inline dshash_table_item *
949 : 1129954 : find_in_bucket(dshash_table *hash_table, const void *key,
950 : : dsa_pointer item_pointer)
951 : : {
952 [ + + ]: 1302905 : while (DsaPointerIsValid(item_pointer))
953 : : {
954 : : dshash_table_item *item;
955 : :
956 : 885420 : item = dsa_get_address(hash_table->area, item_pointer);
957 [ + + ]: 885420 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
958 : 712469 : return item;
959 : 172951 : item_pointer = item->next;
960 : : }
961 : 417485 : return NULL;
962 : : }
963 : :
964 : : /*
965 : : * Insert an already-allocated item into a bucket.
966 : : */
967 : : static void
968 : 303424 : insert_item_into_bucket(dshash_table *hash_table,
969 : : dsa_pointer item_pointer,
970 : : dshash_table_item *item,
971 : : dsa_pointer *bucket)
972 : : {
973 [ - + ]: 303424 : Assert(item == dsa_get_address(hash_table->area, item_pointer));
974 : :
975 : 303424 : item->next = *bucket;
976 : 303424 : *bucket = item_pointer;
977 : 303424 : }
978 : :
979 : : /*
980 : : * Allocate space for an entry with the given key and insert it into the
981 : : * provided bucket.
982 : : */
983 : : static dshash_table_item *
984 : 242931 : insert_into_bucket(dshash_table *hash_table,
985 : : const void *key,
986 : : dsa_pointer *bucket)
987 : : {
988 : : dsa_pointer item_pointer;
989 : : dshash_table_item *item;
990 : :
991 : 242931 : item_pointer = dsa_allocate(hash_table->area,
992 : : hash_table->params.entry_size +
993 : : MAXALIGN(sizeof(dshash_table_item)));
994 : 242931 : item = dsa_get_address(hash_table->area, item_pointer);
48 nathan@postgresql.or 995 :GNC 242931 : copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
2427 andres@anarazel.de 996 :CBC 242931 : insert_item_into_bucket(hash_table, item_pointer, item, bucket);
997 : 242931 : return item;
998 : : }
999 : :
1000 : : /*
1001 : : * Search a bucket for a matching key and delete it.
1002 : : */
1003 : : static bool
1004 : 128 : delete_key_from_bucket(dshash_table *hash_table,
1005 : : const void *key,
1006 : : dsa_pointer *bucket_head)
1007 : : {
1008 [ + + ]: 128 : while (DsaPointerIsValid(*bucket_head))
1009 : : {
1010 : : dshash_table_item *item;
1011 : :
1012 : 94 : item = dsa_get_address(hash_table->area, *bucket_head);
1013 : :
1014 [ + - ]: 94 : if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
1015 : : {
1016 : : dsa_pointer next;
1017 : :
1018 : 94 : next = item->next;
1019 : 94 : dsa_free(hash_table->area, *bucket_head);
1020 : 94 : *bucket_head = next;
1021 : :
1022 : 94 : return true;
1023 : : }
2427 andres@anarazel.de 1024 :UBC 0 : bucket_head = &item->next;
1025 : : }
2427 andres@anarazel.de 1026 :CBC 34 : return false;
1027 : : }
1028 : :
1029 : : /*
1030 : : * Delete the specified item from the bucket.
1031 : : */
1032 : : static bool
1033 : 33174 : delete_item_from_bucket(dshash_table *hash_table,
1034 : : dshash_table_item *item,
1035 : : dsa_pointer *bucket_head)
1036 : : {
1037 [ + - ]: 33482 : while (DsaPointerIsValid(*bucket_head))
1038 : : {
1039 : : dshash_table_item *bucket_item;
1040 : :
1041 : 33482 : bucket_item = dsa_get_address(hash_table->area, *bucket_head);
1042 : :
1043 [ + + ]: 33482 : if (bucket_item == item)
1044 : : {
1045 : : dsa_pointer next;
1046 : :
1047 : 33174 : next = item->next;
1048 : 33174 : dsa_free(hash_table->area, *bucket_head);
1049 : 33174 : *bucket_head = next;
1050 : 33174 : return true;
1051 : : }
1052 : 308 : bucket_head = &bucket_item->next;
1053 : : }
2427 andres@anarazel.de 1054 :UBC 0 : return false;
1055 : : }
1056 : :
1057 : : /*
1058 : : * Compute the hash value for a key.
1059 : : */
1060 : : static inline dshash_hash
2427 andres@anarazel.de 1061 :CBC 1127926 : hash_key(dshash_table *hash_table, const void *key)
1062 : : {
2425 1063 : 1127926 : return hash_table->params.hash_function(key,
1064 : : hash_table->params.key_size,
1065 : : hash_table->arg);
1066 : : }
1067 : :
1068 : : /*
1069 : : * Check whether two keys compare equal.
1070 : : */
1071 : : static inline bool
2427 1072 : 885514 : equal_keys(dshash_table *hash_table, const void *a, const void *b)
1073 : : {
2425 1074 : 885514 : return hash_table->params.compare_function(a, b,
1075 : : hash_table->params.key_size,
1076 : 885514 : hash_table->arg) == 0;
1077 : : }
1078 : :
1079 : : /*
1080 : : * Copy a key.
1081 : : */
1082 : : static inline void
48 nathan@postgresql.or 1083 :GNC 242931 : copy_key(dshash_table *hash_table, void *dest, const void *src)
1084 : : {
1085 : 242931 : hash_table->params.copy_function(dest, src,
1086 : : hash_table->params.key_size,
1087 : : hash_table->arg);
1088 : 242931 : }
|
