/*-------------------------------------------------------------------------

 *

 * combocid.c

 *    Combo command ID support routines

 *

 * Before version 8.3, HeapTupleHeaderData had separate fields for cmin

 * and cmax.  To reduce the header size, cmin and cmax are now overlaid

 * in the same field in the header.  That usually works because you rarely

 * insert and delete a tuple in the same transaction, and we don't need

 * either field to remain valid after the originating transaction exits.

 * To make it work when the inserting transaction does delete the tuple,

 * we create a "combo" command ID and store that in the tuple header

 * instead of cmin and cmax. The combo command ID can be mapped to the

 * real cmin and cmax using a backend-private array, which is managed by

 * this module.

 *

 * To allow reusing existing combo CIDs, we also keep a hash table that

 * maps cmin,cmax pairs to combo CIDs.  This keeps the data structure size

 * reasonable in most cases, since the number of unique pairs used by any

 * one transaction is likely to be small.

 *

 * With a 32-bit combo command id we can represent 2^32 distinct cmin,cmax

 * combinations. In the most perverse case where each command deletes a tuple

 * generated by every previous command, the number of combo command ids

 * required for N commands is N*(N+1)/2.  That means that in the worst case,

 * that's enough for 92682 commands.  In practice, you'll run out of memory

 * and/or disk space way before you reach that limit.

 *

 * The array and hash table are kept in TopTransactionContext, and are

 * destroyed at the end of each transaction.

 *

 *

 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 * IDENTIFICATION

 *    src/backend/utils/time/combocid.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "access/htup_details.h"

#include "access/xact.h"

#include "miscadmin.h"

#include "storage/shmem.h"

#include "utils/combocid.h"

#include "utils/hsearch.h"

#include "utils/memutils.h"

/* Hash table to lookup combo CIDs by cmin and cmax */

static HTAB *comboHash = NULL;

/* Key and entry structures for the hash table */

typedef struct

{

  CommandId cmin;

  CommandId cmax;

} ComboCidKeyData;

typedef ComboCidKeyData *ComboCidKey;

typedef struct

{

  ComboCidKeyData key;

  CommandId combocid;

} ComboCidEntryData;

typedef ComboCidEntryData *ComboCidEntry;

/* Initial size of the hash table */

#define CCID_HASH_SIZE      100

/*

 * An array of cmin,cmax pairs, indexed by combo command id.

 * To convert a combo CID to cmin and cmax, you do a simple array lookup.

 */

static ComboCidKey comboCids = NULL;

static int  usedComboCids = 0;  /* number of elements in comboCids */

static int  sizeComboCids = 0;  /* allocated size of array */

/* Initial size of the array */

#define CCID_ARRAY_SIZE     100

/* prototypes for internal functions */

static CommandId GetComboCommandId(CommandId cmin, CommandId cmax);

static CommandId GetRealCmin(CommandId combocid);

static CommandId GetRealCmax(CommandId combocid);

/**** External API ****/

/*

 * GetCmin and GetCmax assert that they are only called in situations where

 * they make sense, that is, can deliver a useful answer.  If you have

 * reason to examine a tuple's t_cid field from a transaction other than

 * the originating one, use HeapTupleHeaderGetRawCommandId() directly.

 */

CommandId

HeapTupleHeaderGetCmin(const HeapTupleHeaderData *tup)

{

  CommandId cid = HeapTupleHeaderGetRawCommandId(tup);

  Assert(!(tup->t_infomask & HEAP_MOVED));

  Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));

  if (tup->t_infomask & HEAP_COMBOCID)

    return GetRealCmin(cid);

  else

    return cid;

}

CommandId

HeapTupleHeaderGetCmax(const HeapTupleHeaderData *tup)

{

  CommandId cid = HeapTupleHeaderGetRawCommandId(tup);

  Assert(!(tup->t_infomask & HEAP_MOVED));

  /*

   * Because GetUpdateXid() performs memory allocations if xmax is a

   * multixact we can't Assert() if we're inside a critical section. This

   * weakens the check, but not using GetCmax() inside one would complicate

   * things too much.

   */

  Assert(CritSectionCount > 0 ||

       TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tup)));

  if (tup->t_infomask & HEAP_COMBOCID)

    return GetRealCmax(cid);

  else

    return cid;

}

/*

 * Given a tuple we are about to delete, determine the correct value to store

 * into its t_cid field.

 *

 * If we don't need a combo CID, *cmax is unchanged and *iscombo is set to

 * false.  If we do need one, *cmax is replaced by a combo CID and *iscombo

 * is set to true.

 *

 * The reason this is separate from the actual HeapTupleHeaderSetCmax()

 * operation is that this could fail due to out-of-memory conditions.  Hence

 * we need to do this before entering the critical section that actually

 * changes the tuple in shared buffers.

 */

void

HeapTupleHeaderAdjustCmax(const HeapTupleHeaderData *tup,

              CommandId *cmax,

              bool *iscombo)

{

  /*

   * If we're marking a tuple deleted that was inserted by (any

   * subtransaction of) our transaction, we need to use a combo command id.

   * Test for HeapTupleHeaderXminCommitted() first, because it's cheaper

   * than a TransactionIdIsCurrentTransactionId call.

   */

  if (!HeapTupleHeaderXminCommitted(tup) &&

    TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tup)))

  {

    CommandId cmin = HeapTupleHeaderGetCmin(tup);

    *cmax = GetComboCommandId(cmin, *cmax);

    *iscombo = true;

  }

  else

  {

    *iscombo = false;

  }

}

