linux-kernel - Re: [PATCH-tip v7 11/20] locking/rwsem: Wake up almost all readers in wait queue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1e5e939f-3725-14d9-feec-aabb63998406@redhat.com>
Date:   Fri, 3 May 2019 13:15:22 -0400
From:   Waiman Long <longman@...hat.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Ingo Molnar <mingo@...hat.com>, Will Deacon <will.deacon@....com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Borislav Petkov <bp@...en8.de>,
        "H. Peter Anvin" <hpa@...or.com>, linux-kernel@...r.kernel.org,
        x86@...nel.org, Davidlohr Bueso <dave@...olabs.net>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Tim Chen <tim.c.chen@...ux.intel.com>,
        huang ying <huang.ying.caritas@...il.com>
Subject: Re: [PATCH-tip v7 11/20] locking/rwsem: Wake up almost all readers in
 wait queue

On 5/3/19 12:51 PM, Peter Zijlstra wrote:
> On Sun, Apr 28, 2019 at 05:25:48PM -0400, Waiman Long wrote:
>> When the front of the wait queue is a reader, other readers
>> immediately following the first reader will also be woken up at the
>> same time. However, if there is a writer in between. Those readers
>> behind the writer will not be woken up.
>> @@ -345,13 +359,20 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
>>  	 * 2) For each waiters in the new list, clear waiter->task and
>>  	 *    put them into wake_q to be woken up later.
>>  	 */
>> -	list_for_each_entry(waiter, &sem->wait_list, list) {
>> +	INIT_LIST_HEAD(&wlist);
>> +	list_for_each_entry_safe(waiter, tmp, &sem->wait_list, list) {
>>  		if (waiter->type == RWSEM_WAITING_FOR_WRITE)
>> -			break;
>> +			continue;
>>  
>>  		woken++;
>> +		list_move_tail(&waiter->list, &wlist);
>> +
>> +		/*
>> +		 * Limit # of readers that can be woken up per wakeup call.
>> +		 */
>> +		if (woken >= MAX_READERS_WAKEUP)
>> +			break;
>>  	}
>> -	list_cut_before(&wlist, &sem->wait_list, &waiter->list);
>>  
>>  	adjustment = woken * RWSEM_READER_BIAS - adjustment;
>>  	lockevent_cond_inc(rwsem_wake_reader, woken);
> An idea for later; maybe we can simplify this by playing silly games
> with the queueing.
>
> Writers: always list_add_tail()
> Readers: keep a pointer to first_reader in the queue;
> 	 when NULL; list_add_tail() and set
> 	 otherwise: list_add_tail(, first_reader);
>
> Possily also keep a count of first_reader list size, and if 'big' reset
> first_reader.
>
> That way we never have to skip over writers.
>
Yes, that can work. However, that will require adding one more pointer
to the rw_semaphore structure. The performance gain with this
optimization may not justify increasing the size of the structure by 4/8
bytes.

Cheers,
Longman