LCOV - code coverage report
Current view: top level - src/backend/utils/time - combocid.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 75 77 97.4 %
Date: 2019-11-15 23:07:02 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 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-2019, 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    10260770 : HeapTupleHeaderGetCmin(HeapTupleHeader tup)
     105             : {
     106    10260770 :     CommandId   cid = HeapTupleHeaderGetRawCommandId(tup);
     107             : 
     108             :     Assert(!(tup->t_infomask & HEAP_MOVED));
     109             :     Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
     110             : 
     111    10260770 :     if (tup->t_infomask & HEAP_COMBOCID)
     112      133214 :         return GetRealCmin(cid);
     113             :     else
     114    10127556 :         return cid;
     115             : }
     116             : 
     117             : CommandId
     118      243586 : HeapTupleHeaderGetCmax(HeapTupleHeader tup)
     119             : {
     120      243586 :     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      243586 :     if (tup->t_infomask & HEAP_COMBOCID)
     134      133142 :         return GetRealCmax(cid);
     135             :     else
     136      110444 :         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     1875048 : 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     2001152 :     if (!HeapTupleHeaderXminCommitted(tup) &&
     164      126104 :         TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tup)))
     165      125408 :     {
     166      125408 :         CommandId   cmin = HeapTupleHeaderGetCmin(tup);
     167             : 
     168      125408 :         *cmax = GetComboCommandId(cmin, *cmax);
     169      125408 :         *iscombo = true;
     170             :     }
     171             :     else
     172             :     {
     173     1749640 :         *iscombo = false;
     174             :     }
     175     1875048 : }
     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      458574 : 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      458574 :     comboHash = NULL;
     189             : 
     190      458574 :     comboCids = NULL;
     191      458574 :     usedComboCids = 0;
     192      458574 :     sizeComboCids = 0;
     193      458574 : }
     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      158034 : 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      158034 :     if (comboHash == NULL)
     216             :     {
     217             :         HASHCTL     hash_ctl;
     218             : 
     219             :         /* Make array first; existence of hash table asserts array exists */
     220       57016 :         comboCids = (ComboCidKeyData *)
     221       57016 :             MemoryContextAlloc(TopTransactionContext,
     222             :                                sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);
     223       57016 :         sizeComboCids = CCID_ARRAY_SIZE;
     224       57016 :         usedComboCids = 0;
     225             : 
     226       57016 :         memset(&hash_ctl, 0, sizeof(hash_ctl));
     227       57016 :         hash_ctl.keysize = sizeof(ComboCidKeyData);
     228       57016 :         hash_ctl.entrysize = sizeof(ComboCidEntryData);
     229       57016 :         hash_ctl.hcxt = TopTransactionContext;
     230             : 
     231       57016 :         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      158034 :     if (usedComboCids >= sizeComboCids)
     243             :     {
     244           8 :         int         newsize = sizeComboCids * 2;
     245             : 
     246           8 :         comboCids = (ComboCidKeyData *)
     247           8 :             repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);
     248           8 :         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      158034 :     key.cmin = cmin;
     255      158034 :     key.cmax = cmax;
     256      158034 :     entry = (ComboCidEntry) hash_search(comboHash,
     257             :                                         (void *) &key,
     258             :                                         HASH_ENTER,
     259             :                                         &found);
     260             : 
     261      158034 :     if (found)
     262             :     {
     263             :         /* Reuse an existing combo cid */
     264       49162 :         return entry->combocid;
     265             :     }
     266             : 
     267             :     /* We have to create a new combo cid; we already made room in the array */
     268      108872 :     combocid = usedComboCids;
     269             : 
     270      108872 :     comboCids[combocid].cmin = cmin;
     271      108872 :     comboCids[combocid].cmax = cmax;
     272      108872 :     usedComboCids++;
     273             : 
     274      108872 :     entry->combocid = combocid;
     275             : 
     276      108872 :     return combocid;
     277             : }
     278             : 
     279             : static CommandId
     280      133214 : GetRealCmin(CommandId combocid)
     281             : {
     282             :     Assert(combocid < usedComboCids);
     283      133214 :     return comboCids[combocid].cmin;
     284             : }
     285             : 
     286             : static CommandId
     287      133142 : GetRealCmax(CommandId combocid)
     288             : {
     289             :     Assert(combocid < usedComboCids);
     290      133142 :     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         446 : EstimateComboCIDStateSpace(void)
     299             : {
     300             :     Size        size;
     301             : 
     302             :     /* Add space required for saving usedComboCids */
     303         446 :     size = sizeof(int);
     304             : 
     305             :     /* Add space required for saving the combocids key */
     306         446 :     size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));
     307             : 
     308         446 :     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         446 : SerializeComboCIDState(Size maxsize, char *start_address)
     318             : {
     319             :     char       *endptr;
     320             : 
     321             :     /* First, we store the number of currently-existing ComboCIDs. */
     322         446 :     *(int *) start_address = usedComboCids;
     323             : 
     324             :     /* If maxsize is too small, throw an error. */
     325         446 :     endptr = start_address + sizeof(int) +
     326         446 :         (sizeof(ComboCidKeyData) * usedComboCids);
     327         446 :     if (endptr < start_address || endptr > start_address + maxsize)
     328           0 :         elog(ERROR, "not enough space to serialize ComboCID state");
     329             : 
     330             :     /* Now, copy the actual cmin/cmax pairs. */
     331         446 :     if (usedComboCids > 0)
     332         278 :         memcpy(start_address + sizeof(int), comboCids,
     333             :                (sizeof(ComboCidKeyData) * usedComboCids));
     334         446 : }
     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        1520 : 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        1520 :     num_elements = *(int *) comboCIDstate;
     354        1520 :     keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));
     355             : 
     356             :     /* Use GetComboCommandId to restore each ComboCID. */
     357       34146 :     for (i = 0; i < num_elements; i++)
     358             :     {
     359       32626 :         cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);
     360             : 
     361             :         /* Verify that we got the expected answer. */
     362       32626 :         if (cid != i)
     363           0 :             elog(ERROR, "unexpected command ID while restoring combo CIDs");
     364             :     }
     365        1520 : }

Generated by: LCOV version 1.13