[PATCH 3/6] compcache: TLSF Allocator interface - Kernel

This is a discussion on [PATCH 3/6] compcache: TLSF Allocator interface - Kernel ; Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for variable size compressed pages. Its fast and gives low fragmentation. Following links give details on this allocator: *- http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf *- http://code.google.com/p/compcache/wiki/TLSFAllocator This kernel port of TLSF (v2.3.2) introduces ...

+ Reply to Thread
Results 1 to 6 of 6

Thread: [PATCH 3/6] compcache: TLSF Allocator interface

  1. [PATCH 3/6] compcache: TLSF Allocator interface

    Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for
    variable size compressed pages. Its fast and gives low fragmentation.
    Following links give details on this allocator:
    *- http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf
    *- http://code.google.com/p/compcache/wiki/TLSFAllocator

    This kernel port of TLSF (v2.3.2) introduces several changes but underlying
    algorithm remains the same.

    Changelog TLSF v2.3.2 vs this kernel port
    *- Pool now dynamically expands/shrinks.
    * *It is collection of contiguous memory regions.
    *- Changes to pool create interface as a result of above change.
    *- Collect and export stats (/proc/tlsfinfo)
    *- Cleanups: kernel coding style, added comments, macros -> static inline, etc.

    Signed-off-by: Nitin Gupta
    ---

    include/linux/tlsf.h | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++
    1 files changed, 93 insertions(+), 0 deletions(-)

    diff --git a/include/linux/tlsf.h b/include/linux/tlsf.h
    new file mode 100644
    index 0000000..ef8092c
    --- /dev/null
    +++ b/include/linux/tlsf.h
    @@ -0,0 +1,93 @@
    +/*
    + * Two Levels Segregate Fit memory allocator (TLSF)
    + * Version 2.3.2
    + *
    + * Written by Miguel Masmano Tello
    + *
    + * Thanks to Ismael Ripoll for his suggestions and reviews
    + *
    + * Copyright (C) 2007, 2006, 2005, 2004
    + *
    + * This code is released using a dual license strategy: GPL/LGPL
    + * You can choose the licence that better fits your requirements.
    + *
    + * Released under the terms of the GNU General Public License Version 2.0
    + * Released under the terms of the GNU Lesser General Public License Version 2.1
    + *
    + * This is kernel port of TLSF allocator.
    + * Original code can be found at: http://rtportal.upv.es/rtmalloc/
    + * - Nitin Gupta (nitingupta910 at gmail dot com)
    + */
    +
    +#ifndef _TLSF_H_
    +#define _TLSF_H_
    +
    +typedef void* (get_memory)(size_t bytes);
    +typedef void (put_memory)(void *ptr);
    +
    +/**
    + * tlsf_create_memory_pool - create dynamic memory pool
    + * @name: name of the pool
    + * @get_mem: callback function used to expand pool
    + * @put_mem: callback function used to shrink pool
    + * @init_size: inital pool size (in bytes)
    + * @max_size: maximum pool size (in bytes) - set this as 0 for no limit
    + * @grow_size: amount of memory (in bytes) added to pool whenever required
    + *
    + * All size values are rounded up to next page boundary.
    + */
    +extern void *tlsf_create_memory_pool(const char *name,
    + get_memory get_mem,
    + put_memory put_mem,
    + size_t init_size,
    + size_t max_size,
    + size_t grow_size);
    +/**
    + * tlsf_destory_memory_pool - cleanup given pool
    + * @mem_pool: Pool to be destroyed
    + *
    + * Data structures associated with pool are freed.
    + * All memory allocated from pool must be freed before
    + * destorying it.
    + */
    +extern void tlsf_destroy_memory_pool(void *mem_pool);
    +
    +/**
    + * tlsf_malloc - allocate memory from given pool
    + * @size: no. of bytes
    + * @mem_pool: pool to allocate from
    + */
    +extern void *tlsf_malloc(size_t size, void *mem_pool);
    +
    +/**
    + * tlsf_calloc - allocate and zero-out memory from given pool
    + * @size: no. of bytes
    + * @mem_pool: pool to allocate from
    + */
    +extern void *tlsf_calloc(size_t nelem, size_t elem_size, void *mem_pool);
    +
    +/**
    + * tlsf_free - free memory from given pool
    + * @ptr: address of memory to be freed
    + * @mem_pool: pool to free from
    + */
    +extern void tlsf_free(void *ptr, void *mem_pool);
    +
    +/**
    + * tlsf_get_used_size - get memory currently used by given pool
    + *
    + * Used memory includes stored data + metadata + internal fragmentation
    + */
    +extern size_t tlsf_get_used_size(void *mem_pool);
    +
    +/**
    + * tlsf_get_total_size - get total memory currently allocated for given pool
    + *
    + * This is the total memory currently allocated for this pool which includes
    + * used size + free size.
    + *
    + * (Total - Used) is good indicator of memory efficiency of allocator.
    + */
    +extern size_t tlsf_get_total_size(void *mem_pool);
    +
    +#endif
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  2. Re: [PATCH 3/6] compcache: TLSF Allocator interface

    On Mon, 2008-03-24 at 20:34 +0530, Nitin Gupta wrote:
    > Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for
    > variable size compressed pages. Its fast and gives low fragmentation.
    > Following links give details on this allocator:
    > - http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf
    > - http://code.google.com/p/compcache/wiki/TLSFAllocator
    >
    > This kernel port of TLSF (v2.3.2) introduces several changes but underlying
    > algorithm remains the same.
    >
    > Changelog TLSF v2.3.2 vs this kernel port
    > - Pool now dynamically expands/shrinks.
    > It is collection of contiguous memory regions.
    > - Changes to pool create interface as a result of above change.
    > - Collect and export stats (/proc/tlsfinfo)
    > - Cleanups: kernel coding style, added comments, macros -> static inline, etc.


    Can you explain why you need this allocator, why don't the current
    kernel allocators work for you?




    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  3. Re: [PATCH 3/6] compcache: TLSF Allocator interface

    On Mon, Mar 24, 2008 at 10:26 PM, Peter Zijlstra wrote:
    > On Mon, 2008-03-24 at 20:34 +0530, Nitin Gupta wrote:
    > > Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for
    > > variable size compressed pages. Its fast and gives low fragmentation.
    > > Following links give details on this allocator:
    > > - http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf
    > > - http://code.google.com/p/compcache/wiki/TLSFAllocator
    > >
    > > This kernel port of TLSF (v2.3.2) introduces several changes but underlying
    > > algorithm remains the same.
    > >
    > > Changelog TLSF v2.3.2 vs this kernel port
    > > - Pool now dynamically expands/shrinks.
    > > It is collection of contiguous memory regions.
    > > - Changes to pool create interface as a result of above change.
    > > - Collect and export stats (/proc/tlsfinfo)
    > > - Cleanups: kernel coding style, added comments, macros -> static inline, etc.

    >
    > Can you explain why you need this allocator, why don't the current
    > kernel allocators work for you?
    >
    >


    kmalloc() allocates one of pre-defined sizes (as defined in
    kmalloc_sizes.h). This will surely cause severe fragmentation with
    these variable sized compressed pages.

    Whereas, TLSF maintains very fine grained size lists. In all the
    workloads I tested, it showed <5% fragmentation. Also, its very simple
    as just ~700 LOC.

    - Nitin
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  4. Re: [PATCH 3/6] compcache: TLSF Allocator interface

    On Mon, 2008-03-24 at 23:04 +0530, Nitin Gupta wrote:
    > On Mon, Mar 24, 2008 at 10:26 PM, Peter Zijlstra wrote:
    > > On Mon, 2008-03-24 at 20:34 +0530, Nitin Gupta wrote:
    > > > Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for
    > > > variable size compressed pages. Its fast and gives low fragmentation.
    > > > Following links give details on this allocator:
    > > > - http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf
    > > > - http://code.google.com/p/compcache/wiki/TLSFAllocator
    > > >
    > > > This kernel port of TLSF (v2.3.2) introduces several changes but underlying
    > > > algorithm remains the same.
    > > >
    > > > Changelog TLSF v2.3.2 vs this kernel port
    > > > - Pool now dynamically expands/shrinks.
    > > > It is collection of contiguous memory regions.
    > > > - Changes to pool create interface as a result of above change.
    > > > - Collect and export stats (/proc/tlsfinfo)
    > > > - Cleanups: kernel coding style, added comments, macros -> static inline, etc.

    > >
    > > Can you explain why you need this allocator, why don't the current
    > > kernel allocators work for you?
    > >
    > >

    >
    > kmalloc() allocates one of pre-defined sizes (as defined in
    > kmalloc_sizes.h). This will surely cause severe fragmentation with
    > these variable sized compressed pages.
    >
    > Whereas, TLSF maintains very fine grained size lists. In all the
    > workloads I tested, it showed <5% fragmentation. Also, its very simple
    > as just ~700 LOC.


    Yeah, it also suffers from a horrible coding style, can use excessive
    amounts of vmalloc space, isn't hooked into the reclaim process as an
    allocator should be and has a severe lack of per-cpu data making it a
    pretty big bottleneck on anything with more than a few cores.

    Now, it might be needed, might work better, and the scalability issue
    might not be a problem when used for swap, but still, you don't treat
    any of these points in your changelog.

    FWIW, please split up the patches in a sane way. This series looks like
    it wants to be 2 or 3 patches. The first introducing all of TLSF (this
    split per file is horrible). The second doing all of the block device,
    and a possible last doing documentation and such.

    Also, how bad was kmalloc() compared to this TLSF, we need numbers :-)

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  5. Re: [PATCH 3/6] compcache: TLSF Allocator interface

    On Tue, Mar 25, 2008 at 12:26 AM, Peter Zijlstra wrote:
    >
    > On Mon, 2008-03-24 at 23:04 +0530, Nitin Gupta wrote:
    > > On Mon, Mar 24, 2008 at 10:26 PM, Peter Zijlstra wrote:
    > > > On Mon, 2008-03-24 at 20:34 +0530, Nitin Gupta wrote:
    > > > > Two Level Segregate Fit (TLSF) Allocator is used to allocate memory for
    > > > > variable size compressed pages. Its fast and gives low fragmentation.
    > > > > Following links give details on this allocator:
    > > > > - http://rtportal.upv.es/rtmalloc/file...r_spe_2007.pdf
    > > > > - http://code.google.com/p/compcache/wiki/TLSFAllocator
    > > > >
    > > > > This kernel port of TLSF (v2.3.2) introduces several changes but underlying
    > > > > algorithm remains the same.
    > > > >
    > > > > Changelog TLSF v2.3.2 vs this kernel port
    > > > > - Pool now dynamically expands/shrinks.
    > > > > It is collection of contiguous memory regions.
    > > > > - Changes to pool create interface as a result of above change.
    > > > > - Collect and export stats (/proc/tlsfinfo)
    > > > > - Cleanups: kernel coding style, added comments, macros -> static inline, etc.
    > > >
    > > > Can you explain why you need this allocator, why don't the current
    > > > kernel allocators work for you?
    > > >
    > > >

    > >
    > > kmalloc() allocates one of pre-defined sizes (as defined in
    > > kmalloc_sizes.h). This will surely cause severe fragmentation with
    > > these variable sized compressed pages.
    > >
    > > Whereas, TLSF maintains very fine grained size lists. In all the
    > > workloads I tested, it showed <5% fragmentation. Also, its very simple
    > > as just ~700 LOC.

    >
    > Yeah, it also suffers from a horrible coding style, can use excessive
    > amounts of vmalloc space, isn't hooked into the reclaim process as an
    > allocator should be and has a severe lack of per-cpu data making it a
    > pretty big bottleneck on anything with more than a few cores.
    >
    > Now, it might be needed, might work better, and the scalability issue
    > might not be a problem when used for swap, but still, you don't treat
    > any of these points in your changelog.


    Currently, this TLSF implementation is not scalable at all (and thats
    why it depends on EMBEDDED).

    >
    > FWIW, please split up the patches in a sane way. This series looks like
    > it wants to be 2 or 3 patches. The first introducing all of TLSF (this
    > split per file is horrible). The second doing all of the block device,
    > and a possible last doing documentation and such.
    >
    > Also, how bad was kmalloc() compared to this TLSF, we need numbers :-)
    >
    >


    Ok, I will get them and present here.

    Thanks,
    Nitin
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  6. Re: [PATCH 3/6] compcache: TLSF Allocator interface

    On Tue, Mar 25, 2008 at 12:26 AM, Peter Zijlstra wrote:

    > Yeah, it also suffers from a horrible coding style, can use excessive
    > amounts of vmalloc space, isn't hooked into the reclaim process as an
    > allocator should be and has a severe lack of per-cpu data making it a
    > pretty big bottleneck on anything with more than a few cores.
    >
    > Now, it might be needed, might work better, and the scalability issue
    > might not be a problem when used for swap, but still, you don't treat
    > any of these points in your changelog.
    >



    I will add these points to changelog.
    This project is meant for small systems only. So, scalability is not an issue.


    > FWIW, please split up the patches in a sane way. This series looks like
    > it wants to be 2 or 3 patches. The first introducing all of TLSF (this
    > split per file is horrible). The second doing all of the block device,
    > and a possible last doing documentation and such.
    >


    Ok. I will resend with better splitting.


    > Also, how bad was kmalloc() compared to this TLSF, we need numbers :-)
    >
    >


    I have posted performance numbers at:
    http://code.google.com/p/compcache/w...torsComparison

    Data Summary:

    Peak Memory Usage:

    * Ideal: 24947 KB
    * TLSF: 25377 KB
    * KMalloc(SLUB): 36483 KB

    So, KMalloc uses ~43% more memory than TLSF!


    - Nitin
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

+ Reply to Thread