[Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Nikita Pettik]

Imagine following situation at the moment of region truncation:

       1 slab      2 slab/HEAD
     x of s1 used  y of s2 used
     +---------+   +---------+
...->|xx|      |-->|yyyyyy|  |--> NULL
     |xx|      |   |yyyyyy|  |
     +---------+   +---------+

And region is going to be truncated by size y (i.g.
region_truncate(&region, region_used() - y)). After this operation
second slab will remain empty (slab.used == 0). Currently, this slab is
returned back to the slab cache, which leads to slab rotation. This may
not be useful in terms of performance, especially for requests which
don't abuse region memory (for instance, SQL queries) but do call
region_truncate() intensively. For example, during transfer tuples to
ephemeral table truncate() is called for each tuple. What is more,
truncate is also called on each returned tuple in sql_row_to_port()
(see runtime_tuple_new()).

Also, taking into consideration revert of 67d7ab4 (see 81dda5b) this may
lead to memory usage fluctuations: region memory in use before query
execution and after may not be the same. For instance: total region memory
in usage is x, but the first slab (head) is empty (since between
requests region_reset() is called). During query execution
region_truncate() is called and first slab is put back to the slab
cache. Now another slab forms head of slab list, but there's no
guarantee that its size is 0 (since slab's sizes are not zeroed on
reset). As a result, total region memory may change (decrease) due to
slab rotation. It is likely to be misleading for users and in particular
for our testing system: to detect region memory leak cases, we have
nothing to do but restart Tarantool instance each time before test.
---
Branch: https://github.com/tarantool/small/tree/np/dont-rotate-region-on-truncate

 small/region.c |  2 +-
 test/region.c  | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 1 deletion(-)

diff --git a/small/region.c b/small/region.c
index 04476c4..b60ad38 100644
--- a/small/region.c
+++ b/small/region.c
@@ -79,7 +79,7 @@ region_truncate(struct region *region, size_t used)
 		struct rslab *slab = rlist_first_entry(&region->slabs.slabs,
 						       struct rslab,
 						       slab.next_in_list);
-		if (slab->used > cut_size) {
+		if (slab->used >= cut_size) {
 			/* This is the last slab to trim. */
 			slab->used -= cut_size;
 			cut_size = 0;
diff --git a/test/region.c b/test/region.c
index bd5a4c1..8735a59 100644
--- a/test/region.c
+++ b/test/region.c
@@ -63,6 +63,74 @@ region_test_truncate()
 	footer();
 }
 
+/**
+ * Make sure that in case cut_size == slab_used (i.e. we are going
+ * to truncate whole slab) slab itself is not put back to the slab
+ * cache. It should be kept in the list and reused instead.
+ */
+void
+region_test_truncate_rotate()
+{
+	header();
+
+	struct region region;
+
+	region_create(&region, &cache);
+
+	size_t alloc1_sz = 10;
+	void *ptr = region_alloc(&region, alloc1_sz);
+
+	fail_unless(ptr != NULL);
+
+	fail_if(region_total(&region) > 5000);
+	size_t total_before_alloc = region_total(&region);
+
+	/*
+	 * This allocation does not fit in previously
+	 * allocated slab (default slab size is 4kb), so
+	 * there's two slabs now in the region list.
+	 */
+	size_t alloc2_sz = 10000;
+	region_alloc(&region, alloc2_sz);
+	fail_if(total_before_alloc == region_total(&region));
+
+	/*
+	 * Before truncate ('x' is occupied space):
+	 *
+	 *    1 slab      2 slab/HEAD
+	 *   10b used      10kb used
+	 *  +---------+   +---------+
+	 *  |xx|      |-->|xxxxxx|  |--> NULL
+	 *  |xx|      |   |xxxxxx|  |
+	 *  +---------+   +---------+
+	 *
+	 * After truncate:
+	 *
+	 *    1 slab      2 slab/HEAD
+	 *   10b used       0kb used
+	 *  +---------+   +---------+
+	 *  |xx|      |-->|         |--> NULL
+	 *  |xx|      |   |         |
+	 *  +---------+   +---------+
+	 *
+	 */
+	size_t total_before_truncate = region_total(&region);
+	region_truncate(&region, alloc1_sz);
+
+	/*
+	 * Whole slab has been purified but it shouldn't be
+	 * returned back to the slab cache. So that it can be
+	 * reused for further allocations.
+	 */
+	fail_if(total_before_truncate != region_total(&region));
+	region_alloc(&region, alloc2_sz);
+	fail_if(total_before_truncate != region_total(&region));
+
+	region_free(&region);
+
+	footer();
+}
+
 int main()
 {
 	quota_init(&quota, UINT_MAX);
@@ -72,6 +140,7 @@ int main()
 
 	region_basic();
 	region_test_truncate();
+	region_test_truncate_rotate();
 
 	slab_cache_destroy(&cache);
 }
-- 
2.15.1

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Konstantin Osipov]

