PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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 overlayed
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-2017, 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 "miscadmin.h"
45 #include "access/htup_details.h"
46 #include "access/xact.h"
47 #include "storage/shmem.h"
48 #include "utils/combocid.h"
49 #include "utils/hsearch.h"
50 #include "utils/memutils.h"
51 
52 
53 /* Hash table to lookup combo cids by cmin and cmax */
54 static HTAB *comboHash = NULL;
55 
56 /* Key and entry structures for the hash table */
57 typedef struct
58 {
62 
64 
65 typedef struct
66 {
70 
72 
73 /* Initial size of the hash table */
74 #define CCID_HASH_SIZE 100
75 
76 
77 /*
78  * An array of cmin,cmax pairs, indexed by combo command id.
79  * To convert a combo cid to cmin and cmax, you do a simple array lookup.
80  */
81 static ComboCidKey comboCids = NULL;
82 static int usedComboCids = 0; /* number of elements in comboCids */
83 static int sizeComboCids = 0; /* allocated size of array */
84 
85 /* Initial size of the array */
86 #define CCID_ARRAY_SIZE 100
87 
88 
89 /* prototypes for internal functions */
91 static CommandId GetRealCmin(CommandId combocid);
92 static CommandId GetRealCmax(CommandId combocid);
93 
94 
95 /**** External API ****/
96 
97 /*
98  * GetCmin and GetCmax assert that they are only called in situations where
99  * they make sense, that is, can deliver a useful answer. If you have
100  * reason to examine a tuple's t_cid field from a transaction other than
101  * the originating one, use HeapTupleHeaderGetRawCommandId() directly.
102  */
103 
104 CommandId
106 {
108 
109  Assert(!(tup->t_infomask & HEAP_MOVED));
111 
112  if (tup->t_infomask & HEAP_COMBOCID)
113  return GetRealCmin(cid);
114  else
115  return cid;
116 }
117 
118 CommandId
120 {
122 
123  Assert(!(tup->t_infomask & HEAP_MOVED));
124 
125  /*
126  * Because GetUpdateXid() performs memory allocations if xmax is a
127  * multixact we can't Assert() if we're inside a critical section. This
128  * weakens the check, but not using GetCmax() inside one would complicate
129  * things too much.
130  */
131  Assert(CritSectionCount > 0 ||
133 
134  if (tup->t_infomask & HEAP_COMBOCID)
135  return GetRealCmax(cid);
136  else
137  return cid;
138 }
139 
140 /*
141  * Given a tuple we are about to delete, determine the correct value to store
142  * into its t_cid field.
143  *
144  * If we don't need a combo CID, *cmax is unchanged and *iscombo is set to
145  * FALSE. If we do need one, *cmax is replaced by a combo CID and *iscombo
146  * is set to TRUE.
147  *
148  * The reason this is separate from the actual HeapTupleHeaderSetCmax()
149  * operation is that this could fail due to out-of-memory conditions. Hence
150  * we need to do this before entering the critical section that actually
151  * changes the tuple in shared buffers.
152  */
153 void
155  CommandId *cmax,
156  bool *iscombo)
157 {
158  /*
159  * If we're marking a tuple deleted that was inserted by (any
160  * subtransaction of) our transaction, we need to use a combo command id.
161  * Test for HeapTupleHeaderXminCommitted() first, because it's cheaper
162  * than a TransactionIdIsCurrentTransactionId call.
163  */
164  if (!HeapTupleHeaderXminCommitted(tup) &&
166  {
167  CommandId cmin = HeapTupleHeaderGetCmin(tup);
168 
169  *cmax = GetComboCommandId(cmin, *cmax);
170  *iscombo = true;
171  }
172  else
173  {
174  *iscombo = false;
175  }
176 }
177 
178 /*
179  * Combo command ids are only interesting to the inserting and deleting
180  * transaction, so we can forget about them at the end of transaction.
181  */
182 void
184 {
185  /*
186  * Don't bother to pfree. These are allocated in TopTransactionContext, so
187  * they're going to go away at the end of transaction anyway.
188  */
189  comboHash = NULL;
190 
191  comboCids = NULL;
192  usedComboCids = 0;
193  sizeComboCids = 0;
194 }
195 
196 
197 /**** Internal routines ****/
198 
199 /*
200  * Get a combo command id that maps to cmin and cmax.
201  *
202  * We try to reuse old combo command ids when possible.
203  */
204 static CommandId
206 {
207  CommandId combocid;
208  ComboCidKeyData key;
209  ComboCidEntry entry;
210  bool found;
211 
212  /*
213  * Create the hash table and array the first time we need to use combo
214  * cids in the transaction.
215  */
216  if (comboHash == NULL)
217  {
218  HASHCTL hash_ctl;
219 
220  /* Make array first; existence of hash table asserts array exists */
221  comboCids = (ComboCidKeyData *)
223  sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
225  usedComboCids = 0;
226 
227  memset(&hash_ctl, 0, sizeof(hash_ctl));
228  hash_ctl.keysize = sizeof(ComboCidKeyData);
229  hash_ctl.entrysize = sizeof(ComboCidEntryData);
230  hash_ctl.hcxt = TopTransactionContext;
231 
232  comboHash = hash_create("Combo CIDs",
234  &hash_ctl,
236  }
237 
238  /*
239  * Grow the array if there's not at least one free slot. We must do this
240  * before possibly entering a new hashtable entry, else failure to
241  * repalloc would leave a corrupt hashtable entry behind.
242  */
244  {
245  int newsize = sizeComboCids * 2;
246 
247  comboCids = (ComboCidKeyData *)
248  repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
249  sizeComboCids = newsize;
250  }
251 
252  /* Lookup or create a hash entry with the desired cmin/cmax */
253 
254  /* We assume there is no struct padding in ComboCidKeyData! */
255  key.cmin = cmin;
256  key.cmax = cmax;
257  entry = (ComboCidEntry) hash_search(comboHash,
258  (void *) &key,
259  HASH_ENTER,
260  &found);
261 
262  if (found)
263  {
264  /* Reuse an existing combo cid */
265  return entry->combocid;
266  }
267 
268  /* We have to create a new combo cid; we already made room in the array */
269  combocid = usedComboCids;
270 
271  comboCids[combocid].cmin = cmin;
272  comboCids[combocid].cmax = cmax;
273  usedComboCids++;
274 
275  entry->combocid = combocid;
276 
277  return combocid;
278 }
279 
280 static CommandId
282 {
283  Assert(combocid < usedComboCids);
284  return comboCids[combocid].cmin;
285 }
286 
287 static CommandId
289 {
290  Assert(combocid < usedComboCids);
291  return comboCids[combocid].cmax;
292 }
293 
294 /*
295  * Estimate the amount of space required to serialize the current ComboCID
296  * state.
297  */
298 Size
300 {
301  Size size;
302 
303  /* Add space required for saving usedComboCids */
304  size = sizeof(int);
305 
306  /* Add space required for saving the combocids key */
307  size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
308 
309  return size;
310 }
311 
312 /*
313  * Serialize the ComboCID state into the memory, beginning at start_address.
314  * maxsize should be at least as large as the value returned by
315  * EstimateComboCIDStateSpace.
316  */
317 void
318 SerializeComboCIDState(Size maxsize, char *start_address)
319 {
320  char *endptr;
321 
322  /* First, we store the number of currently-existing ComboCIDs. */
323  *(int *) start_address = usedComboCids;
324 
325  /* If maxsize is too small, throw an error. */
326  endptr = start_address + sizeof(int) +
327  (sizeof(ComboCidKeyData) * usedComboCids);
328  if (endptr < start_address || endptr > start_address + maxsize)
329  elog(ERROR, "not enough space to serialize ComboCID state");
330 
331  /* Now, copy the actual cmin/cmax pairs. */
332  if (usedComboCids > 0)
333  memcpy(start_address + sizeof(int), comboCids,
334  (sizeof(ComboCidKeyData) * usedComboCids));
335 }
336 
337 /*
338  * Read the ComboCID state at the specified address and initialize this
339  * backend with the same ComboCIDs. This is only valid in a backend that
340  * currently has no ComboCIDs (and only makes sense if the transaction state
341  * is serialized and restored as well).
342  */
343 void
344 RestoreComboCIDState(char *comboCIDstate)
345 {
346  int num_elements;
347  ComboCidKeyData *keydata;
348  int i;
349  CommandId cid;
350 
351  Assert(!comboCids && !comboHash);
352 
353  /* First, we retrieve the number of ComboCIDs that were serialized. */
354  num_elements = *(int *) comboCIDstate;
355  keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
356 
357  /* Use GetComboCommandId to restore each ComboCID. */
358  for (i = 0; i < num_elements; i++)
359  {
360  cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
361 
362  /* Verify that we got the expected answer. */
363  if (cid != i)
364  elog(ERROR, "unexpected command ID while restoring combo CIDs");
365  }
366 }
#define HeapTupleHeaderGetUpdateXid(tup)
Definition: htup_details.h:359
uint32 CommandId
Definition: c.h:405
ComboCidKeyData key
Definition: combocid.c:67
MemoryContext TopTransactionContext
Definition: mcxt.c:48
#define HASH_CONTEXT
Definition: hsearch.h:93
#define HASH_ELEM
Definition: hsearch.h:87
MemoryContext hcxt
Definition: hsearch.h:78
bool TransactionIdIsCurrentTransactionId(TransactionId xid)
Definition: xact.c:774
#define CCID_ARRAY_SIZE
Definition: combocid.c:86
CommandId HeapTupleHeaderGetCmin(HeapTupleHeader tup)
Definition: combocid.c:105
Size entrysize
Definition: hsearch.h:73
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:902
void RestoreComboCIDState(char *comboCIDstate)
Definition: combocid.c:344
static int usedComboCids
Definition: combocid.c:82
static ComboCidKey comboCids
Definition: combocid.c:81
Definition: dynahash.c:208
#define ERROR
Definition: elog.h:43
#define HeapTupleHeaderXminCommitted(tup)
Definition: htup_details.h:318
static CommandId GetComboCommandId(CommandId cmin, CommandId cmax)
Definition: combocid.c:205
static CommandId GetRealCmin(CommandId combocid)
Definition: combocid.c:281
Size EstimateComboCIDStateSpace(void)
Definition: combocid.c:299
static HTAB * comboHash
Definition: combocid.c:54
volatile uint32 CritSectionCount
Definition: globals.c:37
ComboCidKeyData * ComboCidKey
Definition: combocid.c:63
#define HASH_BLOBS
Definition: hsearch.h:88
static CommandId GetRealCmax(CommandId combocid)
Definition: combocid.c:288
CommandId cmin
Definition: combocid.c:59
Size mul_size(Size s1, Size s2)
Definition: shmem.c:492
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:316
Size add_size(Size s1, Size s2)
Definition: shmem.c:475
Size keysize
Definition: hsearch.h:72
static int sizeComboCids
Definition: combocid.c:83
#define HEAP_MOVED
Definition: htup_details.h:202
CommandId cmax
Definition: combocid.c:60
void AtEOXact_ComboCid(void)
Definition: combocid.c:183
#define HEAP_COMBOCID
Definition: htup_details.h:180
#define Assert(condition)
Definition: c.h:664
CommandId HeapTupleHeaderGetCmax(HeapTupleHeader tup)
Definition: combocid.c:119
#define HeapTupleHeaderGetXmin(tup)
Definition: htup_details.h:307
size_t Size
Definition: c.h:350
#define HeapTupleHeaderGetRawXmin(tup)
Definition: htup_details.h:302
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:962
void HeapTupleHeaderAdjustCmax(HeapTupleHeader tup, CommandId *cmax, bool *iscombo)
Definition: combocid.c:154
#define CCID_HASH_SIZE
Definition: combocid.c:74
#define HeapTupleHeaderGetRawCommandId(tup)
Definition: htup_details.h:385
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:706
int i
CommandId combocid
Definition: combocid.c:68
#define elog
Definition: elog.h:219
void SerializeComboCIDState(Size maxsize, char *start_address)
Definition: combocid.c:318
ComboCidEntryData * ComboCidEntry
Definition: combocid.c:71