Skip to content

K
Kernel

openeuler / Kernel
1 年多 前同步成功

通知 8
Star 0
Fork 0
K
Kernel
切换分支/标签
  1. 21 5月, 2016 8 次提交
  3. 18 3月, 2016 5 次提交
    • M
      radix_tree: add radix_tree_dump · 7cf19af4
      由 Matthew Wilcox 提交于 
      This is debug code which is #if 0 out.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Matthew Wilcox <willy@linux.intel.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      7cf19af4
    • M
      radix_tree: add support for multi-order entries · e6145236
      由 Matthew Wilcox 提交于 
      With huge pages, it is convenient to have the radix tree be able to
return an entry that covers multiple indices.  Previous attempts to deal
with the problem have involved inserting N duplicate entries, which is a
waste of memory and leads to problems trying to handle aliased tags, or
probing the tree multiple times to find alternative entries which might
cover the requested index.

This approach inserts one canonical entry into the tree for a given
range of indices, and may also insert other entries in order to ensure
that lookups find the canonical entry.

This solution only tolerates inserting powers of two that are greater
than the fanout of the tree.  If we wish to expand the radix tree's
abilities to support large-ish pages that is less than the fanout at the
penultimate level of the tree, then we would need to add one more step
in lookup to ensure that any sibling nodes in the final level of the
tree are dereferenced and we return the canonical entry that they
reference.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Matthew Wilcox <willy@linux.intel.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      e6145236
    • M
      radix_tree: loop based on shift count, not height · 0070e28d
      由 Matthew Wilcox 提交于 
      When we introduce entries that can cover multiple indices, we will need
to stop in __radix_tree_create based on the shift, not the height.
Split out for ease of bisect.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Matthew Wilcox <willy@linux.intel.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      0070e28d
    • M
      radix_tree: tag all internal tree nodes as indirect pointers · 339e6353
      由 Matthew Wilcox 提交于 
      Set the 'indirect_ptr' bit on all the pointers to internal nodes, not
just on the root node.  This enables the following patches to support
multi-order entries in the radix tree.  This patch is split out for ease
of bisection.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Matthew Wilcox <willy@linux.intel.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      339e6353
    • V
      radix-tree: account radix_tree_node to memory cgroup · 58e698af
      由 Vladimir Davydov 提交于 
      Allocation of radix_tree_node objects can be easily triggered from
userspace, so we should account them to memory cgroup.  Besides, we need
them accounted for making shadow node shrinker per memcg (see
mm/workingset.c).

A tricky thing about accounting radix_tree_node objects is that they are
mostly allocated through radix_tree_preload(), so we can't just set
SLAB_ACCOUNT for radix_tree_node_cachep - that would likely result in a
lot of unrelated cgroups using objects from each other's caches.

One way to overcome this would be making radix tree preloads per memcg,
but that would probably look cumbersome and overcomplicated.

Instead, we make radix_tree_node_alloc() first try to allocate from the
cache with __GFP_ACCOUNT, no matter if the caller has preloaded or not,
and only if it fails fall back on using per cpu preloads.  This should
make most allocations accounted.
Signed-off-by: NVladimir Davydov <vdavydov@virtuozzo.com>
Acked-by: NJohannes Weiner <hannes@cmpxchg.org>
Cc: Michal Hocko <mhocko@kernel.org>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      58e698af
  5. 04 2月, 2016 1 次提交
    • M
      radix-tree: fix race in gang lookup · 46437f9a
      由 Matthew Wilcox 提交于 
      If the indirect_ptr bit is set on a slot, that indicates we need to redo
the lookup.  Introduce a new function radix_tree_iter_retry() which
forces the loop to retry the lookup by setting 'slot' to NULL and
turning the iterator back to point at the problematic entry.

This is a pretty rare problem to hit at the moment; the lookup has to
race with a grow of the radix tree from a height of 0.  The consequences
of hitting this race are that gang lookup could return a pointer to a
radix_tree_node instead of a pointer to whatever the user had inserted
in the tree.

Fixes: cebbd29e ("radix-tree: rewrite gang lookup using iterator")
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Ohad Ben-Cohen <ohad@wizery.com>
Cc: Konstantin Khlebnikov <khlebnikov@openvz.org>
Cc: <stable@vger.kernel.org>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      46437f9a
  7. 07 11月, 2015 1 次提交
    • M
      mm, page_alloc: distinguish between being unable to sleep, unwilling to sleep... · d0164adc
      由 Mel Gorman 提交于 
      mm, page_alloc: distinguish between being unable to sleep, unwilling to sleep and avoiding waking kswapd

__GFP_WAIT has been used to identify atomic context in callers that hold
spinlocks or are in interrupts.  They are expected to be high priority and
have access one of two watermarks lower than "min" which can be referred
to as the "atomic reserve".  __GFP_HIGH users get access to the first
lower watermark and can be called the "high priority reserve".

Over time, callers had a requirement to not block when fallback options
were available.  Some have abused __GFP_WAIT leading to a situation where
an optimisitic allocation with a fallback option can access atomic
reserves.

This patch uses __GFP_ATOMIC to identify callers that are truely atomic,
cannot sleep and have no alternative.  High priority users continue to use
__GFP_HIGH.  __GFP_DIRECT_RECLAIM identifies callers that can sleep and
are willing to enter direct reclaim.  __GFP_KSWAPD_RECLAIM to identify
callers that want to wake kswapd for background reclaim.  __GFP_WAIT is
redefined as a caller that is willing to enter direct reclaim and wake
kswapd for background reclaim.

This patch then converts a number of sites

o __GFP_ATOMIC is used by callers that are high priority and have memory
  pools for those requests. GFP_ATOMIC uses this flag.

o Callers that have a limited mempool to guarantee forward progress clear
  __GFP_DIRECT_RECLAIM but keep __GFP_KSWAPD_RECLAIM. bio allocations fall
  into this category where kswapd will still be woken but atomic reserves
  are not used as there is a one-entry mempool to guarantee progress.

o Callers that are checking if they are non-blocking should use the
  helper gfpflags_allow_blocking() where possible. This is because
  checking for __GFP_WAIT as was done historically now can trigger false
  positives. Some exceptions like dm-crypt.c exist where the code intent
  is clearer if __GFP_DIRECT_RECLAIM is used instead of the helper due to
  flag manipulations.

o Callers that built their own GFP flags instead of starting with GFP_KERNEL
  and friends now also need to specify __GFP_KSWAPD_RECLAIM.

The first key hazard to watch out for is callers that removed __GFP_WAIT
and was depending on access to atomic reserves for inconspicuous reasons.
In some cases it may be appropriate for them to use __GFP_HIGH.

