granicus.if.org Git - postgresql/blob - src/backend/utils/time/tqual.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * tqual.c
   4  *        POSTGRES "time qualification" code, ie, tuple visibility rules.
   5  *
   6  * NOTE: all the HeapTupleSatisfies routines will update the tuple's
   7  * "hint" status bits if we see that the inserting or deleting transaction
   8  * has now committed or aborted (and it is safe to set the hint bits).
   9  * If the hint bits are changed, SetBufferCommitInfoNeedsSave is called on
  10  * the passed-in buffer.  The caller must hold not only a pin, but at least
  11  * shared buffer content lock on the buffer containing the tuple.
  12  *
  13  * NOTE: must check TransactionIdIsInProgress (which looks in PGXACT array)
  14  * before TransactionIdDidCommit/TransactionIdDidAbort (which look in
  15  * pg_clog).  Otherwise we have a race condition: we might decide that a
  16  * just-committed transaction crashed, because none of the tests succeed.
  17  * xact.c is careful to record commit/abort in pg_clog before it unsets
  18  * MyPgXact->xid in PGXACT array.  That fixes that problem, but it also
  19  * means there is a window where TransactionIdIsInProgress and
  20  * TransactionIdDidCommit will both return true.  If we check only
  21  * TransactionIdDidCommit, we could consider a tuple committed when a
  22  * later GetSnapshotData call will still think the originating transaction
  23  * is in progress, which leads to application-level inconsistency.      The
  24  * upshot is that we gotta check TransactionIdIsInProgress first in all
  25  * code paths, except for a few cases where we are looking at
  26  * subtransactions of our own main transaction and so there can't be any
  27  * race condition.
  28  *
  29  * Summary of visibility functions:
  30  *
  31  *       HeapTupleSatisfiesMVCC()
  32  *                visible to supplied snapshot, excludes current command
  33  *       HeapTupleSatisfiesNow()
  34  *                visible to instant snapshot, excludes current command
  35  *       HeapTupleSatisfiesUpdate()
  36  *                like HeapTupleSatisfiesNow(), but with user-supplied command
  37  *                counter and more complex result
  38  *       HeapTupleSatisfiesSelf()
  39  *                visible to instant snapshot and current command
  40  *       HeapTupleSatisfiesDirty()
  41  *                like HeapTupleSatisfiesSelf(), but includes open transactions
  42  *       HeapTupleSatisfiesVacuum()
  43  *                visible to any running transaction, used by VACUUM
  44  *       HeapTupleSatisfiesToast()
  45  *                visible unless part of interrupted vacuum, used for TOAST
  46  *       HeapTupleSatisfiesAny()
  47  *                all tuples are visible
  48  *
  49  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
  50  * Portions Copyright (c) 1994, Regents of the University of California
  51  *
  52  * IDENTIFICATION
  53  *        src/backend/utils/time/tqual.c
  54  *
  55  *-------------------------------------------------------------------------
  56  */
  57
  58 #include "postgres.h"
  59
  60 #include "access/htup_details.h"
  61 #include "access/multixact.h"
  62 #include "access/subtrans.h"
  63 #include "access/transam.h"
  64 #include "access/xact.h"
  65 #include "storage/bufmgr.h"
  66 #include "storage/procarray.h"
  67 #include "utils/tqual.h"
  68
  69
  70 /* Static variables representing various special snapshot semantics */
  71 SnapshotData SnapshotNowData = {HeapTupleSatisfiesNow};
  72 SnapshotData SnapshotSelfData = {HeapTupleSatisfiesSelf};
  73 SnapshotData SnapshotAnyData = {HeapTupleSatisfiesAny};
  74 SnapshotData SnapshotToastData = {HeapTupleSatisfiesToast};
  75
  76 /* local functions */
  77 static bool XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot);
  78
  79
  80 /*
  81  * SetHintBits()
  82  *
  83  * Set commit/abort hint bits on a tuple, if appropriate at this time.
  84  *
  85  * It is only safe to set a transaction-committed hint bit if we know the
  86  * transaction's commit record has been flushed to disk, or if the table is
  87  * temporary or unlogged and will be obliterated by a crash anyway.  We
  88  * cannot change the LSN of the page here because we may hold only a share
  89  * lock on the buffer, so we can't use the LSN to interlock this; we have to
  90  * just refrain from setting the hint bit until some future re-examination
  91  * of the tuple.
  92  *
  93  * We can always set hint bits when marking a transaction aborted.      (Some
  94  * code in heapam.c relies on that!)
  95  *
  96  * Also, if we are cleaning up HEAP_MOVED_IN or HEAP_MOVED_OFF entries, then
  97  * we can always set the hint bits, since pre-9.0 VACUUM FULL always used
  98  * synchronous commits and didn't move tuples that weren't previously
  99  * hinted.      (This is not known by this subroutine, but is applied by its
 100  * callers.)  Note: old-style VACUUM FULL is gone, but we have to keep this
 101  * module's support for MOVED_OFF/MOVED_IN flag bits for as long as we
 102  * support in-place update from pre-9.0 databases.
 103  *
 104  * Normal commits may be asynchronous, so for those we need to get the LSN
 105  * of the transaction and then check whether this is flushed.
 106  *
 107  * The caller should pass xid as the XID of the transaction to check, or
 108  * InvalidTransactionId if no check is needed.
 109  */
 110 static inline void
 111 SetHintBits(HeapTupleHeader tuple, Buffer buffer,
 112                         uint16 infomask, TransactionId xid)
 113 {
 114         if (TransactionIdIsValid(xid))
 115         {
 116                 /* NB: xid must be known committed here! */
 117                 XLogRecPtr      commitLSN = TransactionIdGetCommitLSN(xid);
 118
 119                 if (XLogNeedsFlush(commitLSN) && BufferIsPermanent(buffer))
 120                         return;                         /* not flushed yet, so don't set hint */
 121         }
 122
 123         tuple->t_infomask |= infomask;
 124         SetBufferCommitInfoNeedsSave(buffer);
 125 }
 126
 127 /*
 128  * HeapTupleSetHintBits --- exported version of SetHintBits()
 129  *
 130  * This must be separate because of C99's brain-dead notions about how to
 131  * implement inline functions.
 132  */
 133 void
 134 HeapTupleSetHintBits(HeapTupleHeader tuple, Buffer buffer,
 135                                          uint16 infomask, TransactionId xid)
 136 {
 137         SetHintBits(tuple, buffer, infomask, xid);
 138 }
 139
 140
 141 /*
 142  * HeapTupleSatisfiesSelf
 143  *              True iff heap tuple is valid "for itself".
 144  *
 145  *      Here, we consider the effects of:
 146  *              all committed transactions (as of the current instant)
 147  *              previous commands of this transaction
 148  *              changes made by the current command
 149  *
 150  * Note:
 151  *              Assumes heap tuple is valid.
 152  *
 153  * The satisfaction of "itself" requires the following:
 154  *
 155  * ((Xmin == my-transaction &&                          the row was updated by the current transaction, and
 156  *              (Xmax is null                                           it was not deleted
 157  *               [|| Xmax != my-transaction)])                  [or it was deleted by another transaction]
 158  * ||
 159  *
 160  * (Xmin is committed &&                                        the row was modified by a committed transaction, and
 161  *              (Xmax is null ||                                        the row has not been deleted, or
 162  *                      (Xmax != my-transaction &&                      the row was deleted by another transaction
 163  *                       Xmax is not committed)))                       that has not been committed
 164  */
 165 bool
 166 HeapTupleSatisfiesSelf(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
 167 {
 168         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 169         {
 170                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 171                         return false;
 172
 173                 /* Used by pre-9.0 binary upgrades */
 174                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 175                 {
 176                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 177
 178                         if (TransactionIdIsCurrentTransactionId(xvac))
 179                                 return false;
 180                         if (!TransactionIdIsInProgress(xvac))
 181                         {
 182                                 if (TransactionIdDidCommit(xvac))
 183                                 {
 184                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 185                                                                 InvalidTransactionId);
 186                                         return false;
 187                                 }
 188                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 189                                                         InvalidTransactionId);
 190                         }
 191                 }
 192                 /* Used by pre-9.0 binary upgrades */
 193                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 194                 {
 195                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 196
 197                         if (!TransactionIdIsCurrentTransactionId(xvac))
 198                         {
 199                                 if (TransactionIdIsInProgress(xvac))
 200                                         return false;
 201                                 if (TransactionIdDidCommit(xvac))
 202                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 203                                                                 InvalidTransactionId);
 204                                 else
 205                                 {
 206                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 207                                                                 InvalidTransactionId);
 208                                         return false;
 209                                 }
 210                         }
 211                 }
 212                 else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
 213                 {
 214                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
 215                                 return true;
 216
 217                         if (tuple->t_infomask & HEAP_IS_LOCKED)         /* not deleter */
 218                                 return true;
 219
 220                         Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 221
 222                         if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 223                         {
 224                                 /* deleting subtransaction must have aborted */
 225                                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 226                                                         InvalidTransactionId);
 227                                 return true;
 228                         }
 229
 230                         return false;
 231                 }
 232                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
 233                         return false;
 234                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
 235                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 236                                                 HeapTupleHeaderGetXmin(tuple));
 237                 else
 238                 {
 239                         /* it must have aborted or crashed */
 240                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 241                                                 InvalidTransactionId);
 242                         return false;
 243                 }
 244         }
 245
 246         /* by here, the inserting transaction has committed */
 247
 248         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid or aborted */
 249                 return true;
 250
 251         if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
 252         {
 253                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 254                         return true;
 255                 return false;                   /* updated by other */
 256         }
 257
 258         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
 259         {
 260                 /* MultiXacts are currently only allowed to lock tuples */
 261                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
 262                 return true;
 263         }
 264
 265         if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 266         {
 267                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 268                         return true;
 269                 return false;
 270         }
 271
 272         if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
 273                 return true;
 274
 275         if (!TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
 276         {
 277                 /* it must have aborted or crashed */
 278                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 279                                         InvalidTransactionId);
 280                 return true;
 281         }
 282
 283         /* xmax transaction committed */
 284
 285         if (tuple->t_infomask & HEAP_IS_LOCKED)
 286         {
 287                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 288                                         InvalidTransactionId);
 289                 return true;
 290         }
 291
 292         SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
 293                                 HeapTupleHeaderGetXmax(tuple));
 294         return false;
 295 }
 296
 297 /*
 298  * HeapTupleSatisfiesNow
 299  *              True iff heap tuple is valid "now".
 300  *
 301  *      Here, we consider the effects of:
 302  *              all committed transactions (as of the current instant)
 303  *              previous commands of this transaction
 304  *
 305  * Note we do _not_ include changes made by the current command.  This
 306  * solves the "Halloween problem" wherein an UPDATE might try to re-update
 307  * its own output tuples, http://en.wikipedia.org/wiki/Halloween_Problem.
 308  *
 309  * Note:
 310  *              Assumes heap tuple is valid.
 311  *
 312  * The satisfaction of "now" requires the following:
 313  *
 314  * ((Xmin == my-transaction &&                          inserted by the current transaction
 315  *       Cmin < my-command &&                                   before this command, and
 316  *       (Xmax is null ||                                               the row has not been deleted, or
 317  *        (Xmax == my-transaction &&                    it was deleted by the current transaction
 318  *         Cmax >= my-command)))                                but not before this command,
 319  * ||                                                                           or
 320  *      (Xmin is committed &&                                   the row was inserted by a committed transaction, and
 321  *              (Xmax is null ||                                        the row has not been deleted, or
 322  *               (Xmax == my-transaction &&                     the row is being deleted by this transaction
 323  *                Cmax >= my-command) ||                        but it's not deleted "yet", or
 324  *               (Xmax != my-transaction &&                     the row was deleted by another transaction
 325  *                Xmax is not committed))))                     that has not been committed
 326  *
 327  */
 328 bool
 329 HeapTupleSatisfiesNow(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
 330 {
 331         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 332         {
 333                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 334                         return false;
 335
 336                 /* Used by pre-9.0 binary upgrades */
 337                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 338                 {
 339                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 340
 341                         if (TransactionIdIsCurrentTransactionId(xvac))
 342                                 return false;
 343                         if (!TransactionIdIsInProgress(xvac))
 344                         {
 345                                 if (TransactionIdDidCommit(xvac))
 346                                 {
 347                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 348                                                                 InvalidTransactionId);
 349                                         return false;
 350                                 }
 351                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 352                                                         InvalidTransactionId);
 353                         }
 354                 }
 355                 /* Used by pre-9.0 binary upgrades */
 356                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 357                 {
 358                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 359
 360                         if (!TransactionIdIsCurrentTransactionId(xvac))
 361                         {
 362                                 if (TransactionIdIsInProgress(xvac))
 363                                         return false;
 364                                 if (TransactionIdDidCommit(xvac))
 365                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 366                                                                 InvalidTransactionId);
 367                                 else
 368                                 {
 369                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 370                                                                 InvalidTransactionId);
 371                                         return false;
 372                                 }
 373                         }
 374                 }
 375                 else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
 376                 {
 377                         if (HeapTupleHeaderGetCmin(tuple) >= GetCurrentCommandId(false))
 378                                 return false;   /* inserted after scan started */
 379
 380                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
 381                                 return true;
 382
 383                         if (tuple->t_infomask & HEAP_IS_LOCKED)         /* not deleter */
 384                                 return true;
 385
 386                         Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 387
 388                         if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 389                         {
 390                                 /* deleting subtransaction must have aborted */
 391                                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 392                                                         InvalidTransactionId);
 393                                 return true;
 394                         }
 395
 396                         if (HeapTupleHeaderGetCmax(tuple) >= GetCurrentCommandId(false))
 397                                 return true;    /* deleted after scan started */
 398                         else
 399                                 return false;   /* deleted before scan started */
 400                 }
 401                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
 402                         return false;
 403                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
 404                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 405                                                 HeapTupleHeaderGetXmin(tuple));
 406                 else
 407                 {
 408                         /* it must have aborted or crashed */
 409                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 410                                                 InvalidTransactionId);
 411                         return false;
 412                 }
 413         }
 414
 415         /* by here, the inserting transaction has committed */
 416
 417         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid or aborted */
 418                 return true;
 419
 420         if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
 421         {
 422                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 423                         return true;
 424                 return false;
 425         }
 426
 427         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
 428         {
 429                 /* MultiXacts are currently only allowed to lock tuples */
 430                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
 431                 return true;
 432         }
 433
 434         if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 435         {
 436                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 437                         return true;
 438                 if (HeapTupleHeaderGetCmax(tuple) >= GetCurrentCommandId(false))
 439                         return true;            /* deleted after scan started */
 440                 else
 441                         return false;           /* deleted before scan started */
 442         }
 443
 444         if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
 445                 return true;
 446
 447         if (!TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
 448         {
 449                 /* it must have aborted or crashed */
 450                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 451                                         InvalidTransactionId);
 452                 return true;
 453         }
 454
 455         /* xmax transaction committed */
 456
 457         if (tuple->t_infomask & HEAP_IS_LOCKED)
 458         {
 459                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 460                                         InvalidTransactionId);
 461                 return true;
 462         }
 463
 464         SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
 465                                 HeapTupleHeaderGetXmax(tuple));
 466         return false;
 467 }
 468
 469 /*
 470  * HeapTupleSatisfiesAny
 471  *              Dummy "satisfies" routine: any tuple satisfies SnapshotAny.
 472  */
 473 bool
 474 HeapTupleSatisfiesAny(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
 475 {
 476         return true;
 477 }
 478
 479 /*
 480  * HeapTupleSatisfiesToast
 481  *              True iff heap tuple is valid as a TOAST row.
 482  *
 483  * This is a simplified version that only checks for VACUUM moving conditions.
 484  * It's appropriate for TOAST usage because TOAST really doesn't want to do
 485  * its own time qual checks; if you can see the main table row that contains
 486  * a TOAST reference, you should be able to see the TOASTed value.      However,
 487  * vacuuming a TOAST table is independent of the main table, and in case such
 488  * a vacuum fails partway through, we'd better do this much checking.
 489  *
 490  * Among other things, this means you can't do UPDATEs of rows in a TOAST
 491  * table.
 492  */
 493 bool
 494 HeapTupleSatisfiesToast(HeapTupleHeader tuple, Snapshot snapshot,
 495                                                 Buffer buffer)
 496 {
 497         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 498         {
 499                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 500                         return false;
 501
 502                 /* Used by pre-9.0 binary upgrades */
 503                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 504                 {
 505                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 506
 507                         if (TransactionIdIsCurrentTransactionId(xvac))
 508                                 return false;
 509                         if (!TransactionIdIsInProgress(xvac))
 510                         {
 511                                 if (TransactionIdDidCommit(xvac))
 512                                 {
 513                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 514                                                                 InvalidTransactionId);
 515                                         return false;
 516                                 }
 517                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 518                                                         InvalidTransactionId);
 519                         }
 520                 }
 521                 /* Used by pre-9.0 binary upgrades */
 522                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 523                 {
 524                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 525
 526                         if (!TransactionIdIsCurrentTransactionId(xvac))
 527                         {
 528                                 if (TransactionIdIsInProgress(xvac))
 529                                         return false;
 530                                 if (TransactionIdDidCommit(xvac))
 531                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 532                                                                 InvalidTransactionId);
 533                                 else
 534                                 {
 535                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 536                                                                 InvalidTransactionId);
 537                                         return false;
 538                                 }
 539                         }
 540                 }
 541         }
 542
 543         /* otherwise assume the tuple is valid for TOAST. */
 544         return true;
 545 }
 546
 547 /*
 548  * HeapTupleSatisfiesUpdate
 549  *
 550  *      Same logic as HeapTupleSatisfiesNow, but returns a more detailed result
 551  *      code, since UPDATE needs to know more than "is it visible?".  Also,
 552  *      tuples of my own xact are tested against the passed CommandId not
 553  *      CurrentCommandId.
 554  *
 555  *      The possible return codes are:
 556  *
 557  *      HeapTupleInvisible: the tuple didn't exist at all when the scan started,
 558  *      e.g. it was created by a later CommandId.
 559  *
 560  *      HeapTupleMayBeUpdated: The tuple is valid and visible, so it may be
 561  *      updated.
 562  *
 563  *      HeapTupleSelfUpdated: The tuple was updated by the current transaction,
 564  *      after the current scan started.
 565  *
 566  *      HeapTupleUpdated: The tuple was updated by a committed transaction.
 567  *
 568  *      HeapTupleBeingUpdated: The tuple is being updated by an in-progress
 569  *      transaction other than the current transaction.  (Note: this includes
 570  *      the case where the tuple is share-locked by a MultiXact, even if the
 571  *      MultiXact includes the current transaction.  Callers that want to
 572  *      distinguish that case must test for it themselves.)
 573  */
 574 HTSU_Result
 575 HeapTupleSatisfiesUpdate(HeapTupleHeader tuple, CommandId curcid,
 576                                                  Buffer buffer)
 577 {
 578         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 579         {
 580                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 581                         return HeapTupleInvisible;
 582
 583                 /* Used by pre-9.0 binary upgrades */
 584                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 585                 {
 586                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 587
 588                         if (TransactionIdIsCurrentTransactionId(xvac))
 589                                 return HeapTupleInvisible;
 590                         if (!TransactionIdIsInProgress(xvac))
 591                         {
 592                                 if (TransactionIdDidCommit(xvac))
 593                                 {
 594                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 595                                                                 InvalidTransactionId);
 596                                         return HeapTupleInvisible;
 597                                 }
 598                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 599                                                         InvalidTransactionId);
 600                         }
 601                 }
 602                 /* Used by pre-9.0 binary upgrades */
 603                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 604                 {
 605                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 606
 607                         if (!TransactionIdIsCurrentTransactionId(xvac))
 608                         {
 609                                 if (TransactionIdIsInProgress(xvac))
 610                                         return HeapTupleInvisible;
 611                                 if (TransactionIdDidCommit(xvac))
 612                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 613                                                                 InvalidTransactionId);
 614                                 else
 615                                 {
 616                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 617                                                                 InvalidTransactionId);
 618                                         return HeapTupleInvisible;
 619                                 }
 620                         }
 621                 }
 622                 else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
 623                 {
 624                         if (HeapTupleHeaderGetCmin(tuple) >= curcid)
 625                                 return HeapTupleInvisible;              /* inserted after scan started */
 626
 627                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
 628                                 return HeapTupleMayBeUpdated;
 629
 630                         if (tuple->t_infomask & HEAP_IS_LOCKED)         /* not deleter */
 631                                 return HeapTupleMayBeUpdated;
 632
 633                         Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 634
 635                         if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 636                         {
 637                                 /* deleting subtransaction must have aborted */
 638                                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 639                                                         InvalidTransactionId);
 640                                 return HeapTupleMayBeUpdated;
 641                         }
 642
 643                         if (HeapTupleHeaderGetCmax(tuple) >= curcid)
 644                                 return HeapTupleSelfUpdated;    /* updated after scan started */
 645                         else
 646                                 return HeapTupleInvisible;              /* updated before scan started */
 647                 }
 648                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
 649                         return HeapTupleInvisible;
 650                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
 651                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 652                                                 HeapTupleHeaderGetXmin(tuple));
 653                 else
 654                 {
 655                         /* it must have aborted or crashed */
 656                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 657                                                 InvalidTransactionId);
 658                         return HeapTupleInvisible;
 659                 }
 660         }
 661
 662         /* by here, the inserting transaction has committed */
 663
 664         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid or aborted */
 665                 return HeapTupleMayBeUpdated;
 666
 667         if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
 668         {
 669                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 670                         return HeapTupleMayBeUpdated;
 671                 return HeapTupleUpdated;        /* updated by other */
 672         }
 673
 674         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
 675         {
 676                 /* MultiXacts are currently only allowed to lock tuples */
 677                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
 678
 679                 if (MultiXactIdIsRunning(HeapTupleHeaderGetXmax(tuple)))
 680                         return HeapTupleBeingUpdated;
 681                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 682                                         InvalidTransactionId);
 683                 return HeapTupleMayBeUpdated;
 684         }
 685
 686         if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 687         {
 688                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 689                         return HeapTupleMayBeUpdated;
 690                 if (HeapTupleHeaderGetCmax(tuple) >= curcid)
 691                         return HeapTupleSelfUpdated;            /* updated after scan started */
 692                 else
 693                         return HeapTupleInvisible;      /* updated before scan started */
 694         }
 695
 696         if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
 697                 return HeapTupleBeingUpdated;
 698
 699         if (!TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
 700         {
 701                 /* it must have aborted or crashed */
 702                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 703                                         InvalidTransactionId);
 704                 return HeapTupleMayBeUpdated;
 705         }
 706
 707         /* xmax transaction committed */
 708
 709         if (tuple->t_infomask & HEAP_IS_LOCKED)
 710         {
 711                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 712                                         InvalidTransactionId);
 713                 return HeapTupleMayBeUpdated;
 714         }
 715
 716         SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
 717                                 HeapTupleHeaderGetXmax(tuple));
 718         return HeapTupleUpdated;        /* updated by other */
 719 }
 720
 721 /*
 722  * HeapTupleSatisfiesDirty
 723  *              True iff heap tuple is valid including effects of open transactions.
 724  *
 725  *      Here, we consider the effects of:
 726  *              all committed and in-progress transactions (as of the current instant)
 727  *              previous commands of this transaction
 728  *              changes made by the current command
 729  *
 730  * This is essentially like HeapTupleSatisfiesSelf as far as effects of
 731  * the current transaction and committed/aborted xacts are concerned.
 732  * However, we also include the effects of other xacts still in progress.
 733  *
 734  * A special hack is that the passed-in snapshot struct is used as an
 735  * output argument to return the xids of concurrent xacts that affected the
 736  * tuple.  snapshot->xmin is set to the tuple's xmin if that is another
 737  * transaction that's still in progress; or to InvalidTransactionId if the
 738  * tuple's xmin is committed good, committed dead, or my own xact.  Similarly
 739  * for snapshot->xmax and the tuple's xmax.
 740  */
 741 bool
 742 HeapTupleSatisfiesDirty(HeapTupleHeader tuple, Snapshot snapshot,
 743                                                 Buffer buffer)
 744 {
 745         snapshot->xmin = snapshot->xmax = InvalidTransactionId;
 746
 747         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 748         {
 749                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 750                         return false;
 751
 752                 /* Used by pre-9.0 binary upgrades */
 753                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 754                 {
 755                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 756
 757                         if (TransactionIdIsCurrentTransactionId(xvac))
 758                                 return false;
 759                         if (!TransactionIdIsInProgress(xvac))
 760                         {
 761                                 if (TransactionIdDidCommit(xvac))
 762                                 {
 763                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 764                                                                 InvalidTransactionId);
 765                                         return false;
 766                                 }
 767                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 768                                                         InvalidTransactionId);
 769                         }
 770                 }
 771                 /* Used by pre-9.0 binary upgrades */
 772                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 773                 {
 774                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 775
 776                         if (!TransactionIdIsCurrentTransactionId(xvac))
 777                         {
 778                                 if (TransactionIdIsInProgress(xvac))
 779                                         return false;
 780                                 if (TransactionIdDidCommit(xvac))
 781                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 782                                                                 InvalidTransactionId);
 783                                 else
 784                                 {
 785                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 786                                                                 InvalidTransactionId);
 787                                         return false;
 788                                 }
 789                         }
 790                 }
 791                 else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
 792                 {
 793                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
 794                                 return true;
 795
 796                         if (tuple->t_infomask & HEAP_IS_LOCKED)         /* not deleter */
 797                                 return true;
 798
 799                         Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 800
 801                         if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 802                         {
 803                                 /* deleting subtransaction must have aborted */
 804                                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 805                                                         InvalidTransactionId);
 806                                 return true;
 807                         }
 808
 809                         return false;
 810                 }
 811                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
 812                 {
 813                         snapshot->xmin = HeapTupleHeaderGetXmin(tuple);
 814                         /* XXX shouldn't we fall through to look at xmax? */
 815                         return true;            /* in insertion by other */
 816                 }
 817                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
 818                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 819                                                 HeapTupleHeaderGetXmin(tuple));
 820                 else
 821                 {
 822                         /* it must have aborted or crashed */
 823                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 824                                                 InvalidTransactionId);
 825                         return false;
 826                 }
 827         }
 828
 829         /* by here, the inserting transaction has committed */
 830
 831         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid or aborted */
 832                 return true;
 833
 834         if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
 835         {
 836                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 837                         return true;
 838                 return false;                   /* updated by other */
 839         }
 840
 841         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
 842         {
 843                 /* MultiXacts are currently only allowed to lock tuples */
 844                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
 845                 return true;
 846         }
 847
 848         if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 849         {
 850                 if (tuple->t_infomask & HEAP_IS_LOCKED)
 851                         return true;
 852                 return false;
 853         }
 854
 855         if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
 856         {
 857                 snapshot->xmax = HeapTupleHeaderGetXmax(tuple);
 858                 return true;
 859         }
 860
 861         if (!TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
 862         {
 863                 /* it must have aborted or crashed */
 864                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 865                                         InvalidTransactionId);
 866                 return true;
 867         }
 868
 869         /* xmax transaction committed */
 870
 871         if (tuple->t_infomask & HEAP_IS_LOCKED)
 872         {
 873                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 874                                         InvalidTransactionId);
 875                 return true;
 876         }
 877
 878         SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
 879                                 HeapTupleHeaderGetXmax(tuple));
 880         return false;                           /* updated by other */
 881 }
 882
 883 /*
 884  * HeapTupleSatisfiesMVCC
 885  *              True iff heap tuple is valid for the given MVCC snapshot.
 886  *
 887  *      Here, we consider the effects of:
 888  *              all transactions committed as of the time of the given snapshot
 889  *              previous commands of this transaction
 890  *
 891  *      Does _not_ include:
 892  *              transactions shown as in-progress by the snapshot
 893  *              transactions started after the snapshot was taken
 894  *              changes made by the current command
 895  *
 896  * This is the same as HeapTupleSatisfiesNow, except that transactions that
 897  * were in progress or as yet unstarted when the snapshot was taken will
 898  * be treated as uncommitted, even if they have committed by now.
 899  *
 900  * (Notice, however, that the tuple status hint bits will be updated on the
 901  * basis of the true state of the transaction, even if we then pretend we
 902  * can't see it.)
 903  */
 904 bool
 905 HeapTupleSatisfiesMVCC(HeapTupleHeader tuple, Snapshot snapshot,
 906                                            Buffer buffer)
 907 {
 908         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 909         {
 910                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
 911                         return false;
 912
 913                 /* Used by pre-9.0 binary upgrades */
 914                 if (tuple->t_infomask & HEAP_MOVED_OFF)
 915                 {
 916                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 917
 918                         if (TransactionIdIsCurrentTransactionId(xvac))
 919                                 return false;
 920                         if (!TransactionIdIsInProgress(xvac))
 921                         {
 922                                 if (TransactionIdDidCommit(xvac))
 923                                 {
 924                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 925                                                                 InvalidTransactionId);
 926                                         return false;
 927                                 }
 928                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 929                                                         InvalidTransactionId);
 930                         }
 931                 }
 932                 /* Used by pre-9.0 binary upgrades */
 933                 else if (tuple->t_infomask & HEAP_MOVED_IN)
 934                 {
 935                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 936
 937                         if (!TransactionIdIsCurrentTransactionId(xvac))
 938                         {
 939                                 if (TransactionIdIsInProgress(xvac))
 940                                         return false;
 941                                 if (TransactionIdDidCommit(xvac))
 942                                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 943                                                                 InvalidTransactionId);
 944                                 else
 945                                 {
 946                                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 947                                                                 InvalidTransactionId);
 948                                         return false;
 949                                 }
 950                         }
 951                 }
 952                 else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
 953                 {
 954                         if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
 955                                 return false;   /* inserted after scan started */
 956
 957                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
 958                                 return true;
 959
 960                         if (tuple->t_infomask & HEAP_IS_LOCKED)         /* not deleter */
 961                                 return true;
 962
 963                         Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 964
 965                         if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
 966                         {
 967                                 /* deleting subtransaction must have aborted */
 968                                 SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 969                                                         InvalidTransactionId);
 970                                 return true;
 971                         }
 972
 973                         if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
 974                                 return true;    /* deleted after scan started */
 975                         else
 976                                 return false;   /* deleted before scan started */
 977                 }
 978                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
 979                         return false;
 980                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
 981                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 982                                                 HeapTupleHeaderGetXmin(tuple));
 983                 else
 984                 {
 985                         /* it must have aborted or crashed */
 986                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
 987                                                 InvalidTransactionId);
 988                         return false;
 989                 }
 990         }
 991
 992         /*
 993          * By here, the inserting transaction has committed - have to check
 994          * when...
 995          */
 996         if (XidInMVCCSnapshot(HeapTupleHeaderGetXmin(tuple), snapshot))
 997                 return false;                   /* treat as still in progress */
 998
 999         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid or aborted */
1000                 return true;
1001
1002         if (tuple->t_infomask & HEAP_IS_LOCKED)
1003                 return true;
1004
1005         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
1006         {
1007                 /* MultiXacts are currently only allowed to lock tuples */
1008                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
1009                 return true;
1010         }
1011
1012         if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
1013         {
1014                 if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
1015                 {
1016                         if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
1017                                 return true;    /* deleted after scan started */
1018                         else
1019                                 return false;   /* deleted before scan started */
1020                 }
1021
1022                 if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
1023                         return true;
1024
1025                 if (!TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
1026                 {
1027                         /* it must have aborted or crashed */
1028                         SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
1029                                                 InvalidTransactionId);
1030                         return true;
1031                 }
1032
1033                 /* xmax transaction committed */
1034                 SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
1035                                         HeapTupleHeaderGetXmax(tuple));
1036         }
1037
1038         /*
1039          * OK, the deleting transaction committed too ... but when?
1040          */
1041         if (XidInMVCCSnapshot(HeapTupleHeaderGetXmax(tuple), snapshot))
1042                 return true;                    /* treat as still in progress */
1043
1044         return false;
1045 }
1046
1047
1048 /*
1049  * HeapTupleSatisfiesVacuum
1050  *
1051  *      Determine the status of tuples for VACUUM purposes.  Here, what
1052  *      we mainly want to know is if a tuple is potentially visible to *any*
1053  *      running transaction.  If so, it can't be removed yet by VACUUM.
1054  *
1055  * OldestXmin is a cutoff XID (obtained from GetOldestXmin()).  Tuples
1056  * deleted by XIDs >= OldestXmin are deemed "recently dead"; they might
1057  * still be visible to some open transaction, so we can't remove them,
1058  * even if we see that the deleting transaction has committed.
1059  */
1060 HTSV_Result
1061 HeapTupleSatisfiesVacuum(HeapTupleHeader tuple, TransactionId OldestXmin,
1062                                                  Buffer buffer)
1063 {
1064         /*
1065          * Has inserting transaction committed?
1066          *
1067          * If the inserting transaction aborted, then the tuple was never visible
1068          * to any other transaction, so we can delete it immediately.
1069          */
1070         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
1071         {
1072                 if (tuple->t_infomask & HEAP_XMIN_INVALID)
1073                         return HEAPTUPLE_DEAD;
1074                 /* Used by pre-9.0 binary upgrades */
1075                 else if (tuple->t_infomask & HEAP_MOVED_OFF)
1076                 {
1077                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
1078
1079                         if (TransactionIdIsCurrentTransactionId(xvac))
1080                                 return HEAPTUPLE_DELETE_IN_PROGRESS;
1081                         if (TransactionIdIsInProgress(xvac))
1082                                 return HEAPTUPLE_DELETE_IN_PROGRESS;
1083                         if (TransactionIdDidCommit(xvac))
1084                         {
1085                                 SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
1086                                                         InvalidTransactionId);
1087                                 return HEAPTUPLE_DEAD;
1088                         }
1089                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
1090                                                 InvalidTransactionId);
1091                 }
1092                 /* Used by pre-9.0 binary upgrades */
1093                 else if (tuple->t_infomask & HEAP_MOVED_IN)
1094                 {
1095                         TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
1096
1097                         if (TransactionIdIsCurrentTransactionId(xvac))
1098                                 return HEAPTUPLE_INSERT_IN_PROGRESS;
1099                         if (TransactionIdIsInProgress(xvac))
1100                                 return HEAPTUPLE_INSERT_IN_PROGRESS;
1101                         if (TransactionIdDidCommit(xvac))
1102                                 SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
1103                                                         InvalidTransactionId);
1104                         else
1105                         {
1106                                 SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
1107                                                         InvalidTransactionId);
1108                                 return HEAPTUPLE_DEAD;
1109                         }
1110                 }
1111                 else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
1112                 {
1113                         if (tuple->t_infomask & HEAP_XMAX_INVALID)      /* xid invalid */
1114                                 return HEAPTUPLE_INSERT_IN_PROGRESS;
1115                         if (tuple->t_infomask & HEAP_IS_LOCKED)
1116                                 return HEAPTUPLE_INSERT_IN_PROGRESS;
1117                         /* inserted and then deleted by same xact */
1118                         return HEAPTUPLE_DELETE_IN_PROGRESS;
1119                 }
1120                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
1121                         SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
1122                                                 HeapTupleHeaderGetXmin(tuple));
1123                 else
1124                 {
1125                         /*
1126                          * Not in Progress, Not Committed, so either Aborted or crashed
1127                          */
1128                         SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
1129                                                 InvalidTransactionId);
1130                         return HEAPTUPLE_DEAD;
1131                 }
1132
1133                 /*
1134                  * At this point the xmin is known committed, but we might not have
1135                  * been able to set the hint bit yet; so we can no longer Assert that
1136                  * it's set.
1137                  */
1138         }
1139
1140         /*
1141          * Okay, the inserter committed, so it was good at some point.  Now what
1142          * about the deleting transaction?
1143          */
1144         if (tuple->t_infomask & HEAP_XMAX_INVALID)
1145                 return HEAPTUPLE_LIVE;
1146
1147         if (tuple->t_infomask & HEAP_IS_LOCKED)
1148         {
1149                 /*
1150                  * "Deleting" xact really only locked it, so the tuple is live in any
1151                  * case.  However, we should make sure that either XMAX_COMMITTED or
1152                  * XMAX_INVALID gets set once the xact is gone, to reduce the costs of
1153                  * examining the tuple for future xacts.  Also, marking dead
1154                  * MultiXacts as invalid here provides defense against MultiXactId
1155                  * wraparound (see also comments in heap_freeze_tuple()).
1156                  */
1157                 if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
1158                 {
1159                         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
1160                         {
1161                                 if (MultiXactIdIsRunning(HeapTupleHeaderGetXmax(tuple)))
1162                                         return HEAPTUPLE_LIVE;
1163                         }
1164                         else
1165                         {
1166                                 if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
1167                                         return HEAPTUPLE_LIVE;
1168                         }
1169
1170                         /*
1171                          * We don't really care whether xmax did commit, abort or crash.
1172                          * We know that xmax did lock the tuple, but it did not and will
1173                          * never actually update it.
1174                          */
1175                         SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
1176                                                 InvalidTransactionId);
1177                 }
1178                 return HEAPTUPLE_LIVE;
1179         }
1180
1181         if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
1182         {
1183                 /* MultiXacts are currently only allowed to lock tuples */
1184                 Assert(tuple->t_infomask & HEAP_IS_LOCKED);
1185                 return HEAPTUPLE_LIVE;
1186         }
1187
1188         if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
1189         {
1190                 if (TransactionIdIsInProgress(HeapTupleHeaderGetXmax(tuple)))
1191                         return HEAPTUPLE_DELETE_IN_PROGRESS;
1192                 else if (TransactionIdDidCommit(HeapTupleHeaderGetXmax(tuple)))
1193                         SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
1194                                                 HeapTupleHeaderGetXmax(tuple));
1195                 else
1196                 {
1197                         /*
1198                          * Not in Progress, Not Committed, so either Aborted or crashed
1199                          */
1200                         SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
1201                                                 InvalidTransactionId);
1202                         return HEAPTUPLE_LIVE;
1203                 }
1204
1205                 /*
1206                  * At this point the xmax is known committed, but we might not have
1207                  * been able to set the hint bit yet; so we can no longer Assert that
1208                  * it's set.
1209                  */
1210         }
1211
1212         /*
1213          * Deleter committed, but perhaps it was recent enough that some open
1214          * transactions could still see the tuple.
1215          */
1216         if (!TransactionIdPrecedes(HeapTupleHeaderGetXmax(tuple), OldestXmin))
1217                 return HEAPTUPLE_RECENTLY_DEAD;
1218
1219         /* Otherwise, it's dead and removable */
1220         return HEAPTUPLE_DEAD;
1221 }
1222
1223 /*
1224  * HeapTupleIsSurelyDead
1225  *
1226  *      Determine whether a tuple is surely dead.  We sometimes use this
1227  *      in lieu of HeapTupleSatisifesVacuum when the tuple has just been
1228  *      tested by HeapTupleSatisfiesMVCC and, therefore, any hint bits that
1229  *      can be set should already be set.  We assume that if no hint bits
1230  *      either for xmin or xmax, the transaction is still running.      This is
1231  *      therefore faster than HeapTupleSatisfiesVacuum, because we don't
1232  *      consult CLOG (and also because we don't need to give an exact answer,
1233  *      just whether or not the tuple is surely dead).
1234  */
1235 bool
1236 HeapTupleIsSurelyDead(HeapTupleHeader tuple, TransactionId OldestXmin)
1237 {
1238         /*
1239          * If the inserting transaction is marked invalid, then it aborted, and
1240          * the tuple is definitely dead.  If it's marked neither committed nor
1241          * invalid, then we assume it's still alive (since the presumption is that
1242          * all relevant hint bits were just set moments ago).
1243          */
1244         if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
1245                 return (tuple->t_infomask & HEAP_XMIN_INVALID) != 0 ? true : false;
1246
1247         /*
1248          * If the inserting transaction committed, but any deleting transaction
1249          * aborted, the tuple is still alive.  Likewise, if XMAX is a lock rather
1250          * than a delete, the tuple is still alive.
1251          */
1252         if (tuple->t_infomask &
1253                 (HEAP_XMAX_INVALID | HEAP_IS_LOCKED | HEAP_XMAX_IS_MULTI))
1254                 return false;
1255
1256         /* If deleter isn't known to have committed, assume it's still running. */
1257         if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
1258                 return false;
1259
1260         /* Deleter committed, so tuple is dead if the XID is old enough. */
1261         return TransactionIdPrecedes(HeapTupleHeaderGetXmax(tuple), OldestXmin);
1262 }
1263
1264 /*
1265  * XidInMVCCSnapshot
1266  *              Is the given XID still-in-progress according to the snapshot?
1267  *
1268  * Note: GetSnapshotData never stores either top xid or subxids of our own
1269  * backend into a snapshot, so these xids will not be reported as "running"
1270  * by this function.  This is OK for current uses, because we actually only
1271  * apply this for known-committed XIDs.
1272  */
1273 static bool
1274 XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
1275 {
1276         uint32          i;
1277
1278         /*
1279          * Make a quick range check to eliminate most XIDs without looking at the
1280          * xip arrays.  Note that this is OK even if we convert a subxact XID to
1281          * its parent below, because a subxact with XID < xmin has surely also got
1282          * a parent with XID < xmin, while one with XID >= xmax must belong to a
1283          * parent that was not yet committed at the time of this snapshot.
1284          */
1285
1286         /* Any xid < xmin is not in-progress */
1287         if (TransactionIdPrecedes(xid, snapshot->xmin))
1288                 return false;
1289         /* Any xid >= xmax is in-progress */
1290         if (TransactionIdFollowsOrEquals(xid, snapshot->xmax))
1291                 return true;
1292
1293         /*
1294          * Snapshot information is stored slightly differently in snapshots taken
1295          * during recovery.
1296          */
1297         if (!snapshot->takenDuringRecovery)
1298         {
1299                 /*
1300                  * If the snapshot contains full subxact data, the fastest way to
1301                  * check things is just to compare the given XID against both subxact
1302                  * XIDs and top-level XIDs.  If the snapshot overflowed, we have to
1303                  * use pg_subtrans to convert a subxact XID to its parent XID, but
1304                  * then we need only look at top-level XIDs not subxacts.
1305                  */
1306                 if (!snapshot->suboverflowed)
1307                 {
1308                         /* full data, so search subxip */
1309                         int32           j;
1310
1311                         for (j = 0; j < snapshot->subxcnt; j++)
1312                         {
1313                                 if (TransactionIdEquals(xid, snapshot->subxip[j]))
1314                                         return true;
1315                         }
1316
1317                         /* not there, fall through to search xip[] */
1318                 }
1319                 else
1320                 {
1321                         /* overflowed, so convert xid to top-level */
1322                         xid = SubTransGetTopmostTransaction(xid);
1323
1324                         /*
1325                          * If xid was indeed a subxact, we might now have an xid < xmin,
1326                          * so recheck to avoid an array scan.  No point in rechecking
1327                          * xmax.
1328                          */
1329                         if (TransactionIdPrecedes(xid, snapshot->xmin))
1330                                 return false;
1331                 }
1332
1333                 for (i = 0; i < snapshot->xcnt; i++)
1334                 {
1335                         if (TransactionIdEquals(xid, snapshot->xip[i]))
1336                                 return true;
1337                 }
1338         }
1339         else
1340         {
1341                 int32           j;
1342
1343                 /*
1344                  * In recovery we store all xids in the subxact array because it is by
1345                  * far the bigger array, and we mostly don't know which xids are
1346                  * top-level and which are subxacts. The xip array is empty.
1347                  *
1348                  * We start by searching subtrans, if we overflowed.
1349                  */
1350                 if (snapshot->suboverflowed)
1351                 {
1352                         /* overflowed, so convert xid to top-level */
1353                         xid = SubTransGetTopmostTransaction(xid);
1354
1355                         /*
1356                          * If xid was indeed a subxact, we might now have an xid < xmin,
1357                          * so recheck to avoid an array scan.  No point in rechecking
1358                          * xmax.
1359                          */
1360                         if (TransactionIdPrecedes(xid, snapshot->xmin))
1361                                 return false;
1362                 }
1363
1364                 /*
1365                  * We now have either a top-level xid higher than xmin or an
1366                  * indeterminate xid. We don't know whether it's top level or subxact
1367                  * but it doesn't matter. If it's present, the xid is visible.
1368                  */
1369                 for (j = 0; j < snapshot->subxcnt; j++)
1370                 {
1371                         if (TransactionIdEquals(xid, snapshot->subxip[j]))
1372                                 return true;
1373                 }
1374         }
1375
1376         return false;
1377 }