On Thu, Aug 09 2018, Jeff Layton wrote:
> On Thu, 2018-08-09 at 12:04 +1000, NeilBrown wrote:
>> When we find an existing lock which conflicts with a request,
>> and the request wants to wait, we currently add the request
>> to a list. When the lock is removed, the whole list is woken.
>> This can cause the thundering-herd problem.
>> To reduce the problem, we make use of the (new) fact that
>> a pending request can itself have a list of blocked requests.
>> When we find a conflict, we look through the existing blocked requests.
>> If any one of them blocks the new request, the new request is attached
>> below that request.
>> This way, when the lock is released, only a set of non-conflicting
>> locks will be woken. The rest of the herd can stay asleep.
>>
>> Reported-and-tested-by: Martin Wilck <mwilck@xxxxxxx>
>> Signed-off-by: NeilBrown <neilb@xxxxxxxx>
>> ---
>> fs/locks.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
>> 1 file changed, 63 insertions(+), 6 deletions(-)
>>
>> diff --git a/fs/locks.c b/fs/locks.c
>> index fc64016d01ee..17843feb6f5b 100644
>> --- a/fs/locks.c
>> +++ b/fs/locks.c
>> @@ -738,6 +738,39 @@ static void locks_delete_block(struct file_lock *waiter)
>> spin_unlock(&blocked_lock_lock);
>> }
>>
>> +static void wake_non_conflicts(struct file_lock *waiter, struct file_lock *blocker,
>> + enum conflict conflict(struct file_lock *,
>> + struct file_lock *))
>> +{
>> + struct file_lock *parent = waiter;
>> + struct file_lock *fl;
>> + struct file_lock *t;
>> +
>> + fl = list_entry(&parent->fl_blocked, struct file_lock, fl_block);
>> +restart:
>> + list_for_each_entry_safe_continue(fl, t, &parent->fl_blocked, fl_block) {
>> + switch (conflict(fl, blocker)) {
>> + default:
>
> BUG or WARN here too please.
Maybe .... I'd rather not have the default case at all.
I can remove this one, but if I remove the next one, gcc complains
../fs/locks.c: In function ‘posix_locks_conflict’:
../fs/locks.c:912:1: warning: control reaches end of non-void function [-Wreturn-type]
event though control cannot reach the end of the function.
Maybe:
switch (locks_conflict(caller_fl, sys_fl)) {
default:
WARN(1, "locks_conflict returned impossible value");
/* fallthrough */
case FL_NO_CONFLICT:
>
>> + case FL_NO_CONFLICT:
>> + __locks_wake_one(fl);
>> + break;
>> + case FL_CONFLICT:
>> + /* Need to check children */
>> + parent = fl;
>> + fl = list_entry(&parent->fl_blocked, struct file_lock, fl_block);
>> + goto restart;
>> + case FL_TRANSITIVE_CONFLICT:
>> + /* all children must also conflict, no need to check */
>> + continue;
>> + }
>> + }
>> + if (parent != waiter) {
>> + parent = parent->fl_blocker;
>> + fl = parent;
>> + goto restart;
>> + }
>> +}
>> +
>> /* Insert waiter into blocker's block list.
>> * We use a circular list so that processes can be easily woken up in
>> * the order they blocked. The documentation doesn't require this but
>> @@ -747,11 +780,32 @@ static void locks_delete_block(struct file_lock *waiter)
>> * fl_blocked list itself is protected by the blocked_lock_lock, but by ensuring
>> * that the flc_lock is also held on insertions we can avoid taking the
>> * blocked_lock_lock in some cases when we see that the fl_blocked list is empty.
>> + *
>> + * Rather than just adding to the list, we check for conflicts with any existing
>> + * waiter, and add to that waiter instead.
>> + * Thus wakeups don't happen until needed.
>> */
>> static void __locks_insert_block(struct file_lock *blocker,
>> - struct file_lock *waiter)
>> + struct file_lock *waiter,
>> + enum conflict conflict(struct file_lock *,
>> + struct file_lock *))
>> {
>> + struct file_lock *fl;
>> BUG_ON(!list_empty(&waiter->fl_block));
>> +
>> + /* Any request in waiter->fl_blocked is know to conflict with
>
> "known"
>
>> + * waiter, but it might not conflict with blocker.
>> + * If it doesn't, it needs to be woken now so it can find
>> + * somewhere else to wait, or possible it can get granted.
>
> "possibly it can be"
Both fixed, thanks.
>
>> + */
>> + if (conflict(waiter, blocker) != FL_TRANSITIVE_CONFLICT)
>> + wake_non_conflicts(waiter, blocker, conflict);
>> +new_blocker:
>> + list_for_each_entry(fl, &blocker->fl_blocked, fl_block)
>> + if (conflict(fl, waiter)) {
>> + blocker = fl;
>> + goto new_blocker;
>> + }
>>
>> > waiter->fl_blocker = blocker;
>> list_add_tail(&waiter->fl_block, &blocker->fl_blocked);
>> if (IS_POSIX(blocker) && !IS_OFDLCK(blocker))
>
> I wonder if it might be better to insert the blocker first before waking
> up other waiters? Consider that anything awoken will end up contending
> for the flc_lock that is held by "current" at this point. Doing most of
> what you need to get done before waking them might mean less spinning in
> other tasks.
>
Maybe.
I think you are suggesting we move the call to wake_non_conflicts() to
the end of the function.
The main reason I put it at the top is to use the original value of
"blocker" before it gets changed.
Even if we move it to the end, there is still quite a few other little
tasks to be performed before the lock is dropped.
Will all this get done before some other processor has a chance to wake
up a process, and for that process to get a to spinlock ???
Maybe - though the first spinlock would be blocked_lock_lock in
locks_delete_block(), and that is dropped almost immediately.
I don't know ... it seems much of a muchness.
If the process will be woken that quickly, then some other processor
must be idle, and does it matter much if it spends a microsecond
spinning on a lock rather than being idle a bit longer?
Thanks.
I won't to do a least a little testing before I repost with any of these
changes.
NeilBrown
>> @@ -760,10 +814,12 @@ static void __locks_insert_block(struct file_lock *blocker,
>>
>> /* Must be called with flc_lock held. */
>> static void locks_insert_block(struct file_lock *blocker,
>> - struct file_lock *waiter)
>> + struct file_lock *waiter,
>> + enum conflict conflict(struct file_lock *,
>> + struct file_lock *))
>> {
>> spin_lock(&blocked_lock_lock);
>> - __locks_insert_block(blocker, waiter);
>> + __locks_insert_block(blocker, waiter, conflict);
>> spin_unlock(&blocked_lock_lock);
>> }
>>
>> @@ -1033,7 +1089,7 @@ static int flock_lock_inode(struct inode *inode, struct file_lock *request)
>> if (!(request->fl_flags & FL_SLEEP))
>> goto out;
>> error = FILE_LOCK_DEFERRED;
>> - locks_insert_block(fl, request);
>> + locks_insert_block(fl, request, flock_locks_conflict);
>> goto out;
>> }
>> if (request->fl_flags & FL_ACCESS)
>> @@ -1107,7 +1163,8 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
>> spin_lock(&blocked_lock_lock);
>> if (likely(!posix_locks_deadlock(request, fl))) {
>> error = FILE_LOCK_DEFERRED;
>> - __locks_insert_block(fl, request);
>> + __locks_insert_block(fl, request,
>> + posix_locks_conflict);
>> }
>> spin_unlock(&blocked_lock_lock);
>> goto out;
>> @@ -1581,7 +1638,7 @@ int __break_lease(struct inode *inode, unsigned int mode, unsigned int type)
>> break_time -= jiffies;
>> if (break_time == 0)
>> break_time++;
>> - locks_insert_block(fl, new_fl);
>> + locks_insert_block(fl, new_fl, leases_conflict);
>> trace_break_lease_block(inode, new_fl);
>> spin_unlock(&ctx->flc_lock);
>> percpu_up_read_preempt_enable(&file_rwsem);
>>
>>
>
> --
> Jeff Layton <jlayton@xxxxxxxxxx>
Attachment:
signature.asc
Description: PGP signature
