linux-kernel - Re: [PATCH] llist: Use try_cmpxchg in llist_add_batch and llist_del

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:   Sun, 14 Aug 2022 18:48:23 -0700
From:   Andrew Morton <akpm@...ux-foundation.org>
To:     Uros Bizjak <ubizjak@...il.com>
Cc:     linux-kernel@...r.kernel.org
Subject: Re: [PATCH] llist: Use try_cmpxchg in llist_add_batch and
 llist_del_first

On Tue, 12 Jul 2022 16:49:17 +0200 Uros Bizjak <ubizjak@...il.com> wrote:

> Use try_cmpxchg instead of cmpxchg (*ptr, old, new) == old in
> llist_add_batch and llist_del_first. x86 CMPXCHG instruction returns
> success in ZF flag, so this change saves a compare after cmpxchg.
> 
> Also, try_cmpxchg implicitly assigns old *ptr value to "old" when
> cmpxchg fails, enabling further code simplifications.
> 
> No functional change intended.

Well this is strange.  Your innocuous little patch:

> --- a/lib/llist.c
> +++ b/lib/llist.c
> @@ -30,7 +30,7 @@ bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
>  
>  	do {
>  		new_last->next = first = READ_ONCE(head->first);
> -	} while (cmpxchg(&head->first, first, new_first) != first);
> +	} while (!try_cmpxchg(&head->first, &first, new_first));
>  
>  	return !first;
>  }
> @@ -52,18 +52,14 @@ EXPORT_SYMBOL_GPL(llist_add_batch);
>   */
>  struct llist_node *llist_del_first(struct llist_head *head)
>  {
> -	struct llist_node *entry, *old_entry, *next;
> +	struct llist_node *entry, *next;
>  
>  	entry = smp_load_acquire(&head->first);
> -	for (;;) {
> +	do {
>  		if (entry == NULL)
>  			return NULL;
> -		old_entry = entry;
>  		next = READ_ONCE(entry->next);
> -		entry = cmpxchg(&head->first, old_entry, next);
> -		if (entry == old_entry)
> -			break;
> -	}
> +	} while (!try_cmpxchg(&head->first, &entry, next));
>  
>  	return entry;
>  }

Does this:

x1:/usr/src/25> size lib/llist.o-before lib/llist.o-after  
   text	   data	    bss	    dec	    hex	filename
    541	     24	      0	    565	    235	lib/llist.o-before
    940	     24	      0	    964	    3c4	lib/llist.o-after

with x86_64 allmodconfig, gcc-11.1.0.

No change with allnoconfig, some bloat with defconfig.

I was too lazy to figure out why this happened, but it'd be great if
someone could investigate.  Something has gone wrong somewhere.

x1:/usr/src/25> scripts/bloat-o-meter lib/llist.o-before lib/llist.o-after 
add/remove: 0/0 grow/shrink: 2/0 up/down: 351/0 (351)
Function                                     old     new   delta
llist_add_batch                              106     286    +180
llist_del_first                              106     277    +171
Total: Before=310, After=661, chg +113.23%

in the two functions you touched.