Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * shmem_hash.c
4 : * hash table implementation in shared memory
5 : *
6 : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : * A shared memory hash table implementation on top of the named, fixed-size
10 : * shared memory areas managed by shmem.c. Each hash table has its own free
11 : * list, so hash buckets can be reused when an item is deleted.
12 : *
13 : * IDENTIFICATION
14 : * src/backend/storage/ipc/shmem_hash.c
15 : *
16 : *-------------------------------------------------------------------------
17 : */
18 :
19 : #include "postgres.h"
20 :
21 : #include "storage/shmem.h"
22 : #include "storage/shmem_internal.h"
23 : #include "utils/memutils.h"
24 :
25 : /*
26 : * A very simple allocator used to carve out different parts of a hash table
27 : * from a previously allocated contiguous shared memory area.
28 : */
29 : typedef struct shmem_hash_allocator
30 : {
31 : char *next; /* start of free space in the area */
32 : char *end; /* end of the shmem area */
33 : } shmem_hash_allocator;
34 :
35 : static void *ShmemHashAlloc(Size size, void *alloc_arg);
36 :
37 : /*
38 : * ShmemRequestHash -- Request a shared memory hash table.
39 : *
40 : * Similar to ShmemRequestStruct(), but requests a hash table instead of an
41 : * opaque area.
42 : */
43 : void
44 9875 : ShmemRequestHashWithOpts(const ShmemHashOpts *options)
45 : {
46 : ShmemHashOpts *options_copy;
47 :
48 : Assert(options->name != NULL);
49 :
50 9875 : options_copy = MemoryContextAlloc(TopMemoryContext,
51 : sizeof(ShmemHashOpts));
52 9875 : memcpy(options_copy, options, sizeof(ShmemHashOpts));
53 :
54 : /* Set options for the fixed-size area holding the hash table */
55 9875 : options_copy->base.name = options->name;
56 9875 : options_copy->base.size = hash_estimate_size(options_copy->nelems,
57 : options_copy->hash_info.entrysize);
58 :
59 9875 : ShmemRequestInternal(&options_copy->base, SHMEM_KIND_HASH);
60 9875 : }
61 :
62 : void
63 9851 : shmem_hash_init(void *location, ShmemStructOpts *base_options)
64 : {
65 9851 : ShmemHashOpts *options = (ShmemHashOpts *) base_options;
66 9851 : int hash_flags = options->hash_flags;
67 : HTAB *htab;
68 :
69 9851 : options->hash_info.hctl = location;
70 9851 : htab = shmem_hash_create(location, options->base.size, false,
71 : options->name,
72 : options->nelems, &options->hash_info, hash_flags);
73 :
74 9851 : if (options->ptr)
75 9851 : *options->ptr = htab;
76 9851 : }
77 :
78 : void
79 0 : shmem_hash_attach(void *location, ShmemStructOpts *base_options)
80 : {
81 0 : ShmemHashOpts *options = (ShmemHashOpts *) base_options;
82 0 : int hash_flags = options->hash_flags;
83 : HTAB *htab;
84 :
85 : /* attach to it rather than allocate and initialize new space */
86 0 : hash_flags |= HASH_ATTACH;
87 0 : options->hash_info.hctl = location;
88 : Assert(options->hash_info.hctl != NULL);
89 0 : htab = shmem_hash_create(location, options->base.size, true,
90 : options->name,
91 : options->nelems, &options->hash_info, hash_flags);
92 :
93 0 : if (options->ptr)
94 0 : *options->ptr = htab;
95 0 : }
96 :
97 : /*
98 : * ShmemInitHash -- Create and initialize, or attach to, a
99 : * shared memory hash table.
100 : *
101 : * We assume caller is doing some kind of synchronization
102 : * so that two processes don't try to create/initialize the same
103 : * table at once. (In practice, all creations are done in the postmaster
104 : * process; child processes should always be attaching to existing tables.)
105 : *
106 : * nelems is the maximum number of hashtable entries.
107 : *
108 : * *infoP and hash_flags must specify at least the entry sizes and key
109 : * comparison semantics (see hash_create()). Flag bits and values specific
110 : * to shared-memory hash tables are added here, except that callers may
111 : * choose to specify HASH_PARTITION.
112 : *
113 : * Note: This is a legacy interface, kept for backwards compatibility with
114 : * extensions. Use ShmemRequestHash() in new code!
115 : */
116 : HTAB *
117 0 : ShmemInitHash(const char *name, /* table string name for shmem index */
118 : int64 nelems, /* size of the table */
119 : HASHCTL *infoP, /* info about key and bucket size */
120 : int hash_flags) /* info about infoP */
121 : {
122 : bool found;
123 : size_t size;
124 : void *location;
125 :
126 0 : size = hash_estimate_size(nelems, infoP->entrysize);
127 :
128 : /*
129 : * Look it up in the shmem index or allocate.
130 : *
131 : * NOTE: The area is requested internally as SHMEM_KIND_STRUCT instead of
132 : * SHMEM_KIND_HASH. That's correct because we do the hash table
133 : * initialization by calling shmem_hash_create() ourselves. (We don't
134 : * expose the request kind to users; if we did, that would be confusing.)
135 : */
136 0 : location = ShmemInitStruct(name, size, &found);
137 :
138 0 : return shmem_hash_create(location, size, found,
139 : name, nelems, infoP, hash_flags);
140 : }
141 :
142 : /*
143 : * Initialize or attach to a shared hash table in the given shmem region.
144 : *
145 : * This is exposed to allow InitShmemAllocator() to share the logic for
146 : * bootstrapping the ShmemIndex hash table.
147 : */
148 : HTAB *
149 11081 : shmem_hash_create(void *location, size_t size, bool found,
150 : const char *name, int64 nelems, HASHCTL *infoP, int hash_flags)
151 : {
152 : shmem_hash_allocator allocator;
153 :
154 : /*
155 : * Hash tables allocated in shared memory have a fixed directory and have
156 : * all elements allocated upfront. We don't support growing because we'd
157 : * need to grow the underlying shmem region with it.
158 : *
159 : * The shared memory allocator must be specified too.
160 : */
161 11081 : infoP->alloc = ShmemHashAlloc;
162 11081 : infoP->alloc_arg = NULL;
163 11081 : hash_flags |= HASH_SHARED_MEM | HASH_ALLOC | HASH_FIXED_SIZE;
164 :
165 : /*
166 : * if it already exists, attach to it rather than allocate and initialize
167 : * new space
168 : */
169 11081 : if (!found)
170 : {
171 11081 : allocator.next = (char *) location;
172 11081 : allocator.end = (char *) location + size;
173 11081 : infoP->alloc_arg = &allocator;
174 : }
175 : else
176 : {
177 : /* Pass location of hashtable header to hash_create */
178 0 : infoP->hctl = (HASHHDR *) location;
179 0 : hash_flags |= HASH_ATTACH;
180 : }
181 :
182 11081 : return hash_create(name, nelems, infoP, hash_flags);
183 : }
184 :
185 : /*
186 : * ShmemHashAlloc -- alloc callback for shared memory hash tables
187 : *
188 : * Carve out the allocation from a pre-allocated region. All shared memory
189 : * hash tables are initialized with HASH_FIXED_SIZE, so all the allocations
190 : * happen upfront during initialization and no locking is required.
191 : */
192 : static void *
193 718260 : ShmemHashAlloc(Size size, void *alloc_arg)
194 : {
195 718260 : shmem_hash_allocator *allocator = (shmem_hash_allocator *) alloc_arg;
196 : void *result;
197 :
198 718260 : size = MAXALIGN(size);
199 :
200 718260 : if (allocator->end - allocator->next < size)
201 0 : return NULL;
202 718260 : result = allocator->next;
203 718260 : allocator->next += size;
204 :
205 718260 : return result;
206 : }
|
