user/sven/linux.git/include/linux/list.h, branch v3.3.5

list: remove prefetching from regular list iterators

2011-05-19T21:15:29Z

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

hlist: remove software prefetching in hlist iterators

2011-05-19T20:50:07Z

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

Expand CONFIG_DEBUG_LIST to several other list operations

2011-02-18T19:32:28Z

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

list.h: new helper - hlist_add_fake()

2010-10-26T01:24:15Z

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

Drop a couple of unnecessary asm/system.h inclusions

2010-10-07T13:08:53Z

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

Merge branch 'master' into for-linus

2010-07-06T17:45:24Z

Move list types from to .

2010-07-06T17:33:54Z

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

fs: fix superblock iteration race

2010-06-29T17:38:22Z

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

lib: fix first line of kernel-doc for a few functions

2010-03-06T19:26:35Z

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

list: Introduce list_rotate_left()

2010-01-16T11:29:32Z

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