Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * combocid.c
4 : : * Combo command ID support routines
5 : : *
6 : : * Before version 8.3, HeapTupleHeaderData had separate fields for cmin
7 : : * and cmax. To reduce the header size, cmin and cmax are now overlaid
8 : : * in the same field in the header. That usually works because you rarely
9 : : * insert and delete a tuple in the same transaction, and we don't need
10 : : * either field to remain valid after the originating transaction exits.
11 : : * To make it work when the inserting transaction does delete the tuple,
12 : : * we create a "combo" command ID and store that in the tuple header
13 : : * instead of cmin and cmax. The combo command ID can be mapped to the
14 : : * real cmin and cmax using a backend-private array, which is managed by
15 : : * this module.
16 : : *
17 : : * To allow reusing existing combo CIDs, we also keep a hash table that
18 : : * maps cmin,cmax pairs to combo CIDs. This keeps the data structure size
19 : : * reasonable in most cases, since the number of unique pairs used by any
20 : : * one transaction is likely to be small.
21 : : *
22 : : * With a 32-bit combo command id we can represent 2^32 distinct cmin,cmax
23 : : * combinations. In the most perverse case where each command deletes a tuple
24 : : * generated by every previous command, the number of combo command ids
25 : : * required for N commands is N*(N+1)/2. That means that in the worst case,
26 : : * that's enough for 92682 commands. In practice, you'll run out of memory
27 : : * and/or disk space way before you reach that limit.
28 : : *
29 : : * The array and hash table are kept in TopTransactionContext, and are
30 : : * destroyed at the end of each transaction.
31 : : *
32 : : *
33 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
34 : : * Portions Copyright (c) 1994, Regents of the University of California
35 : : *
36 : : * IDENTIFICATION
37 : : * src/backend/utils/time/combocid.c
38 : : *
39 : : *-------------------------------------------------------------------------
40 : : */
41 : :
42 : : #include "postgres.h"
43 : :
44 : : #include "access/htup_details.h"
45 : : #include "access/xact.h"
46 : : #include "miscadmin.h"
47 : : #include "storage/shmem.h"
48 : : #include "utils/combocid.h"
49 : : #include "utils/hsearch.h"
50 : : #include "utils/memutils.h"
51 : :
52 : : /* Hash table to lookup combo CIDs by cmin and cmax */
53 : : static HTAB *comboHash = NULL;
54 : :
55 : : /* Key and entry structures for the hash table */
56 : : typedef struct
57 : : {
58 : : CommandId cmin;
59 : : CommandId cmax;
60 : : } ComboCidKeyData;
61 : :
62 : : typedef ComboCidKeyData *ComboCidKey;
63 : :
64 : : typedef struct
65 : : {
66 : : ComboCidKeyData key;
67 : : CommandId combocid;
68 : : } ComboCidEntryData;
69 : :
70 : : typedef ComboCidEntryData *ComboCidEntry;
71 : :
72 : : /* Initial size of the hash table */
73 : : #define CCID_HASH_SIZE 100
74 : :
75 : :
76 : : /*
77 : : * An array of cmin,cmax pairs, indexed by combo command id.
78 : : * To convert a combo CID to cmin and cmax, you do a simple array lookup.
79 : : */
80 : : static ComboCidKey comboCids = NULL;
81 : : static int usedComboCids = 0; /* number of elements in comboCids */
82 : : static int sizeComboCids = 0; /* allocated size of array */
83 : :
84 : : /* Initial size of the array */
85 : : #define CCID_ARRAY_SIZE 100
86 : :
87 : :
88 : : /* prototypes for internal functions */
89 : : static CommandId GetComboCommandId(CommandId cmin, CommandId cmax);
90 : : static CommandId GetRealCmin(CommandId combocid);
91 : : static CommandId GetRealCmax(CommandId combocid);
92 : :
93 : :
94 : : /**** External API ****/
95 : :
96 : : /*
97 : : * GetCmin and GetCmax assert that they are only called in situations where
98 : : * they make sense, that is, can deliver a useful answer. If you have
99 : : * reason to examine a tuple's t_cid field from a transaction other than
100 : : * the originating one, use HeapTupleHeaderGetRawCommandId() directly.
101 : : */
102 : :
103 : : CommandId
104 : 3414364 : HeapTupleHeaderGetCmin(const HeapTupleHeaderData *tup)
105 : : {
106 : 3414364 : CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
107 : :
108 [ + - ]: 3414364 : Assert(!(tup->t_infomask & HEAP_MOVED));
109 [ + - ]: 3414364 : Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
110 : :
111 [ + + ]: 3414364 : if (tup->t_infomask & HEAP_COMBOCID)
112 : 931301 : return GetRealCmin(cid);
113 : : else
114 : 2483063 : return cid;
115 : 3414364 : }
116 : :
117 : : CommandId
118 : 964347 : HeapTupleHeaderGetCmax(const HeapTupleHeaderData *tup)
119 : : {
120 : 964347 : CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
121 : :
122 [ + - ]: 964347 : Assert(!(tup->t_infomask & HEAP_MOVED));
123 : :
124 : : /*
125 : : * Because GetUpdateXid() performs memory allocations if xmax is a
126 : : * multixact we can't Assert() if we're inside a critical section. This
127 : : * weakens the check, but not using GetCmax() inside one would complicate
128 : : * things too much.
129 : : */
130 [ + - + - ]: 964347 : Assert(CritSectionCount > 0 ||
131 : : TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tup)));
132 : :
133 [ + + ]: 964347 : if (tup->t_infomask & HEAP_COMBOCID)
134 : 931249 : return GetRealCmax(cid);
135 : : else
136 : 33098 : return cid;
137 : 964347 : }
138 : :
139 : : /*
140 : : * Given a tuple we are about to delete, determine the correct value to store
141 : : * into its t_cid field.
142 : : *
143 : : * If we don't need a combo CID, *cmax is unchanged and *iscombo is set to
144 : : * false. If we do need one, *cmax is replaced by a combo CID and *iscombo
145 : : * is set to true.
146 : : *
147 : : * The reason this is separate from the actual HeapTupleHeaderSetCmax()
148 : : * operation is that this could fail due to out-of-memory conditions. Hence
149 : : * we need to do this before entering the critical section that actually
150 : : * changes the tuple in shared buffers.
151 : : */
152 : : void
153 : 327930 : HeapTupleHeaderAdjustCmax(const HeapTupleHeaderData *tup,
154 : : CommandId *cmax,
155 : : bool *iscombo)
156 : : {
157 : : /*
158 : : * If we're marking a tuple deleted that was inserted by (any
159 : : * subtransaction of) our transaction, we need to use a combo command id.
160 : : * Test for HeapTupleHeaderXminCommitted() first, because it's cheaper
161 : : * than a TransactionIdIsCurrentTransactionId call.
162 : : */
163 [ + + + + ]: 327930 : if (!HeapTupleHeaderXminCommitted(tup) &&
164 : 15259 : TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tup)))
165 : : {
166 : 15167 : CommandId cmin = HeapTupleHeaderGetCmin(tup);
167 : :
168 : 15167 : *cmax = GetComboCommandId(cmin, *cmax);
169 : 15167 : *iscombo = true;
170 : 15167 : }
171 : : else
172 : : {
173 : 312763 : *iscombo = false;
174 : : }
175 : 327930 : }
176 : :
177 : : /*
178 : : * Combo command ids are only interesting to the inserting and deleting
179 : : * transaction, so we can forget about them at the end of transaction.
180 : : */
181 : : void
182 : 57914 : AtEOXact_ComboCid(void)
183 : : {
184 : : /*
185 : : * Don't bother to pfree. These are allocated in TopTransactionContext, so
186 : : * they're going to go away at the end of transaction anyway.
187 : : */
188 : 57914 : comboHash = NULL;
189 : :
190 : 57914 : comboCids = NULL;
191 : 57914 : usedComboCids = 0;
192 : 57914 : sizeComboCids = 0;
193 : 57914 : }
194 : :
195 : :
196 : : /**** Internal routines ****/
197 : :
198 : : /*
199 : : * Get a combo command id that maps to cmin and cmax.
200 : : *
201 : : * We try to reuse old combo command ids when possible.
202 : : */
203 : : static CommandId
204 : 24700 : GetComboCommandId(CommandId cmin, CommandId cmax)
205 : : {
206 : 24700 : CommandId combocid;
207 : 24700 : ComboCidKeyData key;
208 : 24700 : ComboCidEntry entry;
209 : 24700 : bool found;
210 : :
211 : : /*
212 : : * Create the hash table and array the first time we need to use combo
213 : : * cids in the transaction.
214 : : */
215 [ + + ]: 24700 : if (comboHash == NULL)
216 : : {
217 : 4393 : HASHCTL hash_ctl;
218 : :
219 : : /* Make array first; existence of hash table asserts array exists */
220 : 4393 : comboCids = (ComboCidKeyData *)
221 : 4393 : MemoryContextAlloc(TopTransactionContext,
222 : : sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
223 : 4393 : sizeComboCids = CCID_ARRAY_SIZE;
224 : 4393 : usedComboCids = 0;
225 : :
226 : 4393 : hash_ctl.keysize = sizeof(ComboCidKeyData);
227 : 4393 : hash_ctl.entrysize = sizeof(ComboCidEntryData);
228 : 4393 : hash_ctl.hcxt = TopTransactionContext;
229 : :
230 : 4393 : comboHash = hash_create("Combo CIDs",
231 : : CCID_HASH_SIZE,
232 : : &hash_ctl,
233 : : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
234 : 4393 : }
235 : :
236 : : /*
237 : : * Grow the array if there's not at least one free slot. We must do this
238 : : * before possibly entering a new hashtable entry, else failure to
239 : : * repalloc would leave a corrupt hashtable entry behind.
240 : : */
241 [ + + ]: 24700 : if (usedComboCids >= sizeComboCids)
242 : : {
243 : 4 : int newsize = sizeComboCids * 2;
244 : :
245 : 4 : comboCids = (ComboCidKeyData *)
246 : 4 : repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
247 : 4 : sizeComboCids = newsize;
248 : 4 : }
249 : :
250 : : /* Lookup or create a hash entry with the desired cmin/cmax */
251 : :
252 : : /* We assume there is no struct padding in ComboCidKeyData! */
253 : 24700 : key.cmin = cmin;
254 : 24700 : key.cmax = cmax;
255 : 24700 : entry = (ComboCidEntry) hash_search(comboHash,
256 : : &key,
257 : : HASH_ENTER,
258 : : &found);
259 : :
260 [ + + ]: 24700 : if (found)
261 : : {
262 : : /* Reuse an existing combo CID */
263 : 5065 : return entry->combocid;
264 : : }
265 : :
266 : : /* We have to create a new combo CID; we already made room in the array */
267 : 19635 : combocid = usedComboCids;
268 : :
269 : 19635 : comboCids[combocid].cmin = cmin;
270 : 19635 : comboCids[combocid].cmax = cmax;
271 : 19635 : usedComboCids++;
272 : :
273 : 19635 : entry->combocid = combocid;
274 : :
275 : 19635 : return combocid;
276 : 24700 : }
277 : :
278 : : static CommandId
279 : 931301 : GetRealCmin(CommandId combocid)
280 : : {
281 [ + - ]: 931301 : Assert(combocid < usedComboCids);
282 : 931301 : return comboCids[combocid].cmin;
283 : : }
284 : :
285 : : static CommandId
286 : 931249 : GetRealCmax(CommandId combocid)
287 : : {
288 [ + - ]: 931249 : Assert(combocid < usedComboCids);
289 : 931249 : return comboCids[combocid].cmax;
290 : : }
291 : :
292 : : /*
293 : : * Estimate the amount of space required to serialize the current combo CID
294 : : * state.
295 : : */
296 : : Size
297 : 155 : EstimateComboCIDStateSpace(void)
298 : : {
299 : 155 : Size size;
300 : :
301 : : /* Add space required for saving usedComboCids */
302 : 155 : size = sizeof(int);
303 : :
304 : : /* Add space required for saving ComboCidKeyData */
305 : 155 : size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
306 : :
307 : 310 : return size;
308 : 155 : }
309 : :
310 : : /*
311 : : * Serialize the combo CID state into the memory, beginning at start_address.
312 : : * maxsize should be at least as large as the value returned by
313 : : * EstimateComboCIDStateSpace.
314 : : */
315 : : void
316 : 155 : SerializeComboCIDState(Size maxsize, char *start_address)
317 : : {
318 : 155 : char *endptr;
319 : :
320 : : /* First, we store the number of currently-existing combo CIDs. */
321 : 155 : *(int *) start_address = usedComboCids;
322 : :
323 : : /* If maxsize is too small, throw an error. */
324 : 310 : endptr = start_address + sizeof(int) +
325 : 155 : (sizeof(ComboCidKeyData) * usedComboCids);
326 [ + - ]: 155 : if (endptr < start_address || endptr > start_address + maxsize)
327 [ # # # # ]: 0 : elog(ERROR, "not enough space to serialize ComboCID state");
328 : :
329 : : /* Now, copy the actual cmin/cmax pairs. */
330 [ + + ]: 155 : if (usedComboCids > 0)
331 : 87 : memcpy(start_address + sizeof(int), comboCids,
332 : : (sizeof(ComboCidKeyData) * usedComboCids));
333 : 155 : }
334 : :
335 : : /*
336 : : * Read the combo CID state at the specified address and initialize this
337 : : * backend with the same combo CIDs. This is only valid in a backend that
338 : : * currently has no combo CIDs (and only makes sense if the transaction state
339 : : * is serialized and restored as well).
340 : : */
341 : : void
342 : 477 : RestoreComboCIDState(char *comboCIDstate)
343 : : {
344 : 477 : int num_elements;
345 : 477 : ComboCidKeyData *keydata;
346 : 477 : int i;
347 : 477 : CommandId cid;
348 : :
349 [ + - ]: 477 : Assert(!comboCids && !comboHash);
350 : :
351 : : /* First, we retrieve the number of combo CIDs that were serialized. */
352 : 477 : num_elements = *(int *) comboCIDstate;
353 : 477 : keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
354 : :
355 : : /* Use GetComboCommandId to restore each combo CID. */
356 [ + + ]: 10010 : for (i = 0; i < num_elements; i++)
357 : : {
358 : 9533 : cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
359 : :
360 : : /* Verify that we got the expected answer. */
361 [ + - ]: 9533 : if (cid != i)
362 [ # # # # ]: 0 : elog(ERROR, "unexpected command ID while restoring combo CIDs");
363 : 9533 : }
364 : 477 : }
|
