All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
@ 2018-07-03 15:08 Kirill Tkhai
  2018-07-03 15:08 ` [PATCH v8 01/17] list_lru: Combine code under the same define Kirill Tkhai
                   ` (16 more replies)
  0 siblings, 17 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:08 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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.

v8: REBASED on akpm tree of 20180703

v7: Refactorings and readability improvements.
    REBASED on 4.18-rc1

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   |   21 ++---
 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            |   13 ++-
 13 files changed, 479 insertions(+), 113 deletions(-)

--
Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>

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

* [PATCH v8 01/17] list_lru: Combine code under the same define
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
@ 2018-07-03 15:08 ` Kirill Tkhai
  2018-07-03 15:08 ` [PATCH v8 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB Kirill Tkhai
                   ` (15 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:08 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 bff3f6b615f7..b93f64f25414 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] 42+ messages in thread

* [PATCH v8 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
  2018-07-03 15:08 ` [PATCH v8 01/17] list_lru: Combine code under the same define Kirill Tkhai
@ 2018-07-03 15:08 ` Kirill Tkhai
  2018-07-03 15:09 ` [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
                   ` (14 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:08 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 c2161c3a1809..5d7f951f4f32 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
@@ -52,7 +52,7 @@ struct list_lru_node {
 struct list_lru {
 	struct list_lru_node	*node;
 	bool			lock_irq;
-#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 04b18ce4f1fd..62309f180ee6 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -280,7 +280,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;
@@ -1253,7 +1253,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;
 
@@ -1306,6 +1306,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 251245601719..bd5212523af0 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -723,7 +723,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 14e3fe4bd6a1..ed9cbddeb4a6 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 4fac26b0efba..ce683fcbc701 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -691,6 +691,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 b93f64f25414..6743cdb76ea6 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, bool lock_irq,
 		    struct lock_class_key *key)
diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index 20220b164616..31d203099af8 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
@@ -2182,7 +2182,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;
@@ -2447,7 +2447,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
 
@@ -3060,7 +3060,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;
@@ -3160,7 +3160,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)
@@ -4464,7 +4464,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
@@ -6330,7 +6330,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 a6545332cc86..2215eec16c0a 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 2296caf87bfb..fea3376f9816 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);
 
@@ -256,7 +256,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
@@ -584,7 +584,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.
@@ -861,7 +861,7 @@ static inline int shutdown_memcg_caches(struct kmem_cache *s)
 static inline void flush_memcg_workqueue(struct kmem_cache *s)
 {
 }
-#endif /* CONFIG_MEMCG && !CONFIG_SLOB */
+#endif /* CONFIG_MEMCG_KMEM */
 
 void slab_kmem_cache_release(struct kmem_cache *s)
 {


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

* [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
  2018-07-03 15:08 ` [PATCH v8 01/17] list_lru: Combine code under the same define Kirill Tkhai
  2018-07-03 15:08 ` [PATCH v8 02/17] mm: Introduce CONFIG_MEMCG_KMEM as combination of CONFIG_MEMCG && !CONFIG_SLOB Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 15:27   ` Matthew Wilcox
  2018-07-03 15:09 ` [PATCH v8 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
                   ` (13 subsequent siblings)
  16 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 8d2ffae4db28..f9ca6b57d72f 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] 42+ messages in thread

* [PATCH v8 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (2 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 15:09 ` [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
                   ` (12 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 mm/memcontrol.c |   30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index 31d203099af8..74247a580cdd 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)
 {
@@ -913,21 +928,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] 42+ messages in thread

* [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (3 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 04/17] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 20:50   ` Andrew Morton
  2018-07-03 15:09 ` [PATCH v8 06/17] mm: Refactoring in workingset_init() Kirill Tkhai
                   ` (11 subsequent siblings)
  16 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 62309f180ee6..d8c38eafa251 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -113,6 +113,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.
  */
@@ -126,6 +135,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*/
@@ -1284,6 +1296,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 74247a580cdd..f81581e26667 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 */
 
 /**
@@ -4541,6 +4655,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);
@@ -4593,6 +4712,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 f9ca6b57d72f..d8b1958c751d 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] 42+ messages in thread

* [PATCH v8 06/17] mm: Refactoring in workingset_init()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (4 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 15:09 ` [PATCH v8 07/17] fs: Refactoring in alloc_super() Kirill Tkhai
                   ` (10 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 mm/workingset.c |    9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/mm/workingset.c b/mm/workingset.c
index a466e731231d..b16489c60471 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -507,16 +507,17 @@ 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);
 
-	/* list_lru lock nests inside the IRQ-safe i_pages lock */
-	ret = __list_lru_init(&shadow_nodes, true, true, &shadow_nodes_key);
+	ret = prealloc_shrinker(&workingset_shadow_shrinker);
 	if (ret)
 		goto err;
-	ret = register_shrinker(&workingset_shadow_shrinker);
+	/* list_lru lock nests inside the IRQ-safe i_pages lock */
+	ret = __list_lru_init(&shadow_nodes, true, 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] 42+ messages in thread

* [PATCH v8 07/17] fs: Refactoring in alloc_super()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (5 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 06/17] mm: Refactoring in workingset_init() Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 15:09 ` [PATCH v8 08/17] fs: Propagate shrinker::id to list_lru Kirill Tkhai
                   ` (9 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 fs/super.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index 43400f5fa33a..002e46d874da 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -243,10 +243,6 @@ static struct super_block *alloc_super(struct fs_context *fc)
 	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);
@@ -264,6 +260,10 @@ static struct super_block *alloc_super(struct fs_context *fc)
 	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] 42+ messages in thread

* [PATCH v8 08/17] fs: Propagate shrinker::id to list_lru
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (6 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 07/17] fs: Refactoring in alloc_super() Kirill Tkhai
@ 2018-07-03 15:09 ` Kirill Tkhai
  2018-07-03 15:10 ` [PATCH v8 09/17] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
                   ` (8 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:09 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 fs/super.c               |    4 ++--
 include/linux/list_lru.h |   17 +++++++++--------
 mm/list_lru.c            |   11 ++++++++++-
 mm/workingset.c          |    3 ++-
 4 files changed, 23 insertions(+), 12 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index 002e46d874da..f858178f74fe 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -260,9 +260,9 @@ static struct super_block *alloc_super(struct fs_context *fc)
 	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 5d7f951f4f32..c4cdda4dffa0 100644
--- a/include/linux/list_lru.h
+++ b/include/linux/list_lru.h
@@ -54,19 +54,20 @@ struct list_lru {
 	bool			lock_irq;
 #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, bool lock_irq,
-		    struct lock_class_key *key);
-
-#define list_lru_init(lru)		__list_lru_init((lru), false, false, \
-							NULL)
-#define list_lru_init_key(lru, key)	__list_lru_init((lru), false, false, \
-							(key))
-#define list_lru_init_memcg(lru)	__list_lru_init((lru), true, false, \
-							NULL)
+		    struct lock_class_key *key, struct shrinker *shrinker);
+
+#define list_lru_init(lru)				\
+	__list_lru_init((lru), false, false, NULL, NULL)
+#define list_lru_init_key(lru, key)			\
+	__list_lru_init((lru), false, false, (key), NULL)
+#define list_lru_init_memcg(lru, shrinker)		\
+	__list_lru_init((lru), true, false, 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 6743cdb76ea6..f8ae4a04ef36 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, bool lock_irq,
-		    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 b16489c60471..a682306db49b 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -511,7 +511,8 @@ static int __init workingset_init(void)
 	if (ret)
 		goto err;
 	/* list_lru lock nests inside the IRQ-safe i_pages lock */
-	ret = __list_lru_init(&shadow_nodes, true, true, &shadow_nodes_key);
+	ret = __list_lru_init(&shadow_nodes, true, true, &shadow_nodes_key,
+			      &workingset_shadow_shrinker);
 	if (ret)
 		goto err_list_lru;
 	register_shrinker_prepared(&workingset_shadow_shrinker);


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

* [PATCH v8 09/17] list_lru: Add memcg argument to list_lru_from_kmem()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (7 preceding siblings ...)
  2018-07-03 15:09 ` [PATCH v8 08/17] fs: Propagate shrinker::id to list_lru Kirill Tkhai
@ 2018-07-03 15:10 ` Kirill Tkhai
  2018-07-03 15:10 ` [PATCH v8 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
                   ` (7 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:10 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 f8ae4a04ef36..016c7d3924e4 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] 42+ messages in thread

* [PATCH v8 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (8 preceding siblings ...)
  2018-07-03 15:10 ` [PATCH v8 09/17] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
@ 2018-07-03 15:10 ` Kirill Tkhai
  2018-07-03 15:10 ` [PATCH v8 11/17] list_lru: Pass lru " Kirill Tkhai
                   ` (6 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:10 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 c4cdda4dffa0..144d6d70320c 100644
--- a/include/linux/list_lru.h
+++ b/include/linux/list_lru.h
@@ -70,7 +70,7 @@ int __list_lru_init(struct list_lru *lru, bool memcg_aware, bool lock_irq,
 	__list_lru_init((lru), true, false, 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 016c7d3924e4..467820201e2f 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 f81581e26667..510c435a15dd 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -3246,7 +3246,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] 42+ messages in thread

* [PATCH v8 11/17] list_lru: Pass lru argument to memcg_drain_list_lru_node()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (9 preceding siblings ...)
  2018-07-03 15:10 ` [PATCH v8 10/17] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
@ 2018-07-03 15:10 ` Kirill Tkhai
  2018-07-03 15:10 ` [PATCH v8 12/17] mm: Export mem_cgroup_is_root() Kirill Tkhai
                   ` (5 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:10 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 467820201e2f..fbda35ac5c17 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] 42+ messages in thread

* [PATCH v8 12/17] mm: Export mem_cgroup_is_root()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (10 preceding siblings ...)
  2018-07-03 15:10 ` [PATCH v8 11/17] list_lru: Pass lru " Kirill Tkhai
@ 2018-07-03 15:10 ` Kirill Tkhai
  2018-07-03 15:10 ` [PATCH v8 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
                   ` (4 subsequent siblings)
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:10 UTC (permalink / raw)
  To: 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, akpm, ktkhai

This will be used in next patch.

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 d8c38eafa251..2c52b4313117 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -327,6 +327,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);
@@ -800,6 +805,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 510c435a15dd..1a6c61814dbc 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] 42+ messages in thread

* [PATCH v8 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (11 preceding siblings ...)
  2018-07-03 15:10 ` [PATCH v8 12/17] mm: Export mem_cgroup_is_root() Kirill Tkhai
@ 2018-07-03 15:10 ` Kirill Tkhai
  2018-07-03 20:54   ` Andrew Morton
  2018-07-03 15:11 ` [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
                   ` (3 subsequent siblings)
  16 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:10 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 2c52b4313117..c6ea182ca54b 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -1308,6 +1308,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; )
@@ -1330,6 +1342,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 fbda35ac5c17..b2d8be96e267 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] 42+ messages in thread

* [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (12 preceding siblings ...)
  2018-07-03 15:10 ` [PATCH v8 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
@ 2018-07-03 15:11 ` Kirill Tkhai
  2018-07-03 20:58   ` Andrew Morton
  2018-07-03 15:11 ` [PATCH v8 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
                   ` (2 subsequent siblings)
  16 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:11 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 mm/vmscan.c |   87 +++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 78 insertions(+), 9 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index d8b1958c751d..d4c40ed9ec5d 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] 42+ messages in thread

* [PATCH v8 15/17] mm: Generalize shrink_slab() calls in shrink_node()
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (13 preceding siblings ...)
  2018-07-03 15:11 ` [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
@ 2018-07-03 15:11 ` Kirill Tkhai
  2018-07-03 15:11 ` [PATCH v8 16/17] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
  2018-07-03 15:11 ` [PATCH v8 17/17] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:11 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Tested-by: Shakeel Butt <shakeelb@google.com>
---
 mm/vmscan.c |   21 ++++++---------------
 1 file changed, 6 insertions(+), 15 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index d4c40ed9ec5d..39f0ba75f7f7 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] 42+ messages in thread

* [PATCH v8 16/17] mm: Add SHRINK_EMPTY shrinker methods return value
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (14 preceding siblings ...)
  2018-07-03 15:11 ` [PATCH v8 15/17] mm: Generalize shrink_slab() calls in shrink_node() Kirill Tkhai
@ 2018-07-03 15:11 ` Kirill Tkhai
  2018-07-03 15:11 ` [PATCH v8 17/17] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:11 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 f858178f74fe..00b0154487df 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -146,6 +146,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 39f0ba75f7f7..96279b5f1f6d 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 a682306db49b..8350b6ec76ce 100644
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -397,6 +397,9 @@ static unsigned long count_shadow_nodes(struct shrinker *shrinker,
 	}
 	max_nodes = cache >> (XA_CHUNK_SHIFT - 3);
 
+	if (!nodes)
+		return SHRINK_EMPTY;
+
 	if (nodes <= max_nodes)
 		return 0;
 	return nodes - max_nodes;


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

* [PATCH v8 17/17] mm: Clear shrinker bit if there are no objects related to memcg
  2018-07-03 15:08 [PATCH v8 00/17] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n)) Kirill Tkhai
                   ` (15 preceding siblings ...)
  2018-07-03 15:11 ` [PATCH v8 16/17] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
@ 2018-07-03 15:11 ` Kirill Tkhai
  16 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:11 UTC (permalink / raw)
  To: 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, akpm, ktkhai

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.

Shakeel Butt tested this patchset with fork-bomb on his configuration:

 > 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

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
Acked-by: Vladimir Davydov <vdavydov.dev@gmail.com>
Tested-by: Shakeel Butt <shakeelb@google.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 c6ea182ca54b..c79c4a54c0ee 100644
--- a/include/linux/memcontrol.h
+++ b/include/linux/memcontrol.h
@@ -1316,6 +1316,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 96279b5f1f6d..45d153508d1c 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] 42+ messages in thread

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:09 ` [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
@ 2018-07-03 15:27   ` Matthew Wilcox
  2018-07-03 15:46     ` Shakeel Butt
  2018-07-03 15:46     ` Kirill Tkhai
  0 siblings, 2 replies; 42+ messages in thread
From: Matthew Wilcox @ 2018-07-03 15:27 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, lirongqing, aryabinin, akpm

On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
> +++ 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;

So ... we've now got a list_head (shrinker_list) which contains all of
the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?

Why not replace the shrinker_list with the shrinker_idr?  It's only used
twice in vmscan.c:

void register_shrinker_prepared(struct shrinker *shrinker)
{
        down_write(&shrinker_rwsem);
        list_add_tail(&shrinker->list, &shrinker_list);
        up_write(&shrinker_rwsem);
}

        list_for_each_entry(shrinker, &shrinker_list, list) {
...

The first is simply idr_alloc() and the second is

	idr_for_each_entry(&shrinker_idr, shrinker, id) {

I understand there's a difference between allocating the shrinker's ID and
adding it to the list.  You can do this by calling idr_alloc with NULL
as the pointer, and then using idr_replace() when you want to add the
shrinker to the list.  idr_for_each_entry() skips over NULL entries.

This will actually reduce the size of each shrinker and be more
cache-efficient when calling the shrinkers.  I think we can also get
rid of the shrinker_rwsem eventually, but let's leave it for now.

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:27   ` Matthew Wilcox
@ 2018-07-03 15:46     ` Shakeel Butt
  2018-07-03 16:17       ` Kirill Tkhai
  2018-07-03 17:47       ` Matthew Wilcox
  2018-07-03 15:46     ` Kirill Tkhai
  1 sibling, 2 replies; 42+ messages in thread
From: Shakeel Butt @ 2018-07-03 15:46 UTC (permalink / raw)
  To: Matthew Wilcox
  Cc: Kirill Tkhai, 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
> > +++ 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;
>
> So ... we've now got a list_head (shrinker_list) which contains all of
> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
>
> Why not replace the shrinker_list with the shrinker_idr?  It's only used
> twice in vmscan.c:
>
> void register_shrinker_prepared(struct shrinker *shrinker)
> {
>         down_write(&shrinker_rwsem);
>         list_add_tail(&shrinker->list, &shrinker_list);
>         up_write(&shrinker_rwsem);
> }
>
>         list_for_each_entry(shrinker, &shrinker_list, list) {
> ...
>
> The first is simply idr_alloc() and the second is
>
>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
>
> I understand there's a difference between allocating the shrinker's ID and
> adding it to the list.  You can do this by calling idr_alloc with NULL
> as the pointer, and then using idr_replace() when you want to add the
> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
>
> This will actually reduce the size of each shrinker and be more
> cache-efficient when calling the shrinkers.  I think we can also get
> rid of the shrinker_rwsem eventually, but let's leave it for now.

Can you explain how you envision shrinker_rwsem can be removed? I am
very much interested in doing that.

thanks,
Shakeel

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:27   ` Matthew Wilcox
  2018-07-03 15:46     ` Shakeel Butt
@ 2018-07-03 15:46     ` Kirill Tkhai
  2018-07-03 17:58       ` Matthew Wilcox
  1 sibling, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 15:46 UTC (permalink / raw)
  To: Matthew Wilcox
  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, lirongqing, aryabinin, akpm

On 03.07.2018 18:27, Matthew Wilcox wrote:
> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
>> +++ 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;
> 
> So ... we've now got a list_head (shrinker_list) which contains all of
> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
> 
> Why not replace the shrinker_list with the shrinker_idr?  It's only used
> twice in vmscan.c:
> 
> void register_shrinker_prepared(struct shrinker *shrinker)
> {
>         down_write(&shrinker_rwsem);
>         list_add_tail(&shrinker->list, &shrinker_list);
>         up_write(&shrinker_rwsem);
> }
> 
>         list_for_each_entry(shrinker, &shrinker_list, list) {
> ...
> 
> The first is simply idr_alloc() and the second is
> 
> 	idr_for_each_entry(&shrinker_idr, shrinker, id) {
> 
> I understand there's a difference between allocating the shrinker's ID and
> adding it to the list.  You can do this by calling idr_alloc with NULL
> as the pointer, and then using idr_replace() when you want to add the
> shrinker to the list.  idr_for_each_entry() skips over NULL entries.

shrinker_idr now contains only memcg-aware shrinkers, so all bits from memcg map
may be potentially populated. In case of memcg-aware shrinkers and !memcg-aware
shrinkers share the same numbers like you suggest, this will lead to increasing
size of memcg maps, which is bad for memory consumption. So, memcg-aware shrinkers
should to have its own IDR and its own numbers. The tricks like allocation big
IDs for !memcg-aware shrinkers seem bad for me, since they make the code more
complicated.

> This will actually reduce the size of each shrinker and be more
> cache-efficient when calling the shrinkers.  I think we can also get
> rid of the shrinker_rwsem eventually, but let's leave it for now.

This patchset does not make the cache-efficient bad, since without the patchset the situation
is so bad, that it's just impossible to talk about the cache efficiently,
so let's leave lockless iteration/etc for the future works.

Kirill

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:46     ` Shakeel Butt
@ 2018-07-03 16:17       ` Kirill Tkhai
  2018-07-03 17:00         ` Shakeel Butt
  2018-07-03 17:47       ` Matthew Wilcox
  1 sibling, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 16:17 UTC (permalink / raw)
  To: Shakeel Butt, Matthew Wilcox
  Cc: 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

Hi, Shakeel,

On 03.07.2018 18:46, Shakeel Butt wrote:
> On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
>>
>> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
>>> +++ 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;
>>
>> So ... we've now got a list_head (shrinker_list) which contains all of
>> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
>>
>> Why not replace the shrinker_list with the shrinker_idr?  It's only used
>> twice in vmscan.c:
>>
>> void register_shrinker_prepared(struct shrinker *shrinker)
>> {
>>         down_write(&shrinker_rwsem);
>>         list_add_tail(&shrinker->list, &shrinker_list);
>>         up_write(&shrinker_rwsem);
>> }
>>
>>         list_for_each_entry(shrinker, &shrinker_list, list) {
>> ...
>>
>> The first is simply idr_alloc() and the second is
>>
>>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
>>
>> I understand there's a difference between allocating the shrinker's ID and
>> adding it to the list.  You can do this by calling idr_alloc with NULL
>> as the pointer, and then using idr_replace() when you want to add the
>> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
>>
>> This will actually reduce the size of each shrinker and be more
>> cache-efficient when calling the shrinkers.  I think we can also get
>> rid of the shrinker_rwsem eventually, but let's leave it for now.
> 
> Can you explain how you envision shrinker_rwsem can be removed? I am
> very much interested in doing that.

Have you tried to do some games with SRCU? It looks like we just need to
teach count_objects() and scan_objects() to work with semi-destructed
shrinkers. Though, this looks this will make impossible to introduce
shrinkers, which do synchronize_srcu() in scan_objects() for example.
Not sure, someone will actually use this, and this is possible to consider
as limitation.

Kirill

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 16:17       ` Kirill Tkhai
@ 2018-07-03 17:00         ` Shakeel Butt
  2018-07-03 17:32           ` Kirill Tkhai
  0 siblings, 1 reply; 42+ messages in thread
From: Shakeel Butt @ 2018-07-03 17:00 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: Matthew Wilcox, 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, lirongqing, Andrey Ryabinin, Andrew Morton,
	Paul McKenney

On Tue, Jul 3, 2018 at 9:17 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>
> Hi, Shakeel,
>
> On 03.07.2018 18:46, Shakeel Butt wrote:
> > On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
> >>
> >> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
> >>> +++ 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;
> >>
> >> So ... we've now got a list_head (shrinker_list) which contains all of
> >> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
> >>
> >> Why not replace the shrinker_list with the shrinker_idr?  It's only used
> >> twice in vmscan.c:
> >>
> >> void register_shrinker_prepared(struct shrinker *shrinker)
> >> {
> >>         down_write(&shrinker_rwsem);
> >>         list_add_tail(&shrinker->list, &shrinker_list);
> >>         up_write(&shrinker_rwsem);
> >> }
> >>
> >>         list_for_each_entry(shrinker, &shrinker_list, list) {
> >> ...
> >>
> >> The first is simply idr_alloc() and the second is
> >>
> >>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
> >>
> >> I understand there's a difference between allocating the shrinker's ID and
> >> adding it to the list.  You can do this by calling idr_alloc with NULL
> >> as the pointer, and then using idr_replace() when you want to add the
> >> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
> >>
> >> This will actually reduce the size of each shrinker and be more
> >> cache-efficient when calling the shrinkers.  I think we can also get
> >> rid of the shrinker_rwsem eventually, but let's leave it for now.
> >
> > Can you explain how you envision shrinker_rwsem can be removed? I am
> > very much interested in doing that.
>
> Have you tried to do some games with SRCU? It looks like we just need to
> teach count_objects() and scan_objects() to work with semi-destructed
> shrinkers. Though, this looks this will make impossible to introduce
> shrinkers, which do synchronize_srcu() in scan_objects() for example.
> Not sure, someone will actually use this, and this is possible to consider
> as limitation.
>

Hi Kirill, I tried SRCU and the discussion is at
https://lore.kernel.org/lkml/20171117173521.GA21692@infradead.org/T/#u

Paul E. McKenney suggested to enable SRCU unconditionally. So, to use
SRCU for shrinkers, we first have to push unconditional SRCU.

Tetsuo had another lockless solution which was a bit involved but does
not depend on SRCU.

thanks,
Shakeel

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 17:00         ` Shakeel Butt
@ 2018-07-03 17:32           ` Kirill Tkhai
  2018-07-12 11:13             ` Kirill Tkhai
  0 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 17:32 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Matthew Wilcox, 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, lirongqing, Andrey Ryabinin, Andrew Morton,
	Paul McKenney

On 03.07.2018 20:00, Shakeel Butt wrote:
> On Tue, Jul 3, 2018 at 9:17 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>>
>> Hi, Shakeel,
>>
>> On 03.07.2018 18:46, Shakeel Butt wrote:
>>> On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
>>>>
>>>> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
>>>>> +++ 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;
>>>>
>>>> So ... we've now got a list_head (shrinker_list) which contains all of
>>>> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
>>>>
>>>> Why not replace the shrinker_list with the shrinker_idr?  It's only used
>>>> twice in vmscan.c:
>>>>
>>>> void register_shrinker_prepared(struct shrinker *shrinker)
>>>> {
>>>>         down_write(&shrinker_rwsem);
>>>>         list_add_tail(&shrinker->list, &shrinker_list);
>>>>         up_write(&shrinker_rwsem);
>>>> }
>>>>
>>>>         list_for_each_entry(shrinker, &shrinker_list, list) {
>>>> ...
>>>>
>>>> The first is simply idr_alloc() and the second is
>>>>
>>>>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
>>>>
>>>> I understand there's a difference between allocating the shrinker's ID and
>>>> adding it to the list.  You can do this by calling idr_alloc with NULL
>>>> as the pointer, and then using idr_replace() when you want to add the
>>>> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
>>>>
>>>> This will actually reduce the size of each shrinker and be more
>>>> cache-efficient when calling the shrinkers.  I think we can also get
>>>> rid of the shrinker_rwsem eventually, but let's leave it for now.
>>>
>>> Can you explain how you envision shrinker_rwsem can be removed? I am
>>> very much interested in doing that.
>>
>> Have you tried to do some games with SRCU? It looks like we just need to
>> teach count_objects() and scan_objects() to work with semi-destructed
>> shrinkers. Though, this looks this will make impossible to introduce
>> shrinkers, which do synchronize_srcu() in scan_objects() for example.
>> Not sure, someone will actually use this, and this is possible to consider
>> as limitation.
>>
> 
> Hi Kirill, I tried SRCU and the discussion is at
> https://lore.kernel.org/lkml/20171117173521.GA21692@infradead.org/T/#u
> 
> Paul E. McKenney suggested to enable SRCU unconditionally. So, to use
> SRCU for shrinkers, we first have to push unconditional SRCU.

First time, I read this, I though the talk goes about some new srcu_read_lock()
without an argument and it's need to rework SRCU in some huge way. Thanks
god, it was just a misreading :)
> Tetsuo had another lockless solution which was a bit involved but does
> not depend on SRCU.

Ok, I see refcounters suggestion. Thanks for the link, Shakeel!

Kirill

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:46     ` Shakeel Butt
  2018-07-03 16:17       ` Kirill Tkhai
@ 2018-07-03 17:47       ` Matthew Wilcox
  2018-07-03 20:39         ` Al Viro
  1 sibling, 1 reply; 42+ messages in thread
From: Matthew Wilcox @ 2018-07-03 17:47 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Kirill Tkhai, 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

On Tue, Jul 03, 2018 at 08:46:28AM -0700, Shakeel Butt wrote:
> On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
> > This will actually reduce the size of each shrinker and be more
> > cache-efficient when calling the shrinkers.  I think we can also get
> > rid of the shrinker_rwsem eventually, but let's leave it for now.
> 
> Can you explain how you envision shrinker_rwsem can be removed? I am
> very much interested in doing that.

Sure.  Right now we have 3 uses of shrinker_rwsem -- two for adding and
removing shrinkers to the list and one for walking the list.  If we switch
to an IDR then we can use a spinlock for adding/removing shrinkers and
the RCU read lock for looking up an entry in the IDR each iteration of
the loop.

We'd need to stop the shrinker from disappearing underneath us while we
drop the RCU lock, so we'd need a refcount in the shrinker, and to free
the shrinkers using RCU.  We do similar things for other data structures,
so this is all pretty well understood.

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 15:46     ` Kirill Tkhai
@ 2018-07-03 17:58       ` Matthew Wilcox
  2018-07-03 19:12         ` Kirill Tkhai
  0 siblings, 1 reply; 42+ messages in thread
From: Matthew Wilcox @ 2018-07-03 17:58 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, lirongqing, aryabinin, akpm

On Tue, Jul 03, 2018 at 06:46:57PM +0300, Kirill Tkhai wrote:
> shrinker_idr now contains only memcg-aware shrinkers, so all bits from memcg map
> may be potentially populated. In case of memcg-aware shrinkers and !memcg-aware
> shrinkers share the same numbers like you suggest, this will lead to increasing
> size of memcg maps, which is bad for memory consumption. So, memcg-aware shrinkers
> should to have its own IDR and its own numbers. The tricks like allocation big
> IDs for !memcg-aware shrinkers seem bad for me, since they make the code more
> complicated.

Do we really have so very many !memcg-aware shrinkers?

$ git grep -w register_shrinker |wc
     32     119    2221
$ git grep -w register_shrinker_prepared |wc
      4      13     268
(that's an overstatement; one of those is the declaration, one the definition,
and one an internal call, so we actually only have one caller of _prepared).

So it looks to me like your average system has one shrinker per
filesystem, one per graphics card, one per raid5 device, and a few
miscellaneous.  I'd be shocked if anybody had more than 100 shrinkers
registered on their laptop.

I think we should err on the side of simiplicity and just have one IDR for
every shrinker instead of playing games to solve a theoretical problem.

> > This will actually reduce the size of each shrinker and be more
> > cache-efficient when calling the shrinkers.  I think we can also get
> > rid of the shrinker_rwsem eventually, but let's leave it for now.
> 
> This patchset does not make the cache-efficient bad, since without the patchset the situation
> is so bad, that it's just impossible to talk about the cache efficiently,
> so let's leave lockless iteration/etc for the future works.

The situation is that bad /for your use case/.  Not so much for others.
You're introducing additional complexity here, and it'd be nice if we
can remove some of the complexity that's already there.

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 17:58       ` Matthew Wilcox
@ 2018-07-03 19:12         ` Kirill Tkhai
  2018-07-03 19:19           ` Shakeel Butt
  0 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-03 19:12 UTC (permalink / raw)
  To: Matthew Wilcox
  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, lirongqing, aryabinin, akpm

On 03.07.2018 20:58, Matthew Wilcox wrote:
> On Tue, Jul 03, 2018 at 06:46:57PM +0300, Kirill Tkhai wrote:
>> shrinker_idr now contains only memcg-aware shrinkers, so all bits from memcg map
>> may be potentially populated. In case of memcg-aware shrinkers and !memcg-aware
>> shrinkers share the same numbers like you suggest, this will lead to increasing
>> size of memcg maps, which is bad for memory consumption. So, memcg-aware shrinkers
>> should to have its own IDR and its own numbers. The tricks like allocation big
>> IDs for !memcg-aware shrinkers seem bad for me, since they make the code more
>> complicated.
> 
> Do we really have so very many !memcg-aware shrinkers?
> 
> $ git grep -w register_shrinker |wc
>      32     119    2221
> $ git grep -w register_shrinker_prepared |wc
>       4      13     268
> (that's an overstatement; one of those is the declaration, one the definition,
> and one an internal call, so we actually only have one caller of _prepared).
> 
> So it looks to me like your average system has one shrinker per
> filesystem, one per graphics card, one per raid5 device, and a few
> miscellaneous.  I'd be shocked if anybody had more than 100 shrinkers
> registered on their laptop.
> 
> I think we should err on the side of simiplicity and just have one IDR for
> every shrinker instead of playing games to solve a theoretical problem.

It just a standard situation for the systems with many containers. Every mount
introduce a new shrinker to the system, so it's easy to see a system with
100 or ever 1000 shrinkers. AFAIR, Shakeel said he also has the similar
configurations.

So, this problem is not theoretical, it's just a standard situation
for active consumer or Docker/etc.

>>> This will actually reduce the size of each shrinker and be more
>>> cache-efficient when calling the shrinkers.  I think we can also get
>>> rid of the shrinker_rwsem eventually, but let's leave it for now.
>>
>> This patchset does not make the cache-efficient bad, since without the patchset the situation
>> is so bad, that it's just impossible to talk about the cache efficiently,
>> so let's leave lockless iteration/etc for the future works.
> 
> The situation is that bad /for your use case/.  Not so much for others.
> You're introducing additional complexity here, and it'd be nice if we
> can remove some of the complexity that's already there.

You started from cache-efficienty, and now you moved to existing complexity.
I did some cleanups in this patchset, also there is Vladimir's patch, which
simplifies shrinker logic. Also there is already 17 patches.
Which already existing complexity you want to remove? I don't think there is
existing complexity directly connected to this patchset.

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 19:12         ` Kirill Tkhai
@ 2018-07-03 19:19           ` Shakeel Butt
  2018-07-03 19:25             ` Matthew Wilcox
  0 siblings, 1 reply; 42+ messages in thread
From: Shakeel Butt @ 2018-07-03 19:19 UTC (permalink / raw)
  To: Kirill Tkhai
  Cc: Matthew Wilcox, 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, lirongqing, Andrey Ryabinin, Andrew Morton

On Tue, Jul 3, 2018 at 12:13 PM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>
> On 03.07.2018 20:58, Matthew Wilcox wrote:
> > On Tue, Jul 03, 2018 at 06:46:57PM +0300, Kirill Tkhai wrote:
> >> shrinker_idr now contains only memcg-aware shrinkers, so all bits from memcg map
> >> may be potentially populated. In case of memcg-aware shrinkers and !memcg-aware
> >> shrinkers share the same numbers like you suggest, this will lead to increasing
> >> size of memcg maps, which is bad for memory consumption. So, memcg-aware shrinkers
> >> should to have its own IDR and its own numbers. The tricks like allocation big
> >> IDs for !memcg-aware shrinkers seem bad for me, since they make the code more
> >> complicated.
> >
> > Do we really have so very many !memcg-aware shrinkers?
> >
> > $ git grep -w register_shrinker |wc
> >      32     119    2221
> > $ git grep -w register_shrinker_prepared |wc
> >       4      13     268
> > (that's an overstatement; one of those is the declaration, one the definition,
> > and one an internal call, so we actually only have one caller of _prepared).
> >
> > So it looks to me like your average system has one shrinker per
> > filesystem, one per graphics card, one per raid5 device, and a few
> > miscellaneous.  I'd be shocked if anybody had more than 100 shrinkers
> > registered on their laptop.
> >
> > I think we should err on the side of simiplicity and just have one IDR for
> > every shrinker instead of playing games to solve a theoretical problem.
>
> It just a standard situation for the systems with many containers. Every mount
> introduce a new shrinker to the system, so it's easy to see a system with
> 100 or ever 1000 shrinkers. AFAIR, Shakeel said he also has the similar
> configurations.
>

I can say on our production systems, a couple thousand shrinkers is normal.

Shakeel

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 19:19           ` Shakeel Butt
@ 2018-07-03 19:25             ` Matthew Wilcox
  2018-07-03 19:54               ` Shakeel Butt
  0 siblings, 1 reply; 42+ messages in thread
From: Matthew Wilcox @ 2018-07-03 19:25 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Kirill Tkhai, 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

On Tue, Jul 03, 2018 at 12:19:35PM -0700, Shakeel Butt wrote:
> On Tue, Jul 3, 2018 at 12:13 PM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> > > Do we really have so very many !memcg-aware shrinkers?
> > >
> > > $ git grep -w register_shrinker |wc
> > >      32     119    2221
> > > $ git grep -w register_shrinker_prepared |wc
> > >       4      13     268
> > > (that's an overstatement; one of those is the declaration, one the definition,
> > > and one an internal call, so we actually only have one caller of _prepared).
> > >
> > > So it looks to me like your average system has one shrinker per
> > > filesystem, one per graphics card, one per raid5 device, and a few
> > > miscellaneous.  I'd be shocked if anybody had more than 100 shrinkers
> > > registered on their laptop.
> > >
> > > I think we should err on the side of simiplicity and just have one IDR for
> > > every shrinker instead of playing games to solve a theoretical problem.
> >
> > It just a standard situation for the systems with many containers. Every mount
> > introduce a new shrinker to the system, so it's easy to see a system with
> > 100 or ever 1000 shrinkers. AFAIR, Shakeel said he also has the similar
> > configurations.
> >
> 
> I can say on our production systems, a couple thousand shrinkers is normal.

But how many are !memcg aware?  It sounds to me like almost all of the
shrinkers come through the sget_userns() caller, so the other shrinkers
are almost irrelevant.

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 19:25             ` Matthew Wilcox
@ 2018-07-03 19:54               ` Shakeel Butt
  0 siblings, 0 replies; 42+ messages in thread
From: Shakeel Butt @ 2018-07-03 19:54 UTC (permalink / raw)
  To: Matthew Wilcox
  Cc: Kirill Tkhai, 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

On Tue, Jul 3, 2018 at 12:25 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Tue, Jul 03, 2018 at 12:19:35PM -0700, Shakeel Butt wrote:
> > On Tue, Jul 3, 2018 at 12:13 PM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> > > > Do we really have so very many !memcg-aware shrinkers?
> > > >
> > > > $ git grep -w register_shrinker |wc
> > > >      32     119    2221
> > > > $ git grep -w register_shrinker_prepared |wc
> > > >       4      13     268
> > > > (that's an overstatement; one of those is the declaration, one the definition,
> > > > and one an internal call, so we actually only have one caller of _prepared).
> > > >
> > > > So it looks to me like your average system has one shrinker per
> > > > filesystem, one per graphics card, one per raid5 device, and a few
> > > > miscellaneous.  I'd be shocked if anybody had more than 100 shrinkers
> > > > registered on their laptop.
> > > >
> > > > I think we should err on the side of simiplicity and just have one IDR for
> > > > every shrinker instead of playing games to solve a theoretical problem.
> > >
> > > It just a standard situation for the systems with many containers. Every mount
> > > introduce a new shrinker to the system, so it's easy to see a system with
> > > 100 or ever 1000 shrinkers. AFAIR, Shakeel said he also has the similar
> > > configurations.
> > >
> >
> > I can say on our production systems, a couple thousand shrinkers is normal.
>
> But how many are !memcg aware?  It sounds to me like almost all of the
> shrinkers come through the sget_userns() caller, so the other shrinkers
> are almost irrelevant.

I would say almost half. Sorry I do not have exact numbers. Basically
we use ext4 very extensively and majority of shrinkers are related to
ext4 (again I do not have exact numbers). One ext4 mount typically
registers three shrinkers, one memcg-aware (sget) and two non-memcg
aware (ext4_es_register_shrinker, ext4_xattr_create_cache).

Shakeel

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 17:47       ` Matthew Wilcox
@ 2018-07-03 20:39         ` Al Viro
  0 siblings, 0 replies; 42+ messages in thread
From: Al Viro @ 2018-07-03 20:39 UTC (permalink / raw)
  To: Matthew Wilcox
  Cc: Shakeel Butt, Kirill Tkhai, Vladimir Davydov, 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, lirongqing,
	Andrey Ryabinin, Andrew Morton

On Tue, Jul 03, 2018 at 10:47:44AM -0700, Matthew Wilcox wrote:
> On Tue, Jul 03, 2018 at 08:46:28AM -0700, Shakeel Butt wrote:
> > On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
> > > This will actually reduce the size of each shrinker and be more
> > > cache-efficient when calling the shrinkers.  I think we can also get
> > > rid of the shrinker_rwsem eventually, but let's leave it for now.
> > 
> > Can you explain how you envision shrinker_rwsem can be removed? I am
> > very much interested in doing that.
> 
> Sure.  Right now we have 3 uses of shrinker_rwsem -- two for adding and
> removing shrinkers to the list and one for walking the list.  If we switch
> to an IDR then we can use a spinlock for adding/removing shrinkers and
> the RCU read lock for looking up an entry in the IDR each iteration of
> the loop.
> 
> We'd need to stop the shrinker from disappearing underneath us while we
> drop the RCU lock, so we'd need a refcount in the shrinker, and to free
> the shrinkers using RCU.  We do similar things for other data structures,
> so this is all pretty well understood.

<censored>
struct super_block {
...
        struct shrinker s_shrink;       /* per-sb shrinker handle */
...
}
<censored>

What was that about refcount in the shrinker and taking over the lifetime
rules of the objects it might be embedded into, again?

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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-03 15:09 ` [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
@ 2018-07-03 20:50   ` Andrew Morton
  2018-07-04 15:51     ` Kirill Tkhai
                       ` (2 more replies)
  0 siblings, 3 replies; 42+ messages in thread
From: Andrew Morton @ 2018-07-03 20:50 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 Tue, 03 Jul 2018 18:09:26 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> 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.
> 
> ...
>
> --- 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;

This function ends up being a rather sad little thing.

: 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 (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;
: 	ret = 0;
: unlock:
: 	up_write(&shrinker_rwsem);
: 	return ret;
: }

- there's no need to call memcg_expand_shrinker_maps() unless id >=
  shrinker_nr_max so why not move the code and avoid calling
  memcg_expand_shrinker_maps() in most cases.

- why aren't we decreasing shrinker_nr_max in
  unregister_memcg_shrinker()?  That's easy to do, avoids pointless
  work in shrink_slab_memcg() and avoids memory waste in future
  prealloc_memcg_shrinker() calls.

  It should be possible to find the highest ID in an IDR tree with a
  straightforward descent of the underlying radix tree, but I doubt if
  that has been wired up.  Otherwise a simple loop in
  unregister_memcg_shrinker() would be needed.



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

* Re: [PATCH v8 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance
  2018-07-03 15:10 ` [PATCH v8 13/17] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
@ 2018-07-03 20:54   ` Andrew Morton
  0 siblings, 0 replies; 42+ messages in thread
From: Andrew Morton @ 2018-07-03 20:54 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 Tue, 03 Jul 2018 18:10:56 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> 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.
> 
> ...
>
> --- a/include/linux/memcontrol.h
> +++ b/include/linux/memcontrol.h
> @@ -1308,6 +1308,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();
> +	}
> +}

Three callsites, this seem rather large for inlining.

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

* Re: [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab()
  2018-07-03 15:11 ` [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
@ 2018-07-03 20:58   ` Andrew Morton
  2018-07-04 14:56     ` Kirill Tkhai
  0 siblings, 1 reply; 42+ messages in thread
From: Andrew Morton @ 2018-07-03 20:58 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 Tue, 03 Jul 2018 18:11:06 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> 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.
> 
> ...
>
> @@ -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;

Why trylock?  Presumably some other code path is known to hold the lock
for long periods?  Dunno.  Comment it, please.

> +	/*
> +	 * 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));

Fair enough as a development-time sanity check but we shouldn't need
this in production code.  Or make it VM_BUG_ON(), at least.

> +		/* 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;
> +}


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

* Re: [PATCH v8 14/17] mm: Iterate only over charged shrinkers during memcg shrink_slab()
  2018-07-03 20:58   ` Andrew Morton
@ 2018-07-04 14:56     ` Kirill Tkhai
  0 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-04 14:56 UTC (permalink / raw)
  To: Andrew Morton
  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 03.07.2018 23:58, Andrew Morton wrote:
> On Tue, 03 Jul 2018 18:11:06 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> 
>> 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.
>>
>> ...
>>
>> @@ -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;
> 
> Why trylock?  Presumably some other code path is known to hold the lock
> for long periods?  Dunno.

We take shrinker_rwsem in prealloc_memcg_shrinker() and do memory allocation
there. It may result in reclaim under shrinker_rwsem write locked, so we use
down_read_trylock() to avoid deadlocks. The first versions of the patchset
contained different lock for this function, but it has gone in the process
of review.

>Comment it, please.

OK

>> +	/*
>> +	 * 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));
> 
> Fair enough as a development-time sanity check but we shouldn't need
> this in production code.  Or make it VM_BUG_ON(), at least.

OK

>> +		/* 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;
>> +}
> 

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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-03 20:50   ` Andrew Morton
@ 2018-07-04 15:51     ` Kirill Tkhai
  2018-07-05 22:10       ` Andrew Morton
  2018-07-05 22:50     ` Matthew Wilcox
  2018-07-06 17:30     ` Vladimir Davydov
  2 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-04 15:51 UTC (permalink / raw)
  To: Andrew Morton
  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 03.07.2018 23:50, Andrew Morton wrote:
> On Tue, 03 Jul 2018 18:09:26 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> 
>> 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.
>>
>> ...
>>
>> --- 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;
> 
> This function ends up being a rather sad little thing.
> 
> : 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 (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;
> : 	ret = 0;
> : unlock:
> : 	up_write(&shrinker_rwsem);
> : 	return ret;
> : }
> 
> - there's no need to call memcg_expand_shrinker_maps() unless id >=
>   shrinker_nr_max so why not move the code and avoid calling
>   memcg_expand_shrinker_maps() in most cases.

OK

> - why aren't we decreasing shrinker_nr_max in
>   unregister_memcg_shrinker()?  That's easy to do, avoids pointless
>   work in shrink_slab_memcg() and avoids memory waste in future
>   prealloc_memcg_shrinker() calls.

You sure, but there are some things. Initially I went in the same way
as memcg_nr_cache_ids is made and just took the same x2 arithmetic.
It never decreases, so it looked good to make shrinker maps like it.
It's the only reason, so, it should not be a problem to rework.

The only moment is Vladimir strongly recommends modularity, i.e.
to have memcg_shrinker_map_size and shrinker_nr_max as different variables.
After the rework we won't be able to have this anymore, since memcontrol.c
will have to know actual shrinker_nr_max value and it will have to be exported.

Could this be a problem?

>   It should be possible to find the highest ID in an IDR tree with a
>   straightforward descent of the underlying radix tree, but I doubt if
>   that has been wired up.  Otherwise a simple loop in
>   unregister_memcg_shrinker() would be needed.

Kirill

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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-04 15:51     ` Kirill Tkhai
@ 2018-07-05 22:10       ` Andrew Morton
  2018-07-06 17:50         ` Vladimir Davydov
  0 siblings, 1 reply; 42+ messages in thread
From: Andrew Morton @ 2018-07-05 22:10 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 Wed, 4 Jul 2018 18:51:12 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> > - why aren't we decreasing shrinker_nr_max in
> >   unregister_memcg_shrinker()?  That's easy to do, avoids pointless
> >   work in shrink_slab_memcg() and avoids memory waste in future
> >   prealloc_memcg_shrinker() calls.
> 
> You sure, but there are some things. Initially I went in the same way
> as memcg_nr_cache_ids is made and just took the same x2 arithmetic.
> It never decreases, so it looked good to make shrinker maps like it.
> It's the only reason, so, it should not be a problem to rework.
> 
> The only moment is Vladimir strongly recommends modularity, i.e.
> to have memcg_shrinker_map_size and shrinker_nr_max as different variables.

For what reasons?

> After the rework we won't be able to have this anymore, since memcontrol.c
> will have to know actual shrinker_nr_max value and it will have to be exported.
>
> Could this be a problem?

Vladimir?

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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-03 20:50   ` Andrew Morton
  2018-07-04 15:51     ` Kirill Tkhai
@ 2018-07-05 22:50     ` Matthew Wilcox
  2018-07-06 17:30     ` Vladimir Davydov
  2 siblings, 0 replies; 42+ messages in thread
From: Matthew Wilcox @ 2018-07-05 22:50 UTC (permalink / raw)
  To: Andrew Morton
  Cc: Kirill Tkhai, 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, lirongqing, aryabinin

On Tue, Jul 03, 2018 at 01:50:00PM -0700, Andrew Morton wrote:
>   It should be possible to find the highest ID in an IDR tree with a
>   straightforward descent of the underlying radix tree, but I doubt if
>   that has been wired up.  Otherwise a simple loop in
>   unregister_memcg_shrinker() would be needed.

Feature request received.  I've actually implemented it for the XArray
already, but it should be easy to do for the IDR too.


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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-03 20:50   ` Andrew Morton
  2018-07-04 15:51     ` Kirill Tkhai
  2018-07-05 22:50     ` Matthew Wilcox
@ 2018-07-06 17:30     ` Vladimir Davydov
  2 siblings, 0 replies; 42+ messages in thread
From: Vladimir Davydov @ 2018-07-06 17:30 UTC (permalink / raw)
  To: Andrew Morton
  Cc: Kirill Tkhai, 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 Tue, Jul 03, 2018 at 01:50:00PM -0700, Andrew Morton wrote:
> On Tue, 03 Jul 2018 18:09:26 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> 
> > 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.
> > 
> > ...
> >
> > --- 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;
> 
> This function ends up being a rather sad little thing.
> 
> : 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 (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;
> : 	ret = 0;
> : unlock:
> : 	up_write(&shrinker_rwsem);
> : 	return ret;
> : }
> 
> - there's no need to call memcg_expand_shrinker_maps() unless id >=
>   shrinker_nr_max so why not move the code and avoid calling
>   memcg_expand_shrinker_maps() in most cases.

memcg_expand_shrinker_maps will return immediately if per memcg shrinker
maps can accommodate the new id. Since prealloc_memcg_shrinker is
definitely not a hot path, I don't see any penalty in calling this
function on each prealloc_memcg_shrinker invocation.

> 
> - why aren't we decreasing shrinker_nr_max in
>   unregister_memcg_shrinker()?  That's easy to do, avoids pointless
>   work in shrink_slab_memcg() and avoids memory waste in future
>   prealloc_memcg_shrinker() calls.

We can shrink the maps, but IMHO it isn't worth the complexity it would
introduce, because in my experience if a workload used N mount points
(containers, whatever) at some point of its lifetime, it is likely to
use the same amount in the future.

> 
>   It should be possible to find the highest ID in an IDR tree with a
>   straightforward descent of the underlying radix tree, but I doubt if
>   that has been wired up.  Otherwise a simple loop in
>   unregister_memcg_shrinker() would be needed.
> 
> 

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

* Re: [PATCH v8 05/17] mm: Assign memcg-aware shrinkers bitmap to memcg
  2018-07-05 22:10       ` Andrew Morton
@ 2018-07-06 17:50         ` Vladimir Davydov
  0 siblings, 0 replies; 42+ messages in thread
From: Vladimir Davydov @ 2018-07-06 17:50 UTC (permalink / raw)
  To: Andrew Morton
  Cc: Kirill Tkhai, 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 Thu, Jul 05, 2018 at 03:10:30PM -0700, Andrew Morton wrote:
> On Wed, 4 Jul 2018 18:51:12 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> 
> > > - why aren't we decreasing shrinker_nr_max in
> > >   unregister_memcg_shrinker()?  That's easy to do, avoids pointless
> > >   work in shrink_slab_memcg() and avoids memory waste in future
> > >   prealloc_memcg_shrinker() calls.
> > 
> > You sure, but there are some things. Initially I went in the same way
> > as memcg_nr_cache_ids is made and just took the same x2 arithmetic.
> > It never decreases, so it looked good to make shrinker maps like it.
> > It's the only reason, so, it should not be a problem to rework.
> > 
> > The only moment is Vladimir strongly recommends modularity, i.e.
> > to have memcg_shrinker_map_size and shrinker_nr_max as different variables.
> 
> For what reasons?

Having the only global variable updated in vmscan.c and used in
memcontrol.c or vice versa didn't look good to me. So I suggested to
introduce two separate static variables: one for max shrinker id (local
to vmscan.c) and another for max allocated size of per memcg shrinker
maps (local to memcontrol.c). Having the two variables instead of one
allows us to define a clear API between memcontrol.c and shrinker
infrastructure without sharing variables, which makes the code easier
to follow IMHO.

It is also more flexible: with the two variables we can decrease
shrinker_id_max when a shrinker is destroyed so that we can speed up
shrink_slab - this is fairly easy to do - but leave per memcg shrinker
maps the same size, because shrinking them is rather complicated and
doesn't seem to be worthwhile - the workload is likely to use the same
amount of memory again in the future.

> 
> > After the rework we won't be able to have this anymore, since memcontrol.c
> > will have to know actual shrinker_nr_max value and it will have to be exported.

Not necessarily. You can pass max shrinker id instead of the new id to
memcontrol.c in function arguments. But as I said before, I really don't
think that shrinking per memcg maps would make much sense.

> >
> > Could this be a problem?

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-03 17:32           ` Kirill Tkhai
@ 2018-07-12 11:13             ` Kirill Tkhai
  2018-07-12 11:19               ` Kirill Tkhai
  0 siblings, 1 reply; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-12 11:13 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Matthew Wilcox, 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, lirongqing, Andrey Ryabinin, Andrew Morton,
	Paul McKenney

On 03.07.2018 20:32, Kirill Tkhai wrote:
> On 03.07.2018 20:00, Shakeel Butt wrote:
>> On Tue, Jul 3, 2018 at 9:17 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>>>
>>> Hi, Shakeel,
>>>
>>> On 03.07.2018 18:46, Shakeel Butt wrote:
>>>> On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
>>>>>
>>>>> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
>>>>>> +++ 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;
>>>>>
>>>>> So ... we've now got a list_head (shrinker_list) which contains all of
>>>>> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
>>>>>
>>>>> Why not replace the shrinker_list with the shrinker_idr?  It's only used
>>>>> twice in vmscan.c:
>>>>>
>>>>> void register_shrinker_prepared(struct shrinker *shrinker)
>>>>> {
>>>>>         down_write(&shrinker_rwsem);
>>>>>         list_add_tail(&shrinker->list, &shrinker_list);
>>>>>         up_write(&shrinker_rwsem);
>>>>> }
>>>>>
>>>>>         list_for_each_entry(shrinker, &shrinker_list, list) {
>>>>> ...
>>>>>
>>>>> The first is simply idr_alloc() and the second is
>>>>>
>>>>>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
>>>>>
>>>>> I understand there's a difference between allocating the shrinker's ID and
>>>>> adding it to the list.  You can do this by calling idr_alloc with NULL
>>>>> as the pointer, and then using idr_replace() when you want to add the
>>>>> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
>>>>>
>>>>> This will actually reduce the size of each shrinker and be more
>>>>> cache-efficient when calling the shrinkers.  I think we can also get
>>>>> rid of the shrinker_rwsem eventually, but let's leave it for now.
>>>>
>>>> Can you explain how you envision shrinker_rwsem can be removed? I am
>>>> very much interested in doing that.
>>>
>>> Have you tried to do some games with SRCU? It looks like we just need to
>>> teach count_objects() and scan_objects() to work with semi-destructed
>>> shrinkers. Though, this looks this will make impossible to introduce
>>> shrinkers, which do synchronize_srcu() in scan_objects() for example.
>>> Not sure, someone will actually use this, and this is possible to consider
>>> as limitation.
>>>
>>
>> Hi Kirill, I tried SRCU and the discussion is at
>> https://lore.kernel.org/lkml/20171117173521.GA21692@infradead.org/T/#u
>>
>> Paul E. McKenney suggested to enable SRCU unconditionally. So, to use
>> SRCU for shrinkers, we first have to push unconditional SRCU.
> 
> First time, I read this, I though the talk goes about some new srcu_read_lock()
> without an argument and it's need to rework SRCU in some huge way. Thanks
> god, it was just a misreading :)
>> Tetsuo had another lockless solution which was a bit involved but does
>> not depend on SRCU.
> 
> Ok, I see refcounters suggestion. Thanks for the link, Shakeel!

Just returning to this theme. Since both of the suggested ways contain
srcu synchronization, it may be better just to use percpu-rwsem, since
there is the same functionality out-of-box.

register/unregister_shrinker() will use two rw semaphores:

register_shrinker()
{
	down_write(&shrinker_rwsem);
	idr_alloc();
	up_write(&shrinker_rwsem);
}

unregister_shrinker()
{
	percpu_down_write(&percpu_shrinker_rwsem);
	down_write(&shrinker_rwsem);
	idr_remove();
	up_write(&shrinker_rwsem);
	percpu_up_write(&percpu_shrinker_rwsem);
}

shrink_slab()
{
	percpu_down_read(&percpu_shrinker_rwsem);
	rcu_read_lock();
	shrinker = idr_find();
	rcu_read_unlock();

	do_shrink_slab(shrinker);
	percpu_up_read(&percpu_shrinker_rwsem);
}

1)Here is a trick to make register_shrinker() not use percpu semaphore,
  i.e., not to wait RCU synchronization. This just makes register_shrinker()
  faster. So, we introduce 2 semaphores instead of 1:
  shrinker_rwsem to protect IDR and percpu_shrinker_rwsem.

2)rcu_read_lock() -- to synchronize idr_find() with idr_alloc().
  Not sure, we really need this. It's possible, lockless idr_find()
  is OK in parallel with allocation of new ID. Parallel removing
  is not possible because of percpu rwsem.

3)Places, which are performance critical to unregister_shrinker() speed
  (e.g., like deactivate_locked_super(), as we want umount() to be fast),
  may just call it delayed from work:

diff --git a/fs/super.c b/fs/super.c
index 13647d4fd262..b4a98cb00166 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -324,19 +324,7 @@ void deactivate_locked_super(struct super_block *s)
 	struct file_system_type *fs = s->s_type;
 	if (atomic_dec_and_test(&s->s_active)) {
 		cleancache_invalidate_fs(s);
-		unregister_shrinker(&s->s_shrink);
-		fs->kill_sb(s);
-
-		/*
-		 * Since list_lru_destroy() may sleep, we cannot call it from
-		 * put_super(), where we hold the sb_lock. Therefore we destroy
-		 * the lru lists right now.
-		 */
-		list_lru_destroy(&s->s_dentry_lru);
-		list_lru_destroy(&s->s_inode_lru);
-
-		put_filesystem(fs);
-		put_super(s);
+		schedule_delayed_deactivate_super(s)
 	} else {
 		up_write(&s->s_umount);
 	}


Kirill

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

* Re: [PATCH v8 03/17] mm: Assign id to every memcg-aware shrinker
  2018-07-12 11:13             ` Kirill Tkhai
@ 2018-07-12 11:19               ` Kirill Tkhai
  0 siblings, 0 replies; 42+ messages in thread
From: Kirill Tkhai @ 2018-07-12 11:19 UTC (permalink / raw)
  To: Shakeel Butt
  Cc: Matthew Wilcox, 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, lirongqing, Andrey Ryabinin, Andrew Morton,
	Paul McKenney

On 12.07.2018 14:13, Kirill Tkhai wrote:
> On 03.07.2018 20:32, Kirill Tkhai wrote:
>> On 03.07.2018 20:00, Shakeel Butt wrote:
>>> On Tue, Jul 3, 2018 at 9:17 AM Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
>>>>
>>>> Hi, Shakeel,
>>>>
>>>> On 03.07.2018 18:46, Shakeel Butt wrote:
>>>>> On Tue, Jul 3, 2018 at 8:27 AM Matthew Wilcox <willy@infradead.org> wrote:
>>>>>>
>>>>>> On Tue, Jul 03, 2018 at 06:09:05PM +0300, Kirill Tkhai wrote:
>>>>>>> +++ 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;
>>>>>>
>>>>>> So ... we've now got a list_head (shrinker_list) which contains all of
>>>>>> the shrinkers, plus a shrinker_idr which contains the memcg-aware shrinkers?
>>>>>>
>>>>>> Why not replace the shrinker_list with the shrinker_idr?  It's only used
>>>>>> twice in vmscan.c:
>>>>>>
>>>>>> void register_shrinker_prepared(struct shrinker *shrinker)
>>>>>> {
>>>>>>         down_write(&shrinker_rwsem);
>>>>>>         list_add_tail(&shrinker->list, &shrinker_list);
>>>>>>         up_write(&shrinker_rwsem);
>>>>>> }
>>>>>>
>>>>>>         list_for_each_entry(shrinker, &shrinker_list, list) {
>>>>>> ...
>>>>>>
>>>>>> The first is simply idr_alloc() and the second is
>>>>>>
>>>>>>         idr_for_each_entry(&shrinker_idr, shrinker, id) {
>>>>>>
>>>>>> I understand there's a difference between allocating the shrinker's ID and
>>>>>> adding it to the list.  You can do this by calling idr_alloc with NULL
>>>>>> as the pointer, and then using idr_replace() when you want to add the
>>>>>> shrinker to the list.  idr_for_each_entry() skips over NULL entries.
>>>>>>
>>>>>> This will actually reduce the size of each shrinker and be more
>>>>>> cache-efficient when calling the shrinkers.  I think we can also get
>>>>>> rid of the shrinker_rwsem eventually, but let's leave it for now.
>>>>>
>>>>> Can you explain how you envision shrinker_rwsem can be removed? I am
>>>>> very much interested in doing that.
>>>>
>>>> Have you tried to do some games with SRCU? It looks like we just need to
>>>> teach count_objects() and scan_objects() to work with semi-destructed
>>>> shrinkers. Though, this looks this will make impossible to introduce
>>>> shrinkers, which do synchronize_srcu() in scan_objects() for example.
>>>> Not sure, someone will actually use this, and this is possible to consider
>>>> as limitation.
>>>>
>>>
>>> Hi Kirill, I tried SRCU and the discussion is at
>>> https://lore.kernel.org/lkml/20171117173521.GA21692@infradead.org/T/#u
>>>
>>> Paul E. McKenney suggested to enable SRCU unconditionally. So, to use
>>> SRCU for shrinkers, we first have to push unconditional SRCU.
>>
>> First time, I read this, I though the talk goes about some new srcu_read_lock()
>> without an argument and it's need to rework SRCU in some huge way. Thanks
>> god, it was just a misreading :)
>>> Tetsuo had another lockless solution which was a bit involved but does
>>> not depend on SRCU.
>>
>> Ok, I see refcounters suggestion. Thanks for the link, Shakeel!
> 
> Just returning to this theme. Since both of the suggested ways contain
> srcu synchronization, it may be better just to use percpu-rwsem, since
> there is the same functionality out-of-box.
> 
> register/unregister_shrinker() will use two rw semaphores:
> 
> register_shrinker()
> {
> 	down_write(&shrinker_rwsem);
> 	idr_alloc();
> 	up_write(&shrinker_rwsem);
> }
> 
> unregister_shrinker()
> {
> 	percpu_down_write(&percpu_shrinker_rwsem);
> 	down_write(&shrinker_rwsem);
> 	idr_remove();
> 	up_write(&shrinker_rwsem);
> 	percpu_up_write(&percpu_shrinker_rwsem);
> }
> 
> shrink_slab()
> {
> 	percpu_down_read(&percpu_shrinker_rwsem);
> 	rcu_read_lock();
> 	shrinker = idr_find();
> 	rcu_read_unlock();
> 
> 	do_shrink_slab(shrinker);
> 	percpu_up_read(&percpu_shrinker_rwsem);
> }
> 
> 1)Here is a trick to make register_shrinker() not use percpu semaphore,
>   i.e., not to wait RCU synchronization. This just makes register_shrinker()
>   faster. So, we introduce 2 semaphores instead of 1:
>   shrinker_rwsem to protect IDR and percpu_shrinker_rwsem.
> 
> 2)rcu_read_lock() -- to synchronize idr_find() with idr_alloc().
>   Not sure, we really need this. It's possible, lockless idr_find()
>   is OK in parallel with allocation of new ID. Parallel removing
>   is not possible because of percpu rwsem.
> 
> 3)Places, which are performance critical to unregister_shrinker() speed
>   (e.g., like deactivate_locked_super(), as we want umount() to be fast),
>   may just call it delayed from work:
> 
> diff --git a/fs/super.c b/fs/super.c
> index 13647d4fd262..b4a98cb00166 100644
> --- a/fs/super.c
> +++ b/fs/super.c
> @@ -324,19 +324,7 @@ void deactivate_locked_super(struct super_block *s)
>  	struct file_system_type *fs = s->s_type;
>  	if (atomic_dec_and_test(&s->s_active)) {
>  		cleancache_invalidate_fs(s);
> -		unregister_shrinker(&s->s_shrink);
> -		fs->kill_sb(s);
> -
> -		/*
> -		 * Since list_lru_destroy() may sleep, we cannot call it from
> -		 * put_super(), where we hold the sb_lock. Therefore we destroy
> -		 * the lru lists right now.
> -		 */
> -		list_lru_destroy(&s->s_dentry_lru);
> -		list_lru_destroy(&s->s_inode_lru);
> -
> -		put_filesystem(fs);
> -		put_super(s);
> +		schedule_delayed_deactivate_super(s)
>  	} else {
>  		up_write(&s->s_umount);
>  	}

s/shrinker_rwsem/shrinker_mutex/

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

end of thread, other threads:[~2018-07-12 11:19 UTC | newest]

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

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.