The second key hazard is callers that assembled their own combination of
GFP flags instead of starting with something like GFP_KERNEL.  They may
now wish to specify __GFP_KSWAPD_RECLAIM.  It's almost certainly harmless
if it's missed in most cases as other activity will wake kswapd.
Signed-off-by: NMel Gorman <mgorman@techsingularity.net>
Acked-by: NVlastimil Babka <vbabka@suse.cz>
Acked-by: NMichal Hocko <mhocko@suse.com>
Acked-by: NJohannes Weiner <hannes@cmpxchg.org>
Cc: Christoph Lameter <cl@linux.com>
Cc: David Rientjes <rientjes@google.com>
Cc: Vitaly Wool <vitalywool@gmail.com>
Cc: Rik van Riel <riel@redhat.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      d0164adc
  9. 26 6月, 2015 1 次提交
  11. 19 5月, 2015 1 次提交
    • F
      sched/preempt: Merge preempt_mask.h into preempt.h · 92cf2118
      由 Frederic Weisbecker 提交于 
      preempt_mask.h defines all the preempt_count semantics and related
symbols: preempt, softirq, hardirq, nmi, preempt active, need resched,
etc...

preempt.h defines the accessors and mutators of preempt_count.

But there is a messy dependency game around those two header files:

	* preempt_mask.h includes preempt.h in order to access preempt_count()

	* preempt_mask.h defines all preempt_count semantic and symbols
	  except PREEMPT_NEED_RESCHED that is needed by asm/preempt.h
	  Thus we need to define it from preempt.h, right before including
	  asm/preempt.h, instead of defining it to preempt_mask.h with the
	  other preempt_count symbols. Therefore the preempt_count semantics
	  happen to be spread out.

	* We plan to introduce preempt_active_[enter,exit]() to consolidate
	  preempt_schedule*() code. But we'll need to access both preempt_count
	  mutators (preempt_count_add()) and preempt_count symbols
	  (PREEMPT_ACTIVE, PREEMPT_OFFSET). The usual place to define preempt
	  operations is in preempt.h but then we'll need symbols in
	  preempt_mask.h which already includes preempt.h. So we end up with
	  a ressource circle dependency.

Lets merge preempt_mask.h into preempt.h to solve these dependency issues.
This way we gather semantic symbols and operation definition of
preempt_count in a single file.

This is a dumb copy-paste merge. Further merge re-arrangments are
performed in a subsequent patch to ease review.
Signed-off-by: NFrederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: NPeter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1431441711-29753-2-git-send-email-fweisbec@gmail.comSigned-off-by: NIngo Molnar <mingo@kernel.org>
      92cf2118
  13. 13 2月, 2015 1 次提交
  15. 07 6月, 2014 1 次提交
  17. 05 6月, 2014 2 次提交
  19. 04 4月, 2014 4 次提交
    • J
      mm: keep page cache radix tree nodes in check · 449dd698
      由 Johannes Weiner 提交于 
      Previously, page cache radix tree nodes were freed after reclaim emptied
out their page pointers.  But now reclaim stores shadow entries in their
place, which are only reclaimed when the inodes themselves are
reclaimed.  This is problematic for bigger files that are still in use
after they have a significant amount of their cache reclaimed, without
any of those pages actually refaulting.  The shadow entries will just
sit there and waste memory.  In the worst case, the shadow entries will
accumulate until the machine runs out of memory.

To get this under control, the VM will track radix tree nodes
exclusively containing shadow entries on a per-NUMA node list.  Per-NUMA
rather than global because we expect the radix tree nodes themselves to
be allocated node-locally and we want to reduce cross-node references of
otherwise independent cache workloads.  A simple shrinker will then
reclaim these nodes on memory pressure.

A few things need to be stored in the radix tree node to implement the
shadow node LRU and allow tree deletions coming from the list:

1. There is no index available that would describe the reverse path
   from the node up to the tree root, which is needed to perform a
   deletion.  To solve this, encode in each node its offset inside the
   parent.  This can be stored in the unused upper bits of the same
   member that stores the node's height at no extra space cost.

2. The number of shadow entries needs to be counted in addition to the
   regular entries, to quickly detect when the node is ready to go to
   the shadow node LRU list.  The current entry count is an unsigned
   int but the maximum number of entries is 64, so a shadow counter
   can easily be stored in the unused upper bits.

3. Tree modification needs tree lock and tree root, which are located
   in the address space, so store an address_space backpointer in the
   node.  The parent pointer of the node is in a union with the 2-word
   rcu_head, so the backpointer comes at no extra cost as well.

4. The node needs to be linked to an LRU list, which requires a list
   head inside the node.  This does increase the size of the node, but
   it does not change the number of objects that fit into a slab page.

[akpm@linux-foundation.org: export the right function]
Signed-off-by: NJohannes Weiner <hannes@cmpxchg.org>
Reviewed-by: NRik van Riel <riel@redhat.com>
Reviewed-by: NMinchan Kim <minchan@kernel.org>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Bob Liu <bob.liu@oracle.com>
Cc: Christoph Hellwig <hch@infradead.org>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Greg Thelen <gthelen@google.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Jan Kara <jack@suse.cz>
Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
Cc: Luigi Semenzato <semenzato@google.com>
Cc: Mel Gorman <mgorman@suse.de>
Cc: Metin Doslu <metin@citusdata.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Ozgun Erdogan <ozgun@citusdata.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Roman Gushchin <klamm@yandex-team.ru>
Cc: Ryan Mallon <rmallon@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      449dd698
    • J
      lib: radix_tree: tree node interface · 139e5616
      由 Johannes Weiner 提交于 
      Make struct radix_tree_node part of the public interface and provide API
functions to create, look up, and delete whole nodes.  Refactor the
existing insert, look up, delete functions on top of these new node
primitives.

This will allow the VM to track and garbage collect page cache radix
tree nodes.

[sasha.levin@oracle.com: return correct error code on insertion failure]
Signed-off-by: NJohannes Weiner <hannes@cmpxchg.org>
Reviewed-by: NRik van Riel <riel@redhat.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Bob Liu <bob.liu@oracle.com>
Cc: Christoph Hellwig <hch@infradead.org>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Greg Thelen <gthelen@google.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Jan Kara <jack@suse.cz>
Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
Cc: Luigi Semenzato <semenzato@google.com>
Cc: Mel Gorman <mgorman@suse.de>
Cc: Metin Doslu <metin@citusdata.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Ozgun Erdogan <ozgun@citusdata.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Roman Gushchin <klamm@yandex-team.ru>
Cc: Ryan Mallon <rmallon@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: NSasha Levin <sasha.levin@oracle.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      139e5616
    • J
      mm: filemap: move radix tree hole searching here · e7b563bb
      由 Johannes Weiner 提交于 
      The radix tree hole searching code is only used for page cache, for
