Thread: MAX_BACKENDS size (comment accuracy)

Hi,

On 2025-01-25 16:06:29 -0800, Jacob Brazeal wrote:
> > In lwlocks.c, we have the following comment, related to LWLock state:
> >
> >
> > */* Must be greater than MAX_BACKENDS - which is 2^23-1, so we're fine.
> > */#define LW_SHARED_MASK ((uint32) ((1 << 24)-1))*
> >
> > However, MAX_BACKENDS is set to 2^18-1. Here is the comment in
> > postmaster.h:

> > */* * Note: MAX_BACKENDS is limited to 2^18-1 because that's the width
> > reserved * for buffer references in buf_internals.h.  This limitation could
> > be lifted * by using a 64bit state; but it's unlikely to be worthwhile as
> > 2^18-1 * backends exceed currently realistic configurations. Even if that
> > limitation * were removed, we still could not a) exceed 2^23-1 because
> > inval.c stores * the ProcNumber as a 3-byte signed integer, b) INT_MAX/4
> > because some places * compute 4*MaxBackends without any overflow check.
> > This is rechecked in the * relevant GUC check hooks and in
> > RegisterBackgroundWorker(). */#define MAX_BACKENDS 0x3FFFF*
> >
> > 2^23-1 is noted as an additional upper limit, but I wonder if it'd be
> > correct to update the comment in lwlocks.c to

> Thinking a bit further about this, the purpose of the LW_SHARED_MASK
> section of the state is to count the number of lock-sharers. Thus, we only
> care about the actual number of backends (up to 2^18-1) here and not the
> size of the ProcNumber data type. So I do think the comment should read
> 2^18-1 and not 2^23-1. Here is a patch to that effect.

At the time that comment was written MAX_BACKENDS was 2^23-1. Alexander and I
lowered MAX_BACKENDS in 48354581a49c to 2^18-1 and apparently didn't think
about the comment in lwlock.h.

commit 48354581a49c30f5757c203415aa8412d85b0f70
Author: Andres Freund <andres@anarazel.de>
Date:   2016-04-10 20:12:32 -0700

    Allow Pin/UnpinBuffer to operate in a lockfree manner.
...

    To allow atomic operations to be used, cram BufferDesc's flags,
    usage_count, buf_hdr_lock, refcount into a single 32bit atomic variable;
    that allows to manipulate them together using 32bit compare-and-swap
    operations. This requires reducing MAX_BACKENDS to 2^18-1 (which could
    be lifted by using a 64bit field, but it's not a realistic configuration
    atm).



> > */* Must be greater than MAX_BACKENDS - which is 2^18-1, so we're fine. */*
> >
> > I'm not sure if this could lead to us actually saving some bits in the
> > lwlock state, or if we could do anything useful with them anyway.

It's not quite enough bits to be useful I think. If we could free 16 bits (or
we defined LWLock.tranche to be narrower), we could store the tranche as part
of the atomic, and save 4 bytes (2 bytes of alignment padding, 2 bytes for the
tranche). But unless we reduce the size of the tranche field a decent bit
there's not enough space.

I'd really like to reduce the size of struct LWLock, but I think that'll need
a bit more changes. I think we should use a single 64bit atomic and store the
list of waiters inside the atomic.

flags: 3
exclusively locked: 1 bit
share locks: 18 bits
head of wait list: 18 bits (proc number offset)
tail of wait list: 18 bits (proc number offset)
= 58

That doesn't leave enough space for the tranche unfortunately. But if we
reduced MAX_BACKENDS to 2^16-1 and reduced the size of the tranche to to 12
bits, it'd work!

I continue to believe that MAX_BACKENDS of 2^16-1 would be sufficient - we're
far from that being a realistic limit.  Halfing the size of LWLock and laying
the ground work for making the wait-list lock-free imo would be very well
worth the reduction in an unrealistic limit...

Anyway, that's really just a periodic rant / project suggestion...


