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-2019, 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 */
54static HTAB *comboHash = NULL;
55
56/* Key and entry structures for the hash table */
57typedef struct
58{
59 CommandId cmin;
60 CommandId cmax;
61} ComboCidKeyData;
62
63typedef ComboCidKeyData *ComboCidKey;
64
65typedef struct
66{
67 ComboCidKeyData key;
68 CommandId combocid;
69} ComboCidEntryData;
70
71typedef ComboCidEntryData *ComboCidEntry;
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 */
81static ComboCidKey comboCids = NULL;
82static int usedComboCids = 0; /* number of elements in comboCids */
83static 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 */
90static CommandId GetComboCommandId(CommandId cmin, CommandId cmax);
91static CommandId GetRealCmin(CommandId combocid);
92static 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
104CommandId
105HeapTupleHeaderGetCmin(HeapTupleHeader tup)
106{
107 CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
108
109 Assert(!(tup->t_infomask & HEAP_MOVED));
110 Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
111
112 if (tup->t_infomask & HEAP_COMBOCID)
113 return GetRealCmin(cid);
114 else
115 return cid;
116}
117
118CommandId
119HeapTupleHeaderGetCmax(HeapTupleHeader tup)
120{
121 CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
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 ||
132 TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tup)));
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 */
153void
154HeapTupleHeaderAdjustCmax(HeapTupleHeader tup,
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) &&
165 TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(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 */
182void
183AtEOXact_ComboCid(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 */
204static CommandId
205GetComboCommandId(CommandId cmin, CommandId cmax)
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 *)
222 MemoryContextAlloc(TopTransactionContext,
223 sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
224 sizeComboCids = 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",
233 CCID_HASH_SIZE,
234 &hash_ctl,
235 HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
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 */
243 if (usedComboCids >= sizeComboCids)
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
280static CommandId
281GetRealCmin(CommandId combocid)
282{
283 Assert(combocid < usedComboCids);
284 return comboCids[combocid].cmin;
285}
286
287static CommandId
288GetRealCmax(CommandId combocid)
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 */
298Size
299EstimateComboCIDStateSpace(void)
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 */
317void
318SerializeComboCIDState(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 */
343void
344RestoreComboCIDState(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}
367