linux-toradex.git/include/linux/llist.h, branch v4.11-rc3

llist: Clarify comments about when locking is needed

2017-01-23T19:37:13+00:00

llist.h comments are confusing about when locking is needed versus when it
isn't. Clarify these comments by being more descriptive about why locking is
needed for llist_del_first.

Cc: Ingo Molnar 
Cc: Will Deacon 
Cc: Paul McKenney 
Acked-by: Huang Ying 
Acked-by: Mathieu Desnoyers 
Signed-off-by: Joel Fernandes 
Signed-off-by: Paul E. McKenney 
Reviewed-by: Josh Triplett

locking, include/llist: Use linux/atomic.h instead of asm/cmpxchg.h

2015-08-12T09:59:08+00:00

Including an asm/ header directly is best avoided, so use linux/atomic.h
instead of asm/cmpxchg.h in linux/llist.h.

Signed-off-by: Will Deacon 
Signed-off-by: Peter Zijlstra (Intel) 
Cc: Linus Torvalds 
Cc: Peter Zijlstra 
Cc: Thomas Gleixner 
Cc: Waiman.Long@hp.com
Cc: paulmck@linux.vnet.ibm.com
Link: http://lkml.kernel.org/r/1438880084-18856-8-git-send-email-will.deacon@arm.com
Signed-off-by: Ingo Molnar

llists: move llist_reverse_order from raid5 to llist.c

2013-11-15T00:32:22+00:00

Make this useful helper available for other users.

Signed-off-by: Christoph Hellwig 
Reviewed-by: Jan Kara 
Cc: Jens Axboe 
Cc: Neil Brown 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

tty: Use lockless flip buffer free list

2013-07-23T23:47:08+00:00

In preparation for lockless flip buffers, make the flip buffer
free list lockless.

NB: using llist is not the optimal solution, as the driver and
buffer work may contend over the llist head unnecessarily. However,
test measurements indicate this contention is low.

Signed-off-by: Peter Hurley 
Signed-off-by: Greg Kroah-Hartman

llist: llist_add() can use llist_add_batch()

2013-07-13T09:29:32+00:00

llist_add(new, head) can simply use llist_add_batch(new, new, head),
no need to duplicate the code.

This obviously uninlines llist_add() and to me this is a win. But we
can make llist_add_batch() inline if this is desirable, in this case
gcc can notice that new_first == new_last if the caller is llist_add().

Signed-off-by: Oleg Nesterov 
Cc: Al Viro 
Cc: Andrey Vagin 
Cc: "Eric W. Biederman" 
Cc: David Howells 
Cc: Huang Ying 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton 
Signed-off-by: Al Viro

llist: fix/simplify llist_add() and llist_add_batch()

2013-07-13T09:29:24+00:00

1. This is mostly theoretical, but llist_add*() need ACCESS_ONCE().

   Otherwise it is not guaranteed that the first cmpxchg() uses the
   same value for old_entry and new_last->next.

2. These helpers cache the result of cmpxchg() and read the initial
   value of head->first before the main loop. I do not think this
   makes sense. In the likely case cmpxchg() succeeds, otherwise
   it doesn't hurt to reload head->first.

   I think it would be better to simplify the code and simply read
   ->first before cmpxchg().

Signed-off-by: Oleg Nesterov 
Cc: Al Viro 
Cc: Andrey Vagin 
Cc: "Eric W. Biederman" 
Cc: David Howells 
Cc: Huang Ying 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton 
Signed-off-by: Al Viro

Add #includes needed to permit the removal of asm/system.h

2012-03-28T17:30:03+00:00

asm/system.h is a cause of circular dependency problems because it contains
commonly used primitive stuff like barrier definitions and uncommonly used
stuff like switch_to() that might require MMU definitions.

asm/system.h has been disintegrated by this point on all arches into the
following common segments:

 (1) asm/barrier.h

     Moved memory barrier definitions here.

 (2) asm/cmpxchg.h

     Moved xchg() and cmpxchg() here.  #included in asm/atomic.h.

 (3) asm/bug.h

     Moved die() and similar here.

 (4) asm/exec.h

     Moved arch_align_stack() here.

 (5) asm/elf.h

     Moved AT_VECTOR_SIZE_ARCH here.

 (6) asm/switch_to.h

     Moved switch_to() here.

Signed-off-by: David Howells

llist-return-whether-list-is-empty-before-adding-in-llist_add-fix

2011-11-01T00:30:57+00:00

clarify comment

Cc: Huang Ying 
Cc: Mathieu Desnoyers 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

llist: Add back llist_add_batch() and llist_del_first() prototypes

2011-10-11T10:51:22+00:00

Commit 1230db8e1543 ("llist: Make some llist functions inline")
has deleted the definitions, causing problems for (not upstream yet)
code that tries to make use of them.

Signed-off-by: Stephen Rothwell 
Acked-by: Peter Zijlstra 
Cc: Huang Ying 
Cc: David Miller 
Link: http://lkml.kernel.org/r/20111005172528.0d0a8afc65acef7ace22a24e@canb.auug.org.au
Signed-off-by: Ingo Molnar

llist: Remove cpu_relax() usage in cmpxchg loops

2011-10-04T10:44:03+00:00

Initial benchmarks show they're a net loss:

 $ for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor ; do echo performance > $i; done
 $ echo 4096 32000 64 128 > /proc/sys/kernel/sem
 $ ./sembench -t 2048 -w 1900 -o 0

Pre:

 run time 30 seconds 778936 worker burns per second
 run time 30 seconds 912190 worker burns per second
 run time 30 seconds 817506 worker burns per second
 run time 30 seconds 830870 worker burns per second
 run time 30 seconds 845056 worker burns per second

Post:

 run time 30 seconds 905920 worker burns per second
 run time 30 seconds 849046 worker burns per second
 run time 30 seconds 886286 worker burns per second
 run time 30 seconds 822320 worker burns per second
 run time 30 seconds 900283 worker burns per second

So about 4% faster. (!)

cpu_relax() stalls the pipeline, therefore, when used in a tight loop
it has the following benefits:

 - allows SMT siblings to have a go;
 - reduces pressure on the CPU interconnect.

However, cmpxchg loops are unfair and thus have unbounded completion
time, therefore we should avoid getting in such heavily contended
situations where the above benefits make any difference.

A typical cmpxchg loop should not go round more than a handfull of
times at worst, therefore adding extra delays just slows things down.

Since the llist primitives are new, there aren't any bad users yet,
and we should avoid growing them. Heavily contended sites should
generally be better off using the ticket locks for serialization since
they provide bounded completion times (fifo-fair over the cpus).

Signed-off-by: Peter Zijlstra 
Cc: Huang Ying 
Cc: Andrew Morton 
Link: http://lkml.kernel.org/r/1315836358.26517.43.camel@twins
Signed-off-by: Ingo Molnar