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 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 : {
59 : CommandId cmin;
60 : CommandId cmax;
61 : } ComboCidKeyData;
62 :
63 : typedef ComboCidKeyData *ComboCidKey;
64 :
65 : typedef struct
66 : {
67 : ComboCidKeyData key;
68 : CommandId combocid;
69 : } ComboCidEntryData;
70 :
71 : typedef 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 : */
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 */
90 : static CommandId GetComboCommandId(CommandId cmin, CommandId cmax);
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
105 171861 : HeapTupleHeaderGetCmin(HeapTupleHeader tup)
106 : {
107 171861 : CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
108 :
109 171861 : Assert(!(tup->t_infomask & HEAP_MOVED));
110 171861 : Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
111 :
112 171861 : if (tup->t_infomask & HEAP_COMBOCID)
113 3999 : return GetRealCmin(cid);
114 : else
115 167862 : return cid;
116 : }
117 :
118 : CommandId
119 10523 : HeapTupleHeaderGetCmax(HeapTupleHeader tup)
120 : {
121 10523 : CommandId cid = HeapTupleHeaderGetRawCommandId(tup);
122 :
123 10523 : 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 10523 : Assert(CritSectionCount > 0 ||
132 : TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tup)));
133 :
134 10523 : if (tup->t_infomask & HEAP_COMBOCID)
135 3988 : return GetRealCmax(cid);
136 : else
137 6535 : 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
154 118568 : HeapTupleHeaderAdjustCmax(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 123582 : if (!HeapTupleHeaderXminCommitted(tup) &&
165 5014 : TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tup)))
166 4950 : {
167 4950 : CommandId cmin = HeapTupleHeaderGetCmin(tup);
168 :
169 4950 : *cmax = GetComboCommandId(cmin, *cmax);
170 4950 : *iscombo = true;
171 : }
172 : else
173 : {
174 113618 : *iscombo = false;
175 : }
176 118568 : }
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
183 26218 : AtEOXact_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 26218 : comboHash = NULL;
190 :
191 26218 : comboCids = NULL;
192 26218 : usedComboCids = 0;
193 26218 : sizeComboCids = 0;
194 26218 : }
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
205 5365 : GetComboCommandId(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 5365 : if (comboHash == NULL)
217 : {
218 : HASHCTL hash_ctl;
219 :
220 : /* Make array first; existence of hash table asserts array exists */
221 1651 : comboCids = (ComboCidKeyData *)
222 1651 : MemoryContextAlloc(TopTransactionContext,
223 : sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
224 1651 : sizeComboCids = CCID_ARRAY_SIZE;
225 1651 : usedComboCids = 0;
226 :
227 1651 : memset(&hash_ctl, 0, sizeof(hash_ctl));
228 1651 : hash_ctl.keysize = sizeof(ComboCidKeyData);
229 1651 : hash_ctl.entrysize = sizeof(ComboCidEntryData);
230 1651 : hash_ctl.hcxt = TopTransactionContext;
231 :
232 1651 : 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 5365 : if (usedComboCids >= sizeComboCids)
244 : {
245 0 : int newsize = sizeComboCids * 2;
246 :
247 0 : comboCids = (ComboCidKeyData *)
248 0 : repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
249 0 : 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 5365 : key.cmin = cmin;
256 5365 : key.cmax = cmax;
257 5365 : entry = (ComboCidEntry) hash_search(comboHash,
258 : (void *) &key,
259 : HASH_ENTER,
260 : &found);
261 :
262 5365 : if (found)
263 : {
264 : /* Reuse an existing combo cid */
265 1875 : return entry->combocid;
266 : }
267 :
268 : /* We have to create a new combo cid; we already made room in the array */
269 3490 : combocid = usedComboCids;
270 :
271 3490 : comboCids[combocid].cmin = cmin;
272 3490 : comboCids[combocid].cmax = cmax;
273 3490 : usedComboCids++;
274 :
275 3490 : entry->combocid = combocid;
276 :
277 3490 : return combocid;
278 : }
279 :
280 : static CommandId
281 3999 : GetRealCmin(CommandId combocid)
282 : {
283 3999 : Assert(combocid < usedComboCids);
284 3999 : return comboCids[combocid].cmin;
285 : }
286 :
287 : static CommandId
288 3988 : GetRealCmax(CommandId combocid)
289 : {
290 3988 : Assert(combocid < usedComboCids);
291 3988 : return comboCids[combocid].cmax;
292 : }
293 :
294 : /*
295 : * Estimate the amount of space required to serialize the current ComboCID
296 : * state.
297 : */
298 : Size
299 17 : EstimateComboCIDStateSpace(void)
300 : {
301 : Size size;
302 :
303 : /* Add space required for saving usedComboCids */
304 17 : size = sizeof(int);
305 :
306 : /* Add space required for saving the combocids key */
307 17 : size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
308 :
309 17 : 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 17 : SerializeComboCIDState(Size maxsize, char *start_address)
319 : {
320 : char *endptr;
321 :
322 : /* First, we store the number of currently-existing ComboCIDs. */
323 17 : *(int *) start_address = usedComboCids;
324 :
325 : /* If maxsize is too small, throw an error. */
326 34 : endptr = start_address + sizeof(int) +
327 17 : (sizeof(ComboCidKeyData) * usedComboCids);
328 17 : if (endptr < start_address || endptr > start_address + maxsize)
329 0 : elog(ERROR, "not enough space to serialize ComboCID state");
330 :
331 : /* Now, copy the actual cmin/cmax pairs. */
332 17 : if (usedComboCids > 0)
333 14 : memcpy(start_address + sizeof(int), comboCids,
334 : (sizeof(ComboCidKeyData) * usedComboCids));
335 17 : }
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 115 : RestoreComboCIDState(char *comboCIDstate)
345 : {
346 : int num_elements;
347 : ComboCidKeyData *keydata;
348 : int i;
349 : CommandId cid;
350 :
351 115 : Assert(!comboCids && !comboHash);
352 :
353 : /* First, we retrieve the number of ComboCIDs that were serialized. */
354 115 : num_elements = *(int *) comboCIDstate;
355 115 : keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
356 :
357 : /* Use GetComboCommandId to restore each ComboCID. */
358 530 : for (i = 0; i < num_elements; i++)
359 : {
360 415 : cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
361 :
362 : /* Verify that we got the expected answer. */
363 415 : if (cid != i)
364 0 : elog(ERROR, "unexpected command ID while restoring combo CIDs");
365 : }
366 115 : }
|
