LCOV - code coverage report
Current view: top level - src/backend/utils/time - combocid.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 74 76 97.4 %
Date: 2024-03-29 05:11:05 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

          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 overlaid
       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-2024, 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    20597246 : HeapTupleHeaderGetCmin(HeapTupleHeader tup)
     105             : {
     106    20597246 :     CommandId   cid = HeapTupleHeaderGetRawCommandId(tup);
     107             : 
     108             :     Assert(!(tup->t_infomask & HEAP_MOVED));
     109             :     Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
     110             : 
     111    20597246 :     if (tup->t_infomask & HEAP_COMBOCID)
     112     5715912 :         return GetRealCmin(cid);
     113             :     else
     114    14881334 :         return cid;
     115             : }
     116             : 
     117             : CommandId
     118     5894220 : HeapTupleHeaderGetCmax(HeapTupleHeader tup)
     119             : {
     120     5894220 :     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     5894220 :     if (tup->t_infomask & HEAP_COMBOCID)
     134     5715780 :         return GetRealCmax(cid);
     135             :     else
     136      178440 :         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     3352046 : 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     3743006 :     if (!HeapTupleHeaderXminCommitted(tup) &&
     164      390960 :         TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tup)))
     165      388624 :     {
     166      388624 :         CommandId   cmin = HeapTupleHeaderGetCmin(tup);
     167             : 
     168      388624 :         *cmax = GetComboCommandId(cmin, *cmax);
     169      388624 :         *iscombo = true;
     170             :     }
     171             :     else
     172             :     {
     173     2963422 :         *iscombo = false;
     174             :     }
     175     3352046 : }
     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      566288 : 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      566288 :     comboHash = NULL;
     189             : 
     190      566288 :     comboCids = NULL;
     191      566288 :     usedComboCids = 0;
     192      566288 :     sizeComboCids = 0;
     193      566288 : }
     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      443212 : 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      443212 :     if (comboHash == NULL)
     216             :     {
     217             :         HASHCTL     hash_ctl;
     218             : 
     219             :         /* Make array first; existence of hash table asserts array exists */
     220       39372 :         comboCids = (ComboCidKeyData *)
     221       39372 :             MemoryContextAlloc(TopTransactionContext,
     222             :                                sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
     223       39372 :         sizeComboCids = CCID_ARRAY_SIZE;
     224       39372 :         usedComboCids = 0;
     225             : 
     226       39372 :         hash_ctl.keysize = sizeof(ComboCidKeyData);
     227       39372 :         hash_ctl.entrysize = sizeof(ComboCidEntryData);
     228       39372 :         hash_ctl.hcxt = TopTransactionContext;
     229             : 
     230       39372 :         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      443212 :     if (usedComboCids >= sizeComboCids)
     242             :     {
     243         136 :         int         newsize = sizeComboCids * 2;
     244             : 
     245         136 :         comboCids = (ComboCidKeyData *)
     246         136 :             repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
     247         136 :         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      443212 :     key.cmin = cmin;
     254      443212 :     key.cmax = cmax;
     255      443212 :     entry = (ComboCidEntry) hash_search(comboHash,
     256             :                                         &key,
     257             :                                         HASH_ENTER,
     258             :                                         &found);
     259             : 
     260      443212 :     if (found)
     261             :     {
     262             :         /* Reuse an existing combo CID */
     263      234866 :         return entry->combocid;
     264             :     }
     265             : 
     266             :     /* We have to create a new combo CID; we already made room in the array */
     267      208346 :     combocid = usedComboCids;
     268             : 
     269      208346 :     comboCids[combocid].cmin = cmin;
     270      208346 :     comboCids[combocid].cmax = cmax;
     271      208346 :     usedComboCids++;
     272             : 
     273      208346 :     entry->combocid = combocid;
     274             : 
     275      208346 :     return combocid;
     276             : }
     277             : 
     278             : static CommandId
     279     5715912 : GetRealCmin(CommandId combocid)
     280             : {
     281             :     Assert(combocid < usedComboCids);
     282     5715912 :     return comboCids[combocid].cmin;
     283             : }
     284             : 
     285             : static CommandId
     286     5715780 : GetRealCmax(CommandId combocid)
     287             : {
     288             :     Assert(combocid < usedComboCids);
     289     5715780 :     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         816 : EstimateComboCIDStateSpace(void)
     298             : {
     299             :     Size        size;
     300             : 
     301             :     /* Add space required for saving usedComboCids */
     302         816 :     size = sizeof(int);
     303             : 
     304             :     /* Add space required for saving ComboCidKeyData */
     305         816 :     size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
     306             : 
     307         816 :     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         816 : SerializeComboCIDState(Size maxsize, char *start_address)
     317             : {
     318             :     char       *endptr;
     319             : 
     320             :     /* First, we store the number of currently-existing combo CIDs. */
     321         816 :     *(int *) start_address = usedComboCids;
     322             : 
     323             :     /* If maxsize is too small, throw an error. */
     324         816 :     endptr = start_address + sizeof(int) +
     325         816 :         (sizeof(ComboCidKeyData) * usedComboCids);
     326         816 :     if (endptr < start_address || endptr > start_address + maxsize)
     327           0 :         elog(ERROR, "not enough space to serialize ComboCID state");
     328             : 
     329             :     /* Now, copy the actual cmin/cmax pairs. */
     330         816 :     if (usedComboCids > 0)
     331         470 :         memcpy(start_address + sizeof(int), comboCids,
     332             :                (sizeof(ComboCidKeyData) * usedComboCids));
     333         816 : }
     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        2612 : 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        2612 :     num_elements = *(int *) comboCIDstate;
     353        2612 :     keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
     354             : 
     355             :     /* Use GetComboCommandId to restore each combo CID. */
     356       57200 :     for (i = 0; i < num_elements; i++)
     357             :     {
     358       54588 :         cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
     359             : 
     360             :         /* Verify that we got the expected answer. */
     361       54588 :         if (cid != i)
     362           0 :             elog(ERROR, "unexpected command ID while restoring combo CIDs");
     363             :     }
     364        2612 : }

Generated by: LCOV version 1.14