* Nikita Pettik <korablev@tarantool.org> [20/02/06 20:16]:
> Imagine following situation at the moment of region truncation:

LGTM.

 

-- 
Konstantin Osipov, Moscow, Russia

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Vladislav Shpilevoy]

Hi! Thanks for the patch!

On 06/02/2020 18:14, Nikita Pettik wrote:
> Imagine following situation at the moment of region truncation:
> 
>        1 slab      2 slab/HEAD
>      x of s1 used  y of s2 used
>      +---------+   +---------+
> ...->|xx|      |-->|yyyyyy|  |--> NULL
>      |xx|      |   |yyyyyy|  |
>      +---------+   +---------+
> 
> And region is going to be truncated by size y (i.g.
> region_truncate(&region, region_used() - y)). After this operation
> second slab will remain empty (slab.used == 0). Currently, this slab is
> returned back to the slab cache, which leads to slab rotation. This may
> not be useful in terms of performance, especially for requests which
> don't abuse region memory (for instance, SQL queries) but do call
> region_truncate() intensively. For example, during transfer tuples to
> ephemeral table truncate() is called for each tuple. What is more,
> truncate is also called on each returned tuple in sql_row_to_port()
> (see runtime_tuple_new()).

I understand the point about perf and slab oscillation, but
don't see how is it related to the tests.

> Also, taking into consideration revert of 67d7ab4 (see 81dda5b) this may
> lead to memory usage fluctuations: region memory in use before query
> execution and after may not be the same.

Yeah, but your patch does not fix that. It is a bigger problem.
Region does not free its slabs even at fiber_gc() if their total
size is small enough. So how is this related to memory fluctuations?

> For instance: total region memory
> in usage is x, but the first slab (head) is empty (since between
> requests region_reset() is called). During query execution
> region_truncate() is called and first slab is put back to the slab
> cache. Now another slab forms head of slab list, but there's no
> guarantee that its size is 0 (since slab's sizes are not zeroed on
> reset).

How slab size can be 0? You mean 'used' size? In that case it is
zeroed in reset. Otherwise I am missing something.

> As a result, total region memory may change (decrease) due to
> slab rotation. It is likely to be misleading for users and in particular
> for our testing system: to detect region memory leak cases, we have
> nothing to do but restart Tarantool instance each time before test.

From what I see, this patch makes region keep slab more often. It does
not free them more aggressively or something. So how is it going to fix
the slab leak or at least make it less severe?

> ---
> Branch: https://github.com/tarantool/small/tree/np/dont-rotate-region-on-truncate
> 
>  small/region.c |  2 +-
>  test/region.c  | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 70 insertions(+), 1 deletion(-)

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Nikita Pettik]