> diff --git a/src/backend/storage/lmgr/lwlock.c
> b/src/backend/storage/lmgr/lwlock.c index 2f558ffea1..d3a2619072 100644 ---
> a/src/backend/storage/lmgr/lwlock.c +++ b/src/backend/storage/lmgr/lwlock.c
> @@ -99,7 +99,7 @@ #define LW_VAL_SHARED 1
>
>  #define LW_LOCK_MASK                ((uint32) ((1 << 25)-1))
> -/* Must be greater than MAX_BACKENDS - which is 2^23-1, so we're fine. */
> +/* Must be greater than MAX_BACKENDS - which is 2^18-1, so we're fine. */
>  #define LW_SHARED_MASK                ((uint32) ((1 << 24)-1))
>
>  StaticAssertDecl(LW_VAL_EXCLUSIVE > (uint32) MAX_BACKENDS,

I'm inclined to think that we should adjust the various constants at the same
time as the comment? It's imo somewhat weird to have bits LW_SHARED_MASK that
can never be set...

I wonder if we should instead define LW_VAL_EXCLUSIVE and LW_SHARED_MASK using
MAX_BACKENDS and have a static assertion ensuring it doesn't overlap with flag
bits?  That way we don't have two sets of defines to keep in sync.

Greetings,

Andres Freund

Hi,

On 2025-01-25 23:35:51 -0800, Jacob Brazeal wrote:
> While we are on the topic of comments from lwlock.c, there is one other one
> that confused me, in LWLockWaitListLock:

> *  /* and then spin without atomic operations until lock is released */ {
> SpinDelayStatus delayStatus; init_local_spin_delay(&delayStatus); while
> (old_state & LW_FLAG_LOCKED) { perform_spin_delay(&delayStatus); old_state
> = pg_atomic_read_u32(&lock->state); }#ifdef LWLOCK_STATS delays +=
> delayStatus.delays;#endif finish_spin_delay(&delayStatus); }*
> 
> It seems that we *are* using an atomic operation in the loop (though, no
> compare-and-set, etc.) I might be mis-reading the intent of the comment,
> but I'm curious if there's a way to reword it, too.

It's not really an atomic operation. It's just reading an atomic variable
(which just guarantees that the compiler isn't eliding the read and that the
read isn't torn).  Personally I don't think there's a need to rephrase the
comment, but I probably wrote it, so take that with a grain of salt.

Greetings,

Andres Freund

PS: FYI, this list values properly quoting messages instead of replying ontop
of the entire quoted messages.

Hi,

On 2025-02-09 12:41:58 -0800, Jacob Brazeal wrote:
> > Halfing the size of LWLock and laying
> > the ground work for making the wait-list lock-free imo would be very well
> > worth the reduction in an unrealistic limit...
>
> BTW, I spent a week or two researching the lock-free queue idea,
> specifically looking at what it might look like to have a Michael-Scott
> type lock-free queue adapted to the waitlist. In the end, it seems like a
> fairly challenging project, and probably beyond my powers, but I'm very
> curious if you had some ideas around it that I'm missing. Here is a summary
> of my digging:

> The proclist has several advantages. We can always store a waitlist entry
> for a given process in the same spot in shared memory, so there's no memory
> allocation or cleanup to worry about. It's a doubly-linked list and hence
> easy to remove items from the middle of the list (given a lock is acquired).

> A Michael-Scott style lock-free queue would require giving up these
> advantages:
> * When you pop a node from a queue, it is repurposed into a temporary
> "dummy" node at the head of the queue. This means that if we want to add a
> process to a new queue, we can't reuse the memory from its previous queue
> node, because it might be in use as a dummy node. So we can't store
> waitlist entries in PGPROCs anymore; we'd probably want some kind of
> freelist. This also means that we need to eventually free nodes that have
> been popped, and the next time they're used, it might be by a different
> process.
> * The queue only supports popping from the head. So we can't directly
> support the current logic, which can skip some nodes in the waitlist to
> wakeup others. Two possibles workarounds I see: 1) split the waitlist into
> 3 different queues, one for each type (shared, exclusive, wait for val) -
> or have a lock-free "waitlist for the waitlist" that accumulates new
> entries and then we take out a lock when we actually want to release nodes.
>
> Finally, we'd need to set up some mechanism for safely freeing queue nodes
> when we're done with them, like hazard pointers or maybe epoch-based
> reclamation, which looks like a slightly better fit to me for our case, but
> both mechanisms are fairly tricky and I think we'd have to seriously
> consider finding some existing implementation that's well-tested and
> compatibly licensed instead of writing our own. (Or, maybe writing and
> testing our own version is the actual heart of this project.)

Yea, I think a general lock free doubly linked list would be hard.



> So, as I say, in the end this feels beyond my powers, but it was very
> interesting to look into and I'm curious if you had some notes lying around
> on it.


As I was suggesting upthread, I was thinking that we would continue to use
something like proclist, except that we'd "inline" the head and tail pointers
into a, now 64bit, state variable.

Generic lock free queues are decidedly nontrivial to write using
compare-exchange etc as a primitive, primarily due to ABA issues. Addressing
that in turn will often require some safe memory reclamation mechanism.  But I
think we actually have a considerably simpler case here than a general
lock-free doubly linked list.

E.g.:

1) While waiting for an lwlock, a process will not do anything else (there is
   is the corner case of enqueueing while the lock is concurrently released
   however)

2) Memory lifetime is not a concern from a need-to-free POV (it could be a
   concern from an ABA POV)

