LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Kirill Tkhai <ktkhai@virtuozzo.com>
To: akpm@linux-foundation.org, vdavydov.dev@gmail.com,
	shakeelb@google.com, viro@zeniv.linux.org.uk, hannes@cmpxchg.org,
	mhocko@kernel.org, ktkhai@virtuozzo.com, tglx@linutronix.de,
	pombredanne@nexb.com, stummala@codeaurora.org,
	gregkh@linuxfoundation.org, sfr@canb.auug.org.au, guro@fb.com,
	mka@chromium.org, penguin-kernel@I-love.SAKURA.ne.jp,
	chris@chris-wilson.co.uk, longman@redhat.com, minchan@kernel.org,
	ying.huang@intel.com, mgorman@techsingularity.net, jbacik@fb.com,
	linux@roeck-us.net, linux-kernel@vger.kernel.org,
	linux-mm@kvack.org, willy@infradead.org, lirongqing@baidu.com,
	aryabinin@virtuozzo.com
Subject: [PATCH v5 00/13] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))
Date: Thu, 10 May 2018 12:52:08 +0300	[thread overview]
Message-ID: <152594582808.22949.8353313986092337675.stgit@localhost.localdomain> (raw)

Hi,

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

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

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

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

Let's see the small test below:

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

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

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


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

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

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

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

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

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

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

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

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

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 (13):
      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: 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


 fs/super.c                 |   18 ++++-
 include/linux/list_lru.h   |    5 +
 include/linux/memcontrol.h |   39 ++++++++++
 include/linux/shrinker.h   |   11 ++-
 init/Kconfig               |    5 +
 mm/list_lru.c              |   65 +++++++++++++----
 mm/memcontrol.c            |  148 ++++++++++++++++++++++++++++++++++----
 mm/vmscan.c                |  170 +++++++++++++++++++++++++++++++++++++++++---
 mm/workingset.c            |   13 +++
 9 files changed, 421 insertions(+), 53 deletions(-)

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

             reply	other threads:[~2018-05-10  9:52 UTC|newest]

Thread overview: 33+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-10  9:52 Kirill Tkhai [this message]
2018-05-10  9:52 ` [PATCH v5 01/13] mm: Assign id to every memcg-aware shrinker Kirill Tkhai
2018-05-13  5:15   ` Vladimir Davydov
2018-05-14  9:03     ` Kirill Tkhai
2018-05-15  3:29       ` Vladimir Davydov
2018-05-10  9:52 ` [PATCH v5 02/13] memcg: Move up for_each_mem_cgroup{, _tree} defines Kirill Tkhai
2018-05-10  9:52 ` [PATCH v5 03/13] mm: Assign memcg-aware shrinkers bitmap to memcg Kirill Tkhai
2018-05-13 16:47   ` Vladimir Davydov
2018-05-14  9:34     ` Kirill Tkhai
2018-05-15  3:54       ` Vladimir Davydov
2018-05-10  9:52 ` [PATCH v5 04/13] mm: Refactoring in workingset_init() Kirill Tkhai
2018-05-10  9:52 ` [PATCH v5 05/13] fs: Refactoring in alloc_super() Kirill Tkhai
2018-05-10  9:53 ` [PATCH v5 06/13] fs: Propagate shrinker::id to list_lru Kirill Tkhai
2018-05-13 16:57   ` Vladimir Davydov
2018-05-10  9:53 ` [PATCH v5 07/13] list_lru: Add memcg argument to list_lru_from_kmem() Kirill Tkhai
2018-05-10  9:53 ` [PATCH v5 08/13] list_lru: Pass dst_memcg argument to memcg_drain_list_lru_node() Kirill Tkhai
2018-05-10  9:53 ` [PATCH v5 09/13] list_lru: Pass lru " Kirill Tkhai
2018-05-10  9:53 ` [PATCH v5 10/13] mm: Set bit in memcg shrinker bitmap on first list_lru item apearance Kirill Tkhai
2018-05-15  4:08   ` Vladimir Davydov
2018-05-10  9:53 ` [PATCH v5 11/13] mm: Iterate only over charged shrinkers during memcg shrink_slab() Kirill Tkhai
2018-05-15  5:44   ` Vladimir Davydov
2018-05-15 10:12     ` Kirill Tkhai
2018-05-17  4:33       ` Vladimir Davydov
2018-05-17 11:39         ` Kirill Tkhai
2018-05-15 14:49     ` Kirill Tkhai
2018-05-17  4:16       ` Vladimir Davydov
2018-05-17 11:49         ` Kirill Tkhai
2018-05-17 13:51           ` Vladimir Davydov
2018-05-10  9:54 ` [PATCH v5 12/13] mm: Add SHRINK_EMPTY shrinker methods return value Kirill Tkhai
2018-05-10  9:54 ` [PATCH v5 13/13] mm: Clear shrinker bit if there are no objects related to memcg Kirill Tkhai
2018-05-15  5:59   ` Vladimir Davydov
2018-05-15  8:55     ` Kirill Tkhai
2018-05-17  4:49       ` Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=152594582808.22949.8353313986092337675.stgit@localhost.localdomain \
    --to=ktkhai@virtuozzo.com \
    --cc=akpm@linux-foundation.org \
    --cc=aryabinin@virtuozzo.com \
    --cc=chris@chris-wilson.co.uk \
    --cc=gregkh@linuxfoundation.org \
    --cc=guro@fb.com \
    --cc=hannes@cmpxchg.org \
    --cc=jbacik@fb.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=linux@roeck-us.net \
    --cc=lirongqing@baidu.com \
    --cc=longman@redhat.com \
    --cc=mgorman@techsingularity.net \
    --cc=mhocko@kernel.org \
    --cc=minchan@kernel.org \
    --cc=mka@chromium.org \
    --cc=penguin-kernel@I-love.SAKURA.ne.jp \
    --cc=pombredanne@nexb.com \
    --cc=sfr@canb.auug.org.au \
    --cc=shakeelb@google.com \
    --cc=stummala@codeaurora.org \
    --cc=tglx@linutronix.de \
    --cc=vdavydov.dev@gmail.com \
    --cc=viro@zeniv.linux.org.uk \
    --cc=willy@infradead.org \
    --cc=ying.huang@intel.com \
    --subject='Re: [PATCH v5 00/13] Improve shrink_slab() scalability (old complexity was O(n^2), new is O(n))' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

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