Implement sharable row-level locks, and use them for foreign key references

to eliminate unnecessary deadlocks.  This commit adds SELECT ... FOR SHARE
paralleling SELECT ... FOR UPDATE.  The implementation uses a new SLRU
data structure (managed much like pg_subtrans) to represent multiple-
transaction-ID sets.  When more than one transaction is holding a shared
lock on a particular row, we create a MultiXactId representing that set
of transactions and store its ID in the row's XMAX.  This scheme allows
an effectively unlimited number of row locks, just as we did before,
while not costing any extra overhead except when a shared lock actually
has to be shared.   Still TODO: use the regular lock manager to control
the grant order when multiple backends are waiting for a row lock.

Alvaro Herrera and Tom Lane.

13 files changed, 102 insertions, 29 deletions

diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 8b18cc4224..9138186ba6 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/heapam.h,v 1.99 2005/04/14 20:03:27 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/access/heapam.h,v 1.100 2005/04/28 21:47:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -123,6 +123,12 @@ extern Datum fastgetattr(HeapTuple tup, int attnum, TupleDesc tupleDesc,
 
 /* heapam.c */
 
+typedef enum
+{
+	LockTupleShared,
+	LockTupleExclusive
+} LockTupleMode;
+
 extern Relation relation_open(Oid relationId, LOCKMODE lockmode);
 extern Relation conditional_relation_open(Oid relationId, LOCKMODE lockmode, bool nowait);
 extern Relation relation_openrv(const RangeVar *relation, LOCKMODE lockmode);
@@ -155,8 +161,8 @@ extern HTSU_Result heap_delete(Relation relation, ItemPointer tid, ItemPointer c
 			CommandId cid, Snapshot crosscheck, bool wait);
 extern HTSU_Result heap_update(Relation relation, ItemPointer otid, HeapTuple tup,
 		ItemPointer ctid, CommandId cid, Snapshot crosscheck, bool wait);
-extern HTSU_Result heap_mark4update(Relation relation, HeapTuple tup,
-				 Buffer *userbuf, CommandId cid);
+extern HTSU_Result heap_lock_tuple(Relation relation, HeapTuple tup,
+				 Buffer *userbuf, CommandId cid, LockTupleMode mode);
 
 extern Oid	simple_heap_insert(Relation relation, HeapTuple tup);
 extern void simple_heap_delete(Relation relation, ItemPointer tid);
diff --git a/src/include/access/htup.h b/src/include/access/htup.h
index e57ce8a3cb..adeb05fd56 100644
--- a/src/include/access/htup.h
+++ b/src/include/access/htup.h
@@ -1,4 +1,4 @@
- /*-------------------------------------------------------------------------
+/*-------------------------------------------------------------------------
  *
  * htup.h
  *	  POSTGRES heap tuple definitions.
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/htup.h,v 1.73 2005/03/28 01:50:34 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/access/htup.h,v 1.74 2005/04/28 21:47:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -93,11 +93,11 @@ typedef struct HeapTupleFields
 {
 	TransactionId t_xmin;		/* inserting xact ID */
 	CommandId	t_cmin;			/* inserting command ID */
-	TransactionId t_xmax;		/* deleting xact ID */
+	TransactionId t_xmax;		/* deleting or locking xact ID */
 
 	union
 	{
-		CommandId	t_cmax;		/* deleting command ID */
+		CommandId	t_cmax;		/* deleting or locking command ID */
 		TransactionId t_xvac;	/* VACUUM FULL xact ID */
 	}			t_field4;
 } HeapTupleFields;
@@ -152,12 +152,16 @@ typedef HeapTupleHeaderData *HeapTupleHeader;
 										 * attribute(s) */
 #define HEAP_HASEXTENDED		0x000C	/* the two above combined */
 #define HEAP_HASOID				0x0010	/* has an object-id field */
-/* 0x0020, 0x0040 and 0x0080 are unused */
+/* 0x0020 is presently unused */
+#define HEAP_XMAX_EXCL_LOCK		0x0040  /* xmax is exclusive locker */
+#define HEAP_XMAX_SHARED_LOCK	0x0080  /* xmax is shared locker */
+/* if either LOCK bit is set, xmax hasn't deleted the tuple, only locked it */
+#define HEAP_IS_LOCKED	(HEAP_XMAX_EXCL_LOCK | HEAP_XMAX_SHARED_LOCK)
 #define HEAP_XMIN_COMMITTED		0x0100	/* t_xmin committed */
 #define HEAP_XMIN_INVALID		0x0200	/* t_xmin invalid/aborted */
 #define HEAP_XMAX_COMMITTED		0x0400	/* t_xmax committed */
 #define HEAP_XMAX_INVALID		0x0800	/* t_xmax invalid/aborted */
