Re: Wait free LW_SHARED acquisition - v0.2

On Tue, Jun 24, 2014 at 9:33 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
wrote:
> On Mon, Jun 23, 2014 at 9:12 PM, Andres Freund <andres(at)2ndquadrant(dot)com>
wrote:
> > On 2014-06-23 19:59:10 +0530, Amit Kapila wrote:
> > > 7.
> > > LWLockWaitForVar()
> > > {
> > > ..
> > > /*
> > > * Add myself to wait queue. Note that this is racy, somebody else
> > > * could wakeup before we're finished queuing.
> > > * NB: We're using nearly the same twice-in-a-row lock acquisition
> > > * protocol as LWLockAcquire(). Check its comments for details.
> > > */
> > > LWLockQueueSelf(l, LW_WAIT_UNTIL_FREE);
> > >
> > > /* we're now guaranteed to be woken up if necessary */
> > > mustwait = LWLockAttemptLock(l, LW_EXCLUSIVE, false,
> > > &potentially_spurious);
> > > }
> > >
> > > Why is it important to Attempt lock after queuing in this case, can't
> > > we just re-check exclusive lock as done before queuing?
> >
> > Well, that's how Heikki designed LWLockWaitForVar().
>
> In that case I might be missing some point here, un-patched code of
> LWLockWaitForVar() never tries to acquire the lock, but the new code
> does so. Basically I am not able to think what is the problem if we just
> do below after queuing:
> mustwait = pg_atomic_read_u32(&lock->lockcount) != 0;
>
> Could you please explain what is the problem in just rechecking?

I have further reviewed the lwlock related changes and thought
its good to share my findings with you. This completes my initial
review for lwlock related changes and below are my findings:

1.
LWLockRelease()
{
..
TRACE_POSTGRESQL_LWLOCK_RELEASE(T_NAME(l), T_ID(l));
}

Dynamic tracing macro seems to be omitted from LWLockRelease()
call.

2.
LWLockWakeup()
{
..
#ifdef LWLOCK_STATS
lwstats->spin_delay_count += SpinLockAcquire(&lock->mutex);
#else
SpinLockAcquire(&lock->mutex);
#endif
..
}

Earlier while releasing lock, we don't count it towards LWLock stats
spin_delay_count. I think if we see other places in lwlock.c, it only gets
counted when we try to acquire it in a loop.

3.
LWLockRelease()
{
..
/* grant permission to run, even if a spurious share lock increases
lockcount */
else if (mode == LW_EXCLUSIVE && have_waiters)
check_waiters = true;
/* nobody has this locked anymore, potential exclusive lockers get a chance
*/
else if (lockcount == 0 && have_waiters)
check_waiters = true;
..
}

It seems comments have been reversed in above code.

4.
LWLockWakeup()
{
..
dlist_foreach_modify(iter, (dlist_head *) &l->waiters)
..
}

Shouldn't we need to use volatile variable in above loop (lock instead of
l)?

5.
LWLockWakeup()
{
..
dlist_foreach_modify(iter, (dlist_head *) &wakeup)
{
PGPROC *waiter = dlist_container(PGPROC, lwWaitLink, iter.cur);
LOG_LWDEBUG("LWLockRelease", l, mode, "release waiter");
dlist_delete(&waiter->lwWaitLink);
pg_write_barrier();
waiter->lwWaiting = false;
PGSemaphoreUnlock(&waiter->sem);
}
..
}

Why can't we decrement the nwaiters after waking up? I don't think
there is any major problem even if callers do that themselves, but
in some rare cases LWLockRelease() might spuriously assume that
there are some waiters and tries to call LWLockWakeup(). Although
this doesn't create any problem, keeping the value sane is good unless
there is some problem in doing so.

6.
LWLockWakeup()
{
..
dlist_foreach_modify(iter, (dlist_head *) &l->waiters)
{
..
if (wokeup_somebody && waiter->lwWaitMode == LW_EXCLUSIVE)
continue;
..
if (waiter->lwWaitMode != LW_WAIT_UNTIL_FREE)
{
..
wokeup_somebody = true;
}
..
}
..
}

a.
IIUC above logic, if the waiter queue is as follows:
(S-Shared; X-Exclusive) S X S S S X S S

it can skip the exclusive waiters and release shared waiter.

If my understanding is right, then I think instead of continue, there
should be *break* in above logic.

b.
Consider below sequence of waiters:
(S-Shared; X-Exclusive) S S X S S

I think as per un-patched code, it will wakeup waiters uptill (including)
first Exclusive, but patch will wake up uptill (*excluding*) first
Exclusive.

