[PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Kirill Tkhai]

The patch introduces a special value SHRINKER_REGISTERING to use instead
of list_empty() to detect a semi-registered shrinker.

This should be clearer for a reader since "list is empty"  is not
an intuitive state of a shrinker), and this gives a better assembler
code:

Before:
callq  <idr_find>
mov    %rax,%r15
test   %rax,%rax
je     <shrink_slab_memcg+0x1d5>
mov    0x20(%rax),%rax
lea    0x20(%r15),%rdx
cmp    %rax,%rdx
je     <shrink_slab_memcg+0xbd>
mov    0x8(%rsp),%edx
mov    %r15,%rsi
lea    0x10(%rsp),%rdi
callq  <do_shrink_slab>

After:
callq  <idr_find>
mov    %rax,%r15
lea    -0x1(%rax),%rax
cmp    $0xfffffffffffffffd,%rax
ja     <shrink_slab_memcg+0x1cd>
mov    0x8(%rsp),%edx
mov    %r15,%rsi
lea    0x10(%rsp),%rdi
callq  ffffffff810cefd0 <do_shrink_slab>

Also, improve the comment.

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

diff --git a/mm/vmscan.c b/mm/vmscan.c
index 0d980e801b8a..c18c4acf9599 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -170,6 +170,21 @@ static LIST_HEAD(shrinker_list);
 static DECLARE_RWSEM(shrinker_rwsem);
 
 #ifdef CONFIG_MEMCG_KMEM
+
+/*
+ * 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 use this value to detect the situation,
+ * when id is assigned, but shrinker is not completely
+ * registered yet.
+ */
+#define SHRINKER_REGISTERING ((struct shrinker *)~0UL)
+
 static DEFINE_IDR(shrinker_idr);
 static int shrinker_nr_max;
 
@@ -179,7 +194,7 @@ static int prealloc_memcg_shrinker(struct shrinker *shrinker)
 
 	down_write(&shrinker_rwsem);
 	/* This may call shrinker, so it must use down_read_trylock() */
-	id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
+	id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);
 	if (id < 0)
 		goto unlock;
 
@@ -364,21 +379,6 @@ int prealloc_shrinker(struct shrinker *shrinker)
 	if (!shrinker->nr_deferred)
 		return -ENOMEM;
 
-	/*
-	 * 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);
-
 	if (shrinker->flags & SHRINKER_MEMCG_AWARE) {
 		if (prealloc_memcg_shrinker(shrinker))
 			goto free_deferred;
@@ -408,6 +408,7 @@ void register_shrinker_prepared(struct shrinker *shrinker)
 {
 	down_write(&shrinker_rwsem);
 	list_add_tail(&shrinker->list, &shrinker_list);
+	idr_replace(&shrinker_idr, shrinker, shrinker->id);
 	up_write(&shrinker_rwsem);
 }
 
@@ -589,15 +590,12 @@ static unsigned long shrink_slab_memcg(gfp_t gfp_mask, int nid,
 		struct shrinker *shrinker;
 
 		shrinker = idr_find(&shrinker_idr, i);
-		if (unlikely(!shrinker)) {
-			clear_bit(i, map->map);
+		if (unlikely(!shrinker || shrinker == SHRINKER_REGISTERING)) {
+			if (!shrinker)
+				clear_bit(i, map->map);
 			continue;
 		}
 
-		/* See comment in prealloc_shrinker() */
-		if (unlikely(list_empty(&shrinker->list)))
-			continue;
-
 		ret = do_shrink_slab(&sc, shrinker, priority);
 		if (ret == SHRINK_EMPTY) {
 			clear_bit(i, map->map);

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Andrew Morton]

On Fri, 03 Aug 2018 18:36:14 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> The patch introduces a special value SHRINKER_REGISTERING to use instead
> of list_empty() to detect a semi-registered shrinker.
> 
> This should be clearer for a reader since "list is empty"  is not
> an intuitive state of a shrinker), and this gives a better assembler
> code:
> 
> Before:
> callq  <idr_find>
> mov    %rax,%r15
> test   %rax,%rax
> je     <shrink_slab_memcg+0x1d5>
> mov    0x20(%rax),%rax
> lea    0x20(%r15),%rdx
> cmp    %rax,%rdx
> je     <shrink_slab_memcg+0xbd>
> mov    0x8(%rsp),%edx
> mov    %r15,%rsi
> lea    0x10(%rsp),%rdi
> callq  <do_shrink_slab>
> 
> After:
> callq  <idr_find>
> mov    %rax,%r15
> lea    -0x1(%rax),%rax
> cmp    $0xfffffffffffffffd,%rax
> ja     <shrink_slab_memcg+0x1cd>
> mov    0x8(%rsp),%edx
> mov    %r15,%rsi
> lea    0x10(%rsp),%rdi
> callq  ffffffff810cefd0 <do_shrink_slab>
> 
> Also, improve the comment.

All this isn't terribly nice.  Why can't we avoid installing the
shrinker into the idr until it is fully initialized?

Or extend the down_write(shrinker_rwsem) coverage so it protects the
entire initialization, instead of only in the prealloc_memcg_shrinker()
part of that initialization.  This is not as good - it would be better
to do all the initialization locklessly then just install the fully
initialized thing under the lock.

> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -170,6 +170,21 @@ static LIST_HEAD(shrinker_list);
>  static DECLARE_RWSEM(shrinker_rwsem);
>  
>  #ifdef CONFIG_MEMCG_KMEM
> +
> +/*
> + * 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 use this value to detect the situation,
> + * when id is assigned, but shrinker is not completely
> + * registered yet.
> + */

This comment is still quite hard to understand.  Could you please spend
a little more time over it?

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Matthew Wilcox]

On Fri, Aug 03, 2018 at 03:51:20PM -0700, Andrew Morton wrote:
> On Fri, 03 Aug 2018 18:36:14 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> > The patch introduces a special value SHRINKER_REGISTERING to use instead
> > of list_empty() to detect a semi-registered shrinker.
> 
> All this isn't terribly nice.  Why can't we avoid installing the
> shrinker into the idr until it is fully initialized?

I haven't reviewed the current state of the code in question, but the
IDR allows you to store a NULL in order to allocate an ID.  One should
then either call idr_remove() in order to release the ID or idr_replace()
once the object has been fully initialised.

Another way to potentially accomplish the same thing is to use
idr_alloc_u32 which will assign the ID immediately before inserting
the pointer into the IDR.  This only works if the caller can initialise
everything but the ID, and can handle an ENOMEM.

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Kirill Tkhai]

On 04.08.2018 01:51, Andrew Morton wrote:
> On Fri, 03 Aug 2018 18:36:14 +0300 Kirill Tkhai <ktkhai@virtuozzo.com> wrote:
> 
>> The patch introduces a special value SHRINKER_REGISTERING to use instead
>> of list_empty() to detect a semi-registered shrinker.
>>
>> This should be clearer for a reader since "list is empty"  is not
>> an intuitive state of a shrinker), and this gives a better assembler
>> code:
>>
>> Before:
>> callq  <idr_find>
>> mov    %rax,%r15
>> test   %rax,%rax
>> je     <shrink_slab_memcg+0x1d5>
>> mov    0x20(%rax),%rax
>> lea    0x20(%r15),%rdx
>> cmp    %rax,%rdx
>> je     <shrink_slab_memcg+0xbd>
>> mov    0x8(%rsp),%edx
>> mov    %r15,%rsi
>> lea    0x10(%rsp),%rdi
>> callq  <do_shrink_slab>
>>
>> After:
>> callq  <idr_find>
>> mov    %rax,%r15
>> lea    -0x1(%rax),%rax
>> cmp    $0xfffffffffffffffd,%rax
>> ja     <shrink_slab_memcg+0x1cd>
>> mov    0x8(%rsp),%edx
>> mov    %r15,%rsi
>> lea    0x10(%rsp),%rdi
>> callq  ffffffff810cefd0 <do_shrink_slab>
>>
>> Also, improve the comment.
> 
> All this isn't terribly nice.  Why can't we avoid installing the
> shrinker into the idr until it is fully initialized?

This is exactly the thing the patch makes. Instead of inserting a shrinker pointer
to idr, it inserts a fake value SHRINKER_REGISTERING there. The patch makes impossible
to dereference a shrinker unless it's completely registered. 

This value is used in shrink_slab_memcg() to differ a registering shrinker from
unregistered shrinker.

shrink_slab_memcg() clears a bit, when it can't find corresponding shrinker.
We do that, because we don't want to iterate all allocated maps and clear the bit
for each of them when shrinker is unregistering.

But we don't want shrinker_slab_memcg() clears a bit of registering shrinker
since it may be already set by a subsystem, which uses the shrinker, and we
don't want to introduce restrictions on subsystems design.
 
> Or extend the down_write(shrinker_rwsem) coverage so it protects the
> entire initialization, instead of only in the prealloc_memcg_shrinker()
> part of that initialization.  This is not as good - it would be better
> to do all the initialization locklessly then just install the fully
> initialized thing under the lock.

Current code (without patch) uses list_empty() as an indicator of
shrinker is completely registered. And it is changed under shrinekr_rwsem
in register_shrinker_prepared(). list_empty() is just like a flag.
Currently there is no a lockless inserts or races. The patch introduces
another indicator. I'm not sure I understand what you mean, please, clarify.