/*

 * Combo command ids are only interesting to the inserting and deleting

 * transaction, so we can forget about them at the end of transaction.

 */

void

AtEOXact_ComboCid(void)

{

  /*

   * Don't bother to pfree. These are allocated in TopTransactionContext, so

   * they're going to go away at the end of transaction anyway.

   */

  comboHash = NULL;

  comboCids = NULL;

  usedComboCids = 0;

  sizeComboCids = 0;

}

/**** Internal routines ****/

/*

 * Get a combo command id that maps to cmin and cmax.

 *

 * We try to reuse old combo command ids when possible.

 */

static CommandId

GetComboCommandId(CommandId cmin, CommandId cmax)

{

  CommandId combocid;

  ComboCidKeyData key;

  ComboCidEntry entry;

  bool    found;

  /*

   * Create the hash table and array the first time we need to use combo

   * cids in the transaction.

   */

  if (comboHash == NULL)

  {

    HASHCTL   hash_ctl;

    /* Make array first; existence of hash table asserts array exists */

    comboCids = (ComboCidKeyData *)

      MemoryContextAlloc(TopTransactionContext,

                 sizeof(ComboCidKeyData) * CCID_ARRAY_SIZE);

    sizeComboCids = CCID_ARRAY_SIZE;

    usedComboCids = 0;

    hash_ctl.keysize = sizeof(ComboCidKeyData);

    hash_ctl.entrysize = sizeof(ComboCidEntryData);

    hash_ctl.hcxt = TopTransactionContext;

    comboHash = hash_create("Combo CIDs",

                CCID_HASH_SIZE,

                &hash_ctl,

                HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);

  }

  /*

   * Grow the array if there's not at least one free slot.  We must do this

   * before possibly entering a new hashtable entry, else failure to

   * repalloc would leave a corrupt hashtable entry behind.

   */

  if (usedComboCids >= sizeComboCids)

  {

    int     newsize = sizeComboCids * 2;

    comboCids = (ComboCidKeyData *)

      repalloc(comboCids, sizeof(ComboCidKeyData) * newsize);

    sizeComboCids = newsize;

  }

  /* Lookup or create a hash entry with the desired cmin/cmax */

  /* We assume there is no struct padding in ComboCidKeyData! */

  key.cmin = cmin;

  key.cmax = cmax;

  entry = (ComboCidEntry) hash_search(comboHash,

                    &key,

                    HASH_ENTER,

                    &found);

  if (found)

  {

    /* Reuse an existing combo CID */

    return entry->combocid;

  }

  /* We have to create a new combo CID; we already made room in the array */

  combocid = usedComboCids;

  comboCids[combocid].cmin = cmin;

  comboCids[combocid].cmax = cmax;

  usedComboCids++;

  entry->combocid = combocid;

  return combocid;

}

static CommandId

GetRealCmin(CommandId combocid)

{

  Assert(combocid < usedComboCids);

  return comboCids[combocid].cmin;

}

static CommandId

GetRealCmax(CommandId combocid)

{

  Assert(combocid < usedComboCids);

  return comboCids[combocid].cmax;

}

/*

 * Estimate the amount of space required to serialize the current combo CID

 * state.

 */

Size

EstimateComboCIDStateSpace(void)

{

  Size    size;

  /* Add space required for saving usedComboCids */

  size = sizeof(int);

  /* Add space required for saving ComboCidKeyData */

  size = add_size(size, mul_size(sizeof(ComboCidKeyData), usedComboCids));

  return size;

}

/*

 * Serialize the combo CID state into the memory, beginning at start_address.

 * maxsize should be at least as large as the value returned by

 * EstimateComboCIDStateSpace.

 */

void

SerializeComboCIDState(Size maxsize, char *start_address)

{

  char     *endptr;

  /* First, we store the number of currently-existing combo CIDs. */

  *(int *) start_address = usedComboCids;

  /* If maxsize is too small, throw an error. */

  endptr = start_address + sizeof(int) +

    (sizeof(ComboCidKeyData) * usedComboCids);

  if (endptr < start_address || endptr > start_address + maxsize)

    elog(ERROR, "not enough space to serialize ComboCID state");

  /* Now, copy the actual cmin/cmax pairs. */

  if (usedComboCids > 0)

    memcpy(start_address + sizeof(int), comboCids,

         (sizeof(ComboCidKeyData) * usedComboCids));

}

/*

 * Read the combo CID state at the specified address and initialize this

 * backend with the same combo CIDs.  This is only valid in a backend that

 * currently has no combo CIDs (and only makes sense if the transaction state

 * is serialized and restored as well).

 */

void

RestoreComboCIDState(char *comboCIDstate)

{

  int     num_elements;

  ComboCidKeyData *keydata;

  int     i;

  CommandId cid;

  Assert(!comboCids && !comboHash);

  /* First, we retrieve the number of combo CIDs that were serialized. */

  num_elements = *(int *) comboCIDstate;

  keydata = (ComboCidKeyData *) (comboCIDstate + sizeof(int));

  /* Use GetComboCommandId to restore each combo CID. */

  for (i = 0; i < num_elements; i++)

  {

    cid = GetComboCommandId(keydata[i].cmin, keydata[i].cmax);

    /* Verify that we got the expected answer. */

    if (cid != i)

      elog(ERROR, "unexpected command ID while restoring combo CIDs");

  }

}