linux-kernel - Re: [PATCH] osq_lock: fix osq

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]

Date:   Mon, 7 Aug 2017 10:36:18 +0530
From:   Prateek Sood <prsood@...eaurora.org>
To:     peterz@...radead.org, mingo@...hat.com
Cc:     sramana@...eaurora.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] osq_lock: fix osq_lock queue corruption

On 07/31/2017 10:54 PM, Prateek Sood wrote:
> Fix ordering of link creation between node->prev and prev->next in
> osq_lock(). A case in which the status of optimistic spin queue is
> CPU6->CPU2 in which CPU6 has acquired the lock.
> 
>         tail
>           v
>   ,-. <- ,-.
>   |6|    |2|
>   `-' -> `-'
> 
> At this point if CPU0 comes in to acquire osq_lock, it will update the
> tail count.
> 
>   CPU2			CPU0
>   ----------------------------------
> 
> 				       tail
> 				         v
> 			  ,-. <- ,-.    ,-.
> 			  |6|    |2|    |0|
> 			  `-' -> `-'    `-'
> 
> After tail count update if CPU2 starts to unqueue itself from
> optimistic spin queue, it will find updated tail count with CPU0 and
> update CPU2 node->next to NULL in osq_wait_next().
> 
>   unqueue-A
> 
> 	       tail
> 	         v
>   ,-. <- ,-.    ,-.
>   |6|    |2|    |0|
>   `-'    `-'    `-'
> 
>   unqueue-B
> 
>   ->tail != curr && !node->next
> 
> If reordering of following stores happen then
> prev->next where prev being CPU2 would be updated to point to CPU0 node:
> 
> 				       tail
> 				         v
> 			  ,-. <- ,-.    ,-.
> 			  |6|    |2|    |0|
> 			  `-' -> `-' -> `-'
> 
>   osq_wait_next()
>     node->next <- 0
>     xchg(node->next, NULL)
> 
> 	       tail
> 	         v
>   ,-. <- ,-.    ,-.
>   |6|    |2|    |0|
>   `-'    `-'    `-'
> 
>   unqueue-C
> 
> At this point if next instruction
> WRITE_ONCE(next->prev, prev);
> in CPU2 path is committed before the update of CPU0 node->prev = prev then
> CPU0 node->prev will point to CPU6 node.
> 
> 	       tail
>     V----------. v
>   ,-. <- ,-.    ,-.
>   |6|    |2|    |0|
>   `-'    `-'    `-'
>      `----------^
> 
> At this point if CPU0 path's node->prev = prev is committed resulting
> in change of CPU0 prev back to CPU2 node. CPU2 node->next is NULL
> currently,
> 
> 				       tail
> 			                 v
> 			  ,-. <- ,-. <- ,-.
> 			  |6|    |2|    |0|
> 			  `-'    `-'    `-'
> 			     `----------^
> 
> so if CPU0 gets into unqueue path of osq_lock it will keep spinning
> in infinite loop as condition prev->next == node will never be true.
> 
> Signed-off-by: Prateek Sood <prsood@...eaurora.org>
> ---
>  kernel/locking/osq_lock.c | 13 +++++++++++++
>  1 file changed, 13 insertions(+)
> 
> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> index a316794..9f4afa3 100644
> --- a/kernel/locking/osq_lock.c
> +++ b/kernel/locking/osq_lock.c
> @@ -109,6 +109,19 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>  
>  	prev = decode_cpu(old);
>  	node->prev = prev;
> +
> +	/*
> +	 * osq_lock()			unqueue
> +	 *
> +	 * node->prev = prev            osq_wait_next()
> +	 * WMB                          MB
> +	 * prev->next = node            next->prev = prev //unqueue-C
> +	 *
> +	 * Here 'node->prev' and 'next->prev' are the same variable and we need
> +	 * to ensure these stores happen in-order to avoid corrupting the list.
> +	 */
> +	smp_wmb();
> +
>  	WRITE_ONCE(prev->next, node);
>  
>  	/*
> 

Hi Peter,

I have updated the change log and comments in code.

-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation
Center, Inc., is a member of Code Aurora Forum, a Linux Foundation
Collaborative Project