> 
>> --- a/mm/vmscan.c
>> +++ b/mm/vmscan.c
>> @@ -170,6 +170,21 @@ static LIST_HEAD(shrinker_list);
>>  static DECLARE_RWSEM(shrinker_rwsem);
>>  
>>  #ifdef CONFIG_MEMCG_KMEM
>> +
>> +/*
>> + * 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 use this value to detect the situation,
>> + * when id is assigned, but shrinker is not completely
>> + * registered yet.
>> + */
> 
> This comment is still quite hard to understand.  Could you please spend
> a little more time over it?
> 
> 

Ok, I'll introduce better one in v2.


Kirill

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Matthew Wilcox]

On Sat, Aug 04, 2018 at 09:42:05PM +0300, Kirill Tkhai wrote:
> This is exactly the thing the patch makes. Instead of inserting a shrinker pointer
> to idr, it inserts a fake value SHRINKER_REGISTERING there. The patch makes impossible
> to dereference a shrinker unless it's completely registered. 

-       id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
+       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);

Instead:

+       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);

... and the rest of your patch becomes even simpler.

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Kirill Tkhai]

On 05.08.2018 03:03, Matthew Wilcox wrote:
> On Sat, Aug 04, 2018 at 09:42:05PM +0300, Kirill Tkhai wrote:
>> This is exactly the thing the patch makes. Instead of inserting a shrinker pointer
>> to idr, it inserts a fake value SHRINKER_REGISTERING there. The patch makes impossible
>> to dereference a shrinker unless it's completely registered. 
> 
> -       id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
> +       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);
> 
> Instead:
> 
> +       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);
> 
> ... and the rest of your patch becomes even simpler.

The patch, we are discussing at the moment, does *exactly* this:

https://lkml.org/lkml/2018/8/3/588

It looks like you missed this hunk in the patch.

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Matthew Wilcox]

On Sun, Aug 05, 2018 at 08:30:43AM +0300, Kirill Tkhai wrote:
> On 05.08.2018 03:03, Matthew Wilcox wrote:
> > On Sat, Aug 04, 2018 at 09:42:05PM +0300, Kirill Tkhai wrote:
> >> This is exactly the thing the patch makes. Instead of inserting a shrinker pointer
> >> to idr, it inserts a fake value SHRINKER_REGISTERING there. The patch makes impossible
> >> to dereference a shrinker unless it's completely registered. 
> > 
> > -       id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
> > +       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);
> > 
> > Instead:
> > 
> > +       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);
> > 
> > ... and the rest of your patch becomes even simpler.
> 
> The patch, we are discussing at the moment, does *exactly* this:
> 
> https://lkml.org/lkml/2018/8/3/588
> 
> It looks like you missed this hunk in the patch.

No, it does this:

+       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);

I'm saying do this:

+       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);

Re: [PATCH] mm: Use special value SHRINKER_REGISTERING instead list_empty() check

[Kirill Tkhai]

On 05.08.2018 15:50, Matthew Wilcox wrote:
> On Sun, Aug 05, 2018 at 08:30:43AM +0300, Kirill Tkhai wrote:
>> On 05.08.2018 03:03, Matthew Wilcox wrote:
>>> On Sat, Aug 04, 2018 at 09:42:05PM +0300, Kirill Tkhai wrote:
>>>> This is exactly the thing the patch makes. Instead of inserting a shrinker pointer
>>>> to idr, it inserts a fake value SHRINKER_REGISTERING there. The patch makes impossible
>>>> to dereference a shrinker unless it's completely registered. 
>>>
>>> -       id = idr_alloc(&shrinker_idr, shrinker, 0, 0, GFP_KERNEL);
>>> +       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);
>>>
>>> Instead:
>>>
>>> +       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);
>>>
>>> ... and the rest of your patch becomes even simpler.
>>
>> The patch, we are discussing at the moment, does *exactly* this:
>>
>> https://lkml.org/lkml/2018/8/3/588
>>
>> It looks like you missed this hunk in the patch.
> 
> No, it does this:
> 
> +       id = idr_alloc(&shrinker_idr, SHRINKER_REGISTERING, 0, 0, GFP_KERNEL);
> 
> I'm saying do this:
> 
> +       id = idr_alloc(&shrinker_idr, NULL, 0, 0, GFP_KERNEL);

No, this won't work at all. The patch introduces special value SHRINKER_REGISTERING,
because shrink_slab_memcg() needs to differ the cases, when 1)shrinker is registering
and 2)shrinker is unregistered. In case of shrinker is registering we do not clear
the bit in shrink_slab_memcg(), while in the other case we must do that. This introduce
a generic solution for all type of shrinkers, and this allows to not impose restrictions
on specific shrinker registering code. A user of shrinker may add a first element to its
LRU list before register_shrinker_prepared() is called, and the corresponding bit won't
be cleared. This gives flexibility for users, it's just the same flexibility they have now.

Before the patch, list_empty() was used like such the indicator, and this is the difference
the patch makes.