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-2024, 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 {
61 
63 
64 typedef 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  */
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 */
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
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 
117 CommandId
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  */
130  Assert(CritSectionCount > 0 ||
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  */
152 void
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  if (!HeapTupleHeaderXminCommitted(tup) &&
165  {
166  CommandId cmin = HeapTupleHeaderGetCmin(tup);
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  */
181 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  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  */
203 static 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 */
222  sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
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,
257  HASH_ENTER,
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;
271  usedComboCids++;
272 
273  entry->combocid = combocid;
274 
275  return combocid;
276 }
277 
278 static CommandId
280 {
281  Assert(combocid < usedComboCids);
282  return comboCids[combocid].cmin;
283 }
284 
285 static 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  */
296 Size
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  */
315 void
316 SerializeComboCIDState(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  */
341 void
342 RestoreComboCIDState(char *comboCIDstate)
343 {
344  int num_elements;
345  ComboCidKeyData *keydata;
346  int i;
347  CommandId cid;
348 
349  Assert(!comboCids && !comboHash);
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 }
uint32 CommandId
Definition: c.h:653
size_t Size
Definition: c.h:592
void RestoreComboCIDState(char *comboCIDstate)
Definition: combocid.c:342
void HeapTupleHeaderAdjustCmax(HeapTupleHeader tup, CommandId *cmax, bool *iscombo)
Definition: combocid.c:153
static ComboCidKey comboCids
Definition: combocid.c:80
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
CommandId HeapTupleHeaderGetCmin(HeapTupleHeader tup)
Definition: combocid.c:104
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(HeapTupleHeader 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:224
volatile uint32 CritSectionCount
Definition: globals.c:43
@ 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
#define HeapTupleHeaderGetXmin(tup)
Definition: htup_details.h:309
#define HEAP_MOVED
Definition: htup_details.h:213
#define HEAP_COMBOCID
Definition: htup_details.h:195
#define HeapTupleHeaderGetRawXmin(tup)
Definition: htup_details.h:304
#define HeapTupleHeaderXminCommitted(tup)
Definition: htup_details.h:320
#define HeapTupleHeaderGetUpdateXid(tup)
Definition: htup_details.h:361
#define HeapTupleHeaderGetRawCommandId(tup)
Definition: htup_details.h:387
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
MemoryContext TopTransactionContext
Definition: mcxt.c:142
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1528
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1168
Size add_size(Size s1, Size s2)
Definition: shmem.c:493
Size mul_size(Size s1, Size s2)
Definition: shmem.c:510
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:938