20 May, 2011
2 commits
-
This is removes the use of software prefetching from the regular list
iterators. We don't want it. If you do want to prefetch in some
iterator of yours, go right ahead. Just don't expect the iterator to do
it, since normally the downsides are bigger than the upsides.It also replaces with , because the
use of LIST_POISON ends up needing it. is sadly not
self-contained, and including prefetch.h just happened to hide that.Suggested by David Miller (networking has a lot of regular lists that
are often empty or a single entry, and prefetching is not going to do
anything but add useless instructions).Acked-by: Ingo Molnar
Acked-by: David S. Miller
Cc: linux-arch@vger.kernel.org
Signed-off-by: Linus Torvalds -
They not only increase the code footprint, they actually make things
slower rather than faster. On internationally acclaimed benchmarks
("make -j16" on an already fully built kernel source tree) the hlist
prefetching slows down the build by up to 1%.(Almost all of it comes from hlist_for_each_entry_rcu() as used by
avc_has_perm_noaudit(), which is very hot due to all the pathname
lookups to see if there is anything to do).The cause seems to be two-fold:
- on at least some Intel cores, prefetch(NULL) ends up with some
microarchitectural stall due to the TLB miss that it incurs. The
hlist case triggers this very commonly, since the NULL pointer is the
last entry in the list.- the prefetch appears to cause more D$ activity, probably because it
prefetches hash list entries that are never actually used (because we
ended the search early due to a hit).Regardless, the numbers clearly say that the implicit prefetching is
simply a bad idea. If some _particular_ user of the hlist iterators
wants to prefetch the next list entry, they can do so themselves
explicitly, rather than depend on all list iterators doing so
implicitly.Acked-by: Ingo Molnar
Acked-by: David S. Miller
Cc: linux-arch@vger.kernel.org
Signed-off-by: Linus Torvalds
19 Feb, 2011
1 commit
-
When list debugging is enabled, we aim to readably show list corruption
errors, and the basic list_add/list_del operations end up having extra
debugging code in them to do some basic validation of the list entries.However, "list_del_init()" and "list_move[_tail]()" ended up avoiding
the debug code due to how they were written. This fixes that.So the _next_ time we have list_move() problems with stale list entries,
we'll hopefully have an easier time finding them..Signed-off-by: Linus Torvalds
26 Oct, 2010
1 commit
-
Make node look as if it was on hlist, with hlist_del()
working correctly. Usable without any locking...Convert a couple of places where we want to do that to
inode->i_hash.Signed-off-by: Al Viro
07 Oct, 2010
1 commit
-
Drop inclusions of asm/system.h from linux/hardirq.h and linux/list.h as
they're no longer required and prevent the M68K arch's IRQ flag handling macros
from being made into inlined functions due to circular dependencies.Signed-off-by: David Howells
Acked-by: Greg Ungerer
Acked-by: Geert Uytterhoeven
07 Jul, 2010
2 commits
-
This allows a list_head (or hlist_head, etc.) to be used from places
that used to be impractical, in particular , which
used to cause include file recursion: includes
, which always includes for the
prefetch macros, as well as , which often includes
directly or indirectly.This avoids a lot of painful workaround hackery on the tile
architecture, where we use a list_head in the thread_struct to chain
together tasks that are activated on a particular hardwall.Signed-off-by: Chris Metcalf
Reviewed-by: Matthew Wilcox
30 Jun, 2010
1 commit
-
list_for_each_entry_safe is not suitable to protect against concurrent
modification of the list. 6754af6 introduced a race in sb walking.list_for_each_entry can use the trick of pinning the current entry in
the list before we drop and retake the lock because it subsequently
follows cur->next. However list_for_each_entry_safe saves n=cur->next
for following before entering the loop body, so when the lock is
dropped, n may be deleted.Signed-off-by: Nick Piggin
Cc: Christoph Hellwig
Cc: John Stultz
Cc: Frank Mayhar
Cc: Al Viro
Signed-off-by: Linus Torvalds
07 Mar, 2010
1 commit
-
The function name must be followed by a space, hypen, space, and a short
description.Signed-off-by: Ben Hutchings
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
16 Jan, 2010
1 commit
-
Bring a new list_rotate_left() helper that rotates a list to
the left. This is useful for codes that need to round roubin
elements which queue priority increases from tail to head.Signed-off-by: Frederic Weisbecker
Acked-by: Peter Zijlstra
Cc: Paul Mackerras
Cc: Ingo Molnar
Cc: Arnaldo Carvalho de Melo
01 Sep, 2008
1 commit
-
Daniel J. Blueman reported:
> =======================================================
> [ INFO: possible circular locking dependency detected ]
> 2.6.27-rc4-224c #1
> -------------------------------------------------------
> hald/4680 is trying to acquire lock:
> (&n->list_lock){++..}, at: [] add_partial+0x26/0x80
>
> but task is already holding lock:
> (&obj_hash[i].lock){++..}, at: []
> debug_object_free+0x5c/0x120We fix it by moving the actual freeing to outside the lock (the lock
now only protects the list).The pool lock is also promoted to irq-safe (suggested by Dan). It's
necessary because free_pool is now called outside the irq disabled
region. So we need to protect against an interrupt handler which calls
debug_object_init().[tglx@linutronix.de: added hlist_move_list helper to avoid looping
through the list twice]Reported-by: Daniel J Blueman
Signed-off-by: Vegard Nossum
Signed-off-by: Thomas Gleixner
09 Aug, 2008
1 commit
-
Fix fatal multi-line kernel-doc error in list.h:
function short description must be on one line.Error(linux-2.6.27-rc2-git3//include/linux/list.h:318): duplicate section name 'Description'
Signed-off-by: Randy Dunlap
Signed-off-by: Linus Torvalds
07 Aug, 2008
2 commits
-
This adds list_cut_position() which lets you cut a list into
two lists given a pivot in the list.Signed-off-by: Luis R. Rodriguez
Signed-off-by: John W. Linville -
If you are using linked lists for queues list_splice() will not do what
you would expect even if you use the elements passed reversed. We need
to handle these differently. We add list_splice_tail() and
list_splice_tail_init().Signed-off-by: Peter Zijlstra
Signed-off-by: Luis R. Rodriguez
Signed-off-by: John W. Linville
26 Jul, 2008
1 commit
-
Remove the conditional surrounding the definition of list_add() from list.h
since, if you define CONFIG_DEBUG_LIST, the definition you will subsequently
pick up from lib/list_debug.c will be absolutely identical, at which point you
can remove that redundant definition from list_debug.c as well.Signed-off-by: Robert P. J. Day
Cc: Dave Jones
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
19 May, 2008
1 commit
-
Move rcu-protected lists from list.h into a new header file rculist.h.
This is done because list are a very used primitive structure all over the
kernel and it's currently impossible to include other header files in this
list.h without creating some circular dependencies.For example, list.h implements rcu-protected list and uses rcu_dereference()
without including rcupdate.h. It actually compiles because users of
rcu_dereference() are macros. Others RCU functions could be used too but
aren't probably because of this.Therefore this patch creates rculist.h which includes rcupdates without to
many changes/troubles.Signed-off-by: Franck Bui-Huu
Acked-by: Paul E. McKenney
Acked-by: Josh Triplett
Signed-off-by: Andrew Morton
Signed-off-by: Ingo Molnar
30 Apr, 2008
1 commit
-
Remove the "#ifdef __KERNEL__" tests from unexported header files in
linux/include whose entire contents are wrapped in that preprocessor
test.Signed-off-by: Robert P. J. Day
Cc: David Woodhouse
Cc: Sam Ravnborg
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
29 Apr, 2008
1 commit
-
Since neither the list_splice() nor __list_splice() routines modify their
first argument, might as well declare them "const".[akpm@linux-foundation.org: coding-style fixes]
Signed-off-by: Robert P. J. Day
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
28 Apr, 2008
1 commit
-
Add list_is_singular() to check a list has just one entry.
list_is_singular() is useful to check whether a list_head which have been
temporarily allocated for listing objects can be released or not.Signed-off-by: Masami Hiramatsu
Cc: Peter Zijlstra
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
21 Apr, 2008
1 commit
-
The RCU iterators used 'rcu_dereference()' on an already-fetched RCU
pointer value, which defeats the whole point of the exercise.When we dereference a pointer protected by RCU, we need to make sure
that we only fetch the value _once_, because if the compiler ends up
re-loading it due to register pressure, the newly reloaded value could
be different from the previously fetched one, and you get inconsistent
results.Cleaned-up, fixed, and the pointless list_for_each_safe_rcu #define
deleted by Paul Kenney.Acked-by: Herbert Xu
Signed-off-by: Paul E. McKenney
Signed-off-by: Linus Torvalds
20 Oct, 2007
1 commit
-
Fix kernel-api docbook contents problems.
docproc: linux-2.6.23-git13/include/asm-x86/unaligned_32.h: No such file or directory
Warning(linux-2.6.23-git13//include/linux/list.h:482): bad line: of list entry
Warning(linux-2.6.23-git13//mm/filemap.c:864): No description found for parameter 'ra'
Warning(linux-2.6.23-git13//block/ll_rw_blk.c:3760): No description found for parameter 'req'
Warning(linux-2.6.23-git13//include/linux/input.h:1077): No description found for parameter 'private'
Warning(linux-2.6.23-git13//include/linux/input.h:1077): No description found for parameter 'cdev'Signed-off-by: Randy Dunlap
Cc: Jens Axboe
Cc: WU Fengguang
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
17 Oct, 2007
1 commit
-
This patch makes shrink_dcache_sb consistent with dentry pruning policy.
On the first pass we iterate over dentry unused list and prepare some
dentries for removal.However, since the existing code moves evicted dentries to the beginning of
the LRU it can happen that fresh dentries from other superblocks will be
inserted *before* our dentries.This can result in significant slowdown of shrink_dcache_sb(). Moreover,
for virtual filesystems like unionfs which can call dput() during dentries
kill existing code results in O(n^2) complexity.We observed 2 minutes shrink_dcache_sb() with only 35000 dentries.
To avoid this effects we propose to isolate sb dentries at the end
of LRU list.Signed-off-by: Denis V. Lunev
Signed-off-by: Kirill Korotaev
Signed-off-by: Andrey Mirkin
Cc: Neil Brown
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
11 Oct, 2007
1 commit
-
I proposed introducing a list_for_each_entry_continue_reverse macro
to be used in setup_net() when unrolling the failed ->init callback.Here is the macro and some more cleanup in the setup_net() itself
to remove one variable from the stack :) The same thing is for the
cleanup_net() - the existing list_for_each_entry_reverse() is used.Minor, but the code looks nicer.
Signed-off-by: Pavel Emelyanov
Acked-by: "Eric W. Biederman"
Signed-off-by: David S. Miller
13 May, 2007
1 commit
-
Adding tabs where spaces currently are.
Signed-off-by: Daniel Walker
Signed-off-by: Linus Torvalds
09 May, 2007
1 commit
-
There are many places in the kernel where the construction like
foo = list_entry(head->next, struct foo_struct, list);
are used.
The code might look more descriptive and neat if using the macrolist_first_entry(head, type, member) \
list_entry((head)->next, type, member)Here is the macro itself and the examples of its usage in the generic code.
If it will turn out to be useful, I can prepare the set of patches to
inject in into arch-specific code, drivers, networking, etc.Signed-off-by: Pavel Emelianov
Signed-off-by: Kirill Korotaev
Cc: Randy Dunlap
Cc: Andi Kleen
Cc: Zach Brown
Cc: Davide Libenzi
Cc: John McCutchan
Cc: Thomas Gleixner
Cc: Ingo Molnar
Cc: john stultz
Cc: Ram Pai
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Feb, 2007
2 commits
-
A variety of (mostly) innocuous fixes to the embedded kernel-doc content in
source files, including:* make multi-line initial descriptions single line
* denote some function names, constants and structs as such
* change erroneous opening '/*' to '/**' in a few places
* reword some text for claritySigned-off-by: Robert P. J. Day
Cc: "Randy.Dunlap"
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
This patch is in support of the IPMI driver. I have tested this with the
IPMI driver changes coming in the next patch.Add a list_splice_init_rcu() function to splice an RCU-protected list into
another list. This takes the sync function as an argument, so one would do
something like:INIT_LIST_HEAD(&list);
list_splice_init_rcu(&source, &dest, synchronize_rcu);The idea being to keep the RCU API proliferation down to a dull roar.
[akpm@osdl.org: build fix]
Signed-off-by: Paul E. McKenney
Signed-off-by: Corey Minyard
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
27 Jan, 2007
1 commit
-
Fix a number of kernel-doc entries for header files in include/linux by
making sure they begin with the appropriate '/**' notation and use @var
notation.Signed-off-by: Robert P. J. Day
Signed-off-by: Randy Dunlap
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
30 Sep, 2006
1 commit
-
Signed-off-by: Dave Jones
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
15 Jul, 2006
1 commit
-
Add another list utility function to check for last element in a list.
Signed-off-by: Shailabh Nagar
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
28 Jun, 2006
1 commit
-
Localize poison values into one header file for better documentation and
easier/quicker debugging and so that the same values won't be used for
multiple purposes.Use these constants in core arch., mm, driver, and fs code.
Signed-off-by: Randy Dunlap
Acked-by: Matt Mackall
Cc: Paul Mackerras
Cc: Benjamin Herrenschmidt
Cc: "David S. Miller"
Cc: Andi Kleen
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
26 Jun, 2006
2 commits
-
Use loop "cursor" instead of loop "counter" for list iterator descriptions.
They are not counters, they are pointers or positions.Signed-off-by: Randy Dunlap
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
kernel-doc:
Put all short function descriptions on one line or if they are too long,
omit the short description & add a Description: section for them.Change some list iterator descriptions to use "current" point instead of
"existing" point.Signed-off-by: Randy Dunlap
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
23 Jun, 2006
1 commit
-
list_replace() is similar to list_replace_rcu(), but unlike
list_replace_rcu() itcould be used when list_empty(old) == 1
doesn't use barriers
Signed-off-by: Oleg Nesterov
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
30 Apr, 2006
1 commit
-
Use hlist_unhashed() rather than accessing inside data structure.
Signed-off-by: Akinobu Mita
Signed-off-by: Andrew Morton
Signed-off-by: David S. Miller
21 Mar, 2006
2 commits
-
For iterating over list of given type continuing from existing point.
Signed-off-by: Arnaldo Carvalho de Melo
Signed-off-by: David S. Miller -
For iterate over list of given type from existing point safe against removal of
list entry.Signed-off-by: Arnaldo Carvalho de Melo
Signed-off-by: David S. Miller
04 Feb, 2006
1 commit
-
I noticed that list.h init functions were evaluating macro arguments
multiple times and thought it might be nice to protect the unsuspecting
caller. Converting the macros to inline functions seems to reduce code
size, too. A i386 defconfig build with gcc 3.3.3 from fc4:text data bss dec hex filename
3573148 565664 188828 4327640 4208d8 vmlinux.before
3572177 565664 188828 4326669 42050d vmlinuxadd/remove: 0/0 grow/shrink: 11/144 up/down: 88/-1016 (-928)
There was no difference in checkstack output.
Signed-off-by: Zach Brown
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
11 Jan, 2006
1 commit
-
Add list_for_each_entry_safe_reverse() to linux/list.h
This is needed by unmerged cachefs and be an as-yet-unreviewed
device_shutdown() fix.Signed-off-by: David Howells
Cc: Patrick Mochel
Cc: Greg KH
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
13 Dec, 2005
1 commit
-
Add list_replace_rcu: replace old entry by new one.
Signed-off-by: Paul E. McKenney
Signed-off-by: Ingo Molnar
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds