Message-ID: <20161118082942.GH18676@quack2.suse.cz>
Date:   Fri, 18 Nov 2016 09:29:42 +0100
From:   Jan Kara <jack@...e.cz>
To:     Johannes Weiner <hannes@...xchg.org>
Cc:     Andrew Morton <akpm@...ux-foundation.org>, Jan Kara <jack@...e.cz>,
        "Kirill A. Shutemov" <kirill@...temov.name>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        kernel-team@...com
Subject: Re: [PATCH 8/9] mm: workingset: move shadow entry tracking to radix
 tree exceptional tracking

On Thu 17-11-16 14:32:11, Johannes Weiner wrote:
> Currently, we track the shadow entries in the page cache in the upper
> bits of the radix_tree_node->count, behind the back of the radix tree
> implementation. Because the radix tree code has no awareness of them,
> we rely on random subtleties throughout the implementation (such as
> the node->count != 1 check in the shrinking code, which is meant to
> exclude multi-entry nodes but also happens to skip nodes with only one
> shadow entry, as that's accounted in the upper bits). This is error
> prone and has, in fact, caused the bug fixed in d3798ae8c6f3 ("mm:
> filemap: don't plant shadow entries without radix tree node").
> 
> To remove these subtleties, this patch moves shadow entry tracking
> from the upper bits of node->count to the existing counter for
> exceptional entries. node->count goes back to being a simple counter
> of valid entries in the tree node and can be shrunk to a single byte.
> 
> This vastly simplifies the page cache code. All accounting happens
> natively inside the radix tree implementation, and maintaining the LRU
> linkage of shadow nodes is consolidated into a single function in the
> workingset code that is called for leaf nodes affected by a change in
> the page cache tree.
> 
> This also removes the last user of the __radix_delete_node() return
> value. Eliminate it.

Looks good. You can add:

Reviewed-by: Jan Kara <jack@...e.cz>

								Honza

> 
> Signed-off-by: Johannes Weiner <hannes@...xchg.org>
> ---
>  include/linux/radix-tree.h |  8 ++-----
>  include/linux/swap.h       | 34 +---------------------------
>  lib/radix-tree.c           | 25 +++++----------------
>  mm/filemap.c               | 54 +++++---------------------------------------
>  mm/truncate.c              | 21 +++--------------
>  mm/workingset.c            | 56 +++++++++++++++++++++++++++++++++++-----------
>  6 files changed, 60 insertions(+), 138 deletions(-)
> 
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 15c972ea9510..744486057e9e 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -80,14 +80,10 @@ static inline bool radix_tree_is_internal_node(void *ptr)
>  #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
>  					  RADIX_TREE_MAP_SHIFT))
>  
> -/* Internally used bits of node->count */
> -#define RADIX_TREE_COUNT_SHIFT	(RADIX_TREE_MAP_SHIFT + 1)
> -#define RADIX_TREE_COUNT_MASK	((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
> -
>  struct radix_tree_node {
>  	unsigned char	shift;		/* Bits remaining in each slot */
>  	unsigned char	offset;		/* Slot offset in parent */
> -	unsigned int	count;		/* Total entry count */
> +	unsigned char	count;		/* Total entry count */
>  	unsigned char	exceptional;	/* Exceptional entry count */
>  	union {
>  		struct {
> @@ -270,7 +266,7 @@ void __radix_tree_replace(struct radix_tree_root *root,
>  			  radix_tree_update_node_t update_node, void *private);
>  void radix_tree_replace_slot(struct radix_tree_root *root,
>  			     void **slot, void *item);
> -bool __radix_tree_delete_node(struct radix_tree_root *root,
> +void __radix_tree_delete_node(struct radix_tree_root *root,
>  			      struct radix_tree_node *node);
>  void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
>  void *radix_tree_delete(struct radix_tree_root *, unsigned long);
> diff --git a/include/linux/swap.h b/include/linux/swap.h
> index a56523cefb9b..09b212d37f1d 100644
> --- a/include/linux/swap.h
> +++ b/include/linux/swap.h
> @@ -246,39 +246,7 @@ struct swap_info_struct {
>  void *workingset_eviction(struct address_space *mapping, struct page *page);
>  bool workingset_refault(void *shadow);
>  void workingset_activation(struct page *page);
> -extern struct list_lru workingset_shadow_nodes;
> -
> -static inline unsigned int workingset_node_pages(struct radix_tree_node *node)
> -{
> -	return node->count & RADIX_TREE_COUNT_MASK;
> -}
> -
> -static inline void workingset_node_pages_inc(struct radix_tree_node *node)
> -{
> -	node->count++;
> -}
> -
> -static inline void workingset_node_pages_dec(struct radix_tree_node *node)
> -{
> -	VM_WARN_ON_ONCE(!workingset_node_pages(node));
> -	node->count--;
> -}
> -
> -static inline unsigned int workingset_node_shadows(struct radix_tree_node *node)
> -{
> -	return node->count >> RADIX_TREE_COUNT_SHIFT;
> -}
> -
> -static inline void workingset_node_shadows_inc(struct radix_tree_node *node)
> -{
> -	node->count += 1U << RADIX_TREE_COUNT_SHIFT;
> -}
> -
> -static inline void workingset_node_shadows_dec(struct radix_tree_node *node)
> -{
> -	VM_WARN_ON_ONCE(!workingset_node_shadows(node));
> -	node->count -= 1U << RADIX_TREE_COUNT_SHIFT;
> -}
> +void workingset_update_node(struct radix_tree_node *node, void *private);
>  
>  /* linux/mm/page_alloc.c */
>  extern unsigned long totalram_pages;
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index df4ff18dd63c..9dbfaac05e6c 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -541,12 +541,10 @@ static int radix_tree_extend(struct radix_tree_root *root,
>   *	radix_tree_shrink    -    shrink radix tree to minimum height
>   *	@root		radix tree root
>   */
> -static inline bool radix_tree_shrink(struct radix_tree_root *root,
> +static inline void radix_tree_shrink(struct radix_tree_root *root,
>  				     radix_tree_update_node_t update_node,
>  				     void *private)
>  {
> -	bool shrunk = false;
> -
>  	for (;;) {
>  		struct radix_tree_node *node = root->rnode;
>  		struct radix_tree_node *child;
> @@ -606,26 +604,20 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
>  		}
>  
>  		radix_tree_node_free(node);
> -		shrunk = true;
>  	}
> -
> -	return shrunk;
>  }
>  
> -static bool delete_node(struct radix_tree_root *root,
> +static void delete_node(struct radix_tree_root *root,
>  			struct radix_tree_node *node,
>  			radix_tree_update_node_t update_node, void *private)
>  {
> -	bool deleted = false;
> -
>  	do {
>  		struct radix_tree_node *parent;
>  
>  		if (node->count) {
>  			if (node == entry_to_node(root->rnode))
> -				deleted |= radix_tree_shrink(root, update_node,
> -							     private);
> -			return deleted;
> +				radix_tree_shrink(root, update_node, private);
> +			return;
>  		}
>  
>  		parent = node->parent;
> @@ -638,12 +630,9 @@ static bool delete_node(struct radix_tree_root *root,
>  		}
>  
>  		radix_tree_node_free(node);
> -		deleted = true;
>  
>  		node = parent;
>  	} while (node);
> -
> -	return deleted;
>  }
>  
>  /**
> @@ -1595,13 +1584,11 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
>   *	After clearing the slot at @index in @node from radix tree
>   *	rooted at @root, call this function to attempt freeing the
>   *	node and shrinking the tree.
> - *
> - *	Returns %true if @node was freed, %false otherwise.
>   */
> -bool __radix_tree_delete_node(struct radix_tree_root *root,
> +void __radix_tree_delete_node(struct radix_tree_root *root,
>  			      struct radix_tree_node *node)
>  {
> -	return delete_node(root, node, NULL, NULL);
> +	delete_node(root, node, NULL, NULL);
>  }
>  
>  static inline void delete_sibling_entries(struct radix_tree_node *node,
> diff --git a/mm/filemap.c b/mm/filemap.c
> index eb463156f29a..7d92032277ff 100644
> --- a/mm/filemap.c
> +++ b/mm/filemap.c
> @@ -132,37 +132,19 @@ static int page_cache_tree_insert(struct address_space *mapping,
>  		if (!dax_mapping(mapping)) {
>  			if (shadowp)
>  				*shadowp = p;
> -			if (node)
> -				workingset_node_shadows_dec(node);
>  		} else {
>  			/* DAX can replace empty locked entry with a hole */
>  			WARN_ON_ONCE(p !=
>  				(void *)(RADIX_TREE_EXCEPTIONAL_ENTRY |
>  					 RADIX_DAX_ENTRY_LOCK));
> -			/* DAX accounts exceptional entries as normal pages */
> -			if (node)
> -				workingset_node_pages_dec(node);
>  			/* Wakeup waiters for exceptional entry lock */
>  			dax_wake_mapping_entry_waiter(mapping, page->index,
>  						      false);
>  		}
>  	}
> -	radix_tree_replace_slot(&mapping->page_tree, slot, page);
> +	__radix_tree_replace(&mapping->page_tree, node, slot, page,
> +			     workingset_update_node, mapping);
>  	mapping->nrpages++;
> -	if (node) {
> -		workingset_node_pages_inc(node);
> -		/*
> -		 * Don't track node that contains actual pages.
> -		 *
> -		 * Avoid acquiring the list_lru lock if already
> -		 * untracked.  The list_empty() test is safe as
> -		 * node->private_list is protected by
> -		 * mapping->tree_lock.
> -		 */
> -		if (!list_empty(&node->private_list))
> -			list_lru_del(&workingset_shadow_nodes,
> -				     &node->private_list);
> -	}
>  	return 0;
>  }
>  
> @@ -182,8 +164,6 @@ static void page_cache_tree_delete(struct address_space *mapping,
>  		__radix_tree_lookup(&mapping->page_tree, page->index + i,
>  				    &node, &slot);
>  
> -		radix_tree_clear_tags(&mapping->page_tree, node, slot);
> -
>  		if (!node) {
>  			VM_BUG_ON_PAGE(nr != 1, page);
>  			/*
> @@ -193,33 +173,9 @@ static void page_cache_tree_delete(struct address_space *mapping,
>  			shadow = NULL;
>  		}
>  
> -		radix_tree_replace_slot(&mapping->page_tree, slot, shadow);
> -
> -		if (!node)
> -			break;
> -
> -		workingset_node_pages_dec(node);
> -		if (shadow)
> -			workingset_node_shadows_inc(node);
> -		else
> -			if (__radix_tree_delete_node(&mapping->page_tree, node))
> -				continue;
> -
> -		/*
> -		 * Track node that only contains shadow entries. DAX mappings
> -		 * contain no shadow entries and may contain other exceptional
> -		 * entries so skip those.
> -		 *
> -		 * Avoid acquiring the list_lru lock if already tracked.
> -		 * The list_empty() test is safe as node->private_list is
> -		 * protected by mapping->tree_lock.
> -		 */
> -		if (!dax_mapping(mapping) && !workingset_node_pages(node) &&
> -				list_empty(&node->private_list)) {
> -			node->private_data = mapping;
> -			list_lru_add(&workingset_shadow_nodes,
> -					&node->private_list);
> -		}
> +		radix_tree_clear_tags(&mapping->page_tree, node, slot);
> +		__radix_tree_replace(&mapping->page_tree, node, slot, shadow,
> +				     workingset_update_node, mapping);
>  	}
>  
>  	if (shadow) {
> diff --git a/mm/truncate.c b/mm/truncate.c
> index 6ae44571d4c7..7e5464a611db 100644
> --- a/mm/truncate.c
> +++ b/mm/truncate.c
> @@ -44,28 +44,13 @@ static void clear_exceptional_entry(struct address_space *mapping,
>  	 * without the tree itself locked.  These unlocked entries
>  	 * need verification under the tree lock.
>  	 */
> -	if (!__radix_tree_lookup(&mapping->page_tree, index, &node,
> -				&slot))
> +	if (!__radix_tree_lookup(&mapping->page_tree, index, &node, &slot))
>  		goto unlock;
>  	if (*slot != entry)
>  		goto unlock;
> -	radix_tree_replace_slot(&mapping->page_tree, slot, NULL);
> +	__radix_tree_replace(&mapping->page_tree, node, slot, NULL,
> +			     workingset_update_node, mapping);
>  	mapping->nrexceptional--;
> -	if (!node)
> -		goto unlock;
> -	workingset_node_shadows_dec(node);
> -	/*
> -	 * Don't track node without shadow entries.
> -	 *
> -	 * Avoid acquiring the list_lru lock if already untracked.
> -	 * The list_empty() test is safe as node->private_list is
> -	 * protected by mapping->tree_lock.
> -	 */
> -	if (!workingset_node_shadows(node) &&
> -	    !list_empty(&node->private_list))
> -		list_lru_del(&workingset_shadow_nodes,
> -				&node->private_list);
> -	__radix_tree_delete_node(&mapping->page_tree, node);
>  unlock:
>  	spin_unlock_irq(&mapping->tree_lock);
>  }
> diff --git a/mm/workingset.c b/mm/workingset.c
> index 3cfc61d84a52..111e06559892 100644
> --- a/mm/workingset.c
> +++ b/mm/workingset.c
> @@ -10,6 +10,7 @@
>  #include <linux/atomic.h>
>  #include <linux/module.h>
>  #include <linux/swap.h>
> +#include <linux/dax.h>
>  #include <linux/fs.h>
>  #include <linux/mm.h>
>  
> @@ -334,18 +335,45 @@ void workingset_activation(struct page *page)
>   * point where they would still be useful.
>   */
>  
> -struct list_lru workingset_shadow_nodes;
> +static struct list_lru shadow_nodes;
> +
> +void workingset_update_node(struct radix_tree_node *node, void *private)
> +{
> +	struct address_space *mapping = private;
> +
> +	/* Only regular page cache has shadow entries */
> +	if (dax_mapping(mapping) || shmem_mapping(mapping))
> +		return;
> +
> +	/*
> +	 * Track non-empty nodes that contain only shadow entries;
> +	 * unlink those that contain pages or are being freed.
> +	 *
> +	 * Avoid acquiring the list_lru lock when the nodes are
> +	 * already where they should be. The list_empty() test is safe
> +	 * as node->private_list is protected by &mapping->tree_lock.
> +	 */
> +	if (node->count && node->count == node->exceptional) {
> +		if (list_empty(&node->private_list)) {
> +			node->private_data = mapping;
> +			list_lru_add(&shadow_nodes, &node->private_list);
> +		}
> +	} else {
> +		if (!list_empty(&node->private_list))
> +			list_lru_del(&shadow_nodes, &node->private_list);
> +	}
> +}
>  
>  static unsigned long count_shadow_nodes(struct shrinker *shrinker,
>  					struct shrink_control *sc)
>  {
> -	unsigned long shadow_nodes;
>  	unsigned long max_nodes;
> +	unsigned long nodes;
>  	unsigned long pages;
>  
>  	/* list_lru lock nests inside IRQ-safe mapping->tree_lock */
>  	local_irq_disable();
> -	shadow_nodes = list_lru_shrink_count(&workingset_shadow_nodes, sc);
> +	nodes = list_lru_shrink_count(&shadow_nodes, sc);
>  	local_irq_enable();
>  
>  	if (memcg_kmem_enabled()) {
> @@ -372,10 +400,10 @@ static unsigned long count_shadow_nodes(struct shrinker *shrinker,
>  	 */
>  	max_nodes = pages >> (1 + RADIX_TREE_MAP_SHIFT - 3);
>  
> -	if (shadow_nodes <= max_nodes)
> +	if (nodes <= max_nodes)
>  		return 0;
>  
> -	return shadow_nodes - max_nodes;
> +	return nodes - max_nodes;
>  }
>  
>  static enum lru_status shadow_lru_isolate(struct list_head *item,
> @@ -418,22 +446,25 @@ static enum lru_status shadow_lru_isolate(struct list_head *item,
>  	 * no pages, so we expect to be able to remove them all and
>  	 * delete and free the empty node afterwards.
>  	 */
> -	if (WARN_ON_ONCE(!workingset_node_shadows(node)))
> +	if (WARN_ON_ONCE(!node->exceptional))
>  		goto out_invalid;
> -	if (WARN_ON_ONCE(workingset_node_pages(node)))
> +	if (WARN_ON_ONCE(node->count != node->exceptional))
>  		goto out_invalid;
>  	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
>  		if (node->slots[i]) {
>  			if (WARN_ON_ONCE(!radix_tree_exceptional_entry(node->slots[i])))
>  				goto out_invalid;
> +			if (WARN_ON_ONCE(!node->exceptional))
> +				goto out_invalid;
>  			if (WARN_ON_ONCE(!mapping->nrexceptional))
>  				goto out_invalid;
>  			node->slots[i] = NULL;
> -			workingset_node_shadows_dec(node);
> +			node->exceptional--;
> +			node->count--;
>  			mapping->nrexceptional--;
>  		}
>  	}
> -	if (WARN_ON_ONCE(workingset_node_shadows(node)))
> +	if (WARN_ON_ONCE(node->exceptional))
>  		goto out_invalid;
>  	inc_node_state(page_pgdat(virt_to_page(node)), WORKINGSET_NODERECLAIM);
>  	__radix_tree_delete_node(&mapping->page_tree, node);
> @@ -456,8 +487,7 @@ static unsigned long scan_shadow_nodes(struct shrinker *shrinker,
>  
>  	/* list_lru lock nests inside IRQ-safe mapping->tree_lock */
>  	local_irq_disable();
> -	ret =  list_lru_shrink_walk(&workingset_shadow_nodes, sc,
> -				    shadow_lru_isolate, NULL);
> +	ret = list_lru_shrink_walk(&shadow_nodes, sc, shadow_lru_isolate, NULL);
>  	local_irq_enable();
>  	return ret;
>  }
> @@ -496,7 +526,7 @@ static int __init workingset_init(void)
>  	pr_info("workingset: timestamp_bits=%d max_order=%d bucket_order=%u\n",
>  	       timestamp_bits, max_order, bucket_order);
>  
> -	ret = list_lru_init_key(&workingset_shadow_nodes, &shadow_nodes_key);
> +	ret = list_lru_init_key(&shadow_nodes, &shadow_nodes_key);
>  	if (ret)
>  		goto err;
>  	ret = register_shrinker(&workingset_shadow_shrinker);
> @@ -504,7 +534,7 @@ static int __init workingset_init(void)
>  		goto err_list_lru;
>  	return 0;
>  err_list_lru:
> -	list_lru_destroy(&workingset_shadow_nodes);
> +	list_lru_destroy(&shadow_nodes);
>  err:
>  	return ret;
>  }
> -- 
> 2.10.2
> 
-- 
Jan Kara <jack@...e.com>
SUSE Labs, CR

Powered by blists - more mailing lists