example the readahead code trying to get a a picture of the area
surrounding a fault.

It sufficed to rely on the radix tree definition of holes, which is
"empty tree slot".  But this is about to change, though, as shadow page
descriptors will be stored in the page cache after the actual pages get
evicted from memory.

Move the functions over to mm/filemap.c and make them native page cache
operations, where they can later be adapted to handle the new definition
of "page cache hole".
Signed-off-by: NJohannes Weiner <hannes@cmpxchg.org>
Reviewed-by: NRik van Riel <riel@redhat.com>
Reviewed-by: NMinchan Kim <minchan@kernel.org>
Acked-by: NMel Gorman <mgorman@suse.de>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Bob Liu <bob.liu@oracle.com>
Cc: Christoph Hellwig <hch@infradead.org>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Greg Thelen <gthelen@google.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Jan Kara <jack@suse.cz>
Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
Cc: Luigi Semenzato <semenzato@google.com>
Cc: Metin Doslu <metin@citusdata.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Ozgun Erdogan <ozgun@citusdata.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Roman Gushchin <klamm@yandex-team.ru>
Cc: Ryan Mallon <rmallon@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      e7b563bb
    • J
      lib: radix-tree: add radix_tree_delete_item() · 53c59f26
      由 Johannes Weiner 提交于 
      Provide a function that does not just delete an entry at a given index,
but also allows passing in an expected item.  Delete only if that item
is still located at the specified index.

This is handy when lockless tree traversals want to delete entries as
well because they don't have to do an second, locked lookup to verify
the slot has not changed under them before deleting the entry.
Signed-off-by: NJohannes Weiner <hannes@cmpxchg.org>
Reviewed-by: NMinchan Kim <minchan@kernel.org>
Reviewed-by: NRik van Riel <riel@redhat.com>
Acked-by: NMel Gorman <mgorman@suse.de>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Bob Liu <bob.liu@oracle.com>
Cc: Christoph Hellwig <hch@infradead.org>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Greg Thelen <gthelen@google.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Jan Kara <jack@suse.cz>
Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
Cc: Luigi Semenzato <semenzato@google.com>
Cc: Metin Doslu <metin@citusdata.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Ozgun Erdogan <ozgun@citusdata.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Roman Gushchin <klamm@yandex-team.ru>
Cc: Ryan Mallon <rmallon@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      53c59f26
  21. 04 3月, 2014 1 次提交
    • H
      lib/radix-tree.c: swapoff tmpfs radix_tree: remember to rcu_read_unlock · 5f30fc94
      由 Hugh Dickins 提交于 
      Running fsx on tmpfs with concurrent memhog-swapoff-swapon, lots of

  BUG: sleeping function called from invalid context at kernel/fork.c:606
  in_atomic(): 0, irqs_disabled(): 0, pid: 1394, name: swapoff
  1 lock held by swapoff/1394:
   #0:  (rcu_read_lock){.+.+.+}, at: [<ffffffff812520a1>] radix_tree_locate_item+0x1f/0x2b6

followed by

  ================================================
  [ BUG: lock held when returning to user space! ]
  3.14.0-rc1 #3 Not tainted
  ------------------------------------------------
  swapoff/1394 is leaving the kernel with locks still held!
  1 lock held by swapoff/1394:
   #0:  (rcu_read_lock){.+.+.+}, at: [<ffffffff812520a1>] radix_tree_locate_item+0x1f/0x2b6

after which the system recovered nicely.

Whoops, I long ago forgot the rcu_read_unlock() on one unlikely branch.

Fixes e504f3fd ("tmpfs radix_tree: locate_item to speed up swapoff")
Signed-off-by: NHugh Dickins <hughd@google.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      5f30fc94
  23. 12 9月, 2013 1 次提交
    • J
      lib/radix-tree.c: make radix_tree_node_alloc() work correctly within interrupt · 5e4c0d97
      由 Jan Kara 提交于 
      With users of radix_tree_preload() run from interrupt (block/blk-ioc.c is
one such possible user), the following race can happen:

radix_tree_preload()
...
radix_tree_insert()
  radix_tree_node_alloc()
    if (rtp->nr) {
      ret = rtp->nodes[rtp->nr - 1];
<interrupt>
...
radix_tree_preload()
...
radix_tree_insert()
  radix_tree_node_alloc()
    if (rtp->nr) {
      ret = rtp->nodes[rtp->nr - 1];

And we give out one radix tree node twice.  That clearly results in radix
tree corruption with different results (usually OOPS) depending on which
two users of radix tree race.

We fix the problem by making radix_tree_node_alloc() always allocate fresh
radix tree nodes when in interrupt.  Using preloading when in interrupt
doesn't make sense since all the allocations have to be atomic anyway and
we cannot steal nodes from process-context users because some users rely
on radix_tree_insert() succeeding after radix_tree_preload().
in_interrupt() check is somewhat ugly but we cannot simply key off passed
gfp_mask as that is acquired from root_gfp_mask() and thus the same for
all preload users.

Another part of the fix is to avoid node preallocation in
radix_tree_preload() when passed gfp_mask doesn't allow waiting.  Again,
preallocation in such case doesn't make sense and when preallocation would
happen in interrupt we could possibly leak some allocated nodes.  However,
some users of radix_tree_preload() require following radix_tree_insert()
to succeed.  To avoid unexpected effects for these users,
radix_tree_preload() only warns if passed gfp mask doesn't allow waiting
and we provide a new function radix_tree_maybe_preload() for those users
which get different gfp mask from different call sites and which are
prepared to handle radix_tree_insert() failure.
Signed-off-by: NJan Kara <jack@suse.cz>
Cc: Jens Axboe <jaxboe@fusionio.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      5e4c0d97
  25. 06 6月, 2012 1 次提交
  27. 30 5月, 2012 1 次提交
  29. 29 3月, 2012 2 次提交
    • K
      radix-tree: rewrite gang lookup using iterator · cebbd29e
      由 Konstantin Khlebnikov 提交于 
      Rewrite radix_tree_gang_lookup_* functions using the new radix-tree
iterator.
Signed-off-by: NKonstantin Khlebnikov <khlebnikov@openvz.org>
Tested-by: NHugh Dickins <hughd@google.com>
Cc: Christoph Hellwig <hch@lst.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      cebbd29e
    • K
      radix-tree: introduce bit-optimized iterator · 78c1d784
      由 Konstantin Khlebnikov 提交于 
      A series of radix tree cleanups, and usage of them in the core pagecache
code.

Micro-benchmark:

lookup 14 slots (typical page-vector size)
in radix-tree there earch <step> slot filled and tagged
before/after - nsec per full scan through tree

* Intel Sandy Bridge i7-2620M 4Mb L3
New code always faster

* AMD Athlon 6000+ 2x1Mb L2, without L3
New code generally faster,
Minor degradation (marked with "*") for huge sparse trees

* i386 on Sandy Bridge
New code faster for common cases: tagged and dense trees.
Some degradations for non-tagged lookup on sparse trees.

Ideally, there might help __ffs() analog for searching first non-zero
long element in array, gcc sometimes cannot optimize this loop corretly.

Numbers:

CPU: Intel Sandy Bridge i7-2620M 4Mb L3

radix-tree with 1024 slots:

tagged lookup

step  1      before  7156        after  3613
step  2      before  5399        after  2696
step  3      before  4779        after  1928
step  4      before  4456        after  1429
step  5      before  4292        after  1213
step  6      before  4183        after  1052
step  7      before  4157        after  951
step  8      before  4016        after  812
step  9      before  3952        after  851
step  10     before  3937        after  732
step  11     before  4023        after  709
step  12     before  3872        after  657
step  13     before  3892        after  633
step  14     before  3720        after  591
step  15     before  3879        after  578
step  16     before  3561        after  513

normal lookup

step  1      before  4266       after  3301
step  2      before  2695       after  2129
step  3      before  2083       after  1712
step  4      before  1801       after  1534
step  5      before  1628       after  1313
step  6      before  1551       after  1263
step  7      before  1475       after  1185
step  8      before  1432       after  1167
step  9      before  1373       after  1092
step  10     before  1339       after  1134
step  11     before  1292       after  1056
step  12     before  1319       after  1030
step  13     before  1276       after  1004
step  14     before  1256       after  987
step  15     before  1228       after  992
step  16     before  1247       after  999

radix-tree with 1024*1024*128 slots:

tagged lookup

step  1      before  1086102841  after  674196409
step  2      before  816839155   after  498138306
step  7      before  599728907   after  240676762
step  15     before  555729253   after  185219677
step  63     before  606637748   after  128585664
step  64     before  608384432   after  102945089
step  65     before  596987114   after  123996019
step  128    before  304459225   after  56783056
step  256    before  158846855   after  31232481
step  512    before  86085652    after  18950595
step  12345  before  6517189     after  1674057

normal lookup

step  1      before  626064869  after  544418266
step  2      before  418809975  after  336321473
step  7      before  242303598  after  207755560
step  15     before  208380563  after  176496355
step  63     before  186854206  after  167283638
step  64     before  176188060  after  170143976
step  65     before  185139608  after  167487116
step  128    before  88181865   after  86913490
step  256    before  45733628   after  45143534
step  512    before  24506038   after  23859036
step  12345  before  2177425    after  2018662

* AMD Athlon 6000+ 2x1Mb L2, without L3

radix-tree with 1024 slots:

tag-lookup

step  1      before  8164        after  5379
step  2      before  5818        after  5581
step  3      before  4959        after  4213
step  4      before  4371        after  3386
step  5      before  4204        after  2997
step  6      before  4950        after  2744
step  7      before  4598        after  2480
step  8      before  4251        after  2288
step  9      before  4262        after  2243
step  10     before  4175        after  2131
step  11     before  3999        after  2024
step  12     before  3979        after  1994
step  13     before  3842        after  1929
step  14     before  3750        after  1810
step  15     before  3735        after  1810
step  16     before  3532        after  1660

normal-lookup

step  1      before  7875        after  5847
step  2      before  4808        after  4071
step  3      before  4073        after  3462
step  4      before  3677        after  3074
step  5      before  4308        after  2978
step  6      before  3911        after  3807
step  7      before  3635        after  3522
step  8      before  3313        after  3202
step  9      before  3280        after  3257
step  10     before  3166        after  3083
step  11     before  3066        after  3026
step  12     before  2985        after  2982
step  13     before  2925        after  2924
step  14     before  2834        after  2808
step  15     before  2805        after  2803
step  16     before  2647        after  2622

radix-tree with 1024*1024*128 slots:

tag-lookup

step  1      before  1288059720  after  951736580
step  2      before  961292300   after  884212140
step  7      before  768905140   after  547267580
step  15     before  771319480   after  456550640
step  63     before  504847640   after  242704304
step  64     before  392484800   after  177920786
step  65     before  491162160   after  246895264
step  128    before  208084064   after  97348392
step  256    before  112401035   after  51408126
step  512    before  75825834    after  29145070
step  12345  before  5603166     after  2847330

normal-lookup

step  1      before  1025677120  after  861375100
step  2      before  647220080   after  572258540
step  7      before  505518960   after  484041813
step  15     before  430483053   after  444815320	*
step  63     before  388113453   after  404250546	*
step  64     before  374154666   after  396027440	*
step  65     before  381423973   after  396704853	*
step  128    before  190078700   after  202619384	*
step  256    before  100886756   after  102829108	*
step  512    before  64074505    after  56158720
step  12345  before  4237289     after  4422299		*

* i686 on Sandy bridge

radix-tree with 1024 slots:

tagged lookup

step  1      before  7990        after  4019
step  2      before  5698        after  2897
step  3      before  5013        after  2475
step  4      before  4630        after  1721
step  5      before  4346        after  1759
step  6      before  4299        after  1556
step  7      before  4098        after  1513
step  8      before  4115        after  1222
step  9      before  3983        after  1390
step  10     before  4077        after  1207
step  11     before  3921        after  1231
step  12     before  3894        after  1116
step  13     before  3840        after  1147
step  14     before  3799        after  1090
step  15     before  3797        after  1059
step  16     before  3783        after  745

normal lookup

step  1      before  5103       after  3499
step  2      before  3299       after  2550
step  3      before  2489       after  2370
step  4      before  2034       after  2302		*
step  5      before  1846       after  2268		*
step  6      before  1752       after  2249		*
step  7      before  1679       after  2164		*
step  8      before  1627       after  2153		*
step  9      before  1542       after  2095		*
step  10     before  1479       after  2109		*
step  11     before  1469       after  2009		*
step  12     before  1445       after  2039		*
step  13     before  1411       after  2013		*
step  14     before  1374       after  2046		*
step  15     before  1340       after  1975		*
step  16     before  1331       after  2000		*

radix-tree with 1024*1024*128 slots:

tagged lookup

step  1      before  1225865377  after  667153553
step  2      before  842427423   after  471533007
step  7      before  609296153   after  276260116
step  15     before  544232060   after  226859105
step  63     before  519209199   after  141343043
step  64     before  588980279   after  141951339
step  65     before  521099710   after  138282060
step  128    before  298476778   after  83390628
step  256    before  149358342   after  43602609
step  512    before  76994713    after  22911077
step  12345  before  53286669     after  1472111

normal lookup

step  1      before  819284564  after  533635310
step  2      before  512421605  after  364956155
step  7      before  271443305  after  305721345	*
step  15     before  223591630  after  273960216	*
step  63     before  190320247  after  217770207	*
step  64     before  178538168  after  267411372	*
step  65     before  186400423  after  215347937	*
step  128    before  88106045   after  140540612	*
step  256    before  44812420   after  70660377		*
step  512    before  24435438   after  36328275		*
step  12345  before  2123924    after  2148062		*

bloat-o-meter delta for this patchset + patchset with related shmem cleanups

bloat-o-meter: x86_64

add/remove: 4/3 grow/shrink: 5/6 up/down: 928/-939 (-11)
function                                     old     new   delta
radix_tree_next_chunk                          -     499    +499
shmem_unuse                                  428     554    +126
shmem_radix_tree_replace                     131     227     +96
find_get_pages_tag                           354     419     +65
find_get_pages_contig                        345     407     +62
find_get_pages                               362     396     +34
__kstrtab_radix_tree_next_chunk                -      22     +22
__ksymtab_radix_tree_next_chunk                -      16     +16
__kcrctab_radix_tree_next_chunk                -       8      +8
radix_tree_gang_lookup_slot                  204     203      -1
static.shmem_xattr_set                       384     381      -3
radix_tree_gang_lookup_tag_slot              208     191     -17
radix_tree_gang_lookup                       231     187     -44
radix_tree_gang_lookup_tag                   247     199     -48
shmem_unlock_mapping                         278     190     -88
__lookup                                     217       -    -217
__lookup_tag                                 242       -    -242
radix_tree_locate_item                       279       -    -279

bloat-o-meter: i386

add/remove: 3/3 grow/shrink: 8/9 up/down: 1075/-1275 (-200)
function                                     old     new   delta
radix_tree_next_chunk                          -     757    +757
shmem_unuse                                  352     449     +97
find_get_pages_contig                        269     322     +53
shmem_radix_tree_replace                     113     154     +41
find_get_pages_tag                           277     318     +41
dcache_dir_lseek                             426     458     +32
__kstrtab_radix_tree_next_chunk                -      22     +22
vc_do_resize                                 968     977      +9
snd_pcm_lib_read1                            725     733      +8
__ksymtab_radix_tree_next_chunk                -       8      +8
netlbl_cipsov4_list                         1120    1127      +7
find_get_pages                               293     291      -2
new_slab                                     467     459      -8
bitfill_unaligned_rev                        425     417      -8
radix_tree_gang_lookup_tag_slot              177     146     -31
blk_dump_cmd                                 267     229     -38
radix_tree_gang_lookup_slot                  212     134     -78
shmem_unlock_mapping                         221     128     -93
radix_tree_gang_lookup_tag                   275     162    -113
radix_tree_gang_lookup                       255     126    -129
__lookup                                     227       -    -227
__lookup_tag                                 271       -    -271
radix_tree_locate_item                       277       -    -277

This patch:

Implement a clean, simple and effective radix-tree iteration routine.

Iterating divided into two phases:
* lookup next chunk in radix-tree leaf node
* iterating through slots in this chunk

Main iterator function radix_tree_next_chunk() returns pointer to first
slot, and stores in the struct radix_tree_iter index of next-to-last slot.
 For tagged-iterating it also constuct bitmask of tags for retunted chunk.
 All additional logic implemented as static-inline functions and macroses.

Also adds radix_tree_find_next_bit() static-inline variant of
find_next_bit() optimized for small constant size arrays, because
find_next_bit() too heavy for searching in an array with one/two long
elements.

[akpm@linux-foundation.org: rework comments a bit]
Signed-off-by: NKonstantin Khlebnikov <khlebnikov@openvz.org>
Tested-by: NHugh Dickins <hughd@google.com>
Cc: Christoph Hellwig <hch@lst.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      78c1d784
  31. 08 3月, 2012 1 次提交
  33. 13 1月, 2012 1 次提交
    • H
      radix_tree: take radix_tree_path off stack · e2bdb933
      由 Hugh Dickins 提交于 
      Down, down in the deepest depths of GFP_NOIO page reclaim, we have
shrink_page_list() calling __remove_mapping() calling __delete_from_
swap_cache() or __delete_from_page_cache().

You would not expect those to need much stack, but in fact they call
radix_tree_delete(): which declares a 192-byte radix_tree_path array on
its stack (to record the node,offsets it visits when descending, in case
it needs to ascend to update them).  And if any tag is still set [1],
that calls radix_tree_tag_clear(), which declares a further such
192-byte radix_tree_path array on the stack.  (At least we have
interrupts disabled here, so won't then be pushing registers too.)

That was probably a good choice when most users were 32-bit (array of
half the size), and adding fields to radix_tree_node would have bloated
it unnecessarily.  But nowadays many are 64-bit, and each
radix_tree_node contains a struct rcu_head, which is only used when
freeing; whereas the radix_tree_path info is only used for updating the
tree (deleting, clearing tags or setting tags if tagged) when a lock
must be held, of no interest when accessing the tree locklessly.

So add a parent pointer to the radix_tree_node, in union with the
rcu_head, and remove all uses of the radix_tree_path.  There would be
space in that union to save the offset when descending as before (we can
argue that a lock must already be held to exclude other users), but
recalculating it when ascending is both easy (a constant shift and a
constant mask) and uncommon, so it seems better just to do that.

Two little optimizations: no need to decrement height when descending,
adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
tag on a node and its ancestors, it need not ascend from that node
again.

perf on the radix tree test harness reports radix_tree_insert() as 2%
slower (now having to set parent), but radix_tree_delete() 24% faster.
Surely that's an exaggeration from rtth's artificially low map shift 3,
but forcing it back to 6 still rates radix_tree_delete() 8% faster.

[1] Can a pagecache tag (dirty, writeback or towrite) actually still be
set at the time of radix_tree_delete()? Perhaps not if the filesystem is
well-behaved.  But although I've not tracked any stack overflow down to
this cause, I have observed a curious case in which a dirty tag is set
and left set on tmpfs: page migration's migrate_page_copy() happens to
use __set_page_dirty_nobuffers() to set PageDirty on the newpage, and
that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
filesystem which doesn't use tags, except for this stack depth issue.
Signed-off-by: NHugh Dickins <hughd@google.com>
Cc: Jan Kara <jack@suse.cz>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Mel Gorman <mgorman@suse.de>
Cc: Nai Xia <nai.xia@gmail.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      e2bdb933
  35. 01 11月, 2011 1 次提交
  37. 04 8月, 2011 2 次提交
    • H
      tmpfs radix_tree: locate_item to speed up swapoff · e504f3fd
      由 Hugh Dickins 提交于 
      We have already acknowledged that swapoff of a tmpfs file is slower than
it was before conversion to the generic radix_tree: a little slower
there will be acceptable, if the hotter paths are faster.

But it was a shock to find swapoff of a 500MB file 20 times slower on my
laptop, taking 10 minutes; and at that rate it significantly slows down
my testing.

Now, most of that turned out to be overhead from PROVE_LOCKING and
PROVE_RCU: without those it was only 4 times slower than before; and
more realistic tests on other machines don't fare as badly.

I've tried a number of things to improve it, including tagging the swap
entries, then doing lookup by tag: I'd expected that to halve the time,
but in practice it's erratic, and often counter-productive.

The only change I've so far found to make a consistent improvement, is
to short-circuit the way we go back and forth, gang lookup packing
entries into the array supplied, then shmem scanning that array for the
target entry.  Scanning in place doubles the speed, so it's now only
twice as slow as before (or three times slower when the PROVEs are on).

So, add radix_tree_locate_item() as an expedient, once-off,
single-caller hack to do the lookup directly in place.  #ifdef it on
CONFIG_SHMEM and CONFIG_SWAP, as much to document its limited
applicability as save space in other configurations.  And, sadly,
#include sched.h for cond_resched().
Signed-off-by: NHugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      e504f3fd
    • H
      radix_tree: exceptional entries and indices · 6328650b
      由 Hugh Dickins 提交于 
      A patchset to extend tmpfs to MAX_LFS_FILESIZE by abandoning its
peculiar swap vector, instead keeping a file's swap entries in the same
radix tree as its struct page pointers: thus saving memory, and
simplifying its code and locking.

This patch:

The radix_tree is used by several subsystems for different purposes.  A
major use is to store the struct page pointers of a file's pagecache for
memory management.  But what if mm wanted to store something other than
page pointers there too?

The low bit of a radix_tree entry is already used to denote an indirect
pointer, for internal use, and the unlikely radix_tree_deref_retry()
case.

Define the next bit as denoting an exceptional entry, and supply inline
functions radix_tree_exception() to return non-0 in either unlikely
case, and radix_tree_exceptional_entry() to return non-0 in the second
case.

If a subsystem already uses radix_tree with that bit set, no problem: it
does not affect internal workings at all, but is defined for the
convenience of those storing well-aligned pointers in the radix_tree.

The radix_tree_gang_lookups have an implicit assumption that the caller
can deduce the offset of each entry returned e.g.  by the page->index of
a struct page.  But that may not be feasible for some kinds of item to
be stored there.

radix_tree_gang_lookup_slot() allow for an optional indices argument,
output array in which to return those offsets.  The same could be added
to other radix_tree_gang_lookups, but for now keep it to the only one
for which we need it.
Signed-off-by: NHugh Dickins <hughd@google.com>
Acked-by: NRik van Riel <riel@redhat.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      6328650b
  39. 26 1月, 2011 1 次提交
    • T
      radix_tree: radix_tree_gang_lookup_tag_slot() may never return · ac15ee69
      由 Toshiyuki Okajima 提交于 
      Executed command: fsstress -d /mnt -n 600 -p 850

  crash> bt
  PID: 7947   TASK: ffff880160546a70  CPU: 0   COMMAND: "fsstress"
   #0 [ffff8800dfc07d00] machine_kexec at ffffffff81030db9
   #1 [ffff8800dfc07d70] crash_kexec at ffffffff810a7952
   #2 [ffff8800dfc07e40] oops_end at ffffffff814aa7c8
   #3 [ffff8800dfc07e70] die_nmi at ffffffff814aa969
   #4 [ffff8800dfc07ea0] do_nmi_callback at ffffffff8102b07b
   #5 [ffff8800dfc07f10] do_nmi at ffffffff814aa514
   #6 [ffff8800dfc07f50] nmi at ffffffff814a9d60
      [exception RIP: __lookup_tag+100]
      RIP: ffffffff812274b4  RSP: ffff88016056b998  RFLAGS: 00000287
      RAX: 0000000000000000  RBX: 0000000000000002  RCX: 0000000000000006
      RDX: 000000000000001d  RSI: ffff88016056bb18  RDI: ffff8800c85366e0
      RBP: ffff88016056b9c8   R8: ffff88016056b9e8   R9: 0000000000000000
      R10: 000000000000000e  R11: ffff8800c8536908  R12: 0000000000000010
      R13: 0000000000000040  R14: ffffffffffffffc0  R15: ffff8800c85366e0
      ORIG_RAX: ffffffffffffffff  CS: 0010  SS: 0018
  <NMI exception stack>
   #7 [ffff88016056b998] __lookup_tag at ffffffff812274b4
   #8 [ffff88016056b9d0] radix_tree_gang_lookup_tag_slot at ffffffff81227605
   #9 [ffff88016056ba20] find_get_pages_tag at ffffffff810fc110
  #10 [ffff88016056ba80] pagevec_lookup_tag at ffffffff81105e85
  #11 [ffff88016056baa0] write_cache_pages at ffffffff81104c47
  #12 [ffff88016056bbd0] generic_writepages at ffffffff81105014
  #13 [ffff88016056bbe0] do_writepages at ffffffff81105055
  #14 [ffff88016056bbf0] __filemap_fdatawrite_range at ffffffff810fb2cb
  #15 [ffff88016056bc40] filemap_write_and_wait_range at ffffffff810fb32a
  #16 [ffff88016056bc70] generic_file_direct_write at ffffffff810fb3dc
  #17 [ffff88016056bce0] __generic_file_aio_write at ffffffff810fcee5
  #18 [ffff88016056bda0] generic_file_aio_write at ffffffff810fd085
  #19 [ffff88016056bdf0] do_sync_write at ffffffff8114f9ea
  #20 [ffff88016056bf00] vfs_write at ffffffff8114fcf8
  #21 [ffff88016056bf30] sys_write at ffffffff81150691
  #22 [ffff88016056bf80] system_call_fastpath at ffffffff8100c0b2

I think this root cause is the following:

 radix_tree_range_tag_if_tagged() always tags the root tag with settag
 if the root tag is set with iftag even if there are no iftag tags
 in the specified range (Of course, there are some iftag tags
 outside the specified range).

===============================================================================
[[[Detailed description]]]

(1) Why cannot radix_tree_gang_lookup_tag_slot() return forever?

__lookup_tag():
 - Return with 0.
 - Return with the index which is not bigger than the old one as the
   input parameter.

Therefore the following "while" repeats forever because the above
conditions cause "ret" not to be updated and the cur_index cannot be
changed into the bigger one.

(So, radix_tree_gang_lookup_tag_slot() cannot return forever.)

radix_tree_gang_lookup_tag_slot():
1178         while (ret < max_items) {
1179                 unsigned int slots_found;
1180                 unsigned long next_index;       /* Index of next search */
1181
1182                 if (cur_index > max_index)
1183                         break;
1184                 slots_found = __lookup_tag(node, results + ret,
1185                                 cur_index, max_items - ret, &next_index,
tag);
1186                 ret += slots_found;
			// cannot update ret because slots_found == 0.
			// so, this while loops forever.
1187                 if (next_index == 0)
1188                         break;
1189                 cur_index = next_index;
1190         }

(2) Why does __lookup_tag() return with 0 and doesn't update the index?

Assuming the following:
  - the one of the slot in radix_tree_node is NULL.
  - the one of the tag which corresponds to the slot sets with
    PAGECACHE_TAG_TOWRITE or other.
  - In a certain height(!=0), the corresponding index is 0.

a) __lookup_tag() notices that the tag is set.

1005 static unsigned int
1006 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
1007         unsigned int max_items, unsigned long *next_index, unsigned int tag)
1008 {
1009         unsigned int nr_found = 0;
1010         unsigned int shift, height;
1011
1012         height = slot->height;
1013         if (height == 0)
1014                 goto out;
1015         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
1016
1017         while (height > 0) {
1018                 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
1019
1020                 for (;;) {
1021                         if (tag_get(slot, tag, i))
1022                                 break;
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* the index is not updated yet.

b) __lookup_tag() notices that the slot is NULL.

1023                         index &= ~((1UL << shift) - 1);
1024                         index += 1UL << shift;
1025                         if (index == 0)
1026                                 goto out;       /* 32-bit wraparound */
1027                         i++;
1028                         if (i == RADIX_TREE_MAP_SIZE)
1029                                 goto out;
1030                 }
1031                 height--;
1032                 if (height == 0) {      /* Bottom level: grab some items */
...
1055                 }
1056                 shift -= RADIX_TREE_MAP_SHIFT;
1057                 slot = rcu_dereference_raw(slot->slots[i]);
1058                 if (slot == NULL)
1059                         break;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

c) __lookup_tag() doesn't update the index and return with 0.

1060         }
1061 out:
1062         *next_index = index;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1063         return nr_found;
1064 }

