staging: zcache: xcfmalloc support
cover staging: zcache: xcfmalloc support
This patchset introduces a new memory allocator for persistent pages for zcache. The current allocator is xvmalloc. xvmalloc has two notable limitations:
* High (up to 50%) external fragmentation on allocation sets > PAGE_SIZE/2
* No compaction support which reduces page reclaimation
xcfmalloc seeks to fix these issues by using scatter-gather model that allows for cross-page allocations and relocatable data blocks.
In tests, with pages that only compress to 75% of their original size, xvmalloc had an effective compression (pages stored / pages used by the compressed memory pool) of ~95% (~20% lost to fragmentation). Almost nothing was gained by the compression in this case. xcfmalloc had an effective compression of ~77% (about ~2% lost to fragmentation and metadata overhead).
xcfmalloc uses the same locking scheme as xvmalloc; a single pool-level spinlock. This can lead to some contention. However, in my tests on a 4 way SMP system, the contention was minimal (200 contentions out of 600k aquisitions). The locking scheme may be able to be improved in the future. In tests, xcfmalloc and xvmalloc had identical throughputs.
While the xcfmalloc design lends itself to compaction, this is not yet implemented. Support will be added in a follow-on patch.
Based on 3.1-rc4.
Seth Jennings (3):
staging: zcache: xcfmalloc memory allocator for zcache
staging: zcache: replace xvmalloc with xcfmalloc
staging: zcache: add zv_page_count and zv_desc_count
drivers/staging/zcache/Makefile | 2 +- drivers/staging/zcache/xcfmalloc.c | 653 ++++++++++++++++++++++++++++++++++ drivers/staging/zcache/xcfmalloc.h | 29 ++ drivers/staging/zcache/zcache-main.c | 154 ++++++--- 4 files changed, 791 insertions(+), 47 deletions(-) create mode 100644 drivers/staging/zcache/xcfmalloc.c create mode 100644 drivers/staging/zcache/xcfmalloc.h
Signature · 1 line
1.7.4.1
PATCH 1/3 staging: zcache: xcfmalloc memory allocator for zcache
xcfmalloc is a memory allocator based on a scatter-gather model that allows for cross-page storage and relocatable data blocks. This is achieved through a simple, though non-standard, memory allocation API.
xcfmalloc is a replacement for the xvmalloc allocator used by zcache for persistent compressed page storage.
xcfmalloc uses a scatter-gather block model in order to reduce external fragmentation (at the expense of an extra memcpy). Low fragmentation is especially important for a zcache allocator since memory will already be under pressure.
It also uses relocatable data blocks in order to allow compaction to take place. Compacting seeks to move blocks to other, less sparsely used, pages such that the maximum number of pages can be returned to the kernel buddy allocator. Compaction is not yet implemented in this patch.
--- drivers/staging/zcache/Makefile | 2 +- drivers/staging/zcache/xcfmalloc.c | 653 ++++++++++++++++++++++++++++++++++++ drivers/staging/zcache/xcfmalloc.h | 29 ++ 3 files changed, 683 insertions(+), 1 deletions(-) create mode 100644 drivers/staging/zcache/xcfmalloc.c create mode 100644 drivers/staging/zcache/xcfmalloc.h
drivers/staging/zcache/Makefile +1 -1
@@ -1,3 +1,3 @@ -zcache-y := zcache-main.o tmem.o +zcache-y := zcache-main.o tmem.o xcfmalloc.o obj-$(CONFIG_ZCACHE) += zcache.o
drivers/staging/zcache/xcfmalloc.c new file +653 -0
653 lines not on this page · raw message
drivers/staging/zcache/xcfmalloc.h new file +29 -0
@@ -0,0 +1,29 @@ +/* xcfmalloc.h */ + +#ifndef _XCFMALLOC_H_ +#define _XCFMALLOC_H_ + +#include <linux/kernel.h> +#include <linux/types.h> + +struct xcf_pool ; +struct xcf_handle { +void *desc; +}; + +void *xcf_malloc (struct xcf_pool *pool,int size,gfp_t flags); +void xcf_free (struct xcf_pool *pool,struct xcf_handle *handle); + +int xcf_write (struct xcf_handle *handle,void *buf); +int xcf_read (struct xcf_handle *handle,void *buf); + +struct xcf_pool *xcf_create_pool (gfp_t flags); +void xcf_destroy_pool (struct xcf_pool *pool); + +int xcf_get_alloc_size (struct xcf_handle *handle); + +u64 xcf_get_total_size_bytes (struct xcf_pool *pool); +int xcf_get_desc_count (struct xcf_pool *pool); + +#endif /* _XCFMALLOC_H_ */ +
Signature · 1 line
1.7.4.1
Re: [PATCH 1/3] staging: zcache: xcfmalloc memory allocator for zcache
Quoted 5 lines · Seth Jennings
drivers/staging/zcache/xcfmalloc.c new file +5
-0+static struct xcf_blkdesc *xcf_find_remove_block (struct xcf_pool *pool, +int size,int blocknum) +{ +int flindex, i; +struct xcf_blkdesc *desc =NULL ;
drivers/staging/zcache/xcfmalloc.c line 254
Quoted 10 lines
drivers/staging/zcache/xcfmalloc.c new file +10
-0+ + flindex =xcf_size_to_flindex (size +sizeof (struct xcf_blkhdr )); + +/* look for best fit */ +if (pool->freelists[flindex]) + goto remove; + +/* if this is the last block allowed in the allocation, we shouldn't +* consider smaller blocks. it's all or nothing now */ +if (blocknum ==XCF_MAX_BLOCKS_PER_ALLOC ) {
In gathering my performance numbers for Dan, I discovered I introduced a regression by making a late change in my development.
This line should be:
if (blocknum != XCF_MAX_BLOCKS_PER_ALLOC) {This regression actually causes xcfmalloc to have the same fragmentation issue as xvmalloc.
drivers/staging/zcache/xcfmalloc.c line 262
Quoted 8 lines
drivers/staging/zcache/xcfmalloc.c new file +8
-0+/* look for largest smaller block */ +for (i = flindex; i >0 ; i--) { +if (pool->freelists[i]) { + flindex = i; + goto remove; + } + } + }
--
Seth
Re: [PATCH 1/3] staging: zcache: xcfmalloc memory allocator for zcache
Quoted 21 lines · Seth Jennings
Quoted 5 lines · Seth Jennings
drivers/staging/zcache/xcfmalloc.c new file +5
-0+static struct xcf_blkdesc *xcf_find_remove_block (struct xcf_pool *pool, +int size,int blocknum) +{ +int flindex, i; +struct xcf_blkdesc *desc =NULL ;drivers/staging/zcache/xcfmalloc.c line 254
Quoted 10 lines
drivers/staging/zcache/xcfmalloc.c new file +10
-0+ + flindex =xcf_size_to_flindex (size +sizeof (struct xcf_blkhdr )); + +/* look for best fit */ +if (pool->freelists[flindex]) + goto remove; + +/* if this is the last block allowed in the allocation, we shouldn't +* consider smaller blocks. it's all or nothing now */ +if (blocknum ==XCF_MAX_BLOCKS_PER_ALLOC ) {In gathering my performance numbers for Dan, I discovered I introduced a regression by making a late change in my development.
Quoted 5 lines
This line should be:
if (blocknum != XCF_MAX_BLOCKS_PER_ALLOC) {This regression actually causes xcfmalloc to have the same fragmentation issue as xvmalloc.
Ok, care to resend a tested and correct patch series then?
greg k-h
PATCH 2/3 staging: zcache: replace xvmalloc with xcfmalloc
In reply to Seth JenningsThis patch replaces xvmalloc with xcfmalloc as the persistent page allocator for zcache.
Because the API is not the same between xvmalloc and xcfmalloc, the changes are not a simple find/replace on the function names.
--- drivers/staging/zcache/zcache-main.c | 130 ++++++++++++++++++++++------------ 1 files changed, 84 insertions(+), 46 deletions(-)
drivers/staging/zcache/zcache-main.c +84 -46
@@ -8,7 +8,7 @@* and, thus indirectly, for cleancache and frontswap. Zcache includes two * page-accessible memory [1] interfaces, both utilizing lzo1x compression: * 1) "compression buddies" ("zbud") is used for ephemeral pages -* 2) xvmalloc is used for persistent pages. +* 2) xcfmalloc is used for persistent pages. * Xvmalloc (based on the TLSF allocator) has very low fragmentation * so maximizes space efficiency, while zbud allows pairs (and potentially, * in the future, more than a pair of) compressed pages to be closely linked
@@ -31,7 +31,7 @@#include <linux/math64.h> #include "tmem.h" -#include "../zram/xvmalloc.h" /* if built in drivers/staging */ +#include "xcfmalloc.h" #if (!defined(CONFIG_CLEANCACHE ) && !defined(CONFIG_FRONTSWAP ))#error "zcache is useless without CONFIG_CLEANCACHE or CONFIG_FRONTSWAP"
@@ -60,7 +60,7 @@ MODULE_LICENSE("GPL");struct zcache_client {struct tmem_pool *tmem_pools[MAX_POOLS_PER_CLIENT ]; -struct xv_pool *xvpool; +struct xcf_pool *xcfmpool;bool allocated;atomic_t refcount; };
@@ -623,9 +623,8 @@ static int zbud_show_cumul_chunk_counts(char *buf)#endif /********** -* This "zv" PAM implementation combines the TLSF-based xvMalloc -* with lzo1x compression to maximize the amount of data that can -* be packed into a physical page. +* This "zv" PAM implementation combines xcfmalloc with lzo1x compression +* to maximize the amount of data that can be packed into a physical page. * * Zv represents a PAM page with the index and object (plus a "size" value * necessary for decompression) immediately preceding the compressed data.
@@ -658,71 +657,97 @@ static unsigned int zv_max_mean_zsize = (PAGE_SIZE / 8) * 5;static unsigned long zv_curr_dist_counts[NCHUNKS ];static unsigned long zv_cumul_dist_counts[NCHUNKS ]; -static struct zv_hdr *zv_create (struct xv_pool *xvpool,uint32_t pool_id, +static DEFINE_PER_CPU(unsigned char *, zv_cbuf); /* zv create buffer */ +static DEFINE_PER_CPU(unsigned char *, zv_dbuf); /* zv decompress buffer */ + +static int zv_cpu_notifier (struct notifier_block *nb, +unsigned long action,void *pcpu) +{ +int cpu = (long )pcpu; + +switch (action) { +case CPU_UP_PREPARE : +per_cpu (zv_cbuf, cpu) = (void *)__get_free_page ( +GFP_KERNEL | __GFP_REPEAT); +per_cpu (zv_dbuf, cpu) = (void *)__get_free_page ( +GFP_KERNEL | __GFP_REPEAT); +break ; +case CPU_DEAD : +case CPU_UP_CANCELED : +free_page ((unsigned long )per_cpu (zv_cbuf, cpu)); +per_cpu (zv_cbuf, cpu) =NULL ; +free_page ((unsigned long )per_cpu (zv_dbuf, cpu)); +per_cpu (zv_dbuf, cpu) =NULL ; +break ; +default : +break ; + } + +return NOTIFY_OK ; +} + + +static void **zv_create (struct xcf_pool *xcfmpool,uint32_t pool_id,struct tmem_oid *oid,uint32_t index,void *cdata,unsigned clen) { -struct page *page; -struct zv_hdr *zv =NULL ; -uint32_t offset; -int alloc_size = clen +sizeof (struct zv_hdr ); -int chunks = (alloc_size + (CHUNK_SIZE -1 )) >>CHUNK_SHIFT ; -int ret; +struct zv_hdr *zv; +u32 size = clen +sizeof (struct zv_hdr ); +int chunks = (size + (CHUNK_SIZE -1 )) >>CHUNK_SHIFT ; +void *handle;BUG_ON (!irqs_disabled ());BUG_ON (chunks >=NCHUNKS ); - ret =xv_malloc (xvpool, alloc_size, - &page, &offset,ZCACHE_GFP_MASK ); -if (unlikely (ret)) - goto out; + + handle =xcf_malloc (xcfmpool, size,ZCACHE_GFP_MASK ); +if (!handle) +return NULL ; + zv_curr_dist_counts[chunks]++; zv_cumul_dist_counts[chunks]++; - zv =kmap_atomic (page,KM_USER0 ) + offset; + + zv = (struct zv_hdr *)((char *)cdata -sizeof (*zv)); zv->index = index; zv->oid = *oid; zv->pool_id = pool_id;SET_SENTINEL (zv,ZVH ); -memcpy ((char *)zv +sizeof (struct zv_hdr ), cdata, clen); -kunmap_atomic (zv,KM_USER0 ); -out: -return zv; +xcf_write (handle, zv); + +return handle; } -static void zv_free (struct xv_pool *xvpool,struct zv_hdr *zv) +static void zv_free (struct xcf_pool *xcfmpool,void *handle) {unsigned long flags; -struct page *page; -uint32_t offset; -uint16_t size =xv_get_object_size (zv); +u32 size =xcf_get_alloc_size (handle);int chunks = (size + (CHUNK_SIZE -1 )) >>CHUNK_SHIFT ; -ASSERT_SENTINEL (zv,ZVH );BUG_ON (chunks >=NCHUNKS ); zv_curr_dist_counts[chunks]--; - size -=sizeof (*zv); -BUG_ON (size ==0 ); -INVERT_SENTINEL (zv,ZVH ); - page =virt_to_page (zv); - offset = (unsigned long )zv & ~PAGE_MASK ; +local_irq_save (flags); -xv_free (xvpool, page, offset); +xcf_free (xcfmpool, handle);local_irq_restore (flags); } -static void zv_decompress (struct page *page,struct zv_hdr *zv) +static void zv_decompress (struct page *page,void *handle) {size_t clen =PAGE_SIZE ;char *to_va;unsigned size;int ret; +struct zv_hdr *zv; -ASSERT_SENTINEL (zv,ZVH ); - size =xv_get_object_size (zv) -sizeof (*zv); + size =xcf_get_alloc_size (handle) -sizeof (*zv);BUG_ON (size ==0 ); + zv = (struct zv_hdr *)(get_cpu_var (zv_dbuf)); +xcf_read (handle, zv); +ASSERT_SENTINEL (zv,ZVH ); to_va =kmap_atomic (page,KM_USER0 ); ret =lzo1x_decompress_safe ((char *)zv +sizeof (*zv), size, to_va, &clen);kunmap_atomic (to_va,KM_USER0 ); +put_cpu_var (zv_dbuf);BUG_ON (ret !=LZO_E_OK );BUG_ON (clen !=PAGE_SIZE ); }
@@ -949,8 +974,9 @@ int zcache_new_client(uint16_t cli_id) goto out; cli->allocated =1 ;#ifdef CONFIG_FRONTSWAP - cli->xvpool =xv_create_pool (); -if (cli->xvpool ==NULL ) + cli->xcfmpool = +xcf_create_pool (ZCACHE_GFP_MASK ); +if (cli->xcfmpool ==NULL ) goto out;#endif ret =0 ;
@@ -1154,7 +1180,7 @@ static void *zcache_pampd_create(char *data, size_t size, bool raw, int eph, struct tmem_pool *pool, struct tmem_oid *oid, uint32_t index) { - void *pampd = NULL, *cdata; + void *pampd = NULL, *cdata = NULL;size_t clen;int ret;unsigned long count;
@@ -1186,26 +1212,30 @@ static void *zcache_pampd_create(char *data, size_t size, bool raw, int eph,if (curr_pers_pampd_count > (zv_page_count_policy_percent * totalram_pages) /100 ) goto out; + cdata =get_cpu_var (zv_cbuf) +sizeof (struct zv_hdr ); ret =zcache_compress (page, &cdata, &clen);if (ret ==0 ) goto out;/* reject if compression is too poor */ if (clen > zv_max_zsize) { zcache_compress_poor++; +put_cpu_var (zv_cbuf); goto out; }/* reject if mean compression is too poor */ if ((clen > zv_max_mean_zsize) && (curr_pers_pampd_count >0 )) { - total_zsize =xv_get_total_size_bytes (cli->xvpool); + total_zsize =xcf_get_total_size_bytes (cli->xcfmpool); zv_mean_zsize =div_u64 (total_zsize, curr_pers_pampd_count);if (zv_mean_zsize > zv_max_mean_zsize) { zcache_mean_compress_poor++; +put_cpu_var (zv_cbuf); goto out; } } - pampd = (void *)zv_create (cli->xvpool, pool->pool_id, + pampd = (void *)zv_create (cli->xcfmpool, pool->pool_id, oid, index, cdata, clen); +put_cpu_var (zv_cbuf);if (pampd ==NULL ) goto out; count =atomic_inc_return (&zcache_curr_pers_pampd_count);
@@ -1262,7 +1292,7 @@ static void zcache_pampd_free(void *pampd, struct tmem_pool *pool,atomic_dec (&zcache_curr_eph_pampd_count);BUG_ON (atomic_read (&zcache_curr_eph_pampd_count) <0 ); }else { -zv_free (cli->xvpool, (struct zv_hdr *)pampd); +zv_free (cli->xcfmpool, pampd);atomic_dec (&zcache_curr_pers_pampd_count);BUG_ON (atomic_read (&zcache_curr_pers_pampd_count) <0 ); }
@@ -1309,11 +1339,16 @@ static DEFINE_PER_CPU(unsigned char *, zcache_dstmem);static int zcache_compress (struct page *from,void **out_va,size_t *out_len) {int ret =0 ; -unsigned char *dmem =__get_cpu_var (zcache_dstmem); +unsigned char *dmem;unsigned char *wmem =__get_cpu_var (zcache_workmem);char *from_va;BUG_ON (!irqs_disabled ()); +if (out_va && *out_va) + dmem = *out_va; +else + dmem =__get_cpu_var (zcache_dstmem); +if (unlikely (dmem ==NULL || wmem ==NULL )) goto out;/* no buffer, so can't compress */ from_va =kmap_atomic (from,KM_USER0 );
@@ -1331,7 +1366,7 @@ out:static int zcache_cpu_notifier (struct notifier_block *nb,unsigned long action,void *pcpu) { -int cpu = (long )pcpu; +int ret, cpu = (long )pcpu;struct zcache_preload *kp;switch (action) {
@@ -1363,7 +1398,10 @@ static int zcache_cpu_notifier(struct notifier_block *nb,default :break ; } -return NOTIFY_OK ; + + ret =zv_cpu_notifier (nb, action, pcpu); + +return ret; }static struct notifier_block zcache_cpu_notifier_block = {
@@ -1991,7 +2029,7 @@ static int __init zcache_init(void) old_ops =zcache_frontswap_register_ops ();pr_info ("zcache: frontswap enabled using kernel " -"transcendent memory and xvmalloc\n" ); +"transcendent memory and xcfmalloc\n" );if (old_ops.init !=NULL )pr_warning ("ktmem: frontswap_ops overridden" ); }
Signature · 1 line
1.7.4.1
PATCH 3/3 staging: zcache: add zv_page_count and zv_desc_count
In reply to Seth JenningsThis patch adds the zv_page_count and zv_desc_count attributes to the zcache sysfs. They are read-only attributes and return the number of pages and the number of block descriptors in use by the pool respectively.
These statistics can be used to calculate effective compression and block descriptor overhead for the xcfmalloc allocator.
Using the frontswap curr_pages attribute, effective compression
is: zv_page_count / curr_pages
Using /proc/slabinfo to get the objsize for a xcf_desc_cache object, descriptor overhead is: zv_desc_count * objsize
--- drivers/staging/zcache/zcache-main.c | 24 ++++++++++++++++++++++++ 1 files changed, 24 insertions(+), 0 deletions(-)
drivers/staging/zcache/zcache-main.c +24 -0
@@ -789,6 +789,24 @@ static int zv_cumul_dist_counts_show(char *buf)return p - buf; } +static int zv_page_count_show (char *buf) +{ +char *p = buf; +unsigned long count; + count =xcf_get_total_size_bytes (zcache_host.xcfmpool) >>PAGE_SHIFT ; + p +=sprintf (p,"%lu\n" , count); +return p - buf; +} + +static int zv_desc_count_show (char *buf) +{ +char *p = buf; +unsigned long count; + count =xcf_get_desc_count (zcache_host.xcfmpool); + p +=sprintf (p,"%lu\n" , count); +return p - buf; +} +/* * setting zv_max_zsize via sysfs causes all persistent (e.g. swap) * pages that don't compress to less than this value (including metadata
@@ -1477,6 +1495,10 @@ ZCACHE_SYSFS_RO_CUSTOM(zv_curr_dist_counts, zv_curr_dist_counts_show);ZCACHE_SYSFS_RO_CUSTOM (zv_cumul_dist_counts, zv_cumul_dist_counts_show); +ZCACHE_SYSFS_RO_CUSTOM (zv_page_count, + zv_page_count_show); +ZCACHE_SYSFS_RO_CUSTOM (zv_desc_count, + zv_desc_count_show);static struct attribute *zcache_attrs[] = { &zcache_curr_obj_count_attr.attr,
@@ -1513,6 +1535,8 @@ static struct attribute *zcache_attrs[] = { &zcache_zv_max_zsize_attr.attr, &zcache_zv_max_mean_zsize_attr.attr, &zcache_zv_page_count_policy_percent_attr.attr, + &zcache_zv_page_count_attr.attr, + &zcache_zv_desc_count_attr.attr, NULL, };
Signature · 1 line
1.7.4.1
Quoted 6 lines
This patchset introduces a new memory allocator for persistent pages for zcache. The current allocator is xvmalloc. xvmalloc has two notable limitations:
* High (up to 50%) external fragmentation on allocation sets > PAGE_SIZE/2
* No compaction support which reduces page reclaimation
Quoted 8 lines
xcfmalloc seeks to fix these issues by using scatter-gather model that allows for cross-page allocations and relocatable data blocks.
In tests, with pages that only compress to 75% of their original size, xvmalloc had an effective compression (pages stored / pages used by the compressed memory pool) of ~95% (~20% lost to fragmentation). Almost nothing was gained by the compression in this case. xcfmalloc had an effective compression of ~77% (about ~2% lost to fragmentation and metadata overhead).
Hi Seth --
Do you have any data comparing xcfmalloc vs xvmalloc for compression ratio and/or performance (cycles to compress or decompress different pages) on a wide(r) range of data? Assuming xcfmalloc isn't "always better", maybe it would be best to allow the algorithm to be selectable? (And then we would also need to decide the default.)
(Hopefully Nitin will have a chance to comment, since he has much more expertise in compression than I do.)
Thanks,
Dan
Quoted 15 lines · Dan Magenheimer
Quoted 6 lines
This patchset introduces a new memory allocator for persistent pages for zcache. The current allocator is xvmalloc. xvmalloc has two notable limitations:
* High (up to 50%) external fragmentation on allocation sets > PAGE_SIZE/2
* No compaction support which reduces page reclaimationQuoted 8 lines
xcfmalloc seeks to fix these issues by using scatter-gather model that allows for cross-page allocations and relocatable data blocks.
In tests, with pages that only compress to 75% of their original size, xvmalloc had an effective compression (pages stored / pages used by the compressed memory pool) of ~95% (~20% lost to fragmentation). Almost nothing was gained by the compression in this case. xcfmalloc had an effective compression of ~77% (about ~2% lost to fragmentation and metadata overhead).
Quoted 9 lines
Hi Seth --
Do you have any data comparing xcfmalloc vs xvmalloc for compression ratio and/or performance (cycles to compress or decompress different pages) on a wide(r) range of data? Assuming xcfmalloc isn't "always better", maybe it would be best to allow the algorithm to be selectable? (And then we would also need to decide the default.)
I can get you some results comparing the two tomorrow.
You have to make the distinction between the "compression ratio" and the "effective compression". The compression ratio is the same since the compression algorithm, LZO, was changed. The effective compression, the ratio of stored compressed pages to allocator pool pages, is different between the two, especially for allocation sets > PAGE_SIZE/2.
What the numbers will tell you is that for allocations sets < PAGE_SIZE/2 xcfmalloc is a little worse (~2% greater overhead). But for allocation sets > PAGE_SIZE/2, xcfmalloc has up to a 50% advantage over xvmalloc.
As far as performance numbers, all I can see is that the throughput is the same between the two. I'm not sure how to get, for example, and cycles delta between the two.
I would be difficult to make it selectable because the function signatures (and some concepts) aren't the same. You can see the changes that were required in the patch 2/3.
Quoted 5 lines
(Hopefully Nitin will have a chance to comment, since he has much more expertise in compression than I do.)
Thanks,
Dan
Thanks,
Seth
Quoted 8 lines
Quoted 7 lines
Do you have any data comparing xcfmalloc vs xvmalloc for compression ratio and/or performance (cycles to compress or decompress different pages) on a wide(r) range of data? Assuming xcfmalloc isn't "always better", maybe it would be best to allow the algorithm to be selectable? (And then we would also need to decide the default.)
Quoted 6 lines
I can get you some results comparing the two tomorrow.
You have to make the distinction between the "compression ratio" and the "effective compression". The compression ratio is the same since the compression algorithm, LZO, was changed. The effective compression,
changed -> NOT changed, correct? LZO is used in both? I had forgotten that, so the only issue might be the overhead.
Quoted 9 lines
the ratio of stored compressed pages to allocator pool pages, is different between the two, especially for allocation sets > PAGE_SIZE/2.
What the numbers will tell you is that for allocations sets < PAGE_SIZE/2 xcfmalloc is a little worse (~2% greater overhead). But for allocation sets > PAGE_SIZE/2, xcfmalloc has up to a 50% advantage over xvmalloc.
Quoted 4 lines
As far as performance numbers, all I can see is that the throughput is the same between the two. I'm not sure how to get, for example, and cycles delta between the two.
IIRC, xvmalloc has O(1) overhead regardless of the number of chunks of data stored. Some algorithms are O(N) or even O(N**2), i.e. might walk a potentially increasingly very long list of allocations/descriptors
to find a slot, which would not be acceptable for zcache as, for a large data set, the overhead might be much worse than the cycles-to-compress. Which is xcfmalloc, O(1) or O(N) or O(N**2)?
(Also, since I think interrupts are still disabled, reading the tsc before/after should be safe to get the cycles delta.)
Quoted 4 lines
I would be difficult to make it selectable because the function signatures (and some concepts) aren't the same. You can see the changes that were required in the patch 2/3.
Then I definitely would like to see some review and discussion from Nitin. Clearly xcfmalloc is better for poorly-compressible data; I would like to be confident that it is not "worse" for another large common set of data.
An even better implementation could be if both are active and the selection is made at runtime depending on the compressibility of the data, i.e. poorly-compressible data gets stored in xcfmalloc and other data in xvmalloc? Probably not worth the effort, but food for thought.
Thanks,
Dan
Quoted 10 lines · Dan Magenheimer
Quoted 10 lines
Quoted 7 lines
Do you have any data comparing xcfmalloc vs xvmalloc for compression ratio and/or performance (cycles to compress or decompress different pages) on a wide(r) range of data? Assuming xcfmalloc isn't "always better", maybe it would be best to allow the algorithm to be selectable? (And then we would also need to decide the default.)
I can get you some results comparing the two tomorrow.
Quoted 9 lines
Quoted 4 lines
You have to make the distinction between the "compression ratio" and the "effective compression". The compression ratio is the same since the compression algorithm, LZO, was changed. The effective compression,
changed -> NOT changed, correct? LZO is used in both? I had forgotten that, so the only issue might be the overhead.
Yes, LZO is NOT changed. Typo on my part.
Quoted 14 lines
Quoted 9 lines
the ratio of stored compressed pages to allocator pool pages, is different between the two, especially for allocation sets > PAGE_SIZE/2.
What the numbers will tell you is that for allocations sets < PAGE_SIZE/2 xcfmalloc is a little worse (~2% greater overhead). But for allocation sets > PAGE_SIZE/2, xcfmalloc has up to a 50% advantage over xvmalloc.
Quoted 4 lines
As far as performance numbers, all I can see is that the throughput is the same between the two. I'm not sure how to get, for example, and cycles delta between the two.
Quoted 8 lines
IIRC, xvmalloc has O(1) overhead regardless of the number of chunks of data stored. Some algorithms are O(N) or even
O(N**2), i.e. might walk a potentially increasingly very long list of allocations/descriptors
to find a slot, which would not be acceptable for zcache as, for a large data set, the overhead might be much worse than the cycles-to-compress. Which is xcfmalloc, O(1) or O(N) orO(N**2)?
xcfmalloc is also 0(1) in that the number of freelists at that have to be checked is constant and not increasing with the number of allocations. The constant hidden in the O(1) for finding a suitable block is NUM_FREELISTS.
The performance on the block lookup could be improved by using a freelist bitmap similar to xvmalloc. However, I don't think there would be a measurable change in performance, because this in not where the zcache_put_page() codepath is spending all its time. The time eater in this codepath is the LZO compression, as dictated by the large difference in throughput depending on the compressibility of the page. This is supported by the metrics I am about to send you.
Quoted 16 lines
(Also, since I think interrupts are still disabled, reading the tsc before/after should be safe to get the cycles delta.)
Quoted 4 lines
I would be difficult to make it selectable because the function signatures (and some concepts) aren't the same. You can see the changes that were required in the patch 2/3.
Then I definitely would like to see some review and discussion from Nitin. Clearly xcfmalloc is better for poorly-compressible data; I would like to be confident that it is not "worse" for another large common set of data.
Quoted 6 lines
An even better implementation could be if both are active and the selection is made at runtime depending on the compressibility of the data, i.e. poorly-compressible data gets stored in xcfmalloc and other data in xvmalloc? Probably not worth the effort, but food for thought.
In the metrics I am about to send, you'll see that xcfmalloc only does <2% worse on zeroed pages (the worst case for xcfmalloc), but does almost 22% better on pages that compress to 75% of their original size.
Quoted 2 lines
Thanks,
Dan
Quoted 4 lines · Seth Jennings
xcfmalloc is also 0(1) in that the number of freelists at that have to be checked is constant and not increasing with the number of allocations. The constant hidden in the O(1) for finding a suitable block is
NUM_FREELISTS.
The algorithm is technically O(n^2) since there are XCF_MAX_BLOCKS_PER_ALLOC searches through XCF_NUM_FREELISTS. There's also the reserved pages refill loop, which is linear too.
xcfmalloc's big compromise is that it doesn't do any searching or fitting. It might needlessly split larger blocks when two small ones would have worked, for instance.
-- Dave
Quoted 10 lines · Dave Hansen
Quoted 4 lines · Seth Jennings
xcfmalloc is also 0(1) in that the number of freelists at that have to be checked is constant and not increasing with the number of allocations. The constant hidden in the O(1) for finding a suitable block is
NUM_FREELISTS.The algorithm is technically O(n^2) since there are
XCF_MAX_BLOCKS_PER_ALLOCsearches throughXCF_NUM_FREELISTS. There's also the reserved pages refill loop, which is linear too.
I was seeing n as the number of allocations. Since XCF_MAX_BLOCKS_PER_ALLOC and XCF_NUM_FREELISTS are constant (i.e. not increasing with the number of allocations) wouldn't it be O(1)?
I see it like this:
for (i=0; i<2; i++) {
do_something();
}vs.
do_something();do_something();
Is one O(n) and the other O(1)? They do the same thing because the loop iterates a constant number of times.
For it to be O(n) it would have to be:
for (i=0; i<n; i++) {
do_something();
}Right?
Quoted 3 lines
xcfmalloc's big compromise is that it doesn't do any searching or fitting. It might needlessly split larger blocks when two small ones would have worked, for instance.
Splitting a larger block is the last option. I might not be understanding you correctly, but find_remove_block() does try to find the optimal block to use, which is "searching and fitting" in my mind.
Quoted 3 lines
-- Dave
Quoted 4 lines · Seth Jennings
I was seeing n as the number of allocations. Since
XCF_MAX_BLOCKS_PER_ALLOCandXCF_NUM_FREELISTSare constant (i.e. not increasing with the number of allocations) wouldn't it be O(1)?
It's the difference between your implementation and the _algorithm_ you've chosen. If someone doubled XCF_MAX_BLOCKS_PER_ALLOC and XCF_NUM_FREELISTS, you'd see the time quadruple, not stay constant. That's a property of the _algorithm_.
Quoted 8 lines
Quoted 3 lines
xcfmalloc's big compromise is that it doesn't do any searching or fitting. It might needlessly split larger blocks when two small ones would have worked, for instance.
Splitting a larger block is the last option. I might not be understanding you correctly, but
find_remove_block()does try to find the optimal block to use, which is "searching and fitting" in my mind.
I don't want to split hairs on the wording. It's obvious, though, that xcfmalloc does not find _optimal_ fits. It also doesn't use the smallest-possible blocks to fit the alloction. Consider if you wanted a 1000 byte allocation (with 10 100-byte buckets and no metadata for simplicity), and had 4 blocks:
900
500,500,500I think it would split a 500 into 100,400, and leave the 400:
500,500
400It took the largest (most valuable) block, and split a 500 block when it didn't have to. The reason it doesn't do this is that it doesn't _search_. It just indexes and guesses. That's *fast*, but it errs on the side of speed rather than being optimal. That's OK, we do it all the time, but it *is* a compromise. We should at least be thinking of the cases when this doesn't perform well.
-- Dave
Quoted 15 lines · Dan Magenheimer
Quoted 6 lines
This patchset introduces a new memory allocator for persistent pages for zcache. The current allocator is xvmalloc. xvmalloc has two notable limitations:
* High (up to 50%) external fragmentation on allocation sets > PAGE_SIZE/2
* No compaction support which reduces page reclaimationQuoted 8 lines
xcfmalloc seeks to fix these issues by using scatter-gather model that allows for cross-page allocations and relocatable data blocks.
In tests, with pages that only compress to 75% of their original size, xvmalloc had an effective compression (pages stored / pages used by the compressed memory pool) of ~95% (~20% lost to fragmentation). Almost nothing was gained by the compression in this case. xcfmalloc had an effective compression of ~77% (about ~2% lost to fragmentation and metadata overhead).
Quoted 9 lines
Hi Seth --
Do you have any data comparing xcfmalloc vs xvmalloc for compression ratio and/or performance (cycles to compress or decompress different pages) on a wide(r) range of data? Assuming xcfmalloc isn't "always better", maybe it would be best to allow the algorithm to be selectable? (And then we would also need to decide the default.)
Ok, so I was able to get some numbers and I said I'd send them out today, so... here they are. 32-bit system. I create a cgroup with a memory.limit_in_bytes of 256MB. Then I ran a program that allocates 512MB, one 4k page a time. The pages can be filled with zeros or text depending on the command arguments. The text is english text that has an average compression ratio, using lzo1x, of 75% with little deviation. zv_max_mean_zsize and zv_max_zsize are both set to 3584 (7 * PAGE_SIZE / 8).
xvmalloc
curr_pages zv_page_count effective compression
zero filled 65859 1269 1.93%
text (75%) 65925 65892 99.95%
xcfmalloc (descriptors are 24 bytes, 170 per 4k page)
curr_pages zv_page_count zv_desc_count effective compression
zero filled 65845 2068 65858 3.72% (+1.79)
text (75%) 65965 50848 114980 78.11% (-21.84)
This shows that xvmalloc is 1.79 points better on zero filled pages. This is because xcfmalloc has higher internal fragmentation because the block sizes aren't as granular as xvmalloc. This contributes to 1.21 points of the delta. xcfmalloc also has block descriptors, which contributes to the remaining 0.58 points.
It also shows that xcfmalloc is 21.84 points better on text filled pages. This is because of xcfmalloc allocations can span different pages which greatly reduces external fragmentation compared to xvmalloc.
I did some quick tests with "time" using the same program and the timings are very close (3 run average, little deviation):
xvmalloc:
zero filled 0m0.852s
text (75%) 0m14.415s
xcfmalloc:
zero filled 0m0.870s
text (75%) 0m15.089s
I suspect that the small decrease in throughput is due to the extra memcpy in xcfmalloc. However, these timing, more than anything, demonstrate that the throughput is GREATLY effected by the compressibility of the data.
In all cases, all swapped pages where captured by frontswap with no put failures.
Quoted 5 lines
(Hopefully Nitin will have a chance to comment, since he has much more expertise in compression than I do.)
Thanks,
Dan