* [PATCH v3 1/2] mm: swap: swap cluster switch to double link list
2024-06-19 9:20 [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Chris Li
@ 2024-06-19 9:20 ` Chris Li
2024-06-21 2:59 ` Huang, Ying
2024-06-19 9:20 ` [PATCH v3 2/2] mm: swap: mTHP allocate swap entries from nonfull list Chris Li
` (3 subsequent siblings)
4 siblings, 1 reply; 16+ messages in thread
From: Chris Li @ 2024-06-19 9:20 UTC (permalink / raw)
To: Andrew Morton
Cc: Kairui Song, Ryan Roberts, Huang, Ying, Kairui Song,
Kalesh Singh, linux-kernel, linux-mm, Chris Li, Barry Song
Previously, the swap cluster used a cluster index as a pointer
to construct a custom single link list type "swap_cluster_list".
The next cluster pointer is shared with the cluster->count.
It prevents puting the non free cluster into a list.
Change the cluster to use the standard double link list instead.
This allows tracing the nonfull cluster in the follow up patch.
That way, it is faster to get to the nonfull cluster of that order.
Remove the cluster getter/setter for accessing the cluster
struct member.
The list operation is protected by the swap_info_struct->lock.
Change cluster code to use "struct swap_cluster_info *" to
reference the cluster rather than by using index. That is more
consistent with the list manipulation. It avoids the repeat
adding index to the cluser_info. The code is easier to understand.
Remove the cluster next pointer is NULL flag, the double link
list can handle the empty list pretty well.
The "swap_cluster_info" struct is two pointer bigger, because
512 swap entries share one swap struct, it has very little impact
on the average memory usage per swap entry. For 1TB swapfile, the
swap cluster data structure increases from 8MB to 24MB.
Other than the list conversion, there is no real function change
in this patch.
Signed-off-by: Chris Li <chrisl@kernel.org>
---
include/linux/swap.h | 26 +++---
mm/swapfile.c | 227 ++++++++++++++-------------------------------------
2 files changed, 70 insertions(+), 183 deletions(-)
diff --git a/include/linux/swap.h b/include/linux/swap.h
index 3df75d62a835..690a04f06674 100644
--- a/include/linux/swap.h
+++ b/include/linux/swap.h
@@ -243,22 +243,21 @@ enum {
* free clusters are organized into a list. We fetch an entry from the list to
* get a free cluster.
*
- * The data field stores next cluster if the cluster is free or cluster usage
- * counter otherwise. The flags field determines if a cluster is free. This is
- * protected by swap_info_struct.lock.
+ * The flags field determines if a cluster is free. This is
+ * protected by cluster lock.
*/
struct swap_cluster_info {
spinlock_t lock; /*
* Protect swap_cluster_info fields
- * and swap_info_struct->swap_map
- * elements correspond to the swap
- * cluster
+ * other than list, and swap_info_struct->swap_map
+ * elements correspond to the swap cluster.
*/
- unsigned int data:24;
- unsigned int flags:8;
+ u16 count;
+ u8 flags;
+ struct list_head list;
};
#define CLUSTER_FLAG_FREE 1 /* This cluster is free */
-#define CLUSTER_FLAG_NEXT_NULL 2 /* This cluster has no next cluster */
+
/*
* The first page in the swap file is the swap header, which is always marked
@@ -283,11 +282,6 @@ struct percpu_cluster {
unsigned int next[SWAP_NR_ORDERS]; /* Likely next allocation offset */
};
-struct swap_cluster_list {
- struct swap_cluster_info head;
- struct swap_cluster_info tail;
-};
-
/*
* The in-memory structure used to track swap areas.
*/
@@ -300,7 +294,7 @@ struct swap_info_struct {
unsigned int max; /* extent of the swap_map */
unsigned char *swap_map; /* vmalloc'ed array of usage counts */
struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
- struct swap_cluster_list free_clusters; /* free clusters list */
+ struct list_head free_clusters; /* free clusters list */
unsigned int lowest_bit; /* index of first free in swap_map */
unsigned int highest_bit; /* index of last free in swap_map */
unsigned int pages; /* total of usable pages of swap */
@@ -331,7 +325,7 @@ struct swap_info_struct {
* list.
*/
struct work_struct discard_work; /* discard worker */
- struct swap_cluster_list discard_clusters; /* discard clusters list */
+ struct list_head discard_clusters; /* discard clusters list */
struct plist_node avail_lists[]; /*
* entries in swap_avail_heads, one
* entry per node.
diff --git a/mm/swapfile.c b/mm/swapfile.c
index 9c6d8e557c0f..0b11c437f9cc 100644
--- a/mm/swapfile.c
+++ b/mm/swapfile.c
@@ -290,64 +290,11 @@ static void discard_swap_cluster(struct swap_info_struct *si,
#endif
#define LATENCY_LIMIT 256
-static inline void cluster_set_flag(struct swap_cluster_info *info,
- unsigned int flag)
-{
- info->flags = flag;
-}
-
-static inline unsigned int cluster_count(struct swap_cluster_info *info)
-{
- return info->data;
-}
-
-static inline void cluster_set_count(struct swap_cluster_info *info,
- unsigned int c)
-{
- info->data = c;
-}
-
-static inline void cluster_set_count_flag(struct swap_cluster_info *info,
- unsigned int c, unsigned int f)
-{
- info->flags = f;
- info->data = c;
-}
-
-static inline unsigned int cluster_next(struct swap_cluster_info *info)
-{
- return info->data;
-}
-
-static inline void cluster_set_next(struct swap_cluster_info *info,
- unsigned int n)
-{
- info->data = n;
-}
-
-static inline void cluster_set_next_flag(struct swap_cluster_info *info,
- unsigned int n, unsigned int f)
-{
- info->flags = f;
- info->data = n;
-}
-
static inline bool cluster_is_free(struct swap_cluster_info *info)
{
return info->flags & CLUSTER_FLAG_FREE;
}
-static inline bool cluster_is_null(struct swap_cluster_info *info)
-{
- return info->flags & CLUSTER_FLAG_NEXT_NULL;
-}
-
-static inline void cluster_set_null(struct swap_cluster_info *info)
-{
- info->flags = CLUSTER_FLAG_NEXT_NULL;
- info->data = 0;
-}
-
static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
unsigned long offset)
{
@@ -394,65 +341,11 @@ static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
spin_unlock(&si->lock);
}
-static inline bool cluster_list_empty(struct swap_cluster_list *list)
-{
- return cluster_is_null(&list->head);
-}
-
-static inline unsigned int cluster_list_first(struct swap_cluster_list *list)
-{
- return cluster_next(&list->head);
-}
-
-static void cluster_list_init(struct swap_cluster_list *list)
-{
- cluster_set_null(&list->head);
- cluster_set_null(&list->tail);
-}
-
-static void cluster_list_add_tail(struct swap_cluster_list *list,
- struct swap_cluster_info *ci,
- unsigned int idx)
-{
- if (cluster_list_empty(list)) {
- cluster_set_next_flag(&list->head, idx, 0);
- cluster_set_next_flag(&list->tail, idx, 0);
- } else {
- struct swap_cluster_info *ci_tail;
- unsigned int tail = cluster_next(&list->tail);
-
- /*
- * Nested cluster lock, but both cluster locks are
- * only acquired when we held swap_info_struct->lock
- */
- ci_tail = ci + tail;
- spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);
- cluster_set_next(ci_tail, idx);
- spin_unlock(&ci_tail->lock);
- cluster_set_next_flag(&list->tail, idx, 0);
- }
-}
-
-static unsigned int cluster_list_del_first(struct swap_cluster_list *list,
- struct swap_cluster_info *ci)
-{
- unsigned int idx;
-
- idx = cluster_next(&list->head);
- if (cluster_next(&list->tail) == idx) {
- cluster_set_null(&list->head);
- cluster_set_null(&list->tail);
- } else
- cluster_set_next_flag(&list->head,
- cluster_next(&ci[idx]), 0);
-
- return idx;
-}
-
/* Add a cluster to discard list and schedule it to do discard */
static void swap_cluster_schedule_discard(struct swap_info_struct *si,
- unsigned int idx)
+ struct swap_cluster_info *ci)
{
+ unsigned int idx = ci - si->cluster_info;
/*
* If scan_swap_map_slots() can't find a free cluster, it will check
* si->swap_map directly. To make sure the discarding cluster isn't
@@ -462,17 +355,14 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
memset(si->swap_map + idx * SWAPFILE_CLUSTER,
SWAP_MAP_BAD, SWAPFILE_CLUSTER);
- cluster_list_add_tail(&si->discard_clusters, si->cluster_info, idx);
-
+ list_add_tail(&ci->list, &si->discard_clusters);
schedule_work(&si->discard_work);
}
-static void __free_cluster(struct swap_info_struct *si, unsigned long idx)
+static void __free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
{
- struct swap_cluster_info *ci = si->cluster_info;
-
- cluster_set_flag(ci + idx, CLUSTER_FLAG_FREE);
- cluster_list_add_tail(&si->free_clusters, ci, idx);
+ ci->flags = CLUSTER_FLAG_FREE;
+ list_add_tail(&ci->list, &si->free_clusters);
}
/*
@@ -481,21 +371,22 @@ static void __free_cluster(struct swap_info_struct *si, unsigned long idx)
*/
static void swap_do_scheduled_discard(struct swap_info_struct *si)
{
- struct swap_cluster_info *info, *ci;
+ struct swap_cluster_info *ci;
unsigned int idx;
- info = si->cluster_info;
-
- while (!cluster_list_empty(&si->discard_clusters)) {
- idx = cluster_list_del_first(&si->discard_clusters, info);
+ while (!list_empty(&si->discard_clusters)) {
+ ci = list_first_entry(&si->discard_clusters, struct swap_cluster_info, list);
+ list_del(&ci->list);
+ idx = ci - si->cluster_info;
spin_unlock(&si->lock);
discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
SWAPFILE_CLUSTER);
spin_lock(&si->lock);
- ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
- __free_cluster(si, idx);
+
+ spin_lock(&ci->lock);
+ __free_cluster(si, ci);
memset(si->swap_map + idx * SWAPFILE_CLUSTER,
0, SWAPFILE_CLUSTER);
unlock_cluster(ci);
@@ -521,20 +412,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
complete(&si->comp);
}
-static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
+static struct swap_cluster_info *alloc_cluster(struct swap_info_struct *si, unsigned long idx)
{
- struct swap_cluster_info *ci = si->cluster_info;
+ struct swap_cluster_info *ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
- VM_BUG_ON(cluster_list_first(&si->free_clusters) != idx);
- cluster_list_del_first(&si->free_clusters, ci);
- cluster_set_count_flag(ci + idx, 0, 0);
+ VM_BUG_ON(ci - si->cluster_info != idx);
+ list_del(&ci->list);
+ ci->count = 0;
+ ci->flags = 0;
+ return ci;
}
-static void free_cluster(struct swap_info_struct *si, unsigned long idx)
+static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
{
- struct swap_cluster_info *ci = si->cluster_info + idx;
-
- VM_BUG_ON(cluster_count(ci) != 0);
+ VM_BUG_ON(ci->count != 0);
/*
* If the swap is discardable, prepare discard the cluster
* instead of free it immediately. The cluster will be freed
@@ -542,11 +433,11 @@ static void free_cluster(struct swap_info_struct *si, unsigned long idx)
*/
if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
(SWP_WRITEOK | SWP_PAGE_DISCARD)) {
- swap_cluster_schedule_discard(si, idx);
+ swap_cluster_schedule_discard(si, ci);
return;
}
- __free_cluster(si, idx);
+ __free_cluster(si, ci);
}
/*
@@ -559,15 +450,15 @@ static void add_cluster_info_page(struct swap_info_struct *p,
unsigned long count)
{
unsigned long idx = page_nr / SWAPFILE_CLUSTER;
+ struct swap_cluster_info *ci = cluster_info + idx;
if (!cluster_info)
return;
- if (cluster_is_free(&cluster_info[idx]))
+ if (cluster_is_free(ci))
alloc_cluster(p, idx);
- VM_BUG_ON(cluster_count(&cluster_info[idx]) + count > SWAPFILE_CLUSTER);
- cluster_set_count(&cluster_info[idx],
- cluster_count(&cluster_info[idx]) + count);
+ VM_BUG_ON(ci->count + count > SWAPFILE_CLUSTER);
+ ci->count += count;
}
/*
@@ -581,24 +472,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
}
/*
- * The cluster corresponding to page_nr decreases one usage. If the usage
- * counter becomes 0, which means no page in the cluster is in using, we can
- * optionally discard the cluster and add it to free cluster list.
+ * The cluster ci decreases one usage. If the usage counter becomes 0,
+ * which means no page in the cluster is in using, we can optionally discard
+ * the cluster and add it to free cluster list.
*/
-static void dec_cluster_info_page(struct swap_info_struct *p,
- struct swap_cluster_info *cluster_info, unsigned long page_nr)
+static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluster_info *ci)
{
- unsigned long idx = page_nr / SWAPFILE_CLUSTER;
-
- if (!cluster_info)
+ if (!p->cluster_info)
return;
- VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
- cluster_set_count(&cluster_info[idx],
- cluster_count(&cluster_info[idx]) - 1);
+ VM_BUG_ON(ci->count == 0);
+ ci->count--;
- if (cluster_count(&cluster_info[idx]) == 0)
- free_cluster(p, idx);
+ if (!ci->count)
+ free_cluster(p, ci);
}
/*
@@ -611,10 +498,10 @@ scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
{
struct percpu_cluster *percpu_cluster;
bool conflict;
-
+ struct swap_cluster_info *first = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
offset /= SWAPFILE_CLUSTER;
- conflict = !cluster_list_empty(&si->free_clusters) &&
- offset != cluster_list_first(&si->free_clusters) &&
+ conflict = !list_empty(&si->free_clusters) &&
+ offset != first - si->cluster_info &&
cluster_is_free(&si->cluster_info[offset]);
if (!conflict)
@@ -655,10 +542,14 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
cluster = this_cpu_ptr(si->percpu_cluster);
tmp = cluster->next[order];
if (tmp == SWAP_NEXT_INVALID) {
- if (!cluster_list_empty(&si->free_clusters)) {
- tmp = cluster_next(&si->free_clusters.head) *
- SWAPFILE_CLUSTER;
- } else if (!cluster_list_empty(&si->discard_clusters)) {
+ if (!list_empty(&si->free_clusters)) {
+ ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
+ list_del(&ci->list);
+ spin_lock(&ci->lock);
+ ci->flags = 0;
+ spin_unlock(&ci->lock);
+ tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
+ } else if (!list_empty(&si->discard_clusters)) {
/*
* we don't have free cluster but have some clusters in
* discarding, do discard now and reclaim them, then
@@ -1062,8 +953,9 @@ static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx)
ci = lock_cluster(si, offset);
memset(si->swap_map + offset, 0, SWAPFILE_CLUSTER);
- cluster_set_count_flag(ci, 0, 0);
- free_cluster(si, idx);
+ ci->count = 0;
+ ci->flags = 0;
+ free_cluster(si, ci);
unlock_cluster(ci);
swap_range_free(si, offset, SWAPFILE_CLUSTER);
}
@@ -1336,7 +1228,7 @@ static void swap_entry_free(struct swap_info_struct *p, swp_entry_t entry)
count = p->swap_map[offset];
VM_BUG_ON(count != SWAP_HAS_CACHE);
p->swap_map[offset] = 0;
- dec_cluster_info_page(p, p->cluster_info, offset);
+ dec_cluster_info_page(p, ci);
unlock_cluster(ci);
mem_cgroup_uncharge_swap(entry, 1);
@@ -3003,8 +2895,8 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p,
nr_good_pages = maxpages - 1; /* omit header page */
- cluster_list_init(&p->free_clusters);
- cluster_list_init(&p->discard_clusters);
+ INIT_LIST_HEAD(&p->free_clusters);
+ INIT_LIST_HEAD(&p->discard_clusters);
for (i = 0; i < swap_header->info.nr_badpages; i++) {
unsigned int page_nr = swap_header->info.badpages[i];
@@ -3055,14 +2947,15 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p,
for (k = 0; k < SWAP_CLUSTER_COLS; k++) {
j = (k + col) % SWAP_CLUSTER_COLS;
for (i = 0; i < DIV_ROUND_UP(nr_clusters, SWAP_CLUSTER_COLS); i++) {
+ struct swap_cluster_info *ci;
idx = i * SWAP_CLUSTER_COLS + j;
+ ci = cluster_info + idx;
if (idx >= nr_clusters)
continue;
- if (cluster_count(&cluster_info[idx]))
+ if (ci->count)
continue;
- cluster_set_flag(&cluster_info[idx], CLUSTER_FLAG_FREE);
- cluster_list_add_tail(&p->free_clusters, cluster_info,
- idx);
+ ci->flags = CLUSTER_FLAG_FREE;
+ list_add_tail(&ci->list, &p->free_clusters);
}
}
return nr_extents;
--
2.45.2.627.g7a2c4fd464-goog
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 1/2] mm: swap: swap cluster switch to double link list
2024-06-19 9:20 ` [PATCH v3 1/2] mm: swap: swap cluster switch to double link list Chris Li
@ 2024-06-21 2:59 ` Huang, Ying
2024-06-21 18:55 ` Chris Li
0 siblings, 1 reply; 16+ messages in thread
From: Huang, Ying @ 2024-06-21 2:59 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> Previously, the swap cluster used a cluster index as a pointer
> to construct a custom single link list type "swap_cluster_list".
> The next cluster pointer is shared with the cluster->count.
> It prevents puting the non free cluster into a list.
>
> Change the cluster to use the standard double link list instead.
> This allows tracing the nonfull cluster in the follow up patch.
> That way, it is faster to get to the nonfull cluster of that order.
>
> Remove the cluster getter/setter for accessing the cluster
> struct member.
>
> The list operation is protected by the swap_info_struct->lock.
>
> Change cluster code to use "struct swap_cluster_info *" to
> reference the cluster rather than by using index. That is more
> consistent with the list manipulation. It avoids the repeat
> adding index to the cluser_info. The code is easier to understand.
>
> Remove the cluster next pointer is NULL flag, the double link
> list can handle the empty list pretty well.
>
> The "swap_cluster_info" struct is two pointer bigger, because
> 512 swap entries share one swap struct, it has very little impact
> on the average memory usage per swap entry. For 1TB swapfile, the
> swap cluster data structure increases from 8MB to 24MB.
>
> Other than the list conversion, there is no real function change
> in this patch.
>
> Signed-off-by: Chris Li <chrisl@kernel.org>
> ---
> include/linux/swap.h | 26 +++---
> mm/swapfile.c | 227 ++++++++++++++-------------------------------------
> 2 files changed, 70 insertions(+), 183 deletions(-)
>
> diff --git a/include/linux/swap.h b/include/linux/swap.h
> index 3df75d62a835..690a04f06674 100644
> --- a/include/linux/swap.h
> +++ b/include/linux/swap.h
> @@ -243,22 +243,21 @@ enum {
> * free clusters are organized into a list. We fetch an entry from the list to
> * get a free cluster.
> *
> - * The data field stores next cluster if the cluster is free or cluster usage
> - * counter otherwise. The flags field determines if a cluster is free. This is
> - * protected by swap_info_struct.lock.
> + * The flags field determines if a cluster is free. This is
> + * protected by cluster lock.
> */
> struct swap_cluster_info {
> spinlock_t lock; /*
> * Protect swap_cluster_info fields
> - * and swap_info_struct->swap_map
> - * elements correspond to the swap
> - * cluster
> + * other than list, and swap_info_struct->swap_map
> + * elements correspond to the swap cluster.
> */
> - unsigned int data:24;
> - unsigned int flags:8;
> + u16 count;
> + u8 flags;
> + struct list_head list;
> };
> #define CLUSTER_FLAG_FREE 1 /* This cluster is free */
> -#define CLUSTER_FLAG_NEXT_NULL 2 /* This cluster has no next cluster */
> +
>
> /*
> * The first page in the swap file is the swap header, which is always marked
> @@ -283,11 +282,6 @@ struct percpu_cluster {
> unsigned int next[SWAP_NR_ORDERS]; /* Likely next allocation offset */
> };
>
> -struct swap_cluster_list {
> - struct swap_cluster_info head;
> - struct swap_cluster_info tail;
> -};
> -
> /*
> * The in-memory structure used to track swap areas.
> */
> @@ -300,7 +294,7 @@ struct swap_info_struct {
> unsigned int max; /* extent of the swap_map */
> unsigned char *swap_map; /* vmalloc'ed array of usage counts */
> struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
> - struct swap_cluster_list free_clusters; /* free clusters list */
> + struct list_head free_clusters; /* free clusters list */
> unsigned int lowest_bit; /* index of first free in swap_map */
> unsigned int highest_bit; /* index of last free in swap_map */
> unsigned int pages; /* total of usable pages of swap */
> @@ -331,7 +325,7 @@ struct swap_info_struct {
> * list.
> */
> struct work_struct discard_work; /* discard worker */
> - struct swap_cluster_list discard_clusters; /* discard clusters list */
> + struct list_head discard_clusters; /* discard clusters list */
> struct plist_node avail_lists[]; /*
> * entries in swap_avail_heads, one
> * entry per node.
> diff --git a/mm/swapfile.c b/mm/swapfile.c
> index 9c6d8e557c0f..0b11c437f9cc 100644
> --- a/mm/swapfile.c
> +++ b/mm/swapfile.c
> @@ -290,64 +290,11 @@ static void discard_swap_cluster(struct swap_info_struct *si,
> #endif
> #define LATENCY_LIMIT 256
>
> -static inline void cluster_set_flag(struct swap_cluster_info *info,
> - unsigned int flag)
> -{
> - info->flags = flag;
> -}
> -
> -static inline unsigned int cluster_count(struct swap_cluster_info *info)
> -{
> - return info->data;
> -}
> -
> -static inline void cluster_set_count(struct swap_cluster_info *info,
> - unsigned int c)
> -{
> - info->data = c;
> -}
> -
> -static inline void cluster_set_count_flag(struct swap_cluster_info *info,
> - unsigned int c, unsigned int f)
> -{
> - info->flags = f;
> - info->data = c;
> -}
> -
> -static inline unsigned int cluster_next(struct swap_cluster_info *info)
> -{
> - return info->data;
> -}
> -
> -static inline void cluster_set_next(struct swap_cluster_info *info,
> - unsigned int n)
> -{
> - info->data = n;
> -}
> -
> -static inline void cluster_set_next_flag(struct swap_cluster_info *info,
> - unsigned int n, unsigned int f)
> -{
> - info->flags = f;
> - info->data = n;
> -}
> -
> static inline bool cluster_is_free(struct swap_cluster_info *info)
> {
> return info->flags & CLUSTER_FLAG_FREE;
> }
>
> -static inline bool cluster_is_null(struct swap_cluster_info *info)
> -{
> - return info->flags & CLUSTER_FLAG_NEXT_NULL;
> -}
> -
> -static inline void cluster_set_null(struct swap_cluster_info *info)
> -{
> - info->flags = CLUSTER_FLAG_NEXT_NULL;
> - info->data = 0;
> -}
> -
> static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
> unsigned long offset)
> {
> @@ -394,65 +341,11 @@ static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
> spin_unlock(&si->lock);
> }
>
> -static inline bool cluster_list_empty(struct swap_cluster_list *list)
> -{
> - return cluster_is_null(&list->head);
> -}
> -
> -static inline unsigned int cluster_list_first(struct swap_cluster_list *list)
> -{
> - return cluster_next(&list->head);
> -}
> -
> -static void cluster_list_init(struct swap_cluster_list *list)
> -{
> - cluster_set_null(&list->head);
> - cluster_set_null(&list->tail);
> -}
> -
> -static void cluster_list_add_tail(struct swap_cluster_list *list,
> - struct swap_cluster_info *ci,
> - unsigned int idx)
> -{
> - if (cluster_list_empty(list)) {
> - cluster_set_next_flag(&list->head, idx, 0);
> - cluster_set_next_flag(&list->tail, idx, 0);
> - } else {
> - struct swap_cluster_info *ci_tail;
> - unsigned int tail = cluster_next(&list->tail);
> -
> - /*
> - * Nested cluster lock, but both cluster locks are
> - * only acquired when we held swap_info_struct->lock
> - */
> - ci_tail = ci + tail;
> - spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);
> - cluster_set_next(ci_tail, idx);
> - spin_unlock(&ci_tail->lock);
> - cluster_set_next_flag(&list->tail, idx, 0);
> - }
> -}
> -
> -static unsigned int cluster_list_del_first(struct swap_cluster_list *list,
> - struct swap_cluster_info *ci)
> -{
> - unsigned int idx;
> -
> - idx = cluster_next(&list->head);
> - if (cluster_next(&list->tail) == idx) {
> - cluster_set_null(&list->head);
> - cluster_set_null(&list->tail);
> - } else
> - cluster_set_next_flag(&list->head,
> - cluster_next(&ci[idx]), 0);
> -
> - return idx;
> -}
> -
> /* Add a cluster to discard list and schedule it to do discard */
> static void swap_cluster_schedule_discard(struct swap_info_struct *si,
> - unsigned int idx)
> + struct swap_cluster_info *ci)
> {
> + unsigned int idx = ci - si->cluster_info;
IIRC, we have reached consensus that we will add a helper for this
pattern.
> /*
> * If scan_swap_map_slots() can't find a free cluster, it will check
> * si->swap_map directly. To make sure the discarding cluster isn't
> @@ -462,17 +355,14 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
> memset(si->swap_map + idx * SWAPFILE_CLUSTER,
> SWAP_MAP_BAD, SWAPFILE_CLUSTER);
>
> - cluster_list_add_tail(&si->discard_clusters, si->cluster_info, idx);
> -
> + list_add_tail(&ci->list, &si->discard_clusters);
> schedule_work(&si->discard_work);
> }
>
> -static void __free_cluster(struct swap_info_struct *si, unsigned long idx)
> +static void __free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
> {
> - struct swap_cluster_info *ci = si->cluster_info;
> -
> - cluster_set_flag(ci + idx, CLUSTER_FLAG_FREE);
> - cluster_list_add_tail(&si->free_clusters, ci, idx);
> + ci->flags = CLUSTER_FLAG_FREE;
> + list_add_tail(&ci->list, &si->free_clusters);
> }
>
> /*
> @@ -481,21 +371,22 @@ static void __free_cluster(struct swap_info_struct *si, unsigned long idx)
> */
> static void swap_do_scheduled_discard(struct swap_info_struct *si)
> {
> - struct swap_cluster_info *info, *ci;
> + struct swap_cluster_info *ci;
> unsigned int idx;
>
> - info = si->cluster_info;
> -
> - while (!cluster_list_empty(&si->discard_clusters)) {
> - idx = cluster_list_del_first(&si->discard_clusters, info);
> + while (!list_empty(&si->discard_clusters)) {
> + ci = list_first_entry(&si->discard_clusters, struct swap_cluster_info, list);
> + list_del(&ci->list);
> + idx = ci - si->cluster_info;
> spin_unlock(&si->lock);
>
> discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
> SWAPFILE_CLUSTER);
>
> spin_lock(&si->lock);
> - ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
> - __free_cluster(si, idx);
> +
> + spin_lock(&ci->lock);
If you really don't like lock_cluster(), please replace unlock_cluster()
below with spin_unlock() too.
> + __free_cluster(si, ci);
> memset(si->swap_map + idx * SWAPFILE_CLUSTER,
> 0, SWAPFILE_CLUSTER);
> unlock_cluster(ci);
> @@ -521,20 +412,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
> complete(&si->comp);
> }
>
> -static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> +static struct swap_cluster_info *alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> {
> - struct swap_cluster_info *ci = si->cluster_info;
> + struct swap_cluster_info *ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
>
> - VM_BUG_ON(cluster_list_first(&si->free_clusters) != idx);
> - cluster_list_del_first(&si->free_clusters, ci);
> - cluster_set_count_flag(ci + idx, 0, 0);
> + VM_BUG_ON(ci - si->cluster_info != idx);
> + list_del(&ci->list);
> + ci->count = 0;
> + ci->flags = 0;
> + return ci;
> }
>
> -static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> +static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
> {
> - struct swap_cluster_info *ci = si->cluster_info + idx;
> -
> - VM_BUG_ON(cluster_count(ci) != 0);
> + VM_BUG_ON(ci->count != 0);
> /*
> * If the swap is discardable, prepare discard the cluster
> * instead of free it immediately. The cluster will be freed
> @@ -542,11 +433,11 @@ static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> */
> if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
> (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
> - swap_cluster_schedule_discard(si, idx);
> + swap_cluster_schedule_discard(si, ci);
> return;
> }
>
> - __free_cluster(si, idx);
> + __free_cluster(si, ci);
> }
>
> /*
> @@ -559,15 +450,15 @@ static void add_cluster_info_page(struct swap_info_struct *p,
> unsigned long count)
> {
> unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> + struct swap_cluster_info *ci = cluster_info + idx;
>
> if (!cluster_info)
> return;
> - if (cluster_is_free(&cluster_info[idx]))
> + if (cluster_is_free(ci))
> alloc_cluster(p, idx);
>
> - VM_BUG_ON(cluster_count(&cluster_info[idx]) + count > SWAPFILE_CLUSTER);
> - cluster_set_count(&cluster_info[idx],
> - cluster_count(&cluster_info[idx]) + count);
> + VM_BUG_ON(ci->count + count > SWAPFILE_CLUSTER);
> + ci->count += count;
> }
>
> /*
> @@ -581,24 +472,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
> }
>
> /*
> - * The cluster corresponding to page_nr decreases one usage. If the usage
> - * counter becomes 0, which means no page in the cluster is in using, we can
> - * optionally discard the cluster and add it to free cluster list.
> + * The cluster ci decreases one usage. If the usage counter becomes 0,
> + * which means no page in the cluster is in using, we can optionally discard
> + * the cluster and add it to free cluster list.
> */
> -static void dec_cluster_info_page(struct swap_info_struct *p,
> - struct swap_cluster_info *cluster_info, unsigned long page_nr)
> +static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluster_info *ci)
> {
> - unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> -
> - if (!cluster_info)
> + if (!p->cluster_info)
> return;
>
> - VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
> - cluster_set_count(&cluster_info[idx],
> - cluster_count(&cluster_info[idx]) - 1);
> + VM_BUG_ON(ci->count == 0);
> + ci->count--;
>
> - if (cluster_count(&cluster_info[idx]) == 0)
> - free_cluster(p, idx);
> + if (!ci->count)
> + free_cluster(p, ci);
> }
>
> /*
> @@ -611,10 +498,10 @@ scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
> {
> struct percpu_cluster *percpu_cluster;
> bool conflict;
> -
> + struct swap_cluster_info *first = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> offset /= SWAPFILE_CLUSTER;
> - conflict = !cluster_list_empty(&si->free_clusters) &&
> - offset != cluster_list_first(&si->free_clusters) &&
> + conflict = !list_empty(&si->free_clusters) &&
> + offset != first - si->cluster_info &&
> cluster_is_free(&si->cluster_info[offset]);
>
> if (!conflict)
> @@ -655,10 +542,14 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
> cluster = this_cpu_ptr(si->percpu_cluster);
> tmp = cluster->next[order];
> if (tmp == SWAP_NEXT_INVALID) {
> - if (!cluster_list_empty(&si->free_clusters)) {
> - tmp = cluster_next(&si->free_clusters.head) *
> - SWAPFILE_CLUSTER;
> - } else if (!cluster_list_empty(&si->discard_clusters)) {
> + if (!list_empty(&si->free_clusters)) {
> + ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> + list_del(&ci->list);
IIRC, we shouldn't delete the cluster from the free list here, because
we will delete it later in alloc_cluster().
> + spin_lock(&ci->lock);
> + ci->flags = 0;
And also shouldn't set ci->flags here too. Because the cluster may be
kept in free list if scan_swap_map_ssd_cluster_conflict() returns true.
> + spin_unlock(&ci->lock);
> + tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
> + } else if (!list_empty(&si->discard_clusters)) {
> /*
> * we don't have free cluster but have some clusters in
> * discarding, do discard now and reclaim them, then
[snip]
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 1/2] mm: swap: swap cluster switch to double link list
2024-06-21 2:59 ` Huang, Ying
@ 2024-06-21 18:55 ` Chris Li
2024-06-24 10:16 ` Huang, Ying
0 siblings, 1 reply; 16+ messages in thread
From: Chris Li @ 2024-06-21 18:55 UTC (permalink / raw)
To: Huang, Ying
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
On Thu, Jun 20, 2024 at 8:01 PM Huang, Ying <ying.huang@intel.com> wrote:
>
> Chris Li <chrisl@kernel.org> writes:
>
> > Previously, the swap cluster used a cluster index as a pointer
> > to construct a custom single link list type "swap_cluster_list".
> > The next cluster pointer is shared with the cluster->count.
> > It prevents puting the non free cluster into a list.
> >
> > Change the cluster to use the standard double link list instead.
> > This allows tracing the nonfull cluster in the follow up patch.
> > That way, it is faster to get to the nonfull cluster of that order.
> >
> > Remove the cluster getter/setter for accessing the cluster
> > struct member.
> >
> > The list operation is protected by the swap_info_struct->lock.
> >
> > Change cluster code to use "struct swap_cluster_info *" to
> > reference the cluster rather than by using index. That is more
> > consistent with the list manipulation. It avoids the repeat
> > adding index to the cluser_info. The code is easier to understand.
> >
> > Remove the cluster next pointer is NULL flag, the double link
> > list can handle the empty list pretty well.
> >
> > The "swap_cluster_info" struct is two pointer bigger, because
> > 512 swap entries share one swap struct, it has very little impact
> > on the average memory usage per swap entry. For 1TB swapfile, the
> > swap cluster data structure increases from 8MB to 24MB.
> >
> > Other than the list conversion, there is no real function change
> > in this patch.
> >
> > Signed-off-by: Chris Li <chrisl@kernel.org>
> > ---
> > include/linux/swap.h | 26 +++---
> > mm/swapfile.c | 227 ++++++++++++++-------------------------------------
> > 2 files changed, 70 insertions(+), 183 deletions(-)
> >
> > diff --git a/include/linux/swap.h b/include/linux/swap.h
> > index 3df75d62a835..690a04f06674 100644
> > --- a/include/linux/swap.h
> > +++ b/include/linux/swap.h
> > @@ -243,22 +243,21 @@ enum {
> > * free clusters are organized into a list. We fetch an entry from the list to
> > * get a free cluster.
> > *
> > - * The data field stores next cluster if the cluster is free or cluster usage
> > - * counter otherwise. The flags field determines if a cluster is free. This is
> > - * protected by swap_info_struct.lock.
> > + * The flags field determines if a cluster is free. This is
> > + * protected by cluster lock.
> > */
> > struct swap_cluster_info {
> > spinlock_t lock; /*
> > * Protect swap_cluster_info fields
> > - * and swap_info_struct->swap_map
> > - * elements correspond to the swap
> > - * cluster
> > + * other than list, and swap_info_struct->swap_map
> > + * elements correspond to the swap cluster.
> > */
> > - unsigned int data:24;
> > - unsigned int flags:8;
> > + u16 count;
> > + u8 flags;
> > + struct list_head list;
> > };
> > #define CLUSTER_FLAG_FREE 1 /* This cluster is free */
> > -#define CLUSTER_FLAG_NEXT_NULL 2 /* This cluster has no next cluster */
> > +
> >
> > /*
> > * The first page in the swap file is the swap header, which is always marked
> > @@ -283,11 +282,6 @@ struct percpu_cluster {
> > unsigned int next[SWAP_NR_ORDERS]; /* Likely next allocation offset */
> > };
> >
> > -struct swap_cluster_list {
> > - struct swap_cluster_info head;
> > - struct swap_cluster_info tail;
> > -};
> > -
> > /*
> > * The in-memory structure used to track swap areas.
> > */
> > @@ -300,7 +294,7 @@ struct swap_info_struct {
> > unsigned int max; /* extent of the swap_map */
> > unsigned char *swap_map; /* vmalloc'ed array of usage counts */
> > struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
> > - struct swap_cluster_list free_clusters; /* free clusters list */
> > + struct list_head free_clusters; /* free clusters list */
> > unsigned int lowest_bit; /* index of first free in swap_map */
> > unsigned int highest_bit; /* index of last free in swap_map */
> > unsigned int pages; /* total of usable pages of swap */
> > @@ -331,7 +325,7 @@ struct swap_info_struct {
> > * list.
> > */
> > struct work_struct discard_work; /* discard worker */
> > - struct swap_cluster_list discard_clusters; /* discard clusters list */
> > + struct list_head discard_clusters; /* discard clusters list */
> > struct plist_node avail_lists[]; /*
> > * entries in swap_avail_heads, one
> > * entry per node.
> > diff --git a/mm/swapfile.c b/mm/swapfile.c
> > index 9c6d8e557c0f..0b11c437f9cc 100644
> > --- a/mm/swapfile.c
> > +++ b/mm/swapfile.c
> > @@ -290,64 +290,11 @@ static void discard_swap_cluster(struct swap_info_struct *si,
> > #endif
> > #define LATENCY_LIMIT 256
> >
> > -static inline void cluster_set_flag(struct swap_cluster_info *info,
> > - unsigned int flag)
> > -{
> > - info->flags = flag;
> > -}
> > -
> > -static inline unsigned int cluster_count(struct swap_cluster_info *info)
> > -{
> > - return info->data;
> > -}
> > -
> > -static inline void cluster_set_count(struct swap_cluster_info *info,
> > - unsigned int c)
> > -{
> > - info->data = c;
> > -}
> > -
> > -static inline void cluster_set_count_flag(struct swap_cluster_info *info,
> > - unsigned int c, unsigned int f)
> > -{
> > - info->flags = f;
> > - info->data = c;
> > -}
> > -
> > -static inline unsigned int cluster_next(struct swap_cluster_info *info)
> > -{
> > - return info->data;
> > -}
> > -
> > -static inline void cluster_set_next(struct swap_cluster_info *info,
> > - unsigned int n)
> > -{
> > - info->data = n;
> > -}
> > -
> > -static inline void cluster_set_next_flag(struct swap_cluster_info *info,
> > - unsigned int n, unsigned int f)
> > -{
> > - info->flags = f;
> > - info->data = n;
> > -}
> > -
> > static inline bool cluster_is_free(struct swap_cluster_info *info)
> > {
> > return info->flags & CLUSTER_FLAG_FREE;
> > }
> >
> > -static inline bool cluster_is_null(struct swap_cluster_info *info)
> > -{
> > - return info->flags & CLUSTER_FLAG_NEXT_NULL;
> > -}
> > -
> > -static inline void cluster_set_null(struct swap_cluster_info *info)
> > -{
> > - info->flags = CLUSTER_FLAG_NEXT_NULL;
> > - info->data = 0;
> > -}
> > -
> > static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
> > unsigned long offset)
> > {
> > @@ -394,65 +341,11 @@ static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
> > spin_unlock(&si->lock);
> > }
> >
> > -static inline bool cluster_list_empty(struct swap_cluster_list *list)
> > -{
> > - return cluster_is_null(&list->head);
> > -}
> > -
> > -static inline unsigned int cluster_list_first(struct swap_cluster_list *list)
> > -{
> > - return cluster_next(&list->head);
> > -}
> > -
> > -static void cluster_list_init(struct swap_cluster_list *list)
> > -{
> > - cluster_set_null(&list->head);
> > - cluster_set_null(&list->tail);
> > -}
> > -
> > -static void cluster_list_add_tail(struct swap_cluster_list *list,
> > - struct swap_cluster_info *ci,
> > - unsigned int idx)
> > -{
> > - if (cluster_list_empty(list)) {
> > - cluster_set_next_flag(&list->head, idx, 0);
> > - cluster_set_next_flag(&list->tail, idx, 0);
> > - } else {
> > - struct swap_cluster_info *ci_tail;
> > - unsigned int tail = cluster_next(&list->tail);
> > -
> > - /*
> > - * Nested cluster lock, but both cluster locks are
> > - * only acquired when we held swap_info_struct->lock
> > - */
> > - ci_tail = ci + tail;
> > - spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);
> > - cluster_set_next(ci_tail, idx);
> > - spin_unlock(&ci_tail->lock);
> > - cluster_set_next_flag(&list->tail, idx, 0);
> > - }
> > -}
> > -
> > -static unsigned int cluster_list_del_first(struct swap_cluster_list *list,
> > - struct swap_cluster_info *ci)
> > -{
> > - unsigned int idx;
> > -
> > - idx = cluster_next(&list->head);
> > - if (cluster_next(&list->tail) == idx) {
> > - cluster_set_null(&list->head);
> > - cluster_set_null(&list->tail);
> > - } else
> > - cluster_set_next_flag(&list->head,
> > - cluster_next(&ci[idx]), 0);
> > -
> > - return idx;
> > -}
> > -
> > /* Add a cluster to discard list and schedule it to do discard */
> > static void swap_cluster_schedule_discard(struct swap_info_struct *si,
> > - unsigned int idx)
> > + struct swap_cluster_info *ci)
> > {
> > + unsigned int idx = ci - si->cluster_info;
>
> IIRC, we have reached consensus that we will add a helper for this
> pattern.
Yes, sorry about that. When I drop the V2 fixup branch, I forget to update that.
>
> > - while (!cluster_list_empty(&si->discard_clusters)) {
> > - idx = cluster_list_del_first(&si->discard_clusters, info);
> > + while (!list_empty(&si->discard_clusters)) {
> > + ci = list_first_entry(&si->discard_clusters, struct swap_cluster_info, list);
> > + list_del(&ci->list);
> > + idx = ci - si->cluster_info;
> > spin_unlock(&si->lock);
> >
> > discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
> > SWAPFILE_CLUSTER);
> >
> > spin_lock(&si->lock);
> > - ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
> > - __free_cluster(si, idx);
> > +
> > + spin_lock(&ci->lock);
>
> If you really don't like lock_cluster(), please replace unlock_cluster()
> below with spin_unlock() too.
>
Done. Switch to spin_unlock().
> > + __free_cluster(si, ci);
> > memset(si->swap_map + idx * SWAPFILE_CLUSTER,
> > 0, SWAPFILE_CLUSTER);
> > unlock_cluster(ci);
> > @@ -521,20 +412,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
> > complete(&si->comp);
> > }
> >
> > -static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> > +static struct swap_cluster_info *alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> > {
> > - struct swap_cluster_info *ci = si->cluster_info;
> > + struct swap_cluster_info *ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> >
> > - VM_BUG_ON(cluster_list_first(&si->free_clusters) != idx);
> > - cluster_list_del_first(&si->free_clusters, ci);
> > - cluster_set_count_flag(ci + idx, 0, 0);
> > + VM_BUG_ON(ci - si->cluster_info != idx);
> > + list_del(&ci->list);
> > + ci->count = 0;
> > + ci->flags = 0;
> > + return ci;
> > }
> >
> > -static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> > +static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
> > {
> > - struct swap_cluster_info *ci = si->cluster_info + idx;
> > -
> > - VM_BUG_ON(cluster_count(ci) != 0);
> > + VM_BUG_ON(ci->count != 0);
> > /*
> > * If the swap is discardable, prepare discard the cluster
> > * instead of free it immediately. The cluster will be freed
> > @@ -542,11 +433,11 @@ static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> > */
> > if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
> > (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
> > - swap_cluster_schedule_discard(si, idx);
> > + swap_cluster_schedule_discard(si, ci);
> > return;
> > }
> >
> > - __free_cluster(si, idx);
> > + __free_cluster(si, ci);
> > }
> >
> > /*
> > @@ -559,15 +450,15 @@ static void add_cluster_info_page(struct swap_info_struct *p,
> > unsigned long count)
> > {
> > unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> > + struct swap_cluster_info *ci = cluster_info + idx;
> >
> > if (!cluster_info)
> > return;
> > - if (cluster_is_free(&cluster_info[idx]))
> > + if (cluster_is_free(ci))
> > alloc_cluster(p, idx);
> >
> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) + count > SWAPFILE_CLUSTER);
> > - cluster_set_count(&cluster_info[idx],
> > - cluster_count(&cluster_info[idx]) + count);
> > + VM_BUG_ON(ci->count + count > SWAPFILE_CLUSTER);
> > + ci->count += count;
> > }
> >
> > /*
> > @@ -581,24 +472,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
> > }
> >
> > /*
> > - * The cluster corresponding to page_nr decreases one usage. If the usage
> > - * counter becomes 0, which means no page in the cluster is in using, we can
> > - * optionally discard the cluster and add it to free cluster list.
> > + * The cluster ci decreases one usage. If the usage counter becomes 0,
> > + * which means no page in the cluster is in using, we can optionally discard
> > + * the cluster and add it to free cluster list.
> > */
> > -static void dec_cluster_info_page(struct swap_info_struct *p,
> > - struct swap_cluster_info *cluster_info, unsigned long page_nr)
> > +static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluster_info *ci)
> > {
> > - unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> > -
> > - if (!cluster_info)
> > + if (!p->cluster_info)
> > return;
> >
> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
> > - cluster_set_count(&cluster_info[idx],
> > - cluster_count(&cluster_info[idx]) - 1);
> > + VM_BUG_ON(ci->count == 0);
> > + ci->count--;
> >
> > - if (cluster_count(&cluster_info[idx]) == 0)
> > - free_cluster(p, idx);
> > + if (!ci->count)
> > + free_cluster(p, ci);
> > }
> >
> > /*
> > @@ -611,10 +498,10 @@ scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
> > {
> > struct percpu_cluster *percpu_cluster;
> > bool conflict;
> > -
> > + struct swap_cluster_info *first = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> > offset /= SWAPFILE_CLUSTER;
> > - conflict = !cluster_list_empty(&si->free_clusters) &&
> > - offset != cluster_list_first(&si->free_clusters) &&
> > + conflict = !list_empty(&si->free_clusters) &&
> > + offset != first - si->cluster_info &&
> > cluster_is_free(&si->cluster_info[offset]);
> >
> > if (!conflict)
> > @@ -655,10 +542,14 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
> > cluster = this_cpu_ptr(si->percpu_cluster);
> > tmp = cluster->next[order];
> > if (tmp == SWAP_NEXT_INVALID) {
> > - if (!cluster_list_empty(&si->free_clusters)) {
> > - tmp = cluster_next(&si->free_clusters.head) *
> > - SWAPFILE_CLUSTER;
> > - } else if (!cluster_list_empty(&si->discard_clusters)) {
> > + if (!list_empty(&si->free_clusters)) {
> > + ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> > + list_del(&ci->list);
>
> IIRC, we shouldn't delete the cluster from the free list here, because
> we will delete it later in alloc_cluster().
>
> > + spin_lock(&ci->lock);
> > + ci->flags = 0;
>
> And also shouldn't set ci->flags here too. Because the cluster may be
> kept in free list if scan_swap_map_ssd_cluster_conflict() returns true.
If we both delete the cluster from the free list and clear the flag
here. alloc_cluster() will not see this cluster because the flags have
been cleared.
Will that work?
Chris
>
> > + spin_unlock(&ci->lock);
> > + tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
> > + } else if (!list_empty(&si->discard_clusters)) {
> > /*
> > * we don't have free cluster but have some clusters in
> > * discarding, do discard now and reclaim them, then
>
> [snip]
>
> --
> Best Regards,
> Huang, Ying
>
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 1/2] mm: swap: swap cluster switch to double link list
2024-06-21 18:55 ` Chris Li
@ 2024-06-24 10:16 ` Huang, Ying
2024-06-24 15:52 ` Chris Li
0 siblings, 1 reply; 16+ messages in thread
From: Huang, Ying @ 2024-06-24 10:16 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> On Thu, Jun 20, 2024 at 8:01 PM Huang, Ying <ying.huang@intel.com> wrote:
>>
>> Chris Li <chrisl@kernel.org> writes:
>>
>> > Previously, the swap cluster used a cluster index as a pointer
>> > to construct a custom single link list type "swap_cluster_list".
>> > The next cluster pointer is shared with the cluster->count.
>> > It prevents puting the non free cluster into a list.
>> >
>> > Change the cluster to use the standard double link list instead.
>> > This allows tracing the nonfull cluster in the follow up patch.
>> > That way, it is faster to get to the nonfull cluster of that order.
>> >
>> > Remove the cluster getter/setter for accessing the cluster
>> > struct member.
>> >
>> > The list operation is protected by the swap_info_struct->lock.
>> >
>> > Change cluster code to use "struct swap_cluster_info *" to
>> > reference the cluster rather than by using index. That is more
>> > consistent with the list manipulation. It avoids the repeat
>> > adding index to the cluser_info. The code is easier to understand.
>> >
>> > Remove the cluster next pointer is NULL flag, the double link
>> > list can handle the empty list pretty well.
>> >
>> > The "swap_cluster_info" struct is two pointer bigger, because
>> > 512 swap entries share one swap struct, it has very little impact
>> > on the average memory usage per swap entry. For 1TB swapfile, the
>> > swap cluster data structure increases from 8MB to 24MB.
>> >
>> > Other than the list conversion, there is no real function change
>> > in this patch.
>> >
>> > Signed-off-by: Chris Li <chrisl@kernel.org>
>> > ---
>> > include/linux/swap.h | 26 +++---
>> > mm/swapfile.c | 227 ++++++++++++++-------------------------------------
>> > 2 files changed, 70 insertions(+), 183 deletions(-)
>> >
>> > diff --git a/include/linux/swap.h b/include/linux/swap.h
>> > index 3df75d62a835..690a04f06674 100644
>> > --- a/include/linux/swap.h
>> > +++ b/include/linux/swap.h
>> > @@ -243,22 +243,21 @@ enum {
>> > * free clusters are organized into a list. We fetch an entry from the list to
>> > * get a free cluster.
>> > *
>> > - * The data field stores next cluster if the cluster is free or cluster usage
>> > - * counter otherwise. The flags field determines if a cluster is free. This is
>> > - * protected by swap_info_struct.lock.
>> > + * The flags field determines if a cluster is free. This is
>> > + * protected by cluster lock.
>> > */
>> > struct swap_cluster_info {
>> > spinlock_t lock; /*
>> > * Protect swap_cluster_info fields
>> > - * and swap_info_struct->swap_map
>> > - * elements correspond to the swap
>> > - * cluster
>> > + * other than list, and swap_info_struct->swap_map
>> > + * elements correspond to the swap cluster.
>> > */
>> > - unsigned int data:24;
>> > - unsigned int flags:8;
>> > + u16 count;
>> > + u8 flags;
>> > + struct list_head list;
>> > };
>> > #define CLUSTER_FLAG_FREE 1 /* This cluster is free */
>> > -#define CLUSTER_FLAG_NEXT_NULL 2 /* This cluster has no next cluster */
>> > +
>> >
>> > /*
>> > * The first page in the swap file is the swap header, which is always marked
>> > @@ -283,11 +282,6 @@ struct percpu_cluster {
>> > unsigned int next[SWAP_NR_ORDERS]; /* Likely next allocation offset */
>> > };
>> >
>> > -struct swap_cluster_list {
>> > - struct swap_cluster_info head;
>> > - struct swap_cluster_info tail;
>> > -};
>> > -
>> > /*
>> > * The in-memory structure used to track swap areas.
>> > */
>> > @@ -300,7 +294,7 @@ struct swap_info_struct {
>> > unsigned int max; /* extent of the swap_map */
>> > unsigned char *swap_map; /* vmalloc'ed array of usage counts */
>> > struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
>> > - struct swap_cluster_list free_clusters; /* free clusters list */
>> > + struct list_head free_clusters; /* free clusters list */
>> > unsigned int lowest_bit; /* index of first free in swap_map */
>> > unsigned int highest_bit; /* index of last free in swap_map */
>> > unsigned int pages; /* total of usable pages of swap */
>> > @@ -331,7 +325,7 @@ struct swap_info_struct {
>> > * list.
>> > */
>> > struct work_struct discard_work; /* discard worker */
>> > - struct swap_cluster_list discard_clusters; /* discard clusters list */
>> > + struct list_head discard_clusters; /* discard clusters list */
>> > struct plist_node avail_lists[]; /*
>> > * entries in swap_avail_heads, one
>> > * entry per node.
>> > diff --git a/mm/swapfile.c b/mm/swapfile.c
>> > index 9c6d8e557c0f..0b11c437f9cc 100644
>> > --- a/mm/swapfile.c
>> > +++ b/mm/swapfile.c
>> > @@ -290,64 +290,11 @@ static void discard_swap_cluster(struct swap_info_struct *si,
>> > #endif
>> > #define LATENCY_LIMIT 256
>> >
>> > -static inline void cluster_set_flag(struct swap_cluster_info *info,
>> > - unsigned int flag)
>> > -{
>> > - info->flags = flag;
>> > -}
>> > -
>> > -static inline unsigned int cluster_count(struct swap_cluster_info *info)
>> > -{
>> > - return info->data;
>> > -}
>> > -
>> > -static inline void cluster_set_count(struct swap_cluster_info *info,
>> > - unsigned int c)
>> > -{
>> > - info->data = c;
>> > -}
>> > -
>> > -static inline void cluster_set_count_flag(struct swap_cluster_info *info,
>> > - unsigned int c, unsigned int f)
>> > -{
>> > - info->flags = f;
>> > - info->data = c;
>> > -}
>> > -
>> > -static inline unsigned int cluster_next(struct swap_cluster_info *info)
>> > -{
>> > - return info->data;
>> > -}
>> > -
>> > -static inline void cluster_set_next(struct swap_cluster_info *info,
>> > - unsigned int n)
>> > -{
>> > - info->data = n;
>> > -}
>> > -
>> > -static inline void cluster_set_next_flag(struct swap_cluster_info *info,
>> > - unsigned int n, unsigned int f)
>> > -{
>> > - info->flags = f;
>> > - info->data = n;
>> > -}
>> > -
>> > static inline bool cluster_is_free(struct swap_cluster_info *info)
>> > {
>> > return info->flags & CLUSTER_FLAG_FREE;
>> > }
>> >
>> > -static inline bool cluster_is_null(struct swap_cluster_info *info)
>> > -{
>> > - return info->flags & CLUSTER_FLAG_NEXT_NULL;
>> > -}
>> > -
>> > -static inline void cluster_set_null(struct swap_cluster_info *info)
>> > -{
>> > - info->flags = CLUSTER_FLAG_NEXT_NULL;
>> > - info->data = 0;
>> > -}
>> > -
>> > static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
>> > unsigned long offset)
>> > {
>> > @@ -394,65 +341,11 @@ static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
>> > spin_unlock(&si->lock);
>> > }
>> >
>> > -static inline bool cluster_list_empty(struct swap_cluster_list *list)
>> > -{
>> > - return cluster_is_null(&list->head);
>> > -}
>> > -
>> > -static inline unsigned int cluster_list_first(struct swap_cluster_list *list)
>> > -{
>> > - return cluster_next(&list->head);
>> > -}
>> > -
>> > -static void cluster_list_init(struct swap_cluster_list *list)
>> > -{
>> > - cluster_set_null(&list->head);
>> > - cluster_set_null(&list->tail);
>> > -}
>> > -
>> > -static void cluster_list_add_tail(struct swap_cluster_list *list,
>> > - struct swap_cluster_info *ci,
>> > - unsigned int idx)
>> > -{
>> > - if (cluster_list_empty(list)) {
>> > - cluster_set_next_flag(&list->head, idx, 0);
>> > - cluster_set_next_flag(&list->tail, idx, 0);
>> > - } else {
>> > - struct swap_cluster_info *ci_tail;
>> > - unsigned int tail = cluster_next(&list->tail);
>> > -
>> > - /*
>> > - * Nested cluster lock, but both cluster locks are
>> > - * only acquired when we held swap_info_struct->lock
>> > - */
>> > - ci_tail = ci + tail;
>> > - spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);
>> > - cluster_set_next(ci_tail, idx);
>> > - spin_unlock(&ci_tail->lock);
>> > - cluster_set_next_flag(&list->tail, idx, 0);
>> > - }
>> > -}
>> > -
>> > -static unsigned int cluster_list_del_first(struct swap_cluster_list *list,
>> > - struct swap_cluster_info *ci)
>> > -{
>> > - unsigned int idx;
>> > -
>> > - idx = cluster_next(&list->head);
>> > - if (cluster_next(&list->tail) == idx) {
>> > - cluster_set_null(&list->head);
>> > - cluster_set_null(&list->tail);
>> > - } else
>> > - cluster_set_next_flag(&list->head,
>> > - cluster_next(&ci[idx]), 0);
>> > -
>> > - return idx;
>> > -}
>> > -
>> > /* Add a cluster to discard list and schedule it to do discard */
>> > static void swap_cluster_schedule_discard(struct swap_info_struct *si,
>> > - unsigned int idx)
>> > + struct swap_cluster_info *ci)
>> > {
>> > + unsigned int idx = ci - si->cluster_info;
>>
>> IIRC, we have reached consensus that we will add a helper for this
>> pattern.
>
> Yes, sorry about that. When I drop the V2 fixup branch, I forget to update that.
>
>
>>
>> > - while (!cluster_list_empty(&si->discard_clusters)) {
>> > - idx = cluster_list_del_first(&si->discard_clusters, info);
>> > + while (!list_empty(&si->discard_clusters)) {
>> > + ci = list_first_entry(&si->discard_clusters, struct swap_cluster_info, list);
>> > + list_del(&ci->list);
>> > + idx = ci - si->cluster_info;
>> > spin_unlock(&si->lock);
>> >
>> > discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
>> > SWAPFILE_CLUSTER);
>> >
>> > spin_lock(&si->lock);
>> > - ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
>> > - __free_cluster(si, idx);
>> > +
>> > + spin_lock(&ci->lock);
>>
>> If you really don't like lock_cluster(), please replace unlock_cluster()
>> below with spin_unlock() too.
>>
>
> Done. Switch to spin_unlock().
>
>
>
>> > + __free_cluster(si, ci);
>> > memset(si->swap_map + idx * SWAPFILE_CLUSTER,
>> > 0, SWAPFILE_CLUSTER);
>> > unlock_cluster(ci);
>> > @@ -521,20 +412,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
>> > complete(&si->comp);
>> > }
>> >
>> > -static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
>> > +static struct swap_cluster_info *alloc_cluster(struct swap_info_struct *si, unsigned long idx)
>> > {
>> > - struct swap_cluster_info *ci = si->cluster_info;
>> > + struct swap_cluster_info *ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
>> >
>> > - VM_BUG_ON(cluster_list_first(&si->free_clusters) != idx);
>> > - cluster_list_del_first(&si->free_clusters, ci);
>> > - cluster_set_count_flag(ci + idx, 0, 0);
>> > + VM_BUG_ON(ci - si->cluster_info != idx);
>> > + list_del(&ci->list);
>> > + ci->count = 0;
>> > + ci->flags = 0;
>> > + return ci;
>> > }
>> >
>> > -static void free_cluster(struct swap_info_struct *si, unsigned long idx)
>> > +static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
>> > {
>> > - struct swap_cluster_info *ci = si->cluster_info + idx;
>> > -
>> > - VM_BUG_ON(cluster_count(ci) != 0);
>> > + VM_BUG_ON(ci->count != 0);
>> > /*
>> > * If the swap is discardable, prepare discard the cluster
>> > * instead of free it immediately. The cluster will be freed
>> > @@ -542,11 +433,11 @@ static void free_cluster(struct swap_info_struct *si, unsigned long idx)
>> > */
>> > if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
>> > (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
>> > - swap_cluster_schedule_discard(si, idx);
>> > + swap_cluster_schedule_discard(si, ci);
>> > return;
>> > }
>> >
>> > - __free_cluster(si, idx);
>> > + __free_cluster(si, ci);
>> > }
>> >
>> > /*
>> > @@ -559,15 +450,15 @@ static void add_cluster_info_page(struct swap_info_struct *p,
>> > unsigned long count)
>> > {
>> > unsigned long idx = page_nr / SWAPFILE_CLUSTER;
>> > + struct swap_cluster_info *ci = cluster_info + idx;
>> >
>> > if (!cluster_info)
>> > return;
>> > - if (cluster_is_free(&cluster_info[idx]))
>> > + if (cluster_is_free(ci))
>> > alloc_cluster(p, idx);
>> >
>> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) + count > SWAPFILE_CLUSTER);
>> > - cluster_set_count(&cluster_info[idx],
>> > - cluster_count(&cluster_info[idx]) + count);
>> > + VM_BUG_ON(ci->count + count > SWAPFILE_CLUSTER);
>> > + ci->count += count;
>> > }
>> >
>> > /*
>> > @@ -581,24 +472,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
>> > }
>> >
>> > /*
>> > - * The cluster corresponding to page_nr decreases one usage. If the usage
>> > - * counter becomes 0, which means no page in the cluster is in using, we can
>> > - * optionally discard the cluster and add it to free cluster list.
>> > + * The cluster ci decreases one usage. If the usage counter becomes 0,
>> > + * which means no page in the cluster is in using, we can optionally discard
>> > + * the cluster and add it to free cluster list.
>> > */
>> > -static void dec_cluster_info_page(struct swap_info_struct *p,
>> > - struct swap_cluster_info *cluster_info, unsigned long page_nr)
>> > +static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluster_info *ci)
>> > {
>> > - unsigned long idx = page_nr / SWAPFILE_CLUSTER;
>> > -
>> > - if (!cluster_info)
>> > + if (!p->cluster_info)
>> > return;
>> >
>> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
>> > - cluster_set_count(&cluster_info[idx],
>> > - cluster_count(&cluster_info[idx]) - 1);
>> > + VM_BUG_ON(ci->count == 0);
>> > + ci->count--;
>> >
>> > - if (cluster_count(&cluster_info[idx]) == 0)
>> > - free_cluster(p, idx);
>> > + if (!ci->count)
>> > + free_cluster(p, ci);
>> > }
>> >
>> > /*
>> > @@ -611,10 +498,10 @@ scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
>> > {
>> > struct percpu_cluster *percpu_cluster;
>> > bool conflict;
>> > -
>> > + struct swap_cluster_info *first = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
>> > offset /= SWAPFILE_CLUSTER;
>> > - conflict = !cluster_list_empty(&si->free_clusters) &&
>> > - offset != cluster_list_first(&si->free_clusters) &&
>> > + conflict = !list_empty(&si->free_clusters) &&
>> > + offset != first - si->cluster_info &&
>> > cluster_is_free(&si->cluster_info[offset]);
>> >
>> > if (!conflict)
>> > @@ -655,10 +542,14 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
>> > cluster = this_cpu_ptr(si->percpu_cluster);
>> > tmp = cluster->next[order];
>> > if (tmp == SWAP_NEXT_INVALID) {
>> > - if (!cluster_list_empty(&si->free_clusters)) {
>> > - tmp = cluster_next(&si->free_clusters.head) *
>> > - SWAPFILE_CLUSTER;
>> > - } else if (!cluster_list_empty(&si->discard_clusters)) {
>> > + if (!list_empty(&si->free_clusters)) {
>> > + ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
>> > + list_del(&ci->list);
>>
>> IIRC, we shouldn't delete the cluster from the free list here, because
>> we will delete it later in alloc_cluster().
>>
>> > + spin_lock(&ci->lock);
>> > + ci->flags = 0;
>>
>> And also shouldn't set ci->flags here too. Because the cluster may be
>> kept in free list if scan_swap_map_ssd_cluster_conflict() returns true.
>
> If we both delete the cluster from the free list and clear the flag
> here. alloc_cluster() will not see this cluster because the flags have
> been cleared.
> Will that work?
You are right. This works.
However, I think that it's better to change as less as possible except
converting cluster list implementation. If we don't delete the cluster
from the free cluster list here and leave it to alloc_cluster(), does it
work? If so, we can make the patch smaller and focused. If necessary,
we can make the change in the later patch of the series.
>
>>
>> > + spin_unlock(&ci->lock);
>> > + tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
>> > + } else if (!list_empty(&si->discard_clusters)) {
>> > /*
>> > * we don't have free cluster but have some clusters in
>> > * discarding, do discard now and reclaim them, then
>>
>> [snip]
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 1/2] mm: swap: swap cluster switch to double link list
2024-06-24 10:16 ` Huang, Ying
@ 2024-06-24 15:52 ` Chris Li
0 siblings, 0 replies; 16+ messages in thread
From: Chris Li @ 2024-06-24 15:52 UTC (permalink / raw)
To: Huang, Ying
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
On Mon, Jun 24, 2024 at 3:18 AM Huang, Ying <ying.huang@intel.com> wrote:
>
> Chris Li <chrisl@kernel.org> writes:
>
> > On Thu, Jun 20, 2024 at 8:01 PM Huang, Ying <ying.huang@intel.com> wrote:
> >>
> >> Chris Li <chrisl@kernel.org> writes:
> >>
> >> > Previously, the swap cluster used a cluster index as a pointer
> >> > to construct a custom single link list type "swap_cluster_list".
> >> > The next cluster pointer is shared with the cluster->count.
> >> > It prevents puting the non free cluster into a list.
> >> >
> >> > Change the cluster to use the standard double link list instead.
> >> > This allows tracing the nonfull cluster in the follow up patch.
> >> > That way, it is faster to get to the nonfull cluster of that order.
> >> >
> >> > Remove the cluster getter/setter for accessing the cluster
> >> > struct member.
> >> >
> >> > The list operation is protected by the swap_info_struct->lock.
> >> >
> >> > Change cluster code to use "struct swap_cluster_info *" to
> >> > reference the cluster rather than by using index. That is more
> >> > consistent with the list manipulation. It avoids the repeat
> >> > adding index to the cluser_info. The code is easier to understand.
> >> >
> >> > Remove the cluster next pointer is NULL flag, the double link
> >> > list can handle the empty list pretty well.
> >> >
> >> > The "swap_cluster_info" struct is two pointer bigger, because
> >> > 512 swap entries share one swap struct, it has very little impact
> >> > on the average memory usage per swap entry. For 1TB swapfile, the
> >> > swap cluster data structure increases from 8MB to 24MB.
> >> >
> >> > Other than the list conversion, there is no real function change
> >> > in this patch.
> >> >
> >> > Signed-off-by: Chris Li <chrisl@kernel.org>
> >> > ---
> >> > include/linux/swap.h | 26 +++---
> >> > mm/swapfile.c | 227 ++++++++++++++-------------------------------------
> >> > 2 files changed, 70 insertions(+), 183 deletions(-)
> >> >
> >> > diff --git a/include/linux/swap.h b/include/linux/swap.h
> >> > index 3df75d62a835..690a04f06674 100644
> >> > --- a/include/linux/swap.h
> >> > +++ b/include/linux/swap.h
> >> > @@ -243,22 +243,21 @@ enum {
> >> > * free clusters are organized into a list. We fetch an entry from the list to
> >> > * get a free cluster.
> >> > *
> >> > - * The data field stores next cluster if the cluster is free or cluster usage
> >> > - * counter otherwise. The flags field determines if a cluster is free. This is
> >> > - * protected by swap_info_struct.lock.
> >> > + * The flags field determines if a cluster is free. This is
> >> > + * protected by cluster lock.
> >> > */
> >> > struct swap_cluster_info {
> >> > spinlock_t lock; /*
> >> > * Protect swap_cluster_info fields
> >> > - * and swap_info_struct->swap_map
> >> > - * elements correspond to the swap
> >> > - * cluster
> >> > + * other than list, and swap_info_struct->swap_map
> >> > + * elements correspond to the swap cluster.
> >> > */
> >> > - unsigned int data:24;
> >> > - unsigned int flags:8;
> >> > + u16 count;
> >> > + u8 flags;
> >> > + struct list_head list;
> >> > };
> >> > #define CLUSTER_FLAG_FREE 1 /* This cluster is free */
> >> > -#define CLUSTER_FLAG_NEXT_NULL 2 /* This cluster has no next cluster */
> >> > +
> >> >
> >> > /*
> >> > * The first page in the swap file is the swap header, which is always marked
> >> > @@ -283,11 +282,6 @@ struct percpu_cluster {
> >> > unsigned int next[SWAP_NR_ORDERS]; /* Likely next allocation offset */
> >> > };
> >> >
> >> > -struct swap_cluster_list {
> >> > - struct swap_cluster_info head;
> >> > - struct swap_cluster_info tail;
> >> > -};
> >> > -
> >> > /*
> >> > * The in-memory structure used to track swap areas.
> >> > */
> >> > @@ -300,7 +294,7 @@ struct swap_info_struct {
> >> > unsigned int max; /* extent of the swap_map */
> >> > unsigned char *swap_map; /* vmalloc'ed array of usage counts */
> >> > struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
> >> > - struct swap_cluster_list free_clusters; /* free clusters list */
> >> > + struct list_head free_clusters; /* free clusters list */
> >> > unsigned int lowest_bit; /* index of first free in swap_map */
> >> > unsigned int highest_bit; /* index of last free in swap_map */
> >> > unsigned int pages; /* total of usable pages of swap */
> >> > @@ -331,7 +325,7 @@ struct swap_info_struct {
> >> > * list.
> >> > */
> >> > struct work_struct discard_work; /* discard worker */
> >> > - struct swap_cluster_list discard_clusters; /* discard clusters list */
> >> > + struct list_head discard_clusters; /* discard clusters list */
> >> > struct plist_node avail_lists[]; /*
> >> > * entries in swap_avail_heads, one
> >> > * entry per node.
> >> > diff --git a/mm/swapfile.c b/mm/swapfile.c
> >> > index 9c6d8e557c0f..0b11c437f9cc 100644
> >> > --- a/mm/swapfile.c
> >> > +++ b/mm/swapfile.c
> >> > @@ -290,64 +290,11 @@ static void discard_swap_cluster(struct swap_info_struct *si,
> >> > #endif
> >> > #define LATENCY_LIMIT 256
> >> >
> >> > -static inline void cluster_set_flag(struct swap_cluster_info *info,
> >> > - unsigned int flag)
> >> > -{
> >> > - info->flags = flag;
> >> > -}
> >> > -
> >> > -static inline unsigned int cluster_count(struct swap_cluster_info *info)
> >> > -{
> >> > - return info->data;
> >> > -}
> >> > -
> >> > -static inline void cluster_set_count(struct swap_cluster_info *info,
> >> > - unsigned int c)
> >> > -{
> >> > - info->data = c;
> >> > -}
> >> > -
> >> > -static inline void cluster_set_count_flag(struct swap_cluster_info *info,
> >> > - unsigned int c, unsigned int f)
> >> > -{
> >> > - info->flags = f;
> >> > - info->data = c;
> >> > -}
> >> > -
> >> > -static inline unsigned int cluster_next(struct swap_cluster_info *info)
> >> > -{
> >> > - return info->data;
> >> > -}
> >> > -
> >> > -static inline void cluster_set_next(struct swap_cluster_info *info,
> >> > - unsigned int n)
> >> > -{
> >> > - info->data = n;
> >> > -}
> >> > -
> >> > -static inline void cluster_set_next_flag(struct swap_cluster_info *info,
> >> > - unsigned int n, unsigned int f)
> >> > -{
> >> > - info->flags = f;
> >> > - info->data = n;
> >> > -}
> >> > -
> >> > static inline bool cluster_is_free(struct swap_cluster_info *info)
> >> > {
> >> > return info->flags & CLUSTER_FLAG_FREE;
> >> > }
> >> >
> >> > -static inline bool cluster_is_null(struct swap_cluster_info *info)
> >> > -{
> >> > - return info->flags & CLUSTER_FLAG_NEXT_NULL;
> >> > -}
> >> > -
> >> > -static inline void cluster_set_null(struct swap_cluster_info *info)
> >> > -{
> >> > - info->flags = CLUSTER_FLAG_NEXT_NULL;
> >> > - info->data = 0;
> >> > -}
> >> > -
> >> > static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
> >> > unsigned long offset)
> >> > {
> >> > @@ -394,65 +341,11 @@ static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
> >> > spin_unlock(&si->lock);
> >> > }
> >> >
> >> > -static inline bool cluster_list_empty(struct swap_cluster_list *list)
> >> > -{
> >> > - return cluster_is_null(&list->head);
> >> > -}
> >> > -
> >> > -static inline unsigned int cluster_list_first(struct swap_cluster_list *list)
> >> > -{
> >> > - return cluster_next(&list->head);
> >> > -}
> >> > -
> >> > -static void cluster_list_init(struct swap_cluster_list *list)
> >> > -{
> >> > - cluster_set_null(&list->head);
> >> > - cluster_set_null(&list->tail);
> >> > -}
> >> > -
> >> > -static void cluster_list_add_tail(struct swap_cluster_list *list,
> >> > - struct swap_cluster_info *ci,
> >> > - unsigned int idx)
> >> > -{
> >> > - if (cluster_list_empty(list)) {
> >> > - cluster_set_next_flag(&list->head, idx, 0);
> >> > - cluster_set_next_flag(&list->tail, idx, 0);
> >> > - } else {
> >> > - struct swap_cluster_info *ci_tail;
> >> > - unsigned int tail = cluster_next(&list->tail);
> >> > -
> >> > - /*
> >> > - * Nested cluster lock, but both cluster locks are
> >> > - * only acquired when we held swap_info_struct->lock
> >> > - */
> >> > - ci_tail = ci + tail;
> >> > - spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);
> >> > - cluster_set_next(ci_tail, idx);
> >> > - spin_unlock(&ci_tail->lock);
> >> > - cluster_set_next_flag(&list->tail, idx, 0);
> >> > - }
> >> > -}
> >> > -
> >> > -static unsigned int cluster_list_del_first(struct swap_cluster_list *list,
> >> > - struct swap_cluster_info *ci)
> >> > -{
> >> > - unsigned int idx;
> >> > -
> >> > - idx = cluster_next(&list->head);
> >> > - if (cluster_next(&list->tail) == idx) {
> >> > - cluster_set_null(&list->head);
> >> > - cluster_set_null(&list->tail);
> >> > - } else
> >> > - cluster_set_next_flag(&list->head,
> >> > - cluster_next(&ci[idx]), 0);
> >> > -
> >> > - return idx;
> >> > -}
> >> > -
> >> > /* Add a cluster to discard list and schedule it to do discard */
> >> > static void swap_cluster_schedule_discard(struct swap_info_struct *si,
> >> > - unsigned int idx)
> >> > + struct swap_cluster_info *ci)
> >> > {
> >> > + unsigned int idx = ci - si->cluster_info;
> >>
> >> IIRC, we have reached consensus that we will add a helper for this
> >> pattern.
> >
> > Yes, sorry about that. When I drop the V2 fixup branch, I forget to update that.
> >
> >
> >>
> >> > - while (!cluster_list_empty(&si->discard_clusters)) {
> >> > - idx = cluster_list_del_first(&si->discard_clusters, info);
> >> > + while (!list_empty(&si->discard_clusters)) {
> >> > + ci = list_first_entry(&si->discard_clusters, struct swap_cluster_info, list);
> >> > + list_del(&ci->list);
> >> > + idx = ci - si->cluster_info;
> >> > spin_unlock(&si->lock);
> >> >
> >> > discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
> >> > SWAPFILE_CLUSTER);
> >> >
> >> > spin_lock(&si->lock);
> >> > - ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
> >> > - __free_cluster(si, idx);
> >> > +
> >> > + spin_lock(&ci->lock);
> >>
> >> If you really don't like lock_cluster(), please replace unlock_cluster()
> >> below with spin_unlock() too.
> >>
> >
> > Done. Switch to spin_unlock().
> >
> >
> >
> >> > + __free_cluster(si, ci);
> >> > memset(si->swap_map + idx * SWAPFILE_CLUSTER,
> >> > 0, SWAPFILE_CLUSTER);
> >> > unlock_cluster(ci);
> >> > @@ -521,20 +412,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
> >> > complete(&si->comp);
> >> > }
> >> >
> >> > -static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> >> > +static struct swap_cluster_info *alloc_cluster(struct swap_info_struct *si, unsigned long idx)
> >> > {
> >> > - struct swap_cluster_info *ci = si->cluster_info;
> >> > + struct swap_cluster_info *ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> >> >
> >> > - VM_BUG_ON(cluster_list_first(&si->free_clusters) != idx);
> >> > - cluster_list_del_first(&si->free_clusters, ci);
> >> > - cluster_set_count_flag(ci + idx, 0, 0);
> >> > + VM_BUG_ON(ci - si->cluster_info != idx);
> >> > + list_del(&ci->list);
> >> > + ci->count = 0;
> >> > + ci->flags = 0;
> >> > + return ci;
> >> > }
> >> >
> >> > -static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> >> > +static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
> >> > {
> >> > - struct swap_cluster_info *ci = si->cluster_info + idx;
> >> > -
> >> > - VM_BUG_ON(cluster_count(ci) != 0);
> >> > + VM_BUG_ON(ci->count != 0);
> >> > /*
> >> > * If the swap is discardable, prepare discard the cluster
> >> > * instead of free it immediately. The cluster will be freed
> >> > @@ -542,11 +433,11 @@ static void free_cluster(struct swap_info_struct *si, unsigned long idx)
> >> > */
> >> > if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
> >> > (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
> >> > - swap_cluster_schedule_discard(si, idx);
> >> > + swap_cluster_schedule_discard(si, ci);
> >> > return;
> >> > }
> >> >
> >> > - __free_cluster(si, idx);
> >> > + __free_cluster(si, ci);
> >> > }
> >> >
> >> > /*
> >> > @@ -559,15 +450,15 @@ static void add_cluster_info_page(struct swap_info_struct *p,
> >> > unsigned long count)
> >> > {
> >> > unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> >> > + struct swap_cluster_info *ci = cluster_info + idx;
> >> >
> >> > if (!cluster_info)
> >> > return;
> >> > - if (cluster_is_free(&cluster_info[idx]))
> >> > + if (cluster_is_free(ci))
> >> > alloc_cluster(p, idx);
> >> >
> >> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) + count > SWAPFILE_CLUSTER);
> >> > - cluster_set_count(&cluster_info[idx],
> >> > - cluster_count(&cluster_info[idx]) + count);
> >> > + VM_BUG_ON(ci->count + count > SWAPFILE_CLUSTER);
> >> > + ci->count += count;
> >> > }
> >> >
> >> > /*
> >> > @@ -581,24 +472,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
> >> > }
> >> >
> >> > /*
> >> > - * The cluster corresponding to page_nr decreases one usage. If the usage
> >> > - * counter becomes 0, which means no page in the cluster is in using, we can
> >> > - * optionally discard the cluster and add it to free cluster list.
> >> > + * The cluster ci decreases one usage. If the usage counter becomes 0,
> >> > + * which means no page in the cluster is in using, we can optionally discard
> >> > + * the cluster and add it to free cluster list.
> >> > */
> >> > -static void dec_cluster_info_page(struct swap_info_struct *p,
> >> > - struct swap_cluster_info *cluster_info, unsigned long page_nr)
> >> > +static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluster_info *ci)
> >> > {
> >> > - unsigned long idx = page_nr / SWAPFILE_CLUSTER;
> >> > -
> >> > - if (!cluster_info)
> >> > + if (!p->cluster_info)
> >> > return;
> >> >
> >> > - VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
> >> > - cluster_set_count(&cluster_info[idx],
> >> > - cluster_count(&cluster_info[idx]) - 1);
> >> > + VM_BUG_ON(ci->count == 0);
> >> > + ci->count--;
> >> >
> >> > - if (cluster_count(&cluster_info[idx]) == 0)
> >> > - free_cluster(p, idx);
> >> > + if (!ci->count)
> >> > + free_cluster(p, ci);
> >> > }
> >> >
> >> > /*
> >> > @@ -611,10 +498,10 @@ scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
> >> > {
> >> > struct percpu_cluster *percpu_cluster;
> >> > bool conflict;
> >> > -
> >> > + struct swap_cluster_info *first = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> >> > offset /= SWAPFILE_CLUSTER;
> >> > - conflict = !cluster_list_empty(&si->free_clusters) &&
> >> > - offset != cluster_list_first(&si->free_clusters) &&
> >> > + conflict = !list_empty(&si->free_clusters) &&
> >> > + offset != first - si->cluster_info &&
> >> > cluster_is_free(&si->cluster_info[offset]);
> >> >
> >> > if (!conflict)
> >> > @@ -655,10 +542,14 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
> >> > cluster = this_cpu_ptr(si->percpu_cluster);
> >> > tmp = cluster->next[order];
> >> > if (tmp == SWAP_NEXT_INVALID) {
> >> > - if (!cluster_list_empty(&si->free_clusters)) {
> >> > - tmp = cluster_next(&si->free_clusters.head) *
> >> > - SWAPFILE_CLUSTER;
> >> > - } else if (!cluster_list_empty(&si->discard_clusters)) {
> >> > + if (!list_empty(&si->free_clusters)) {
> >> > + ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
> >> > + list_del(&ci->list);
> >>
> >> IIRC, we shouldn't delete the cluster from the free list here, because
> >> we will delete it later in alloc_cluster().
> >>
> >> > + spin_lock(&ci->lock);
> >> > + ci->flags = 0;
> >>
> >> And also shouldn't set ci->flags here too. Because the cluster may be
> >> kept in free list if scan_swap_map_ssd_cluster_conflict() returns true.
> >
> > If we both delete the cluster from the free list and clear the flag
> > here. alloc_cluster() will not see this cluster because the flags have
> > been cleared.
> > Will that work?
>
> You are right. This works.
Thanks for the confirmation.
> However, I think that it's better to change as less as possible except
> converting cluster list implementation. If we don't delete the cluster
> from the free cluster list here and leave it to alloc_cluster(), does it
> work? If so, we can make the patch smaller and focused. If necessary,
> we can make the change in the later patch of the series.
Agree. I later came to the same conclusion. Let me do just that in the
next version.
Thanks for the review and suggestion.
Chris
^ permalink raw reply [flat|nested] 16+ messages in thread
* [PATCH v3 2/2] mm: swap: mTHP allocate swap entries from nonfull list
2024-06-19 9:20 [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Chris Li
2024-06-19 9:20 ` [PATCH v3 1/2] mm: swap: swap cluster switch to double link list Chris Li
@ 2024-06-19 9:20 ` Chris Li
2024-06-19 9:31 ` [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Ryan Roberts
` (2 subsequent siblings)
4 siblings, 0 replies; 16+ messages in thread
From: Chris Li @ 2024-06-19 9:20 UTC (permalink / raw)
To: Andrew Morton
Cc: Kairui Song, Ryan Roberts, Huang, Ying, Kairui Song,
Kalesh Singh, linux-kernel, linux-mm, Chris Li, Barry Song
Track the nonfull cluster as well as the empty cluster
on lists. Each order has one nonfull cluster list.
The cluster will remember which order it was used during
new cluster allocation.
When the cluster has free entry, add to the nonfull[order]
list. When the free cluster list is empty, also allocate
from the nonempty list of that order.
This improves the mTHP swap allocation success rate.
There are limitations if the distribution of numbers of
different orders of mTHP changes a lot. e.g. there are a lot
of nonfull cluster assign to order A while later time there
are a lot of order B allocation while very little allocation
in order A. Currently the cluster used by order A will not
reused by order B unless the cluster is 100% empty.
Signed-off-by: Chris Li <chrisl@kernel.org>
---
include/linux/swap.h | 4 ++++
mm/swapfile.c | 27 ++++++++++++++++++++++++---
2 files changed, 28 insertions(+), 3 deletions(-)
diff --git a/include/linux/swap.h b/include/linux/swap.h
index 690a04f06674..92613bb4a87b 100644
--- a/include/linux/swap.h
+++ b/include/linux/swap.h
@@ -254,9 +254,11 @@ struct swap_cluster_info {
*/
u16 count;
u8 flags;
+ u8 order;
struct list_head list;
};
#define CLUSTER_FLAG_FREE 1 /* This cluster is free */
+#define CLUSTER_FLAG_NONFULL 2 /* This cluster is on nonfull list */
/*
@@ -295,6 +297,8 @@ struct swap_info_struct {
unsigned char *swap_map; /* vmalloc'ed array of usage counts */
struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
struct list_head free_clusters; /* free clusters list */
+ struct list_head nonfull_clusters[SWAP_NR_ORDERS];
+ /* list of cluster that contains at least one free slot */
unsigned int lowest_bit; /* index of first free in swap_map */
unsigned int highest_bit; /* index of last free in swap_map */
unsigned int pages; /* total of usable pages of swap */
diff --git a/mm/swapfile.c b/mm/swapfile.c
index 0b11c437f9cc..ba6676a4a8ef 100644
--- a/mm/swapfile.c
+++ b/mm/swapfile.c
@@ -361,8 +361,11 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
static void __free_cluster(struct swap_info_struct *si, struct swap_cluster_info *ci)
{
+ if (ci->flags & CLUSTER_FLAG_NONFULL)
+ list_move_tail(&ci->list, &si->free_clusters);
+ else
+ list_add_tail(&ci->list, &si->free_clusters);
ci->flags = CLUSTER_FLAG_FREE;
- list_add_tail(&ci->list, &si->free_clusters);
}
/*
@@ -485,7 +488,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
ci->count--;
if (!ci->count)
- free_cluster(p, ci);
+ return free_cluster(p, ci);
+
+ if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+ list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);
+ ci->flags |= CLUSTER_FLAG_NONFULL;
+ }
}
/*
@@ -542,10 +550,18 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
cluster = this_cpu_ptr(si->percpu_cluster);
tmp = cluster->next[order];
if (tmp == SWAP_NEXT_INVALID) {
- if (!list_empty(&si->free_clusters)) {
+ if (!list_empty(&si->nonfull_clusters[order])) {
+ ci = list_first_entry(&si->nonfull_clusters[order], struct swap_cluster_info, list);
+ list_del(&ci->list);
+ spin_lock(&ci->lock);
+ ci->flags = 0;
+ spin_unlock(&ci->lock);
+ tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
+ } else if (!list_empty(&si->free_clusters)) {
ci = list_first_entry(&si->free_clusters, struct swap_cluster_info, list);
list_del(&ci->list);
spin_lock(&ci->lock);
+ ci->order = order;
ci->flags = 0;
spin_unlock(&ci->lock);
tmp = (ci - si->cluster_info) * SWAPFILE_CLUSTER;
@@ -576,6 +592,7 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
break;
tmp += nr_pages;
}
+ WARN_ONCE(ci->order != order, "expecting order %d got %d", order, ci->order);
unlock_cluster(ci);
}
if (tmp >= max) {
@@ -954,6 +971,7 @@ static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx)
ci = lock_cluster(si, offset);
memset(si->swap_map + offset, 0, SWAPFILE_CLUSTER);
ci->count = 0;
+ ci->order = 0;
ci->flags = 0;
free_cluster(si, ci);
unlock_cluster(ci);
@@ -2898,6 +2916,9 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p,
INIT_LIST_HEAD(&p->free_clusters);
INIT_LIST_HEAD(&p->discard_clusters);
+ for (i = 0; i < SWAP_NR_ORDERS; i++)
+ INIT_LIST_HEAD(&p->nonfull_clusters[i]);
+
for (i = 0; i < swap_header->info.nr_badpages; i++) {
unsigned int page_nr = swap_header->info.badpages[i];
if (page_nr == 0 || page_nr > swap_header->info.last_page)
--
2.45.2.627.g7a2c4fd464-goog
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-19 9:20 [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Chris Li
2024-06-19 9:20 ` [PATCH v3 1/2] mm: swap: swap cluster switch to double link list Chris Li
2024-06-19 9:20 ` [PATCH v3 2/2] mm: swap: mTHP allocate swap entries from nonfull list Chris Li
@ 2024-06-19 9:31 ` Ryan Roberts
2024-06-20 2:30 ` Huang, Ying
2024-06-25 2:43 ` Huang, Ying
4 siblings, 0 replies; 16+ messages in thread
From: Ryan Roberts @ 2024-06-19 9:31 UTC (permalink / raw)
To: Chris Li, Andrew Morton
Cc: Kairui Song, Huang, Ying, Kalesh Singh, linux-kernel, linux-mm,
Barry Song
On 19/06/2024 10:20, Chris Li wrote:
> This is the short term solutiolns "swap cluster order" listed
> in my "Swap Abstraction" discussion slice 8 in the recent
> LSF/MM conference.
>
> When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> orders" is introduced, it only allocates the mTHP swap entries
> from new empty cluster list. It has a fragmentation issue
> reported by Barry.
>
> https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>
> The reason is that all the empty cluster has been exhausted while
> there are planty of free swap entries to in the cluster that is
> not 100% free.
>
> Remember the swap allocation order in the cluster.
> Keep track of the per order non full cluster list for later allocation.
>
> User impact: For users that allocate and free mix order mTHP swapping,
> It greatly improves the success rate of the mTHP swap allocation after the
> initial phase.
>
> Barry provides a test program to show the effect:
> https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
>
> Without:
> $ mthp-swapout
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
> Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
> Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
> Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
>
> $ mthp-swapout -s
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
> Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
> Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>
> With:
> $ mthp-swapout
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> ...
> Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>
> $ mthp-swapout -s
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> ...
> Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
Excellent!
>
> Reported-by: Barry Song <21cnbao@gmail.com>
> Signed-off-by: Chris Li <chrisl@kernel.org>
> ---
> Changes in v3:
> - Using V1 as base.
> - Rename "next" to "list" for the list field, suggested by Ying.
> - Update comment for the locking rules for cluster fields and list,
> suggested by Ying.
> - Allocate from the nonfull list before attempting free list, suggested
> by Kairui.
Sorry I didn't follow this original conversation. But the original intent of
having a per-cpu current cluster was to prevent interleving pages from multiple
processes and therefore optimize IO. See commit ebc2a1a69111 ("swap: make
cluster allocation per-cpu"). I wonder if this change could lead to a swap
performance regression in the common order-0 case?
Thanks,
Ryan
> - Link to v2: https://lore.kernel.org/r/20240614-swap-allocator-v2-0-2a513b4a7f2f@kernel.org
>
> Changes in v2:
> - Abandoned.
> - Link to v1: https://lore.kernel.org/r/20240524-swap-allocator-v1-0-47861b423b26@kernel.org
>
> ---
> Chris Li (2):
> mm: swap: swap cluster switch to double link list
> mm: swap: mTHP allocate swap entries from nonfull list
>
> include/linux/swap.h | 30 +++----
> mm/swapfile.c | 248 +++++++++++++++++----------------------------------
> 2 files changed, 95 insertions(+), 183 deletions(-)
> ---
> base-commit: 19b8422c5bd56fb5e7085995801c6543a98bda1f
> change-id: 20240523-swap-allocator-1534c480ece4
>
> Best regards,
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-19 9:20 [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Chris Li
` (2 preceding siblings ...)
2024-06-19 9:31 ` [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Ryan Roberts
@ 2024-06-20 2:30 ` Huang, Ying
2024-06-21 8:43 ` Chris Li
2024-06-25 2:43 ` Huang, Ying
4 siblings, 1 reply; 16+ messages in thread
From: Huang, Ying @ 2024-06-20 2:30 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> This is the short term solutiolns "swap cluster order" listed
> in my "Swap Abstraction" discussion slice 8 in the recent
> LSF/MM conference.
>
> When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> orders" is introduced, it only allocates the mTHP swap entries
> from new empty cluster list. It has a fragmentation issue
> reported by Barry.
>
> https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>
> The reason is that all the empty cluster has been exhausted while
> there are planty of free swap entries to in the cluster that is
> not 100% free.
>
> Remember the swap allocation order in the cluster.
> Keep track of the per order non full cluster list for later allocation.
>
> User impact: For users that allocate and free mix order mTHP swapping,
> It greatly improves the success rate of the mTHP swap allocation after the
> initial phase.
>
> Barry provides a test program to show the effect:
> https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
>
> Without:
> $ mthp-swapout
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
> Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
> Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
> Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
>
> $ mthp-swapout -s
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
> Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
> Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>
> With:
> $ mthp-swapout
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> ...
> Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>
> $ mthp-swapout -s
> Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> ...
> Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
Unfortunately, the data is gotten using a special designed test program
which always swap-in pages with swapped-out size. I don't know whether
such workloads exist in reality. Otherwise, you need to wait for mTHP
swap-in to be merged firstly, and people reach consensus that we should
always swap-in pages with swapped-out size.
Alternately, we can make some design adjustment to make the patchset
work in current situation (mTHP swap-out, normal page swap-in).
- One non-full cluster list for each order (same as current design)
- When one swap entry is freed, check whether one "order+1" swap entry
becomes free, if so, move the cluster to "order+1" non-full cluster
list.
- When allocate swap entry with "order", get cluster from free, "order",
"order+1", ... non-full cluster list. If all are empty, fallback to
order 0.
Do you think that this works?
> Reported-by: Barry Song <21cnbao@gmail.com>
> Signed-off-by: Chris Li <chrisl@kernel.org>
> ---
> Changes in v3:
> - Using V1 as base.
> - Rename "next" to "list" for the list field, suggested by Ying.
> - Update comment for the locking rules for cluster fields and list,
> suggested by Ying.
> - Allocate from the nonfull list before attempting free list, suggested
> by Kairui.
Haven't looked into this. It appears that this breaks the original
discard behavior which helps performance of some SSD, please refer to
commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
And as pointed out by Ryan, this may reduce the opportunity of the
sequential block device writing during swap-out, which may hurt
performance of SSD too.
[snip]
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-20 2:30 ` Huang, Ying
@ 2024-06-21 8:43 ` Chris Li
2024-06-25 2:34 ` Huang, Ying
0 siblings, 1 reply; 16+ messages in thread
From: Chris Li @ 2024-06-21 8:43 UTC (permalink / raw)
To: Huang, Ying
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
>
> Chris Li <chrisl@kernel.org> writes:
>
> > This is the short term solutiolns "swap cluster order" listed
> > in my "Swap Abstraction" discussion slice 8 in the recent
> > LSF/MM conference.
> >
> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> > orders" is introduced, it only allocates the mTHP swap entries
> > from new empty cluster list. It has a fragmentation issue
> > reported by Barry.
> >
> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
> >
> > The reason is that all the empty cluster has been exhausted while
> > there are planty of free swap entries to in the cluster that is
> > not 100% free.
> >
> > Remember the swap allocation order in the cluster.
> > Keep track of the per order non full cluster list for later allocation.
> >
> > User impact: For users that allocate and free mix order mTHP swapping,
> > It greatly improves the success rate of the mTHP swap allocation after the
> > initial phase.
> >
> > Barry provides a test program to show the effect:
> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
> >
> > Without:
> > $ mthp-swapout
> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
> >
> > $ mthp-swapout -s
> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> >
> > With:
> > $ mthp-swapout
> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> > ...
> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >
> > $ mthp-swapout -s
> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> > ...
> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
>
> Unfortunately, the data is gotten using a special designed test program
> which always swap-in pages with swapped-out size. I don't know whether
> such workloads exist in reality. Otherwise, you need to wait for mTHP
The test program is designed to simulate mTHP swap behavior using
zsmalloc and 64KB buffer.
If we insist on only designing for existing workloads, then zsmalloc
using 64KB buffer usage will never be able to run, exactly due the
kernel has high failure rate allocating swap entries for 64KB. There
is a bit of a chick and egg problem there, such a usage can not exist
because the kernel can't support it yet. Kernel can't add patches to
support it because such simulation tests are not "real".
We need to break this cycle to support something new.
> swap-in to be merged firstly, and people reach consensus that we should
> always swap-in pages with swapped-out size.
We don't have to be always. We can identify the situation that makes
sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
same swap in size makes sense.
I think we have agreement on such zsmalloc 64K usage cases we do want
to support.
>
> Alternately, we can make some design adjustment to make the patchset
> work in current situation (mTHP swap-out, normal page swap-in).
>
> - One non-full cluster list for each order (same as current design)
>
> - When one swap entry is freed, check whether one "order+1" swap entry
> becomes free, if so, move the cluster to "order+1" non-full cluster
> list.
In the intended zsmalloc usage case, there is no order+1 swap entry request.
Moving the cluster to "order+1" will make less cluster available for "order".
For that usage case it is negative gain.
> - When allocate swap entry with "order", get cluster from free, "order",
> "order+1", ... non-full cluster list. If all are empty, fallback to
I don't see that it is useful for the zsmalloc 64K buffer usage case.
There will be order 0 and order 4 and nothing else.
How about let's keep it simple for now. If we identify some workload
this algorithm can help. We can do that as a follow up step.
> order 0.
>
> Do you think that this works?
>
> > Reported-by: Barry Song <21cnbao@gmail.com>
> > Signed-off-by: Chris Li <chrisl@kernel.org>
> > ---
> > Changes in v3:
> > - Using V1 as base.
> > - Rename "next" to "list" for the list field, suggested by Ying.
> > - Update comment for the locking rules for cluster fields and list,
> > suggested by Ying.
> > - Allocate from the nonfull list before attempting free list, suggested
> > by Kairui.
>
> Haven't looked into this. It appears that this breaks the original
> discard behavior which helps performance of some SSD, please refer to
Can you clarify by "discard" you mean SSD discard command or just the
way swap allocator recycles free clusters?
> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
I did read that change log. Help me understand in more detail which
discard behavior you have in mind. A lot of low end micro SD cards
have proper FTL wear leveling now, ssd even better on that.
> And as pointed out by Ryan, this may reduce the opportunity of the
> sequential block device writing during swap-out, which may hurt
> performance of SSD too.
Only at the initial phase. If the swap IO continues, after the first
pass fills up the swap file, the write will be random on the swapfile
anyway. Because the swapfile only issues 2M discards commands when all
512 4K pages are free. The discarded area will be much smaller than
the free area on swapfile. That combined with the random write page on
the whole swap file. It might produce a worse internal write
amplification for SSD, compared to only writing a subset of the
swapfile area. I would love to hear from someone who understands SSD
internals to confirm or deny my theory.
Even let's assume the SSD wants a free block over a nonfull cluster
first. Zswap and zram swap are not subject to SSD property. We might
want to have a kernel option to select using nonfree clusters over
the free one for zram and zswap (ghost swapfile). That will help
contain the fragmented swap area.
Chris
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-21 8:43 ` Chris Li
@ 2024-06-25 2:34 ` Huang, Ying
2024-07-26 6:46 ` Chris Li
0 siblings, 1 reply; 16+ messages in thread
From: Huang, Ying @ 2024-06-25 2:34 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
>>
>> Chris Li <chrisl@kernel.org> writes:
>>
>> > This is the short term solutiolns "swap cluster order" listed
>> > in my "Swap Abstraction" discussion slice 8 in the recent
>> > LSF/MM conference.
>> >
>> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
>> > orders" is introduced, it only allocates the mTHP swap entries
>> > from new empty cluster list. It has a fragmentation issue
>> > reported by Barry.
>> >
>> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>> >
>> > The reason is that all the empty cluster has been exhausted while
>> > there are planty of free swap entries to in the cluster that is
>> > not 100% free.
>> >
>> > Remember the swap allocation order in the cluster.
>> > Keep track of the per order non full cluster list for later allocation.
>> >
>> > User impact: For users that allocate and free mix order mTHP swapping,
>> > It greatly improves the success rate of the mTHP swap allocation after the
>> > initial phase.
>> >
>> > Barry provides a test program to show the effect:
>> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
>> >
>> > Without:
>> > $ mthp-swapout
>> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
>> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
>> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
>> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
>> >
>> > $ mthp-swapout -s
>> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
>> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
>> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> >
>> > With:
>> > $ mthp-swapout
>> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > ...
>> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >
>> > $ mthp-swapout -s
>> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > ...
>> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
>>
>> Unfortunately, the data is gotten using a special designed test program
>> which always swap-in pages with swapped-out size. I don't know whether
>> such workloads exist in reality. Otherwise, you need to wait for mTHP
>
> The test program is designed to simulate mTHP swap behavior using
> zsmalloc and 64KB buffer.
> If we insist on only designing for existing workloads, then zsmalloc
> using 64KB buffer usage will never be able to run, exactly due the
> kernel has high failure rate allocating swap entries for 64KB. There
> is a bit of a chick and egg problem there, such a usage can not exist
> because the kernel can't support it yet. Kernel can't add patches to
> support it because such simulation tests are not "real".
>
> We need to break this cycle to support something new.
>
>> swap-in to be merged firstly, and people reach consensus that we should
>> always swap-in pages with swapped-out size.
>
> We don't have to be always. We can identify the situation that makes
> sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
> same swap in size makes sense.
> I think we have agreement on such zsmalloc 64K usage cases we do want
> to support.
>
>>
>> Alternately, we can make some design adjustment to make the patchset
>> work in current situation (mTHP swap-out, normal page swap-in).
>>
>> - One non-full cluster list for each order (same as current design)
>>
>> - When one swap entry is freed, check whether one "order+1" swap entry
>> becomes free, if so, move the cluster to "order+1" non-full cluster
>> list.
>
> In the intended zsmalloc usage case, there is no order+1 swap entry
> request.
This my main concern about this series. Only the Android use cases are
considered. The general use cases are just ignored. Is it hard to
consider or test a normal swap partition on your development machine?
> Moving the cluster to "order+1" will make less cluster available for "order".
> For that usage case it is negative gain.
The "order+1" cluster can be used to allocate "order" cluster when
existing "order" cluster is used up.
And in this way, we can protect clusters with more free spaces so that
they may become free.
>> - When allocate swap entry with "order", get cluster from free, "order",
>> "order+1", ... non-full cluster list. If all are empty, fallback to
>
> I don't see that it is useful for the zsmalloc 64K buffer usage case.
> There will be order 0 and order 4 and nothing else.
>
> How about let's keep it simple for now. If we identify some workload
> this algorithm can help. We can do that as a follow up step.
The simple design isn't flexible enough for your workloads too. For
example,
- Initially, almost only order-0 pages are swapped out, most non-full
clusters are order-0.
- Later, quite some order-0 swap entries are freed so that there are
quite some order-4 swap entries available.
- Order-4 pages need to be swapped out, but no enough order-4 non-full
clusters available.
So, we need a way to migrate non-full clusters among orders to adjust to
the situations automatically.
>> order 0.
>>
>> Do you think that this works?
>>
>> > Reported-by: Barry Song <21cnbao@gmail.com>
>> > Signed-off-by: Chris Li <chrisl@kernel.org>
>> > ---
>> > Changes in v3:
>> > - Using V1 as base.
>> > - Rename "next" to "list" for the list field, suggested by Ying.
>> > - Update comment for the locking rules for cluster fields and list,
>> > suggested by Ying.
>> > - Allocate from the nonfull list before attempting free list, suggested
>> > by Kairui.
>>
>> Haven't looked into this. It appears that this breaks the original
>> discard behavior which helps performance of some SSD, please refer to
>
> Can you clarify by "discard" you mean SSD discard command or just the
> way swap allocator recycles free clusters?
The SSD discard command, like in the following URL,
https://en.wikipedia.org/wiki/Trim_(computing)
>> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
>
> I did read that change log. Help me understand in more detail which
> discard behavior you have in mind. A lot of low end micro SD cards
> have proper FTL wear leveling now, ssd even better on that.
It's not FTL, it's discard/trim for SSD as above.
>> And as pointed out by Ryan, this may reduce the opportunity of the
>> sequential block device writing during swap-out, which may hurt
>> performance of SSD too.
>
> Only at the initial phase. If the swap IO continues, after the first
> pass fills up the swap file, the write will be random on the swapfile
> anyway. Because the swapfile only issues 2M discards commands when all
> 512 4K pages are free. The discarded area will be much smaller than
> the free area on swapfile. That combined with the random write page on
> the whole swap file. It might produce a worse internal write
> amplification for SSD, compared to only writing a subset of the
> swapfile area. I would love to hear from someone who understands SSD
> internals to confirm or deny my theory.
It depends on workloads. Some workloads will have more severe
fragmentation than others. For example, on quite some machines, the
swap devices will be far from being full to avoid possible OOM.
> Even let's assume the SSD wants a free block over a nonfull cluster
> first. Zswap and zram swap are not subject to SSD property. We might
> want to have a kernel option to select using nonfree clusters over
> the free one for zram and zswap (ghost swapfile). That will help
> contain the fragmented swap area.
I suspect that it will help fragmentation avoidance much. Please prove
its effectiveness with data firstly. It can be a further optimization
patch in the series.
Even if we really need it, we can try to do it without a kernel option.
For example, detect whether we are using zram and enable it for zram
automatically (through a general flag).
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-25 2:34 ` Huang, Ying
@ 2024-07-26 6:46 ` Chris Li
2024-07-26 6:57 ` Huang, Ying
0 siblings, 1 reply; 16+ messages in thread
From: Chris Li @ 2024-07-26 6:46 UTC (permalink / raw)
To: Huang, Ying
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
On Mon, Jun 24, 2024 at 7:36 PM Huang, Ying <ying.huang@intel.com> wrote:
>
> Chris Li <chrisl@kernel.org> writes:
>
> > On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
> >>
> >> Chris Li <chrisl@kernel.org> writes:
> >>
> >> > This is the short term solutiolns "swap cluster order" listed
> >> > in my "Swap Abstraction" discussion slice 8 in the recent
> >> > LSF/MM conference.
> >> >
> >> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> >> > orders" is introduced, it only allocates the mTHP swap entries
> >> > from new empty cluster list. It has a fragmentation issue
> >> > reported by Barry.
> >> >
> >> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
> >> >
> >> > The reason is that all the empty cluster has been exhausted while
> >> > there are planty of free swap entries to in the cluster that is
> >> > not 100% free.
> >> >
> >> > Remember the swap allocation order in the cluster.
> >> > Keep track of the per order non full cluster list for later allocation.
> >> >
> >> > User impact: For users that allocate and free mix order mTHP swapping,
> >> > It greatly improves the success rate of the mTHP swap allocation after the
> >> > initial phase.
> >> >
> >> > Barry provides a test program to show the effect:
> >> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
> >> >
> >> > Without:
> >> > $ mthp-swapout
> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> >> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
> >> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> >> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> >> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
> >> >
> >> > $ mthp-swapout -s
> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> >> >
> >> > With:
> >> > $ mthp-swapout
> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > ...
> >> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >
> >> > $ mthp-swapout -s
> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > ...
> >> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
> >>
> >> Unfortunately, the data is gotten using a special designed test program
> >> which always swap-in pages with swapped-out size. I don't know whether
> >> such workloads exist in reality. Otherwise, you need to wait for mTHP
> >
> > The test program is designed to simulate mTHP swap behavior using
> > zsmalloc and 64KB buffer.
> > If we insist on only designing for existing workloads, then zsmalloc
> > using 64KB buffer usage will never be able to run, exactly due the
> > kernel has high failure rate allocating swap entries for 64KB. There
> > is a bit of a chick and egg problem there, such a usage can not exist
> > because the kernel can't support it yet. Kernel can't add patches to
> > support it because such simulation tests are not "real".
> >
> > We need to break this cycle to support something new.
> >
> >> swap-in to be merged firstly, and people reach consensus that we should
> >> always swap-in pages with swapped-out size.
> >
> > We don't have to be always. We can identify the situation that makes
> > sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
> > same swap in size makes sense.
> > I think we have agreement on such zsmalloc 64K usage cases we do want
> > to support.
> >
> >>
> >> Alternately, we can make some design adjustment to make the patchset
> >> work in current situation (mTHP swap-out, normal page swap-in).
> >>
> >> - One non-full cluster list for each order (same as current design)
> >>
> >> - When one swap entry is freed, check whether one "order+1" swap entry
> >> becomes free, if so, move the cluster to "order+1" non-full cluster
> >> list.
> >
> > In the intended zsmalloc usage case, there is no order+1 swap entry
> > request.
>
> This my main concern about this series. Only the Android use cases are
> considered. The general use cases are just ignored. Is it hard to
> consider or test a normal swap partition on your development machine?
Please see the V4 cover letter. The V4 already has the SSD, zram and
HDD stress testing.
Of course I want to make sure the allocator works well with Barry's
mthp test case as well.
> > Moving the cluster to "order+1" will make less cluster available for "order".
> > For that usage case it is negative gain.
>
> The "order+1" cluster can be used to allocate "order" cluster when
> existing "order" cluster is used up.
>
> And in this way, we can protect clusters with more free spaces so that
> they may become free.
>
> >> - When allocate swap entry with "order", get cluster from free, "order",
> >> "order+1", ... non-full cluster list. If all are empty, fallback to
> >
> > I don't see that it is useful for the zsmalloc 64K buffer usage case.
> > There will be order 0 and order 4 and nothing else.
> >
> > How about let's keep it simple for now. If we identify some workload
> > this algorithm can help. We can do that as a follow up step.
>
> The simple design isn't flexible enough for your workloads too. For
> example,
>
> - Initially, almost only order-0 pages are swapped out, most non-full
> clusters are order-0.
>
> - Later, quite some order-0 swap entries are freed so that there are
> quite some order-4 swap entries available.
>
> - Order-4 pages need to be swapped out, but no enough order-4 non-full
> clusters available.
>
> So, we need a way to migrate non-full clusters among orders to adjust to
> the situations automatically.
Depends on how lucky it is to form the order-4 cluster naturally. The
odds of forming the order-4 cluster naturally in random swap
allocation/ free case is very low. I have the number in my other email
thread.
Anyway, if we convince this payout for the complexity it introduces,
we can do that as follow up steps. Try to keep things simple at first
for the review benefit.
>
> >> order 0.
> >>
> >> Do you think that this works?
> >>
> >> > Reported-by: Barry Song <21cnbao@gmail.com>
> >> > Signed-off-by: Chris Li <chrisl@kernel.org>
> >> > ---
> >> > Changes in v3:
> >> > - Using V1 as base.
> >> > - Rename "next" to "list" for the list field, suggested by Ying.
> >> > - Update comment for the locking rules for cluster fields and list,
> >> > suggested by Ying.
> >> > - Allocate from the nonfull list before attempting free list, suggested
> >> > by Kairui.
> >>
> >> Haven't looked into this. It appears that this breaks the original
> >> discard behavior which helps performance of some SSD, please refer to
> >
> > Can you clarify by "discard" you mean SSD discard command or just the
> > way swap allocator recycles free clusters?
>
> The SSD discard command, like in the following URL,
>
> https://en.wikipedia.org/wiki/Trim_(computing)
Thanks. I know what an SSD discard command is. Want to understand why
that behavior is preferred.
So the reasoning to prefer a new free block rather than a recent
particle free cluster is to let the previous written cluster have a
higher chance to issue the discard command?
This preferred new block behavior is actually not friendly to SSD from
a wearing point of view.
Take this example:
Let say the data need to allocate and free from swap. At any given
time the swap usage is 1G. The swap SSD drive is 16G.
Let say the allocation and free are at random 4K page locations. There
is totally 64G swap data needed to write to swap, but at any given
time there is only 1G data occupite on swapfile.
a) If you always prefer new free blocks. Then the swap data will
eventually write at all 16G drives then random write to full 16G.
Chance of forming a free cluster so a discard command can be issued is
very low. (15/16)**512 = 4.4E-15. From SSD point of view, it does not
know most of the data written to 16G drive is not used. When a page is
free on a swapfile, SSD drive doesn't know about it. It sees 4K random
writes to all 16G of the drive, total 64G data written.
b) If you always prefer a non full cluster first over a new cluster.
The 64G data will concentrate random writing to the first 1G of drive
location. Total 64G data written.
I consider b) are more friendly to SSD than a). Because concentrate
the write into the first 1G location. The SSD can know the data
overwritten in those 1G has internally obsolete, so it can internally
GC the those overwritten data without a discard command. Where a)
random 4K writes to the whole drive without much discard at all. Full
SSD doing random writes is a bad combination from a wearing point of
view.
Just my 2 cents. Anyway I revert the V4 to use free cluster before
nonfull cluster just to behave the same as previously.
> >> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
> >
> > I did read that change log. Help me understand in more detail which
> > discard behavior you have in mind. A lot of low end micro SD cards
> > have proper FTL wear leveling now, ssd even better on that.
>
> It's not FTL, it's discard/trim for SSD as above.
Thanks for the clarification.
>
> >> And as pointed out by Ryan, this may reduce the opportunity of the
> >> sequential block device writing during swap-out, which may hurt
> >> performance of SSD too.
> >
> > Only at the initial phase. If the swap IO continues, after the first
> > pass fills up the swap file, the write will be random on the swapfile
> > anyway. Because the swapfile only issues 2M discards commands when all
> > 512 4K pages are free. The discarded area will be much smaller than
> > the free area on swapfile. That combined with the random write page on
> > the whole swap file. It might produce a worse internal write
> > amplification for SSD, compared to only writing a subset of the
> > swapfile area. I would love to hear from someone who understands SSD
> > internals to confirm or deny my theory.
>
> It depends on workloads. Some workloads will have more severe
> fragmentation than others. For example, on quite some machines, the
> swap devices will be far from being full to avoid possible OOM.
I suspect most of the SSD swap on client devices nowadays are only as
backup just in case it needs to be swapped.
There is not much SSD swap IO during normal use. The zram and zswap
are more actively used in the data center and Android phone case, from
swap IO ops point of view.
>
> > Even let's assume the SSD wants a free block over a nonfull cluster
> > first. Zswap and zram swap are not subject to SSD property. We might
> > want to have a kernel option to select using nonfree clusters over
> > the free one for zram and zswap (ghost swapfile). That will help
> > contain the fragmented swap area.
>
> I suspect that it will help fragmentation avoidance much. Please prove
> its effectiveness with data firstly. It can be a further optimization
> patch in the series.
Take the above 1GB data written in a 16GB drive example. a) will
fragment the whole 16GB drive.
b) will concentrate on the first 1GB location that was used.
>
> Even if we really need it, we can try to do it without a kernel option.
> For example, detect whether we are using zram and enable it for zram
> automatically (through a general flag).
zswap you need to have an option to choose from because it can write
to the real swappfile as well.
Do you optimize the swap allocator for the zswap or physical swapfile.
Chris
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-07-26 6:46 ` Chris Li
@ 2024-07-26 6:57 ` Huang, Ying
2024-07-26 7:22 ` Chris Li
0 siblings, 1 reply; 16+ messages in thread
From: Huang, Ying @ 2024-07-26 6:57 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> On Mon, Jun 24, 2024 at 7:36 PM Huang, Ying <ying.huang@intel.com> wrote:
>>
>> Chris Li <chrisl@kernel.org> writes:
>>
>> > On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
>> >>
>> >> Chris Li <chrisl@kernel.org> writes:
>> >>
>> >> > This is the short term solutiolns "swap cluster order" listed
>> >> > in my "Swap Abstraction" discussion slice 8 in the recent
>> >> > LSF/MM conference.
>> >> >
>> >> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
>> >> > orders" is introduced, it only allocates the mTHP swap entries
>> >> > from new empty cluster list. It has a fragmentation issue
>> >> > reported by Barry.
>> >> >
>> >> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>> >> >
>> >> > The reason is that all the empty cluster has been exhausted while
>> >> > there are planty of free swap entries to in the cluster that is
>> >> > not 100% free.
>> >> >
>> >> > Remember the swap allocation order in the cluster.
>> >> > Keep track of the per order non full cluster list for later allocation.
>> >> >
>> >> > User impact: For users that allocate and free mix order mTHP swapping,
>> >> > It greatly improves the success rate of the mTHP swap allocation after the
>> >> > initial phase.
>> >> >
>> >> > Barry provides a test program to show the effect:
>> >> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
>> >> >
>> >> > Without:
>> >> > $ mthp-swapout
>> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
>> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
>> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> >> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
>> >> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> >> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> >> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
>> >> >
>> >> > $ mthp-swapout -s
>> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
>> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
>> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> >> >
>> >> > With:
>> >> > $ mthp-swapout
>> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > ...
>> >> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >
>> >> > $ mthp-swapout -s
>> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > ...
>> >> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >>
>> >> Unfortunately, the data is gotten using a special designed test program
>> >> which always swap-in pages with swapped-out size. I don't know whether
>> >> such workloads exist in reality. Otherwise, you need to wait for mTHP
>> >
>> > The test program is designed to simulate mTHP swap behavior using
>> > zsmalloc and 64KB buffer.
>> > If we insist on only designing for existing workloads, then zsmalloc
>> > using 64KB buffer usage will never be able to run, exactly due the
>> > kernel has high failure rate allocating swap entries for 64KB. There
>> > is a bit of a chick and egg problem there, such a usage can not exist
>> > because the kernel can't support it yet. Kernel can't add patches to
>> > support it because such simulation tests are not "real".
>> >
>> > We need to break this cycle to support something new.
>> >
>> >> swap-in to be merged firstly, and people reach consensus that we should
>> >> always swap-in pages with swapped-out size.
>> >
>> > We don't have to be always. We can identify the situation that makes
>> > sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
>> > same swap in size makes sense.
>> > I think we have agreement on such zsmalloc 64K usage cases we do want
>> > to support.
>> >
>> >>
>> >> Alternately, we can make some design adjustment to make the patchset
>> >> work in current situation (mTHP swap-out, normal page swap-in).
>> >>
>> >> - One non-full cluster list for each order (same as current design)
>> >>
>> >> - When one swap entry is freed, check whether one "order+1" swap entry
>> >> becomes free, if so, move the cluster to "order+1" non-full cluster
>> >> list.
>> >
>> > In the intended zsmalloc usage case, there is no order+1 swap entry
>> > request.
>>
>> This my main concern about this series. Only the Android use cases are
>> considered. The general use cases are just ignored. Is it hard to
>> consider or test a normal swap partition on your development machine?
>
> Please see the V4 cover letter. The V4 already has the SSD, zram and
> HDD stress testing.
> Of course I want to make sure the allocator works well with Barry's
> mthp test case as well.
>
>> > Moving the cluster to "order+1" will make less cluster available for "order".
>> > For that usage case it is negative gain.
>>
>> The "order+1" cluster can be used to allocate "order" cluster when
>> existing "order" cluster is used up.
>>
>> And in this way, we can protect clusters with more free spaces so that
>> they may become free.
>>
>> >> - When allocate swap entry with "order", get cluster from free, "order",
>> >> "order+1", ... non-full cluster list. If all are empty, fallback to
>> >
>> > I don't see that it is useful for the zsmalloc 64K buffer usage case.
>> > There will be order 0 and order 4 and nothing else.
>> >
>> > How about let's keep it simple for now. If we identify some workload
>> > this algorithm can help. We can do that as a follow up step.
>>
>> The simple design isn't flexible enough for your workloads too. For
>> example,
>>
>> - Initially, almost only order-0 pages are swapped out, most non-full
>> clusters are order-0.
>>
>> - Later, quite some order-0 swap entries are freed so that there are
>> quite some order-4 swap entries available.
>>
>> - Order-4 pages need to be swapped out, but no enough order-4 non-full
>> clusters available.
>>
>> So, we need a way to migrate non-full clusters among orders to adjust to
>> the situations automatically.
>
> Depends on how lucky it is to form the order-4 cluster naturally. The
> odds of forming the order-4 cluster naturally in random swap
> allocation/ free case is very low. I have the number in my other email
> thread.
> Anyway, if we convince this payout for the complexity it introduces,
> we can do that as follow up steps. Try to keep things simple at first
> for the review benefit.
>
>>
>> >> order 0.
>> >>
>> >> Do you think that this works?
>> >>
>> >> > Reported-by: Barry Song <21cnbao@gmail.com>
>> >> > Signed-off-by: Chris Li <chrisl@kernel.org>
>> >> > ---
>> >> > Changes in v3:
>> >> > - Using V1 as base.
>> >> > - Rename "next" to "list" for the list field, suggested by Ying.
>> >> > - Update comment for the locking rules for cluster fields and list,
>> >> > suggested by Ying.
>> >> > - Allocate from the nonfull list before attempting free list, suggested
>> >> > by Kairui.
>> >>
>> >> Haven't looked into this. It appears that this breaks the original
>> >> discard behavior which helps performance of some SSD, please refer to
>> >
>> > Can you clarify by "discard" you mean SSD discard command or just the
>> > way swap allocator recycles free clusters?
>>
>> The SSD discard command, like in the following URL,
>>
>> https://en.wikipedia.org/wiki/Trim_(computing)
>
> Thanks. I know what an SSD discard command is. Want to understand why
> that behavior is preferred.
>
> So the reasoning to prefer a new free block rather than a recent
> particle free cluster is to let the previous written cluster have a
> higher chance to issue the discard command?
>
> This preferred new block behavior is actually not friendly to SSD from
> a wearing point of view.
> Take this example:
> Let say the data need to allocate and free from swap. At any given
> time the swap usage is 1G. The swap SSD drive is 16G.
> Let say the allocation and free are at random 4K page locations. There
> is totally 64G swap data needed to write to swap, but at any given
> time there is only 1G data occupite on swapfile.
>
> a) If you always prefer new free blocks. Then the swap data will
> eventually write at all 16G drives then random write to full 16G.
> Chance of forming a free cluster so a discard command can be issued is
> very low. (15/16)**512 = 4.4E-15. From SSD point of view, it does not
> know most of the data written to 16G drive is not used. When a page is
> free on a swapfile, SSD drive doesn't know about it. It sees 4K random
> writes to all 16G of the drive, total 64G data written.
>
> b) If you always prefer a non full cluster first over a new cluster.
> The 64G data will concentrate random writing to the first 1G of drive
> location. Total 64G data written.
>
> I consider b) are more friendly to SSD than a). Because concentrate
> the write into the first 1G location. The SSD can know the data
> overwritten in those 1G has internally obsolete, so it can internally
> GC the those overwritten data without a discard command. Where a)
> random 4K writes to the whole drive without much discard at all. Full
> SSD doing random writes is a bad combination from a wearing point of
> view.
>
> Just my 2 cents. Anyway I revert the V4 to use free cluster before
> nonfull cluster just to behave the same as previously.
>
>> >> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
>> >
>> > I did read that change log. Help me understand in more detail which
>> > discard behavior you have in mind. A lot of low end micro SD cards
>> > have proper FTL wear leveling now, ssd even better on that.
>>
>> It's not FTL, it's discard/trim for SSD as above.
>
> Thanks for the clarification.
>
>>
>> >> And as pointed out by Ryan, this may reduce the opportunity of the
>> >> sequential block device writing during swap-out, which may hurt
>> >> performance of SSD too.
>> >
>> > Only at the initial phase. If the swap IO continues, after the first
>> > pass fills up the swap file, the write will be random on the swapfile
>> > anyway. Because the swapfile only issues 2M discards commands when all
>> > 512 4K pages are free. The discarded area will be much smaller than
>> > the free area on swapfile. That combined with the random write page on
>> > the whole swap file. It might produce a worse internal write
>> > amplification for SSD, compared to only writing a subset of the
>> > swapfile area. I would love to hear from someone who understands SSD
>> > internals to confirm or deny my theory.
>>
>> It depends on workloads. Some workloads will have more severe
>> fragmentation than others. For example, on quite some machines, the
>> swap devices will be far from being full to avoid possible OOM.
>
> I suspect most of the SSD swap on client devices nowadays are only as
> backup just in case it needs to be swapped.
> There is not much SSD swap IO during normal use. The zram and zswap
> are more actively used in the data center and Android phone case, from
> swap IO ops point of view.
I use a Linux laptop with 16GB DRAM for work. And I found that the swap
space are almost always used.
>>
>> > Even let's assume the SSD wants a free block over a nonfull cluster
>> > first. Zswap and zram swap are not subject to SSD property. We might
>> > want to have a kernel option to select using nonfree clusters over
>> > the free one for zram and zswap (ghost swapfile). That will help
>> > contain the fragmented swap area.
>>
>> I suspect that it will help fragmentation avoidance much. Please prove
>> its effectiveness with data firstly. It can be a further optimization
>> patch in the series.
>
> Take the above 1GB data written in a 16GB drive example. a) will
> fragment the whole 16GB drive.
> b) will concentrate on the first 1GB location that was used.
>
>>
>> Even if we really need it, we can try to do it without a kernel option.
>> For example, detect whether we are using zram and enable it for zram
>> automatically (through a general flag).
>
> zswap you need to have an option to choose from because it can write
> to the real swappfile as well.
> Do you optimize the swap allocator for the zswap or physical swapfile.
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-07-26 6:57 ` Huang, Ying
@ 2024-07-26 7:22 ` Chris Li
2024-07-26 7:29 ` Huang, Ying
0 siblings, 1 reply; 16+ messages in thread
From: Chris Li @ 2024-07-26 7:22 UTC (permalink / raw)
To: Huang, Ying
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
On Fri, Jul 26, 2024 at 12:01 AM Huang, Ying <ying.huang@intel.com> wrote:
>
> Chris Li <chrisl@kernel.org> writes:
>
> > On Mon, Jun 24, 2024 at 7:36 PM Huang, Ying <ying.huang@intel.com> wrote:
> >>
> >> Chris Li <chrisl@kernel.org> writes:
> >>
> >> > On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
> >> >>
> >> >> Chris Li <chrisl@kernel.org> writes:
> >> >>
> >> >> > This is the short term solutiolns "swap cluster order" listed
> >> >> > in my "Swap Abstraction" discussion slice 8 in the recent
> >> >> > LSF/MM conference.
> >> >> >
> >> >> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> >> >> > orders" is introduced, it only allocates the mTHP swap entries
> >> >> > from new empty cluster list. It has a fragmentation issue
> >> >> > reported by Barry.
> >> >> >
> >> >> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
> >> >> >
> >> >> > The reason is that all the empty cluster has been exhausted while
> >> >> > there are planty of free swap entries to in the cluster that is
> >> >> > not 100% free.
> >> >> >
> >> >> > Remember the swap allocation order in the cluster.
> >> >> > Keep track of the per order non full cluster list for later allocation.
> >> >> >
> >> >> > User impact: For users that allocate and free mix order mTHP swapping,
> >> >> > It greatly improves the success rate of the mTHP swap allocation after the
> >> >> > initial phase.
> >> >> >
> >> >> > Barry provides a test program to show the effect:
> >> >> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
> >> >> >
> >> >> > Without:
> >> >> > $ mthp-swapout
> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
> >> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
> >> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> >> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> >> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> >> >> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
> >> >> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> >> >> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
> >> >> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
> >> >> >
> >> >> > $ mthp-swapout -s
> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
> >> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
> >> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
> >> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
> >> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
> >> >> >
> >> >> > With:
> >> >> > $ mthp-swapout
> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > ...
> >> >> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> >
> >> >> > $ mthp-swapout -s
> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > ...
> >> >> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
> >> >>
> >> >> Unfortunately, the data is gotten using a special designed test program
> >> >> which always swap-in pages with swapped-out size. I don't know whether
> >> >> such workloads exist in reality. Otherwise, you need to wait for mTHP
> >> >
> >> > The test program is designed to simulate mTHP swap behavior using
> >> > zsmalloc and 64KB buffer.
> >> > If we insist on only designing for existing workloads, then zsmalloc
> >> > using 64KB buffer usage will never be able to run, exactly due the
> >> > kernel has high failure rate allocating swap entries for 64KB. There
> >> > is a bit of a chick and egg problem there, such a usage can not exist
> >> > because the kernel can't support it yet. Kernel can't add patches to
> >> > support it because such simulation tests are not "real".
> >> >
> >> > We need to break this cycle to support something new.
> >> >
> >> >> swap-in to be merged firstly, and people reach consensus that we should
> >> >> always swap-in pages with swapped-out size.
> >> >
> >> > We don't have to be always. We can identify the situation that makes
> >> > sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
> >> > same swap in size makes sense.
> >> > I think we have agreement on such zsmalloc 64K usage cases we do want
> >> > to support.
> >> >
> >> >>
> >> >> Alternately, we can make some design adjustment to make the patchset
> >> >> work in current situation (mTHP swap-out, normal page swap-in).
> >> >>
> >> >> - One non-full cluster list for each order (same as current design)
> >> >>
> >> >> - When one swap entry is freed, check whether one "order+1" swap entry
> >> >> becomes free, if so, move the cluster to "order+1" non-full cluster
> >> >> list.
> >> >
> >> > In the intended zsmalloc usage case, there is no order+1 swap entry
> >> > request.
> >>
> >> This my main concern about this series. Only the Android use cases are
> >> considered. The general use cases are just ignored. Is it hard to
> >> consider or test a normal swap partition on your development machine?
> >
> > Please see the V4 cover letter. The V4 already has the SSD, zram and
> > HDD stress testing.
> > Of course I want to make sure the allocator works well with Barry's
> > mthp test case as well.
> >
> >> > Moving the cluster to "order+1" will make less cluster available for "order".
> >> > For that usage case it is negative gain.
> >>
> >> The "order+1" cluster can be used to allocate "order" cluster when
> >> existing "order" cluster is used up.
> >>
> >> And in this way, we can protect clusters with more free spaces so that
> >> they may become free.
> >>
> >> >> - When allocate swap entry with "order", get cluster from free, "order",
> >> >> "order+1", ... non-full cluster list. If all are empty, fallback to
> >> >
> >> > I don't see that it is useful for the zsmalloc 64K buffer usage case.
> >> > There will be order 0 and order 4 and nothing else.
> >> >
> >> > How about let's keep it simple for now. If we identify some workload
> >> > this algorithm can help. We can do that as a follow up step.
> >>
> >> The simple design isn't flexible enough for your workloads too. For
> >> example,
> >>
> >> - Initially, almost only order-0 pages are swapped out, most non-full
> >> clusters are order-0.
> >>
> >> - Later, quite some order-0 swap entries are freed so that there are
> >> quite some order-4 swap entries available.
> >>
> >> - Order-4 pages need to be swapped out, but no enough order-4 non-full
> >> clusters available.
> >>
> >> So, we need a way to migrate non-full clusters among orders to adjust to
> >> the situations automatically.
> >
> > Depends on how lucky it is to form the order-4 cluster naturally. The
> > odds of forming the order-4 cluster naturally in random swap
> > allocation/ free case is very low. I have the number in my other email
> > thread.
> > Anyway, if we convince this payout for the complexity it introduces,
> > we can do that as follow up steps. Try to keep things simple at first
> > for the review benefit.
> >
> >>
> >> >> order 0.
> >> >>
> >> >> Do you think that this works?
> >> >>
> >> >> > Reported-by: Barry Song <21cnbao@gmail.com>
> >> >> > Signed-off-by: Chris Li <chrisl@kernel.org>
> >> >> > ---
> >> >> > Changes in v3:
> >> >> > - Using V1 as base.
> >> >> > - Rename "next" to "list" for the list field, suggested by Ying.
> >> >> > - Update comment for the locking rules for cluster fields and list,
> >> >> > suggested by Ying.
> >> >> > - Allocate from the nonfull list before attempting free list, suggested
> >> >> > by Kairui.
> >> >>
> >> >> Haven't looked into this. It appears that this breaks the original
> >> >> discard behavior which helps performance of some SSD, please refer to
> >> >
> >> > Can you clarify by "discard" you mean SSD discard command or just the
> >> > way swap allocator recycles free clusters?
> >>
> >> The SSD discard command, like in the following URL,
> >>
> >> https://en.wikipedia.org/wiki/Trim_(computing)
> >
> > Thanks. I know what an SSD discard command is. Want to understand why
> > that behavior is preferred.
> >
> > So the reasoning to prefer a new free block rather than a recent
> > particle free cluster is to let the previous written cluster have a
> > higher chance to issue the discard command?
> >
> > This preferred new block behavior is actually not friendly to SSD from
> > a wearing point of view.
> > Take this example:
> > Let say the data need to allocate and free from swap. At any given
> > time the swap usage is 1G. The swap SSD drive is 16G.
> > Let say the allocation and free are at random 4K page locations. There
> > is totally 64G swap data needed to write to swap, but at any given
> > time there is only 1G data occupite on swapfile.
> >
> > a) If you always prefer new free blocks. Then the swap data will
> > eventually write at all 16G drives then random write to full 16G.
> > Chance of forming a free cluster so a discard command can be issued is
> > very low. (15/16)**512 = 4.4E-15. From SSD point of view, it does not
> > know most of the data written to 16G drive is not used. When a page is
> > free on a swapfile, SSD drive doesn't know about it. It sees 4K random
> > writes to all 16G of the drive, total 64G data written.
> >
> > b) If you always prefer a non full cluster first over a new cluster.
> > The 64G data will concentrate random writing to the first 1G of drive
> > location. Total 64G data written.
> >
> > I consider b) are more friendly to SSD than a). Because concentrate
> > the write into the first 1G location. The SSD can know the data
> > overwritten in those 1G has internally obsolete, so it can internally
> > GC the those overwritten data without a discard command. Where a)
> > random 4K writes to the whole drive without much discard at all. Full
> > SSD doing random writes is a bad combination from a wearing point of
> > view.
> >
> > Just my 2 cents. Anyway I revert the V4 to use free cluster before
> > nonfull cluster just to behave the same as previously.
> >
> >> >> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
> >> >
> >> > I did read that change log. Help me understand in more detail which
> >> > discard behavior you have in mind. A lot of low end micro SD cards
> >> > have proper FTL wear leveling now, ssd even better on that.
> >>
> >> It's not FTL, it's discard/trim for SSD as above.
> >
> > Thanks for the clarification.
> >
> >>
> >> >> And as pointed out by Ryan, this may reduce the opportunity of the
> >> >> sequential block device writing during swap-out, which may hurt
> >> >> performance of SSD too.
> >> >
> >> > Only at the initial phase. If the swap IO continues, after the first
> >> > pass fills up the swap file, the write will be random on the swapfile
> >> > anyway. Because the swapfile only issues 2M discards commands when all
> >> > 512 4K pages are free. The discarded area will be much smaller than
> >> > the free area on swapfile. That combined with the random write page on
> >> > the whole swap file. It might produce a worse internal write
> >> > amplification for SSD, compared to only writing a subset of the
> >> > swapfile area. I would love to hear from someone who understands SSD
> >> > internals to confirm or deny my theory.
> >>
> >> It depends on workloads. Some workloads will have more severe
> >> fragmentation than others. For example, on quite some machines, the
> >> swap devices will be far from being full to avoid possible OOM.
> >
> > I suspect most of the SSD swap on client devices nowadays are only as
> > backup just in case it needs to be swapped.
> > There is not much SSD swap IO during normal use. The zram and zswap
> > are more actively used in the data center and Android phone case, from
> > swap IO ops point of view.
>
> I use a Linux laptop with 16GB DRAM for work. And I found that the swap
> space are almost always used.
Just curious how many swap OPS per second on average? I suspect it
will be a very low number.
Chris
>
> >>
> >> > Even let's assume the SSD wants a free block over a nonfull cluster
> >> > first. Zswap and zram swap are not subject to SSD property. We might
> >> > want to have a kernel option to select using nonfree clusters over
> >> > the free one for zram and zswap (ghost swapfile). That will help
> >> > contain the fragmented swap area.
> >>
> >> I suspect that it will help fragmentation avoidance much. Please prove
> >> its effectiveness with data firstly. It can be a further optimization
> >> patch in the series.
> >
> > Take the above 1GB data written in a 16GB drive example. a) will
> > fragment the whole 16GB drive.
> > b) will concentrate on the first 1GB location that was used.
> >
> >>
> >> Even if we really need it, we can try to do it without a kernel option.
> >> For example, detect whether we are using zram and enable it for zram
> >> automatically (through a general flag).
> >
> > zswap you need to have an option to choose from because it can write
> > to the real swappfile as well.
> > Do you optimize the swap allocator for the zswap or physical swapfile.
>
> --
> Best Regards,
> Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-07-26 7:22 ` Chris Li
@ 2024-07-26 7:29 ` Huang, Ying
0 siblings, 0 replies; 16+ messages in thread
From: Huang, Ying @ 2024-07-26 7:29 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> On Fri, Jul 26, 2024 at 12:01 AM Huang, Ying <ying.huang@intel.com> wrote:
>>
>> Chris Li <chrisl@kernel.org> writes:
>>
>> > On Mon, Jun 24, 2024 at 7:36 PM Huang, Ying <ying.huang@intel.com> wrote:
>> >>
>> >> Chris Li <chrisl@kernel.org> writes:
>> >>
>> >> > On Wed, Jun 19, 2024 at 7:32 PM Huang, Ying <ying.huang@intel.com> wrote:
>> >> >>
>> >> >> Chris Li <chrisl@kernel.org> writes:
>> >> >>
>> >> >> > This is the short term solutiolns "swap cluster order" listed
>> >> >> > in my "Swap Abstraction" discussion slice 8 in the recent
>> >> >> > LSF/MM conference.
>> >> >> >
>> >> >> > When commit 845982eb264bc "mm: swap: allow storage of all mTHP
>> >> >> > orders" is introduced, it only allocates the mTHP swap entries
>> >> >> > from new empty cluster list. It has a fragmentation issue
>> >> >> > reported by Barry.
>> >> >> >
>> >> >> > https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>> >> >> >
>> >> >> > The reason is that all the empty cluster has been exhausted while
>> >> >> > there are planty of free swap entries to in the cluster that is
>> >> >> > not 100% free.
>> >> >> >
>> >> >> > Remember the swap allocation order in the cluster.
>> >> >> > Keep track of the per order non full cluster list for later allocation.
>> >> >> >
>> >> >> > User impact: For users that allocate and free mix order mTHP swapping,
>> >> >> > It greatly improves the success rate of the mTHP swap allocation after the
>> >> >> > initial phase.
>> >> >> >
>> >> >> > Barry provides a test program to show the effect:
>> >> >> > https://lore.kernel.org/linux-mm/20240615084714.37499-1-21cnbao@gmail.com/
>> >> >> >
>> >> >> > Without:
>> >> >> > $ mthp-swapout
>> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 5: swpout inc: 110, swpout fallback inc: 117, Fallback percentage: 51.54%
>> >> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 230, Fallback percentage: 100.00%
>> >> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> >> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> >> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> >> >> > Iteration 10: swpout inc: 0, swpout fallback inc: 216, Fallback percentage: 100.00%
>> >> >> > Iteration 11: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> >> >> > Iteration 12: swpout inc: 0, swpout fallback inc: 224, Fallback percentage: 100.00%
>> >> >> > Iteration 13: swpout inc: 0, swpout fallback inc: 214, Fallback percentage: 100.00%
>> >> >> >
>> >> >> > $ mthp-swapout -s
>> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 5: swpout inc: 33, swpout fallback inc: 197, Fallback percentage: 85.65%
>> >> >> > Iteration 6: swpout inc: 0, swpout fallback inc: 229, Fallback percentage: 100.00%
>> >> >> > Iteration 7: swpout inc: 0, swpout fallback inc: 223, Fallback percentage: 100.00%
>> >> >> > Iteration 8: swpout inc: 0, swpout fallback inc: 219, Fallback percentage: 100.00%
>> >> >> > Iteration 9: swpout inc: 0, swpout fallback inc: 212, Fallback percentage: 100.00%
>> >> >> >
>> >> >> > With:
>> >> >> > $ mthp-swapout
>> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 2: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 4: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 5: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 6: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > ...
>> >> >> > Iteration 94: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 95: swpout inc: 221, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 96: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 97: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 98: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 100: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> >
>> >> >> > $ mthp-swapout -s
>> >> >> > Iteration 1: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 2: swpout inc: 227, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 3: swpout inc: 222, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 4: swpout inc: 224, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 5: swpout inc: 230, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 6: swpout inc: 229, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 7: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 8: swpout inc: 219, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > ...
>> >> >> > Iteration 94: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 95: swpout inc: 212, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 96: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 97: swpout inc: 220, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 98: swpout inc: 216, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 99: swpout inc: 223, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >> > Iteration 100: swpout inc: 225, swpout fallback inc: 0, Fallback percentage: 0.00%
>> >> >>
>> >> >> Unfortunately, the data is gotten using a special designed test program
>> >> >> which always swap-in pages with swapped-out size. I don't know whether
>> >> >> such workloads exist in reality. Otherwise, you need to wait for mTHP
>> >> >
>> >> > The test program is designed to simulate mTHP swap behavior using
>> >> > zsmalloc and 64KB buffer.
>> >> > If we insist on only designing for existing workloads, then zsmalloc
>> >> > using 64KB buffer usage will never be able to run, exactly due the
>> >> > kernel has high failure rate allocating swap entries for 64KB. There
>> >> > is a bit of a chick and egg problem there, such a usage can not exist
>> >> > because the kernel can't support it yet. Kernel can't add patches to
>> >> > support it because such simulation tests are not "real".
>> >> >
>> >> > We need to break this cycle to support something new.
>> >> >
>> >> >> swap-in to be merged firstly, and people reach consensus that we should
>> >> >> always swap-in pages with swapped-out size.
>> >> >
>> >> > We don't have to be always. We can identify the situation that makes
>> >> > sense. For the zram/zsmalloc 64K buffer usage case, swap out as the
>> >> > same swap in size makes sense.
>> >> > I think we have agreement on such zsmalloc 64K usage cases we do want
>> >> > to support.
>> >> >
>> >> >>
>> >> >> Alternately, we can make some design adjustment to make the patchset
>> >> >> work in current situation (mTHP swap-out, normal page swap-in).
>> >> >>
>> >> >> - One non-full cluster list for each order (same as current design)
>> >> >>
>> >> >> - When one swap entry is freed, check whether one "order+1" swap entry
>> >> >> becomes free, if so, move the cluster to "order+1" non-full cluster
>> >> >> list.
>> >> >
>> >> > In the intended zsmalloc usage case, there is no order+1 swap entry
>> >> > request.
>> >>
>> >> This my main concern about this series. Only the Android use cases are
>> >> considered. The general use cases are just ignored. Is it hard to
>> >> consider or test a normal swap partition on your development machine?
>> >
>> > Please see the V4 cover letter. The V4 already has the SSD, zram and
>> > HDD stress testing.
>> > Of course I want to make sure the allocator works well with Barry's
>> > mthp test case as well.
>> >
>> >> > Moving the cluster to "order+1" will make less cluster available for "order".
>> >> > For that usage case it is negative gain.
>> >>
>> >> The "order+1" cluster can be used to allocate "order" cluster when
>> >> existing "order" cluster is used up.
>> >>
>> >> And in this way, we can protect clusters with more free spaces so that
>> >> they may become free.
>> >>
>> >> >> - When allocate swap entry with "order", get cluster from free, "order",
>> >> >> "order+1", ... non-full cluster list. If all are empty, fallback to
>> >> >
>> >> > I don't see that it is useful for the zsmalloc 64K buffer usage case.
>> >> > There will be order 0 and order 4 and nothing else.
>> >> >
>> >> > How about let's keep it simple for now. If we identify some workload
>> >> > this algorithm can help. We can do that as a follow up step.
>> >>
>> >> The simple design isn't flexible enough for your workloads too. For
>> >> example,
>> >>
>> >> - Initially, almost only order-0 pages are swapped out, most non-full
>> >> clusters are order-0.
>> >>
>> >> - Later, quite some order-0 swap entries are freed so that there are
>> >> quite some order-4 swap entries available.
>> >>
>> >> - Order-4 pages need to be swapped out, but no enough order-4 non-full
>> >> clusters available.
>> >>
>> >> So, we need a way to migrate non-full clusters among orders to adjust to
>> >> the situations automatically.
>> >
>> > Depends on how lucky it is to form the order-4 cluster naturally. The
>> > odds of forming the order-4 cluster naturally in random swap
>> > allocation/ free case is very low. I have the number in my other email
>> > thread.
>> > Anyway, if we convince this payout for the complexity it introduces,
>> > we can do that as follow up steps. Try to keep things simple at first
>> > for the review benefit.
>> >
>> >>
>> >> >> order 0.
>> >> >>
>> >> >> Do you think that this works?
>> >> >>
>> >> >> > Reported-by: Barry Song <21cnbao@gmail.com>
>> >> >> > Signed-off-by: Chris Li <chrisl@kernel.org>
>> >> >> > ---
>> >> >> > Changes in v3:
>> >> >> > - Using V1 as base.
>> >> >> > - Rename "next" to "list" for the list field, suggested by Ying.
>> >> >> > - Update comment for the locking rules for cluster fields and list,
>> >> >> > suggested by Ying.
>> >> >> > - Allocate from the nonfull list before attempting free list, suggested
>> >> >> > by Kairui.
>> >> >>
>> >> >> Haven't looked into this. It appears that this breaks the original
>> >> >> discard behavior which helps performance of some SSD, please refer to
>> >> >
>> >> > Can you clarify by "discard" you mean SSD discard command or just the
>> >> > way swap allocator recycles free clusters?
>> >>
>> >> The SSD discard command, like in the following URL,
>> >>
>> >> https://en.wikipedia.org/wiki/Trim_(computing)
>> >
>> > Thanks. I know what an SSD discard command is. Want to understand why
>> > that behavior is preferred.
>> >
>> > So the reasoning to prefer a new free block rather than a recent
>> > particle free cluster is to let the previous written cluster have a
>> > higher chance to issue the discard command?
>> >
>> > This preferred new block behavior is actually not friendly to SSD from
>> > a wearing point of view.
>> > Take this example:
>> > Let say the data need to allocate and free from swap. At any given
>> > time the swap usage is 1G. The swap SSD drive is 16G.
>> > Let say the allocation and free are at random 4K page locations. There
>> > is totally 64G swap data needed to write to swap, but at any given
>> > time there is only 1G data occupite on swapfile.
>> >
>> > a) If you always prefer new free blocks. Then the swap data will
>> > eventually write at all 16G drives then random write to full 16G.
>> > Chance of forming a free cluster so a discard command can be issued is
>> > very low. (15/16)**512 = 4.4E-15. From SSD point of view, it does not
>> > know most of the data written to 16G drive is not used. When a page is
>> > free on a swapfile, SSD drive doesn't know about it. It sees 4K random
>> > writes to all 16G of the drive, total 64G data written.
>> >
>> > b) If you always prefer a non full cluster first over a new cluster.
>> > The 64G data will concentrate random writing to the first 1G of drive
>> > location. Total 64G data written.
>> >
>> > I consider b) are more friendly to SSD than a). Because concentrate
>> > the write into the first 1G location. The SSD can know the data
>> > overwritten in those 1G has internally obsolete, so it can internally
>> > GC the those overwritten data without a discard command. Where a)
>> > random 4K writes to the whole drive without much discard at all. Full
>> > SSD doing random writes is a bad combination from a wearing point of
>> > view.
>> >
>> > Just my 2 cents. Anyway I revert the V4 to use free cluster before
>> > nonfull cluster just to behave the same as previously.
>> >
>> >> >> commit 2a8f94493432 ("swap: change block allocation algorithm for SSD").
>> >> >
>> >> > I did read that change log. Help me understand in more detail which
>> >> > discard behavior you have in mind. A lot of low end micro SD cards
>> >> > have proper FTL wear leveling now, ssd even better on that.
>> >>
>> >> It's not FTL, it's discard/trim for SSD as above.
>> >
>> > Thanks for the clarification.
>> >
>> >>
>> >> >> And as pointed out by Ryan, this may reduce the opportunity of the
>> >> >> sequential block device writing during swap-out, which may hurt
>> >> >> performance of SSD too.
>> >> >
>> >> > Only at the initial phase. If the swap IO continues, after the first
>> >> > pass fills up the swap file, the write will be random on the swapfile
>> >> > anyway. Because the swapfile only issues 2M discards commands when all
>> >> > 512 4K pages are free. The discarded area will be much smaller than
>> >> > the free area on swapfile. That combined with the random write page on
>> >> > the whole swap file. It might produce a worse internal write
>> >> > amplification for SSD, compared to only writing a subset of the
>> >> > swapfile area. I would love to hear from someone who understands SSD
>> >> > internals to confirm or deny my theory.
>> >>
>> >> It depends on workloads. Some workloads will have more severe
>> >> fragmentation than others. For example, on quite some machines, the
>> >> swap devices will be far from being full to avoid possible OOM.
>> >
>> > I suspect most of the SSD swap on client devices nowadays are only as
>> > backup just in case it needs to be swapped.
>> > There is not much SSD swap IO during normal use. The zram and zswap
>> > are more actively used in the data center and Android phone case, from
>> > swap IO ops point of view.
>>
>> I use a Linux laptop with 16GB DRAM for work. And I found that the swap
>> space are almost always used.
>
> Just curious how many swap OPS per second on average? I suspect it
> will be a very low number.
It depends on workloads. I have run some LLM pruning experiment
algorithm on the machine. The swap IOPS is high for that.
[snip]
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order
2024-06-19 9:20 [PATCH v3 0/2] mm: swap: mTHP swap allocator base on swap cluster order Chris Li
` (3 preceding siblings ...)
2024-06-20 2:30 ` Huang, Ying
@ 2024-06-25 2:43 ` Huang, Ying
4 siblings, 0 replies; 16+ messages in thread
From: Huang, Ying @ 2024-06-25 2:43 UTC (permalink / raw)
To: Chris Li
Cc: Andrew Morton, Kairui Song, Ryan Roberts, Kalesh Singh,
linux-kernel, linux-mm, Barry Song
Chris Li <chrisl@kernel.org> writes:
> This is the short term solutiolns "swap cluster order" listed
> in my "Swap Abstraction" discussion slice 8 in the recent
> LSF/MM conference.
>
> When commit 845982eb264bc "mm: swap: allow storage of all mTHP
> orders" is introduced, it only allocates the mTHP swap entries
> from new empty cluster list. It has a fragmentation issue
> reported by Barry.
>
> https://lore.kernel.org/all/CAGsJ_4zAcJkuW016Cfi6wicRr8N9X+GJJhgMQdSMp+Ah+NSgNQ@mail.gmail.com/
>
> The reason is that all the empty cluster has been exhausted while
> there are planty of free swap entries to in the cluster that is
> not 100% free.
>
> Remember the swap allocation order in the cluster.
> Keep track of the per order non full cluster list for later allocation.
The "non full" is a kind of negative naming, can we use "partial" as
that used in "slub"?
[snip]
--
Best Regards,
Huang, Ying
^ permalink raw reply [flat|nested] 16+ messages in thread