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-2008, PostgreSQL Global Development Group
  34  * Portions Copyright (c) 1994, Regents of the University of California
  35  *
  36  * IDENTIFICATION
  37  *        $PostgreSQL$
  38  *
  39  *-------------------------------------------------------------------------
  40  */
  41
  42 #include "postgres.h"
  43
  44 #include "access/htup.h"
  45 #include "access/xact.h"
  46 #include "utils/combocid.h"
  47 #include "utils/hsearch.h"
  48 #include "utils/memutils.h"
  49
  50
  51 /* Hash table to lookup combo cids by cmin and cmax */
  52 static HTAB *comboHash = NULL;
  53
  54 /* Key and entry structures for the hash table */
  55 typedef struct
  56 {
  57         CommandId       cmin;
  58         CommandId       cmax;
  59 } ComboCidKeyData;
  60
  61 typedef ComboCidKeyData *ComboCidKey;
  62
  63 typedef struct
  64 {
  65         ComboCidKeyData key;
  66         CommandId       combocid;
  67 } ComboCidEntryData;
  68
  69 typedef ComboCidEntryData *ComboCidEntry;
  70
  71 /* Initial size of the hash table */
  72 #define CCID_HASH_SIZE                  100
  73
  74
  75 /*
  76  * An array of cmin,cmax pairs, indexed by combo command id.
  77  * To convert a combo cid to cmin and cmax, you do a simple array lookup.
  78  */
  79 static ComboCidKey comboCids = NULL;
  80 static int      usedComboCids = 0;      /* number of elements in comboCids */
  81 static int      sizeComboCids = 0;      /* allocated size of array */
  82
  83 /* Initial size of the array */
  84 #define CCID_ARRAY_SIZE                 100
  85
  86
  87 /* prototypes for internal functions */
  88 static CommandId GetComboCommandId(CommandId cmin, CommandId cmax);
  89 static CommandId GetRealCmin(CommandId combocid);
  90 static CommandId GetRealCmax(CommandId combocid);
  91
  92
  93 /**** External API ****/
  94
  95 /*
  96  * GetCmin and GetCmax assert that they are only called in situations where
  97  * they make sense, that is, can deliver a useful answer.  If you have
  98  * reason to examine a tuple's t_cid field from a transaction other than
  99  * the originating one, use HeapTupleHeaderGetRawCommandId() directly.
 100  */
 101
 102 CommandId
 103 HeapTupleHeaderGetCmin(HeapTupleHeader tup)
 104 {
 105         CommandId       cid = HeapTupleHeaderGetRawCommandId(tup);
 106
 107         Assert(!(tup->t_infomask & HEAP_MOVED));
 108         Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
 109
 110         if (tup->t_infomask & HEAP_COMBOCID)
 111                 return GetRealCmin(cid);
 112         else
 113                 return cid;
 114 }
 115
 116 CommandId
 117 HeapTupleHeaderGetCmax(HeapTupleHeader tup)
 118 {
 119         CommandId       cid = HeapTupleHeaderGetRawCommandId(tup);
 120
 121         /* We do not store cmax when locking a tuple */
 122         Assert(!(tup->t_infomask & (HEAP_MOVED | HEAP_IS_LOCKED)));
 123         Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tup)));
 124
 125         if (tup->t_infomask & HEAP_COMBOCID)
 126                 return GetRealCmax(cid);
 127         else
 128                 return cid;
 129 }
 130
 131 /*
 132  * Given a tuple we are about to delete, determine the correct value to store
 133  * into its t_cid field.
 134  *
 135  * If we don't need a combo CID, *cmax is unchanged and *iscombo is set to
 136  * FALSE.  If we do need one, *cmax is replaced by a combo CID and *iscombo
 137  * is set to TRUE.
 138  *
 139  * The reason this is separate from the actual HeapTupleHeaderSetCmax()
 140  * operation is that this could fail due to out-of-memory conditions.  Hence
 141  * we need to do this before entering the critical section that actually
 142  * changes the tuple in shared buffers.
 143  */
 144 void
 145 HeapTupleHeaderAdjustCmax(HeapTupleHeader tup,
 146                                                   CommandId *cmax,
 147                                                   bool *iscombo)
 148 {
 149         /*
 150          * If we're marking a tuple deleted that was inserted by (any
 151          * subtransaction of) our transaction, we need to use a combo command id.
 152          * Test for HEAP_XMIN_COMMITTED first, because it's cheaper than a
 153          * TransactionIdIsCurrentTransactionId call.
 154          */
 155         if (!(tup->t_infomask & HEAP_XMIN_COMMITTED) &&
 156                 TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)))
 157         {
 158                 CommandId       cmin = HeapTupleHeaderGetCmin(tup);
 159
 160                 *cmax = GetComboCommandId(cmin, *cmax);
 161                 *iscombo = true;
 162         }
 163         else
 164         {
 165                 *iscombo = false;
 166         }
 167 }
 168
 169 /*
 170  * Combo command ids are only interesting to the inserting and deleting
 171  * transaction, so we can forget about them at the end of transaction.
 172  */
 173 void
 174 AtEOXact_ComboCid(void)
 175 {
 176         /*
 177          * Don't bother to pfree. These are allocated in TopTransactionContext, so
 178          * they're going to go away at the end of transaction anyway.
 179          */
 180         comboHash = NULL;
 181
 182         comboCids = NULL;
 183         usedComboCids = 0;
 184         sizeComboCids = 0;
 185 }
 186
 187
 188 /**** Internal routines ****/
 189
 190 /*
 191  * Get a combo command id that maps to cmin and cmax.
 192  *
 193  * We try to reuse old combo command ids when possible.
 194  */
 195 static CommandId
 196 GetComboCommandId(CommandId cmin, CommandId cmax)
 197 {
 198         CommandId       combocid;
 199         ComboCidKeyData key;
 200         ComboCidEntry entry;
 201         bool            found;
 202
 203         /*
 204          * Create the hash table and array the first time we need to use combo
 205          * cids in the transaction.
 206          */
 207         if (comboHash == NULL)
 208         {
 209                 HASHCTL         hash_ctl;
 210
 211                 memset(&hash_ctl, 0, sizeof(hash_ctl));
 212                 hash_ctl.keysize = sizeof(ComboCidKeyData);
 213                 hash_ctl.entrysize = sizeof(ComboCidEntryData);
 214                 hash_ctl.hash = tag_hash;
 215                 hash_ctl.hcxt = TopTransactionContext;
 216
 217                 comboHash = hash_create("Combo CIDs",
 218                                                                 CCID_HASH_SIZE,
 219                                                                 &hash_ctl,
 220                                                                 HASH_ELEM | HASH_FUNCTION | HASH_CONTEXT);
 221
 222                 comboCids = (ComboCidKeyData *)
 223                         MemoryContextAlloc(TopTransactionContext,
 224                                                            sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
 225                 sizeComboCids = CCID_ARRAY_SIZE;
 226                 usedComboCids = 0;
 227         }
 228
 229         /* Lookup or create a hash entry with the desired cmin/cmax */
 230
 231         /* We assume there is no struct padding in ComboCidKeyData! */
 232         key.cmin = cmin;
 233         key.cmax = cmax;
 234         entry = (ComboCidEntry) hash_search(comboHash,
 235                                                                                 (void *) &key,
 236                                                                                 HASH_ENTER,
 237                                                                                 &found);
 238
 239         if (found)
 240         {
 241                 /* Reuse an existing combo cid */
 242                 return entry->combocid;
 243         }
 244
 245         /*
 246          * We have to create a new combo cid. Check that there's room for it in
 247          * the array, and grow it if there isn't.
 248          */
 249         if (usedComboCids >= sizeComboCids)
 250         {
 251                 /* We need to grow the array */
 252                 int                     newsize = sizeComboCids * 2;
 253
 254                 comboCids = (ComboCidKeyData *)
 255                         repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
 256                 sizeComboCids = newsize;
 257         }
 258
 259         combocid = usedComboCids;
 260
 261         comboCids[combocid].cmin = cmin;
 262         comboCids[combocid].cmax = cmax;
 263         usedComboCids++;
 264
 265         entry->combocid = combocid;
 266
 267         return combocid;
 268 }
 269
 270 static CommandId
 271 GetRealCmin(CommandId combocid)
 272 {
 273         Assert(combocid < usedComboCids);
 274         return comboCids[combocid].cmin;
 275 }
 276
 277 static CommandId
 278 GetRealCmax(CommandId combocid)
 279 {
 280         Assert(combocid < usedComboCids);
 281         return comboCids[combocid].cmax;
 282 }