3) The set of potential list member is strictly limited and a fairly small
   number (2^18)

   This means we can represent prev/next in list members as a single 64bit
   value that that can be CASed without requiring 128bit CAS (which scales
   very badly)

4) The lock list does not have to be completely lock & wait free, it's
   sufficient for common cases to be lock free.

   We e.g. can do things like have a small ABA avoidance counter and fall back
   to something like the existing spinlock whenver it overflows.



Another aspect that could be interesting is that we effectively have two
different wait queues. One for shared lockers and one for exclusive lockers. I
wonder if we could benefit from representing them as two singly-linked list,
instead of one doubly-linked list.  There's also LW_WAIT_UNTIL_FREE, but
that's basically an exclusive lock and I think we'll get rid of it before
long.

One annoying thing is that we afaict can't rely on pointers to lwlocks to be
stable across processes, that makes some schemes harder.


I started to write up a scheme using the above restrictions, but it was taking
a bit, and I really gotta focus on stuff that can make it into the next
release...


Greetings,

Andres Freund

Hi,

On 2025-01-26 12:55:15 -0800, Jacob Brazeal wrote:
> The patch series looks good.

Thanks for reviewing! And sorry for not getting back to you about your review
comments earlier.


> > StaticAssertDecl((MAX_BACKENDS & LW_FLAG_MASK) == 0,
> >     "MAX_BACKENDS and LW_FLAG_MASK overlap");
>
> Should this check that MAX_BACKENDS & LW_LOCK_MASK == 0? To also ensure the
> LW_VAL_EXCLUSIVE bit does not overlap.

Yes, I think you're right.


On 2025-01-26 12:57:50 -0800, Jacob Brazeal wrote:
> Looking at v1-0003-WIP-Base-LWLock-limits-directly-on-MAX_BACKENDS.patch,
> I'm curious about the following assert;
>
> > #define LW_VAL_EXCLUSIVE (MAX_BACKENDS + 1)
> ...
> > StaticAssertDecl(MAX_BACKENDS < LW_VAL_EXCLUSIVE,
>   "MAX_BACKENDS too big for lwlock.c");
>
> Since LW_VAL_EXCLUSIVE is already defined as MAX_BACKENDS + 1, is this
> basically just checking for an integer overflow?

You're right, it's redundant. I think I added that in an earlier version and
then didn't remove it.


Updated patches attached.


