Improve heavyweight locks instead of building new lock managers?

Hi,

Some of the discussions about improving the locking code, in particular
the group locking / deadlock detector discussion with Robert, again made
me look at lock.c. While looking at how much work it'd be to a) remove
the PROCLOCK hashtable b) move more of the group locking logic into
lock.c, rather than smarts in deadlock.c, I got sidetracked by all the
verbose and hard to read SHM_QUEUE code.

Here's a *draft* patch series for removing all use of SHM_QUEUE, and
subsequently removing SHM_QUEUE. There's a fair bit of polish needed,
but I do think it makes the code considerably easier to read
(particularly for predicate.c). The diffstat is nice too:

src/include/lib/ilist.h | 132 +++++++++++++++++----
src/include/replication/walsender_private.h | 3 +-
src/include/storage/lock.h | 10 +-
src/include/storage/predicate_internals.h | 49 +++-----
src/include/storage/proc.h | 18 +--
src/include/storage/shmem.h | 22 ----
src/backend/access/transam/twophase.c | 4 +-
src/backend/lib/ilist.c | 8 +-
src/backend/replication/syncrep.c | 89 ++++++--------
src/backend/replication/walsender.c | 2 +-
src/backend/storage/ipc/Makefile | 1 -
src/backend/storage/ipc/shmqueue.c | 190 ------------------------------
src/backend/storage/lmgr/deadlock.c | 76 +++++-------
src/backend/storage/lmgr/lock.c | 129 ++++++++------------
src/backend/storage/lmgr/predicate.c | 692 +++++++++++++++++++++++++++++++++++------------------------------------------------------------------------
src/backend/storage/lmgr/proc.c | 197 +++++++++++++------------------
16 files changed, 569 insertions(+), 1053 deletions(-)

I don't want to invest a lot of time into this if there's not some
agreement that this is a good direction to go into. So I'd appreciate a
few cursory looks before spending more time.

Overview:
0001: Add additional prev/next & detached node functions to ilist.
I think the additional prev/next accessors are nice. I am less
convinced by the 'detached' stuff, but it's used by some SHM_QUEUE
users. I don't want to make the plain dlist_delete reset the node's
prev/next pointers, it's not needed in the vast majority of cases...

0002: Use dlists instead of SHM_QUEUE for heavyweight locks.
I mostly removed the odd reliance on PGPROC.links needing to be the
first struct member - seems odd.

I think we should rename PROC_QUEUE.links, elsewhere that's used for
list membership nodes, so it's imo confusing/odd.

0003: Use dlist for syncrep queue.
This seems fairly simple to me.

0004: Use dlists for predicate locking.
Unfortunately pretty large. I think it's a huge improvement, but it's
also subtle code. Wonder if there's something better to do here wrt
OnConflict_CheckForSerializationFailure?

0005: Remove now unused SHMQueue*.
0006: Remove PROC_QUEUE.size.
I'm not sure whether this is a a good idea. I was looking primarily at
that because I thought it'd allow us to remove PROC_QUEUE as a whole
if we wanted to. But as PROC_QUEUE.size doesn't really seem to buy us
much, we should perhaps just do something roughly like in the patch?

Greetings,

Andres Freund

Hi Andres,

On Thu, Feb 20, 2020 at 1:14 PM Andres Freund <andres@anarazel.de> wrote:

Here's a *draft* patch series for removing all use of SHM_QUEUE, and
subsequently removing SHM_QUEUE. There's a fair bit of polish needed,
but I do think it makes the code considerably easier to read
(particularly for predicate.c). The diffstat is nice too:

0005: Remove now unused SHMQueue*.
0006: Remove PROC_QUEUE.size.

Maybe you're aware, but there still seem to be places using it. In
LOCK_DEBUG build:

lock.c: In function ‘LOCK_PRINT’:
lock.c:320:20: error: ‘PROC_QUEUE’ {aka ‘const struct PROC_QUEUE’} has
no member named ‘size’
lock->waitProcs.size,