On 06 Feb 21:48, Vladislav Shpilevoy wrote:
> Hi! Thanks for the patch!
> 
> On 06/02/2020 18:14, Nikita Pettik wrote:
> > Imagine following situation at the moment of region truncation:
> > 
> >        1 slab      2 slab/HEAD
> >      x of s1 used  y of s2 used
> >      +---------+   +---------+
> > ...->|xx|      |-->|yyyyyy|  |--> NULL
> >      |xx|      |   |yyyyyy|  |
> >      +---------+   +---------+
> > 
> > And region is going to be truncated by size y (i.g.
> > region_truncate(&region, region_used() - y)). After this operation
> > second slab will remain empty (slab.used == 0). Currently, this slab is
> > returned back to the slab cache, which leads to slab rotation. This may
> > not be useful in terms of performance, especially for requests which
> > don't abuse region memory (for instance, SQL queries) but do call
> > region_truncate() intensively. For example, during transfer tuples to
> > ephemeral table truncate() is called for each tuple. What is more,
> > truncate is also called on each returned tuple in sql_row_to_port()
> > (see runtime_tuple_new()).
> 
> I understand the point about perf and slab oscillation, but
> don't see how is it related to the tests.

See below.

> > Also, taking into consideration revert of 67d7ab4 (see 81dda5b) this may
> > lead to memory usage fluctuations: region memory in use before query
> > execution and after may not be the same.
> 
> Yeah, but your patch does not fix that. It is a bigger problem.
> Region does not free its slabs even at fiber_gc() if their total
> size is small enough. So how is this related to memory fluctuations?

Let's look at particular example taken from sql/gh-3199-no-mem-leaks.test.lua:

box.execute('SELECT x, y + 3 * b, b FROM test2, test WHERE b = x')

Here's brief region memory use log for this query:

region alloc size 0 //First region allocation of 0 bytes
getting new slab
region alloc size 0
current slab unused 4040 //56 bytes takes slab structure itself
current slab used 0
current slab size 4096
region alloc size 0
... //same values
region free
region alloc size 1
current slab unused 4040
current slab used 0
current slab size 4096
region alloc size 1
...
region alloc size 1
current slab unused 4038
current slab used 2
current slab size 4096
region alloc size 1
...
region join
region truncate
cut size 0 //nothing to truncate
current slab used 4
slabs used 26730 //total region memory in use, before and during execution
region truncate
cut size 4 //cut size matches with memory in use
slab used 4
removing current slab

Slab is purified and put back to the slab cache. At this point we observe
slab rotation. But new slab (i.e. head of list) can be initialized with
non-zero used memory since we reverted Georgy's patch (which zeroed whole
list of slabs). As a result, used memory in first slab has increased (which
looks extremely  contradictory). It can be seen in further logs:
...
cut size 0
slab used 2060 //used memory has bumped from 4 to 2060
slabs used 26726 //total memory in use hasn't changed tho
...
region alloc size 1
current slab unused 1978
current slab used 2062
current slab size 4096
region alloc size 1
current slab unused 1977
current slab used 2063
current slab size 4096
fiber_gc
fiber reset //at this step total memory is 26730 - 2063 = 24667

At the end of execution fibre_gc() is called, which in turn will nullify
slab->used memory consuption and ergo reduce whole fiber.memory.used
consumption by 2063. That's why amount of memory in usage at the end of
query execution does not match with initial value.

Now, if truncate didn't rotate slab, region memory before and after
query execution would be the same. So, it would make tests like this
more stable, since region leaks could be easily detected as difference
between initial (i.e. before query execution) and final
(i.e. after execution) occupied region memory.

> > For instance: total region memory
> > in usage is x, but the first slab (head) is empty (since between
> > requests region_reset() is called). During query execution
> > region_truncate() is called and first slab is put back to the slab
> > cache. Now another slab forms head of slab list, but there's no
> > guarantee that its size is 0 (since slab's sizes are not zeroed on
> > reset).
> 
> How slab size can be 0? You mean 'used' size? In that case it is
> zeroed in reset. Otherwise I am missing something.

Yep, size of used memory. I'll update commit message.
 
> > As a result, total region memory may change (decrease) due to
> > slab rotation. It is likely to be misleading for users and in particular
> > for our testing system: to detect region memory leak cases, we have
> > nothing to do but restart Tarantool instance each time before test.
> 
> From what I see, this patch makes region keep slab more often. It does
> not free them more aggressively or something. So how is it going to fix
> the slab leak or at least make it less severe?

It doesn't affect leak, but it allows avoiding workarounds like server
restart for sql/gh-3199-no-mem-leaks.test.lua:

https://lists.tarantool.org/pipermail/tarantool-patches/2020-January/013837.html

> > ---
> > Branch: https://github.com/tarantool/small/tree/np/dont-rotate-region-on-truncate
> > 
> >  small/region.c |  2 +-
> >  test/region.c  | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 70 insertions(+), 1 deletion(-)

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Vladislav Shpilevoy]

Hi! Thanks for the explanation!

On 07/02/2020 14:58, Nikita Pettik wrote:
> On 06 Feb 21:48, Vladislav Shpilevoy wrote:
>> Hi! Thanks for the patch!
>>
>> On 06/02/2020 18:14, Nikita Pettik wrote:
>>> Imagine following situation at the moment of region truncation:
>>>
>>>        1 slab      2 slab/HEAD
>>>      x of s1 used  y of s2 used
>>>      +---------+   +---------+
>>> ...->|xx|      |-->|yyyyyy|  |--> NULL
>>>      |xx|      |   |yyyyyy|  |
>>>      +---------+   +---------+
>>>
>>> And region is going to be truncated by size y (i.g.
>>> region_truncate(&region, region_used() - y)). After this operation
>>> second slab will remain empty (slab.used == 0). Currently, this slab is
>>> returned back to the slab cache, which leads to slab rotation. This may
>>> not be useful in terms of performance, especially for requests which
>>> don't abuse region memory (for instance, SQL queries) but do call
>>> region_truncate() intensively. For example, during transfer tuples to
>>> ephemeral table truncate() is called for each tuple. What is more,
>>> truncate is also called on each returned tuple in sql_row_to_port()
>>> (see runtime_tuple_new()).
>>
>> I understand the point about perf and slab oscillation, but
>> don't see how is it related to the tests.
> 
> See below.
> 
>>> Also, taking into consideration revert of 67d7ab4 (see 81dda5b) this may
>>> lead to memory usage fluctuations: region memory in use before query
>>> execution and after may not be the same.
>>
>> Yeah, but your patch does not fix that. It is a bigger problem.
>> Region does not free its slabs even at fiber_gc() if their total
>> size is small enough. So how is this related to memory fluctuations?
> 
> Let's look at particular example taken from sql/gh-3199-no-mem-leaks.test.lua:
> 
> box.execute('SELECT x, y + 3 * b, b FROM test2, test WHERE b = x')
> 
> Here's brief region memory use log for this query:
> 
> region alloc size 0 //First region allocation of 0 bytes
> getting new slab
> region alloc size 0
> current slab unused 4040 //56 bytes takes slab structure itself
> current slab used 0
> current slab size 4096
> region alloc size 0
> ... //same values
> region free
> region alloc size 1
> current slab unused 4040
> current slab used 0
> current slab size 4096
> region alloc size 1
> ...
> region alloc size 1
> current slab unused 4038
> current slab used 2
> current slab size 4096
> region alloc size 1
> ...
> region join
> region truncate
> cut size 0 //nothing to truncate
> current slab used 4
> slabs used 26730 //total region memory in use, before and during execution
> region truncate
> cut size 4 //cut size matches with memory in use
> slab used 4
> removing current slab
> 
> Slab is purified and put back to the slab cache. At this point we observe
> slab rotation. But new slab (i.e. head of list) can be initialized with
> non-zero used memory since we reverted Georgy's patch (which zeroed whole
> list of slabs). As a result, used memory in first slab has increased (which
> looks extremely  contradictory). It can be seen in further logs:
> ...
> cut size 0
> slab used 2060 //used memory has bumped from 4 to 2060
> slabs used 26726 //total memory in use hasn't changed tho
> ...
> region alloc size 1
> current slab unused 1978
> current slab used 2062
> current slab size 4096
> region alloc size 1
> current slab unused 1977
> current slab used 2063
> current slab size 4096
> fiber_gc
> fiber reset //at this step total memory is 26730 - 2063 = 24667
> 
> At the end of execution fibre_gc() is called, which in turn will nullify
> slab->used memory consuption and ergo reduce whole fiber.memory.used
> consumption by 2063. That's why amount of memory in usage at the end of
> query execution does not match with initial value.
> 
> Now, if truncate didn't rotate slab, region memory before and after
> query execution would be the same. So, it would make tests like this
> more stable, since region leaks could be easily detected as difference
> between initial (i.e. before query execution) and final
> (i.e. after execution) occupied region memory.

