lkml.org 
[lkml]   [2019]   [Apr]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v4 07/16] locking/rwsem: Implement lock handoff to prevent lock starvation
From
Date
On 04/16/2019 11:49 AM, Peter Zijlstra wrote:
> On Sat, Apr 13, 2019 at 01:22:50PM -0400, Waiman Long wrote:
>
>> +#define RWSEM_COUNT_HANDOFF(c) ((c) & RWSEM_FLAG_HANDOFF)
>> +#define RWSEM_COUNT_LOCKED_OR_HANDOFF(c) \
>> + ((c) & (RWSEM_LOCK_MASK|RWSEM_FLAG_HANDOFF))
> Like said before, I also made these go away.

Yes, my refactored patches will remove all those trivial macros.

>
>> @@ -245,6 +274,8 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
>> struct rwsem_waiter *waiter, *tmp;
>> long oldcount, woken = 0, adjustment = 0;
>>
>> + lockdep_assert_held(&sem->wait_lock);
>> +
>> /*
>> * Take a peek at the queue head waiter such that we can determine
>> * the wakeup(s) to perform.
>> @@ -276,6 +307,15 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
>> adjustment = RWSEM_READER_BIAS;
>> oldcount = atomic_long_fetch_add(adjustment, &sem->count);
>> if (unlikely(oldcount & RWSEM_WRITER_MASK)) {
>> + /*
>> + * Initiate handoff to reader, if applicable.
>> + */
>> + if (!(oldcount & RWSEM_FLAG_HANDOFF) &&
>> + time_after(jiffies, waiter->timeout)) {
>> + adjustment -= RWSEM_FLAG_HANDOFF;
>> + lockevent_inc(rwsem_rlock_handoff);
>> + }
> /*
> * When we've been waiting 'too' long (for
> * writers to give up the lock) request a
> * HANDOFF to force the issue.
> */
>
> ?

Sure.

>
>> +
>> atomic_long_sub(adjustment, &sem->count);
> Can we change this to: atomic_long_add() please? The below loop that
> wakes all remaining readers does use add(), so it is a bit 'weird' to
> have the adjustment being negated on handover.
>
>> return;
>> }
>> @@ -324,6 +364,12 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
>> adjustment -= RWSEM_FLAG_WAITERS;
>> }
>>
>> + /*
>> + * Clear the handoff flag
>> + */
> Right, but that is a trivial comment in the 'increment i' style, it
> clearly states what the code does, but completely fails to elucidate the
> code.
>
> Maybe:
>
> /*
> * When we've woken a reader, we no longer need to force writers
> * to give up the lock and we can clear HANDOFF.
> */
>
> And I suppose this is required if we were the pickup of the handoff set
> above, but is there a guarantee that the HANDOFF was not set by a
> writer?

I can change the comment. The handoff bit is always cleared in
rwsem_try_write_lock() when the lock is successfully acquire. Will add a
comment to document that.

>
>> + if (woken && RWSEM_COUNT_HANDOFF(atomic_long_read(&sem->count)))
>> + adjustment -= RWSEM_FLAG_HANDOFF;
>> +
>> if (adjustment)
>> atomic_long_add(adjustment, &sem->count);
>> }
>> @@ -332,22 +378,42 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
>> * This function must be called with the sem->wait_lock held to prevent
>> * race conditions between checking the rwsem wait list and setting the
>> * sem->count accordingly.
>> + *
>> + * If wstate is WRITER_HANDOFF, it will make sure that either the handoff
>> + * bit is set or the lock is acquired.
>> */
>> +static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem,
>> + enum writer_wait_state wstate)
>> {
>> long new;
>>
> lockdep_assert_held(&sem->wait_lock);

Sure.

>
>> +retry:
>> + if (RWSEM_COUNT_LOCKED(count)) {
>> + if (RWSEM_COUNT_HANDOFF(count) || (wstate != WRITER_HANDOFF))
>> + return false;
>> + /*
>> + * The lock may become free just before setting handoff bit.
>> + * It will be simpler if atomic_long_or_return() is available.
>> + */
>> + atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);
>> + count = atomic_long_read(&sem->count);
>> + goto retry;
>> + }
>> +
>> + if ((wstate == WRITER_NOT_FIRST) && RWSEM_COUNT_HANDOFF(count))
>> return false;
>>
>> + new = (count & ~RWSEM_FLAG_HANDOFF) + RWSEM_WRITER_LOCKED -
>> + (list_is_singular(&sem->wait_list) ? RWSEM_FLAG_WAITERS : 0);
>>
>> if (atomic_long_try_cmpxchg_acquire(&sem->count, &count, new)) {
>> rwsem_set_owner(sem);
>> return true;
>> }
>>
>> + if (unlikely((wstate == WRITER_HANDOFF) && !RWSEM_COUNT_HANDOFF(count)))
>> + goto retry;
>> +
>> return false;
>> }
> This function gives me heartburn. Don't you just feel something readable
> trying to struggle free from that?
>
> See, if you first write that function in the form:
>
> long new;
>
> do {
> new = count | RWSEM_WRITER_LOCKED;
>
> if (count & RWSEM_LOCK_MASK)
> return false;
>
> if (list_is_singular(&sem->wait_list))
> new &= ~RWSEM_FLAG_WAITERS;
>
> } while (atomic_long_try_cmpxchg_acquire(&sem->count, &count, new));
>
> rwsem_set_owner(sem);
> return true;
>
> And then add the HANDOFF bits like:
>
> long new;
>
> do {
> + bool has_handoff = !!(count & RWSEM_FLAG_HANDOFF);
>
> + new = (count | RWSEM_WRITER_LOCKED) & ~RWSEM_FLAG_HANDOFF;
>
> if (count & RWSEM_LOCK_MASK) {
> + if (has_handoff && wstate != WRITER_HANDOFF)
> + return false;
> new |= RWSEM_FLAG_HANDOFF;
> }
>
> + if (has_handoff && wstate == WRITER_NOT_FIRST)
> + return false;
>
> if (list_is_singular(&sem->wait_list))
> new &= ~RWSEM_FLAG_WAITERS;
>
> } while (atomic_long_try_cmpxchg_acquire(&sem->count, &count, new));
>
> rwsem_set_owner(sem);
> return true;
>
> it almost looks like sensible code.

Yes, it looks much better. I don't like that piece of code myself. I am
sorry that I didn't spend the time to make the code more sane.

Thanks for your suggestion. Will modify it accordingly.

