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-2020, 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 { 58 CommandId cmin; 59 CommandId cmax; 60 } ComboCidKeyData; 61 62 typedef ComboCidKeyData *ComboCidKey; 63 64 typedef struct 65 { 66 ComboCidKeyData key; 67 CommandId combocid; 68 } ComboCidEntryData; 69 70 typedef ComboCidEntryData *ComboCidEntry; 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 */ 89 static CommandId GetComboCommandId(CommandId cmin, CommandId cmax); 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 104 HeapTupleHeaderGetCmin(HeapTupleHeader tup) 105 { 106 CommandId cid = HeapTupleHeaderGetRawCommandId(tup); 107 108 Assert(!(tup->t_infomask & HEAP_MOVED)); 109 Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup))); 110 111 if (tup->t_infomask & HEAP_COMBOCID) 112 return GetRealCmin(cid); 113 else 114 return cid; 115 } 116 117 CommandId 118 HeapTupleHeaderGetCmax(HeapTupleHeader tup) 119 { 120 CommandId cid = HeapTupleHeaderGetRawCommandId(tup); 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 || 131 TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tup))); 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 153 HeapTupleHeaderAdjustCmax(HeapTupleHeader tup, 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) && 164 TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(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 182 AtEOXact_ComboCid(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 204 GetComboCommandId(CommandId cmin, CommandId cmax) 205 { 206 CommandId combocid; 207 ComboCidKeyData key; 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 */ 220 comboCids = (ComboCidKeyData *) 221 MemoryContextAlloc(TopTransactionContext, 222 sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE); 223 sizeComboCids = CCID_ARRAY_SIZE; 224 usedComboCids = 0; 225 226 memset(&hash_ctl, 0, sizeof(hash_ctl)); 227 hash_ctl.keysize = sizeof(ComboCidKeyData); 228 hash_ctl.entrysize = sizeof(ComboCidEntryData); 229 hash_ctl.hcxt = TopTransactionContext; 230 231 comboHash = hash_create("Combo CIDs", 232 CCID_HASH_SIZE, 233 &hash_ctl, 234 HASH_ELEM | HASH_BLOBS | HASH_CONTEXT); 235 } 236 237 /* 238 * Grow the array if there's not at least one free slot. We must do this 239 * before possibly entering a new hashtable entry, else failure to 240 * repalloc would leave a corrupt hashtable entry behind. 241 */ 242 if (usedComboCids >= sizeComboCids) 243 { 244 int newsize = sizeComboCids * 2; 245 246 comboCids = (ComboCidKeyData *) 247 repalloc(comboCids, sizeof(ComboCidKeyData) * newsize); 248 sizeComboCids = newsize; 249 } 250 251 /* Lookup or create a hash entry with the desired cmin/cmax */ 252 253 /* We assume there is no struct padding in ComboCidKeyData! */ 254 key.cmin = cmin; 255 key.cmax = cmax; 256 entry = (ComboCidEntry) hash_search(comboHash, 257 (void *) &key, 258 HASH_ENTER, 259 &found); 260 261 if (found) 262 { 263 /* Reuse an existing combo cid */ 264 return entry->combocid; 265 } 266 267 /* We have to create a new combo cid; we already made room in the array */ 268 combocid = usedComboCids; 269 270 comboCids[combocid].cmin = cmin; 271 comboCids[combocid].cmax = cmax; 272 usedComboCids++; 273 274 entry->combocid = combocid; 275 276 return combocid; 277 } 278 279 static CommandId 280 GetRealCmin(CommandId combocid) 281 { 282 Assert(combocid < usedComboCids); 283 return comboCids[combocid].cmin; 284 } 285 286 static CommandId 287 GetRealCmax(CommandId combocid) 288 { 289 Assert(combocid < usedComboCids); 290 return comboCids[combocid].cmax; 291 } 292 293 /* 294 * Estimate the amount of space required to serialize the current ComboCID 295 * state. 296 */ 297 Size 298 EstimateComboCIDStateSpace(void) 299 { 300 Size size; 301 302 /* Add space required for saving usedComboCids */ 303 size = sizeof(int); 304 305 /* Add space required for saving the combocids key */ 306 size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids)); 307 308 return size; 309 } 310 311 /* 312 * Serialize the ComboCID state into the memory, beginning at start_address. 313 * maxsize should be at least as large as the value returned by 314 * EstimateComboCIDStateSpace. 315 */ 316 void 317 SerializeComboCIDState(Size maxsize, char *start_address) 318 { 319 char *endptr; 320 321 /* First, we store the number of currently-existing ComboCIDs. */ 322 *(int *) start_address = usedComboCids; 323 324 /* If maxsize is too small, throw an error. */ 325 endptr = start_address + sizeof(int) + 326 (sizeof(ComboCidKeyData) * usedComboCids); 327 if (endptr < start_address || endptr > start_address + maxsize) 328 elog(ERROR, "not enough space to serialize ComboCID state"); 329 330 /* Now, copy the actual cmin/cmax pairs. */ 331 if (usedComboCids > 0) 332 memcpy(start_address + sizeof(int), comboCids, 333 (sizeof(ComboCidKeyData) * usedComboCids)); 334 } 335 336 /* 337 * Read the ComboCID state at the specified address and initialize this 338 * backend with the same ComboCIDs. This is only valid in a backend that 339 * currently has no ComboCIDs (and only makes sense if the transaction state 340 * is serialized and restored as well). 341 */ 342 void 343 RestoreComboCIDState(char *comboCIDstate) 344 { 345 int num_elements; 346 ComboCidKeyData *keydata; 347 int i; 348 CommandId cid; 349 350 Assert(!comboCids && !comboHash); 351 352 /* First, we retrieve the number of ComboCIDs that were serialized. */ 353 num_elements = *(int *) comboCIDstate; 354 keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int)); 355 356 /* Use GetComboCommandId to restore each ComboCID. */ 357 for (i = 0; i < num_elements; i++) 358 { 359 cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax); 360 361 /* Verify that we got the expected answer. */ 362 if (cid != i) 363 elog(ERROR, "unexpected command ID while restoring combo CIDs"); 364 } 365 } 366