lkml.org 
[lkml]   [2023]   [Jan]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH v2] locking/rwbase: Prevent indefinite writer starvation
    On Thu, Jan 19, 2023 at 05:28:48PM +0100, Sebastian Andrzej Siewior wrote:
    > On 2023-01-19 11:02:20 [+0000], Mel Gorman wrote:
    > > > - Once the writer removes READER_BIAS, it forces the reader into the
    > > > slowpath.
    > >
    > > Removed in __rwbase_write_trylock IIUC
    >
    > And added back in case try trylock failed via __rwbase_write_unlock().
    > The RTmutex is unlocked and the READER_BIAS is "returned".
    >

    Indeed.

    > > > At that time the writer does not own the wait_lock meaning
    > > > the reader _could_ check the timeout before writer had a chance to set
    > > > it. The worst thing is probably that if jiffies does not have the
    > > > highest bit set then it will always disable the reader bias here.
    > > > The easiest thing is probably to check timeout vs 0 and ensure on the
    > > > writer side that the lowest bit is always set (in the unlikely case it
    > > > will end up as zero).
    > > >
    > >
    > > I am missing something important. On the read side, we have
    > >
    >
    > Look at this side by side:
    >
    > writer reader
    >
    > | static int __sched rwbase_write_lock(struct rwbase_rt *rwb,
    > | unsigned int state)
    > | {
    > | /* Force readers into slow path */
    > | atomic_sub(READER_BIAS, &rwb->readers);
    >
    >
    > | static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,
    > | unsigned int state)
    > | {
    > | struct rt_mutex_base *rtm = &rwb->rtmutex;
    > | int ret;
    > |
    > | raw_spin_lock_irq(&rtm->wait_lock);
    >
    > Reader has the lock, writer will wait.
    >
    > | /*
    > | * Allow readers, as long as the writer has not completely
    > | * acquired the semaphore for write.
    > | */
    > | if (atomic_read(&rwb->readers) != WRITER_BIAS) {
    >
    > here, the timeout value is not yet populated by the writer so the reader
    > compares vs 0.
    >
    > | atomic_inc(&rwb->readers);
    > | raw_spin_unlock_irq(&rtm->wait_lock);
    > | return 0;
    > | }
    > |
    >
    > | raw_spin_lock_irqsave(&rtm->wait_lock, flags);
    > | if (__rwbase_write_trylock(rwb))
    > | goto out_unlock;
    > |
    >
    > Hope this makes it easier.
    >

    Yes, it makes your concern much clearer but I'm not sure it actually matters
    in terms of preventing write starvation or in terms of correctness. At
    worst, a writer is blocked that could have acquired the lock during a tiny
    race but that's a timing issue rather than a correctness issue.

    Lets say the race hits

    reader sees waiter_timeout == 0
    writer acquires wait_lock
    __rwbase_write_trylock fails
    update waiter_timeout
    rwbase_schedule

    Each reader that hits the race goes ahead at a point in time but anything
    readers after that observe the timeout and eventually the writer goes ahead.

    If the waiter_timeout was updated before atomic_sub(READER_BIAS),
    it doesn't close the race as atomic_sub is unordered so barriers would
    also be needed and clearing of waiter_timeout moves to out_unlock in case
    __rwbase_write_trylock succeeds. That's possible but the need for barriers
    makes it more complicated than is necessary.

    The race could be closed by moving wait_lock acquisition before the
    atomic_sub in rwbase_write_lock() but it expands the scope of the wait_lock
    and I'm not sure that's necessary for either correctness or preventing
    writer starvation. It's a more straight-forward fix but expanding the
    scope of a lock unnecessarily has been unpopular in the past.

    I think we can close the race that concerns you but I'm not convinced we
    need to and changing the scope of wait_lock would need a big comment and
    probably deserves a separate patch.

    Sorry if I'm still missing something stupid and thanks for your patience
    reviewing this.

    --
    Mel Gorman
    SUSE Labs

    \
     
     \ /
      Last update: 2023-03-26 23:48    [W:2.751 / U:0.012 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site