Aha, now I see. region_reset() does not nullify all the
slabs. I missed that the revert is already pushed. Yes, then
looks fine. Except that if a request uses more than 128Kb, then
it will call region_free() in fiber_gc() and will reduce memory
consumption anyway. But for small tests may help.

The patch LGTM.

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Nikita Pettik]

On 08 Feb 01:28, Vladislav Shpilevoy wrote:
> Hi! Thanks for the explanation!
> 
> On 07/02/2020 14:58, Nikita Pettik wrote:
> > ...
> > region alloc size 1
> > current slab unused 1978
> > current slab used 2062
> > current slab size 4096
> > region alloc size 1
> > current slab unused 1977
> > current slab used 2063
> > current slab size 4096
> > fiber_gc
> > fiber reset //at this step total memory is 26730 - 2063 = 24667
> > 
> > At the end of execution fibre_gc() is called, which in turn will nullify
> > slab->used memory consuption and ergo reduce whole fiber.memory.used
> > consumption by 2063. That's why amount of memory in usage at the end of
> > query execution does not match with initial value.
> > 
> > Now, if truncate didn't rotate slab, region memory before and after
> > query execution would be the same. So, it would make tests like this
> > more stable, since region leaks could be easily detected as difference
> > between initial (i.e. before query execution) and final
> > (i.e. after execution) occupied region memory.
> 
> Aha, now I see. region_reset() does not nullify all the
> slabs. I missed that the revert is already pushed. Yes, then
> looks fine. Except that if a request uses more than 128Kb, then
> it will call region_free() in fiber_gc() and will reduce memory
> consumption anyway. But for small tests may help.
> 
> The patch LGTM.

Fixed a few typos in commit message and re-pushed. Patch received 2 LGTMs;
Alexander Tikhonov reported that there's no performance degradations (as
well as significant gains) according to sysbench.

Re: [Tarantool-patches] [PATCH] region: do not rotate slabs in case of single slab purification

[Aleksandr Lyapunov]

[-- Attachment #1: Type: text/plain, Size: 5600 bytes --]

I have doubts about this patch. It optimizes one case but degrades another.
Looking at the picture you provided I think about a case:
allocate small xx
allocate huge yyyyyy once. real huge.
truncate the yyyyyy
allocate small yy
truncate that yy
allocate small yy
truncate that yy

Without your patch yy will be allocated near xx, after the second slab was
used for yyyyyy and released then.

With you patch small yy will be allocated in the huge second slab with
a large amount of memory wasted in both slabs and losing data locality.

I think the solution should be more careful:
1)huge slabs should not be reserved in the suggested way.
2)space in the previous slab should be reused if possible.
3)if we only had performance test of the allocator..