(3) Why is the slot NULL even if the tag is set?

Because radix_tree_range_tag_if_tagged() always sets the root tag with
PAGECACHE_TAG_TOWRITE if the root tag is set with PAGECACHE_TAG_DIRTY,
even if there is no tag which can be set with PAGECACHE_TAG_TOWRITE
in the specified range (from *first_indexp to last_index). Of course,
some PAGECACHE_TAG_DIRTY nodes must exist outside the specified range.
(radix_tree_range_tag_if_tagged() is called only from tag_pages_for_writeback())

 640 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root
*root,
 641                 unsigned long *first_indexp, unsigned long last_index,
 642                 unsigned long nr_to_tag,
 643                 unsigned int iftag, unsigned int settag)
 644 {
 645         unsigned int height = root->height;
 646         struct radix_tree_path path[height];
 647         struct radix_tree_path *pathp = path;
 648         struct radix_tree_node *slot;
 649         unsigned int shift;
 650         unsigned long tagged = 0;
 651         unsigned long index = *first_indexp;
 652
 653         last_index = min(last_index, radix_tree_maxindex(height));
 654         if (index > last_index)
 655                 return 0;
 656         if (!nr_to_tag)
 657                 return 0;
 658         if (!root_tag_get(root, iftag)) {
 659                 *first_indexp = last_index + 1;
 660                 return 0;
 661         }
 662         if (height == 0) {
 663                 *first_indexp = last_index + 1;
 664                 root_tag_set(root, settag);
 665                 return 1;
 666         }
...
 733         root_tag_set(root, settag);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 734         *first_indexp = index;
 735
 736         return tagged;
 737 }

As the result, there is no radix_tree_node which is set with
PAGECACHE_TAG_TOWRITE but the root tag(radix_tree_root) is set with
PAGECACHE_TAG_TOWRITE.

[figure: inside radix_tree]
(Please see the figure with typewriter font)
===========================================
          [roottag = DIRTY]
                 |             tag=0:NOTHING
         tag[0 0 0 1]              1:DIRTY
            [x x x +]              2:WRITEBACK
                   |               3:DIRTY,WRITEBACK
                   p               4:TOWRITE
             <--->                 5:DIRTY,TOWRITE ...
     specified range (index: 0 to 2)

* There is no DIRTY tag within the specified range.
 (But there is a DIRTY tag outside that range.)

            | | | | | | | | |
    after calling tag_pages_for_writeback()
            | | | | | | | | |
            v v v v v v v v v

          [roottag = DIRTY,TOWRITE]
                 |                 p is "page".
         tag[0 0 0 1]              x is NULL.
            [x x x +]              +- is a pointer to "page".
                   |
                   p

* But TOWRITE tag is set on the root tag.
============================================

After that, radix_tree_extend() via radix_tree_insert() is called
when the page is added.
This function sets the new radix_tree_node with PAGECACHE_TAG_TOWRITE
to succeed the status of the root tag.

 246 static int radix_tree_extend(struct radix_tree_root *root, unsigned long
index)
 247 {
 248         struct radix_tree_node *node;
 249         unsigned int height;
 250         int tag;
 251
 252         /* Figure out what the height should be.  */
 253         height = root->height + 1;
 254         while (index > radix_tree_maxindex(height))
 255                 height++;
 256
 257         if (root->rnode == NULL) {
 258                 root->height = height;
 259                 goto out;
 260         }
 261
 262         do {
 263                 unsigned int newheight;
 264                 if (!(node = radix_tree_node_alloc(root)))
 265                         return -ENOMEM;
 266
 267                 /* Increase the height.  */
 268                 node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
 269
 270                 /* Propagate the aggregated tag info into the new root */
 271                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 272                         if (root_tag_get(root, tag))
 273                                 tag_set(node, tag, 0);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 274                 }

===========================================
          [roottag = DIRTY,TOWRITE]
                 |     :
         tag[0 0 0 1] [0 0 0 0]
            [x x x +] [+ x x x]
                   |   |
                   p   p (new page)

            | | | | | | | | |
    after calling radix_tree_insert
            | | | | | | | | |
            v v v v v v v v v

          [roottag = DIRTY,TOWRITE]
                 |
         tag [5 0 0 0]    *  DIRTY and TOWRITE tags are
             [+ + x x]       succeeded to the new node.
              | |
  tag [0 0 0 1] [0 0 0 0]
      [x x x +] [+ x x x]
             |   |
             p   p
============================================

After that, the index 3 page is released by remove_from_page_cache().
Then we can make the situation that the tag is set with PAGECACHE_TAG_TOWRITE
and that the slot which corresponds to the tag is NULL.
===========================================
          [roottag = DIRTY,TOWRITE]
                 |
         tag [5 0 0 0]
             [+ + x x]
              | |
  tag [0 0 0 1] [0 0 0 0]
      [x x x +] [+ x x x]
             |   |
             p   p
         (remove)

            | | | | | | | | |
    after calling remove_page_cache
            | | | | | | | | |
            v v v v v v v v v

          [roottag = DIRTY,TOWRITE]
                 |
         tag [4 0 0 0]      * Only DIRTY tag is cleared
             [x + x x]        because no TOWRITE tag is existed
                |             in the bottom node.
                [0 0 0 0]
                [+ x x x]
                 |
                 p
============================================

To solve this problem

Change to that radix_tree_tag_if_tagged() doesn't tag the root tag
if it doesn't set any tags within the specified range.

Like this.
============================================
 640 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root
*root,
 641                 unsigned long *first_indexp, unsigned long last_index,
 642                 unsigned long nr_to_tag,
 643                 unsigned int iftag, unsigned int settag)
 644 {
 650         unsigned long tagged = 0;
...
 733 	     if (tagged)
^^^^^^^^^^^^^^^^^^^^^^^^
 734            root_tag_set(root, settag);
 735         *first_indexp = index;
 736
 737         return tagged;
 738 }

============================================
Signed-off-by: NToshiyuki Okajima <toshi.okajima@jp.fujitsu.com>
Acked-by: NJan Kara <jack@suse.cz>
Cc: Dave Chinner <david@fromorbit.com>
Cc: Nick Piggin <nickpiggin@yahoo.com.au>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      ac15ee69
  41. 12 11月, 2010 1 次提交
    • N
      radix-tree: fix RCU bug · 27d20fdd
      由 Nick Piggin 提交于 
      Salman Qazi describes the following radix-tree bug:

In the following case, we get can get a deadlock:

0.  The radix tree contains two items, one has the index 0.
1.  The reader (in this case find_get_pages) takes the rcu_read_lock.
2.  The reader acquires slot(s) for item(s) including the index 0 item.
3.  The non-zero index item is deleted, and as a consequence the other item is
    moved to the root of the tree. The place where it used to be is queued for
    deletion after the readers finish.
3b. The zero item is deleted, removing it from the direct slot, it remains in
    the rcu-delayed indirect node.
4.  The reader looks at the index 0 slot, and finds that the page has 0 ref
    count
5.  The reader looks at it again, hoping that the item will either be freed or
    the ref count will increase. This never happens, as the slot it is looking
    at will never be updated. Also, this slot can never be reclaimed because
    the reader is holding rcu_read_lock and is in an infinite loop.

