LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
@ 2018-05-22 10:07 Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 01/17] list_lru: Combine code under the same define Kirill Tkhai
                   ` (19 more replies)
  0 siblings, 20 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:07 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Hi,

this patches solves the problem with slow shrink_slab() occuring
on the machines having many shrinkers and memory cgroups (i.e.,
with many containers). The problem is complexity of shrink_slab()
is O(n^2) and it grows too fast with the growth of containers
numbers.

Let we have 200 containers, and every container has 10 mounts
and 10 cgroups. All container tasks are isolated, and they don't
touch foreign containers mounts.

In case of global reclaim, a task has to iterate all over the memcgs
and to call all the memcg-aware shrinkers for all of them. This means,
the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
and since there are 2000 memcgs, the total calls of do_shrink_slab()
are 2000 * 2000 = 4000000.

4 million calls are not a number operations, which can takes 1 cpu cycle.
E.g., super_cache_count() accesses at least two lists, and makes arifmetical
calculations. Even, if there are no charged objects, we do these calculations,
and replaces cpu caches by read memory. I observed nodes spending almost 100%
time in kernel, in case of intensive writing and global reclaim. The writer
consumes pages fast, but it's need to shrink_slab() before the reclaimer
reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
there is no writing, the iterations just waste the time, and slows reclaim down.

Let's see the small test below:

$echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
$mkdir /sys/fs/cgroup/memory/ct
$echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
$for i in `seq 0 4000`;
	do mkdir /sys/fs/cgroup/memory/ct/$i;
	echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
	mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
done

Then, let's see drop caches time (5 sequential calls):
$time echo 3 > /proc/sys/vm/drop_caches

0.00user 13.78system 0:13.78elapsed 99%CPU
0.00user 5.59system 0:05.60elapsed 99%CPU
0.00user 5.48system 0:05.48elapsed 99%CPU
0.00user 8.35system 0:08.35elapsed 99%CPU
0.00user 8.34system 0:08.35elapsed 99%CPU


Last four calls don't actually shrink something. So, the iterations
over slab shrinkers take 5.48 seconds. Not so good for scalability.

The patchset solves the problem by making shrink_slab() of O(n)
complexity. There are following functional actions:

1)Assign id to every registered memcg-aware shrinker.
2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
  and set a shrinker-related bit after the first element
  is added to lru list (also, when removed child memcg
  elements are reparanted).
3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
  and call a shrinker if its bit is set in memcg's shrinker
  bitmap.
  (Also, there is a functionality to clear the bit, after
  last element is shrinked).

This gives signify performance increase. The result after patchset is applied:

$time echo 3 > /proc/sys/vm/drop_caches

0.00user 1.10system 0:01.10elapsed 99%CPU
0.00user 0.00system 0:00.01elapsed 64%CPU
0.00user 0.01system 0:00.01elapsed 82%CPU
0.00user 0.00system 0:00.01elapsed 64%CPU
0.00user 0.01system 0:00.01elapsed 82%CPU

The results show the performance increases at least in 548 times.

So, the patchset makes shrink_slab() of less complexity and improves
the performance in such types of load I pointed. This will give a profit
in case of !global reclaim case, since there also will be less
do_shrink_slab() calls.

This patchset is made against linux-next.git tree.

v7: Refactorings and readability improvements.

v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
    Use different functions for allocation and expanding map.
    Use new memcg_shrinker_map_size variable in memcontrol.c.
    Refactorings.

v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB

v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups

v3: Many changes requested in commentaries to v2:

1)rebase on prealloc_shrinker() code base
2)root_mem_cgroup is made out of memcg maps
3)rwsem replaced with shrinkers_nr_max_mutex
4)changes around assignment of shrinker id to list lru
5)everything renamed

v2: Many changes requested in commentaries to v1:

1)the code mostly moved to mm/memcontrol.c;
2)using IDR instead of array of shrinkers;
3)added a possibility to assign list_lru shrinker id
  at the time of shrinker registering;
4)reorginized locking and renamed functions and variables.

---

Kirill Tkhai (16):
      list_lru: Combine code under the same define
      mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
      mm: Assign id to every memcg-aware shrinker
      memcg: Move up for_each_mem_cgroup{,_tree} defines
      mm: Assign memcg-aware shrinkers bitmap to memcg
      mm: Refactoring in workingset_init()
      fs: Refactoring in alloc_super()
      fs: Propagate shrinker::id to list_lru
      list_lru: Add memcg argument to list_lru_from_kmem()
      list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
      list_lru: Pass lru argument to memcg_drain_list_lru_node()
      mm: Export mem_cgroup_is_root()
      mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
      mm: Iterate only over charged shrinkers during memcg shrink_slab()
      mm: Add SHRINK_EMPTY shrinker methods return value
      mm: Clear shrinker bit if there are no objects related to memcg

Vladimir Davydov (1):
      mm: Generalize shrink_slab() calls in shrink_node()


 fs/super.c                 |   11 ++
 include/linux/list_lru.h   |   18 ++--
 include/linux/memcontrol.h |   46 +++++++++-
 include/linux/sched.h      |    2 
 include/linux/shrinker.h   |   11 ++
 include/linux/slab.h       |    2 
 init/Kconfig               |    5 +
 mm/list_lru.c              |   90 ++++++++++++++-----
 mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
 mm/slab.h                  |    6 +
 mm/slab_common.c           |    8 +-
 mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
 mm/workingset.c            |   11 ++
 13 files changed, 478 insertions(+), 109 deletions(-)

--
Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 01/17] list_lru: Combine code under the same define
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
@ 2018-05-22 10:07 ` Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB Kirill Tkhai
                   ` (18 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:07 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

These two pairs of blocks of code are under
the same #ifdef #else #endif.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/list_lru.c |   18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

diff --git a/mm/list_lru.c b/mm/list_lru.c
index d9c84c5bda1d..37d712924e56 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -30,17 +30,7 @@ static void list_lru_unregister(struct list_lru *lru)
 	list_del(&lru->list);
 	mutex_unlock(&list_lrus_mutex);
 }
-#else
-static void list_lru_register(struct list_lru *lru)
-{
-}
-
-static void list_lru_unregister(struct list_lru *lru)
-{
-}
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
 static inline bool list_lru_memcg_aware(struct list_lru *lru)
 {
 	/*
@@ -90,6 +80,14 @@ list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
 	return list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
 }
 #else
+static void list_lru_register(struct list_lru *lru)
+{
+}
+
+static void list_lru_unregister(struct list_lru *lru)
+{
+}
+
 static inline bool list_lru_memcg_aware(struct list_lru *lru)
 {
 	return false;

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 01/17] list_lru: Combine code under the same define Kirill Tkhai
@ 2018-05-22 10:07 ` Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
                   ` (17 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:07 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

This patch introduces new config option, which is used
to replace repeating CONFIG_MEMCG && !CONFIG_SLOB pattern.
Next patches add a little more memcg+kmem related code,
so let's keep the defines more clearly.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/list_lru.h   |    4 ++--
 include/linux/memcontrol.h |    6 +++---
 include/linux/sched.h      |    2 +-
 include/linux/slab.h       |    2 +-
 init/Kconfig               |    5 +++++
 mm/list_lru.c              |    8 ++++----
 mm/memcontrol.c            |   16 ++++++++--------
 mm/slab.h                  |    6 +++---
 mm/slab_common.c           |    8 ++++----
 9 files changed, 31 insertions(+), 26 deletions(-)

diff --git a/include/linux/list_lru.h b/include/linux/list_lru.h
index 96def9d15b1b..2d23b5b745be 100644
--- a/include/linux/list_lru.h
+++ b/include/linux/list_lru.h
@@ -42,7 +42,7 @@ struct list_lru_node {
 	spinlock_t		lock;
 	/* global list, used for the root cgroup in cgroup aware lrus */
 	struct list_lru_one	lru;
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 	/* for cgroup aware lrus points to per cgroup lists, otherwise NULL */
 	struct list_lru_memcg	__rcu *memcg_lrus;
 #endif
@@ -51,7 +51,7 @@ struct list_lru_node {
 
 struct list_lru {
 	struct list_lru_node	*node;
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 	struct list_head	list;
 #endif
 };
diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h
index c6d2ca859802..996469bc2b82 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -264,7 +264,7 @@ struct mem_cgroup {
 	bool			tcpmem_active;
 	int			tcpmem_pressure;
 
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
         /* Index in the kmem_cache->memcg_params.memcg_caches array */
 	int kmemcg_id;
 	enum memcg_kmem_state kmem_state;
@@ -1230,7 +1230,7 @@ int memcg_kmem_charge_memcg(struct page *page, gfp_t gfp, int order,
 int memcg_kmem_charge(struct page *page, gfp_t gfp, int order);
 void memcg_kmem_uncharge(struct page *page, int order);
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 extern struct static_key_false memcg_kmem_enabled_key;
 extern struct workqueue_struct *memcg_kmem_cache_wq;
 
@@ -1283,6 +1283,6 @@ static inline void memcg_put_cache_ids(void)
 {
 }
 
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 #endif /* _LINUX_MEMCONTROL_H */
diff --git a/include/linux/sched.h b/include/linux/sched.h
index c4e70e8481c3..0ccdbdec1e5b 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -722,7 +722,7 @@ struct task_struct {
 #endif
 #ifdef CONFIG_MEMCG
 	unsigned			memcg_may_oom:1;
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 	unsigned			memcg_kmem_skip_account:1;
 #endif
 #endif
diff --git a/include/linux/slab.h b/include/linux/slab.h
index 9ebe659bd4a5..5b63d08a0e43 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -97,7 +97,7 @@
 # define SLAB_FAILSLAB		0
 #endif
 /* Account to memcg */
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 # define SLAB_ACCOUNT		((slab_flags_t __force)0x04000000U)
 #else
 # define SLAB_ACCOUNT		0
diff --git a/init/Kconfig b/init/Kconfig
index 44e62e0dc51f..bcea6671a3ff 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -680,6 +680,11 @@ config MEMCG_SWAP_ENABLED
 	  select this option (if, for some reason, they need to disable it
 	  then swapaccount=0 does the trick).
 
+config MEMCG_KMEM
+	bool
+	depends on MEMCG && !SLOB
+	default y
+
 config BLK_CGROUP
 	bool "IO controller"
 	depends on BLOCK
diff --git a/mm/list_lru.c b/mm/list_lru.c
index 37d712924e56..232bb637cf02 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -13,7 +13,7 @@
 #include <linux/mutex.h>
 #include <linux/memcontrol.h>
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 static LIST_HEAD(list_lrus);
 static DEFINE_MUTEX(list_lrus_mutex);
 
@@ -104,7 +104,7 @@ list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
 {
 	return &nlru->lru;
 }
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 bool list_lru_add(struct list_lru *lru, struct list_head *item)
 {
@@ -297,7 +297,7 @@ static void init_one_lru(struct list_lru_one *l)
 	l->nr_items = 0;
 }
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 static void __memcg_destroy_list_lru_node(struct list_lru_memcg *memcg_lrus,
 					  int begin, int end)
 {
@@ -556,7 +556,7 @@ static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
 static void memcg_destroy_list_lru(struct list_lru *lru)
 {
 }
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 int __list_lru_init(struct list_lru *lru, bool memcg_aware,
 		    struct lock_class_key *key)
diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index bdb8028c806c..fc67e43849eb 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -251,7 +251,7 @@ static inline bool mem_cgroup_is_root(struct mem_cgroup *memcg)
 	return (memcg == root_mem_cgroup);
 }
 
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 /*
  * This will be the memcg's index in each cache's ->memcg_params.memcg_caches.
  * The main reason for not using cgroup id for this:
@@ -305,7 +305,7 @@ EXPORT_SYMBOL(memcg_kmem_enabled_key);
 
 struct workqueue_struct *memcg_kmem_cache_wq;
 
-#endif /* !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 /**
  * mem_cgroup_css_from_page - css of the memcg associated with a page
@@ -2123,7 +2123,7 @@ static void commit_charge(struct page *page, struct mem_cgroup *memcg,
 		unlock_page_lru(page, isolated);
 }
 
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 static int memcg_alloc_cache_id(void)
 {
 	int id, size;
@@ -2388,7 +2388,7 @@ void memcg_kmem_uncharge(struct page *page, int order)
 
 	css_put_many(&memcg->css, nr_pages);
 }
-#endif /* !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
 
@@ -3001,7 +3001,7 @@ static u64 mem_cgroup_read_u64(struct cgroup_subsys_state *css,
 	}
 }
 
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 static int memcg_online_kmem(struct mem_cgroup *memcg)
 {
 	int memcg_id;
@@ -3101,7 +3101,7 @@ static void memcg_offline_kmem(struct mem_cgroup *memcg)
 static void memcg_free_kmem(struct mem_cgroup *memcg)
 {
 }
-#endif /* !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 static int memcg_update_kmem_max(struct mem_cgroup *memcg,
 				 unsigned long max)
@@ -4405,7 +4405,7 @@ static struct mem_cgroup *mem_cgroup_alloc(void)
 	INIT_LIST_HEAD(&memcg->event_list);
 	spin_lock_init(&memcg->event_list_lock);
 	memcg->socket_pressure = jiffies;
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 	memcg->kmemcg_id = -1;
 #endif
 #ifdef CONFIG_CGROUP_WRITEBACK
@@ -6322,7 +6322,7 @@ static int __init mem_cgroup_init(void)
 {
 	int cpu, node;
 
-#ifndef CONFIG_SLOB
+#ifdef CONFIG_MEMCG_KMEM
 	/*
 	 * Kmem cache creation is mostly done with the slab_mutex held,
 	 * so use a workqueue with limited concurrency to avoid stalling
diff --git a/mm/slab.h b/mm/slab.h
index 68bdf498da3b..58c6c1c2a78e 100644
--- a/mm/slab.h
+++ b/mm/slab.h
@@ -203,7 +203,7 @@ ssize_t slabinfo_write(struct file *file, const char __user *buffer,
 void __kmem_cache_free_bulk(struct kmem_cache *, size_t, void **);
 int __kmem_cache_alloc_bulk(struct kmem_cache *, gfp_t, size_t, void **);
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 
 /* List of all root caches. */
 extern struct list_head		slab_root_caches;
@@ -296,7 +296,7 @@ extern void memcg_link_cache(struct kmem_cache *s);
 extern void slab_deactivate_memcg_cache_rcu_sched(struct kmem_cache *s,
 				void (*deact_fn)(struct kmem_cache *));
 
-#else /* CONFIG_MEMCG && !CONFIG_SLOB */
+#else /* CONFIG_MEMCG_KMEM */
 
 /* If !memcg, all caches are root. */
 #define slab_root_caches	slab_caches
@@ -351,7 +351,7 @@ static inline void memcg_link_cache(struct kmem_cache *s)
 {
 }
 
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 static inline struct kmem_cache *cache_from_obj(struct kmem_cache *s, void *x)
 {
diff --git a/mm/slab_common.c b/mm/slab_common.c
index b0dd9db1eb2f..400e26697bb6 100644
--- a/mm/slab_common.c
+++ b/mm/slab_common.c
@@ -127,7 +127,7 @@ int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t nr,
 	return i;
 }
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 
 LIST_HEAD(slab_root_caches);
 
@@ -255,7 +255,7 @@ static inline void destroy_memcg_params(struct kmem_cache *s)
 static inline void memcg_unlink_cache(struct kmem_cache *s)
 {
 }
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 /*
  * Figure out what the alignment of the objects will be given a set of
@@ -579,7 +579,7 @@ static int shutdown_cache(struct kmem_cache *s)
 	return 0;
 }
 
-#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
+#ifdef CONFIG_MEMCG_KMEM
 /*
  * memcg_create_kmem_cache - Create a cache for a memory cgroup.
  * @memcg: The memory cgroup the new cache is for.
@@ -828,7 +828,7 @@ static inline int shutdown_memcg_caches(struct kmem_cache *s)
 {
 	return 0;
 }
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 void slab_kmem_cache_release(struct kmem_cache *s)
 {

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 03/17] mm: Assign id to every memcg-aware shrinker
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 01/17] list_lru: Combine code under the same define Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB Kirill Tkhai
@ 2018-05-22 10:07 ` Kirill Tkhai
  2018-05-22 10:07 ` [PATCH v7 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
                   ` (16 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:07 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

The patch introduces shrinker::id number, which is used to enumerate
memcg-aware shrinkers. The number start from 0, and the code tries
to maintain it as small as possible.

This will be used as to represent a memcg-aware shrinkers in memcg
shrinkers map.

Since all memcg-aware shrinkers are based on list_lru, which is per-memcg
in case of !CONFIG_MEMCG_KMEM only, the new functionality will be under
this config option.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/shrinker.h |    4 +++
 mm/vmscan.c              |   62 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 66 insertions(+)

diff --git a/include/linux/shrinker.h b/include/linux/shrinker.h
index 6794490f25b2..7ca9c18cf130 100644
--- a/include/linux/shrinker.h
+++ b/include/linux/shrinker.h
@@ -66,6 +66,10 @@ struct shrinker {
 
 	/* These are for internal use */
 	struct list_head list;
+#ifdef CONFIG_MEMCG_KMEM
+	/* ID in shrinker_idr */
+	int id;
+#endif
 	/* objs pending delete, per node */
 	atomic_long_t *nr_deferred;
 };
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 50055d72f294..75b00e6ff9db 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -169,6 +169,49 @@ unsigned long vm_total_pages;
 static LIST_HEAD(shrinker_list);
 static DECLARE_RWSEM(shrinker_rwsem);
 
+#ifdef CONFIG_MEMCG_KMEM
+static DEFINE_IDR(shrinker_idr);
+static int shrinker_nr_max;
+
+static int prealloc_memcg_shrinker(struct shrinker *shrinker)
+{
+	int id, ret = -ENOMEM;
+
+	down_write(&shrinker_rwsem);
+	id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
+	if (id < 0)
+		goto unlock;
+
+	if (id >= shrinker_nr_max)
+		shrinker_nr_max = id + 1;
+	shrinker->id = id;
+	ret = 0;
+unlock:
+	up_write(&shrinker_rwsem);
+	return ret;
+}
+
+static void unregister_memcg_shrinker(struct shrinker *shrinker)
+{
+	int id = shrinker->id;
+
+	BUG_ON(id < 0);
+
+	down_write(&shrinker_rwsem);
+	idr_remove(&shrinker_idr, id);
+	up_write(&shrinker_rwsem);
+}
+#else /* CONFIG_MEMCG_KMEM */
+static int prealloc_memcg_shrinker(struct shrinker *shrinker)
+{
+	return 0;
+}
+
+static void unregister_memcg_shrinker(struct shrinker *shrinker)
+{
+}
+#endif /* CONFIG_MEMCG_KMEM */
+
 #ifdef CONFIG_MEMCG
 static bool global_reclaim(struct scan_control *sc)
 {
@@ -313,13 +356,30 @@ int prealloc_shrinker(struct shrinker *shrinker)
 	shrinker->nr_deferred = kzalloc(size, GFP_KERNEL);
 	if (!shrinker->nr_deferred)
 		return -ENOMEM;
+
+	if (shrinker->flags & SHRINKER_MEMCG_AWARE) {
+		if (prealloc_memcg_shrinker(shrinker))
+			goto free_deferred;
+	}
+
 	return 0;
+
+free_deferred:
+	kfree(shrinker->nr_deferred);
+	shrinker->nr_deferred = NULL;
+	return -ENOMEM;
 }
 
 void free_prealloced_shrinker(struct shrinker *shrinker)
 {
+	if (!shrinker->nr_deferred)
+		return;
+
 	kfree(shrinker->nr_deferred);
 	shrinker->nr_deferred = NULL;
+
+	if (shrinker->flags & SHRINKER_MEMCG_AWARE)
+		unregister_memcg_shrinker(shrinker);
 }
 
 void register_shrinker_prepared(struct shrinker *shrinker)
@@ -347,6 +407,8 @@ void unregister_shrinker(struct shrinker *shrinker)
 {
 	if (!shrinker->nr_deferred)
 		return;
+	if (shrinker->flags & SHRINKER_MEMCG_AWARE)
+		unregister_memcg_shrinker(shrinker);
 	down_write(&shrinker_rwsem);
 	list_del(&shrinker->list);
 	up_write(&shrinker_rwsem);

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (2 preceding siblings ...)
  2018-05-22 10:07 ` [PATCH v7 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
@ 2018-05-22 10:07 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
                   ` (15 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:07 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Next patch requires these defines are above their current
position, so here they are moved to declarations.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/memcontrol.c |   30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index fc67e43849eb..023a1e9c900e 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -233,6 +233,21 @@ enum res_type {
 /* Used for OOM nofiier */
 #define OOM_CONTROL		(0)
 
+/*
+ * Iteration constructs for visiting all cgroups (under a tree).  If
+ * loops are exited prematurely (break), mem_cgroup_iter_break() must
+ * be used for reference counting.
+ */
+#define for_each_mem_cgroup_tree(iter, root)		\
+	for (iter = mem_cgroup_iter(root, NULL, NULL);	\
+	     iter != NULL;				\
+	     iter = mem_cgroup_iter(root, iter, NULL))
+
+#define for_each_mem_cgroup(iter)			\
+	for (iter = mem_cgroup_iter(NULL, NULL, NULL);	\
+	     iter != NULL;				\
+	     iter = mem_cgroup_iter(NULL, iter, NULL))
+
 /* Some nice accessors for the vmpressure. */
 struct vmpressure *memcg_to_vmpressure(struct mem_cgroup *memcg)
 {
@@ -867,21 +882,6 @@ static void invalidate_reclaim_iterators(struct mem_cgroup *dead_memcg)
 	}
 }
 
-/*
- * Iteration constructs for visiting all cgroups (under a tree).  If
- * loops are exited prematurely (break), mem_cgroup_iter_break() must
- * be used for reference counting.
- */
-#define for_each_mem_cgroup_tree(iter, root)		\
-	for (iter = mem_cgroup_iter(root, NULL, NULL);	\
-	     iter != NULL;				\
-	     iter = mem_cgroup_iter(root, iter, NULL))
-
-#define for_each_mem_cgroup(iter)			\
-	for (iter = mem_cgroup_iter(NULL, NULL, NULL);	\
-	     iter != NULL;				\
-	     iter = mem_cgroup_iter(NULL, iter, NULL))
-
 /**
  * mem_cgroup_scan_tasks - iterate over tasks of a memory cgroup hierarchy
  * @memcg: hierarchy root

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (3 preceding siblings ...)
  2018-05-22 10:07 ` [PATCH v7 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 06/17] mm: Refactoring in workingset_init() Kirill Tkhai
                   ` (14 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Imagine a big node with many cpus, memory cgroups and containers.
Let we have 200 containers, every container has 10 mounts,
and 10 cgroups. All container tasks don't touch foreign
containers mounts. If there is intensive pages write,
and global reclaim happens, a writing task has to iterate
over all memcgs to shrink slab, before it's able to go
to shrink_page_list().

Iteration over all the memcg slabs is very expensive:
the task has to visit 200 * 10 = 2000 shrinkers
for every memcg, and since there are 2000 memcgs,
the total calls are 2000 * 2000 = 4000000.

So, the shrinker makes 4 million do_shrink_slab() calls
just to try to isolate SWAP_CLUSTER_MAX pages in one
of the actively writing memcg via shrink_page_list().
I've observed a node spending almost 100% in kernel,
making useless iteration over already shrinked slab.

This patch adds bitmap of memcg-aware shrinkers to memcg.
The size of the bitmap depends on bitmap_nr_ids, and during
memcg life it's maintained to be enough to fit bitmap_nr_ids
shrinkers. Every bit in the map is related to corresponding
shrinker id.

Next patches will maintain set bit only for really charged
memcg. This will allow shrink_slab() to increase its
performance in significant way. See the last patch for
the numbers.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/memcontrol.h |   14 +++++
 mm/memcontrol.c            |  120 ++++++++++++++++++++++++++++++++++++++++++++
 mm/vmscan.c                |    5 ++
 3 files changed, 139 insertions(+)

diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h
index 996469bc2b82..e51c6e953d7a 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -112,6 +112,15 @@ struct lruvec_stat {
 	long count[NR_VM_NODE_STAT_ITEMS];
 };
 
+/*
+ * Bitmap of shrinker::id corresponding to memcg-aware shrinkers,
+ * which have elements charged to this memcg.
+ */
+struct memcg_shrinker_map {
+	struct rcu_head rcu;
+	unsigned long map[0];
+};
+
 /*
  * per-zone information in memory controller.
  */
@@ -125,6 +134,9 @@ struct mem_cgroup_per_node {
 
 	struct mem_cgroup_reclaim_iter	iter[DEF_PRIORITY + 1];
 
+#ifdef CONFIG_MEMCG_KMEM
+	struct memcg_shrinker_map __rcu	*shrinker_map;
+#endif
 	struct rb_node		tree_node;	/* RB tree node */
 	unsigned long		usage_in_excess;/* Set to the value by which */
 						/* the soft limit is exceeded*/
@@ -1261,6 +1273,8 @@ static inline int memcg_cache_id(struct mem_cgroup *memcg)
 	return memcg ? memcg->kmemcg_id : -1;
 }
 
+extern int memcg_expand_shrinker_maps(int new_id);
+
 #else
 #define for_each_memcg_cache_index(_idx)	\
 	for (; NULL; )
diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index 023a1e9c900e..b454f077de44 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -320,6 +320,120 @@ EXPORT_SYMBOL(memcg_kmem_enabled_key);
 
 struct workqueue_struct *memcg_kmem_cache_wq;
 
+static int memcg_shrinker_map_size;
+static DEFINE_MUTEX(memcg_shrinker_map_mutex);
+
+static void memcg_free_shrinker_map_rcu(struct rcu_head *head)
+{
+	kvfree(container_of(head, struct memcg_shrinker_map, rcu));
+}
+
+static int memcg_expand_one_shrinker_map(struct mem_cgroup *memcg,
+					 int size, int old_size)
+{
+	struct memcg_shrinker_map *new, *old;
+	int nid;
+
+	lockdep_assert_held(&memcg_shrinker_map_mutex);
+
+	for_each_node(nid) {
+		old = rcu_dereference_protected(
+			mem_cgroup_nodeinfo(memcg, nid)->shrinker_map, true);
+		/* Not yet online memcg */
+		if (!old)
+			return 0;
+
+		new = kvmalloc(sizeof(*new) + size, GFP_KERNEL);
+		if (!new)
+			return -ENOMEM;
+
+		/* Set all old bits, clear all new bits */
+		memset(new->map, (int)0xff, old_size);
+		memset((void *)new->map + old_size, 0, size - old_size);
+
+		rcu_assign_pointer(memcg->nodeinfo[nid]->shrinker_map, new);
+		if (old)
+			call_rcu(&old->rcu, memcg_free_shrinker_map_rcu);
+	}
+
+	return 0;
+}
+
+static void memcg_free_shrinker_maps(struct mem_cgroup *memcg)
+{
+	struct mem_cgroup_per_node *pn;
+	struct memcg_shrinker_map *map;
+	int nid;
+
+	if (mem_cgroup_is_root(memcg))
+		return;
+
+	for_each_node(nid) {
+		pn = mem_cgroup_nodeinfo(memcg, nid);
+		map = rcu_dereference_protected(pn->shrinker_map, true);
+		if (map)
+			kvfree(map);
+		rcu_assign_pointer(pn->shrinker_map, NULL);
+	}
+}
+
+static int memcg_alloc_shrinker_maps(struct mem_cgroup *memcg)
+{
+	struct memcg_shrinker_map *map;
+	int nid, size, ret = 0;
+
+	if (mem_cgroup_is_root(memcg))
+		return 0;
+
+	mutex_lock(&memcg_shrinker_map_mutex);
+	size = memcg_shrinker_map_size;
+	for_each_node(nid) {
+		map = kvzalloc(sizeof(*map) + size, GFP_KERNEL);
+		if (!map) {
+			memcg_free_shrinker_maps(memcg);
+			ret = -ENOMEM;
+			break;
+		}
+		rcu_assign_pointer(memcg->nodeinfo[nid]->shrinker_map, map);
+	}
+	mutex_unlock(&memcg_shrinker_map_mutex);
+
+	return ret;
+}
+
+int memcg_expand_shrinker_maps(int new_id)
+{
+	int size, old_size, ret = 0;
+	struct mem_cgroup *memcg;
+
+	size = DIV_ROUND_UP(new_id + 1, BITS_PER_BYTE);
+	old_size = memcg_shrinker_map_size;
+	if (size <= old_size)
+		return 0;
+
+	mutex_lock(&memcg_shrinker_map_mutex);
+	if (!root_mem_cgroup)
+		goto unlock;
+
+	for_each_mem_cgroup(memcg) {
+		if (mem_cgroup_is_root(memcg))
+			continue;
+		ret = memcg_expand_one_shrinker_map(memcg, size, old_size);
+		if (ret)
+			goto unlock;
+	}
+unlock:
+	if (!ret)
+		memcg_shrinker_map_size = size;
+	mutex_unlock(&memcg_shrinker_map_mutex);
+	return ret;
+}
+#else /* CONFIG_MEMCG_KMEM */
+static int memcg_alloc_shrinker_maps(struct mem_cgroup *memcg)
+{
+	return 0;
+}
+static void memcg_free_shrinker_maps(struct mem_cgroup *memcg) { }
 #endif /* CONFIG_MEMCG_KMEM */
 
 /**
@@ -4482,6 +4596,11 @@ static int mem_cgroup_css_online(struct cgroup_subsys_state *css)
 {
 	struct mem_cgroup *memcg = mem_cgroup_from_css(css);
 
+	if (memcg_alloc_shrinker_maps(memcg)) {
+		mem_cgroup_id_remove(memcg);
+		return -ENOMEM;
+	}
+
 	/* Online state pins memcg ID, memcg ID pins CSS */
 	atomic_set(&memcg->id.ref, 1);
 	css_get(css);
@@ -4534,6 +4653,7 @@ static void mem_cgroup_css_free(struct cgroup_subsys_state *css)
 	vmpressure_cleanup(&memcg->vmpressure);
 	cancel_work_sync(&memcg->high_work);
 	mem_cgroup_remove_from_trees(memcg);
+	memcg_free_shrinker_maps(memcg);
 	memcg_free_kmem(memcg);
 	mem_cgroup_free(memcg);
 }
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 75b00e6ff9db..d8a1ca350a58 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -182,6 +182,11 @@ static int prealloc_memcg_shrinker(struct shrinker *shrinker)
 	if (id < 0)
 		goto unlock;
 
+	if (memcg_expand_shrinker_maps(id)) {
+		idr_remove(&shrinker_idr, id);
+		goto unlock;
+	}
+
 	if (id >= shrinker_nr_max)
 		shrinker_nr_max = id + 1;
 	shrinker->id = id;

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 06/17] mm: Refactoring in workingset_init()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (4 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 07/17] fs: Refactoring in alloc_super() Kirill Tkhai
                   ` (13 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Use prealloc_shrinker()/register_shrinker_prepared()
instead of register_shrinker(). This will be used
in next patch.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/workingset.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/mm/workingset.c b/mm/workingset.c
index 40ee02c83978..c3a4fe145bb7 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -528,15 +528,16 @@ 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(&shadow_nodes, true, &shadow_nodes_key);
+	ret = prealloc_shrinker(&workingset_shadow_shrinker);
 	if (ret)
 		goto err;
-	ret = register_shrinker(&workingset_shadow_shrinker);
+	ret = __list_lru_init(&shadow_nodes, true, &shadow_nodes_key);
 	if (ret)
 		goto err_list_lru;
+	register_shrinker_prepared(&workingset_shadow_shrinker);
 	return 0;
 err_list_lru:
-	list_lru_destroy(&shadow_nodes);
+	free_prealloced_shrinker(&workingset_shadow_shrinker);
 err:
 	return ret;
 }

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 07/17] fs: Refactoring in alloc_super()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (5 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 06/17] mm: Refactoring in workingset_init() Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 08/17] fs: Propagate shrinker::id to list_lru Kirill Tkhai
                   ` (12 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Do two list_lru_init_memcg() calls after prealloc_super().
destroy_unused_super() in fail path is OK with this.
Next patch needs such the order.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 fs/super.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index 50728d9c1a05..78227c4ddb21 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -244,10 +244,6 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags,
 	INIT_LIST_HEAD(&s->s_inodes_wb);
 	spin_lock_init(&s->s_inode_wblist_lock);
 
-	if (list_lru_init_memcg(&s->s_dentry_lru))
-		goto fail;
-	if (list_lru_init_memcg(&s->s_inode_lru))
-		goto fail;
 	s->s_count = 1;
 	atomic_set(&s->s_active, 1);
 	mutex_init(&s->s_vfs_rename_mutex);
@@ -265,6 +261,10 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags,
 	s->s_shrink.flags = SHRINKER_NUMA_AWARE | SHRINKER_MEMCG_AWARE;
 	if (prealloc_shrinker(&s->s_shrink))
 		goto fail;
+	if (list_lru_init_memcg(&s->s_dentry_lru))
+		goto fail;
+	if (list_lru_init_memcg(&s->s_inode_lru))
+		goto fail;
 	return s;
 
 fail:

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 08/17] fs: Propagate shrinker::id to list_lru
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (6 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 07/17] fs: Refactoring in alloc_super() Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 09/17] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
                   ` (11 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

The patch adds list_lru::shrinker_id field, and populates
it by registered shrinker id.

This will be used to set correct bit in memcg shrinkers
map by lru code in next patches, after there appeared
the first related to memcg element in list_lru.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 fs/super.c               |    4 ++--
 include/linux/list_lru.h |   14 +++++++++-----
 mm/list_lru.c            |   11 ++++++++++-
 mm/workingset.c          |    3 ++-
 4 files changed, 23 insertions(+), 9 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index 78227c4ddb21..f5f96e52e0cd 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -261,9 +261,9 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags,
 	s->s_shrink.flags = SHRINKER_NUMA_AWARE | SHRINKER_MEMCG_AWARE;
 	if (prealloc_shrinker(&s->s_shrink))
 		goto fail;
-	if (list_lru_init_memcg(&s->s_dentry_lru))
+	if (list_lru_init_memcg(&s->s_dentry_lru, &s->s_shrink))
 		goto fail;
-	if (list_lru_init_memcg(&s->s_inode_lru))
+	if (list_lru_init_memcg(&s->s_inode_lru, &s->s_shrink))
 		goto fail;
 	return s;
 
diff --git a/include/linux/list_lru.h b/include/linux/list_lru.h
index 2d23b5b745be..9e75bb33766b 100644
--- a/include/linux/list_lru.h
+++ b/include/linux/list_lru.h
@@ -53,16 +53,20 @@ struct list_lru {
 	struct list_lru_node	*node;
 #ifdef CONFIG_MEMCG_KMEM
 	struct list_head	list;
+	int			shrinker_id;
 #endif
 };
 
 void list_lru_destroy(struct list_lru *lru);
 int __list_lru_init(struct list_lru *lru, bool memcg_aware,
-		    struct lock_class_key *key);
-
-#define list_lru_init(lru)		__list_lru_init((lru), false, NULL)
-#define list_lru_init_key(lru, key)	__list_lru_init((lru), false, (key))
-#define list_lru_init_memcg(lru)	__list_lru_init((lru), true, NULL)
+		    struct lock_class_key *key, struct shrinker *shrinker);
+
+#define list_lru_init(lru)				\
+	__list_lru_init((lru), false, NULL, NULL)
+#define list_lru_init_key(lru, key)			\
+	__list_lru_init((lru), false, (key), NULL)
+#define list_lru_init_memcg(lru, shrinker)		\
+	__list_lru_init((lru), true, NULL, shrinker)
 
 int memcg_update_all_list_lrus(int num_memcgs);
 void memcg_drain_all_list_lrus(int src_idx, int dst_idx);
diff --git a/mm/list_lru.c b/mm/list_lru.c
index 232bb637cf02..dde9ecae7cb5 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -559,12 +559,18 @@ static void memcg_destroy_list_lru(struct list_lru *lru)
 #endif /* CONFIG_MEMCG_KMEM */
 
 int __list_lru_init(struct list_lru *lru, bool memcg_aware,
-		    struct lock_class_key *key)
+		    struct lock_class_key *key, struct shrinker *shrinker)
 {
 	int i;
 	size_t size = sizeof(*lru->node) * nr_node_ids;
 	int err = -ENOMEM;
 
+#ifdef CONFIG_MEMCG_KMEM
+	if (shrinker)
+		lru->shrinker_id = shrinker->id;
+	else
+		lru->shrinker_id = -1;
+#endif
 	memcg_get_cache_ids();
 
 	lru->node = kzalloc(size, GFP_KERNEL);
@@ -607,6 +613,9 @@ void list_lru_destroy(struct list_lru *lru)
 	kfree(lru->node);
 	lru->node = NULL;
 
+#ifdef CONFIG_MEMCG_KMEM
+	lru->shrinker_id = -1;
+#endif
 	memcg_put_cache_ids();
 }
 EXPORT_SYMBOL_GPL(list_lru_destroy);
diff --git a/mm/workingset.c b/mm/workingset.c
index c3a4fe145bb7..79099bc5c256 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -531,7 +531,8 @@ static int __init workingset_init(void)
 	ret = prealloc_shrinker(&workingset_shadow_shrinker);
 	if (ret)
 		goto err;
-	ret = __list_lru_init(&shadow_nodes, true, &shadow_nodes_key);
+	ret = __list_lru_init(&shadow_nodes, true, &shadow_nodes_key,
+			      &workingset_shadow_shrinker);
 	if (ret)
 		goto err_list_lru;
 	register_shrinker_prepared(&workingset_shadow_shrinker);

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 09/17] list_lru: Add memcg argument to list_lru_from_kmem()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (7 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 08/17] fs: Propagate shrinker::id to list_lru Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:08 ` [PATCH v7 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
                   ` (10 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

This is just refactoring to allow next patches to have
memcg pointer in list_lru_from_kmem().

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/list_lru.c |   25 +++++++++++++++++--------
 1 file changed, 17 insertions(+), 8 deletions(-)

diff --git a/mm/list_lru.c b/mm/list_lru.c
index dde9ecae7cb5..151fa77eb7c9 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -66,18 +66,24 @@ static __always_inline struct mem_cgroup *mem_cgroup_from_kmem(void *ptr)
 }
 
 static inline struct list_lru_one *
-list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
+list_lru_from_kmem(struct list_lru_node *nlru, void *ptr,
+		   struct mem_cgroup **memcg_ptr)
 {
-	struct mem_cgroup *memcg;
+	struct list_lru_one *l = &nlru->lru;
+	struct mem_cgroup *memcg = NULL;
 
 	if (!nlru->memcg_lrus)
-		return &nlru->lru;
+		goto out;
 
 	memcg = mem_cgroup_from_kmem(ptr);
 	if (!memcg)
-		return &nlru->lru;
+		goto out;
 
-	return list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
+	l = list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
+out:
+	if (memcg_ptr)
+		*memcg_ptr = memcg;
+	return l;
 }
 #else
 static void list_lru_register(struct list_lru *lru)
@@ -100,8 +106,11 @@ list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
 }
 
 static inline struct list_lru_one *
-list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
+list_lru_from_kmem(struct list_lru_node *nlru, void *ptr,
+		   struct mem_cgroup **memcg_ptr)
 {
+	if (memcg_ptr)
+		*memcg_ptr = NULL;
 	return &nlru->lru;
 }
 #endif /* CONFIG_MEMCG_KMEM */
@@ -114,7 +123,7 @@ bool list_lru_add(struct list_lru *lru, struct list_head *item)
 
 	spin_lock(&nlru->lock);
 	if (list_empty(item)) {
-		l = list_lru_from_kmem(nlru, item);
+		l = list_lru_from_kmem(nlru, item, NULL);
 		list_add_tail(item, &l->list);
 		l->nr_items++;
 		nlru->nr_items++;
@@ -140,7 +149,7 @@ bool list_lru_del(struct list_lru *lru, struct list_head *item)
 
 	spin_lock(&nlru->lock);
 	if (!list_empty(item)) {
-		l = list_lru_from_kmem(nlru, item);
+		l = list_lru_from_kmem(nlru, item, NULL);
 		list_del_init(item);
 		l->nr_items--;
 		nlru->nr_items--;

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (8 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 09/17] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
@ 2018-05-22 10:08 ` Kirill Tkhai
  2018-05-22 10:09 ` [PATCH v7 11/17] list_lru: Pass lru " Kirill Tkhai
                   ` (9 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:08 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

This is just refactoring to allow next patches to have
dst_memcg pointer in memcg_drain_list_lru_node().

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/list_lru.h |    2 +-
 mm/list_lru.c            |   11 ++++++-----
 mm/memcontrol.c          |    2 +-
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/include/linux/list_lru.h b/include/linux/list_lru.h
index 9e75bb33766b..d9c16f2f2f00 100644
--- a/include/linux/list_lru.h
+++ b/include/linux/list_lru.h
@@ -69,7 +69,7 @@ int __list_lru_init(struct list_lru *lru, bool memcg_aware,
 	__list_lru_init((lru), true, NULL, shrinker)
 
 int memcg_update_all_list_lrus(int num_memcgs);
-void memcg_drain_all_list_lrus(int src_idx, int dst_idx);
+void memcg_drain_all_list_lrus(int src_idx, struct mem_cgroup *dst_memcg);
 
 /**
  * list_lru_add: add an element to the lru list's tail
diff --git a/mm/list_lru.c b/mm/list_lru.c
index 151fa77eb7c9..43cbec52a48a 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -515,8 +515,9 @@ int memcg_update_all_list_lrus(int new_size)
 }
 
 static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
-				      int src_idx, int dst_idx)
+				      int src_idx, struct mem_cgroup *dst_memcg)
 {
+	int dst_idx = dst_memcg->kmemcg_id;
 	struct list_lru_one *src, *dst;
 
 	/*
@@ -536,7 +537,7 @@ static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
 }
 
 static void memcg_drain_list_lru(struct list_lru *lru,
-				 int src_idx, int dst_idx)
+				 int src_idx, struct mem_cgroup *dst_memcg)
 {
 	int i;
 
@@ -544,16 +545,16 @@ static void memcg_drain_list_lru(struct list_lru *lru,
 		return;
 
 	for_each_node(i)
-		memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_idx);
+		memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_memcg);
 }
 
-void memcg_drain_all_list_lrus(int src_idx, int dst_idx)
+void memcg_drain_all_list_lrus(int src_idx, struct mem_cgroup *dst_memcg)
 {
 	struct list_lru *lru;
 
 	mutex_lock(&list_lrus_mutex);
 	list_for_each_entry(lru, &list_lrus, list)
-		memcg_drain_list_lru(lru, src_idx, dst_idx);
+		memcg_drain_list_lru(lru, src_idx, dst_memcg);
 	mutex_unlock(&list_lrus_mutex);
 }
 #else
diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index b454f077de44..a86dfeaa9aa1 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -3187,7 +3187,7 @@ static void memcg_offline_kmem(struct mem_cgroup *memcg)
 	}
 	rcu_read_unlock();
 
-	memcg_drain_all_list_lrus(kmemcg_id, parent->kmemcg_id);
+	memcg_drain_all_list_lrus(kmemcg_id, parent);
 
 	memcg_free_cache_id(kmemcg_id);
 }

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 11/17] list_lru: Pass lru argument to memcg_drain_list_lru_node()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (9 preceding siblings ...)
  2018-05-22 10:08 ` [PATCH v7 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
@ 2018-05-22 10:09 ` Kirill Tkhai
  2018-05-22 10:09 ` [PATCH v7 12/17] mm: Export mem_cgroup_is_root() Kirill Tkhai
                   ` (8 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:09 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

This is just refactoring to allow next patches to have
lru pointer in memcg_drain_list_lru_node().

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/list_lru.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/mm/list_lru.c b/mm/list_lru.c
index 43cbec52a48a..cab8fad7f7e2 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -514,9 +514,10 @@ int memcg_update_all_list_lrus(int new_size)
 	goto out;
 }
 
-static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
+static void memcg_drain_list_lru_node(struct list_lru *lru, int nid,
 				      int src_idx, struct mem_cgroup *dst_memcg)
 {
+	struct list_lru_node *nlru = &lru->node[nid];
 	int dst_idx = dst_memcg->kmemcg_id;
 	struct list_lru_one *src, *dst;
 
@@ -545,7 +546,7 @@ static void memcg_drain_list_lru(struct list_lru *lru,
 		return;
 
 	for_each_node(i)
-		memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_memcg);
+		memcg_drain_list_lru_node(lru, i, src_idx, dst_memcg);
 }
 
 void memcg_drain_all_list_lrus(int src_idx, struct mem_cgroup *dst_memcg)

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 12/17] mm: Export mem_cgroup_is_root()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (10 preceding siblings ...)
  2018-05-22 10:09 ` [PATCH v7 11/17] list_lru: Pass lru " Kirill Tkhai
@ 2018-05-22 10:09 ` Kirill Tkhai
  2018-05-22 10:09 ` [PATCH v7 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
                   ` (7 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:09 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

This will be used in next patch.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/memcontrol.h |   10 ++++++++++
 mm/memcontrol.c            |    5 -----
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h
index e51c6e953d7a..24abed028c6e 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -311,6 +311,11 @@ struct mem_cgroup {
 
 extern struct mem_cgroup *root_mem_cgroup;
 
+static inline bool mem_cgroup_is_root(struct mem_cgroup *memcg)
+{
+	return (memcg == root_mem_cgroup);
+}
+
 static inline bool mem_cgroup_disabled(void)
 {
 	return !cgroup_subsys_enabled(memory_cgrp_subsys);
@@ -780,6 +785,11 @@ void mem_cgroup_split_huge_fixup(struct page *head);
 
 struct mem_cgroup;
 
+static inline bool mem_cgroup_is_root(struct mem_cgroup *memcg)
+{
+	return true;
+}
+
 static inline bool mem_cgroup_disabled(void)
 {
 	return true;
diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index a86dfeaa9aa1..a886fc7398e9 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -261,11 +261,6 @@ struct cgroup_subsys_state *vmpressure_to_css(struct vmpressure *vmpr)
 	return &container_of(vmpr, struct mem_cgroup, vmpressure)->css;
 }
 
-static inline bool mem_cgroup_is_root(struct mem_cgroup *memcg)
-{
-	return (memcg == root_mem_cgroup);
-}
-
 #ifdef CONFIG_MEMCG_KMEM
 /*
  * This will be the memcg's index in each cache's ->memcg_params.memcg_caches.

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (11 preceding siblings ...)
  2018-05-22 10:09 ` [PATCH v7 12/17] mm: Export mem_cgroup_is_root() Kirill Tkhai
@ 2018-05-22 10:09 ` Kirill Tkhai
  2018-05-22 10:09 ` [PATCH v7 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
                   ` (6 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:09 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Introduce set_shrinker_bit() function to set shrinker-related
bit in memcg shrinker bitmap, and set the bit after the first
item is added and in case of reparenting destroyed memcg's items.

This will allow next patch to make shrinkers be called only,
in case of they have charged objects at the moment, and
to improve shrink_slab() performance.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/memcontrol.h |   14 ++++++++++++++
 mm/list_lru.c              |   22 ++++++++++++++++++++--
 2 files changed, 34 insertions(+), 2 deletions(-)

diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h
index 24abed028c6e..b3ae1373c99a 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -1285,6 +1285,18 @@ static inline int memcg_cache_id(struct mem_cgroup *memcg)
 
 extern int memcg_expand_shrinker_maps(int new_id);
 
+static inline void memcg_set_shrinker_bit(struct mem_cgroup *memcg,
+					  int nid, int shrinker_id)
+{
+	if (shrinker_id >= 0 && memcg && !mem_cgroup_is_root(memcg)) {
+		struct memcg_shrinker_map *map;
+
+		rcu_read_lock();
+		map = rcu_dereference(memcg->nodeinfo[nid]->shrinker_map);
+		set_bit(shrinker_id, map->map);
+		rcu_read_unlock();
+	}
+}
 #else
 #define for_each_memcg_cache_index(_idx)	\
 	for (; NULL; )
@@ -1307,6 +1319,8 @@ static inline void memcg_put_cache_ids(void)
 {
 }
 
+static inline void memcg_set_shrinker_bit(struct mem_cgroup *memcg,
+					  int nid, int shrinker_id) { }
 #endif /* CONFIG_MEMCG_KMEM */
 
 #endif /* _LINUX_MEMCONTROL_H */
diff --git a/mm/list_lru.c b/mm/list_lru.c
index cab8fad7f7e2..7df71ab0de1c 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -31,6 +31,11 @@ static void list_lru_unregister(struct list_lru *lru)
 	mutex_unlock(&list_lrus_mutex);
 }
 
+static int lru_shrinker_id(struct list_lru *lru)
+{
+	return lru->shrinker_id;
+}
+
 static inline bool list_lru_memcg_aware(struct list_lru *lru)
 {
 	/*
@@ -94,6 +99,11 @@ static void list_lru_unregister(struct list_lru *lru)
 {
 }
 
+static int lru_shrinker_id(struct list_lru *lru)
+{
+	return -1;
+}
+
 static inline bool list_lru_memcg_aware(struct list_lru *lru)
 {
 	return false;
@@ -119,13 +129,17 @@ bool list_lru_add(struct list_lru *lru, struct list_head *item)
 {
 	int nid = page_to_nid(virt_to_page(item));
 	struct list_lru_node *nlru = &lru->node[nid];
+	struct mem_cgroup *memcg;
 	struct list_lru_one *l;
 
 	spin_lock(&nlru->lock);
 	if (list_empty(item)) {
-		l = list_lru_from_kmem(nlru, item, NULL);
+		l = list_lru_from_kmem(nlru, item, &memcg);
 		list_add_tail(item, &l->list);
-		l->nr_items++;
+		/* Set shrinker bit if the first element was added */
+		if (!l->nr_items++)
+			memcg_set_shrinker_bit(memcg, nid,
+					       lru_shrinker_id(lru));
 		nlru->nr_items++;
 		spin_unlock(&nlru->lock);
 		return true;
@@ -520,6 +534,7 @@ static void memcg_drain_list_lru_node(struct list_lru *lru, int nid,
 	struct list_lru_node *nlru = &lru->node[nid];
 	int dst_idx = dst_memcg->kmemcg_id;
 	struct list_lru_one *src, *dst;
+	bool set;
 
 	/*
 	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
@@ -531,7 +546,10 @@ static void memcg_drain_list_lru_node(struct list_lru *lru, int nid,
 	dst = list_lru_from_memcg_idx(nlru, dst_idx);
 
 	list_splice_init(&src->list, &dst->list);
+	set = (!dst->nr_items && src->nr_items);
 	dst->nr_items += src->nr_items;
+	if (set)
+		memcg_set_shrinker_bit(dst_memcg, nid, lru_shrinker_id(lru));
 	src->nr_items = 0;
 
 	spin_unlock_irq(&nlru->lock);

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (12 preceding siblings ...)
  2018-05-22 10:09 ` [PATCH v7 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
@ 2018-05-22 10:09 ` Kirill Tkhai
  2018-05-22 10:09 ` [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
                   ` (5 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:09 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Using the preparations made in previous patches, in case of memcg
shrink, we may avoid shrinkers, which are not set in memcg's shrinkers
bitmap. To do that, we separate iterations over memcg-aware and
!memcg-aware shrinkers, and memcg-aware shrinkers are chosen
via for_each_set_bit() from the bitmap. In case of big nodes,
having many isolated environments, this gives significant
performance growth. See next patches for the details.

Note, that the patch does not respect to empty memcg shrinkers,
since we never clear the bitmap bits after we set it once.
Their shrinkers will be called again, with no shrinked objects
as result. This functionality is provided by next patches.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/vmscan.c |   87 +++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 78 insertions(+), 9 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index d8a1ca350a58..f26ca1e00efb 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -367,6 +367,20 @@ int prealloc_shrinker(struct shrinker *shrinker)
 			goto free_deferred;
 	}
 
+	/*
+	 * There is a window between prealloc_shrinker()
+	 * and register_shrinker_prepared(). We don't want
+	 * to clear bit of a shrinker in such the state
+	 * in shrink_slab_memcg(), since this will impose
+	 * restrictions on a code registering a shrinker
+	 * (they would have to guarantee, their LRU lists
+	 * are empty till shrinker is completely registered).
+	 * So, we differ the situation, when 1)a shrinker
+	 * is semi-registered (id is assigned, but it has
+	 * not yet linked to shrinker_list) and 2)shrinker
+	 * is not registered (id is not assigned).
+	 */
+	INIT_LIST_HEAD(&shrinker->list);
 	return 0;
 
 free_deferred:
@@ -541,6 +555,67 @@ static unsigned long do_shrink_slab(struct shrink_control *shrinkctl,
 	return freed;
 }
 
+#ifdef CONFIG_MEMCG_KMEM
+static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
+			struct mem_cgroup *memcg, int priority)
+{
+	struct memcg_shrinker_map *map;
+	unsigned long freed = 0;
+	int ret, i;
+
+	if (!memcg_kmem_enabled() || !mem_cgroup_online(memcg))
+		return 0;
+
+	if (!down_read_trylock(&shrinker_rwsem))
+		return 0;
+
+	/*
+	 * 1) Caller passes only alive memcg, so map can't be NULL.
+	 * 2) shrinker_rwsem protects from maps expanding.
+	 */
+	map = rcu_dereference_protected(memcg->nodeinfo[nid]->shrinker_map,
+					true);
+	BUG_ON(!map);
+
+	for_each_set_bit(i, map->map, shrinker_nr_max) {
+		struct shrink_control sc = {
+			.gfp_mask = gfp_mask,
+			.nid = nid,
+			.memcg = memcg,
+		};
+		struct shrinker *shrinker;
+
+		shrinker = idr_find(&shrinker_idr, i);
+		if (unlikely(!shrinker)) {
+			clear_bit(i, map->map);
+			continue;
+		}
+		BUG_ON(!(shrinker->flags & SHRINKER_MEMCG_AWARE));
+
+		/* See comment in prealloc_shrinker() */
+		if (unlikely(list_empty(&shrinker->list)))
+			continue;
+
+		ret = do_shrink_slab(&sc, shrinker, priority);
+		freed += ret;
+
+		if (rwsem_is_contended(&shrinker_rwsem)) {
+			freed = freed ? : 1;
+			break;
+		}
+	}
+
+	up_read(&shrinker_rwsem);
+	return freed;
+}
+#else /* CONFIG_MEMCG_KMEM */
+static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
+			struct mem_cgroup *memcg, int priority)
+{
+	return 0;
+}
+#endif /* CONFIG_MEMCG_KMEM */
+
 /**
  * shrink_slab - shrink slab caches
  * @gfp_mask: allocation context
@@ -570,8 +645,8 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 	struct shrinker *shrinker;
 	unsigned long freed = 0;
 
-	if (memcg && (!memcg_kmem_enabled() || !mem_cgroup_online(memcg)))
-		return 0;
+	if (memcg && !mem_cgroup_is_root(memcg))
+		return shrink_slab_memcg(gfp_mask, nid, memcg, priority);
 
 	if (!down_read_trylock(&shrinker_rwsem))
 		goto out;
@@ -583,13 +658,7 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 			.memcg = memcg,
 		};
 
-		/*
-		 * If kernel memory accounting is disabled, we ignore
-		 * SHRINKER_MEMCG_AWARE flag and call all shrinkers
-		 * passing NULL for memcg.
-		 */
-		if (memcg_kmem_enabled() &&
-		    !!memcg != !!(shrinker->flags & SHRINKER_MEMCG_AWARE))
+		if (!!memcg != !!(shrinker->flags & SHRINKER_MEMCG_AWARE))
 			continue;
 
 		if (!(shrinker->flags & SHRINKER_NUMA_AWARE))

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node()
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (13 preceding siblings ...)
  2018-05-22 10:09 ` [PATCH v7 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
@ 2018-05-22 10:09 ` Kirill Tkhai
  2018-06-08 19:21   ` Shakeel Butt
  2018-05-22 10:10 ` [PATCH v7 16/17] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
                   ` (4 subsequent siblings)
  19 siblings, 1 reply; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:09 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

From: Vladimir Davydov <vdavydov.dev@gmail.com>

The patch makes shrink_slab() be called for root_mem_cgroup
in the same way as it's called for the rest of cgroups.
This simplifies the logic and improves the readability.

Signed-off-by: Vladimir Davydov <vdavydov.dev@gmail.com>
ktkhai: Description written.
Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 mm/vmscan.c |   21 ++++++---------------
 1 file changed, 6 insertions(+), 15 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index f26ca1e00efb..6dbc659db120 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -628,10 +628,8 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
  * @nid is passed along to shrinkers with SHRINKER_NUMA_AWARE set,
  * unaware shrinkers will receive a node id of 0 instead.
  *
- * @memcg specifies the memory cgroup to target. If it is not NULL,
- * only shrinkers with SHRINKER_MEMCG_AWARE set will be called to scan
- * objects from the memory cgroup specified. Otherwise, only unaware
- * shrinkers are called.
+ * @memcg specifies the memory cgroup to target. Unaware shrinkers
+ * are called only if it is the root cgroup.
  *
  * @priority is sc->priority, we take the number of objects and >> by priority
  * in order to get the scan target.
@@ -645,7 +643,7 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 	struct shrinker *shrinker;
 	unsigned long freed = 0;
 
-	if (memcg && !mem_cgroup_is_root(memcg))
+	if (!mem_cgroup_is_root(memcg))
 		return shrink_slab_memcg(gfp_mask, nid, memcg, priority);
 
 	if (!down_read_trylock(&shrinker_rwsem))
@@ -658,9 +656,6 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 			.memcg = memcg,
 		};
 
-		if (!!memcg != !!(shrinker->flags & SHRINKER_MEMCG_AWARE))
-			continue;
-
 		if (!(shrinker->flags & SHRINKER_NUMA_AWARE))
 			sc.nid = 0;
 
@@ -690,6 +685,7 @@ void drop_slab_node(int nid)
 		struct mem_cgroup *memcg = NULL;
 
 		freed = 0;
+		memcg = mem_cgroup_iter(NULL, NULL, NULL);
 		do {
 			freed += shrink_slab(GFP_KERNEL, nid, memcg, 0);
 		} while ((memcg = mem_cgroup_iter(NULL, memcg, NULL)) != NULL);
@@ -2709,9 +2705,8 @@ static bool shrink_node(pg_data_t *pgdat, struct scan_control *sc)
 			shrink_node_memcg(pgdat, memcg, sc, &lru_pages);
 			node_lru_pages += lru_pages;
 
-			if (memcg)
-				shrink_slab(sc->gfp_mask, pgdat->node_id,
-					    memcg, sc->priority);
+			shrink_slab(sc->gfp_mask, pgdat->node_id,
+				    memcg, sc->priority);
 
 			/* Record the group's reclaim efficiency */
 			vmpressure(sc->gfp_mask, memcg, false,
@@ -2735,10 +2730,6 @@ static bool shrink_node(pg_data_t *pgdat, struct scan_control *sc)
 			}
 		} while ((memcg = mem_cgroup_iter(root, memcg, &reclaim)));
 
-		if (global_reclaim(sc))
-			shrink_slab(sc->gfp_mask, pgdat->node_id, NULL,
-				    sc->priority);
-
 		if (reclaim_state) {
 			sc->nr_reclaimed += reclaim_state->reclaimed_slab;
 			reclaim_state->reclaimed_slab = 0;

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 16/17] mm: Add SHRINK_EMPTY shrinker methods return value
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (14 preceding siblings ...)
  2018-05-22 10:09 ` [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
@ 2018-05-22 10:10 ` Kirill Tkhai
  2018-05-22 10:10 ` [PATCH v7 17/17] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
                   ` (3 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:10 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

We need to differ the situations, when shrinker has
very small amount of objects (see vfs_pressure_ratio()
called from super_cache_count()), and when it has no
objects at all. Currently, in the both of these cases,
shrinker::count_objects() returns 0.

The patch introduces new SHRINK_EMPTY return value,
which will be used for "no objects at all" case.
It's is a refactoring mostly, as SHRINK_EMPTY is replaced
by 0 by all callers of do_shrink_slab() in this patch,
and all the magic will happen in further.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 fs/super.c               |    3 +++
 include/linux/shrinker.h |    7 +++++--
 mm/vmscan.c              |   12 +++++++++---
 mm/workingset.c          |    3 +++
 4 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index f5f96e52e0cd..7429588d6b49 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -144,6 +144,9 @@ static unsigned long super_cache_count(struct shrinker *shrink,
 	total_objects += list_lru_shrink_count(&sb->s_dentry_lru, sc);
 	total_objects += list_lru_shrink_count(&sb->s_inode_lru, sc);
 
+	if (!total_objects)
+		return SHRINK_EMPTY;
+
 	total_objects = vfs_pressure_ratio(total_objects);
 	return total_objects;
 }
diff --git a/include/linux/shrinker.h b/include/linux/shrinker.h
index 7ca9c18cf130..b154fd2b084c 100644
--- a/include/linux/shrinker.h
+++ b/include/linux/shrinker.h
@@ -34,12 +34,15 @@ struct shrink_control {
 };
 
 #define SHRINK_STOP (~0UL)
+#define SHRINK_EMPTY (~0UL - 1)
 /*
  * A callback you can register to apply pressure to ageable caches.
  *
  * @count_objects should return the number of freeable items in the cache. If
- * there are no objects to free or the number of freeable items cannot be
- * determined, it should return 0. No deadlock checks should be done during the
+ * there are no objects to free, it should return SHRINK_EMPTY, while 0 is
+ * returned in cases of the number of freeable items cannot be determined
+ * or shrinker should skip this cache for this time (e.g., their number
+ * is below shrinkable limit). No deadlock checks should be done during the
  * count callback - the shrinker relies on aggregating scan counts that couldn't
  * be executed due to potential deadlocks to be run at a later call when the
  * deadlock condition is no longer pending.
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 6dbc659db120..1425907a32dd 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -453,8 +453,8 @@ static unsigned long do_shrink_slab(struct shrink_control *shrinkctl,
 	long scanned = 0, next_deferred;
 
 	freeable = shrinker->count_objects(shrinker, shrinkctl);
-	if (freeable == 0)
-		return 0;
+	if (freeable == 0 || freeable == SHRINK_EMPTY)
+		return freeable;
 
 	/*
 	 * copy the current shrinker scan count into a local variable
@@ -597,6 +597,8 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
 			continue;
 
 		ret = do_shrink_slab(&sc, shrinker, priority);
+		if (ret == SHRINK_EMPTY)
+			ret = 0;
 		freed += ret;
 
 		if (rwsem_is_contended(&shrinker_rwsem)) {
@@ -642,6 +644,7 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 {
 	struct shrinker *shrinker;
 	unsigned long freed = 0;
+	int ret;
 
 	if (!mem_cgroup_is_root(memcg))
 		return shrink_slab_memcg(gfp_mask, nid, memcg, priority);
@@ -659,7 +662,10 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
 		if (!(shrinker->flags & SHRINKER_NUMA_AWARE))
 			sc.nid = 0;
 
-		freed += do_shrink_slab(&sc, shrinker, priority);
+		ret = do_shrink_slab(&sc, shrinker, priority);
+		if (ret == SHRINK_EMPTY)
+			ret = 0;
+		freed += ret;
 		/*
 		 * Bail out if someone want to register a new shrinker to
 		 * prevent the regsitration from being stalled for long periods
diff --git a/mm/workingset.c b/mm/workingset.c
index 79099bc5c256..3bac1b2f649a 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -402,6 +402,9 @@ static unsigned long count_shadow_nodes(struct shrinker *shrinker,
 	}
 	max_nodes = cache >> (RADIX_TREE_MAP_SHIFT - 3);
 
+	if (!nodes)
+		return SHRINK_EMPTY;
+
 	if (nodes <= max_nodes)
 		return 0;
 	return nodes - max_nodes;

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH v7 17/17] mm: Clear shrinker bit if there are no objects related to memcg
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (15 preceding siblings ...)
  2018-05-22 10:10 ` [PATCH v7 16/17] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
@ 2018-05-22 10:10 ` Kirill Tkhai
  2018-05-26 17:15 ` [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Vladimir Davydov
                   ` (2 subsequent siblings)
  19 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-22 10:10 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, ktkhai, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

To avoid further unneed calls of do_shrink_slab()
for shrinkers, which already do not have any charged
objects in a memcg, their bits have to be cleared.

This patch introduces a lockless mechanism to do that
without races without parallel list lru add. After
do_shrink_slab() returns SHRINK_EMPTY the first time,
we clear the bit and call it once again. Then we restore
the bit, if the new return value is different.

Note, that single smp_mb__after_atomic() in shrink_slab_memcg()
covers two situations:

1)list_lru_add()     shrink_slab_memcg
    list_add_tail()    for_each_set_bit() <--- read bit
                         do_shrink_slab() <--- missed list update (no barrier)
    <MB>                 <MB>
    set_bit()            do_shrink_slab() <--- seen list update

This situation, when the first do_shrink_slab() sees set bit,
but it doesn't see list update (i.e., race with the first element
queueing), is rare. So we don't add <MB> before the first call
of do_shrink_slab() instead of this to do not slow down generic
case. Also, it's need the second call as seen in below in (2).

2)list_lru_add()      shrink_slab_memcg()
    list_add_tail()     ...
    set_bit()           ...
  ...                   for_each_set_bit()
  do_shrink_slab()        do_shrink_slab()
    clear_bit()           ...
  ...                     ...
  list_lru_add()          ...
    list_add_tail()       clear_bit()
    <MB>                  <MB>
    set_bit()             do_shrink_slab()

The barriers guarantees, the second do_shrink_slab()
in the right side task sees list update if really
cleared the bit. This case is drawn in the code comment.

[Results/performance of the patchset]

After the whole patchset applied the below test shows signify
increase of performance:

$echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
$mkdir /sys/fs/cgroup/memory/ct
$echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
    $for i in `seq 0 4000`; do mkdir /sys/fs/cgroup/memory/ct/$i;
			    echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
			    mkdir -p s/$i; mount -t tmpfs $i s/$i;
			    touch s/$i/file; done

Then, 5 sequential calls of drop caches:
$time echo 3 > /proc/sys/vm/drop_caches

1)Before:
0.00user 13.78system 0:13.78elapsed 99%CPU
0.00user 5.59system 0:05.60elapsed 99%CPU
0.00user 5.48system 0:05.48elapsed 99%CPU
0.00user 8.35system 0:08.35elapsed 99%CPU
0.00user 8.34system 0:08.35elapsed 99%CPU

2)After
0.00user 1.10system 0:01.10elapsed 99%CPU
0.00user 0.00system 0:00.01elapsed 64%CPU
0.00user 0.01system 0:00.01elapsed 82%CPU
0.00user 0.00system 0:00.01elapsed 64%CPU
0.00user 0.01system 0:00.01elapsed 82%CPU

The results show the performance increases at least in 548 times.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 include/linux/memcontrol.h |    2 ++
 mm/vmscan.c                |   25 +++++++++++++++++++++++--
 2 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h
index b3ae1373c99a..c487e4300b48 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -1293,6 +1293,8 @@ static inline void memcg_set_shrinker_bit(struct mem_cgroup *memcg,
 
 		rcu_read_lock();
 		map = rcu_dereference(memcg->nodeinfo[nid]->shrinker_map);
+		/* Pairs with smp mb in shrink_slab() */
+		smp_mb__before_atomic();
 		set_bit(shrinker_id, map->map);
 		rcu_read_unlock();
 	}
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 1425907a32dd..dba5f72956c6 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -597,8 +597,29 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
 			continue;
 
 		ret = do_shrink_slab(&sc, shrinker, priority);
-		if (ret == SHRINK_EMPTY)
-			ret = 0;
+		if (ret == SHRINK_EMPTY) {
+			clear_bit(i, map->map);
+			/*
+			 * After the shrinker reported that it had no objects to free,
+			 * but before we cleared the corresponding bit in the memcg
+			 * shrinker map, a new object might have been added. To make
+			 * sure, we have the bit set in this case, we invoke the
+			 * shrinker one more time and re-set the bit if it reports that
+			 * it is not empty anymore. The memory barrier here pairs with
+			 * the barrier in memcg_set_shrinker_bit():
+			 *
+			 * list_lru_add()     shrink_slab_memcg()
+			 *   list_add_tail()    clear_bit()
+			 *   <MB>               <MB>
+			 *   set_bit()          do_shrink_slab()
+			 */
+			smp_mb__after_atomic();
+			ret = do_shrink_slab(&sc, shrinker, priority);
+			if (ret == SHRINK_EMPTY)
+				ret = 0;
+			else
+				memcg_set_shrinker_bit(memcg, nid, i);
+		}
 		freed += ret;
 
 		if (rwsem_is_contended(&shrinker_rwsem)) {

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (16 preceding siblings ...)
  2018-05-22 10:10 ` [PATCH v7 17/17] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
@ 2018-05-26 17:15 ` Vladimir Davydov
  2018-05-28  8:44   ` Kirill Tkhai
  2018-06-04 12:45 ` Kirill Tkhai
  2018-06-06 20:49 ` Shakeel Butt
  19 siblings, 1 reply; 26+ messages in thread
From: Vladimir Davydov @ 2018-05-26 17:15 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: akpm, shakeelb, viro, hannes, mhocko, tglx, pombredanne,
	stummala, gregkh, sfr, guro, mka, penguin-kernel, chris, longman,
	minchan, ying.huang, mgorman, jbacik, linux, linux-kernel,
	linux-mm, willy, lirongqing, aryabinin

Hello Kirill,

The whole patch set looks good to me now.

Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>

Thanks,
Vladimir

On Tue, May 22, 2018 at 01:07:10PM +0300, Kirill Tkhai wrote:
> Hi,
> 
> this patches solves the problem with slow shrink_slab() occuring
> on the machines having many shrinkers and memory cgroups (i.e.,
> with many containers). The problem is complexity of shrink_slab()
> is O(n^2) and it grows too fast with the growth of containers
> numbers.
> 
> Let we have 200 containers, and every container has 10 mounts
> and 10 cgroups. All container tasks are isolated, and they don't
> touch foreign containers mounts.
> 
> In case of global reclaim, a task has to iterate all over the memcgs
> and to call all the memcg-aware shrinkers for all of them. This means,
> the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
> and since there are 2000 memcgs, the total calls of do_shrink_slab()
> are 2000 * 2000 = 4000000.
> 
> 4 million calls are not a number operations, which can takes 1 cpu cycle.
> E.g., super_cache_count() accesses at least two lists, and makes arifmetical
> calculations. Even, if there are no charged objects, we do these calculations,
> and replaces cpu caches by read memory. I observed nodes spending almost 100%
> time in kernel, in case of intensive writing and global reclaim. The writer
> consumes pages fast, but it's need to shrink_slab() before the reclaimer
> reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
> there is no writing, the iterations just waste the time, and slows reclaim down.
> 
> Let's see the small test below:
> 
> $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
> $mkdir /sys/fs/cgroup/memory/ct
> $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
> $for i in `seq 0 4000`;
> 	do mkdir /sys/fs/cgroup/memory/ct/$i;
> 	echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
> 	mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
> done
> 
> Then, let's see drop caches time (5 sequential calls):
> $time echo 3 > /proc/sys/vm/drop_caches
> 
> 0.00user 13.78system 0:13.78elapsed 99%CPU
> 0.00user 5.59system 0:05.60elapsed 99%CPU
> 0.00user 5.48system 0:05.48elapsed 99%CPU
> 0.00user 8.35system 0:08.35elapsed 99%CPU
> 0.00user 8.34system 0:08.35elapsed 99%CPU
> 
> 
> Last four calls don't actually shrink something. So, the iterations
> over slab shrinkers take 5.48 seconds. Not so good for scalability.
> 
> The patchset solves the problem by making shrink_slab() of O(n)
> complexity. There are following functional actions:
> 
> 1)Assign id to every registered memcg-aware shrinker.
> 2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
>   and set a shrinker-related bit after the first element
>   is added to lru list (also, when removed child memcg
>   elements are reparanted).
> 3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
>   and call a shrinker if its bit is set in memcg's shrinker
>   bitmap.
>   (Also, there is a functionality to clear the bit, after
>   last element is shrinked).
> 
> This gives signify performance increase. The result after patchset is applied:
> 
> $time echo 3 > /proc/sys/vm/drop_caches
> 
> 0.00user 1.10system 0:01.10elapsed 99%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
> 
> The results show the performance increases at least in 548 times.
> 
> So, the patchset makes shrink_slab() of less complexity and improves
> the performance in such types of load I pointed. This will give a profit
> in case of !global reclaim case, since there also will be less
> do_shrink_slab() calls.
> 
> This patchset is made against linux-next.git tree.
> 
> v7: Refactorings and readability improvements.
> 
> v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
>     Use different functions for allocation and expanding map.
>     Use new memcg_shrinker_map_size variable in memcontrol.c.
>     Refactorings.
> 
> v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB
> 
> v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups
> 
> v3: Many changes requested in commentaries to v2:
> 
> 1)rebase on prealloc_shrinker() code base
> 2)root_mem_cgroup is made out of memcg maps
> 3)rwsem replaced with shrinkers_nr_max_mutex
> 4)changes around assignment of shrinker id to list lru
> 5)everything renamed
> 
> v2: Many changes requested in commentaries to v1:
> 
> 1)the code mostly moved to mm/memcontrol.c;
> 2)using IDR instead of array of shrinkers;
> 3)added a possibility to assign list_lru shrinker id
>   at the time of shrinker registering;
> 4)reorginized locking and renamed functions and variables.
> 
> ---
> 
> Kirill Tkhai (16):
>       list_lru: Combine code under the same define
>       mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
>       mm: Assign id to every memcg-aware shrinker
>       memcg: Move up for_each_mem_cgroup{,_tree} defines
>       mm: Assign memcg-aware shrinkers bitmap to memcg
>       mm: Refactoring in workingset_init()
>       fs: Refactoring in alloc_super()
>       fs: Propagate shrinker::id to list_lru
>       list_lru: Add memcg argument to list_lru_from_kmem()
>       list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
>       list_lru: Pass lru argument to memcg_drain_list_lru_node()
>       mm: Export mem_cgroup_is_root()
>       mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
>       mm: Iterate only over charged shrinkers during memcg shrink_slab()
>       mm: Add SHRINK_EMPTY shrinker methods return value
>       mm: Clear shrinker bit if there are no objects related to memcg
> 
> Vladimir Davydov (1):
>       mm: Generalize shrink_slab() calls in shrink_node()
> 
> 
>  fs/super.c                 |   11 ++
>  include/linux/list_lru.h   |   18 ++--
>  include/linux/memcontrol.h |   46 +++++++++-
>  include/linux/sched.h      |    2 
>  include/linux/shrinker.h   |   11 ++
>  include/linux/slab.h       |    2 
>  init/Kconfig               |    5 +
>  mm/list_lru.c              |   90 ++++++++++++++-----
>  mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
>  mm/slab.h                  |    6 +
>  mm/slab_common.c           |    8 +-
>  mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
>  mm/workingset.c            |   11 ++
>  13 files changed, 478 insertions(+), 109 deletions(-)
> 
> --
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-05-26 17:15 ` [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Vladimir Davydov
@ 2018-05-28  8:44   ` Kirill Tkhai
  0 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-05-28  8:44 UTC (permalink / raw)
  To: Vladimir Davydov
  Cc: akpm, shakeelb, viro, hannes, mhocko, tglx, pombredanne,
	stummala, gregkh, sfr, guro, mka, penguin-kernel, chris, longman,
	minchan, ying.huang, mgorman, jbacik, linux, linux-kernel,
	linux-mm, willy, lirongqing, aryabinin

