| Message ID | 20221121190020.66548-1-avromanov@sberdevices.ru (mailing list archive) |
|---|---|
| Headers | show |
| Series | Introduce merge identical pages mechanism | expand |
On Mon, Nov 21, 2022 at 10:00:16PM +0300, Alexey Romanov wrote: > Hello! > > This RFC series adds feature which allows merge identical > compressed pages into a single one. The main idea is that > zram only stores object references, which store the compressed > content of the pages. Thus, the contents of the zsmalloc objects > don't change in any way. > > For simplicity, let's imagine that 3 pages with the same content > got into zram: > > +----------------+ +----------------+ +----------------+ > |zram_table_entry| |zram_table_entry| |zram_table_entry| > +-------+--------+ +-------+--------+ +--------+-------+ > | | | > | handle (1) | handle (2) | handle (3) > +-------v--------+ +-------v---------+ +--------v-------+ > |zsmalloc object| |zsmalloc object | |zsmalloc object| > ++--------------++ +-+-------------+-+ ++--------------++ > +--------------+ +-------------+ +--------------+ > | buffer: "abc"| |buffer: "abc"| | buffer: "abc"| > +--------------+ +-------------+ +--------------+ > > As you can see, the data is duplicated. Merge mechanism saves > (after scanning objects) only one zsmalloc object. Here's > what happens ater the scan and merge: > > +----------------+ +----------------+ +----------------+ > |zram_table_entry| |zram_table_entry| |zram_tabl _entry| > +-------+--------+ +-------+--------+ +--------+-------+ > | | | > | handle (1) | handle (1) | handle (1) > | +--------v---------+ | > +-----------> zsmalloc object <-----------+ > +--+-------------+-+ > +-------------+ > |buffer: "abc"| > +-------------+ > > Thus, we reduced the amount of memory occupied by 3 times. > > This mechanism doesn't affect the perf of the zram itself in > any way (maybe just a little bit on the zram_free_page function). > In order to describe each such identical object, we (constantly) > need sizeof(zram_rbtree_node) bytes. So, for example, if the system > has 20 identical buffers with a size of 1024, the memory gain will be > (20 * 1024) - (1 * 1024 + sizeof(zram_rbtree_node)) = 19456 - > sizeof(zram_rbtree_node) bytes. But, it should be understood, these are > counts without zsmalloc data structures overhead. > > Testing on my system (8GB ram + 1 gb zram swap) showed that at high > loads, on average, when calling the merge mechanism, we can save > up to 15-20% of the memory usage. This looks pretty great. However, I'm curious why it's specific to zram, and not part of zsmalloc? That way zswap would benefit as well, without having to duplicate the implementation. This happened for example with page_same_filled() and zswap_is_page_same_filled(). It's zsmalloc's job to store content efficiently, so couldn't this feature (just like the page_same_filled one) be an optimization that zsmalloc does transparently for all its users? > This patch serices adds a new sysfs node (trigger merging) and new > field in mm_stat (how many pages are merged in zram at the moment): > > $ cat /sys/block/zram/mm_stat > 431452160 332984392 339894272 0 339894272 282 0 51374 51374 0 > > $ echo 1 > /sys/block/zram/merge > > $ cat /sys/block/zram/mm_stat > 431452160 270376848 287301504 0 339894272 282 0 51374 51374 6593 The optimal frequency for calling this is probably tied to prevalent memory pressure, which is somewhat tricky to do from userspace. Would it make sense to hook this up to a shrinker?
On (22/11/21 15:44), Johannes Weiner wrote: > This looks pretty great. > > However, I'm curious why it's specific to zram, and not part of > zsmalloc? That way zswap would benefit as well, without having to > duplicate the implementation. This happened for example with > page_same_filled() and zswap_is_page_same_filled(). > > It's zsmalloc's job to store content efficiently, so couldn't this > feature (just like the page_same_filled one) be an optimization that > zsmalloc does transparently for all its users? Yea, that's a much needed functionality, but things may be "complicated". We had that KSM-ish thing in the past in zram. Very briefly as we quickly found out that the idea was patented by some company in China and we couldn't figure our if it was safe to land that code upstream. So we ended up dropping the patches. https://lore.kernel.org/lkml/1494556204-25796-1-git-send-email-iamjoonsoo.kim@lge.com/ > Would it make sense to hook this up to a shrinker? Hmm, ratelimited perhaps. We most likely don't want to scan the whole pool every time a shrinker calls us (which can be quite often).
On (22/11/22 12:00), Sergey Senozhatsky wrote: > On (22/11/21 15:44), Johannes Weiner wrote: > > This looks pretty great. > > > > However, I'm curious why it's specific to zram, and not part of > > zsmalloc? That way zswap would benefit as well, without having to > > duplicate the implementation. This happened for example with > > page_same_filled() and zswap_is_page_same_filled(). > > > > It's zsmalloc's job to store content efficiently, so couldn't this > > feature (just like the page_same_filled one) be an optimization that > > zsmalloc does transparently for all its users? > > Yea, that's a much needed functionality, but things may be "complicated". > We had that KSM-ish thing in the past in zram. Very briefly as we quickly > found out that the idea was patented by some company in China and we couldn't > figure our if it was safe to land that code upstream. So we ended up dropping > the patches. > > https://lore.kernel.org/lkml/1494556204-25796-1-git-send-email-iamjoonsoo.kim@lge.com/ IIRC that was patent in question: https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf
Hello! On Tue, Nov 22, 2022 at 12:07:42PM +0900, Sergey Senozhatsky wrote: > On (22/11/22 12:00), Sergey Senozhatsky wrote: > > On (22/11/21 15:44), Johannes Weiner wrote: > > > This looks pretty great. > > > > > > However, I'm curious why it's specific to zram, and not part of > > > zsmalloc? That way zswap would benefit as well, without having to > > > duplicate the implementation. This happened for example with > > > page_same_filled() and zswap_is_page_same_filled(). > > > > > > It's zsmalloc's job to store content efficiently, so couldn't this > > > feature (just like the page_same_filled one) be an optimization that > > > zsmalloc does transparently for all its users? > > > > Yea, that's a much needed functionality, but things may be "complicated". > > We had that KSM-ish thing in the past in zram. Very briefly as we quickly > > found out that the idea was patented by some company in China and we couldn't > > figure our if it was safe to land that code upstream. So we ended up dropping > > the patches. > > > > https://lore.kernel.org/lkml/1494556204-25796-1-git-send-email-iamjoonsoo.kim@lge.com/ > > IIRC that was patent in question: > > https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf I think the patent is talking about "mapping the virtual address" (like in KSM). But zram works with the "handle" abstraction, which is a boxed pointer to the required object. I think my implementation and the patent is slightly different. Also, the patent speaks of "compressing" pages. In this case, we can add zs_merge() function (like zs_compact()), that is, remove the merge logic at the allocator level. zsmalloc doesn't say anything about what objects it can work with. Implementation at the zsmalloc level is possible, though more complicated that at the zram level. I believe that we can implement at least one of the options I proposed. What do you think?
On (22/11/22 12:14), Aleksey Romanov wrote: > > IIRC that was patent in question: > > > > https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf > > I think the patent is talking about "mapping the virtual address" (like > in KSM). But zram works with the "handle" abstraction, which is a boxed > pointer to the required object. I think my implementation and the patent > is slightly different. > > Also, the patent speaks of "compressing" pages. In this case, we can add > zs_merge() function (like zs_compact()), that is, remove the merge logic > at the allocator level. zsmalloc doesn't say anything about what objects > it can work with. Implementation at the zsmalloc level is possible, > though more complicated that at the zram level. > > I believe that we can implement at least one of the options I proposed. > > What do you think? Oh, yeah, I'm not saying that we cannot have something like that in zram/zsmalloc, just wanted to give some historical retrospective on this and point at some implementation details that should be considered.
Hello Sergey, Thank you for your quick and detailed support! Here is my two cents below. On Wed, Nov 23, 2022 at 01:13:55PM +0900, Sergey Senozhatsky wrote: > On (22/11/22 12:14), Aleksey Romanov wrote: > > > IIRC that was patent in question: > > > > > > https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf > > > > I think the patent is talking about "mapping the virtual address" (like > > in KSM). But zram works with the "handle" abstraction, which is a boxed > > pointer to the required object. I think my implementation and the patent > > is slightly different. > > > > Also, the patent speaks of "compressing" pages. In this case, we can add > > zs_merge() function (like zs_compact()), that is, remove the merge logic > > at the allocator level. zsmalloc doesn't say anything about what objects > > it can work with. Implementation at the zsmalloc level is possible, > > though more complicated that at the zram level. > > > > I believe that we can implement at least one of the options I proposed. > > > > What do you think? > > Oh, yeah, I'm not saying that we cannot have something like that > in zram/zsmalloc, just wanted to give some historical retrospective > on this and point at some implementation details that should be > considered. It's a very curious situation, I would say. I'm not so familiar with US patent law, but I suppose it should be based on some keywords and algorithms. If we speak in terms of algorithm Alexey patch is different a little bit from suggested in the patent paper. If we care about keywords, I think by moving Alexey same page merging algorithm to zsmalloc we lose "compressing" keyword, because zsmalloc operates with "objects" only, doesn't matter if they are compressed or not. Anyway, could you please suggest who can help to understand if it's safe to use such same page merging algorithm in the upstream or not? Maybe we can ask Linux Foundation lawyers to help us, just a guess. I'm sure we shouldn't decline helpful features and optimization without complete certainty about all restrictions.
On Wed, Nov 23, 2022 at 01:13:55PM +0900, Sergey Senozhatsky wrote: > On (22/11/22 12:14), Aleksey Romanov wrote: > > > IIRC that was patent in question: > > > > > > https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf > > > > I think the patent is talking about "mapping the virtual address" (like > > in KSM). But zram works with the "handle" abstraction, which is a boxed > > pointer to the required object. I think my implementation and the patent > > is slightly different. > > > > Also, the patent speaks of "compressing" pages. In this case, we can add > > zs_merge() function (like zs_compact()), that is, remove the merge logic > > at the allocator level. zsmalloc doesn't say anything about what objects > > it can work with. Implementation at the zsmalloc level is possible, > > though more complicated that at the zram level. > > > > I believe that we can implement at least one of the options I proposed. > > > > What do you think? > > Oh, yeah, I'm not saying that we cannot have something like that > in zram/zsmalloc, just wanted to give some historical retrospective > on this and point at some implementation details that should be > considered. Okay, in this case, can you review my patches please?
Hello Sergey, Hope you are doing well. Really sorry for the ping. Did you get a chance to see the patch series, my questions, and thoughts? On Wed, Nov 23, 2022 at 11:53:06AM +0300, Dmitry Rokosov wrote: > Hello Sergey, > > Thank you for your quick and detailed support! Here is my two cents > below. > > On Wed, Nov 23, 2022 at 01:13:55PM +0900, Sergey Senozhatsky wrote: > > On (22/11/22 12:14), Aleksey Romanov wrote: > > > > IIRC that was patent in question: > > > > > > > > https://patentimages.storage.googleapis.com/e2/66/9e/0ddbfae5c182ac/US9977598.pdf > > > > > > I think the patent is talking about "mapping the virtual address" (like > > > in KSM). But zram works with the "handle" abstraction, which is a boxed > > > pointer to the required object. I think my implementation and the patent > > > is slightly different. > > > > > > Also, the patent speaks of "compressing" pages. In this case, we can add > > > zs_merge() function (like zs_compact()), that is, remove the merge logic > > > at the allocator level. zsmalloc doesn't say anything about what objects > > > it can work with. Implementation at the zsmalloc level is possible, > > > though more complicated that at the zram level. > > > > > > I believe that we can implement at least one of the options I proposed. > > > > > > What do you think? > > > > Oh, yeah, I'm not saying that we cannot have something like that > > in zram/zsmalloc, just wanted to give some historical retrospective > > on this and point at some implementation details that should be > > considered. > > It's a very curious situation, I would say. I'm not so familiar with US > patent law, but I suppose it should be based on some keywords and > algorithms. > > If we speak in terms of algorithm Alexey patch is different a little bit > from suggested in the patent paper. If we care about keywords, I think by > moving Alexey same page merging algorithm to zsmalloc we lose > "compressing" keyword, because zsmalloc operates with "objects" only, > doesn't matter if they are compressed or not. > > Anyway, could you please suggest who can help to understand if it's safe > to use such same page merging algorithm in the upstream or not? > Maybe we can ask Linux Foundation lawyers to help us, just a guess. > I'm sure we shouldn't decline helpful features and optimization without > complete certainty about all restrictions.
On (22/12/01 13:14), Dmitry Rokosov wrote: > Hello Sergey, > > Hope you are doing well. Really sorry for the ping. > > Did you get a chance to see the patch series, my questions, and > thoughts? Hey, Not really, sorry. It's a holidays season + pre-merge window week. I probably will start looking attentively next week or so. In the meantime time I'll try to reach out to lawyers to get more clarifications on that patent thingy.
On Thu, Dec 01, 2022 at 07:47:21PM +0900, Sergey Senozhatsky wrote: > On (22/12/01 13:14), Dmitry Rokosov wrote: > > Hello Sergey, > > > > Hope you are doing well. Really sorry for the ping. > > > > Did you get a chance to see the patch series, my questions, and > > thoughts? > > Hey, > > Not really, sorry. It's a holidays season + pre-merge window week. > I probably will start looking attentively next week or so. > > In the meantime time I'll try to reach out to lawyers to get more > clarifications on that patent thingy. Yeah, got it. Thanks a lot for the support! Appreciate it! BTW, happy holidays :)
On (22/12/01 14:14), Dmitry Rokosov wrote: > > BTW, happy holidays :) Happy holidays!
Hello Sergey! On Thu, Dec 01, 2022 at 07:47:21PM +0900, Sergey Senozhatsky wrote: > On (22/12/01 13:14), Dmitry Rokosov wrote: > > Hello Sergey, > > > > Hope you are doing well. Really sorry for the ping. > > > > Did you get a chance to see the patch series, my questions, and > > thoughts? > > Hey, > > Not really, sorry. It's a holidays season + pre-merge window week. > I probably will start looking attentively next week or so. > > In the meantime time I'll try to reach out to lawyers to get more > clarifications on that patent thingy. Is there any news about the patent, lawyers and my patchset?
Hi, On Wed, Jan 11, 2023 at 11:00 PM Alexey Romanov <AVRomanov@sberdevices.ru> wrote: > > Is there any news about the patent, lawyers and my patchset? I'll get back to you once I have any updates.
Hello! This RFC series adds feature which allows merge identical compressed pages into a single one. The main idea is that zram only stores object references, which store the compressed content of the pages. Thus, the contents of the zsmalloc objects don't change in any way. For simplicity, let's imagine that 3 pages with the same content got into zram: +----------------+ +----------------+ +----------------+ |zram_table_entry| |zram_table_entry| |zram_table_entry| +-------+--------+ +-------+--------+ +--------+-------+ | | | | handle (1) | handle (2) | handle (3) +-------v--------+ +-------v---------+ +--------v-------+ |zsmalloc object| |zsmalloc object | |zsmalloc object| ++--------------++ +-+-------------+-+ ++--------------++ +--------------+ +-------------+ +--------------+ | buffer: "abc"| |buffer: "abc"| | buffer: "abc"| +--------------+ +-------------+ +--------------+ As you can see, the data is duplicated. Merge mechanism saves (after scanning objects) only one zsmalloc object. Here's what happens ater the scan and merge: +----------------+ +----------------+ +----------------+ |zram_table_entry| |zram_table_entry| |zram_tabl _entry| +-------+--------+ +-------+--------+ +--------+-------+ | | | | handle (1) | handle (1) | handle (1) | +--------v---------+ | +-----------> zsmalloc object <-----------+ +--+-------------+-+ +-------------+ |buffer: "abc"| +-------------+ Thus, we reduced the amount of memory occupied by 3 times. This mechanism doesn't affect the perf of the zram itself in any way (maybe just a little bit on the zram_free_page function). In order to describe each such identical object, we (constantly) need sizeof(zram_rbtree_node) bytes. So, for example, if the system has 20 identical buffers with a size of 1024, the memory gain will be (20 * 1024) - (1 * 1024 + sizeof(zram_rbtree_node)) = 19456 - sizeof(zram_rbtree_node) bytes. But, it should be understood, these are counts without zsmalloc data structures overhead. Testing on my system (8GB ram + 1 gb zram swap) showed that at high loads, on average, when calling the merge mechanism, we can save up to 15-20% of the memory usage. This patch serices adds a new sysfs node (trigger merging) and new field in mm_stat (how many pages are merged in zram at the moment): $ cat /sys/block/zram/mm_stat 431452160 332984392 339894272 0 339894272 282 0 51374 51374 0 $ echo 1 > /sys/block/zram/merge $ cat /sys/block/zram/mm_stat 431452160 270376848 287301504 0 339894272 282 0 51374 51374 6593 Alexey Romanov (4): zram: introduce merge identical pages mechanism zram: add merge sysfs knob zram: add pages_merged counter to mm_stat zram: recompression: add ZRAM_MERGED check Documentation/admin-guide/blockdev/zram.rst | 2 + drivers/block/zram/zram_drv.c | 315 +++++++++++++++++++- drivers/block/zram/zram_drv.h | 7 + 3 files changed, 320 insertions(+), 4 deletions(-)