-#define HEAP_MARKED_FOR_UPDATE	0x1000	/* marked for UPDATE */
+#define HEAP_XMAX_IS_MULTI		0x1000	/* t_xmax is a MultiXactId */
 #define HEAP_UPDATED			0x2000	/* this is UPDATEd version of row */
 #define HEAP_MOVED_OFF			0x4000	/* moved to another place by
 										 * VACUUM FULL */
@@ -406,7 +410,8 @@ typedef HeapTupleData *HeapTuple;
 #define XLOG_HEAP_MOVE		0x30
 #define XLOG_HEAP_CLEAN		0x40
 #define XLOG_HEAP_NEWPAGE	0x50
-/* opcodes 0x60, 0x70 still free */
+#define XLOG_HEAP_LOCK		0x60
+/* opcode 0x70 still free */
 #define XLOG_HEAP_OPMASK	0x70
 /*
  * When we insert 1st item on new page in INSERT/UPDATE
@@ -496,4 +501,13 @@ typedef struct xl_heap_newpage
 
 #define SizeOfHeapNewpage	(offsetof(xl_heap_newpage, blkno) + sizeof(BlockNumber))
 
+/* This is what we need to know about lock */
+typedef struct xl_heap_lock
+{
+	xl_heaptid	target;			/* locked tuple id */
+	bool		shared_lock;	/* shared or exclusive row lock? */
+} xl_heap_lock;
+
+#define SizeOfHeapLock	(offsetof(xl_heap_lock, shared_lock) + sizeof(bool))
+
 #endif   /* HTUP_H */
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
new file mode 100644
index 0000000000..1eafddbe83
--- /dev/null
+++ b/src/include/access/multixact.h
@@ -0,0 +1,37 @@
+/*
+ * multixact.h
+ *
+ * PostgreSQL multi-transaction-log manager
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/access/multixact.h,v 1.1 2005/04/28 21:47:17 tgl Exp $
+ */
+#ifndef MULTIXACT_H
+#define MULTIXACT_H
+
+#define InvalidMultiXactId	((MultiXactId) 0)
+#define FirstMultiXactId	((MultiXactId) 1)
+
+#define MultiXactIdIsValid(multi) ((multi) != InvalidMultiXactId)
+
+extern void MultiXactIdWait(MultiXactId multi);
+extern MultiXactId MultiXactIdExpand(MultiXactId multi, bool isMulti,
+									 TransactionId xid);
+extern bool MultiXactIdIsRunning(MultiXactId multi);
+extern void MultiXactIdSetOldestMember(void);
+
+extern void AtEOXact_MultiXact(void);
+
+extern int	MultiXactShmemSize(void);
+extern void MultiXactShmemInit(void);
+extern void BootStrapMultiXact(void);
+extern void StartupMultiXact(void);
+extern void ShutdownMultiXact(void);
+extern MultiXactId MultiXactGetCheckptMulti(bool is_shutdown);
+extern void CheckPointMultiXact(void);
+extern void MultiXactSetNextMXact(MultiXactId nextMulti);
+extern void MultiXactAdvanceNextMXact(MultiXactId minMulti);
+
+#endif   /* MULTIXACT_H */
diff --git a/src/include/access/xlog.h b/src/include/access/xlog.h
index 41b8bde011..27a076c7e0 100644
--- a/src/include/access/xlog.h
+++ b/src/include/access/xlog.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/xlog.h,v 1.59 2004/12/31 22:03:21 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/access/xlog.h,v 1.60 2005/04/28 21:47:17 tgl Exp $
  */
 #ifndef XLOG_H
 #define XLOG_H
@@ -133,6 +133,7 @@ extern void ShutdownXLOG(int code, Datum arg);
 extern void InitXLOGAccess(void);
 extern void CreateCheckPoint(bool shutdown, bool force);
 extern void XLogPutNextOid(Oid nextOid);
+extern void XLogPutNextMultiXactId(MultiXactId multi);
 extern XLogRecPtr GetRedoRecPtr(void);
 
 #endif   /* XLOG_H */