lock.c: In function ‘DumpLocks’:
lock.c:3906:2: error: unknown type name ‘SHM_QUEUE’; did you mean ‘SI_QUEUE’?

Fwiw, I for one, am all for removing specialized data structures when
more widely used data structures will do, especially if that
specialization is no longer relevant.

Thanks,
Amit

On Thu, Feb 20, 2020 at 5:14 PM Andres Freund <andres@anarazel.de> wrote:

16 files changed, 569 insertions(+), 1053 deletions(-)

Nice!

Some comments on 0001, 0003, 0004:

Subject: [PATCH v1 1/6] Add additional prev/next & detached node functions to

+extern void dlist_check(const dlist_head *head);
+extern void slist_check(const slist_head *head);

I approve of the incidental constification in this patch.

+/*
+ * Like dlist_delete(), but also sets next/prev to NULL to signal not being in
+ * list.
+ */
+static inline void
+dlist_delete_thoroughly(dlist_node *node)
+{
+       node->prev->next = node->next;
+       node->next->prev = node->prev;
+       node->next = NULL;
+       node->prev = NULL;
+}

Instead of introducing this strange terminology, why not just have the
callers do ...

dlist_delete(node);
dlist_node_init(node);

..., or perhaps supply dlist_delete_and_reinit(node) that does exactly
that? That is, reuse the code and terminology.

+/*
+ * Check if node is detached. A node is only detached if it either has been
+ * initialized with dlist_init_node(), or deleted with
+ * dlist_delete_thoroughly().
+ */
+static inline bool
+dlist_node_is_detached(const dlist_node *node)
+{
+    Assert((node->next == NULL && node->prev == NULL) ||
+           (node->next != NULL && node->prev != NULL));
+
+    return node->next == NULL;
+}

How about dlist_node_is_linked()? I don't like introducing random new
verbs when we already have 'linked' in various places, and these
things are, y'know, linked lists.

Subject: [PATCH v1 3/6] Use dlist for syncrep queue.

LGTM.

Subject: [PATCH v1 4/6] Use dlists for predicate locking.

+ dlist_foreach(iter, &unconstify(SERIALIZABLEXACT *, reader)->outConflicts)

Yuck... I suppose you could do this:

-    dlist_foreach(iter, &unconstify(SERIALIZABLEXACT *, reader)->outConflicts)
+    dlist_foreach_const(iter, &reader->outConflicts)

... given:

+/* Variant for when you have a pointer to const dlist_head. */
+#define dlist_foreach_const(iter, lhead)                    \
+    for (AssertVariableIsOfTypeMacro(iter, dlist_iter),            \
+         AssertVariableIsOfTypeMacro(lhead, const dlist_head *),    \
+         (iter).end = (dlist_node *) &(lhead)->head,            \
+         (iter).cur = (iter).end->next ? (iter).end->next : (iter).end;    \
+         (iter).cur != (iter).end;                    \
+         (iter).cur = (iter).cur->next)
+

... or find a way to make dlist_foreach() handle that itself, which
seems pretty reasonable given its remit to traverse lists without
modifying them, though perhaps that would require a different iterator
type...

Otherwise looks OK to me and passes various tests I threw at it.

Hi,

On 2020-02-21 12:40:06 +1300, Thomas Munro wrote:

On Thu, Feb 20, 2020 at 5:14 PM Andres Freund <andres@anarazel.de> wrote:

16 files changed, 569 insertions(+), 1053 deletions(-)

Nice!

Thanks!

Some comments on 0001, 0003, 0004:

Subject: [PATCH v1 1/6] Add additional prev/next & detached node functions to

+extern void dlist_check(const dlist_head *head);
+extern void slist_check(const slist_head *head);

I approve of the incidental constification in this patch.

It was just necessary fallout :)

+/*
+ * Like dlist_delete(), but also sets next/prev to NULL to signal not being in
+ * list.
+ */
+static inline void
+dlist_delete_thoroughly(dlist_node *node)
+{
+       node->prev->next = node->next;
+       node->next->prev = node->prev;
+       node->next = NULL;
+       node->prev = NULL;
+}