>>
>> @@ -359,7 +425,7 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
>> {
>> long count = atomic_long_read(&sem->count);
>>
>> - while (!RWSEM_COUNT_LOCKED(count)) {
>> + while (!RWSEM_COUNT_LOCKED_OR_HANDOFF(count)) {
>> if (atomic_long_try_cmpxchg_acquire(&sem->count, &count,
>> count + RWSEM_WRITER_LOCKED)) {
> RWSEM_WRITER_LOCKED really should be RWSEM_FLAG_WRITER or something like
> that, and since it is a flag, that really should've been | not +.

Sure.

>> rwsem_set_owner(sem);
>> @@ -498,6 +564,16 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
>> }
>> #endif
>>
>> +/*
>> + * This is safe to be called without holding the wait_lock.
>> + */
>> +static inline bool
>> +rwsem_waiter_is_first(struct rw_semaphore *sem, struct rwsem_waiter *waiter)
>> +{
>> + return list_first_entry(&sem->wait_list, struct rwsem_waiter, list)
>> + == waiter;
> Just bust the line limit on that, this is silly. If you feel strongly
> about the 80 char thing, we could do:
>
> #define rwsem_first_waiter(sem) \
> list_first_entry(&sem->wait_list, struct rwsem_waiter, list)
>
> and use that in both locations. (and one could even write the
> list_for_each_entry_safe() loop in the form:
>
> while (!list_empty(&sem->wait_list)) {
> entry = rwsem_first_waiter(sem);
>
> ...
>
> list_del();
>
> ...
> }
>
> Although I suppose that gets you confused later on where you want to
> wake more readers still... I'll get there,.. eventually.

Yes, it is a good idea.

>> +}
>> +
>> /*
>> * Wait for the read lock to be granted
>> */
>> @@ -510,16 +586,18 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
>>
>> waiter.task = current;
>> waiter.type = RWSEM_WAITING_FOR_READ;
>> + waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
>>
>> raw_spin_lock_irq(&sem->wait_lock);
>> if (list_empty(&sem->wait_list)) {
>> /*
>> * In case the wait queue is empty and the lock isn't owned
>> + * by a writer or has the handoff bit set, this reader can
>> + * exit the slowpath and return immediately as its
>> + * RWSEM_READER_BIAS has already been set in the count.
>> */
>> + if (!(atomic_long_read(&sem->count) &
>> + (RWSEM_WRITER_MASK | RWSEM_FLAG_HANDOFF))) {
>> raw_spin_unlock_irq(&sem->wait_lock);
>> rwsem_set_reader_owned(sem);
>> lockevent_inc(rwsem_rlock_fast);
>> @@ -567,7 +645,8 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
>> out_nolock:
>> list_del(&waiter.list);
>> if (list_empty(&sem->wait_list))
>> + atomic_long_andnot(RWSEM_FLAG_WAITERS|RWSEM_FLAG_HANDOFF,
>> + &sem->count);
> If you split the line, this wants { }.

OK.

>> raw_spin_unlock_irq(&sem->wait_lock);
>> __set_current_state(TASK_RUNNING);
>> lockevent_inc(rwsem_rlock_fail);
>> @@ -593,7 +672,7 @@ static inline struct rw_semaphore *
>> __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
>> {
>> long count;
>> + enum writer_wait_state wstate;
>> struct rwsem_waiter waiter;
>> struct rw_semaphore *ret = sem;
>> DEFINE_WAKE_Q(wake_q);
>> @@ -608,56 +687,63 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
>> */
>> waiter.task = current;
>> waiter.type = RWSEM_WAITING_FOR_WRITE;
>> + waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
>>
>> raw_spin_lock_irq(&sem->wait_lock);
>>
>> /* account for this before adding a new element to the list */
>> + wstate = list_empty(&sem->wait_list) ? WRITER_FIRST : WRITER_NOT_FIRST;
>>
>> list_add_tail(&waiter.list, &sem->wait_list);
>>
>> /* we're now waiting on the lock */
>> + if (wstate == WRITER_NOT_FIRST) {
>> count = atomic_long_read(&sem->count);
>>
>> /*
>> + * If there were already threads queued before us and:
>> + * 1) there are no no active locks, wake the front
>> + * queued process(es) as the handoff bit might be set.
>> + * 2) there are no active writers and some readers, the lock
>> + * must be read owned; so we try to wake any read lock
>> + * waiters that were queued ahead of us.
>> */
>> + if (!RWSEM_COUNT_LOCKED(count))
>> + __rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
>> + else if (!(count & RWSEM_WRITER_MASK) &&
>> + (count & RWSEM_READER_MASK))
>> __rwsem_mark_wake(sem, RWSEM_WAKE_READERS, &wake_q);
> That RWSEM_WRITER_MASK is another layer of obfustaction we can do
> without.

The RWSEM_WRITER_MASK macro is added to prepare for the later patch that
merge owner into count where RWSEM_WRITER_LOCK will be different.

> Does the above want to be something like:
>
> if (!(count & RWSEM_WRITER_LOCKED)) {
> __rwsem_mark_wake(sem, (count & RWSEM_READER_MASK) ?
> RWSEM_WAKE_READERS :
> RWSEM_WAKE_ANY, &wake_q);
> }

Yes.

>> + else
>> + goto wait;
>>
>> + /*
>> + * The wakeup is normally called _after_ the wait_lock
>> + * is released, but given that we are proactively waking
>> + * readers we can deal with the wake_q overhead as it is
>> + * similar to releasing and taking the wait_lock again
>> + * for attempting rwsem_try_write_lock().
>> + */
>> + wake_up_q(&wake_q);
> Hurmph.. the reason we do wake_up_q() outside of wait_lock is such that
> those tasks don't bounce on wait_lock. Also, it removes a great deal of
> hold-time from wait_lock.
>
> So I'm not sure I buy your argument here.
>

Actually, we don't want to release the wait_lock, do wake_up_q() and
acquire the wait_lock again as the state would have been changed. I
didn't change the comment on this patch, but will reword it to discuss that.

>> + /*
>> + * Reinitialize wake_q after use.
>> + */
> Or:
> /* we need wake_q again below, reinitialize */
>

Sure.

>> + wake_q_init(&wake_q);
>> } else {
>> count = atomic_long_add_return(RWSEM_FLAG_WAITERS, &sem->count);
>> }
>>
>> +wait:
>> /* wait until we successfully acquire the lock */
>> set_current_state(state);
>> while (true) {
>> + if (rwsem_try_write_lock(count, sem, wstate))
>> break;
>> +
>> raw_spin_unlock_irq(&sem->wait_lock);
>>
>> /* Block until there are no active lockers. */
>> + for (;;) {
>> if (signal_pending_state(state, current))
>> goto out_nolock;
>>
>> @@ -665,9 +751,34 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
>> lockevent_inc(rwsem_sleep_writer);
>> set_current_state(state);
>> count = atomic_long_read(&sem->count);
>> +
>> + if ((wstate == WRITER_NOT_FIRST) &&
>> + rwsem_waiter_is_first(sem, &waiter))
>> + wstate = WRITER_FIRST;
>> +
>> + if (!RWSEM_COUNT_LOCKED(count))
>> + break;
>> +
>> + /*
>> + * An RT task sets the HANDOFF bit immediately.
>> + * Non-RT task will wait a while before doing so.
> Again, this describes what we already read the code to do; but doesn't
> add anything.

Will remove that.

>> + *
>> + * The setting of the handoff bit is deferred
>> + * until rwsem_try_write_lock() is called.
>> + */
>> + if ((wstate == WRITER_FIRST) && (rt_task(current) ||
>> + time_after(jiffies, waiter.timeout))) {
>> + wstate = WRITER_HANDOFF;
>> + lockevent_inc(rwsem_wlock_handoff);
>> + /*
>> + * Break out to call rwsem_try_write_lock().
>> + */
> Another exceedingly useful comment.
>
>> + break;
>> + }
>> + }
>>
>> raw_spin_lock_irq(&sem->wait_lock);
>> + count = atomic_long_read(&sem->count);
>> }
>> __set_current_state(TASK_RUNNING);
>> list_del(&waiter.list);
>> @@ -680,6 +791,12 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
>> __set_current_state(TASK_RUNNING);
>> raw_spin_lock_irq(&sem->wait_lock);
>> list_del(&waiter.list);
>> + /*
>> + * If handoff bit has been set by this waiter, make sure that the
>> + * clearing of it is seen by others before proceeding.
>> + */
>> + if (unlikely(wstate == WRITER_HANDOFF))
>> + atomic_long_add_return(-RWSEM_FLAG_HANDOFF, &sem->count);
> _AGAIN_ no explanation what so ff'ing ever.
>
> And why add_return() if you ignore the return value.
>

OK, will remove those.

>> if (list_empty(&sem->wait_list))
>> atomic_long_andnot(RWSEM_FLAG_WAITERS, &sem->count);
> And you could've easily combined the two flags in a single andnot op.

That is true, but the nolock case is rarely executed. That is why I opt
for simplicity than more complicated but faster code.

Cheers,
Longman

\
 
 \ /
  Last update: 2019-04-16 20:17    [W:0.228 / U:21.840 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site