PostgreSQL Source Code git master
combocid.c
Go to the documentation of this file.
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-2025, 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 */
53static HTAB *comboHash = NULL;
54
55/* Key and entry structures for the hash table */
56typedef struct
57{
61
63
64typedef struct
65{
69
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 */
80static ComboCidKey comboCids = NULL;
81static int usedComboCids = 0; /* number of elements in comboCids */
82static 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 */
90static CommandId GetRealCmin(CommandId combocid);
91static 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
105{
107
108 Assert(!(tup->t_infomask & HEAP_MOVED));
110
111 if (tup->t_infomask & HEAP_COMBOCID)
112 return GetRealCmin(cid);
113 else
114 return cid;
115}
116
119{
121
122 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 */
132
133 if (tup->t_infomask & HEAP_COMBOCID)
134 return GetRealCmax(cid);
135 else
136 return cid;
137}
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 */
152void
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 */
165 {
167
168 *cmax = GetComboCommandId(cmin, *cmax);
169 *iscombo = true;
170 }
171 else
172 {
173 *iscombo = false;
174 }
175}
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 */
181void
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 comboHash = NULL;
189
190 comboCids = NULL;
191 usedComboCids = 0;
192 sizeComboCids = 0;
193}
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 */
203static CommandId
205{
206 CommandId combocid;
208 ComboCidEntry entry;
209 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 if (comboHash == NULL)
216 {
217 HASHCTL hash_ctl;
218
219 /* Make array first; existence of hash table asserts array exists */
224 usedComboCids = 0;
225
226 hash_ctl.keysize = sizeof(ComboCidKeyData);
227 hash_ctl.entrysize = sizeof(ComboCidEntryData);
228 hash_ctl.hcxt = TopTransactionContext;
229
230 comboHash = hash_create("Combo CIDs",
232 &hash_ctl,
234 }
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 */
242 {
243 int newsize = sizeComboCids * 2;
244
246 repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
247 sizeComboCids = newsize;
248 }
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 key.cmin = cmin;
254 key.cmax = cmax;
256 &key,
258 &found);
259
260 if (found)
261 {
262 /* Reuse an existing combo CID */
263 return entry->combocid;
264 }
265
266 /* We have to create a new combo CID; we already made room in the array */
267 combocid = usedComboCids;
268
269 comboCids[combocid].cmin = cmin;
270 comboCids[combocid].cmax = cmax;
272
273 entry->combocid = combocid;
274
275 return combocid;
276}
277
278static CommandId
280{
281 Assert(combocid < usedComboCids);
282 return comboCids[combocid].cmin;
283}
284
285static CommandId
287{
288 Assert(combocid < usedComboCids);
289 return comboCids[combocid].cmax;
290}
291
292/*
293 * Estimate the amount of space required to serialize the current combo CID
294 * state.
295 */
296Size
298{
299 Size size;
300
301 /* Add space required for saving usedComboCids */
302 size = sizeof(int);
303
304 /* Add space required for saving ComboCidKeyData */
306
307 return size;
308}
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 */
315void
316SerializeComboCIDState(Size maxsize, char *start_address)
317{
318 char *endptr;
319
320 /* First, we store the number of currently-existing combo CIDs. */
321 *(int *) start_address = usedComboCids;
322
323 /* If maxsize is too small, throw an error. */
324 endptr = start_address + sizeof(int) +
325 (sizeof(ComboCidKeyData) * usedComboCids);
326 if (endptr < start_address || endptr > start_address + maxsize)
327 elog(ERROR, "not enough space to serialize ComboCID state");
328
329 /* Now, copy the actual cmin/cmax pairs. */
330 if (usedComboCids > 0)
331 memcpy(start_address + sizeof(int), comboCids,
332 (sizeof(ComboCidKeyData) * usedComboCids));
333}
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 */
341void
342RestoreComboCIDState(char *comboCIDstate)
343{
344 int num_elements;
345 ComboCidKeyData *keydata;
346 int i;
347 CommandId cid;
348
350
351 /* First, we retrieve the number of combo CIDs that were serialized. */
352 num_elements = *(int *) comboCIDstate;
353 keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
354
355 /* Use GetComboCommandId to restore each combo CID. */
356 for (i = 0; i < num_elements; i++)
357 {
358 cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
359
360 /* Verify that we got the expected answer. */
361 if (cid != i)
362 elog(ERROR, "unexpected command ID while restoring combo CIDs");
363 }
364}
#define Assert(condition)
Definition: c.h:815
uint32 CommandId
Definition: c.h:623
size_t Size
Definition: c.h:562
CommandId HeapTupleHeaderGetCmin(const HeapTupleHeaderData *tup)
Definition: combocid.c:104
void RestoreComboCIDState(char *comboCIDstate)
Definition: combocid.c:342
static ComboCidKey comboCids
Definition: combocid.c:80
void HeapTupleHeaderAdjustCmax(const HeapTupleHeaderData *tup, CommandId *cmax, bool *iscombo)
Definition: combocid.c:153
static CommandId GetRealCmin(CommandId combocid)
Definition: combocid.c:279
static HTAB * comboHash
Definition: combocid.c:53
static int usedComboCids
Definition: combocid.c:81
ComboCidKeyData * ComboCidKey
Definition: combocid.c:62
static int sizeComboCids
Definition: combocid.c:82
void SerializeComboCIDState(Size maxsize, char *start_address)
Definition: combocid.c:316
#define CCID_HASH_SIZE
Definition: combocid.c:73
static CommandId GetComboCommandId(CommandId cmin, CommandId cmax)
Definition: combocid.c:204
static CommandId GetRealCmax(CommandId combocid)
Definition: combocid.c:286
void AtEOXact_ComboCid(void)
Definition: combocid.c:182
CommandId HeapTupleHeaderGetCmax(const HeapTupleHeaderData *tup)
Definition: combocid.c:118
Size EstimateComboCIDStateSpace(void)
Definition: combocid.c:297
#define CCID_ARRAY_SIZE
Definition: combocid.c:85
ComboCidEntryData * ComboCidEntry
Definition: combocid.c:70
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:955
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Definition: dynahash.c:352
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
volatile uint32 CritSectionCount
Definition: globals.c:44
@ HASH_ENTER
Definition: hsearch.h:114
#define HASH_CONTEXT
Definition: hsearch.h:102
#define HASH_ELEM
Definition: hsearch.h:95
#define HASH_BLOBS
Definition: hsearch.h:97
static CommandId HeapTupleHeaderGetRawCommandId(const HeapTupleHeaderData *tup)
Definition: htup_details.h:415
#define HEAP_MOVED
Definition: htup_details.h:213
static TransactionId HeapTupleHeaderGetXmin(const HeapTupleHeaderData *tup)
Definition: htup_details.h:324
#define HEAP_COMBOCID
Definition: htup_details.h:195
static TransactionId HeapTupleHeaderGetRawXmin(const HeapTupleHeaderData *tup)
Definition: htup_details.h:318
static TransactionId HeapTupleHeaderGetUpdateXid(const HeapTupleHeaderData *tup)
Definition: htup_details.h:397
static bool HeapTupleHeaderXminCommitted(const HeapTupleHeaderData *tup)
Definition: htup_details.h:337
int i
Definition: isn.c:72
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1181
MemoryContext TopTransactionContext
Definition: mcxt.c:154
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1541
Size add_size(Size s1, Size s2)
Definition: shmem.c:488
Size mul_size(Size s1, Size s2)
Definition: shmem.c:505
static pg_noinline void Size size
Definition: slab.c:607
CommandId combocid
Definition: combocid.c:67
ComboCidKeyData key
Definition: combocid.c:66
CommandId cmax
Definition: combocid.c:59
CommandId cmin
Definition: combocid.c:58
Size keysize
Definition: hsearch.h:75
Size entrysize
Definition: hsearch.h:76
MemoryContext hcxt
Definition: hsearch.h:86
Definition: dynahash.c:220
bool TransactionIdIsCurrentTransactionId(TransactionId xid)
Definition: xact.c:940