Instead of introducing this strange terminology, why not just have the
callers do ...

dlist_delete(node);
dlist_node_init(node);

There's quite a few callers in predicate.c - I actually did that first.

..., or perhaps supply dlist_delete_and_reinit(node) that does exactly
that? That is, reuse the code and terminology.

Yea, that's might be better, but see paragraph below. I quite dislike
adding any "empty node" state.

+/*
+ * Check if node is detached. A node is only detached if it either has been
+ * initialized with dlist_init_node(), or deleted with
+ * dlist_delete_thoroughly().
+ */
+static inline bool
+dlist_node_is_detached(const dlist_node *node)
+{
+    Assert((node->next == NULL && node->prev == NULL) ||
+           (node->next != NULL && node->prev != NULL));
+
+    return node->next == NULL;
+}

How about dlist_node_is_linked()? I don't like introducing random new
verbs when we already have 'linked' in various places, and these
things are, y'know, linked lists.

Well, but that doesn't signal that you can't just delete and have
dlist_node_is_linked() work. I *want* it to sound "different". We could
of course make delete always do this, but I don't want to add that
overhead unnecessarily.

Subject: [PATCH v1 4/6] Use dlists for predicate locking.

+ dlist_foreach(iter, &unconstify(SERIALIZABLEXACT *, reader)->outConflicts)

Yuck...

It doesn't seem *that* bad to me, at least signals properly what we're
doing, and only does so in one place.

I suppose you could do this:

-    dlist_foreach(iter, &unconstify(SERIALIZABLEXACT *, reader)->outConflicts)
+    dlist_foreach_const(iter, &reader->outConflicts)

We'd need a different iterator type too, I think? Because the iterator
itself can't be constant, but we'd want the elements themselves be
pointers to constants.

const just isn't a very granular thing in C :(.

... given:

+/* Variant for when you have a pointer to const dlist_head. */
+#define dlist_foreach_const(iter, lhead)                    \
+    for (AssertVariableIsOfTypeMacro(iter, dlist_iter),            \
+         AssertVariableIsOfTypeMacro(lhead, const dlist_head *),    \
+         (iter).end = (dlist_node *) &(lhead)->head,            \
+         (iter).cur = (iter).end->next ? (iter).end->next : (iter).end;    \
+         (iter).cur != (iter).end;                    \
+         (iter).cur = (iter).cur->next)
+

... or find a way to make dlist_foreach() handle that itself, which
seems pretty reasonable given its remit to traverse lists without
modifying them, though perhaps that would require a different iterator
type...

I was trying that first, but I don't easily see how we can do
so. Iterating over a non-constant list with dlist_foreach obviously
still allows to to manipulate the list members. Thus dlist_iter.cur
can't be a 'pointer to const'. Whereas that's arguably what'd be needed
for a correct dlist_foreach() of a constant list?

We could just accept const pointers for dlist_foreach(), but then we'd
*always* accept them, and we'd thus unconditionally have iter.cur as
non-const. Would that be better?

Otherwise looks OK to me and passes various tests I threw at it

Thanks!

Greetings,

Andres Freund

On Mon, Feb 10, 2020 at 11:22 PM Andres Freund <andres@anarazel.de> wrote:

To me this seems to go in the direction of having multiple bespoke lock
managers with slightly different feature sets, different debugging /
logging / monitoring support, with separate locking code each. That's
bad for maintainability.

I think it would help a lot if the lock manager were not such a
monolithic thing. For instance, suppose that instead of having the
deadlock detector be part of the lock manager, it's a separate thing
that integrates with the lock manager. Instead of only knowing about
waits for heavyweight locks, it knows about whatever you want to tell
it about. Then, for instance, you could possibly tell it that process
A is waiting for a cleanup lock while process B holds a pin, possibly
detecting a deadlock we can't notice today. There are likely other
cases as well.

E.g. we could:

- Have an extended LockAcquire API where the caller provides a stack
variable for caching information until the LockRelease call, avoiding
separate LockMethodLocalHash lookup for release.

Maybe. Seems like it might make things a little clunky for the caller,
though. If you just kept a stack of locks acquired and checked the
lock being released against the top of the stack, you'd probably catch
a large percentage of cases. Or, the caller could pass a flag
indicating whether they intend to release the lock prior to the end of
the transaction (which could be cross-checked by assertions). Any that
you intend to release early go on a stack.

- Instead of always implementing HASH_REMOVE as a completely fresh
lookup in dynahash, we should provide an API for removing an object we
*know* is in the hashtable at a specific pointer. We're obviously
already relying on that address to stay constant, so we'd not loose
flexibility. With this separate API we can avoid the bucket lookup,
walking through each element in that bucket, and having to compare the
hash key every time (which is quite expensive for a full LOCKTAG).

That makes a lot of sense, although I wonder if we should go further
and replace dynahash entirely.

- We should try to figure out whether we can avoid needing the separate
lock table for PROCLOCKs. As far as I can tell there's not a single
reason for it to be a hashtable, rather than something like
NUM_LOCK_PARTITIONS lists of free PROCLOCKs.

I agree that the PROCLOCK thing seems ugly and inefficient. I'm not
sure that a bunch of lists is the best answer, though it might be. One
case to consider is when a lock is initially acquired via the
fast-path and then, because of a conflicting lock acquisition,
transferred by *some other process* to the main lock table. If this
occurs, the original locker must be able to find its PROCLOCK. It
doesn't have to be crazy efficient because it shouldn't happen very
often, but it shouldn't suck too much.

- Whenever we do a relation extension, we better already hold a normal
relation lock. We don't actually need to have an entirely distinct
type of lock for extensions, that theoretically could support N
extension locks for each relation. The fact that these are associated
could be utilized in different ways:

- We could define relation extension as a separate lock level only
conflicting with itself (and perhaps treat AELs as including
it). That'd avoid needing separate shared memory states in many
cases.

This might be too problematic, because extension locks don't have
the same desired behaviour around group locking (and a small army of
other issues).

Yeah, I don't think that's likely to work out very nicely.

- We could keep a separate extension lock cached inside the relation
lock. The first time a transaction needs to extend, it does the
normal work, and after that stores the PROCLOCK in the LOCALLOCK (or
something like that). Once extension is done, don't release the lock
entirely, but instead just reduce the lock level to a new
non-conflicting lock level

Alternatively we could implement something very similar outside of
lock.c, e.g. by caching the LOCALLOCK* (possibly identified by an
integer or such) in RelationData. That'd require enough support
from lock.c to be able to make that really cheap.

Not sure I quite see what you mean here.

We could e.g. split the maintenance of the hashtable(s) from protecting
the state of individual locks. The locks protecting the hashtable would
just be held long enough to change a "pin count" of each lock, and then
a per LOCK lwlock would protect each heavyweight lock's state. We'd not
need to lock the partition locks for quite a few cases, because there's
many locks in a loaded system that always have lockers. There'd be cost
to that, needing more atomic ops in some cases, but I think it'd reduce
contention tremendously, and it'd open a lot more optimization
potential. It seems plausible that we could even work, as a followup,
to not needing the partition locks for some lock releases (e.g. when
there are other holders), and we might even be able to avoid it for
acquisitions, by caching the LOCK inside LOCALLOCK, and re-identifying
the identity.

I agree. This seems worth exploring. The idea of caching the probably
location of the lock and re-pinning it to check whether it's the one
you expected seems like it would avoid false sharing in a lot of
practical cases.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Feb 19, 2020 at 11:14 PM Andres Freund <andres@anarazel.de> wrote:

Here's a *draft* patch series for removing all use of SHM_QUEUE, and
subsequently removing SHM_QUEUE.

+1 for that idea.

But color me skeptical of what Thomas described as the "incidental
constification".

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company