| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20240906050501.2494686-3-senozhatsky@chromium.org>
Date: Fri, 6 Sep 2024 14:04:46 +0900
From: Sergey Senozhatsky <senozhatsky@...omium.org>
To: Minchan Kim <minchan@...nel.org>
Cc: Andrew Morton <akpm@...ux-foundation.org>,
Richard Chang <richardycc@...gle.com>,
linux-kernel@...r.kernel.org,
Sergey Senozhatsky <senozhatsky@...omium.org>
Subject: [PATCHv1 2/3] zram: rework recompress target selection strategy
Target slot selection for recompression is just a simple
iteration over zram->table entries (stored pages) from
slot 0 to max slot. Given that zram->table slots are
written in random order and are not sorted by size, a
simple iteration over slots selects suboptimal targets
for recompression. This is not a problem if we recompress
every single zram->table slot, but we never do that in
reality. In reality we limit the number of slots we
can recompress (via max_pages parameter) and hence proper
slot selection becomes very important. The strategy is
quite simple, suppose we have two candidate slots for
recompression, one of size 48 bytes and one of size 2800
bytes, and we can recompress only one, then it certainly
makes more sense to pick 2800 entry for recompression.
Because even if we manage to compress 48 bytes objects
even further the savings are going to be very small.
Potential savings after good re-compression of 2800 bytes
objects are much higher.
This patch reworks slot selection and introduces the
strategy described above: among candidate slots always
select the biggest ones first.
For that the patch introduces zram_pp_ctl (post-processing)
structure which holds 16 pp buckets of slots. Slots are
assigned to a particular group based on their sizes - the
larger the size of the slot the higher the group index.
This, basically, sorts slots by size in liner time (we still
perform just one iteration over zram->table slots). When
we select slot for recompression we always first lookup in
higher pp buckets (those that hold the largest slots).
Which achieves the desired behavior.
TEST
====
A very simple demonstration: zram is configured with zstd, and
zstd with dict as a recompression stream. A limited (max 4096
pages) recompression is performed then, with a log of sizes of
slots that were recompressed. You can see that patched zram
selects slots for recompression in significantly different
manner, which leads to higher memory savings (see column #2 of
mm_stat output).
BASE
----
*** initial state of zram device
/sys/block/zram0/mm_stat
1750994944 504491413 514203648 0 514203648 1 0 34204 34204
*** recompress idle max_pages=4096
/sys/block/zram0/mm_stat
1750994944 504262229 514953216 0 514203648 1 0 34204 34204
Sizes of selected objects for recompression:
... 45 58 24 226 91 40 24 24 24 424 2104 93 2078 2078 2078 959 154 ...
PATCHED
-------
*** initial state of zram device
/sys/block/zram0/mm_stat
1750982656 504492801 514170880 0 514170880 1 0 34204 34204
*** recompress idle max_pages=4096
/sys/block/zram0/mm_stat
1750982656 503716710 517586944 0 514170880 1 0 34204 34204
Sizes of selected objects for recompression:
... 2826 2861 2829 2989 2713 2583 2698 2685 2748 2617 ...
Signed-off-by: Sergey Senozhatsky <senozhatsky@...omium.org>
---
drivers/block/zram/zram_drv.c | 194 +++++++++++++++++++++++++++++-----
1 file changed, 166 insertions(+), 28 deletions(-)
diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
index c91fdf399d1b..ebc3381fb2ac 100644
--- a/drivers/block/zram/zram_drv.c
+++ b/drivers/block/zram/zram_drv.c
@@ -659,8 +659,9 @@ static ssize_t writeback_store(struct device *dev,
goto next;
if (zram_test_flag(zram, index, ZRAM_WB) ||
- zram_test_flag(zram, index, ZRAM_SAME) ||
- zram_test_flag(zram, index, ZRAM_UNDER_WB))
+ zram_test_flag(zram, index, ZRAM_SAME) ||
+ zram_test_flag(zram, index, ZRAM_UNDER_WB) ||
+ zram_test_flag(zram, index, ZRAM_PP_SLOT))
goto next;
if (mode & IDLE_WRITEBACK &&
@@ -1648,6 +1649,126 @@ static int zram_bvec_write(struct zram *zram, struct bio_vec *bvec,
}
#ifdef CONFIG_ZRAM_MULTI_COMP
+struct zram_pp_slot {
+ unsigned long index;
+ struct list_head entry;
+};
+
+#define NUM_PP_BUCKETS 17
+
+struct zram_pp_ctl {
+ struct list_head pp_buckets[NUM_PP_BUCKETS];
+};
+
+static struct zram_pp_ctl *init_pp_ctl(void)
+{
+ struct zram_pp_ctl *ctl;
+ u32 idx;
+
+ ctl = kmalloc(sizeof(*ctl), GFP_KERNEL);
+ if (!ctl)
+ return NULL;
+
+ for (idx = 0; idx < NUM_PP_BUCKETS; idx++)
+ INIT_LIST_HEAD(&ctl->pp_buckets[idx]);
+ return ctl;
+}
+
+static void release_pp_slot(struct zram *zram, struct zram_pp_slot *pps)
+{
+ zram_slot_lock(zram, pps->index);
+ if (zram_test_flag(zram, pps->index, ZRAM_PP_SLOT))
+ zram_clear_flag(zram, pps->index, ZRAM_PP_SLOT);
+ zram_slot_unlock(zram, pps->index);
+ kfree(pps);
+}
+
+static void release_pp_ctl(struct zram *zram, struct zram_pp_ctl *ctl)
+{
+ u32 idx;
+
+ if (!ctl)
+ return;
+
+ for (idx = 0; idx < NUM_PP_BUCKETS; idx++) {
+ while (!list_empty(&ctl->pp_buckets[idx])) {
+ struct zram_pp_slot *pps;
+
+ pps = list_first_entry(&ctl->pp_buckets[idx],
+ struct zram_pp_slot,
+ entry);
+ list_del_init(&pps->entry);
+ release_pp_slot(zram, pps);
+ }
+ }
+
+ kfree(ctl);
+}
+
+static void place_pp_slot(struct zram *zram, struct zram_pp_ctl *ctl,
+ struct zram_pp_slot *pps)
+{
+ s32 diff, idx;
+
+ /*
+ * On 4K system this keeps PP slot groups 256 bytes apart. The
+ * higher the group IDX the larger the slot size.
+ */
+ diff = PAGE_SIZE / (NUM_PP_BUCKETS - 1);
+ idx = zram_get_obj_size(zram, pps->index) / diff;
+ list_add(&pps->entry, &ctl->pp_buckets[idx]);
+
+ zram_set_flag(zram, pps->index, ZRAM_PP_SLOT);
+}
+
+#define RECOMPRESS_IDLE (1 << 0)
+#define RECOMPRESS_HUGE (1 << 1)
+
+static int scan_slots_for_recompress(struct zram *zram, u32 mode,
+ struct zram_pp_ctl *ctl)
+{
+ unsigned long nr_pages = zram->disksize >> PAGE_SHIFT;
+ struct zram_pp_slot *pps = NULL;
+ unsigned long index;
+
+ for (index = 0; index < nr_pages; index++) {
+ if (!pps)
+ pps = kmalloc(sizeof(*pps), GFP_KERNEL);
+ if (!pps)
+ return -ENOMEM;
+
+ INIT_LIST_HEAD(&pps->entry);
+
+ zram_slot_lock(zram, index);
+ if (!zram_allocated(zram, index))
+ goto next;
+
+ if (mode & RECOMPRESS_IDLE &&
+ !zram_test_flag(zram, index, ZRAM_IDLE))
+ goto next;
+
+ if (mode & RECOMPRESS_HUGE &&
+ !zram_test_flag(zram, index, ZRAM_HUGE))
+ goto next;
+
+ if (zram_test_flag(zram, index, ZRAM_WB) ||
+ zram_test_flag(zram, index, ZRAM_UNDER_WB) ||
+ zram_test_flag(zram, index, ZRAM_PP_SLOT) ||
+ zram_test_flag(zram, index, ZRAM_SAME) ||
+ zram_test_flag(zram, index, ZRAM_INCOMPRESSIBLE))
+ goto next;
+
+ pps->index = index;
+ place_pp_slot(zram, ctl, pps);
+ pps = NULL;
+next:
+ zram_slot_unlock(zram, index);
+ }
+
+ kfree(pps);
+ return 0;
+}
+
/*
* This function will decompress (unless it's ZRAM_HUGE) the page and then
* attempt to compress it using provided compression algorithm priority
@@ -1655,7 +1776,7 @@ static int zram_bvec_write(struct zram *zram, struct bio_vec *bvec,
*
* Corresponding ZRAM slot should be locked.
*/
-static int zram_recompress(struct zram *zram, u32 index, struct page *page,
+static int recompress_slot(struct zram *zram, u32 index, struct page *page,
u64 *num_recomp_pages, u32 threshold, u32 prio,
u32 prio_max)
{
@@ -1675,6 +1796,7 @@ static int zram_recompress(struct zram *zram, u32 index, struct page *page,
return -EINVAL;
comp_len_old = zram_get_obj_size(zram, index);
+
/*
* Do not recompress objects that are already "small enough".
*/
@@ -1798,8 +1920,28 @@ static int zram_recompress(struct zram *zram, u32 index, struct page *page,
return 0;
}
-#define RECOMPRESS_IDLE (1 << 0)
-#define RECOMPRESS_HUGE (1 << 1)
+static struct zram_pp_slot *select_pp_slot(struct zram_pp_ctl *ctl)
+{
+ struct zram_pp_slot *pps = NULL;
+ s32 idx = NUM_PP_BUCKETS - 1;
+
+ /*
+ * Select PP-slots starting from the highest group, which should
+ * give us the best candidate for recompression.
+ */
+ while (idx > 0) {
+ pps = list_first_entry_or_null(&ctl->pp_buckets[idx],
+ struct zram_pp_slot,
+ entry);
+ if (pps) {
+ list_del_init(&pps->entry);
+ break;
+ }
+
+ idx--;
+ }
+ return pps;
+}
static ssize_t recompress_store(struct device *dev,
struct device_attribute *attr,
@@ -1807,11 +1949,11 @@ static ssize_t recompress_store(struct device *dev,
{
u32 prio = ZRAM_SECONDARY_COMP, prio_max = ZRAM_MAX_COMPS;
struct zram *zram = dev_to_zram(dev);
- unsigned long nr_pages = zram->disksize >> PAGE_SHIFT;
char *args, *param, *val, *algo = NULL;
u64 num_recomp_pages = ULLONG_MAX;
+ struct zram_pp_ctl *ctl = NULL;
+ struct zram_pp_slot *pps;
u32 mode = 0, threshold = 0;
- unsigned long index;
struct page *page;
ssize_t ret;
@@ -1907,36 +2049,31 @@ static ssize_t recompress_store(struct device *dev,
goto release_init_lock;
}
+ ctl = init_pp_ctl();
+ if (!ctl) {
+ ret = -ENOMEM;
+ goto release_init_lock;
+ }
+ scan_slots_for_recompress(zram, mode, ctl);
+
ret = len;
- for (index = 0; index < nr_pages; index++) {
+ while ((pps = select_pp_slot(ctl))) {
int err = 0;
if (!num_recomp_pages)
break;
- zram_slot_lock(zram, index);
-
- if (!zram_allocated(zram, index))
- goto next;
-
- if (mode & RECOMPRESS_IDLE &&
- !zram_test_flag(zram, index, ZRAM_IDLE))
- goto next;
-
- if (mode & RECOMPRESS_HUGE &&
- !zram_test_flag(zram, index, ZRAM_HUGE))
+ zram_slot_lock(zram, pps->index);
+ if (!zram_test_flag(zram, pps->index, ZRAM_PP_SLOT))
goto next;
- if (zram_test_flag(zram, index, ZRAM_WB) ||
- zram_test_flag(zram, index, ZRAM_UNDER_WB) ||
- zram_test_flag(zram, index, ZRAM_SAME) ||
- zram_test_flag(zram, index, ZRAM_INCOMPRESSIBLE))
- goto next;
-
- err = zram_recompress(zram, index, page, &num_recomp_pages,
- threshold, prio, prio_max);
+ err = recompress_slot(zram, pps->index, page,
+ &num_recomp_pages, threshold,
+ prio, prio_max);
next:
- zram_slot_unlock(zram, index);
+ zram_slot_unlock(zram, pps->index);
+ release_pp_slot(zram, pps);
+
if (err) {
ret = err;
break;
@@ -1948,6 +2085,7 @@ static ssize_t recompress_store(struct device *dev,
__free_page(page);
release_init_lock:
+ release_pp_ctl(zram, ctl);
up_read(&zram->init_lock);
return ret;
}
--
2.46.0.469.g59c65b2a67-goog
Powered by blists - more mailing lists