[PATCH] zsmalloc documentation

[PATCH] zsmalloc documentation

[Nitin Gupta]

Signed-off-by: Nitin Gupta <ngupta@vflare.org>
---
 drivers/staging/zsmalloc/zsmalloc-main.c |   49 ++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/drivers/staging/zsmalloc/zsmalloc-main.c b/drivers/staging/zsmalloc/zsmalloc-main.c
index 4496737..f80f2fd 100644
--- a/drivers/staging/zsmalloc/zsmalloc-main.c
+++ b/drivers/staging/zsmalloc/zsmalloc-main.c
@@ -10,6 +10,55 @@
  * Released under the terms of GNU General Public License Version 2.0
  */
 
+
+/*
+ * This allocator is designed for use with zcache and zram. Thus, the
+ * allocator is supposed to work well under low memory conditions. In
+ * particular, it never attempts higher order page allocation which is
+ * very likely to fail under memory pressure. On the other hand, if we
+ * just use single (0-order) pages, it would suffer from very high
+ * fragmentation -- any object of size PAGE_SIZE/2 or larger would occupy
+ * an entire page. This was one of the major issues with its predecessor
+ * (xvmalloc).
+ *
+ * To overcome these issues, zsmalloc allocates a bunch of 0-order pages
+ * and links them together using various 'struct page' fields. These linked
+ * pages act as a single higher-order page i.e. an object can span 0-order
+ * page boundaries. The code refers to these linked pages as a single entity
+ * called zspage.
+ *
+ * Following is how we use various fields and flags of underlying
+ * struct page(s) to form a zspage.
+ *
+ * Usage of struct page fields:
+ *	page->first_page: points to the first component (0-order) page
+ *	[first] page->private (union with page->first_page): refers to the
+ *		component page after the first page
+ *
+ *	[first] page->freelist: points to the first free object in zspage.
+ *		Free objects are linked together using in-place
+ *		metadata.
+ *	page->index (union with page->freelist): offset of the first object
+ *		starting in this page. For the first page, this is
+ *		always 0, so we use this field (aka freelist) to point
+ *		to the first free object in zspage.
+ *
+ *	[first] page->objects: maximum number of objects we can store in this
+ *		zspage (class->zspage_order * PAGE_SIZE / class->size)
+ *
+ *	page->lru: links together all component pages (except the first page)
+ *		of a zspage
+ *	[first] page->lru: links together first pages of various zspages.
+ *		Basically forming list of zspages in a fullness group.
+ *
+ *	[first] page->mapping: class index and fullness group of the zspage
+ *
+ * Usage of struct page flags:
+ *	PG_private: identifies the first component page
+ *	PG_private2: identifies the last component page
+ *
+ */
+
 #ifdef CONFIG_ZSMALLOC_DEBUG
 #define DEBUG
 #endif
-- 
1.7.10.2

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] zsmalloc documentation

[Konrad Rzeszutek Wilk]

On Sun, Jun 03, 2012 at 01:20:05PM -0700, Nitin Gupta wrote:
> Signed-off-by: Nitin Gupta <ngupta@vflare.org>
> ---
>  drivers/staging/zsmalloc/zsmalloc-main.c |   49 ++++++++++++++++++++++++++++++
>  1 file changed, 49 insertions(+)
> 
> diff --git a/drivers/staging/zsmalloc/zsmalloc-main.c b/drivers/staging/zsmalloc/zsmalloc-main.c
> index 4496737..f80f2fd 100644
> --- a/drivers/staging/zsmalloc/zsmalloc-main.c
> +++ b/drivers/staging/zsmalloc/zsmalloc-main.c
> @@ -10,6 +10,55 @@
>   * Released under the terms of GNU General Public License Version 2.0
>   */
>  
> +
> +/*
> + * This allocator is designed for use with zcache and zram. Thus, the
> + * allocator is supposed to work well under low memory conditions. In
> + * particular, it never attempts higher order page allocation which is
> + * very likely to fail under memory pressure. On the other hand, if we
> + * just use single (0-order) pages, it would suffer from very high
> + * fragmentation -- any object of size PAGE_SIZE/2 or larger would occupy
> + * an entire page. This was one of the major issues with its predecessor
> + * (xvmalloc).
> + *
> + * To overcome these issues, zsmalloc allocates a bunch of 0-order pages
> + * and links them together using various 'struct page' fields. These linked
> + * pages act as a single higher-order page i.e. an object can span 0-order
> + * page boundaries. The code refers to these linked pages as a single entity
> + * called zspage.
> + *
> + * Following is how we use various fields and flags of underlying
> + * struct page(s) to form a zspage.
> + *
> + * Usage of struct page fields:

I took your definition and grouped them a bit differently:
Not sure if it is more easier to read?

page->first_page: points to the first component (0-order) page
page->index (union with page->freelist): offset of the first object
	starting in this page. For the first page, this is
	always 0, so we use this field (aka freelist) to point
	to the first free object in zspage.
page->lru: links together all component pages (except the first page)
	of a zspage

For _first_ page only:

page->private (union with page->first_page): refers to the
	component page after the first page
page->freelist: points to the first free object in zspage.
	Free objects are linked together using in-place
	metadata.
page->objects: maximum number of objects we can store in this
	zspage (class->zspage_order * PAGE_SIZE / class->size)
page->lru: links together first pages of various zspages.
	Basically forming list of zspages in a fullness group.
page->mapping: class index and fullness group of the zspage

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] zsmalloc documentation

[Nitin Gupta]

On 06/09/2012 04:29 AM, Konrad Rzeszutek Wilk wrote:

> On Sun, Jun 03, 2012 at 01:20:05PM -0700, Nitin Gupta wrote:
>> Signed-off-by: Nitin Gupta <ngupta@vflare.org>
>> ---
>>  drivers/staging/zsmalloc/zsmalloc-main.c |   49 ++++++++++++++++++++++++++++++
>>  1 file changed, 49 insertions(+)
>>
>> diff --git a/drivers/staging/zsmalloc/zsmalloc-main.c b/drivers/staging/zsmalloc/zsmalloc-main.c
>> index 4496737..f80f2fd 100644
>> --- a/drivers/staging/zsmalloc/zsmalloc-main.c
>> +++ b/drivers/staging/zsmalloc/zsmalloc-main.c
>> @@ -10,6 +10,55 @@
>>   * Released under the terms of GNU General Public License Version 2.0
>>   */
>>  
>> +
>> +/*
>> + * This allocator is designed for use with zcache and zram. Thus, the
>> + * allocator is supposed to work well under low memory conditions. In
>> + * particular, it never attempts higher order page allocation which is
>> + * very likely to fail under memory pressure. On the other hand, if we
>> + * just use single (0-order) pages, it would suffer from very high
>> + * fragmentation -- any object of size PAGE_SIZE/2 or larger would occupy
>> + * an entire page. This was one of the major issues with its predecessor
>> + * (xvmalloc).
>> + *
>> + * To overcome these issues, zsmalloc allocates a bunch of 0-order pages
>> + * and links them together using various 'struct page' fields. These linked
>> + * pages act as a single higher-order page i.e. an object can span 0-order
>> + * page boundaries. The code refers to these linked pages as a single entity
>> + * called zspage.
>> + *
>> + * Following is how we use various fields and flags of underlying
>> + * struct page(s) to form a zspage.
>> + *
>> + * Usage of struct page fields:
> 
> I took your definition and grouped them a bit differently:
> Not sure if it is more easier to read?
> 
> page->first_page: points to the first component (0-order) page
> page->index (union with page->freelist): offset of the first object
> 	starting in this page. For the first page, this is
> 	always 0, so we use this field (aka freelist) to point
> 	to the first free object in zspage.
> page->lru: links together all component pages (except the first page)
> 	of a zspage
> 
> For _first_ page only:
> 
> page->private (union with page->first_page): refers to the
> 	component page after the first page
> page->freelist: points to the first free object in zspage.
> 	Free objects are linked together using in-place
> 	metadata.
> page->objects: maximum number of objects we can store in this
> 	zspage (class->zspage_order * PAGE_SIZE / class->size)
> page->lru: links together first pages of various zspages.
> 	Basically forming list of zspages in a fullness group.
> page->mapping: class index and fullness group of the zspage


This regrouping indeed looks cleaner. I will send the revised patch soon.

Thanks,
Nitin

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>