diff --git a/src/include/c.h b/src/include/c.h
index ebed0ab945..31d843fde7 100644
--- a/src/include/c.h
+++ b/src/include/c.h
@@ -12,7 +12,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/c.h,v 1.181 2005/03/29 00:17:16 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/c.h,v 1.182 2005/04/28 21:47:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -365,7 +365,8 @@ typedef float float4;
 typedef double float8;
 
 /*
- * Oid, RegProcedure, TransactionId, SubTransactionId, CommandId, AclId
+ * Oid, RegProcedure, TransactionId, SubTransactionId, MultiXactId,
+ * CommandId, AclId
  */
 
 /* typedef Oid is in postgres_ext.h */
@@ -384,6 +385,9 @@ typedef uint32 SubTransactionId;
 #define InvalidSubTransactionId		((SubTransactionId) 0)
 #define TopSubTransactionId			((SubTransactionId) 1)
 
+/* MultiXactId must be equivalent to TransactionId, to fit in t_xmax */
+typedef TransactionId MultiXactId;
+
 typedef uint32 CommandId;
 
 #define FirstCommandId	((CommandId) 0)
diff --git a/src/include/catalog/pg_control.h b/src/include/catalog/pg_control.h
index 83573334fc..e60a879424 100644
--- a/src/include/catalog/pg_control.h
+++ b/src/include/catalog/pg_control.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_control.h,v 1.20 2005/03/29 03:01:32 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_control.h,v 1.21 2005/04/28 21:47:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -22,7 +22,7 @@
 
 
 /* Version identifier for this pg_control format */
-#define PG_CONTROL_VERSION	74
+#define PG_CONTROL_VERSION	81
 
 /*
  * Body of CheckPoint XLOG records.  This is declared here because we keep
@@ -39,12 +39,14 @@ typedef struct CheckPoint
 	TimeLineID	ThisTimeLineID; /* current TLI */
 	TransactionId nextXid;		/* next free XID */
 	Oid			nextOid;		/* next free OID */
+	MultiXactId	nextMulti;		/* next free MultiXactId */
 	time_t		time;			/* time stamp of checkpoint */
 } CheckPoint;
 
 /* XLOG info values for XLOG rmgr */
 #define XLOG_CHECKPOINT_SHUTDOWN		0x00
 #define XLOG_CHECKPOINT_ONLINE			0x10
+#define XLOG_NEXTMULTI					0x20
 #define XLOG_NEXTOID					0x30
 
 
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index ba665025df..1280aff0ca 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.129 2005/04/25 01:30:14 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.130 2005/04/28 21:47:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -318,6 +318,7 @@ typedef struct EState
 	uint32		es_processed;	/* # of tuples processed */
 	Oid			es_lastoid;		/* last oid processed (by INSERT) */
 	List	   *es_rowMark;		/* not good place, but there is no other */
+	bool		es_forUpdate;	/* was it FOR UPDATE or FOR SHARE */
 
 	bool		es_instrument;	/* true requests runtime instrumentation */
 	bool		es_select_into; /* true if doing SELECT INTO */
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index e8a44c34b2..97d5df935a 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.277 2005/04/07 01:51:40 neilc Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.278 2005/04/28 21:47:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -50,7 +50,7 @@ typedef uint32 AclMode;			/* a bitmask of privilege bits */
 #define N_ACL_RIGHTS	11		/* 1 plus the last 1<<x */
 #define ACL_ALL_RIGHTS	(-1)	/* all-privileges marker in GRANT list */
 #define ACL_NO_RIGHTS	0
-/* Currently, SELECT ... FOR UPDATE requires UPDATE privileges */
+/* Currently, SELECT ... FOR UPDATE/FOR SHARE requires UPDATE privileges */
 #define ACL_SELECT_FOR_UPDATE	ACL_UPDATE
 
 
@@ -91,7 +91,10 @@ typedef struct Query
 								 * clauses) */
 
 	List	   *rowMarks;		/* integer list of RT indexes of relations
-								 * that are selected FOR UPDATE */
+								 * that are selected FOR UPDATE/SHARE */
+
+	bool		forUpdate;		/* true if rowMarks are FOR UPDATE,
+								 * false if they are FOR SHARE */
 
 	List	   *targetList;		/* target list (of TargetEntry) */
 
@@ -688,7 +691,8 @@ typedef struct SelectStmt
 	List	   *sortClause;		/* sort clause (a list of SortBy's) */
 	Node	   *limitOffset;	/* # of result tuples to skip */
 	Node	   *limitCount;		/* # of result tuples to return */
