src/backend/utils/time/combocid.c

   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-2022, 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                 hash_ctl.keysize = sizeof(ComboCidKeyData);
 227                 hash_ctl.entrysize = sizeof(ComboCidEntryData);
 228                 hash_ctl.hcxt = TopTransactionContext;
 229
 230                 comboHash = hash_create("Combo CIDs",
 231                                                                 CCID_HASH_SIZE,
 232                                                                 &hash_ctl,
 233                                                                 HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
 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          */
 241         if (usedComboCids >= sizeComboCids)
 242         {
 243                 int                     newsize = sizeComboCids * 2;
 244
 245                 comboCids = (ComboCidKeyData *)
 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;
 255         entry = (ComboCidEntry) hash_search(comboHash,
 256                                                                                 (void *) &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
 279 GetRealCmin(CommandId combocid)
 280 {
 281         Assert(combocid < usedComboCids);
 282         return comboCids[combocid].cmin;
 283 }
 284
 285 static CommandId
 286 GetRealCmax(CommandId combocid)
 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
 297 EstimateComboCIDStateSpace(void)
 298 {
 299         Size            size;
 300
 301         /* Add space required for saving usedComboCids */
 302         size = sizeof(int);
 303
 304         /* Add space required for saving ComboCidKeyData */
 305         size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
 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 }