Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * dynahash.c
4 : : * dynamic chained hash tables
5 : : *
6 : : * dynahash.c supports both local-to-a-backend hash tables and hash tables in
7 : : * shared memory. For shared hash tables, it is the caller's responsibility
8 : : * to provide appropriate access interlocking. The simplest convention is
9 : : * that a single LWLock protects the whole hash table. Searches (HASH_FIND or
10 : : * hash_seq_search) need only shared lock, but any update requires exclusive
11 : : * lock. For heavily-used shared tables, the single-lock approach creates a
12 : : * concurrency bottleneck, so we also support "partitioned" locking wherein
13 : : * there are multiple LWLocks guarding distinct subsets of the table. To use
14 : : * a hash table in partitioned mode, the HASH_PARTITION flag must be given
15 : : * to hash_create. This prevents any attempt to split buckets on-the-fly.
16 : : * Therefore, each hash bucket chain operates independently, and no fields
17 : : * of the hash header change after init except nentries and freeList.
18 : : * (A partitioned table uses multiple copies of those fields, guarded by
19 : : * spinlocks, for additional concurrency.)
20 : : * This lets any subset of the hash buckets be treated as a separately
21 : : * lockable partition. We expect callers to use the low-order bits of a
22 : : * lookup key's hash value as a partition number --- this will work because
23 : : * of the way calc_bucket() maps hash values to bucket numbers.
24 : : *
25 : : * The memory allocator function should match malloc's semantics of returning
26 : : * NULL on failure. (This is essential for hash tables in shared memory.
27 : : * For hash tables in local memory, we used to use palloc() which will throw
28 : : * error on failure; but we no longer do, so it's untested whether this
29 : : * module will still cope with that behavior.)
30 : : *
31 : : * dynahash.c provides support for these types of lookup keys:
32 : : *
33 : : * 1. Null-terminated C strings (truncated if necessary to fit in keysize),
34 : : * compared as though by strcmp(). This is selected by specifying the
35 : : * HASH_STRINGS flag to hash_create.
36 : : *
37 : : * 2. Arbitrary binary data of size keysize, compared as though by memcmp().
38 : : * (Caller must ensure there are no undefined padding bits in the keys!)
39 : : * This is selected by specifying the HASH_BLOBS flag to hash_create.
40 : : *
41 : : * 3. More complex key behavior can be selected by specifying user-supplied
42 : : * hashing, comparison, and/or key-copying functions. At least a hashing
43 : : * function must be supplied; comparison defaults to memcmp() and key copying
44 : : * to memcpy() when a user-defined hashing function is selected.
45 : : *
46 : : * Compared to simplehash, dynahash has the following benefits:
47 : : *
48 : : * - It supports partitioning, which is useful for shared memory access using
49 : : * locks.
50 : : * - Shared memory hashes are allocated in a fixed size area at startup and
51 : : * are discoverable by name from other processes.
52 : : * - Because entries don't need to be moved in the case of hash conflicts,
53 : : * dynahash has better performance for large entries.
54 : : * - Guarantees stable pointers to entries.
55 : : *
56 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
57 : : * Portions Copyright (c) 1994, Regents of the University of California
58 : : *
59 : : *
60 : : * IDENTIFICATION
61 : : * src/backend/utils/hash/dynahash.c
62 : : *
63 : : *-------------------------------------------------------------------------
64 : : */
65 : :
66 : : /*
67 : : * Original comments:
68 : : *
69 : : * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
70 : : * Coded into C, with minor code improvements, and with hsearch(3) interface,
71 : : * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
72 : : * also, hcreate/hdestroy routines added to simulate hsearch(3).
73 : : *
74 : : * These routines simulate hsearch(3) and family, with the important
75 : : * difference that the hash table is dynamic - can grow indefinitely
76 : : * beyond its original size (as supplied to hcreate()).
77 : : *
78 : : * Performance appears to be comparable to that of hsearch(3).
79 : : * The 'source-code' options referred to in hsearch(3)'s 'man' page
80 : : * are not implemented; otherwise functionality is identical.
81 : : *
82 : : * Compilation controls:
83 : : * HASH_STATISTICS causes some usage statistics to be maintained, which can be
84 : : * logged by calling hash_stats().
85 : : *
86 : : * Problems & fixes to ejp@ausmelb.oz. WARNING: relies on pre-processor
87 : : * concatenation property, in probably unnecessary code 'optimization'.
88 : : *
89 : : * Modified margo@postgres.berkeley.edu February 1990
90 : : * added multiple table interface
91 : : * Modified by sullivan@postgres.berkeley.edu April 1990
92 : : * changed ctl structure for shared memory
93 : : */
94 : :
95 : : #include "postgres.h"
96 : :
97 : : #include <limits.h>
98 : :
99 : : #include "access/xact.h"
100 : : #include "common/hashfn.h"
101 : : #include "lib/ilist.h"
102 : : #include "port/pg_bitutils.h"
103 : : #include "storage/shmem.h"
104 : : #include "storage/spin.h"
105 : : #include "utils/memutils.h"
106 : :
107 : :
108 : : /*
109 : : * Constants
110 : : *
111 : : * A hash table has a top-level "directory", each of whose entries points to a
112 : : * "segment" of HASH_SEGSIZE bucket headers. The maximum number of hash
113 : : * buckets is thus dsize * HASH_SEGSIZE (but dsize may be expansible). Of
114 : : * course, the number of records in the table can be larger, but we don't want
115 : : * a whole lot of records per bucket or performance goes down.
116 : : *
117 : : * In a hash table allocated in shared memory, the directory cannot be
118 : : * expanded because it must stay at a fixed address. The directory size is
119 : : * chosen at creation based on the initial number of elements, so even though
120 : : * we support allocating more elements later, performance will suffer if the
121 : : * table grows much beyond the initial size. (Currently, shared memory hash
122 : : * tables are only created by ShmemRequestHash()/ShmemInitHash() though, which
123 : : * doesn't support growing at all.)
124 : : */
125 : : #define HASH_SEGSIZE 256
126 : : #define HASH_SEGSIZE_SHIFT 8 /* must be log2(HASH_SEGSIZE) */
127 : : #define DEF_DIRSIZE 256
128 : :
129 : : /* Number of freelists to be used for a partitioned hash table. */
130 : : #define NUM_FREELISTS 32
131 : :
132 : : /* A hash bucket is a linked list of HASHELEMENTs */
133 : : typedef HASHELEMENT *HASHBUCKET;
134 : :
135 : : /* A hash segment is an array of bucket headers */
136 : : typedef HASHBUCKET *HASHSEGMENT;
137 : :
138 : : /*
139 : : * Per-freelist data.
140 : : *
141 : : * In a partitioned hash table, each freelist is associated with a specific
142 : : * set of hashcodes, as determined by the FREELIST_IDX() macro below.
143 : : * nentries tracks the number of live hashtable entries having those hashcodes
144 : : * (NOT the number of entries in the freelist, as you might expect).
145 : : *
146 : : * The coverage of a freelist might be more or less than one partition, so it
147 : : * needs its own lock rather than relying on caller locking. Relying on that
148 : : * wouldn't work even if the coverage was the same, because of the occasional
149 : : * need to "borrow" entries from another freelist; see get_hash_entry().
150 : : *
151 : : * Using an array of FreeListData instead of separate arrays of mutexes,
152 : : * nentries and freeLists helps to reduce sharing of cache lines between
153 : : * different mutexes.
154 : : */
155 : : typedef struct
156 : : {
157 : : slock_t mutex; /* spinlock for this freelist */
158 : : int64 nentries; /* number of entries in associated buckets */
159 : : HASHELEMENT *freeList; /* chain of free elements */
160 : : } FreeListData;
161 : :
162 : : /*
163 : : * Header structure for a hash table --- contains all changeable info
164 : : *
165 : : * In a shared-memory hash table, the HASHHDR is in shared memory, while
166 : : * each backend has a local HTAB struct. For a non-shared table, there isn't
167 : : * any functional difference between HASHHDR and HTAB, but we separate them
168 : : * anyway to share code between shared and non-shared tables.
169 : : */
170 : : struct HASHHDR
171 : : {
172 : : /*
173 : : * The freelist can become a point of contention in high-concurrency hash
174 : : * tables, so we use an array of freelists, each with its own mutex and
175 : : * nentries count, instead of just a single one. Although the freelists
176 : : * normally operate independently, we will scavenge entries from freelists
177 : : * other than a hashcode's default freelist when necessary.
178 : : *
179 : : * If the hash table is not partitioned, only freeList[0] is used and its
180 : : * spinlock is not used at all; callers' locking is assumed sufficient.
181 : : */
182 : : FreeListData freeList[NUM_FREELISTS];
183 : :
184 : : /* These fields can change, but not in a partitioned table */
185 : : /* Also, dsize can't change in a shared table, even if unpartitioned */
186 : : int64 dsize; /* directory size */
187 : : int64 nsegs; /* number of allocated segments (<= dsize) */
188 : : uint32 max_bucket; /* ID of maximum bucket in use */
189 : : uint32 high_mask; /* mask to modulo into entire table */
190 : : uint32 low_mask; /* mask to modulo into lower half of table */
191 : :
192 : : /* These fields are fixed at hashtable creation */
193 : : Size keysize; /* hash key length in bytes */
194 : : Size entrysize; /* total user element size in bytes */
195 : : int64 num_partitions; /* # partitions (must be power of 2), or 0 */
196 : : int64 max_dsize; /* 'dsize' limit if directory is fixed size */
197 : : int nelem_alloc; /* number of entries to allocate at once */
198 : : bool isfixed; /* if true, don't enlarge */
199 : :
200 : : /* Current directory. In shared tables, this doesn't change */
201 : : HASHSEGMENT *dir;
202 : :
203 : : #ifdef HASH_STATISTICS
204 : :
205 : : /*
206 : : * Count statistics here. NB: stats code doesn't bother with mutex, so
207 : : * counts could be corrupted a bit in a partitioned table.
208 : : */
209 : : uint64 accesses;
210 : : uint64 collisions;
211 : : uint64 expansions;
212 : : #endif
213 : : };
214 : :
215 : : #define IS_PARTITIONED(hctl) ((hctl)->num_partitions != 0)
216 : :
217 : : #define FREELIST_IDX(hctl, hashcode) \
218 : : (IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0)
219 : :
220 : : /*
221 : : * Top control structure for a hashtable --- in a shared table, each backend
222 : : * has its own copy (OK since no fields change at runtime)
223 : : */
224 : : struct HTAB
225 : : {
226 : : HASHHDR *hctl; /* => shared control information */
227 : : HASHSEGMENT *dir; /* directory of segment starts */
228 : : HashValueFunc hash; /* hash function */
229 : : HashCompareFunc match; /* key comparison function */
230 : : HashCopyFunc keycopy; /* key copying function */
231 : : HashAllocFunc alloc; /* memory allocator */
232 : : void *alloc_arg; /* opaque argument passed to allocator */
233 : : MemoryContext hcxt; /* memory context if default allocator used */
234 : : char *tabname; /* table name (for error messages) */
235 : : bool isshared; /* true if table is in shared memory */
236 : :
237 : : /* We keep local copies of these fixed values to reduce contention */
238 : : Size keysize; /* hash key length in bytes */
239 : :
240 : : /*
241 : : * In a USE_VALGRIND build, non-shared hashtables keep an slist chain of
242 : : * all the element blocks they have allocated. This pacifies Valgrind,
243 : : * which would otherwise often claim that the element blocks are "possibly
244 : : * lost" for lack of any non-interior pointers to their starts.
245 : : */
246 : : #ifdef USE_VALGRIND
247 : : slist_head element_blocks;
248 : : #endif
249 : : };
250 : :
251 : : /*
252 : : * Key (also entry) part of a HASHELEMENT
253 : : */
254 : : #define ELEMENTKEY(helem) (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))
255 : :
256 : : /*
257 : : * Obtain element pointer given pointer to key
258 : : */
259 : : #define ELEMENT_FROM_KEY(key) \
260 : : ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))
261 : :
262 : : /*
263 : : * Fast MOD arithmetic, assuming that y is a power of 2 !
264 : : */
265 : : #define MOD(x,y) ((x) & ((y)-1))
266 : :
267 : : /*
268 : : * Private function prototypes
269 : : */
270 : : static void *DynaHashAlloc(Size size, void *alloc_arg);
271 : : static HASHSEGMENT seg_alloc(HTAB *hashp);
272 : : static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx);
273 : : static bool dir_realloc(HTAB *hashp);
274 : : static bool expand_table(HTAB *hashp);
275 : : static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx);
276 : : static void hdefault(HTAB *hashp);
277 : : static int choose_nelem_alloc(Size entrysize);
278 : : static bool init_htab(HTAB *hashp, int64 nelem);
279 : : pg_noreturn static void hash_corrupted(HTAB *hashp);
280 : : static uint32 hash_initial_lookup(HTAB *hashp, uint32 hashvalue,
281 : : HASHBUCKET **bucketptr);
282 : : static int my_log2(int64 num);
283 : : static int64 next_pow2_int64(int64 num);
284 : : static int next_pow2_int(int64 num);
285 : : static void register_seq_scan(HTAB *hashp);
286 : : static void deregister_seq_scan(HTAB *hashp);
287 : : static bool has_seq_scans(HTAB *hashp);
288 : :
289 : :
290 : : /*
291 : : * memory allocation support
292 : : */
293 : : static void *
219 heikki.linnakangas@i 294 :CBC 1790819 : DynaHashAlloc(Size size, void *alloc_arg)
295 : : {
296 : 1790819 : MemoryContext hcxt = (MemoryContext) alloc_arg;
297 : :
298 [ + - - + : 1790819 : Assert(MemoryContextIsValid(hcxt));
- - - - -
- ]
299 : 1790819 : return MemoryContextAllocExtended(hcxt, size, MCXT_ALLOC_NO_OOM);
300 : : }
301 : :
302 : :
303 : : /*
304 : : * HashCompareFunc for string keys
305 : : *
306 : : * Because we copy keys with strlcpy(), they will be truncated at keysize-1
307 : : * bytes, so we can only compare that many ... hence strncmp is almost but
308 : : * not quite the right thing.
309 : : */
310 : : static int
7344 tgl@sss.pgh.pa.us 311 : 606885 : string_compare(const char *key1, const char *key2, Size keysize)
312 : : {
313 : 606885 : return strncmp(key1, key2, keysize - 1);
314 : : }
315 : :
316 : :
317 : : /************************** CREATE ROUTINES **********************/
318 : :
319 : : /*
320 : : * hash_create -- create a new dynamic hash table
321 : : *
322 : : * tabname: a name for the table (for debugging purposes)
323 : : * nelem: maximum number of elements expected
324 : : * *info: additional table parameters, as indicated by flags
325 : : * flags: bitmask indicating which parameters to take from *info
326 : : *
327 : : * The flags value *must* include HASH_ELEM. (Formerly, this was nominally
328 : : * optional, but the default keysize and entrysize values were useless.)
329 : : * The flags value must also include exactly one of HASH_STRINGS, HASH_BLOBS,
330 : : * or HASH_FUNCTION, to define the key hashing semantics (C strings,
331 : : * binary blobs, or custom, respectively). Callers specifying a custom
332 : : * hash function will likely also want to use HASH_COMPARE, and perhaps
333 : : * also HASH_KEYCOPY, to control key comparison and copying.
334 : : * Another often-used flag is HASH_CONTEXT, to allocate the hash table
335 : : * under info->hcxt rather than under TopMemoryContext; the default
336 : : * behavior is only suitable for session-lifespan hash tables.
337 : : * Other flags bits are special-purpose and seldom used, except for those
338 : : * associated with shared-memory hash tables, for which see
339 : : * ShmemRequestHash().
340 : : *
341 : : * Fields in *info are read only when the associated flags bit is set.
342 : : * It is not necessary to initialize other fields of *info.
343 : : * Neither tabname nor *info need persist after the hash_create() call.
344 : : *
345 : : * Note: It is deprecated for callers of hash_create() to explicitly specify
346 : : * string_hash, tag_hash, uint32_hash, or oid_hash. Just set HASH_STRINGS or
347 : : * HASH_BLOBS. Use HASH_FUNCTION only when you want something other than
348 : : * one of these.
349 : : *
350 : : * Note: for a shared-memory hashtable, nelem needs to be a pretty good
351 : : * estimate, since we can't expand the table on the fly. But an unshared
352 : : * hashtable can be expanded on-the-fly, so it's better for nelem to be
353 : : * on the small side and let the table grow if it's exceeded. An overly
354 : : * large nelem will penalize hash_seq_search speed without buying much.
355 : : */
356 : : HTAB *
440 michael@paquier.xyz 357 : 415373 : hash_create(const char *tabname, int64 nelem, const HASHCTL *info, int flags)
358 : : {
359 : : HTAB *hashp;
360 : : HASHHDR *hctl;
361 : : MemoryContext hcxt;
362 : :
363 : : /*
364 : : * Hash tables now allocate space for key and data, but you have to say
365 : : * how much space to allocate.
366 : : */
2151 tgl@sss.pgh.pa.us 367 [ - + ]: 415373 : Assert(flags & HASH_ELEM);
368 [ - + ]: 415373 : Assert(info->keysize > 0);
369 [ - + ]: 415373 : Assert(info->entrysize >= info->keysize);
370 : :
371 : : /*
372 : : * For shared hash tables, we have a local hash header (HTAB struct) that
373 : : * we allocate in TopMemoryContext; all else is in shared memory.
374 : : *
375 : : * For non-shared hash tables, everything including the hash header is in
376 : : * a memory context created specially for the hash table --- this makes
377 : : * hash_destroy very simple. The memory context is made a child of either
378 : : * a context specified by the caller, or TopMemoryContext if nothing is
379 : : * specified.
380 : : *
381 : : * Note that HASH_ALLOC had better be set as well.
382 : : */
7853 383 [ + + ]: 415373 : if (flags & HASH_SHARED_MEM)
384 : : {
385 : : /* Set up to allocate the hash header */
219 heikki.linnakangas@i 386 : 11738 : hcxt = TopMemoryContext;
387 : : }
388 : : else
389 : : {
390 : : /* Create the hash table's private memory context */
7853 tgl@sss.pgh.pa.us 391 [ + + ]: 403635 : if (flags & HASH_CONTEXT)
219 heikki.linnakangas@i 392 : 257037 : hcxt = info->hcxt;
393 : : else
394 : 146598 : hcxt = TopMemoryContext;
395 : 403635 : hcxt = AllocSetContextCreate(hcxt, "dynahash",
396 : : ALLOCSET_DEFAULT_SIZES);
397 : : }
398 : :
399 : : /* Initialize the hash header, plus a copy of the table name */
400 : 415373 : hashp = (HTAB *) MemoryContextAlloc(hcxt,
561 tgl@sss.pgh.pa.us 401 : 415373 : sizeof(HTAB) + strlen(tabname) + 1);
10640 bruce@momjian.us 402 [ + - + - : 4984476 : MemSet(hashp, 0, sizeof(HTAB));
+ - + - +
+ ]
403 : :
7853 tgl@sss.pgh.pa.us 404 : 415373 : hashp->tabname = (char *) (hashp + 1);
9162 405 : 415373 : strcpy(hashp->tabname, tabname);
406 : :
407 : : /* If we have a private context, label it with hashtable's name */
3145 408 [ + + ]: 415373 : if (!(flags & HASH_SHARED_MEM))
219 heikki.linnakangas@i 409 : 403635 : MemoryContextSetIdentifier(hcxt, hashp->tabname);
410 : :
411 : : /*
412 : : * Select the appropriate hash function (see comments at head of file).
413 : : */
10651 bruce@momjian.us 414 [ + + ]: 415373 : if (flags & HASH_FUNCTION)
415 : : {
2151 tgl@sss.pgh.pa.us 416 [ - + ]: 16867 : Assert(!(flags & (HASH_BLOBS | HASH_STRINGS)));
10651 bruce@momjian.us 417 : 16867 : hashp->hash = info->hash;
418 : : }
4340 tgl@sss.pgh.pa.us 419 [ + + ]: 398506 : else if (flags & HASH_BLOBS)
420 : : {
2151 421 [ - + ]: 334040 : Assert(!(flags & HASH_STRINGS));
422 : : /* We can optimize hashing for common key sizes */
4340 423 [ + + ]: 334040 : if (info->keysize == sizeof(uint32))
424 : 235955 : hashp->hash = uint32_hash;
425 : : else
426 : 98085 : hashp->hash = tag_hash;
427 : : }
428 : : else
429 : : {
430 : : /*
431 : : * string_hash used to be considered the default hash method, and in a
432 : : * non-assert build it effectively still is. But we now consider it
433 : : * an assertion error to not say HASH_STRINGS explicitly. To help
434 : : * catch mistaken usage of HASH_STRINGS, we also insist on a
435 : : * reasonably long string length: if the keysize is only 4 or 8 bytes,
436 : : * it's almost certainly an integer or pointer not a string.
437 : : */
2151 438 [ - + ]: 64466 : Assert(flags & HASH_STRINGS);
439 [ - + ]: 64466 : Assert(info->keysize > 8);
440 : :
441 : 64466 : hashp->hash = string_hash;
442 : : }
443 : :
444 : : /*
445 : : * If you don't specify a match function, it defaults to string_compare if
446 : : * you used string_hash, and to memcmp otherwise.
447 : : *
448 : : * Note: explicitly specifying string_hash is deprecated, because this
449 : : * might not work for callers in loadable modules on some platforms due to
450 : : * referencing a trampoline instead of the string_hash function proper.
451 : : * Specify HASH_STRINGS instead.
452 : : */
8479 453 [ + + ]: 415373 : if (flags & HASH_COMPARE)
454 : 9047 : hashp->match = info->match;
455 [ + + ]: 406326 : else if (hashp->hash == string_hash)
7344 456 : 64466 : hashp->match = (HashCompareFunc) string_compare;
457 : : else
8479 458 : 341860 : hashp->match = memcmp;
459 : :
460 : : /*
461 : : * Similarly, the key-copying function defaults to strlcpy or memcpy.
462 : : */
7810 463 [ - + ]: 415373 : if (flags & HASH_KEYCOPY)
7810 tgl@sss.pgh.pa.us 464 :UBC 0 : hashp->keycopy = info->keycopy;
7810 tgl@sss.pgh.pa.us 465 [ + + ]:CBC 415373 : else if (hashp->hash == string_hash)
466 : : {
467 : : /*
468 : : * The signature of keycopy is meant for memcpy(), which returns
469 : : * void*, but strlcpy() returns size_t. Since we never use the return
470 : : * value of keycopy, and size_t is pretty much always the same size as
471 : : * void *, this should be safe. The extra cast in the middle is to
472 : : * avoid warnings from -Wcast-function-type.
473 : : */
2305 peter@eisentraut.org 474 : 64466 : hashp->keycopy = (HashCopyFunc) (pg_funcptr_t) strlcpy;
475 : : }
476 : : else
7810 tgl@sss.pgh.pa.us 477 : 350907 : hashp->keycopy = memcpy;
478 : :
479 : : /* And select the entry allocation function, too. */
7853 480 [ + + ]: 415373 : if (flags & HASH_ALLOC)
481 : : {
482 : 11738 : hashp->alloc = info->alloc;
219 heikki.linnakangas@i 483 : 11738 : hashp->alloc_arg = info->alloc_arg;
484 : : }
485 : : else
486 : : {
7853 tgl@sss.pgh.pa.us 487 : 403635 : hashp->alloc = DynaHashAlloc;
219 heikki.linnakangas@i 488 : 403635 : hashp->alloc_arg = hcxt;
489 : : }
490 : :
10651 bruce@momjian.us 491 [ + + ]: 415373 : if (flags & HASH_SHARED_MEM)
492 : : {
9267 JanWieck@Yahoo.com 493 : 11738 : hashp->hcxt = NULL;
9162 tgl@sss.pgh.pa.us 494 : 11738 : hashp->isshared = true;
495 : :
496 : : /* hash table already exists, we're just attaching to it */
10651 bruce@momjian.us 497 [ - + ]: 11738 : if (flags & HASH_ATTACH)
498 : : {
499 : : /* Caller must pass the pointer to the shared header */
215 heikki.linnakangas@i 500 [ # # ]:UBC 0 : Assert(info->hctl);
501 : 0 : hashp->hctl = info->hctl;
502 : :
503 : : /* make local copies of some heavily-used values */
504 : 0 : hashp->dir = info->hctl->dir;
505 : 0 : hashp->keysize = info->hctl->keysize;
506 : :
10292 bruce@momjian.us 507 : 0 : return hashp;
508 : : }
509 : : }
510 : : else
511 : : {
512 : : /* setup hash table defaults */
10118 tgl@sss.pgh.pa.us 513 :CBC 403635 : hashp->hctl = NULL;
10651 bruce@momjian.us 514 : 403635 : hashp->dir = NULL;
219 heikki.linnakangas@i 515 : 403635 : hashp->hcxt = hcxt;
9162 tgl@sss.pgh.pa.us 516 : 403635 : hashp->isshared = false;
517 : : }
518 : :
519 : : /*
520 : : * Allocate the header structure.
521 : : *
522 : : * XXX: In case of a shared memory hash table, other processes need the
523 : : * pointer to the header to re-find the hash table. There is currently no
524 : : * explicit way to pass it back from here, the caller relies on the fact
525 : : * that this is the first allocation made with the alloc function. That's
526 : : * a little ugly, but works for now.
527 : : */
215 heikki.linnakangas@i 528 : 415373 : hashp->hctl = (HASHHDR *) hashp->alloc(sizeof(HASHHDR), hashp->alloc_arg);
10651 bruce@momjian.us 529 [ - + ]: 415373 : if (!hashp->hctl)
215 heikki.linnakangas@i 530 [ # # ]:UBC 0 : ereport(ERROR,
531 : : (errcode(ERRCODE_OUT_OF_MEMORY),
532 : : errmsg("out of memory")));
533 : :
8049 neilc@samurai.com 534 :CBC 415373 : hdefault(hashp);
535 : :
10651 bruce@momjian.us 536 : 415373 : hctl = hashp->hctl;
537 : :
7411 tgl@sss.pgh.pa.us 538 [ + + ]: 415373 : if (flags & HASH_PARTITION)
539 : : {
540 : : /* Doesn't make sense to partition a local hash table */
541 [ - + ]: 6515 : Assert(flags & HASH_SHARED_MEM);
542 : :
543 : : /*
544 : : * The number of partitions had better be a power of 2. Also, it must
545 : : * be less than INT_MAX (see init_htab()), so call the int version of
546 : : * next_pow2.
547 : : */
5077 548 [ - + ]: 6515 : Assert(info->num_partitions == next_pow2_int(info->num_partitions));
549 : :
7411 550 : 6515 : hctl->num_partitions = info->num_partitions;
551 : : }
552 : :
553 : : /* remember the entry sizes, too */
2151 554 : 415373 : hctl->keysize = info->keysize;
555 : 415373 : hctl->entrysize = info->entrysize;
556 : :
557 : : /* make local copies of heavily-used constant fields */
7411 558 : 415373 : hashp->keysize = hctl->keysize;
559 : :
560 : : /* Build the hash directory structure */
9166 561 [ - + ]: 415373 : if (!init_htab(hashp, nelem))
6995 tgl@sss.pgh.pa.us 562 [ # # ]:UBC 0 : elog(ERROR, "failed to initialize hash table \"%s\"", hashp->tabname);
563 : :
564 : : /*
565 : : * For a shared hash table, preallocate the requested number of elements.
566 : : * This reduces problems with run-time out-of-shared-memory conditions.
567 : : *
568 : : * For a non-shared hash table, preallocate the requested number of
569 : : * elements if it's less than our chosen nelem_alloc. This avoids wasting
570 : : * space if the caller correctly estimates a small table size.
571 : : */
7438 tgl@sss.pgh.pa.us 572 [ + + ]:CBC 415373 : if ((flags & HASH_SHARED_MEM) ||
573 [ + + ]: 403635 : nelem < hctl->nelem_alloc)
574 : : {
575 : : int i,
576 : : freelist_partitions,
577 : : nelem_alloc,
578 : : nelem_alloc_first;
579 : :
580 : : /*
581 : : * If hash table is partitioned, give each freelist an equal share of
582 : : * the initial allocation. Otherwise only freeList[0] is used.
583 : : */
3879 rhaas@postgresql.org 584 [ + + ]: 147297 : if (IS_PARTITIONED(hashp->hctl))
585 : 6515 : freelist_partitions = NUM_FREELISTS;
586 : : else
587 : 140782 : freelist_partitions = 1;
588 : :
589 : 147297 : nelem_alloc = nelem / freelist_partitions;
3393 tgl@sss.pgh.pa.us 590 [ - + ]: 147297 : if (nelem_alloc <= 0)
3879 rhaas@postgresql.org 591 :UBC 0 : nelem_alloc = 1;
592 : :
593 : : /*
594 : : * Make sure we'll allocate all the requested elements; freeList[0]
595 : : * gets the excess if the request isn't divisible by NUM_FREELISTS.
596 : : */
3879 rhaas@postgresql.org 597 [ + + ]:CBC 147297 : if (nelem_alloc * freelist_partitions < nelem)
598 : 61 : nelem_alloc_first =
599 : 61 : nelem - nelem_alloc * (freelist_partitions - 1);
600 : : else
601 : 147236 : nelem_alloc_first = nelem_alloc;
602 : :
603 [ + + ]: 496559 : for (i = 0; i < freelist_partitions; i++)
604 : : {
605 [ + + ]: 349262 : int temp = (i == 0) ? nelem_alloc_first : nelem_alloc;
606 : :
580 tomas.vondra@postgre 607 [ - + ]: 349262 : if (!element_alloc(hashp, temp, i))
580 tomas.vondra@postgre 608 [ # # ]:UBC 0 : ereport(ERROR,
609 : : (errcode(ERRCODE_OUT_OF_MEMORY),
610 : : errmsg("out of memory")));
611 : : }
612 : : }
613 : :
614 : : /* Set isfixed if requested, but not till after we build initial entries */
5687 heikki.linnakangas@i 615 [ + + ]:CBC 415373 : if (flags & HASH_FIXED_SIZE)
468 tgl@sss.pgh.pa.us 616 : 11738 : hctl->isfixed = true;
617 : :
10292 bruce@momjian.us 618 : 415373 : return hashp;
619 : : }
620 : :
621 : : /*
622 : : * Set default HASHHDR parameters.
623 : : */
624 : : static void
10650 625 : 415373 : hdefault(HTAB *hashp)
626 : : {
9142 627 : 415373 : HASHHDR *hctl = hashp->hctl;
628 : :
9166 tgl@sss.pgh.pa.us 629 [ + - + - : 44444911 : MemSet(hctl, 0, sizeof(HASHHDR));
+ - + - +
+ ]
630 : :
7411 631 : 415373 : hctl->num_partitions = 0; /* not partitioned */
632 : :
633 : : /* table has no fixed maximum size */
10651 bruce@momjian.us 634 : 415373 : hctl->max_dsize = NO_MAX_DSIZE;
635 : :
468 tgl@sss.pgh.pa.us 636 : 415373 : hctl->isfixed = false; /* can be enlarged */
637 : :
638 : : #ifdef HASH_STATISTICS
639 : : hctl->accesses = hctl->collisions = hctl->expansions = 0;
640 : : #endif
11076 scrappy@hub.org 641 : 415373 : }
642 : :
643 : : /*
644 : : * Given the user-specified entry size, choose nelem_alloc, ie, how many
645 : : * elements to add to the hash table when we need more.
646 : : */
647 : : static int
7438 tgl@sss.pgh.pa.us 648 : 429571 : choose_nelem_alloc(Size entrysize)
649 : : {
650 : : int nelem_alloc;
651 : : Size elementSize;
652 : : Size allocSize;
653 : :
654 : : /* Each element has a HASHELEMENT header plus user data. */
655 : : /* NB: this had better match element_alloc() */
656 : 429571 : elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);
657 : :
658 : : /*
659 : : * The idea here is to choose nelem_alloc at least 32, but round up so
660 : : * that the allocation request will be a power of 2 or just less. This
661 : : * makes little difference for hash tables in shared memory, but for hash
662 : : * tables managed by palloc, the allocation request will be rounded up to
663 : : * a power of 2 anyway. If we fail to take this into account, we'll waste
664 : : * as much as half the allocated space.
665 : : */
666 : 429571 : allocSize = 32 * 4; /* assume elementSize at least 8 */
667 : : do
668 : : {
669 : 1654283 : allocSize <<= 1;
670 : 1654283 : nelem_alloc = allocSize / elementSize;
671 [ + + ]: 1654283 : } while (nelem_alloc < 32);
672 : :
673 : 429571 : return nelem_alloc;
674 : : }
675 : :
676 : : /*
677 : : * Compute derived fields of hctl and build the initial directory/segment
678 : : * arrays
679 : : */
680 : : static bool
440 michael@paquier.xyz 681 : 415373 : init_htab(HTAB *hashp, int64 nelem)
682 : : {
9142 bruce@momjian.us 683 : 415373 : HASHHDR *hctl = hashp->hctl;
684 : : HASHSEGMENT *segp;
685 : : int nbuckets;
686 : : int nsegs;
687 : : int i;
688 : :
689 : : /*
690 : : * initialize mutexes if it's a partitioned table
691 : : */
7411 tgl@sss.pgh.pa.us 692 [ + + ]: 415373 : if (IS_PARTITIONED(hctl))
3879 rhaas@postgresql.org 693 [ + + ]: 214995 : for (i = 0; i < NUM_FREELISTS; i++)
694 : 208480 : SpinLockInit(&(hctl->freeList[i].mutex));
695 : :
696 : : /*
697 : : * Allocate space for the next greater power of two number of buckets,
698 : : * assuming a desired maximum load factor of 1.
699 : : */
580 tomas.vondra@postgre 700 : 415373 : nbuckets = next_pow2_int(nelem);
701 : :
702 : : /*
703 : : * In a partitioned table, nbuckets must be at least equal to
704 : : * num_partitions; were it less, keys with apparently different partition
705 : : * numbers would map to the same bucket, breaking partition independence.
706 : : * (Normally nbuckets will be much bigger; this is just a safety check.)
707 : : */
708 [ - + ]: 415373 : while (nbuckets < hctl->num_partitions)
580 tomas.vondra@postgre 709 :UBC 0 : nbuckets <<= 1;
710 : :
10651 bruce@momjian.us 711 :CBC 415373 : hctl->max_bucket = hctl->low_mask = nbuckets - 1;
712 : 415373 : hctl->high_mask = (nbuckets << 1) - 1;
713 : :
714 : : /*
715 : : * Figure number of directory segments needed, round up to a power of 2
716 : : */
219 heikki.linnakangas@i 717 : 415373 : nsegs = (nbuckets - 1) / HASH_SEGSIZE + 1;
580 tomas.vondra@postgre 718 : 415373 : nsegs = next_pow2_int(nsegs);
719 : :
720 : : /*
721 : : * Make sure directory is big enough.
722 : : */
215 heikki.linnakangas@i 723 : 415373 : hctl->dsize = Max(DEF_DIRSIZE, nsegs);
724 : :
725 : : /* SHM hash tables have a fixed directory. */
726 [ + + ]: 415373 : if (hashp->isshared)
727 : 11738 : hctl->max_dsize = hctl->dsize;
728 : :
729 : : /* Allocate a directory */
730 : 415373 : hctl->dir = (HASHSEGMENT *)
731 : 415373 : hashp->alloc(hctl->dsize * sizeof(HASHSEGMENT), hashp->alloc_arg);
732 [ - + ]: 415373 : if (!hctl->dir)
215 heikki.linnakangas@i 733 :UBC 0 : return false;
215 heikki.linnakangas@i 734 :CBC 415373 : hashp->dir = hctl->dir;
735 : :
736 : : /* Allocate initial segments */
10651 bruce@momjian.us 737 [ + + ]: 1389750 : for (segp = hashp->dir; hctl->nsegs < nsegs; hctl->nsegs++, segp++)
738 : : {
580 tomas.vondra@postgre 739 : 974377 : *segp = seg_alloc(hashp);
740 [ - + ]: 974377 : if (*segp == NULL)
580 tomas.vondra@postgre 741 :UBC 0 : return false;
742 : : }
743 : :
744 : : /* Choose number of entries to allocate at a time */
580 tomas.vondra@postgre 745 :CBC 415373 : hctl->nelem_alloc = choose_nelem_alloc(hctl->entrysize);
746 : :
9166 tgl@sss.pgh.pa.us 747 : 415373 : return true;
748 : : }
749 : :
750 : : /*
751 : : * Estimate the space needed for a hashtable containing the given number
752 : : * of entries of given size.
753 : : * NOTE: this is used to estimate the footprint of hashtables in shared
754 : : * memory; therefore it does not count HTAB which is in local memory.
755 : : * NB: assumes that all hash structure parameters have default values!
756 : : */
757 : : Size
440 michael@paquier.xyz 758 : 14198 : hash_estimate_size(int64 num_entries, Size entrysize)
759 : : {
760 : : Size size;
761 : : int64 nBuckets,
762 : : nSegments,
763 : : nDirEntries,
764 : : nElementAllocs,
765 : : elementSize,
766 : : elementAllocCnt;
767 : :
768 : : /* estimate number of buckets wanted */
769 : 14198 : nBuckets = next_pow2_int64(num_entries);
770 : : /* # of segments needed for nBuckets */
219 heikki.linnakangas@i 771 : 14198 : nSegments = next_pow2_int64((nBuckets - 1) / HASH_SEGSIZE + 1);
772 : : /* directory entries */
215 773 : 14198 : nDirEntries = Max(DEF_DIRSIZE, nSegments);
774 : :
775 : : /* fixed control info */
7747 tgl@sss.pgh.pa.us 776 : 14198 : size = MAXALIGN(sizeof(HASHHDR)); /* but not HTAB, per above */
777 : : /* directory */
778 : 14198 : size = add_size(size, mul_size(nDirEntries, sizeof(HASHSEGMENT)));
779 : : /* segments */
780 : 14198 : size = add_size(size, mul_size(nSegments,
781 : : MAXALIGN(HASH_SEGSIZE * sizeof(HASHBUCKET))));
782 : : /* elements --- allocated in groups of choose_nelem_alloc() entries */
7438 783 : 14198 : elementAllocCnt = choose_nelem_alloc(entrysize);
7802 784 : 14198 : nElementAllocs = (num_entries - 1) / elementAllocCnt + 1;
7438 785 : 14198 : elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);
7747 786 : 14198 : size = add_size(size,
787 : : mul_size(nElementAllocs,
788 : : mul_size(elementAllocCnt, elementSize)));
789 : :
10118 790 : 14198 : return size;
791 : : }
792 : :
793 : :
794 : : /********************** DESTROY ROUTINES ************************/
795 : :
796 : : void
10650 bruce@momjian.us 797 : 78214 : hash_destroy(HTAB *hashp)
798 : : {
10651 799 [ + - ]: 78214 : if (hashp != NULL)
800 : : {
801 : : /* allocation method must be one we know how to free, too */
7853 tgl@sss.pgh.pa.us 802 [ - + ]: 78214 : Assert(hashp->alloc == DynaHashAlloc);
803 : : /* so this hashtable must have its own context */
9267 JanWieck@Yahoo.com 804 [ - + ]: 78214 : Assert(hashp->hcxt != NULL);
805 : :
443 drowley@postgresql.o 806 : 78214 : hash_stats(__func__, hashp);
807 : :
808 : : /*
809 : : * Free everything by destroying the hash table's memory context.
810 : : */
9267 JanWieck@Yahoo.com 811 : 78214 : MemoryContextDelete(hashp->hcxt);
812 : : }
11076 scrappy@hub.org 813 : 78214 : }
814 : :
815 : : void
443 drowley@postgresql.o 816 : 78214 : hash_stats(const char *caller, HTAB *hashp)
817 : : {
818 : : #ifdef HASH_STATISTICS
819 : : HASHHDR *hctl = hashp->hctl;
820 : :
821 : : elog(DEBUG4,
822 : : "hash_stats: Caller: %s Table Name: \"%s\" Accesses: " UINT64_FORMAT " Collisions: " UINT64_FORMAT " Expansions: " UINT64_FORMAT " Entries: " INT64_FORMAT " Key Size: %zu Max Bucket: %u Segment Count: " INT64_FORMAT,
823 : : caller != NULL ? caller : "(unknown)", hashp->tabname, hctl->accesses,
824 : : hctl->collisions, hctl->expansions, hash_get_num_entries(hashp),
825 : : hctl->keysize, hctl->max_bucket, hctl->nsegs);
826 : : #endif
11076 scrappy@hub.org 827 : 78214 : }
828 : :
829 : : /*******************************SEARCH ROUTINES *****************************/
830 : :
831 : :
832 : : /*
833 : : * get_hash_value -- exported routine to calculate a key's hash value
834 : : *
835 : : * We export this because for partitioned tables, callers need to compute
836 : : * the partition number (from the low-order bits of the hash value) before
837 : : * searching.
838 : : */
839 : : uint32
7411 tgl@sss.pgh.pa.us 840 : 107183607 : get_hash_value(HTAB *hashp, const void *keyPtr)
841 : : {
842 : 107183607 : return hashp->hash(keyPtr, hashp->keysize);
843 : : }
844 : :
845 : : /* Convert a hash value to a bucket number */
846 : : static inline uint32
8479 847 : 243659071 : calc_bucket(HASHHDR *hctl, uint32 hash_val)
848 : : {
849 : : uint32 bucket;
850 : :
10651 bruce@momjian.us 851 : 243659071 : bucket = hash_val & hctl->high_mask;
852 [ + + ]: 243659071 : if (bucket > hctl->max_bucket)
853 : 113966368 : bucket = bucket & hctl->low_mask;
854 : :
9007 tgl@sss.pgh.pa.us 855 : 243659071 : return bucket;
856 : : }
857 : :
858 : : /*
859 : : * hash_search -- look up key in table and perform action
860 : : * hash_search_with_hash_value -- same, with key's hash value already computed
861 : : *
862 : : * action is one of:
863 : : * HASH_FIND: look up key in table
864 : : * HASH_ENTER: look up key in table, creating entry if not present
865 : : * HASH_ENTER_NULL: same, but return NULL if out of memory
866 : : * HASH_REMOVE: look up key in table, remove entry if present
867 : : *
868 : : * Return value is a pointer to the element found/entered/removed if any,
869 : : * or NULL if no match was found. (NB: in the case of the REMOVE action,
870 : : * the result is a dangling pointer that shouldn't be dereferenced!)
871 : : *
872 : : * HASH_ENTER will normally ereport a generic "out of memory" error if
873 : : * it is unable to create a new entry. The HASH_ENTER_NULL operation is
874 : : * the same except it will return NULL if out of memory.
875 : : *
876 : : * If foundPtr isn't NULL, then *foundPtr is set true if we found an
877 : : * existing entry in the table, false otherwise. This is needed in the
878 : : * HASH_ENTER case, but is redundant with the return value otherwise.
879 : : *
880 : : * For hash_search_with_hash_value, the hashvalue parameter must have been
881 : : * calculated with get_hash_value().
882 : : */
883 : : void *
10650 bruce@momjian.us 884 : 145130941 : hash_search(HTAB *hashp,
885 : : const void *keyPtr,
886 : : HASHACTION action,
887 : : bool *foundPtr)
888 : : {
7411 tgl@sss.pgh.pa.us 889 : 145130941 : return hash_search_with_hash_value(hashp,
890 : : keyPtr,
891 : 145130941 : hashp->hash(keyPtr, hashp->keysize),
892 : : action,
893 : : foundPtr);
894 : : }
895 : :
896 : : pg_attribute_no_sanitize_function()
897 : : void *
898 : 241810230 : hash_search_with_hash_value(HTAB *hashp,
899 : : const void *keyPtr,
900 : : uint32 hashvalue,
901 : : HASHACTION action,
902 : : bool *foundPtr)
903 : : {
9142 bruce@momjian.us 904 : 241810230 : HASHHDR *hctl = hashp->hctl;
3393 tgl@sss.pgh.pa.us 905 [ + + ]: 241810230 : int freelist_idx = FREELIST_IDX(hctl, hashvalue);
906 : : Size keysize;
907 : : HASHBUCKET currBucket;
908 : : HASHBUCKET *prevBucketPtr;
909 : : HashCompareFunc match;
910 : :
911 : : #ifdef HASH_STATISTICS
912 : : hctl->accesses++;
913 : : #endif
914 : :
915 : : /*
916 : : * If inserting, check if it is time to split a bucket.
917 : : *
918 : : * NOTE: failure to expand table is not a fatal error, it just means we
919 : : * have to run at higher fill factor than we wanted. However, if we're
920 : : * using the palloc allocator then it will throw error anyway on
921 : : * out-of-memory, so we must do this before modifying the table.
922 : : */
5130 923 [ + + + + ]: 241810230 : if (action == HASH_ENTER || action == HASH_ENTER_NULL)
924 : : {
925 : : /*
926 : : * Can't split if running in partitioned mode, nor if table is the
927 : : * subject of any active hash_seq_search scans.
928 : : */
440 michael@paquier.xyz 929 [ + + ]: 58571699 : if (hctl->freeList[0].nentries > (int64) hctl->max_bucket &&
0 peter@eisentraut.org 930 [ + - + - ]:GNC 429800 : !hctl->isfixed && !IS_PARTITIONED(hctl) &&
5130 tgl@sss.pgh.pa.us 931 [ + - ]:CBC 429800 : !has_seq_scans(hashp))
932 : 429800 : (void) expand_table(hashp);
933 : : }
934 : :
935 : : /*
936 : : * Do the initial lookup
937 : : */
965 michael@paquier.xyz 938 : 241810230 : (void) hash_initial_lookup(hashp, hashvalue, &prevBucketPtr);
7830 tgl@sss.pgh.pa.us 939 : 241810230 : currBucket = *prevBucketPtr;
940 : :
941 : : /*
942 : : * Follow collision chain looking for matching key
943 : : */
944 : 241810230 : match = hashp->match; /* save one fetch in inner loop */
7411 945 : 241810230 : keysize = hashp->keysize; /* ditto */
946 : :
7830 947 [ + + ]: 289945379 : while (currBucket != NULL)
948 : : {
949 [ + + + + ]: 435683897 : if (currBucket->hashvalue == hashvalue &&
950 : 193778035 : match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
951 : 193770713 : break;
952 : 48135149 : prevBucketPtr = &(currBucket->link);
9166 953 : 48135149 : currBucket = *prevBucketPtr;
954 : : #ifdef HASH_STATISTICS
955 : : hctl->collisions++;
956 : : #endif
957 : : }
958 : :
9162 959 [ + + ]: 241810230 : if (foundPtr)
960 : 60132409 : *foundPtr = (bool) (currBucket != NULL);
961 : :
962 : : /*
963 : : * OK, now what?
964 : : */
10651 bruce@momjian.us 965 [ + + + - ]: 241810230 : switch (action)
966 : : {
9162 tgl@sss.pgh.pa.us 967 : 153396369 : case HASH_FIND:
9166 968 [ + + ]: 153396369 : if (currBucket != NULL)
707 peter@eisentraut.org 969 : 140938058 : return ELEMENTKEY(currBucket);
9162 tgl@sss.pgh.pa.us 970 : 12458311 : return NULL;
971 : :
10650 bruce@momjian.us 972 : 29842162 : case HASH_REMOVE:
9166 tgl@sss.pgh.pa.us 973 [ + + ]: 29842162 : if (currBucket != NULL)
974 : : {
975 : : /* if partitioned, must lock to touch nentries and freeList */
4038 rhaas@postgresql.org 976 [ + + ]: 29840317 : if (IS_PARTITIONED(hctl))
3879 977 : 6239448 : SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));
978 : :
979 : : /* delete the record from the appropriate nentries counter. */
980 [ - + ]: 29840317 : Assert(hctl->freeList[freelist_idx].nentries > 0);
981 : 29840317 : hctl->freeList[freelist_idx].nentries--;
982 : :
983 : : /* remove record from hash bucket's chain. */
9166 tgl@sss.pgh.pa.us 984 : 29840317 : *prevBucketPtr = currBucket->link;
985 : :
986 : : /* add the record to the appropriate freelist. */
3879 rhaas@postgresql.org 987 : 29840317 : currBucket->link = hctl->freeList[freelist_idx].freeList;
988 : 29840317 : hctl->freeList[freelist_idx].freeList = currBucket;
989 : :
4038 990 [ + + ]: 29840317 : if (IS_PARTITIONED(hctl))
3879 991 : 6239448 : SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
992 : :
993 : : /*
994 : : * better hope the caller is synchronizing access to this
995 : : * element, because someone else is going to reuse it the next
996 : : * time something is added to the table
997 : : */
707 peter@eisentraut.org 998 : 29840317 : return ELEMENTKEY(currBucket);
999 : : }
9162 tgl@sss.pgh.pa.us 1000 : 1845 : return NULL;
1001 : :
1002 : 58571699 : case HASH_ENTER:
1003 : : case HASH_ENTER_NULL:
1004 : : /* Return existing element if found, else create one */
9166 1005 [ + + ]: 58571699 : if (currBucket != NULL)
707 peter@eisentraut.org 1006 : 22992338 : return ELEMENTKEY(currBucket);
1007 : :
3879 rhaas@postgresql.org 1008 : 35579361 : currBucket = get_hash_entry(hashp, freelist_idx);
9162 tgl@sss.pgh.pa.us 1009 [ - + ]: 35579361 : if (currBucket == NULL)
1010 : : {
1011 : : /* out of memory */
7411 tgl@sss.pgh.pa.us 1012 [ # # ]:UBC 0 : if (action == HASH_ENTER_NULL)
1013 : 0 : return NULL;
1014 : : /* report a generic message */
1015 [ # # ]: 0 : if (hashp->isshared)
1016 [ # # ]: 0 : ereport(ERROR,
1017 : : (errcode(ERRCODE_OUT_OF_MEMORY),
1018 : : errmsg("out of shared memory")));
1019 : : else
1020 [ # # ]: 0 : ereport(ERROR,
1021 : : (errcode(ERRCODE_OUT_OF_MEMORY),
1022 : : errmsg("out of memory")));
1023 : : }
1024 : :
1025 : : /* link into hashbucket chain */
9162 tgl@sss.pgh.pa.us 1026 :CBC 35579361 : *prevBucketPtr = currBucket;
1027 : 35579361 : currBucket->link = NULL;
1028 : :
1029 : : /* copy key into record */
8479 1030 : 35579361 : currBucket->hashvalue = hashvalue;
7810 1031 : 35579361 : hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
1032 : :
1033 : : /*
1034 : : * Caller is expected to fill the data field on return. DO NOT
1035 : : * insert any code that could possibly throw error here, as doing
1036 : : * so would leave the table entry incomplete and hence corrupt the
1037 : : * caller's data structure.
1038 : : */
1039 : :
707 peter@eisentraut.org 1040 : 35579361 : return ELEMENTKEY(currBucket);
1041 : : }
1042 : :
8504 tgl@sss.pgh.pa.us 1043 [ # # ]:UBC 0 : elog(ERROR, "unrecognized hash action code: %d", (int) action);
1044 : :
1045 : : return NULL; /* keep compiler quiet */
1046 : : }
1047 : :
1048 : : /*
1049 : : * hash_update_hash_key -- change the hash key of an existing table entry
1050 : : *
1051 : : * This is equivalent to removing the entry, making a new entry, and copying
1052 : : * over its data, except that the entry never goes to the table's freelist.
1053 : : * Therefore this cannot suffer an out-of-memory failure, even if there are
1054 : : * other processes operating in other partitions of the hashtable.
1055 : : *
1056 : : * Returns true if successful, false if the requested new hash key is already
1057 : : * present. Throws error if the specified entry pointer isn't actually a
1058 : : * table member.
1059 : : *
1060 : : * NB: currently, there is no special case for old and new hash keys being
1061 : : * identical, which means we'll report false for that situation. This is
1062 : : * preferable for existing uses.
1063 : : *
1064 : : * NB: for a partitioned hashtable, caller must hold lock on both relevant
1065 : : * partitions, if the new hash key would belong to a different partition.
1066 : : */
1067 : : pg_attribute_no_sanitize_function()
1068 : : bool
5044 tgl@sss.pgh.pa.us 1069 :CBC 801 : hash_update_hash_key(HTAB *hashp,
1070 : : void *existingEntry,
1071 : : const void *newKeyPtr)
1072 : : {
1073 : 801 : HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry);
1074 : : uint32 newhashvalue;
1075 : : Size keysize;
1076 : : uint32 bucket;
1077 : : uint32 newbucket;
1078 : : HASHBUCKET currBucket;
1079 : : HASHBUCKET *prevBucketPtr;
1080 : : HASHBUCKET *oldPrevPtr;
1081 : : HashCompareFunc match;
1082 : :
1083 : : #ifdef HASH_STATISTICS
1084 : : HASHHDR *hctl = hashp->hctl;
1085 : :
1086 : : hctl->accesses++;
1087 : : #endif
1088 : :
1089 : : /*
1090 : : * Lookup the existing element using its saved hash value. We need to do
1091 : : * this to be able to unlink it from its hash chain, but as a side benefit
1092 : : * we can verify the validity of the passed existingEntry pointer.
1093 : : */
965 michael@paquier.xyz 1094 : 801 : bucket = hash_initial_lookup(hashp, existingElement->hashvalue,
1095 : : &prevBucketPtr);
5044 tgl@sss.pgh.pa.us 1096 : 801 : currBucket = *prevBucketPtr;
1097 : :
1098 [ + - ]: 807 : while (currBucket != NULL)
1099 : : {
1100 [ + + ]: 807 : if (currBucket == existingElement)
1101 : 801 : break;
1102 : 6 : prevBucketPtr = &(currBucket->link);
1103 : 6 : currBucket = *prevBucketPtr;
1104 : : }
1105 : :
1106 [ - + ]: 801 : if (currBucket == NULL)
5044 tgl@sss.pgh.pa.us 1107 [ # # ]:UBC 0 : elog(ERROR, "hash_update_hash_key argument is not in hashtable \"%s\"",
1108 : : hashp->tabname);
1109 : :
5044 tgl@sss.pgh.pa.us 1110 :CBC 801 : oldPrevPtr = prevBucketPtr;
1111 : :
1112 : : /*
1113 : : * Now perform the equivalent of a HASH_ENTER operation to locate the hash
1114 : : * chain we want to put the entry into.
1115 : : */
1116 : 801 : newhashvalue = hashp->hash(newKeyPtr, hashp->keysize);
965 michael@paquier.xyz 1117 : 801 : newbucket = hash_initial_lookup(hashp, newhashvalue, &prevBucketPtr);
5044 tgl@sss.pgh.pa.us 1118 : 801 : currBucket = *prevBucketPtr;
1119 : :
1120 : : /*
1121 : : * Follow collision chain looking for matching key
1122 : : */
1123 : 801 : match = hashp->match; /* save one fetch in inner loop */
1124 : 801 : keysize = hashp->keysize; /* ditto */
1125 : :
1126 [ + + ]: 860 : while (currBucket != NULL)
1127 : : {
1128 [ - + - - ]: 59 : if (currBucket->hashvalue == newhashvalue &&
5044 tgl@sss.pgh.pa.us 1129 :UBC 0 : match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)
1130 : 0 : break;
5044 tgl@sss.pgh.pa.us 1131 :CBC 59 : prevBucketPtr = &(currBucket->link);
1132 : 59 : currBucket = *prevBucketPtr;
1133 : : #ifdef HASH_STATISTICS
1134 : : hctl->collisions++;
1135 : : #endif
1136 : : }
1137 : :
1138 [ - + ]: 801 : if (currBucket != NULL)
5044 tgl@sss.pgh.pa.us 1139 :UBC 0 : return false; /* collision with an existing entry */
1140 : :
5044 tgl@sss.pgh.pa.us 1141 :CBC 801 : currBucket = existingElement;
1142 : :
1143 : : /*
1144 : : * If old and new hash values belong to the same bucket, we need not
1145 : : * change any chain links, and indeed should not since this simplistic
1146 : : * update will corrupt the list if currBucket is the last element. (We
1147 : : * cannot fall out earlier, however, since we need to scan the bucket to
1148 : : * check for duplicate keys.)
1149 : : */
5043 1150 [ + + ]: 801 : if (bucket != newbucket)
1151 : : {
1152 : : /* OK to remove record from old hash bucket's chain. */
1153 : 743 : *oldPrevPtr = currBucket->link;
1154 : :
1155 : : /* link into new hashbucket chain */
1156 : 743 : *prevBucketPtr = currBucket;
1157 : 743 : currBucket->link = NULL;
1158 : : }
1159 : :
1160 : : /* copy new key into record */
5044 1161 : 801 : currBucket->hashvalue = newhashvalue;
1162 : 801 : hashp->keycopy(ELEMENTKEY(currBucket), newKeyPtr, keysize);
1163 : :
1164 : : /* rest of record is untouched */
1165 : :
1166 : 801 : return true;
1167 : : }
1168 : :
1169 : : /*
1170 : : * Allocate a new hashtable entry if possible; return NULL if out of memory.
1171 : : * (Or, if the underlying space allocator throws error for out-of-memory,
1172 : : * we won't return at all.)
1173 : : */
1174 : : static HASHBUCKET
3879 rhaas@postgresql.org 1175 : 35579361 : get_hash_entry(HTAB *hashp, int freelist_idx)
1176 : : {
1177 : 35579361 : HASHHDR *hctl = hashp->hctl;
1178 : : HASHBUCKET newElement;
1179 : :
1180 : : for (;;)
1181 : : {
1182 : : /* if partitioned, must lock to touch nentries and freeList */
4038 1183 [ + + ]: 35962290 : if (IS_PARTITIONED(hctl))
3879 1184 : 6934271 : SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
1185 : :
1186 : : /* try to get an entry from the freelist */
1187 : 35962290 : newElement = hctl->freeList[freelist_idx].freeList;
1188 : :
7411 tgl@sss.pgh.pa.us 1189 [ + + ]: 35962290 : if (newElement != NULL)
1190 : 35544019 : break;
1191 : :
4038 rhaas@postgresql.org 1192 [ + + ]: 418271 : if (IS_PARTITIONED(hctl))
3879 1193 : 35342 : SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
1194 : :
1195 : : /*
1196 : : * No free elements in this freelist. In a partitioned table, there
1197 : : * might be entries in other freelists, but to reduce contention we
1198 : : * prefer to first try to get another chunk of buckets from the main
1199 : : * shmem allocator. If that fails, though, we *MUST* root through all
1200 : : * the other freelists before giving up. There are multiple callers
1201 : : * that assume that they can allocate every element in the initially
1202 : : * requested table size, or that deleting an element guarantees they
1203 : : * can insert a new element, even if shared memory is entirely full.
1204 : : * Failing because the needed element is in a different freelist is
1205 : : * not acceptable.
1206 : : */
580 tomas.vondra@postgre 1207 [ + + ]: 418271 : if (!element_alloc(hashp, hctl->nelem_alloc, freelist_idx))
1208 : : {
1209 : : int borrow_from_idx;
1210 : :
3879 rhaas@postgresql.org 1211 [ - + ]: 35342 : if (!IS_PARTITIONED(hctl))
3879 rhaas@postgresql.org 1212 :UBC 0 : return NULL; /* out of memory */
1213 : :
1214 : : /* try to borrow element from another freelist */
3879 rhaas@postgresql.org 1215 :CBC 35342 : borrow_from_idx = freelist_idx;
1216 : : for (;;)
1217 : : {
1218 : 39063 : borrow_from_idx = (borrow_from_idx + 1) % NUM_FREELISTS;
1219 [ - + ]: 39063 : if (borrow_from_idx == freelist_idx)
3393 tgl@sss.pgh.pa.us 1220 :UBC 0 : break; /* examined all freelists, fail */
1221 : :
3879 rhaas@postgresql.org 1222 :CBC 39063 : SpinLockAcquire(&(hctl->freeList[borrow_from_idx].mutex));
1223 : 39063 : newElement = hctl->freeList[borrow_from_idx].freeList;
1224 : :
1225 [ + + ]: 39063 : if (newElement != NULL)
1226 : : {
1227 : 35342 : hctl->freeList[borrow_from_idx].freeList = newElement->link;
1228 : 35342 : SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
1229 : :
1230 : : /* careful: count the new element in its proper freelist */
1231 : 35342 : SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
1232 : 35342 : hctl->freeList[freelist_idx].nentries++;
1233 : 35342 : SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
1234 : :
3393 tgl@sss.pgh.pa.us 1235 : 35342 : return newElement;
1236 : : }
1237 : :
3879 rhaas@postgresql.org 1238 : 3721 : SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
1239 : : }
1240 : :
1241 : : /* no elements available to borrow either, so out of memory */
3393 tgl@sss.pgh.pa.us 1242 :UBC 0 : return NULL;
1243 : : }
1244 : : }
1245 : :
1246 : : /* remove entry from freelist, bump nentries */
3879 rhaas@postgresql.org 1247 :CBC 35544019 : hctl->freeList[freelist_idx].freeList = newElement->link;
1248 : 35544019 : hctl->freeList[freelist_idx].nentries++;
1249 : :
4038 1250 [ + + ]: 35544019 : if (IS_PARTITIONED(hctl))
3879 1251 : 6898929 : SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
1252 : :
7411 tgl@sss.pgh.pa.us 1253 : 35544019 : return newElement;
1254 : : }
1255 : :
1256 : : /*
1257 : : * hash_get_num_entries -- get the number of entries in a hashtable
1258 : : */
1259 : : int64
1260 : 70376 : hash_get_num_entries(HTAB *hashp)
1261 : : {
1262 : : int i;
440 michael@paquier.xyz 1263 : 70376 : int64 sum = hashp->hctl->freeList[0].nentries;
1264 : :
1265 : : /*
1266 : : * We currently don't bother with acquiring the mutexes; it's only
1267 : : * sensible to call this function if you've got lock on all partitions of
1268 : : * the table.
1269 : : */
3393 tgl@sss.pgh.pa.us 1270 [ + + ]: 70376 : if (IS_PARTITIONED(hashp->hctl))
1271 : : {
1272 [ + + ]: 74112 : for (i = 1; i < NUM_FREELISTS; i++)
1273 : 71796 : sum += hashp->hctl->freeList[i].nentries;
1274 : : }
1275 : :
3879 rhaas@postgresql.org 1276 : 70376 : return sum;
1277 : : }
1278 : :
1279 : : /*
1280 : : * hash_seq_init/_search/_term
1281 : : * Sequentially search through hash table and return
1282 : : * all the elements one by one, return NULL when no more.
1283 : : *
1284 : : * hash_seq_term should be called if and only if the scan is abandoned before
1285 : : * completion; if hash_seq_search returns NULL then it has already done the
1286 : : * end-of-scan cleanup.
1287 : : *
1288 : : * NOTE: caller may delete the returned element before continuing the scan.
1289 : : * However, deleting any other element while the scan is in progress is
1290 : : * UNDEFINED (it might be the one that curIndex is pointing at!). Also,
1291 : : * if elements are added to the table while the scan is in progress, it is
1292 : : * unspecified whether they will be visited by the scan or not.
1293 : : *
1294 : : * NOTE: to use this with a partitioned hashtable, caller had better hold
1295 : : * at least shared lock on all partitions of the table throughout the scan!
1296 : : * We can cope with insertions or deletions by our own backend, but *not*
1297 : : * with concurrent insertions or deletions by another.
1298 : : */
1299 : : void
9438 tgl@sss.pgh.pa.us 1300 : 2822806 : hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
1301 : : {
1302 : 2822806 : status->hashp = hashp;
1303 : 2822806 : status->curBucket = 0;
9166 1304 : 2822806 : status->curEntry = NULL;
820 akorotkov@postgresql 1305 : 2822806 : status->hasHashvalue = false;
0 peter@eisentraut.org 1306 :GNC 2822806 : register_seq_scan(hashp);
9438 tgl@sss.pgh.pa.us 1307 :CBC 2822806 : }
1308 : :
1309 : : /*
1310 : : * Same as above but scan by the given hash value.
1311 : : * See also hash_seq_search().
1312 : : *
1313 : : * NOTE: the default hash function doesn't match syscache hash function.
1314 : : * Thus, if you're going to use this function in syscache callback, make sure
1315 : : * you're using custom hash function. See relatt_cache_syshash()
1316 : : * for example.
1317 : : */
1318 : : void
820 akorotkov@postgresql 1319 : 1240323 : hash_seq_init_with_hash_value(HASH_SEQ_STATUS *status, HTAB *hashp,
1320 : : uint32 hashvalue)
1321 : : {
1322 : : HASHBUCKET *bucketPtr;
1323 : :
1324 : 1240323 : hash_seq_init(status, hashp);
1325 : :
1326 : 1240323 : status->hasHashvalue = true;
1327 : 1240323 : status->hashvalue = hashvalue;
1328 : :
1329 : 1240323 : status->curBucket = hash_initial_lookup(hashp, hashvalue, &bucketPtr);
1330 : 1240323 : status->curEntry = *bucketPtr;
1331 : 1240323 : }
1332 : :
1333 : : void *
9438 tgl@sss.pgh.pa.us 1334 : 36387223 : hash_seq_search(HASH_SEQ_STATUS *status)
1335 : : {
1336 : : HTAB *hashp;
1337 : : HASHHDR *hctl;
1338 : : uint32 max_bucket;
1339 : : int64 segment_num;
1340 : : int64 segment_ndx;
1341 : : HASHSEGMENT segp;
1342 : : uint32 curBucket;
1343 : : HASHELEMENT *curElem;
1344 : :
820 akorotkov@postgresql 1345 [ + + ]: 36387223 : if (status->hasHashvalue)
1346 : : {
1347 : : /*
1348 : : * Scan entries only in the current bucket because only this bucket
1349 : : * can contain entries with the given hash value.
1350 : : */
1351 [ + + ]: 1407580 : while ((curElem = status->curEntry) != NULL)
1352 : : {
1353 : 167257 : status->curEntry = curElem->link;
1354 [ + + ]: 167257 : if (status->hashvalue != curElem->hashvalue)
1355 : 160515 : continue;
1356 : 6742 : return (void *) ELEMENTKEY(curElem);
1357 : : }
1358 : :
1359 : 1240323 : hash_seq_term(status);
1360 : 1240323 : return NULL;
1361 : : }
1362 : :
7853 tgl@sss.pgh.pa.us 1363 [ + + ]: 35140158 : if ((curElem = status->curEntry) != NULL)
1364 : : {
1365 : : /* Continuing scan of curBucket... */
1366 : 9241555 : status->curEntry = curElem->link;
7691 bruce@momjian.us 1367 [ + + ]: 9241555 : if (status->curEntry == NULL) /* end of this bucket */
7853 tgl@sss.pgh.pa.us 1368 : 6631838 : ++status->curBucket;
707 peter@eisentraut.org 1369 : 9241555 : return ELEMENTKEY(curElem);
1370 : : }
1371 : :
1372 : : /*
1373 : : * Search for next nonempty bucket starting at curBucket.
1374 : : */
7853 tgl@sss.pgh.pa.us 1375 : 25898603 : curBucket = status->curBucket;
1376 : 25898603 : hashp = status->hashp;
1377 : 25898603 : hctl = hashp->hctl;
1378 : 25898603 : max_bucket = hctl->max_bucket;
1379 : :
1380 [ + + ]: 25898603 : if (curBucket > max_bucket)
1381 : : {
7133 1382 : 55051 : hash_seq_term(status);
7691 bruce@momjian.us 1383 : 55051 : return NULL; /* search is done */
1384 : : }
1385 : :
1386 : : /*
1387 : : * first find the right segment in the table directory.
1388 : : */
219 heikki.linnakangas@i 1389 : 25843552 : segment_num = curBucket >> HASH_SEGSIZE_SHIFT;
1390 : 25843552 : segment_ndx = MOD(curBucket, HASH_SEGSIZE);
1391 : :
7853 tgl@sss.pgh.pa.us 1392 : 25843552 : segp = hashp->dir[segment_num];
1393 : :
1394 : : /*
1395 : : * Pick up the first item in this bucket's chain. If chain is not empty
1396 : : * we can begin searching it. Otherwise we have to advance to find the
1397 : : * next nonempty bucket. We try to optimize that case since searching a
1398 : : * near-empty hashtable has to iterate this loop a lot.
1399 : : */
1400 [ + + ]: 179828779 : while ((curElem = segp[segment_ndx]) == NULL)
1401 : : {
1402 : : /* empty bucket, advance to next */
1403 [ + + ]: 155489094 : if (++curBucket > max_bucket)
1404 : : {
1405 : 1503867 : status->curBucket = curBucket;
7133 1406 : 1503867 : hash_seq_term(status);
7691 bruce@momjian.us 1407 : 1503867 : return NULL; /* search is done */
1408 : : }
219 heikki.linnakangas@i 1409 [ + + ]: 153985227 : if (++segment_ndx >= HASH_SEGSIZE)
1410 : : {
7853 tgl@sss.pgh.pa.us 1411 : 413972 : segment_num++;
1412 : 413972 : segment_ndx = 0;
1413 : 413972 : segp = hashp->dir[segment_num];
1414 : : }
1415 : : }
1416 : :
1417 : : /* Begin scan of curBucket... */
1418 : 24339685 : status->curEntry = curElem->link;
3424 1419 [ + + ]: 24339685 : if (status->curEntry == NULL) /* end of this bucket */
7853 1420 : 17707774 : ++curBucket;
1421 : 24339685 : status->curBucket = curBucket;
707 peter@eisentraut.org 1422 : 24339685 : return ELEMENTKEY(curElem);
1423 : : }
1424 : :
1425 : : void
7133 tgl@sss.pgh.pa.us 1426 : 2822795 : hash_seq_term(HASH_SEQ_STATUS *status)
1427 : : {
0 peter@eisentraut.org 1428 :GNC 2822795 : deregister_seq_scan(status->hashp);
7133 tgl@sss.pgh.pa.us 1429 :GBC 2822795 : }
1430 : :
1431 : :
1432 : : /********************************* UTILITIES ************************/
1433 : :
1434 : : /*
1435 : : * Expand the table by adding one more hash bucket.
1436 : : */
1437 : : static bool
10650 bruce@momjian.us 1438 :CBC 429800 : expand_table(HTAB *hashp)
1439 : : {
9142 1440 : 429800 : HASHHDR *hctl = hashp->hctl;
1441 : : HASHSEGMENT old_seg,
1442 : : new_seg;
1443 : : int64 old_bucket,
1444 : : new_bucket;
1445 : : int64 new_segnum,
1446 : : new_segndx;
1447 : : int64 old_segnum,
1448 : : old_segndx;
1449 : : HASHBUCKET *oldlink,
1450 : : *newlink;
1451 : : HASHBUCKET currElement,
1452 : : nextElement;
1453 : :
72 heikki.linnakangas@i 1454 [ - + ]: 429800 : Assert(!hctl->isfixed);
7411 tgl@sss.pgh.pa.us 1455 [ - + ]: 429800 : Assert(!IS_PARTITIONED(hctl));
1456 : :
1457 : : #ifdef HASH_STATISTICS
1458 : : hctl->expansions++;
1459 : : #endif
1460 : :
10118 1461 : 429800 : new_bucket = hctl->max_bucket + 1;
219 heikki.linnakangas@i 1462 : 429800 : new_segnum = new_bucket >> HASH_SEGSIZE_SHIFT;
1463 : 429800 : new_segndx = MOD(new_bucket, HASH_SEGSIZE);
1464 : :
10651 bruce@momjian.us 1465 [ + + ]: 429800 : if (new_segnum >= hctl->nsegs)
1466 : : {
1467 : : /* Allocate new segment if necessary -- could fail if dir full */
1468 [ - + ]: 1444 : if (new_segnum >= hctl->dsize)
10026 bruce@momjian.us 1469 [ # # ]:UBC 0 : if (!dir_realloc(hashp))
9166 tgl@sss.pgh.pa.us 1470 : 0 : return false;
10651 bruce@momjian.us 1471 [ - + ]:CBC 1444 : if (!(hashp->dir[new_segnum] = seg_alloc(hashp)))
9166 tgl@sss.pgh.pa.us 1472 :UBC 0 : return false;
10651 bruce@momjian.us 1473 :CBC 1444 : hctl->nsegs++;
1474 : : }
1475 : :
1476 : : /* OK, we created a new bucket */
10118 tgl@sss.pgh.pa.us 1477 : 429800 : hctl->max_bucket++;
1478 : :
1479 : : /*
1480 : : * *Before* changing masks, find old bucket corresponding to same hash
1481 : : * values; values in that bucket may need to be relocated to new bucket.
1482 : : * Note that new_bucket is certainly larger than low_mask at this point,
1483 : : * so we can skip the first step of the regular hash mask calc.
1484 : : */
10020 1485 : 429800 : old_bucket = (new_bucket & hctl->low_mask);
1486 : :
1487 : : /*
1488 : : * If we crossed a power of 2, readjust masks.
1489 : : */
9007 1490 [ + + ]: 429800 : if ((uint32) new_bucket > hctl->high_mask)
1491 : : {
10651 bruce@momjian.us 1492 : 2715 : hctl->low_mask = hctl->high_mask;
9007 tgl@sss.pgh.pa.us 1493 : 2715 : hctl->high_mask = (uint32) new_bucket | hctl->low_mask;
1494 : : }
1495 : :
1496 : : /*
1497 : : * Relocate records to the new bucket. NOTE: because of the way the hash
1498 : : * masking is done in calc_bucket, only one old bucket can need to be
1499 : : * split at this point. With a different way of reducing the hash value,
1500 : : * that might not be true!
1501 : : */
219 heikki.linnakangas@i 1502 : 429800 : old_segnum = old_bucket >> HASH_SEGSIZE_SHIFT;
1503 : 429800 : old_segndx = MOD(old_bucket, HASH_SEGSIZE);
1504 : :
9166 tgl@sss.pgh.pa.us 1505 : 429800 : old_seg = hashp->dir[old_segnum];
1506 : 429800 : new_seg = hashp->dir[new_segnum];
1507 : :
1508 : 429800 : oldlink = &old_seg[old_segndx];
1509 : 429800 : newlink = &new_seg[new_segndx];
1510 : :
1511 : 429800 : for (currElement = *oldlink;
1512 [ + + ]: 1036716 : currElement != NULL;
1513 : 606916 : currElement = nextElement)
1514 : : {
1515 : 606916 : nextElement = currElement->link;
440 michael@paquier.xyz 1516 [ + + ]: 606916 : if ((int64) calc_bucket(hctl, currElement->hashvalue) == old_bucket)
1517 : : {
9166 tgl@sss.pgh.pa.us 1518 : 302561 : *oldlink = currElement;
1519 : 302561 : oldlink = &currElement->link;
1520 : : }
1521 : : else
1522 : : {
1523 : 304355 : *newlink = currElement;
1524 : 304355 : newlink = &currElement->link;
1525 : : }
1526 : : }
1527 : : /* don't forget to terminate the rebuilt hash chains... */
1528 : 429800 : *oldlink = NULL;
1529 : 429800 : *newlink = NULL;
1530 : :
1531 : 429800 : return true;
1532 : : }
1533 : :
1534 : :
1535 : : static bool
10650 bruce@momjian.us 1536 :UBC 0 : dir_realloc(HTAB *hashp)
1537 : : {
1538 : : HASHSEGMENT *p;
1539 : : HASHSEGMENT *old_p;
1540 : : int64 new_dsize;
1541 : : int64 old_dirsize;
1542 : : int64 new_dirsize;
1543 : :
72 heikki.linnakangas@i 1544 [ # # ]: 0 : Assert(!hashp->hctl->isfixed);
10651 bruce@momjian.us 1545 [ # # ]: 0 : if (hashp->hctl->max_dsize != NO_MAX_DSIZE)
9166 tgl@sss.pgh.pa.us 1546 : 0 : return false;
1547 : :
1548 : : /* Reallocate directory */
10118 1549 : 0 : new_dsize = hashp->hctl->dsize << 1;
9166 1550 : 0 : old_dirsize = hashp->hctl->dsize * sizeof(HASHSEGMENT);
1551 : 0 : new_dirsize = new_dsize * sizeof(HASHSEGMENT);
1552 : :
1553 : 0 : old_p = hashp->dir;
219 heikki.linnakangas@i 1554 : 0 : p = (HASHSEGMENT *) hashp->alloc((Size) new_dirsize, hashp->alloc_arg);
1555 : :
10651 bruce@momjian.us 1556 [ # # ]: 0 : if (p != NULL)
1557 : : {
9166 tgl@sss.pgh.pa.us 1558 : 0 : memcpy(p, old_p, old_dirsize);
1559 [ # # # # : 0 : MemSet(((char *) p) + old_dirsize, 0, new_dirsize - old_dirsize);
# # # # #
# ]
215 heikki.linnakangas@i 1560 : 0 : hashp->hctl->dir = p;
9166 tgl@sss.pgh.pa.us 1561 : 0 : hashp->dir = p;
10118 1562 : 0 : hashp->hctl->dsize = new_dsize;
1563 : :
1564 : : /* XXX assume the allocator is palloc, so we know how to free */
7853 1565 [ # # ]: 0 : Assert(hashp->alloc == DynaHashAlloc);
1566 : 0 : pfree(old_p);
1567 : :
9166 1568 : 0 : return true;
1569 : : }
1570 : :
1571 : 0 : return false;
1572 : : }
1573 : :
1574 : :
1575 : : static HASHSEGMENT
10650 bruce@momjian.us 1576 :CBC 975821 : seg_alloc(HTAB *hashp)
1577 : : {
1578 : : HASHSEGMENT segp;
1579 : :
72 heikki.linnakangas@i 1580 [ - + ]: 975821 : Assert(!hashp->hctl->isfixed);
1581 : :
219 1582 : 975821 : segp = (HASHSEGMENT) hashp->alloc(sizeof(HASHBUCKET) * HASH_SEGSIZE, hashp->alloc_arg);
1583 : :
10651 bruce@momjian.us 1584 [ - + ]: 975821 : if (!segp)
9166 tgl@sss.pgh.pa.us 1585 :UBC 0 : return NULL;
1586 : :
219 heikki.linnakangas@i 1587 [ + - + - :CBC 975821 : MemSet(segp, 0, sizeof(HASHBUCKET) * HASH_SEGSIZE);
+ - - + -
- ]
1588 : :
9166 tgl@sss.pgh.pa.us 1589 : 975821 : return segp;
1590 : : }
1591 : :
1592 : : /*
1593 : : * allocate some new elements and link them into the indicated free list
1594 : : */
1595 : : static bool
580 tomas.vondra@postgre 1596 : 767533 : element_alloc(HTAB *hashp, int nelem, int freelist_idx)
1597 : : {
3879 rhaas@postgresql.org 1598 : 767533 : HASHHDR *hctl = hashp->hctl;
1599 : : Size elementSize;
1600 : : Size requestSize;
1601 : : char *allocedBlock;
1602 : : HASHELEMENT *firstElement;
1603 : : HASHELEMENT *tmpElement;
1604 : : HASHELEMENT *prevElement;
1605 : : int i;
1606 : :
468 tgl@sss.pgh.pa.us 1607 [ + + ]: 767533 : if (hctl->isfixed)
580 tomas.vondra@postgre 1608 : 35342 : return false;
1609 : :
1610 : : /* Each element has a HASHELEMENT header plus user data. */
1611 : 732191 : elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);
1612 : :
460 tgl@sss.pgh.pa.us 1613 : 732191 : requestSize = nelem * elementSize;
1614 : :
1615 : : /* Add space for slist_node list link if we need one. */
1616 : : #ifdef USE_VALGRIND
1617 : : if (!hashp->isshared)
1618 : : requestSize += MAXALIGN(sizeof(slist_node));
1619 : : #endif
1620 : :
1621 : : /* Allocate the memory. */
219 heikki.linnakangas@i 1622 : 732191 : allocedBlock = hashp->alloc(requestSize, hashp->alloc_arg);
1623 : :
460 tgl@sss.pgh.pa.us 1624 [ - + ]: 732191 : if (!allocedBlock)
580 tomas.vondra@postgre 1625 :UBC 0 : return false;
1626 : :
1627 : : /*
1628 : : * If USE_VALGRIND, each allocated block of elements of a non-shared
1629 : : * hashtable is chained into a list, so that Valgrind won't think it's
1630 : : * been leaked.
1631 : : */
1632 : : #ifdef USE_VALGRIND
1633 : : if (hashp->isshared)
1634 : : firstElement = (HASHELEMENT *) allocedBlock;
1635 : : else
1636 : : {
1637 : : slist_push_head(&hashp->element_blocks, (slist_node *) allocedBlock);
1638 : : firstElement = (HASHELEMENT *) (allocedBlock + MAXALIGN(sizeof(slist_node)));
1639 : : }
1640 : : #else
460 tgl@sss.pgh.pa.us 1641 :CBC 732191 : firstElement = (HASHELEMENT *) allocedBlock;
1642 : : #endif
1643 : :
1644 : : /* prepare to link all the new entries into the freelist */
7411 1645 : 732191 : prevElement = NULL;
1646 : 732191 : tmpElement = firstElement;
8073 1647 [ + + ]: 99235242 : for (i = 0; i < nelem; i++)
1648 : : {
7411 1649 : 98503051 : tmpElement->link = prevElement;
1650 : 98503051 : prevElement = tmpElement;
9166 1651 : 98503051 : tmpElement = (HASHELEMENT *) (((char *) tmpElement) + elementSize);
1652 : : }
1653 : :
1654 : : /* if partitioned, must lock to touch freeList */
4038 rhaas@postgresql.org 1655 [ + + ]: 732191 : if (IS_PARTITIONED(hctl))
3879 1656 : 208480 : SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
1657 : :
1658 : : /* freelist could be nonempty if two backends did this concurrently */
1659 : 732191 : firstElement->link = hctl->freeList[freelist_idx].freeList;
1660 : 732191 : hctl->freeList[freelist_idx].freeList = prevElement;
1661 : :
4038 1662 [ + + ]: 732191 : if (IS_PARTITIONED(hctl))
3879 1663 : 208480 : SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
1664 : :
580 tomas.vondra@postgre 1665 : 732191 : return true;
1666 : : }
1667 : :
1668 : : /*
1669 : : * Do initial lookup of a bucket for the given hash value, retrieving its
1670 : : * bucket number and its hash bucket.
1671 : : */
1672 : : static inline uint32
965 michael@paquier.xyz 1673 : 243052155 : hash_initial_lookup(HTAB *hashp, uint32 hashvalue, HASHBUCKET **bucketptr)
1674 : : {
1675 : 243052155 : HASHHDR *hctl = hashp->hctl;
1676 : : HASHSEGMENT segp;
1677 : : int64 segment_num;
1678 : : int64 segment_ndx;
1679 : : uint32 bucket;
1680 : :
1681 : 243052155 : bucket = calc_bucket(hctl, hashvalue);
1682 : :
219 heikki.linnakangas@i 1683 : 243052155 : segment_num = bucket >> HASH_SEGSIZE_SHIFT;
1684 : 243052155 : segment_ndx = MOD(bucket, HASH_SEGSIZE);
1685 : :
965 michael@paquier.xyz 1686 : 243052155 : segp = hashp->dir[segment_num];
1687 : :
1688 [ - + ]: 243052155 : if (segp == NULL)
965 michael@paquier.xyz 1689 :UBC 0 : hash_corrupted(hashp);
1690 : :
965 michael@paquier.xyz 1691 :CBC 243052155 : *bucketptr = &segp[segment_ndx];
1692 : 243052155 : return bucket;
1693 : : }
1694 : :
1695 : : /* complain when we have detected a corrupted hashtable */
1696 : : static void
9162 tgl@sss.pgh.pa.us 1697 :UBC 0 : hash_corrupted(HTAB *hashp)
1698 : : {
1699 : : /*
1700 : : * If the corruption is in a shared hashtable, we'd better force a
1701 : : * systemwide restart. Otherwise, just shut down this one backend.
1702 : : */
1703 [ # # ]: 0 : if (hashp->isshared)
8504 1704 [ # # ]: 0 : elog(PANIC, "hash table \"%s\" corrupted", hashp->tabname);
1705 : : else
1706 [ # # ]: 0 : elog(FATAL, "hash table \"%s\" corrupted", hashp->tabname);
1707 : : }
1708 : :
1709 : : /* calculate ceil(log base 2) of num */
1710 : : static int
440 michael@paquier.xyz 1711 :CBC 865657 : my_log2(int64 num)
1712 : : {
1713 : : /*
1714 : : * guard against too-large input, which would be invalid for
1715 : : * pg_ceil_log2_*()
1716 : : */
1717 [ - + ]: 865657 : if (num > PG_INT64_MAX / 2)
440 michael@paquier.xyz 1718 :UBC 0 : num = PG_INT64_MAX / 2;
1719 : :
2402 drowley@postgresql.o 1720 :CBC 865657 : return pg_ceil_log2_64(num);
1721 : : }
1722 : :
1723 : : /* calculate first power of 2 >= num, bounded to what will fit in a int64 */
1724 : : static int64
440 michael@paquier.xyz 1725 : 28396 : next_pow2_int64(int64 num)
1726 : : {
1727 : : /* my_log2's internal range check is sufficient */
200 peter@eisentraut.org 1728 : 28396 : return INT64CONST(1) << my_log2(num);
1729 : : }
1730 : :
1731 : : /* calculate first power of 2 >= num, bounded to what will fit in an int */
1732 : : static int
440 michael@paquier.xyz 1733 : 837261 : next_pow2_int(int64 num)
1734 : : {
5077 tgl@sss.pgh.pa.us 1735 [ - + ]: 837261 : if (num > INT_MAX / 2)
5077 tgl@sss.pgh.pa.us 1736 :UBC 0 : num = INT_MAX / 2;
5077 tgl@sss.pgh.pa.us 1737 :CBC 837261 : return 1 << my_log2(num);
1738 : : }
1739 : :
1740 : :
1741 : : /************************* SEQ SCAN TRACKING ************************/
1742 : :
1743 : : /*
1744 : : * We track active hash_seq_search scans here. The need for this mechanism
1745 : : * comes from the fact that a scan will get confused if a bucket split occurs
1746 : : * while it's in progress: it might visit entries twice, or even miss some
1747 : : * entirely (if it's partway through the same bucket that splits). Hence
1748 : : * we want to inhibit bucket splits if there are any active scans on the
1749 : : * table being inserted into. This is a fairly rare case in current usage,
1750 : : * so just postponing the split until the next insertion seems sufficient.
1751 : : *
1752 : : * Given present usages of the function, only a few scans are likely to be
1753 : : * open concurrently; so a finite-size stack of open scans seems sufficient,
1754 : : * and we don't worry that linear search is too slow. Note that we do
1755 : : * allow multiple scans of the same hashtable to be open concurrently.
1756 : : *
1757 : : * This mechanism can support concurrent scan and insertion in a shared
1758 : : * hashtable if it's the same backend doing both. It would fail otherwise,
1759 : : * but locking reasons seem to preclude any such scenario anyway, so we don't
1760 : : * worry.
1761 : : *
1762 : : * This arrangement is reasonably robust if a transient hashtable is deleted
1763 : : * without notifying us. The absolute worst case is we might inhibit splits
1764 : : * in another table created later at exactly the same address. We will give
1765 : : * a warning at transaction end for reference leaks, so any bugs leading to
1766 : : * lack of notification should be easy to catch.
1767 : : */
1768 : :
1769 : : #define MAX_SEQ_SCANS 100
1770 : :
1771 : : static HTAB *seq_scan_tables[MAX_SEQ_SCANS]; /* tables being scanned */
1772 : : static int seq_scan_level[MAX_SEQ_SCANS]; /* subtransaction nest level */
1773 : : static int num_seq_scans = 0;
1774 : :
1775 : :
1776 : : /* Register a table as having an active hash_seq_search scan */
1777 : : static void
7133 1778 : 2822806 : register_seq_scan(HTAB *hashp)
1779 : : {
1780 [ - + ]: 2822806 : if (num_seq_scans >= MAX_SEQ_SCANS)
6995 tgl@sss.pgh.pa.us 1781 [ # # ]:UBC 0 : elog(ERROR, "too many active hash_seq_search scans, cannot start one on \"%s\"",
1782 : : hashp->tabname);
7133 tgl@sss.pgh.pa.us 1783 :CBC 2822806 : seq_scan_tables[num_seq_scans] = hashp;
1784 : 2822806 : seq_scan_level[num_seq_scans] = GetCurrentTransactionNestLevel();
1785 : 2822806 : num_seq_scans++;
1786 : 2822806 : }
1787 : :
1788 : : /* Deregister an active scan */
1789 : : static void
1790 : 2822795 : deregister_seq_scan(HTAB *hashp)
1791 : : {
1792 : : int i;
1793 : :
1794 : : /* Search backward since it's most likely at the stack top */
1795 [ + - ]: 2822795 : for (i = num_seq_scans - 1; i >= 0; i--)
1796 : : {
1797 [ + - ]: 2822795 : if (seq_scan_tables[i] == hashp)
1798 : : {
1799 : 2822795 : seq_scan_tables[i] = seq_scan_tables[num_seq_scans - 1];
1800 : 2822795 : seq_scan_level[i] = seq_scan_level[num_seq_scans - 1];
1801 : 2822795 : num_seq_scans--;
1802 : 2822795 : return;
1803 : : }
1804 : : }
7133 tgl@sss.pgh.pa.us 1805 [ # # ]:UBC 0 : elog(ERROR, "no hash_seq_search scan for hash table \"%s\"",
1806 : : hashp->tabname);
1807 : : }
1808 : :
1809 : : /* Check if a table has any active scan */
1810 : : static bool
7133 tgl@sss.pgh.pa.us 1811 :CBC 429800 : has_seq_scans(HTAB *hashp)
1812 : : {
1813 : : int i;
1814 : :
1815 [ + + ]: 430119 : for (i = 0; i < num_seq_scans; i++)
1816 : : {
1817 [ - + ]: 319 : if (seq_scan_tables[i] == hashp)
7133 tgl@sss.pgh.pa.us 1818 :UBC 0 : return true;
1819 : : }
7133 tgl@sss.pgh.pa.us 1820 :CBC 429800 : return false;
1821 : : }
1822 : :
1823 : : /* Clean up any open scans at end of transaction */
1824 : : void
1825 : 430416 : AtEOXact_HashTables(bool isCommit)
1826 : : {
1827 : : /*
1828 : : * During abort cleanup, open scans are expected; just silently clean 'em
1829 : : * out. An open scan at commit means someone forgot a hash_seq_term()
1830 : : * call, so complain.
1831 : : *
1832 : : * Note: it's tempting to try to print the tabname here, but refrain for
1833 : : * fear of touching deallocated memory. This isn't a user-facing message
1834 : : * anyway, so it needn't be pretty.
1835 : : */
1836 [ + + ]: 430416 : if (isCommit)
1837 : : {
1838 : : int i;
1839 : :
1840 [ - + ]: 394540 : for (i = 0; i < num_seq_scans; i++)
1841 : : {
7133 tgl@sss.pgh.pa.us 1842 [ # # ]:UBC 0 : elog(WARNING, "leaked hash_seq_search scan for hash table %p",
1843 : : seq_scan_tables[i]);
1844 : : }
1845 : : }
7133 tgl@sss.pgh.pa.us 1846 :CBC 430416 : num_seq_scans = 0;
1847 : 430416 : }
1848 : :
1849 : : /* Clean up any open scans at end of subtransaction */
1850 : : void
1851 : 23004 : AtEOSubXact_HashTables(bool isCommit, int nestDepth)
1852 : : {
1853 : : int i;
1854 : :
1855 : : /*
1856 : : * Search backward to make cleanup easy. Note we must check all entries,
1857 : : * not only those at the end of the array, because deletion technique
1858 : : * doesn't keep them in order.
1859 : : */
1860 [ - + ]: 23004 : for (i = num_seq_scans - 1; i >= 0; i--)
1861 : : {
7133 tgl@sss.pgh.pa.us 1862 [ # # ]:UBC 0 : if (seq_scan_level[i] >= nestDepth)
1863 : : {
1864 [ # # ]: 0 : if (isCommit)
1865 [ # # ]: 0 : elog(WARNING, "leaked hash_seq_search scan for hash table %p",
1866 : : seq_scan_tables[i]);
1867 : 0 : seq_scan_tables[i] = seq_scan_tables[num_seq_scans - 1];
1868 : 0 : seq_scan_level[i] = seq_scan_level[num_seq_scans - 1];
1869 : 0 : num_seq_scans--;
1870 : : }
1871 : : }
7133 tgl@sss.pgh.pa.us 1872 :CBC 23004 : }
|