On 26.05.2018 20:15, Vladimir Davydov wrote:
> Hello Kirill,
> 
> The whole patch set looks good to me now.
> 
> Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>

Thanks for the review, Vova!

Kirill

> 
> On Tue, May 22, 2018 at 01:07:10PM +0300, Kirill Tkhai wrote:
>> Hi,
>>
>> this patches solves the problem with slow shrink_slab() occuring
>> on the machines having many shrinkers and memory cgroups (i.e.,
>> with many containers). The problem is complexity of shrink_slab()
>> is O(n^2) and it grows too fast with the growth of containers
>> numbers.
>>
>> Let we have 200 containers, and every container has 10 mounts
>> and 10 cgroups. All container tasks are isolated, and they don't
>> touch foreign containers mounts.
>>
>> In case of global reclaim, a task has to iterate all over the memcgs
>> and to call all the memcg-aware shrinkers for all of them. This means,
>> the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
>> and since there are 2000 memcgs, the total calls of do_shrink_slab()
>> are 2000 * 2000 = 4000000.
>>
>> 4 million calls are not a number operations, which can takes 1 cpu cycle.
>> E.g., super_cache_count() accesses at least two lists, and makes arifmetical
>> calculations. Even, if there are no charged objects, we do these calculations,
>> and replaces cpu caches by read memory. I observed nodes spending almost 100%
>> time in kernel, in case of intensive writing and global reclaim. The writer
>> consumes pages fast, but it's need to shrink_slab() before the reclaimer
>> reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
>> there is no writing, the iterations just waste the time, and slows reclaim down.
>>
>> Let's see the small test below:
>>
>> $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
>> $mkdir /sys/fs/cgroup/memory/ct
>> $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
>> $for i in `seq 0 4000`;
>> 	do mkdir /sys/fs/cgroup/memory/ct/$i;
>> 	echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
>> 	mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
>> done
>>
>> Then, let's see drop caches time (5 sequential calls):
>> $time echo 3 > /proc/sys/vm/drop_caches
>>
>> 0.00user 13.78system 0:13.78elapsed 99%CPU
>> 0.00user 5.59system 0:05.60elapsed 99%CPU
>> 0.00user 5.48system 0:05.48elapsed 99%CPU
>> 0.00user 8.35system 0:08.35elapsed 99%CPU
>> 0.00user 8.34system 0:08.35elapsed 99%CPU
>>
>>
>> Last four calls don't actually shrink something. So, the iterations
>> over slab shrinkers take 5.48 seconds. Not so good for scalability.
>>
>> The patchset solves the problem by making shrink_slab() of O(n)
>> complexity. There are following functional actions:
>>
>> 1)Assign id to every registered memcg-aware shrinker.
>> 2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
>>   and set a shrinker-related bit after the first element
>>   is added to lru list (also, when removed child memcg
>>   elements are reparanted).
>> 3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
>>   and call a shrinker if its bit is set in memcg's shrinker
>>   bitmap.
>>   (Also, there is a functionality to clear the bit, after
>>   last element is shrinked).
>>
>> This gives signify performance increase. The result after patchset is applied:
>>
>> $time echo 3 > /proc/sys/vm/drop_caches
>>
>> 0.00user 1.10system 0:01.10elapsed 99%CPU
>> 0.00user 0.00system 0:00.01elapsed 64%CPU
>> 0.00user 0.01system 0:00.01elapsed 82%CPU
>> 0.00user 0.00system 0:00.01elapsed 64%CPU
>> 0.00user 0.01system 0:00.01elapsed 82%CPU
>>
>> The results show the performance increases at least in 548 times.
>>
>> So, the patchset makes shrink_slab() of less complexity and improves
>> the performance in such types of load I pointed. This will give a profit
>> in case of !global reclaim case, since there also will be less
>> do_shrink_slab() calls.
>>
>> This patchset is made against linux-next.git tree.
>>
>> v7: Refactorings and readability improvements.
>>
>> v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
>>     Use different functions for allocation and expanding map.
>>     Use new memcg_shrinker_map_size variable in memcontrol.c.
>>     Refactorings.
>>
>> v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB
>>
>> v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups
>>
>> v3: Many changes requested in commentaries to v2:
>>
>> 1)rebase on prealloc_shrinker() code base
>> 2)root_mem_cgroup is made out of memcg maps
>> 3)rwsem replaced with shrinkers_nr_max_mutex
>> 4)changes around assignment of shrinker id to list lru
>> 5)everything renamed
>>
>> v2: Many changes requested in commentaries to v1:
>>
>> 1)the code mostly moved to mm/memcontrol.c;
>> 2)using IDR instead of array of shrinkers;
>> 3)added a possibility to assign list_lru shrinker id
>>   at the time of shrinker registering;
>> 4)reorginized locking and renamed functions and variables.
>>
>> ---
>>
>> Kirill Tkhai (16):
>>       list_lru: Combine code under the same define
>>       mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
>>       mm: Assign id to every memcg-aware shrinker
>>       memcg: Move up for_each_mem_cgroup{,_tree} defines
>>       mm: Assign memcg-aware shrinkers bitmap to memcg
>>       mm: Refactoring in workingset_init()
>>       fs: Refactoring in alloc_super()
>>       fs: Propagate shrinker::id to list_lru
>>       list_lru: Add memcg argument to list_lru_from_kmem()
>>       list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
>>       list_lru: Pass lru argument to memcg_drain_list_lru_node()
>>       mm: Export mem_cgroup_is_root()
>>       mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
>>       mm: Iterate only over charged shrinkers during memcg shrink_slab()
>>       mm: Add SHRINK_EMPTY shrinker methods return value
>>       mm: Clear shrinker bit if there are no objects related to memcg
>>
>> Vladimir Davydov (1):
>>       mm: Generalize shrink_slab() calls in shrink_node()
>>
>>
>>  fs/super.c                 |   11 ++
>>  include/linux/list_lru.h   |   18 ++--
>>  include/linux/memcontrol.h |   46 +++++++++-
>>  include/linux/sched.h      |    2 
>>  include/linux/shrinker.h   |   11 ++
>>  include/linux/slab.h       |    2 
>>  init/Kconfig               |    5 +
>>  mm/list_lru.c              |   90 ++++++++++++++-----
>>  mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
>>  mm/slab.h                  |    6 +
>>  mm/slab_common.c           |    8 +-
>>  mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
>>  mm/workingset.c            |   11 ++
>>  13 files changed, 478 insertions(+), 109 deletions(-)
>>
>> --
>> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (17 preceding siblings ...)
  2018-05-26 17:15 ` [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Vladimir Davydov
@ 2018-06-04 12:45 ` Kirill Tkhai
  2018-06-04 19:07   ` Andrew Morton
  2018-06-06 20:49 ` Shakeel Butt
  19 siblings, 1 reply; 26+ messages in thread
From: Kirill Tkhai @ 2018-06-04 12:45 UTC (permalink / raw)
  To: akpm, vdavydov.dev, shakeelb, viro, hannes, mhocko, tglx,
	pombredanne, stummala, gregkh, sfr, guro, mka, penguin-kernel,
	chris, longman, minchan, ying.huang, mgorman, jbacik, linux,
	linux-kernel, linux-mm, willy, lirongqing, aryabinin

Hi, Andrew!

This patchset is reviewed by Vladimir Davydov. I see, there is
minor change in current linux-next.git, which makes the second
patch to apply not completely clean.

Could you tell what should I do with this? Is this OK or should
I rebase it on top of linux.next or do something else?

Thanks,
Kirill

On 22.05.2018 13:07, Kirill Tkhai wrote:
> Hi,
> 
> this patches solves the problem with slow shrink_slab() occuring
> on the machines having many shrinkers and memory cgroups (i.e.,
> with many containers). The problem is complexity of shrink_slab()
> is O(n^2) and it grows too fast with the growth of containers
> numbers.
> 
> Let we have 200 containers, and every container has 10 mounts
> and 10 cgroups. All container tasks are isolated, and they don't
> touch foreign containers mounts.
> 
> In case of global reclaim, a task has to iterate all over the memcgs
> and to call all the memcg-aware shrinkers for all of them. This means,
> the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
> and since there are 2000 memcgs, the total calls of do_shrink_slab()
> are 2000 * 2000 = 4000000.
> 
> 4 million calls are not a number operations, which can takes 1 cpu cycle.
> E.g., super_cache_count() accesses at least two lists, and makes arifmetical
> calculations. Even, if there are no charged objects, we do these calculations,
> and replaces cpu caches by read memory. I observed nodes spending almost 100%
> time in kernel, in case of intensive writing and global reclaim. The writer
> consumes pages fast, but it's need to shrink_slab() before the reclaimer
> reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
> there is no writing, the iterations just waste the time, and slows reclaim down.
> 
> Let's see the small test below:
> 
> $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
> $mkdir /sys/fs/cgroup/memory/ct
> $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
> $for i in `seq 0 4000`;
> 	do mkdir /sys/fs/cgroup/memory/ct/$i;
> 	echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
> 	mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
> done
> 
> Then, let's see drop caches time (5 sequential calls):
> $time echo 3 > /proc/sys/vm/drop_caches
> 
> 0.00user 13.78system 0:13.78elapsed 99%CPU
> 0.00user 5.59system 0:05.60elapsed 99%CPU
> 0.00user 5.48system 0:05.48elapsed 99%CPU
> 0.00user 8.35system 0:08.35elapsed 99%CPU
> 0.00user 8.34system 0:08.35elapsed 99%CPU
> 
> 
> Last four calls don't actually shrink something. So, the iterations
> over slab shrinkers take 5.48 seconds. Not so good for scalability.
> 
> The patchset solves the problem by making shrink_slab() of O(n)
> complexity. There are following functional actions:
> 
> 1)Assign id to every registered memcg-aware shrinker.
> 2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
>   and set a shrinker-related bit after the first element
>   is added to lru list (also, when removed child memcg
>   elements are reparanted).
> 3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
>   and call a shrinker if its bit is set in memcg's shrinker
>   bitmap.
>   (Also, there is a functionality to clear the bit, after
>   last element is shrinked).
> 
> This gives signify performance increase. The result after patchset is applied:
> 
> $time echo 3 > /proc/sys/vm/drop_caches
> 
> 0.00user 1.10system 0:01.10elapsed 99%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
> 
> The results show the performance increases at least in 548 times.
> 
> So, the patchset makes shrink_slab() of less complexity and improves
> the performance in such types of load I pointed. This will give a profit
> in case of !global reclaim case, since there also will be less
> do_shrink_slab() calls.
> 
> This patchset is made against linux-next.git tree.
> 
> v7: Refactorings and readability improvements.
> 
> v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
>     Use different functions for allocation and expanding map.
>     Use new memcg_shrinker_map_size variable in memcontrol.c.
>     Refactorings.
> 
> v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB
> 
> v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups
> 
> v3: Many changes requested in commentaries to v2:
> 
> 1)rebase on prealloc_shrinker() code base
> 2)root_mem_cgroup is made out of memcg maps
> 3)rwsem replaced with shrinkers_nr_max_mutex
> 4)changes around assignment of shrinker id to list lru
> 5)everything renamed
> 
> v2: Many changes requested in commentaries to v1:
> 
> 1)the code mostly moved to mm/memcontrol.c;
> 2)using IDR instead of array of shrinkers;
> 3)added a possibility to assign list_lru shrinker id
>   at the time of shrinker registering;
> 4)reorginized locking and renamed functions and variables.
> 
> ---
> 
> Kirill Tkhai (16):
>       list_lru: Combine code under the same define
>       mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
>       mm: Assign id to every memcg-aware shrinker
>       memcg: Move up for_each_mem_cgroup{,_tree} defines
>       mm: Assign memcg-aware shrinkers bitmap to memcg
>       mm: Refactoring in workingset_init()
>       fs: Refactoring in alloc_super()
>       fs: Propagate shrinker::id to list_lru
>       list_lru: Add memcg argument to list_lru_from_kmem()
>       list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
>       list_lru: Pass lru argument to memcg_drain_list_lru_node()
>       mm: Export mem_cgroup_is_root()
>       mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
>       mm: Iterate only over charged shrinkers during memcg shrink_slab()
>       mm: Add SHRINK_EMPTY shrinker methods return value
>       mm: Clear shrinker bit if there are no objects related to memcg
> 
> Vladimir Davydov (1):
>       mm: Generalize shrink_slab() calls in shrink_node()
> 
> 
>  fs/super.c                 |   11 ++
>  include/linux/list_lru.h   |   18 ++--
>  include/linux/memcontrol.h |   46 +++++++++-
>  include/linux/sched.h      |    2 
>  include/linux/shrinker.h   |   11 ++
>  include/linux/slab.h       |    2 
>  init/Kconfig               |    5 +
>  mm/list_lru.c              |   90 ++++++++++++++-----
>  mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
>  mm/slab.h                  |    6 +
>  mm/slab_common.c           |    8 +-
>  mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
>  mm/workingset.c            |   11 ++
>  13 files changed, 478 insertions(+), 109 deletions(-)
> 
> --
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
> 

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-06-04 12:45 ` Kirill Tkhai
@ 2018-06-04 19:07   ` Andrew Morton
  0 siblings, 0 replies; 26+ messages in thread
From: Andrew Morton @ 2018-06-04 19:07 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: vdavydov.dev, shakeelb, viro, hannes, mhocko, tglx, pombredanne,
	stummala, gregkh, sfr, guro, mka, penguin-kernel, chris, longman,
	minchan, ying.huang, mgorman, jbacik, linux, linux-kernel,
	linux-mm, willy, lirongqing, aryabinin

On Mon, 4 Jun 2018 15:45:17 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> Hi, Andrew!
> 
> This patchset is reviewed by Vladimir Davydov. I see, there is
> minor change in current linux-next.git, which makes the second
> patch to apply not completely clean.
> 
> Could you tell what should I do with this? Is this OK or should
> I rebase it on top of linux.next or do something else?

A resend against 4.18-rc1 would be ideal, thanks.

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (18 preceding siblings ...)
  2018-06-04 12:45 ` Kirill Tkhai
@ 2018-06-06 20:49 ` Shakeel Butt
  2018-06-07 18:05   ` Kirill Tkhai
  19 siblings, 1 reply; 26+ messages in thread
From: Shakeel Butt @ 2018-06-06 20:49 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: Andrew Morton, Vladimir Davydov, Alexander Viro, Johannes Weiner,
	Michal Hocko, Thomas Gleixner, Philippe Ombredanne, stummala,
	gregkh, Stephen Rothwell, Roman Gushchin, mka, Tetsuo Handa,
	Chris Wilson, longman, Minchan Kim, Huang Ying, Mel Gorman,
	jbacik, Guenter Roeck, LKML, Linux MM, Matthew Wilcox,
	lirongqing, Andrey Ryabinin

On Tue, May 22, 2018 at 3:07 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>
> Hi,
>
> this patches solves the problem with slow shrink_slab() occuring
> on the machines having many shrinkers and memory cgroups (i.e.,
> with many containers). The problem is complexity of shrink_slab()
> is O(n^2) and it grows too fast with the growth of containers
> numbers.
>
> Let we have 200 containers, and every container has 10 mounts
> and 10 cgroups. All container tasks are isolated, and they don't
> touch foreign containers mounts.
>
> In case of global reclaim, a task has to iterate all over the memcgs
> and to call all the memcg-aware shrinkers for all of them. This means,
> the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
> and since there are 2000 memcgs, the total calls of do_shrink_slab()
> are 2000 * 2000 = 4000000.
>
> 4 million calls are not a number operations, which can takes 1 cpu cycle.
> E.g., super_cache_count() accesses at least two lists, and makes arifmetical
> calculations. Even, if there are no charged objects, we do these calculations,
> and replaces cpu caches by read memory. I observed nodes spending almost 100%
> time in kernel, in case of intensive writing and global reclaim. The writer
> consumes pages fast, but it's need to shrink_slab() before the reclaimer
> reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
> there is no writing, the iterations just waste the time, and slows reclaim down.
>
> Let's see the small test below:
>
> $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
> $mkdir /sys/fs/cgroup/memory/ct
> $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
> $for i in `seq 0 4000`;
>         do mkdir /sys/fs/cgroup/memory/ct/$i;
>         echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
>         mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
> done
>
> Then, let's see drop caches time (5 sequential calls):
> $time echo 3 > /proc/sys/vm/drop_caches
>
> 0.00user 13.78system 0:13.78elapsed 99%CPU
> 0.00user 5.59system 0:05.60elapsed 99%CPU
> 0.00user 5.48system 0:05.48elapsed 99%CPU
> 0.00user 8.35system 0:08.35elapsed 99%CPU
> 0.00user 8.34system 0:08.35elapsed 99%CPU
>
>
> Last four calls don't actually shrink something. So, the iterations
> over slab shrinkers take 5.48 seconds. Not so good for scalability.
>
> The patchset solves the problem by making shrink_slab() of O(n)
> complexity. There are following functional actions:
>
> 1)Assign id to every registered memcg-aware shrinker.
> 2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
>   and set a shrinker-related bit after the first element
>   is added to lru list (also, when removed child memcg
>   elements are reparanted).
> 3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
>   and call a shrinker if its bit is set in memcg's shrinker
>   bitmap.
>   (Also, there is a functionality to clear the bit, after
>   last element is shrinked).
>
> This gives signify performance increase. The result after patchset is applied:
>
> $time echo 3 > /proc/sys/vm/drop_caches
>
> 0.00user 1.10system 0:01.10elapsed 99%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
> 0.00user 0.00system 0:00.01elapsed 64%CPU
> 0.00user 0.01system 0:00.01elapsed 82%CPU
>
> The results show the performance increases at least in 548 times.
>
> So, the patchset makes shrink_slab() of less complexity and improves
> the performance in such types of load I pointed. This will give a profit
> in case of !global reclaim case, since there also will be less
> do_shrink_slab() calls.
>
> This patchset is made against linux-next.git tree.
>
> v7: Refactorings and readability improvements.
>
> v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
>     Use different functions for allocation and expanding map.
>     Use new memcg_shrinker_map_size variable in memcontrol.c.
>     Refactorings.
>
> v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB
>
> v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups
>
> v3: Many changes requested in commentaries to v2:
>
> 1)rebase on prealloc_shrinker() code base
> 2)root_mem_cgroup is made out of memcg maps
> 3)rwsem replaced with shrinkers_nr_max_mutex
> 4)changes around assignment of shrinker id to list lru
> 5)everything renamed
>
> v2: Many changes requested in commentaries to v1:
>
> 1)the code mostly moved to mm/memcontrol.c;
> 2)using IDR instead of array of shrinkers;
> 3)added a possibility to assign list_lru shrinker id
>   at the time of shrinker registering;
> 4)reorginized locking and renamed functions and variables.
>
> ---
>
> Kirill Tkhai (16):
>       list_lru: Combine code under the same define
>       mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
>       mm: Assign id to every memcg-aware shrinker
>       memcg: Move up for_each_mem_cgroup{,_tree} defines
>       mm: Assign memcg-aware shrinkers bitmap to memcg
>       mm: Refactoring in workingset_init()
>       fs: Refactoring in alloc_super()
>       fs: Propagate shrinker::id to list_lru
>       list_lru: Add memcg argument to list_lru_from_kmem()
>       list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
>       list_lru: Pass lru argument to memcg_drain_list_lru_node()
>       mm: Export mem_cgroup_is_root()
>       mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
>       mm: Iterate only over charged shrinkers during memcg shrink_slab()
>       mm: Add SHRINK_EMPTY shrinker methods return value
>       mm: Clear shrinker bit if there are no objects related to memcg
>
> Vladimir Davydov (1):
>       mm: Generalize shrink_slab() calls in shrink_node()
>
>
>  fs/super.c                 |   11 ++
>  include/linux/list_lru.h   |   18 ++--
>  include/linux/memcontrol.h |   46 +++++++++-
>  include/linux/sched.h      |    2
>  include/linux/shrinker.h   |   11 ++
>  include/linux/slab.h       |    2
>  init/Kconfig               |    5 +
>  mm/list_lru.c              |   90 ++++++++++++++-----
>  mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
>  mm/slab.h                  |    6 +
>  mm/slab_common.c           |    8 +-
>  mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
>  mm/workingset.c            |   11 ++
>  13 files changed, 478 insertions(+), 109 deletions(-)
>
> --
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

Hi Kirill,

I tested this patch series on mmotm tree's
v4.17-rc6-mmotm-2018-05-25-14-52 tag. I did experiment similar to the
one I did for your lockless lru_list patch but on an actual machine.

I created 255 memcgs, 255 ext4 mounts and made each memcg create a
file containing few KiBs on corresponding mount. Then in a separate
memcg of 200 MiB limit ran a fork-bomb.

I ran the "perf record -ag -- sleep 60" and below are the results:

Without the patch series:
Samples: 4M of event 'cycles', Event count (approx.): 3279403076005
+  36.40%            fb.sh  [kernel.kallsyms]    [k] shrink_slab
+  18.97%            fb.sh  [kernel.kallsyms]    [k] list_lru_count_one
+   6.75%            fb.sh  [kernel.kallsyms]    [k] super_cache_count
+   0.49%            fb.sh  [kernel.kallsyms]    [k] down_read_trylock
+   0.44%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
+   0.27%            fb.sh  [kernel.kallsyms]    [k] up_read
+   0.21%            fb.sh  [kernel.kallsyms]    [k] osq_lock
+   0.13%            fb.sh  [kernel.kallsyms]    [k] shmem_unused_huge_count
+   0.08%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
+   0.08%            fb.sh  [kernel.kallsyms]    [k] shrink_node

With the patch series:
Samples: 4M of event 'cycles', Event count (approx.): 2756866824946
+  47.49%            fb.sh  [kernel.kallsyms]    [k] down_read_trylock
+  30.72%            fb.sh  [kernel.kallsyms]    [k] up_read
+   9.51%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
+   1.69%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
+   1.35%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_protected
+   1.05%            fb.sh  [kernel.kallsyms]    [k] queued_spin_lock_slowpath
+   0.85%            fb.sh  [kernel.kallsyms]    [k] _raw_spin_lock
+   0.78%            fb.sh  [kernel.kallsyms]    [k] lruvec_lru_size
+   0.57%            fb.sh  [kernel.kallsyms]    [k] shrink_node
+   0.54%            fb.sh  [kernel.kallsyms]    [k] queue_work_on
+   0.46%            fb.sh  [kernel.kallsyms]    [k] shrink_slab_memcg


Next I did a simple hack by removing shrinker_rwsem lock/unlock from
shrink_slab_memcg (which is functionally not correct but I made sure
there aren't any parallel mounts). I got the following result:

Samples: 5M of event 'cycles', Event count (approx.): 3473394237366
+  40.13%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_protected
+  17.66%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
+  14.78%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
+   7.07%            fb.sh  [kernel.kallsyms]    [k] lruvec_lru_size
+   3.19%            fb.sh  [kernel.kallsyms]    [k] shrink_slab_memcg
+   2.82%            fb.sh  [kernel.kallsyms]    [k] queued_spin_lock_slowpath
+   1.96%            fb.sh  [kernel.kallsyms]    [k] try_charge
+   1.81%            fb.sh  [kernel.kallsyms]    [k] shrink_node
+   0.91%            fb.sh  [kernel.kallsyms]    [k] page_counter_try_charge
+   0.65%            fb.sh  [kernel.kallsyms]    [k] css_next_descendant_pre
+   0.62%            fb.sh  [kernel.kallsyms]    [k] cgroup_file_notify

>From the result it seems like, in the workload where one job is
thrashing and affecting the whole system, this patch series moves the
load from shrinker list traversal to the shrinker_rwsem lock as there
isn't much to traverse. Since shrink_slab_memcg only takes read lock
on shrinker_rwsem, this seems like cache misses/thrashing for rwsem.
Maybe next direction is to go lockless.

thanks,
Shakeel

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
  2018-06-06 20:49 ` Shakeel Butt