-	List	   *forUpdate;		/* FOR UPDATE clause */
+	List	   *lockedRels;		/* FOR UPDATE or FOR SHARE relations */
+	bool		forUpdate;		/* true = FOR UPDATE, false = FOR SHARE */
 
 	/*
 	 * These fields are used only in upper-level SelectStmts.
diff --git a/src/include/parser/analyze.h b/src/include/parser/analyze.h
index bec10e8bb0..73cbb2fc79 100644
--- a/src/include/parser/analyze.h
+++ b/src/include/parser/analyze.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/parser/analyze.h,v 1.29 2004/12/31 22:03:38 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/parser/analyze.h,v 1.30 2005/04/28 21:47:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,6 +21,6 @@ extern List *parse_analyze_varparams(Node *parseTree, Oid **paramTypes,
 						int *numParams);
 extern List *parse_sub_analyze(Node *parseTree, ParseState *parentParseState);
 extern List *analyzeCreateSchemaStmt(CreateSchemaStmt *stmt);
-extern void CheckSelectForUpdate(Query *qry);
+extern void CheckSelectLocking(Query *qry, bool forUpdate);
 
 #endif   /* ANALYZE_H */
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index 3999918f24..bfcf00fd47 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.42 2004/12/31 22:03:38 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.43 2005/04/28 21:47:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,7 +53,7 @@ typedef struct ParseState
 	Oid		   *p_paramtypes;	/* OIDs of types for $n parameter symbols */
 	int			p_numparams;	/* allocated size of p_paramtypes[] */
 	int			p_next_resno;	/* next targetlist resno to assign */
-	List	   *p_forUpdate;	/* FOR UPDATE clause, if any (see gram.y) */
+	List	   *p_lockedRels;	/* FOR UPDATE/SHARE, if any (see gram.y) */
 	Node	   *p_value_substitute;		/* what to replace VALUE with, if
 										 * any */
 	bool		p_variableparams;
diff --git a/src/include/storage/bufpage.h b/src/include/storage/bufpage.h
index 8b195132cb..c02bb4dc87 100644
--- a/src/include/storage/bufpage.h
+++ b/src/include/storage/bufpage.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.64 2005/03/22 06:17:03 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.65 2005/04/28 21:47:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -135,8 +135,9 @@ typedef PageHeaderData *PageHeader;
  * Page layout version number 0 is for pre-7.3 Postgres releases.
  * Releases 7.3 and 7.4 use 1, denoting a new HeapTupleHeader layout.
  * Release 8.0 changed the HeapTupleHeader layout again.
+ * Release 8.1 redefined HeapTupleHeader infomask bits.
  */
-#define PG_PAGE_LAYOUT_VERSION		2
+#define PG_PAGE_LAYOUT_VERSION		3
 
 
 /* ----------------------------------------------------------------
diff --git a/src/include/storage/lmgr.h b/src/include/storage/lmgr.h
index 6aec7bf19c..8d63294f5c 100644
--- a/src/include/storage/lmgr.h
+++ b/src/include/storage/lmgr.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/storage/lmgr.h,v 1.45 2004/12/31 22:03:42 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/storage/lmgr.h,v 1.46 2005/04/28 21:47:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,7 +23,7 @@
 #define NoLock					0
 
 #define AccessShareLock			1		/* SELECT */
-#define RowShareLock			2		/* SELECT FOR UPDATE */
+#define RowShareLock			2		/* SELECT FOR UPDATE/FOR SHARE */
 #define RowExclusiveLock		3		/* INSERT, UPDATE, DELETE */
 #define ShareUpdateExclusiveLock 4		/* VACUUM (non-FULL) */
 #define ShareLock				5		/* CREATE INDEX */
diff --git a/src/include/storage/lwlock.h b/src/include/storage/lwlock.h
index 50c029cc8b..18215f4838 100644
--- a/src/include/storage/lwlock.h
+++ b/src/include/storage/lwlock.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/storage/lwlock.h,v 1.17 2005/03/04 20:21:07 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/storage/lwlock.h,v 1.18 2005/04/28 21:47:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -40,6 +40,9 @@ typedef enum LWLockId
 	CheckpointStartLock,
 	CLogControlLock,
 	SubtransControlLock,
+	MultiXactGenLock,
+	MultiXactOffsetControlLock,
+	MultiXactMemberControlLock,
 	RelCacheInitLock,
 	BgWriterCommLock,