> Imagine following situation at the moment of region truncation:
>
>         1 slab      2 slab/HEAD
>       x of s1 used  y of s2 used
>       +---------+   +---------+
> ...->|xx|      |-->|yyyyyy|  |--> NULL
>       |xx|      |   |yyyyyy|  |
>       +---------+   +---------+
>
> And region is going to be truncated by size y (i.g.
> region_truncate(&region, region_used() - y)). After this operation
> second slab will remain empty (slab.used == 0). Currently, this slab is
> returned back to the slab cache, which leads to slab rotation. This may
> not be useful in terms of performance, especially for requests which
> don't abuse region memory (for instance, SQL queries) but do call
> region_truncate() intensively. For example, during transfer tuples to
> ephemeral table truncate() is called for each tuple. What is more,
> truncate is also called on each returned tuple in sql_row_to_port()
> (see runtime_tuple_new()).
>
> Also, taking into consideration revert of 67d7ab4 (see 81dda5b) this may
> lead to memory usage fluctuations: region memory in use before query
> execution and after may not be the same. For instance: total region memory
> in usage is x, but the first slab (head) is empty (since between
> requests region_reset() is called). During query execution
> region_truncate() is called and first slab is put back to the slab
> cache. Now another slab forms head of slab list, but there's no
> guarantee that its size is 0 (since slab's sizes are not zeroed on
> reset). As a result, total region memory may change (decrease) due to
> slab rotation. It is likely to be misleading for users and in particular
> for our testing system: to detect region memory leak cases, we have
> nothing to do but restart Tarantool instance each time before test.
> ---
> Branch:https://github.com/tarantool/small/tree/np/dont-rotate-region-on-truncate
>
>   small/region.c |  2 +-
>   test/region.c  | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 70 insertions(+), 1 deletion(-)
>
> diff --git a/small/region.c b/small/region.c
> index 04476c4..b60ad38 100644
> --- a/small/region.c
> +++ b/small/region.c
> @@ -79,7 +79,7 @@ region_truncate(struct region *region, size_t used)
>   		struct rslab *slab = rlist_first_entry(&region->slabs.slabs,
>   						       struct rslab,
>   						       slab.next_in_list);
> -		if (slab->used > cut_size) {
> +		if (slab->used >= cut_size) {
>   			/* This is the last slab to trim. */
>   			slab->used -= cut_size;
>   			cut_size = 0;
> diff --git a/test/region.c b/test/region.c
> index bd5a4c1..8735a59 100644
> --- a/test/region.c
> +++ b/test/region.c
> @@ -63,6 +63,74 @@ region_test_truncate()
>   	footer();
>   }
>   
> +/**
> + * Make sure that in case cut_size == slab_used (i.e. we are going
> + * to truncate whole slab) slab itself is not put back to the slab
> + * cache. It should be kept in the list and reused instead.
> + */
> +void
> +region_test_truncate_rotate()
> +{
> +	header();
> +
> +	struct region region;
> +
> +	region_create(&region, &cache);
> +
> +	size_t alloc1_sz = 10;
> +	void *ptr = region_alloc(&region, alloc1_sz);
> +
> +	fail_unless(ptr != NULL);
> +
> +	fail_if(region_total(&region) > 5000);
> +	size_t total_before_alloc = region_total(&region);
> +
> +	/*
> +	 * This allocation does not fit in previously
> +	 * allocated slab (default slab size is 4kb), so
> +	 * there's two slabs now in the region list.
> +	 */
> +	size_t alloc2_sz = 10000;
> +	region_alloc(&region, alloc2_sz);
> +	fail_if(total_before_alloc == region_total(&region));
> +
> +	/*
> +	 * Before truncate ('x' is occupied space):
> +	 *
> +	 *    1 slab      2 slab/HEAD
> +	 *   10b used      10kb used
> +	 *  +---------+   +---------+
> +	 *  |xx|      |-->|xxxxxx|  |--> NULL
> +	 *  |xx|      |   |xxxxxx|  |
> +	 *  +---------+   +---------+
> +	 *
> +	 * After truncate:
> +	 *
> +	 *    1 slab      2 slab/HEAD
> +	 *   10b used       0kb used
> +	 *  +---------+   +---------+
> +	 *  |xx|      |-->|         |--> NULL
> +	 *  |xx|      |   |         |
> +	 *  +---------+   +---------+
> +	 *
> +	 */
> +	size_t total_before_truncate = region_total(&region);
> +	region_truncate(&region, alloc1_sz);
> +
> +	/*
> +	 * Whole slab has been purified but it shouldn't be
> +	 * returned back to the slab cache. So that it can be
> +	 * reused for further allocations.
> +	 */
> +	fail_if(total_before_truncate != region_total(&region));
> +	region_alloc(&region, alloc2_sz);
> +	fail_if(total_before_truncate != region_total(&region));
> +
> +	region_free(&region);
> +
> +	footer();
> +}
> +
>   int main()
>   {
>   	quota_init(&quota, UINT_MAX);
> @@ -72,6 +140,7 @@ int main()
>   
>   	region_basic();
>   	region_test_truncate();
> +	region_test_truncate_rotate();
>   
>   	slab_cache_destroy(&cache);
>   }
> -- 
> 2.15.1


[-- Attachment #2: Type: text/html, Size: 5965 bytes --]