I didn't really like moving MAX_BACKENDS to pg_config_manual.h, there are too
many constraints on it.  I moved it to procnumber.h. That's maybe not perfect,
but seems a bit better?  I also introduced MAX_BACKENDS_BITS, so that it's
easier to check against when asserting restrictions on bit space.


I also added a patch from a different thread, to remove a bunch of the magic
constants in buf_internals.h, as it felt awkward to assert the refcount bits
alone were compatible with MAX_BACKENDS, when a 'standalone' 18 was used in a
bunch of other places.  As Heikki had already reviewed that quite a while ago,
I'll push that soon.


I chose to not directly base BUF_REFCOUNT_BITS directly on MAX_BACKEND_BITS,
as it's ok to lower MAX_BACKEND_BITS without adjusting BUF_REFCOUNT_BITS. But
I went back and forth on that one.


Greetings,

Andres Freund

On Sat, Feb 22, 2025 at 7:27 AM Andres Freund <andres@anarazel.de> wrote:
+#define MAX_BACKENDS_BITS        18
+#define MAX_BACKENDS            ((1 << MAX_BACKENDS_BITS)-1)

+1 for working forwards from the bits.  But why not call it
PROC_NUMBER_BITS?  After 024c5211 and 024c5211^, the ID for backends
is a ProcNumber, and that is the thing that must fit in 18 bits.  I
like that choice of header too, it's small and limited to definitions
relating to the type and concept of a ProcNumber, which seems like the
right place for this.

Hmm.  Why shouldn't the highest usable ProcNumber (that you might call
PROC_NUMBER_MAX, like INT_MAX et all) be (1 << PROC_NUMBER_BITS) - 1,
and wouldn't that imply that MAX_BACKENDS should actually be 1 <<
PROC_NUMBER_BITS and that any valid ProcNumber (a 0-based index)
should be *less than* MAX_BACKENDS (a count)?  In other words, doesn't
the current coding arbitrarily prevent the use of one more backend,
the one that has the highest ProcNumber representable in 18 bits?  If
I'm right about that I think it is perhaps related to the use of 0 as
an invalid/unset BackendId before the ProcNumber-only redesign.
INVALID_PROC_NUMBER is -1, ie it doesn't eat one of the possible
values in the 18-bit space reserved in various tight corners, since 0
is a valid ProcNumber, unless I'm missing something?

+ * currently realistic configurations. Even if that limitation were removed,
+ * we still could not a) exceed 2^23-1 because inval.c stores the ProcNumber
+ * as a 3-byte signed integer, b) INT_MAX/4 because some places compute
+ * 4*MaxBackends without any overflow check.  This is rechecked in the

Should those two constraints have their own assertions?

Hi,

On 2025-02-22 18:54:08 +1300, Thomas Munro wrote:
> On Sat, Feb 22, 2025 at 7:27 AM Andres Freund <andres@anarazel.de> wrote:
> +#define MAX_BACKENDS_BITS        18
> +#define MAX_BACKENDS            ((1 << MAX_BACKENDS_BITS)-1)
> 
> +1 for working forwards from the bits.  But why not call it
> PROC_NUMBER_BITS?

Partially just because it was named MAX_BACKENDS historically. But also
because it seems like it could be misleading - ProcNumber has more bits than
PROC_NUMBER_BITS would indicate.


> Hmm.  Why shouldn't the highest usable ProcNumber (that you might call
> PROC_NUMBER_MAX, like INT_MAX et all)

FWIW, I don't think we should name it _MAX, precisely because of INT_MAX
etc. INT_MAX indicate the actual range of the type, which isn't what we're
dealing with here.


> be (1 << PROC_NUMBER_BITS) - 1, and wouldn't that imply that MAX_BACKENDS
> should actually be 1 << PROC_NUMBER_BITS and that any valid ProcNumber (a
> 0-based index) should be *less than* MAX_BACKENDS (a count)?

I don't *think* so, but I'm good at off-by-one-ing:

> In other words, doesn't the current coding arbitrarily prevent the use of
> one more backend, the one that has the highest ProcNumber representable in
> 18 bits?  If I'm right about that I think it is perhaps related to the use
> of 0 as an invalid/unset BackendId before the ProcNumber-only redesign.

We do count the number of lwlock share lockers and the number of buffer
refcounts within those bits. And obviously 0 lockers/refcounts has to be
valid. So I think the limit is correct?


> + * currently realistic configurations. Even if that limitation were removed,
> + * we still could not a) exceed 2^23-1 because inval.c stores the ProcNumber
> + * as a 3-byte signed integer, b) INT_MAX/4 because some places compute
> + * 4*MaxBackends without any overflow check.  This is rechecked in the
> 
> Should those two constraints have their own assertions?

Probably wouldn't hurt, even though I think it's unlikely to matter anytime
soon.

I didn't yet have enough coffe, but isn't the inval.c limit 2^24-1 rather than
2^23-1?

Greetings,

Andres Freund

On Sun, Feb 23, 2025 at 4:16 AM Andres Freund <andres@anarazel.de> wrote:
> We do count the number of lwlock share lockers and the number of buffer
> refcounts within those bits. And obviously 0 lockers/refcounts has to be
> valid. So I think the limit is correct?

Ah, right.  That makes perfect sense.  The 18 bits need to be able to
hold a count, not just an index, and I confused myself about that from
the moment I thought about the name PROC_NUMBER_BITS, which I retract.

> I didn't yet have enough coffe, but isn't the inval.c limit 2^24-1 rather than
> 2^23-1?

Yeah, it has 24 bits of space, but curiously backend_hi is signed, so
(msg->sm.backend_hi << 16) would be sign-extended, so it wouldn't actually
work if you used all 24 bits... which is obviously not a real
problem...

Hi,

On 2025-02-23 10:39:36 +1300, Thomas Munro wrote:
> On Sun, Feb 23, 2025 at 4:16 AM Andres Freund <andres@anarazel.de> wrote:
> > We do count the number of lwlock share lockers and the number of buffer
> > refcounts within those bits. And obviously 0 lockers/refcounts has to be
> > valid. So I think the limit is correct?
> 
> Ah, right.  That makes perfect sense.  The 18 bits need to be able to
> hold a count, not just an index, and I confused myself about that from
> the moment I thought about the name PROC_NUMBER_BITS, which I retract.

Cool. I now pushed them, including static asserts in inval.c and deadlock.

Thanks for the reviews and the complaint leading to these changes.


> > I didn't yet have enough coffe, but isn't the inval.c limit 2^24-1 rather than
> > 2^23-1?
> 
> Yeah, it has 24 bits of space, but curiously backend_hi is signed, so
> (msg->sm.backend_hi << 16) would be sign-extended, so it wouldn't actually
> work if you used all 24 bits... which is obviously not a real
> problem...

Heh, that's odd. I left it like that, didn't seem worth changing given that
it's so far from the real limit...

Greetings,

Andres Freund

The recent commits for this drew my attention to the comment for
MAX_BACKENDS.  Specifically, it says we check the value in
RegisterBackgroundWorker() (which appears to have been untrue since we
added max_worker_processes) and relevant GUC check hooks (which I removed
last year in commit 0b1fe14).  I wrote a short patch to fix this, which I
intend to commit soon unless there is feedback.

-- 
nathan

Hi,

On 2025-02-24 13:52:51 -0600, Nathan Bossart wrote:
> The recent commits for this drew my attention to the comment for
> MAX_BACKENDS.  Specifically, it says we check the value in
> RegisterBackgroundWorker() (which appears to have been untrue since we
> added max_worker_processes) and relevant GUC check hooks (which I removed
> last year in commit 0b1fe14).  I wrote a short patch to fix this, which I
> intend to commit soon unless there is feedback.

Makes sense.

Greetings,

Andres Freund

On Mon, Feb 24, 2025 at 03:38:24PM -0500, Andres Freund wrote:
> Makes sense.

Committed, thanks.

-- 
nathan