@ 2018-06-07 18:05   ` Kirill Tkhai
  0 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-06-07 18:05 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Andrew Morton, Vladimir Davydov, Alexander Viro, Johannes Weiner,
	Michal Hocko, Thomas Gleixner, Philippe Ombredanne, stummala,
	gregkh, Stephen Rothwell, Roman Gushchin, mka, Tetsuo Handa,
	Chris Wilson, longman, Minchan Kim, Huang Ying, Mel Gorman,
	jbacik, Guenter Roeck, LKML, Linux MM, Matthew Wilcox,
	lirongqing, Andrey Ryabinin

Hi, Shakeel,

thanks for the testing results.

On 06.06.2018 23:49, Shakeel Butt wrote:
> On Tue, May 22, 2018 at 3:07 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>>
>> Hi,
>>
>> this patches solves the problem with slow shrink_slab() occuring
>> on the machines having many shrinkers and memory cgroups (i.e.,
>> with many containers). The problem is complexity of shrink_slab()
>> is O(n^2) and it grows too fast with the growth of containers
>> numbers.
>>
>> Let we have 200 containers, and every container has 10 mounts
>> and 10 cgroups. All container tasks are isolated, and they don't
>> touch foreign containers mounts.
>>
>> In case of global reclaim, a task has to iterate all over the memcgs
>> and to call all the memcg-aware shrinkers for all of them. This means,
>> the task has to visit 200 * 10 = 2000 shrinkers for every memcg,
>> and since there are 2000 memcgs, the total calls of do_shrink_slab()
>> are 2000 * 2000 = 4000000.
>>
>> 4 million calls are not a number operations, which can takes 1 cpu cycle.
>> E.g., super_cache_count() accesses at least two lists, and makes arifmetical
>> calculations. Even, if there are no charged objects, we do these calculations,
>> and replaces cpu caches by read memory. I observed nodes spending almost 100%
>> time in kernel, in case of intensive writing and global reclaim. The writer
>> consumes pages fast, but it's need to shrink_slab() before the reclaimer
>> reached shrink pages function (and frees SWAP_CLUSTER_MAX pages). Even if
>> there is no writing, the iterations just waste the time, and slows reclaim down.
>>
>> Let's see the small test below:
>>
>> $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
>> $mkdir /sys/fs/cgroup/memory/ct
>> $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
>> $for i in `seq 0 4000`;
>>         do mkdir /sys/fs/cgroup/memory/ct/$i;
>>         echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
>>         mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
>> done
>>
>> Then, let's see drop caches time (5 sequential calls):
>> $time echo 3 > /proc/sys/vm/drop_caches
>>
>> 0.00user 13.78system 0:13.78elapsed 99%CPU
>> 0.00user 5.59system 0:05.60elapsed 99%CPU
>> 0.00user 5.48system 0:05.48elapsed 99%CPU
>> 0.00user 8.35system 0:08.35elapsed 99%CPU
>> 0.00user 8.34system 0:08.35elapsed 99%CPU
>>
>>
>> Last four calls don't actually shrink something. So, the iterations
>> over slab shrinkers take 5.48 seconds. Not so good for scalability.
>>
>> The patchset solves the problem by making shrink_slab() of O(n)
>> complexity. There are following functional actions:
>>
>> 1)Assign id to every registered memcg-aware shrinker.
>> 2)Maintain per-memcgroup bitmap of memcg-aware shrinkers,
>>   and set a shrinker-related bit after the first element
>>   is added to lru list (also, when removed child memcg
>>   elements are reparanted).
>> 3)Split memcg-aware shrinkers and !memcg-aware shrinkers,
>>   and call a shrinker if its bit is set in memcg's shrinker
>>   bitmap.
>>   (Also, there is a functionality to clear the bit, after
>>   last element is shrinked).
>>
>> This gives signify performance increase. The result after patchset is applied:
>>
>> $time echo 3 > /proc/sys/vm/drop_caches
>>
>> 0.00user 1.10system 0:01.10elapsed 99%CPU
>> 0.00user 0.00system 0:00.01elapsed 64%CPU
>> 0.00user 0.01system 0:00.01elapsed 82%CPU
>> 0.00user 0.00system 0:00.01elapsed 64%CPU
>> 0.00user 0.01system 0:00.01elapsed 82%CPU
>>
>> The results show the performance increases at least in 548 times.
>>
>> So, the patchset makes shrink_slab() of less complexity and improves
>> the performance in such types of load I pointed. This will give a profit
>> in case of !global reclaim case, since there also will be less
>> do_shrink_slab() calls.
>>
>> This patchset is made against linux-next.git tree.
>>
>> v7: Refactorings and readability improvements.
>>
>> v6: Added missed rcu_dereference() to memcg_set_shrinker_bit().
>>     Use different functions for allocation and expanding map.
>>     Use new memcg_shrinker_map_size variable in memcontrol.c.
>>     Refactorings.
>>
>> v5: Make the optimizing logic under CONFIG_MEMCG_SHRINKER instead of MEMCG && !SLOB
>>
>> v4: Do not use memcg mem_cgroup_idr for iteration over mem cgroups
>>
>> v3: Many changes requested in commentaries to v2:
>>
>> 1)rebase on prealloc_shrinker() code base
>> 2)root_mem_cgroup is made out of memcg maps
>> 3)rwsem replaced with shrinkers_nr_max_mutex
>> 4)changes around assignment of shrinker id to list lru
>> 5)everything renamed
>>
>> v2: Many changes requested in commentaries to v1:
>>
>> 1)the code mostly moved to mm/memcontrol.c;
>> 2)using IDR instead of array of shrinkers;
>> 3)added a possibility to assign list_lru shrinker id
>>   at the time of shrinker registering;
>> 4)reorginized locking and renamed functions and variables.
>>
>> ---
>>
>> Kirill Tkhai (16):
>>       list_lru: Combine code under the same define
>>       mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
>>       mm: Assign id to every memcg-aware shrinker
>>       memcg: Move up for_each_mem_cgroup{,_tree} defines
>>       mm: Assign memcg-aware shrinkers bitmap to memcg
>>       mm: Refactoring in workingset_init()
>>       fs: Refactoring in alloc_super()
>>       fs: Propagate shrinker::id to list_lru
>>       list_lru: Add memcg argument to list_lru_from_kmem()
>>       list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
>>       list_lru: Pass lru argument to memcg_drain_list_lru_node()
>>       mm: Export mem_cgroup_is_root()
>>       mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
>>       mm: Iterate only over charged shrinkers during memcg shrink_slab()
>>       mm: Add SHRINK_EMPTY shrinker methods return value
>>       mm: Clear shrinker bit if there are no objects related to memcg
>>
>> Vladimir Davydov (1):
>>       mm: Generalize shrink_slab() calls in shrink_node()
>>
>>
>>  fs/super.c                 |   11 ++
>>  include/linux/list_lru.h   |   18 ++--
>>  include/linux/memcontrol.h |   46 +++++++++-
>>  include/linux/sched.h      |    2
>>  include/linux/shrinker.h   |   11 ++
>>  include/linux/slab.h       |    2
>>  init/Kconfig               |    5 +
>>  mm/list_lru.c              |   90 ++++++++++++++-----
>>  mm/memcontrol.c            |  173 +++++++++++++++++++++++++++++++------
>>  mm/slab.h                  |    6 +
>>  mm/slab_common.c           |    8 +-
>>  mm/vmscan.c                |  204 +++++++++++++++++++++++++++++++++++++++-----
>>  mm/workingset.c            |   11 ++
>>  13 files changed, 478 insertions(+), 109 deletions(-)
>>
>> --
>> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
> 
> Hi Kirill,
> 
> I tested this patch series on mmotm tree's
> v4.17-rc6-mmotm-2018-05-25-14-52 tag. I did experiment similar to the
> one I did for your lockless lru_list patch but on an actual machine.
> 
> I created 255 memcgs, 255 ext4 mounts and made each memcg create a
> file containing few KiBs on corresponding mount. Then in a separate
> memcg of 200 MiB limit ran a fork-bomb.
> 
> I ran the "perf record -ag -- sleep 60" and below are the results:
> 
> Without the patch series:
> Samples: 4M of event 'cycles', Event count (approx.): 3279403076005
> +  36.40%            fb.sh  [kernel.kallsyms]    [k] shrink_slab
> +  18.97%            fb.sh  [kernel.kallsyms]    [k] list_lru_count_one
> +   6.75%            fb.sh  [kernel.kallsyms]    [k] super_cache_count
> +   0.49%            fb.sh  [kernel.kallsyms]    [k] down_read_trylock
> +   0.44%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
> +   0.27%            fb.sh  [kernel.kallsyms]    [k] up_read
> +   0.21%            fb.sh  [kernel.kallsyms]    [k] osq_lock
> +   0.13%            fb.sh  [kernel.kallsyms]    [k] shmem_unused_huge_count
> +   0.08%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
> +   0.08%            fb.sh  [kernel.kallsyms]    [k] shrink_node
>
> With the patch series:
> Samples: 4M of event 'cycles', Event count (approx.): 2756866824946
> +  47.49%            fb.sh  [kernel.kallsyms]    [k] down_read_trylock
> +  30.72%            fb.sh  [kernel.kallsyms]    [k] up_read
> +   9.51%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
> +   1.69%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
> +   1.35%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_protected
> +   1.05%            fb.sh  [kernel.kallsyms]    [k] queued_spin_lock_slowpath
> +   0.85%            fb.sh  [kernel.kallsyms]    [k] _raw_spin_lock
> +   0.78%            fb.sh  [kernel.kallsyms]    [k] lruvec_lru_size
> +   0.57%            fb.sh  [kernel.kallsyms]    [k] shrink_node
> +   0.54%            fb.sh  [kernel.kallsyms]    [k] queue_work_on
> +   0.46%            fb.sh  [kernel.kallsyms]    [k] shrink_slab_memcg

The interesting results. In the first case we had iterations over long list
of shrinkers placed somewhere in memory. Since there are many allocated
structures (not only shrinkers) on mount(), the most likely case I think
is the most shrinkers do not share the same cache line. These actions
are so bad, that we don't see the trashing from down_read_trylock(),
since it's a small subset of introduced trashing.

After patches are applied, trashing from down_read_trylock() is the only
trashing and it's visible.

There were: down_read_trylock()/mem_cgroup_iter() = 0.49/0.44 ~ 1.1
It became: 47.49/9.51 ~ 5.0.

This looks like shrinker_rwsem is a good candidate to be placed in separate
__cacheline_aligned place (to prevent its impact on neighbours,
e.g. almost read-only shrinker_idr and shrinker_nr_max). This shouldn't
change perf trace (I assume), but this should be good for real workload.

> Next I did a simple hack by removing shrinker_rwsem lock/unlock from
> shrink_slab_memcg (which is functionally not correct but I made sure
> there aren't any parallel mounts). I got the following result:
> 
> Samples: 5M of event 'cycles', Event count (approx.): 3473394237366
> +  40.13%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_protected
> +  17.66%            fb.sh  [kernel.kallsyms]    [k] shrink_node_memcg
> +  14.78%            fb.sh  [kernel.kallsyms]    [k] mem_cgroup_iter
> +   7.07%            fb.sh  [kernel.kallsyms]    [k] lruvec_lru_size
> +   3.19%            fb.sh  [kernel.kallsyms]    [k] shrink_slab_memcg
> +   2.82%            fb.sh  [kernel.kallsyms]    [k] queued_spin_lock_slowpath
> +   1.96%            fb.sh  [kernel.kallsyms]    [k] try_charge
> +   1.81%            fb.sh  [kernel.kallsyms]    [k] shrink_node
> +   0.91%            fb.sh  [kernel.kallsyms]    [k] page_counter_try_charge
> +   0.65%            fb.sh  [kernel.kallsyms]    [k] css_next_descendant_pre
> +   0.62%            fb.sh  [kernel.kallsyms]    [k] cgroup_file_notify
> 
> From the result it seems like, in the workload where one job is
> thrashing and affecting the whole system, this patch series moves the
> load from shrinker list traversal to the shrinker_rwsem lock as there
> isn't much to traverse. Since shrink_slab_memcg only takes read lock
> on shrinker_rwsem, this seems like cache misses/thrashing for rwsem.
> Maybe next direction is to go lockless.

Yeah, this sounds reasonable for me. Maybe we may simply use percpu rwsem
for this (if it also has something like rwsem_is_contended()).

Thanks,
Kirill

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node()
  2018-05-22 10:09 ` [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
@ 2018-06-08 19:21   ` Shakeel Butt
  2018-06-09  8:46     ` Kirill Tkhai
  0 siblings, 1 reply; 26+ messages in thread
From: Shakeel Butt @ 2018-06-08 19:21 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: Andrew Morton, Vladimir Davydov, Alexander Viro, Johannes Weiner,
	Michal Hocko, Thomas Gleixner, Philippe Ombredanne, stummala,
	gregkh, Stephen Rothwell, Roman Gushchin, mka, Tetsuo Handa,
	Chris Wilson, longman, Minchan Kim, Huang Ying, Mel Gorman,
	jbacik, Guenter Roeck, LKML, Linux MM, Matthew Wilcox,
	lirongqing, Andrey Ryabinin

On Tue, May 22, 2018 at 3:09 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>
> From: Vladimir Davydov <vdavydov.dev@gmail.com>
>
> The patch makes shrink_slab() be called for root_mem_cgroup
> in the same way as it's called for the rest of cgroups.
> This simplifies the logic and improves the readability.
>
> Signed-off-by: Vladimir Davydov <vdavydov.dev@gmail.com>
> ktkhai: Description written.
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
> ---
>  mm/vmscan.c |   21 ++++++---------------
>  1 file changed, 6 insertions(+), 15 deletions(-)
>
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index f26ca1e00efb..6dbc659db120 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -628,10 +628,8 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
>   * @nid is passed along to shrinkers with SHRINKER_NUMA_AWARE set,
>   * unaware shrinkers will receive a node id of 0 instead.
>   *
> - * @memcg specifies the memory cgroup to target. If it is not NULL,
> - * only shrinkers with SHRINKER_MEMCG_AWARE set will be called to scan
> - * objects from the memory cgroup specified. Otherwise, only unaware
> - * shrinkers are called.
> + * @memcg specifies the memory cgroup to target. Unaware shrinkers
> + * are called only if it is the root cgroup.
>   *
>   * @priority is sc->priority, we take the number of objects and >> by priority
>   * in order to get the scan target.
> @@ -645,7 +643,7 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
>         struct shrinker *shrinker;
>         unsigned long freed = 0;
>

Shouldn't there be a VM_BUG_ON(!memcg) here?

> -       if (memcg && !mem_cgroup_is_root(memcg))
> +       if (!mem_cgroup_is_root(memcg))
>                 return shrink_slab_memcg(gfp_mask, nid, memcg, priority);
>
>         if (!down_read_trylock(&shrinker_rwsem))
> @@ -658,9 +656,6 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
>                         .memcg = memcg,
>                 };
>
> -               if (!!memcg != !!(shrinker->flags & SHRINKER_MEMCG_AWARE))
> -                       continue;
> -
>                 if (!(shrinker->flags & SHRINKER_NUMA_AWARE))
>                         sc.nid = 0;
>
> @@ -690,6 +685,7 @@ void drop_slab_node(int nid)
>                 struct mem_cgroup *memcg = NULL;
>
>                 freed = 0;
> +               memcg = mem_cgroup_iter(NULL, NULL, NULL);
>                 do {
>                         freed += shrink_slab(GFP_KERNEL, nid, memcg, 0);
>                 } while ((memcg = mem_cgroup_iter(NULL, memcg, NULL)) != NULL);
> @@ -2709,9 +2705,8 @@ static bool shrink_node(pg_data_t *pgdat, struct scan_control *sc)
>                         shrink_node_memcg(pgdat, memcg, sc, &lru_pages);
>                         node_lru_pages += lru_pages;
>
> -                       if (memcg)
> -                               shrink_slab(sc->gfp_mask, pgdat->node_id,
> -                                           memcg, sc->priority);
> +                       shrink_slab(sc->gfp_mask, pgdat->node_id,
> +                                   memcg, sc->priority);
>
>                         /* Record the group's reclaim efficiency */
>                         vmpressure(sc->gfp_mask, memcg, false,
> @@ -2735,10 +2730,6 @@ static bool shrink_node(pg_data_t *pgdat, struct scan_control *sc)
>                         }
>                 } while ((memcg = mem_cgroup_iter(root, memcg, &reclaim)));
>
> -               if (global_reclaim(sc))
> -                       shrink_slab(sc->gfp_mask, pgdat->node_id, NULL,
> -                                   sc->priority);
> -
>                 if (reclaim_state) {
>                         sc->nr_reclaimed += reclaim_state->reclaimed_slab;
>                         reclaim_state->reclaimed_slab = 0;
>

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node()
  2018-06-08 19:21   ` Shakeel Butt
@ 2018-06-09  8:46     ` Kirill Tkhai
  0 siblings, 0 replies; 26+ messages in thread
From: Kirill Tkhai @ 2018-06-09  8:46 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Andrew Morton, Vladimir Davydov, Alexander Viro, Johannes Weiner,
	Michal Hocko, Thomas Gleixner, Philippe Ombredanne, stummala,
	gregkh, Stephen Rothwell, Roman Gushchin, mka, Tetsuo Handa,
	Chris Wilson, longman, Minchan Kim, Huang Ying, Mel Gorman,
	jbacik, Guenter Roeck, LKML, Linux MM, Matthew Wilcox,
	lirongqing, Andrey Ryabinin

Hi, Shakeel.

On 08.06.2018 22:21, Shakeel Butt wrote:
> On Tue, May 22, 2018 at 3:09 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>>
>> From: Vladimir Davydov <vdavydov.dev@gmail.com>
>>
>> The patch makes shrink_slab() be called for root_mem_cgroup
>> in the same way as it's called for the rest of cgroups.
>> This simplifies the logic and improves the readability.
>>
>> Signed-off-by: Vladimir Davydov <vdavydov.dev@gmail.com>
>> ktkhai: Description written.
>> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
>> ---
>>  mm/vmscan.c |   21 ++++++---------------
>>  1 file changed, 6 insertions(+), 15 deletions(-)
>>
>> diff --git a/mm/vmscan.c b/mm/vmscan.c
>> index f26ca1e00efb..6dbc659db120 100644
>> --- a/mm/vmscan.c
>> +++ b/mm/vmscan.c
>> @@ -628,10 +628,8 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
>>   * @nid is passed along to shrinkers with SHRINKER_NUMA_AWARE set,
>>   * unaware shrinkers will receive a node id of 0 instead.
>>   *
>> - * @memcg specifies the memory cgroup to target. If it is not NULL,
>> - * only shrinkers with SHRINKER_MEMCG_AWARE set will be called to scan
>> - * objects from the memory cgroup specified. Otherwise, only unaware
>> - * shrinkers are called.
>> + * @memcg specifies the memory cgroup to target. Unaware shrinkers
>> + * are called only if it is the root cgroup.
>>   *
>>   * @priority is sc->priority, we take the number of objects and >> by priority
>>   * in order to get the scan target.
>> @@ -645,7 +643,7 @@ static unsigned long shrink_slab(gfp_t gfp_mask, int nid,
>>         struct shrinker *shrinker;
>>         unsigned long freed = 0;
>>
> 
> Shouldn't there be a VM_BUG_ON(!memcg) here?

memcg can be NULL here in case of memory controller is disabled at boot parameters
and in case of it's a global reclaim. So, such the check we can't add here.

Thanks,
Kirill

^ permalink raw reply	[flat|nested] 26+ messages in thread

end of thread, other threads:[~2018-06-09  8:47 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-05-22 10:07 [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
2018-05-22 10:07 ` [PATCH v7 01/17] list_lru: Combine code under the same define Kirill Tkhai
2018-05-22 10:07 ` [PATCH v7 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB Kirill Tkhai
2018-05-22 10:07 ` [PATCH v7 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
2018-05-22 10:07 ` [PATCH v7 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 06/17] mm: Refactoring in workingset_init() Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 07/17] fs: Refactoring in alloc_super() Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 08/17] fs: Propagate shrinker::id to list_lru Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 09/17] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
2018-05-22 10:08 ` [PATCH v7 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
2018-05-22 10:09 ` [PATCH v7 11/17] list_lru: Pass lru " Kirill Tkhai
2018-05-22 10:09 ` [PATCH v7 12/17] mm: Export mem_cgroup_is_root() Kirill Tkhai
2018-05-22 10:09 ` [PATCH v7 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
2018-05-22 10:09 ` [PATCH v7 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
2018-05-22 10:09 ` [PATCH v7 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
2018-06-08 19:21   ` Shakeel Butt
2018-06-09  8:46     ` Kirill Tkhai
2018-05-22 10:10 ` [PATCH v7 16/17] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
2018-05-22 10:10 ` [PATCH v7 17/17] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
2018-05-26 17:15 ` [PATCH v7 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Vladimir Davydov
2018-05-28  8:44   ` Kirill Tkhai
2018-06-04 12:45 ` Kirill Tkhai
2018-06-04 19:07   ` Andrew Morton
2018-06-06 20:49 ` Shakeel Butt
2018-06-07 18:05   ` Kirill Tkhai

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).