The fix is to re-use the same "indirect" pointer case that requires a slot
lookup retry into a general "retry the lookup" bit.
Signed-off-by: NNick Piggin <npiggin@kernel.dk>
Reported-by: NSalman Qazi <sqazi@google.com>
Cc: <stable@kernel.org>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      27d20fdd
  43. 23 8月, 2010 2 次提交
    • D
      radix-tree: radix_tree_range_tag_if_tagged() can set incorrect tags · 144dcfc0
      由 Dave Chinner 提交于 
      Commit ebf8aa44 ("radix-tree:
omplement function radix_tree_range_tag_if_tagged") does not safely
set tags on on intermediate tree nodes. The code walks down the tree
setting tags before it has fully resolved the path to the leaf under
the assumption there will be a leaf slot with the tag set in the
range it is searching.

Unfortunately, this is not a valid assumption - we can abort after
setting a tag on an intermediate node if we overrun the number of
tags we are allowed to set in a batch, or stop scanning because we
we have passed the last scan index before we reach a leaf slot with
the tag we are searching for set.

As a result, we can leave the function with tags set on intemediate
nodes which can be tripped over later by tag-based lookups. The
result of these stale tags is that lookup may end prematurely or
livelock because the lookup cannot make progress.

The fix for the problem involves reocrding the traversal path we
take to the leaf nodes, and only propagating the tags back up the
tree once the tag is set in the leaf node slot. We are already
recording the path for efficient traversal, so there is no
additional overhead to do the intermediately node tag setting in
this manner.

This fixes a radix tree lookup livelock triggered by the new
writeback sync livelock avoidance code introduced in commit
f446daae ("mm: implement writeback
livelock avoidance using page tagging").
Signed-off-by: NDave Chinner <dchinner@redhat.com>
Acked-by: NJan Kara <jack@suse.cz>
      144dcfc0
    • D
      radix-tree: clear all tags in radix_tree_node_rcu_free · b6dd0865
      由 Dave Chinner 提交于 
      Commit f446daae ("mm: implement
writeback livelock avoidance using page tagging") introduced a new
radix tree tag, increasing the number of tags in each node from 2 to
3. It did not, however, fix up the code in
radix_tree_node_rcu_free() that cleans up after radix_tree_shrink()
and hence could leave stray tags set in the new tag array.

The result is that the livelock avoidance code added in the the
above commit would hit stale tags when doing tag based lookups,
resulting in livelocks when trying to traverse the tree.

Fix this problem in radix_tree_node_rcu_free() so it doesn't happen
again in the future by using a loop to walk all the tags up to
RADIX_TREE_MAX_TAGS to clear the stray tags radix_tree_shrink()
leaves behind.
Signed-off-by: NDave Chinner <dchinner@redhat.com>
Acked-by: NNick Piggin <npiggin@kernel.dk>
Acked-by: NJan Kara <jack@suse.cz>
      b6dd0865