7.
LWLockWakeup()
{
..
dlist_foreach_modify(iter, (dlist_head *) &l->waiters)
{
..
dlist_delete(&waiter->lwWaitLink);
dlist_push_tail(&wakeup, &waiter->lwWaitLink);
..
}
..
}

Use of dlist has simplified the code, but I think there might be a slight
overhead of maintaining wakeup queue as compare to un-patched
mechanism especially when there is a long waiter queue.

8.
LWLockConditionalAcquire()
{
..
/*
* We ran into an exclusive lock and might have blocked another
* exclusive lock from taking a shot because it took a time to back
* off. Retry till we are either sure we didn't block somebody (because
* somebody else certainly has the lock) or till we got it.
*
* We cannot rely on the two-step lock-acquisition protocol as in
* LWLockAcquire because we're not using it.
*/
if (potentially_spurious)
{
SPIN_DELAY();
goto retry;
}
..
}

Due to above logic, I think it can keep on retrying for long time before
it actually concludes whether it got lock or not incase other backend/'s
takes Exclusive lock after *double_check* and release before
unconditional increment of shared lock in function LWLockAttemptLock.
I understand that it might be difficult to have such a practical scenario,
however still there is a theoratical possibility of same.

Is there any advantage of retrying in LWLockConditionalAcquire()?

I think its improtant to have 2-phase LockAttempt in case of
LWLockAcquireCommon() as we have splitted the work of trying to
acquire a lock and queuing it for wait incase didn't got the lock,
but here there is no such thing, so I am wondering is there any
problem, if we just return false after failure of first attempt?

9.
LWLockAcquireOrWait()
{
..
/*
* NB: We're using nearly the same twice-in-a-row lock acquisition
* protocol as LWLockAcquire(). Check its comments for details.
*/
mustwait = LWLockAttemptLock(l, mode, false, &potentially_spurious_first);

if (mustwait)
{
LWLockQueueSelf(l, LW_WAIT_UNTIL_FREE);

mustwait = LWLockAttemptLock(l, mode, false, &potentially_spurious_second);

}

In this function, it doesn't seem to be required to use the return value
*mustwait* of second LWLockAttemptLock() call as a return value of
function, as per usage of this function if we don't get the lock at first
attempt, then it needs to check if the corresponding WAL record is flushed.
I think here we need the logic what you have used in LWLockWaitForVar()
(release the lock if we get it in second attempt).

10.
LWLockAcquireOrWait()
{
..
bool potentially_spurious_first;
bool potentially_spurious_second;
..
}

Why to use *_first and *_second in this function, can't we just have
one variable as in other LWLock.. variant functions?

11.
LWLockAcquireOrWait()
{
..
Assert(mode == LW_SHARED || mode == LW_EXCLUSIVE);
}

Isn't it better to use AssertArg() rather than Assert in above usage?

12.
LWLockAcquireOrWait()
{
..
if (mustwait)
{
/*
* Wait until awakened. Like in LWLockAcquire, be prepared for bogus
* wakups, because we share the semaphore with ProcWaitForSignal.
*/
LOG_LWDEBUG("LWLockAcquireOrWait", T_NAME(l), T_ID(l), "waiting");
..
}

log for awakened is missing, it's there is current code.

13.
LWLockAcquireOrWait()
{
..
LOG_LWDEBUG("LWLockAcquireOrWait", lockid, mode, "suceeded");
..
}

a. spelling of "suceeded" is wrong.
b. such a log is not there in any other LWLock.. variants, if we want
to introduce it, then shouldn't it be done at other places as well.

14.
typedef struct lwlock_stats
{
+ int ex_race;
..
}

Currently I don't see the usage of this variable, is there a plan to use
it in future?

15.
/* must be greater than MAX_BACKENDS */
#define SHARED_LOCK_MASK (~EXCLUSIVE_LOCK)

a. how can we guarantee it to be greater than MaxBackends,
as MaxBackends is int (the max value for which will be
equal to SHARED_LOCK_MASK)?
b. This is used only for LWLOCK_STATS, so shouldn't we
define this under LWLOCK_STATS.

16.
LWLockAcquireCommon()
{
volatile LWLock *lock = l;
..
mustwait = LWLockAttemptLock(l, mode, false, &potentially_spurious);
..
lock->releaseOK = true;
..
pg_atomic_fetch_sub_u32(&lock->nwaiters, 1);
}

Shouldn't we need to use *lock* variable in LWLockAttemptLock()
function call?

Note - I have completed the review of LWLock related changes of your
overall patch in 3 different parts, as the changes are more and it makes
me understand your views behind implementation. I am maintaining
all the findings, so when you send the updated patch, I will verify by
using the same. I hope that it's not inconvenient for you.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com