compcache: TLSF Allocator interface

PATCH In review Nitin Gupta 2 participants 6 messages Mar 24, 2008 – Apr 3, 2008 Memory management

Share & tools

Nitin Gupta

author

2008-03-24 15:09 UTC #0 lore raw

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/files/tlsf_paper_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 <nitingupta910 at gmail dot com>

---

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

include/linux/tlsf.h new file +93 -0

new file mode 100644
index 0000000..ef8092c
@@ -0,0 +1,93 @@
+/*
+ * Two Levels Segregate Fit memory allocator (TLSF)
+ * Version 2.3.2
+ *
+ * Written by Miguel Masmano Tello <[email protected]>
+ *
+ * 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, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Peter Zijlstra

2008-03-24 16:56 UTC #1 lore raw

Quoted 9 lines · Nitin Gupta

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/files/tlsf_paper_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.

Quoted 6 lines

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?

Nitin Gupta

author

2008-03-24 17:34 UTC #2 lore raw

Quoted 17 lines · Peter Zijlstra

Quoted 9 lines · Nitin Gupta
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/files/tlsf_paper_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.
Quoted 6 lines
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.

Quoted 4 lines

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

Peter Zijlstra

2008-03-24 18:56 UTC #3 lore raw

Quoted 23 lines · Nitin Gupta

Quoted 17 lines · Peter Zijlstra
Quoted 9 lines · Nitin Gupta
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/files/tlsf_paper_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.
Quoted 6 lines
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.
Quoted 4 lines
Can you explain why you need this allocator, why don't the current kernel allocators work for you?

Quoted 7 lines

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 :-)

Nitin Gupta

author

2008-03-24 19:10 UTC #4 lore raw

Quoted 33 lines · Peter Zijlstra

Quoted 23 lines · Nitin Gupta
Quoted 17 lines · Peter Zijlstra
Quoted 9 lines · Nitin Gupta
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/files/tlsf_paper_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.
Quoted 6 lines
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.
Quoted 4 lines
Can you explain why you need this allocator, why don't the current kernel allocators work for you?
Quoted 7 lines
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.

Quoted 8 lines

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).

Quoted 9 lines

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

Nitin Gupta

author

2008-04-03 17:23 UTC #5 lore raw

In reply to Peter Zijlstra

Quoted 9 lines · Peter Zijlstra

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.

Quoted 5 lines

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.

Quoted 3 lines

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

I have posted performance numbers at:
http://code.google.com/p/compcache/wiki/AllocatorsComparison

Data Summary:

Peak Memory Usage:

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

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

- Nitin