z3fold: the 3-fold allocator for compressed pages
Subsystems (2)
PATCH 1/1 z3fold: the 3-fold allocator for compressed pages
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per physical page. It is a ZBUD derivative which allows for higher compression ratio keeping the simplicity and determinism of its predecessor.
The main differences between z3fold and zbud are:
* unlike zbud, z3fold allows for up to PAGE_SIZE allocations
* z3fold can hold up to 3 compressed pages in its page
This patch comes as a follow-up to the discussions at the Embedded Linux Conference in San-Diego related to the talk [1]. The outcome of these discussions was that it would be good to have a compressed page allocator as stable and deterministic as zbud with with higher compression ratio. To keep the determinism and simplicity, z3fold, just like zbud, always stores an integral number of compressed pages per page, but it can store up to 3 pages unlike zbud which can store at most 2. Therefore the compression ratio goes to around 2.5x while zbud's one is around 1.7x.
The patch is based on the latest linux.git tree.
--- mm/Kconfig | 9 + mm/Makefile | 1 + mm/z3fold.c | 754 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 764 insertions(+) create mode 100644 mm/z3fold.c
mm/Kconfig +9 -0
@@ -565,6 +565,15 @@ config ZBUD deterministic reclaim properties that make it preferable to a higher density approach when reclaim will be used. +config Z3FOLD + tristate "Low density storage for compressed pages" + default n + help + A special purpose allocator for storing compressed pages. + It is designed to store up to three compressed pages per physical + page. It is a ZBUD derivative so the simplicity and determinism are + still there. + config ZSMALLOC tristate "Memory allocator for compressed pages" depends on MMU
mm/Makefile +1 -0
@@ -89,6 +89,7 @@ obj-$(CONFIG_MEMORY_ISOLATION) += page_isolation.o obj-$(CONFIG_ZPOOL) += zpool.o obj-$(CONFIG_ZBUD) += zbud.o obj-$(CONFIG_ZSMALLOC) += zsmalloc.o +obj-$(CONFIG_Z3FOLD) += z3fold.o obj-$(CONFIG_GENERIC_EARLY_IOREMAP) += early_ioremap.o obj-$(CONFIG_CMA) += cma.o obj-$(CONFIG_MEMORY_BALLOON) += balloon_compaction.o
mm/z3fold.c new file +754 -0
754 lines not on this page · raw message
Signature · 7 lines
2.5.0 -- 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>
Quoted 4 lines · Vitaly Wool
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per physical page. It is a ZBUD derivative which allows for higher compression ratio keeping the simplicity and determinism of its predecessor.
So the obvious question is, why a separate allocator and not extend zbud?
I didn't study the code, nor notice a design/algorithm overview doc, but it seems z3fold keeps the idea of one compressed page at the beginning, one at the end of page frame, but it adds another one in the middle? Also how is the buddy-matching done?
Thanks,
Vlastimil
--
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>
Quoted 10 lines · Vlastimil Babka
Quoted 5 lines · Vitaly Wool
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per physical page. It is a ZBUD derivative which allows for higher compression ratio keeping the simplicity and determinism of its predecessor.
So the obvious question is, why a separate allocator and not extend zbud?
Well, as far as I recall Seth was very much for keeping zbud as simple as possible. I am fine either way but if we have zpool API, why not have another zpool API user?
Quoted 5 lines
I didn't study the code, nor notice a design/algorithm overview doc, but it seems z3fold keeps the idea of one compressed page at the beginning, one at the end of page frame, but it adds another one in the middle? Also how is the buddy-matching done?
Basically yes. There is 'start_middle' variable which point to the start of the middle page, if any. The matching is done basing on the buddy number.
~vitaly
Quoted 14 lines · Vitaly Wool
Quoted 11 lines · Vlastimil Babka
Quoted 7 lines · Vitaly Wool
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per
physical page. It is a ZBUD derivative which allows for higher compression
ratio keeping the simplicity and determinism of its predecessor.
Quoted 12 lines
Quoted 1 line
So the obvious question is, why a separate allocator and not extend zbud?
Well, as far as I recall Seth was very much for keeping zbud as simple as possible. I am fine either way but if we have zpool API, why not have another zpool API user?
Quoted 5 lines
I didn't study the code, nor notice a design/algorithm overview doc, but it seems z3fold keeps the idea of one compressed page at the beginning, one at the end of page frame, but it adds another one in the middle? Also how is the buddy-matching done?
Yes, as soon as you introduce a 3rd object in the page, zpage fragmentation becomes an issue. Having a middle object partitions that zpage, blocking allocations that are larger than either partition, even though the combined size of the partitions could have accommodated the object.
This also means that the unbuddied list is broken in this implementation. num_free_chunks() is calculating the _total_ free space in the page. But that is not that the _usable_ free space by a single object, if the middle object has partitioned that free space.
Seth
Quoted 6 lines
Basically yes. There is '
start_middle' variable which point to the start of the middle page, if any. The matching is done basing on the buddy number.~vitaly
--
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>
Quoted 28 lines · Seth Jennings
Quoted 14 lines · Vitaly Wool
Quoted 11 lines · Vlastimil Babka
Quoted 7 lines · Vitaly Wool
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per
physical page. It is a ZBUD derivative which allows for higher compression
ratio keeping the simplicity and determinism of its predecessor.Quoted 12 lines
Quoted 1 line
So the obvious question is, why a separate allocator and not extend zbud?
Well, as far as I recall Seth was very much for keeping zbud as simple as possible. I am fine either way but if we have zpool API, why not have another zpool API user?
Quoted 5 lines
I didn't study the code, nor notice a design/algorithm overview doc, but it seems z3fold keeps the idea of one compressed page at the beginning, one at the end of page frame, but it adds another one in the middle? Also how is the buddy-matching done?
Quoted 5 lines
Yes, as soon as you introduce a 3rd object in the page, zpage fragmentation becomes an issue. Having a middle object partitions that zpage, blocking allocations that are larger than either partition, even though the combined size of the partitions could have accommodated the object.
Yes, but this situation is easy to track down and work around by moving the middle object to either the beginning or the end. In case of the current implementation it is the beginning.
Quoted 4 lines
This also means that the unbuddied list is broken in this implementation.
num_free_chunks()is calculating the _total_ free space in the page. But that is not that the _usable_ free space by a single object, if the middle object has partitioned that free space.
Once again, there is the code in z3fold_free() that makes sure the free space within the page is contiguous so I don't think the unbuddied list is, or will be, broken.
~vitaly
--
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>
Quoted 39 lines · Vitaly Wool
Quoted 28 lines · Seth Jennings
Quoted 14 lines · Vitaly Wool
Quoted 11 lines · Vlastimil Babka
Quoted 7 lines · Vitaly Wool
This patch introduces z3fold, a special purpose allocator for storing compressed pages. It is designed to store up to three compressed pages per
physical page. It is a ZBUD derivative which allows for higher compression
ratio keeping the simplicity and determinism of its predecessor.Quoted 12 lines
Quoted 1 line
So the obvious question is, why a separate allocator and not extend zbud?
Well, as far as I recall Seth was very much for keeping zbud as simple as possible. I am fine either way but if we have zpool API, why not have another zpool API user?
Quoted 5 lines
I didn't study the code, nor notice a design/algorithm overview doc, but it seems z3fold keeps the idea of one compressed page at the beginning, one at the end of page frame, but it adds another one in the middle? Also how is the buddy-matching done?
Quoted 5 lines
Yes, as soon as you introduce a 3rd object in the page, zpage fragmentation becomes an issue. Having a middle object partitions that zpage, blocking allocations that are larger than either partition, even though the combined size of the partitions could have accommodated the object.
Yes, but this situation is easy to track down and work around by moving the middle object to either the beginning or the end. In case of the current implementation it is the beginning.
Quoted 8 lines
Quoted 4 lines
This also means that the unbuddied list is broken in this implementation.
num_free_chunks()is calculating the _total_ free space in the page. But that is not that the _usable_ free space by a single object, if the middle object has partitioned that free space.Once again, there is the code in
z3fold_free()that makes sure the free space within the page is contiguous so I don't think the unbuddied list is, or will be, broken.
Didn't see the relocation before. However, that brings up another question. How is the code moving objects when the location of that object is encoded in the handle that has already been given to the user?
Seth
Quoted 2 lines
~vitaly
Quoted 1 line
Quoted 1 line · Seth Jennings
<snip>
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
This also means that the unbuddied list is broken in this implementation.
num_free_chunks()is calculating the _total_ free space in the page. But that is not that the _usable_ free space by a single object, if the middle object has partitioned that free space.
Quoted 8 lines
Quoted 3 lines
Once again, there is the code in
z3fold_free()that makes sure the free space within the page is contiguous so I don't think the unbuddied list is, or will be, broken.Didn't see the relocation before. However, that brings up another question. How is the code moving objects when the location of that object is encoded in the handle that has already been given to the user?
Relocation is only necessary when there is one remaining object and it is in the middle. In that case the 'first_num' variable is incremented so its handle already given to user will be resolved as the first object and not the middle.
~vitaly
--
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>