mm: swap: mTHP swap allocator base on swap cluster order

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_cluster_info 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 <[email protected]>

---
 include/linux/swap.h |  25 ++----
 mm/swapfile.c        | 226 ++++++++++++++-------------------------------------
 2 files changed, 71 insertions(+), 180 deletions(-)

include/linux/swap.h +9 -16

index e473fe6cfb7a..edafd52d7ac4 100644
@@ -243,22 +243,20 @@ 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 corresponding 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 +281,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.
  */

@@ -301,7 +294,7 @@ struct swap_info_struct {
 	unsigned char *swap_map;	/* vmalloc'ed array of usage counts */
 	unsigned long *zeromap;		/* vmalloc'ed bitmap to track zero pages */
 	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 */

@@ -332,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.

mm/swapfile.c +13 -118

index f7224bc1320c..bceead7f9e3c 100644
@@ -290,62 +290,15 @@ 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)
+static inline unsigned int cluster_index(struct swap_info_struct *si,
+					 struct swap_cluster_info *ci)
 {
-	info->flags = CLUSTER_FLAG_NEXT_NULL;
-	info->data = 0;
+	return ci - si->cluster_info;
 }
 
 static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,

@@ -394,65 +347,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 = cluster_index(si, ci);
 	/*
 	 * 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 +361,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,24 +377,25 @@ 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);

mm/swapfile.c +47 -44

+		spin_lock(&ci->lock);
+		__free_cluster(si, ci);
 		memset(si->swap_map + idx * SWAPFILE_CLUSTER,
 				0, SWAPFILE_CLUSTER);
-		unlock_cluster(ci);
+		spin_unlock(&ci->lock);
 	}
 }
 

@@ -521,20 +418,21 @@ 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(cluster_index(si, ci) != 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 +440,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 +457,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 +479,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 use, 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 +505,12 @@ 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 !=  cluster_index(si, first) &&
 		cluster_is_free(&si->cluster_info[offset]);
 
 	if (!conflict)

@@ -655,10 +551,10 @@ 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);
+			tmp = cluster_index(si, ci) * 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

@@ -1070,8 +966,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);
 }

@@ -1344,7 +1241,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);

@@ -3022,8 +2919,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];

@@ -3074,14 +2971,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;

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 <[email protected]>

---
 include/linux/swap.h |  4 ++++
 mm/swapfile.c        | 38 +++++++++++++++++++++++++++++++++++---
 2 files changed, 39 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index edafd52d7ac4..6716ef236766 100644
@@ -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 */
 
 /*
  * The first page in the swap file is the swap header, which is always marked

@@ -295,6 +297,8 @@ struct swap_info_struct {
 	unsigned long *zeromap;		/* vmalloc'ed bitmap to track zero pages */
 	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 */

mm/swapfile.c +0 -0

index bceead7f9e3c..dcf09eb549db 100644

mm/swapfile.c +17 -2

 	schedule_work(&si->discard_work);
 }
 
 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);
 }
 
 /*

@@ -491,8 +499,15 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
 	VM_BUG_ON(ci->count == 0);
 	ci->count--;
 
-	if (!ci->count)
+	if (!ci->count) {
 		free_cluster(p, ci);
+		return;
+	}
+
+	if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+		list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);
+		ci->flags |= CLUSTER_FLAG_NONFULL;
+	}
 }
 
 /*

@@ -553,6 +568,19 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
 	if (tmp == SWAP_NEXT_INVALID) {
 		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);

mm/swapfile.c +1 -0

 			/*

@@ -967,6 +995,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);

Quoted 58 lines · Chris Li

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 <[email protected]>

---
 include/linux/swap.h |  4 ++++
 mm/swapfile.c        | 38 +++++++++++++++++++++++++++++++++++---
 2 files changed, 39 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index edafd52d7ac4..6716ef236766 100644
@@ -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 */
 
 /*
  * The first page in the swap file is the swap header, which is always marked

@@ -295,6 +297,8 @@ struct swap_info_struct {
      unsigned long *zeromap;         /* vmalloc'ed bitmap to track zero pages */
      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 */

mm/swapfile.c +0 -0

index bceead7f9e3c..dcf09eb549db 100644
@@ -361,14 +361,22 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
      memset(si->swap_map + idx * SWAPFILE_CLUSTER,
                      SWAP_MAP_BAD, SWAPFILE_CLUSTER);
 

mm/swapfile.c static void swap_cluster_schedule_discard(struct swap_info_struct *si, · line 369

Quoted 7 lines

mm/swapfile.c +6 -1

-     list_add_tail(&ci->list, &si->discard_clusters);
+     VM_BUG_ON(ci->flags & CLUSTER_FLAG_FREE);
+     if (ci->flags & CLUSTER_FLAG_NONFULL)
+             list_move_tail(&ci->list, &si->discard_clusters);
+     else
+             list_add_tail(&ci->list, &si->discard_clusters);
+     ci->flags = 0;

As Ryan pointed out before, it's better to clear the specific bit instead of assigning 0. This will make code future proof.

Quoted 45 lines

mm/swapfile.c +21 -2

      schedule_work(&si->discard_work);
 }
 
 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);
 }
 
 /*

@@ -491,8 +499,15 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      VM_BUG_ON(ci->count == 0);
      ci->count--;
 
-     if (!ci->count)
+     if (!ci->count) {
              free_cluster(p, ci);
+             return;
+     }
+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);
+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -553,6 +568,19 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
      if (tmp == SWAP_NEXT_INVALID) {
              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 = cluster_index(si, ci) * SWAPFILE_CLUSTER;
+             } else if (!list_empty(&si->nonfull_clusters[order])) {
+                     ci = list_first_entry(&si->nonfull_clusters[order],
+                                           struct swap_cluster_info, list);

mm/swapfile.c static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si, · line 585

Quoted 6 lines

mm/swapfile.c +4 -0

+                     list_del(&ci->list);
+                     spin_lock(&ci->lock);
+                     ci->flags = 0;
+                     spin_unlock(&ci->lock);
                      tmp = cluster_index(si, ci) * SWAPFILE_CLUSTER;
              } else if (!list_empty(&si->discard_clusters)) {

We should check discard_clusters before nonfull clusters.

Quoted 11 lines

mm/swapfile.c +1 -0

                      /*

@@ -967,6 +995,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);

mm/swapfile.c static int setup_swap_map_and_extents(struct swap_info_struct *p, · line 2959

Quoted 9 lines

mm/swapfile.c +3 -0

@@ -2922,6 +2951,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)

--
Best Regards,
Huang, Ying

Quoted 3 lines · Ying

Chris Li <[email protected]> writes:

Quoted 15 lines

Quoted 15 lines

/*

mm/swapfile.c +9 -0

@@ -553,6 +568,19 @@ static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
      if (tmp == SWAP_NEXT_INVALID) {
              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 = cluster_index(si, ci) * SWAPFILE_CLUSTER;
+             } else if (!list_empty(&si->nonfull_clusters[order])) {
+                     ci = list_first_entry(&si->nonfull_clusters[order],
+                                           struct swap_cluster_info, list);

Quoted 8 lines

mm/swapfile.c static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si, · line 585

Quoted 6 lines

mm/swapfile.c +4 -0

+                     list_del(&ci->list);
+                     spin_lock(&ci->lock);
+                     ci->flags = 0;
+                     spin_unlock(&ci->lock);
                      tmp = cluster_index(si, ci) * SWAPFILE_CLUSTER;
              } else if (!list_empty(&si->discard_clusters)) {

We should check discard_clusters before nonfull clusters.

And the reason behind that is?

I see the discard_cluster can take a long time. It will take a synchronous wait for the issuing the discard command. Why not just use the nonfull list and return immediately. When the discard command finished. It will show up in the free list anyway.

BTW, what is your take on my previous analysis of the current SSD prefer write new cluster can wear out the SSD faster?

I think it might be useful to provide users an option to choose to write a non full list first. The trade off is more friendly to SSD wear out than preferring to write new blocks. If you keep doing the swap long enough, there will be no new free cluster anyway.

The example I give in this email:

https://lore.kernel.org/linux-mm/CACePvbXGBNC9WzzL4s2uB2UciOkV6nb4bKKkc5TBZP6QuHS_aQ@mail.gmail.com/

Chris

Quoted 14 lines

Quoted 14 lines

mm/swapfile.c +1 -0

                      /*

@@ -967,6 +995,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);

@@ -2922,6 +2951,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);
 

Quoted 6 lines

mm/swapfile.c static int setup_swap_map_and_extents(struct swap_info_struct *p, · line 2959

Quoted 6 lines

mm/swapfile.c +3 -0

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

Quoted 2 lines

BTW, what is your take on my previous analysis of the current SSD prefer write new cluster can wear out the SSD faster?

No. I don't agree with you on that. However, my knowledge on SSD wearing out algorithm is quite limited.

Quoted 4 lines

I think it might be useful to provide users an option to choose to write a non full list first. The trade off is more friendly to SSD wear out than preferring to write new blocks. If you keep doing the swap long enough, there will be no new free cluster anyway.

It depends on workloads. Some workloads may demonstrate better spatial locality.

Quoted 20 lines

The example I give in this email:

https://lore.kernel.org/linux-mm/CACePvbXGBNC9WzzL4s2uB2UciOkV6nb4bKKkc5TBZP6QuHS_aQ@mail.gmail.com/

Chris

Quoted 14 lines

Quoted 14 lines

                      /*

mm/swapfile.c +1 -0

@@ -967,6 +995,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);

@@ -2922,6 +2951,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);
 

Quoted 6 lines

Quoted 6 lines

mm/swapfile.c static int setup_swap_map_and_extents(struct swap_info_struct *p, · line 2959

Quoted 6 lines

mm/swapfile.c +3 -0

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

--
Best Regards,
Huang, Ying

Quoted 3 lines · Ying

Quoted 2 lines

BTW, what is your take on my previous analysis of the current SSD prefer write new cluster can wear out the SSD faster?

Quoted 2 lines

No. I don't agree with you on that. However, my knowledge on SSD wearing out algorithm is quite limited.

Hi Ying,

Can you please clarify. You said you have limited knowledge on SSD wearing internals. Does that mean you have low confidence in your verdict?

I would like to understand your reasoning for the disagreement. Starting from which part of my analysis you are disagreeing with.

At the same time, we can consult someone who works in the SSD space and understand the SSD internal wearing better.

I see this is a serious issue for using SSD as swapping for data center usage cases. In your laptop usage case, you are not using the LLM training 24/7 right? So it still fits the usage model of the occasional user of the swap file. It might not be as big a deal. In the data center workload, e.g. Google's swap write 24/7. The amount of data swapped out is much higher than typical laptop usage as well. There the SSD wearing out issue would be much higher because the SSD is under constant write and much bigger swap usage.

I am claiming that *some* SSD would have a higher internal write amplification factor if doing random 4K write all over the drive, than random 4K write to a small area of the drive.
I do believe having a different swap out policy controlling preferring old vs new clusters is beneficial to the data center SSD swap usage case.
It come downs to:
1) SSD are slow to erase. So most of the SSD performance erases at a huge erase block size.
2) SSD remaps the logical block address to the internal erase block. Most of the new data rewritten, regardless of the logical block address of the SSD drive, grouped together and written to the erase block.
3) When new data is overridden to the old logical data address, SSD firmware marks those over-written data as obsolete. The discard command has the similar effect without introducing new data.
4) When the SSD driver runs out of new erase block, it would need to GC the old fragmented erased block and pertectial write out of old data to make room for new erase block. Where the discard command can be beneficial. It tells the SSD firmware which part of the old data the GC process can just ignore and skip rewriting.

GC of the obsolete logical blocks is a general hard problem for the SSD.

I am not claiming every SSD has this kind of behavior, but it is common enough to be worth providing an option.

Quoted 7 lines

Quoted 4 lines

I think it might be useful to provide users an option to choose to write a non full list first. The trade off is more friendly to SSD wear out than preferring to write new blocks. If you keep doing the swap long enough, there will be no new free cluster anyway.

It depends on workloads. Some workloads may demonstrate better spatial locality.

Yes, agree that it may happen or may not happen depending on the workload . The random distribution swap entry is a common pattern we need to consider as well. The odds are against us. As in the quoted email where I did the calculation, the odds of getting the whole cluster free in the random model is very low, 4.4E10-15 even if we are only using 1/16 swap entries in the swapfile.

From: Kairui Song <[email protected]>

Currently when we are freeing mTHP folios from swap cache, we free then one by one and put each entry into swap slot cache. Slot cache is designed to reduce the overhead by batching the freeing, but mTHP swap entries are already continuous so they can be batch freed without it already, it saves litle overhead, or even increase overhead for larger mTHP.

What's more, mTHP entries could stay in swap cache for a while. Contiguous swap entry is an rather rare resource so releasing them directly can help improve mTHP allocation success rate when under pressure.

Signed-off-by Kairui Song <[email protected]>

---
 mm/swapfile.c | 59 ++++++++++++++++++++++++++---------------------------------

 1 file changed, 26 insertions(+), 33 deletions(-)

mm/swapfile.c +26 -34

index 34e6ea13e8e4..9b63b2262cc2 100644
@@ -479,20 +479,21 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
  }
 
  /*
- * The cluster ci decreases one usage. If the usage counter becomes 0,
+ * The cluster ci decreases @nr_pages usage. If the usage counter becomes 0,
   * which means no page in the cluster is in use, 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 *ci)
+static void dec_cluster_info_page(struct swap_info_struct *p,
+                                 struct swap_cluster_info *ci, int nr_pages)
  {
         if (!p->cluster_info)
                 return;
 
-       VM_BUG_ON(ci->count == 0);
+       VM_BUG_ON(ci->count < nr_pages);
         VM_BUG_ON(cluster_is_free(ci));
         lockdep_assert_held(&p->lock);
         lockdep_assert_held(&ci->lock);
-       ci->count--;
+       ci->count -= nr_pages;
 
         if (!ci->count) {
                 free_cluster(p, ci);

@@ -998,19 +999,6 @@ static int scan_swap_map_slots(struct swap_info_struct *si,
         return n_ret;
  }
 
-static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx)
-{
-       unsigned long offset = idx * SWAPFILE_CLUSTER;
-       struct swap_cluster_info *ci;
-
-       ci = lock_cluster(si, offset);
-       memset(si->swap_map + offset, 0, SWAPFILE_CLUSTER);
-       ci->count = 0;
-       free_cluster(si, ci);
-       unlock_cluster(ci);
-       swap_range_free(si, offset, SWAPFILE_CLUSTER);
-}
-
  int get_swap_pages(int n_goal, swp_entry_t swp_entries[], int entry_order)
  {
         int order = swap_entry_order(entry_order);

@@ -1269,21 +1257,28 @@ static unsigned char __swap_entry_free(struct swap_info_struct *p,
         return usage;
  }
 
-static void swap_entry_free(struct swap_info_struct *p, swp_entry_t entry)
+/*
+ * Drop the last HAS_CACHE flag of swap entries, caller have to
+ * ensure all entries belong to the same cgroup.
+ */
+static void swap_entry_range_free(struct swap_info_struct *p, swp_entry_t entry,
+                                 unsigned int nr_pages)
  {
-       struct swap_cluster_info *ci;
         unsigned long offset = swp_offset(entry);
-       unsigned char count;
+       unsigned char *map = p->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+       struct swap_cluster_info *ci;
 
         ci = lock_cluster(p, offset);
-       count = p->swap_map[offset];
-       VM_BUG_ON(count != SWAP_HAS_CACHE);
-       p->swap_map[offset] = 0;
-       dec_cluster_info_page(p, ci);
+       do {
+               VM_BUG_ON(*map != SWAP_HAS_CACHE);
+               *map = 0;
+       } while (++map < map_end);
+       dec_cluster_info_page(p, ci, nr_pages);
         unlock_cluster(ci);
 
-       mem_cgroup_uncharge_swap(entry, 1);
-       swap_range_free(p, offset, 1);
+       mem_cgroup_uncharge_swap(entry, nr_pages);
+       swap_range_free(p, offset, nr_pages);
  }
 
  static void cluster_swap_free_nr(struct swap_info_struct *sis,

@@ -1343,7 +1338,6 @@ void swap_free_nr(swp_entry_t entry, int nr_pages)
  void put_swap_folio(struct folio *folio, swp_entry_t entry)
  {
         unsigned long offset = swp_offset(entry);
-       unsigned long idx = offset / SWAPFILE_CLUSTER;
         struct swap_cluster_info *ci;
         struct swap_info_struct *si;
         unsigned char *map;

@@ -1356,19 +1350,18 @@ void put_swap_folio(struct folio *folio, swp_entry_t entry)
                 return;
 
         ci = lock_cluster_or_swap_info(si, offset);
-       if (size == SWAPFILE_CLUSTER) {
+       if (size > 1) {
                 map = si->swap_map + offset;
-               for (i = 0; i < SWAPFILE_CLUSTER; i++) {
+               for (i = 0; i < size; i++) {
                         val = map[i];
                         VM_BUG_ON(!(val & SWAP_HAS_CACHE));
                         if (val == SWAP_HAS_CACHE)
                                 free_entries++;
                 }
-               if (free_entries == SWAPFILE_CLUSTER) {
+               if (free_entries == size) {
                         unlock_cluster_or_swap_info(si, ci);
                         spin_lock(&si->lock);
-                       mem_cgroup_uncharge_swap(entry, SWAPFILE_CLUSTER);
-                       swap_free_cluster(si, idx);
+                       swap_entry_range_free(si, entry, size);
                         spin_unlock(&si->lock);
                         return;
                 }

@@ -1413,7 +1406,7 @@ void swapcache_free_entries(swp_entry_t *entries, int n)
         for (i = 0; i < n; ++i) {
                 p = swap_info_get_cont(entries[i], prev);
                 if (p)
-                       swap_entry_free(p, entries[i]);
+                       swap_entry_range_free(p, entries[i], 1);
                 prev = p;
         }
         if (p)
 
--

2.46.0.rc1.232.g9752f9e123-goog

Quoted 10 lines · On Wed, Jul 31, 2024 at 6:49 PM <[email protected]> wrote:

From: Kairui Song <[email protected]>

Currently when we are freeing mTHP folios from swap cache, we free then one by one and put each entry into swap slot cache. Slot cache is designed to reduce the overhead by batching the freeing, but mTHP swap entries are already continuous so they can be batch freed without it already, it saves litle overhead, or even increase overhead for larger mTHP.

Quoted 6 lines

What's more, mTHP entries could stay in swap cache for a while. Contiguous swap entry is an rather rare resource so releasing them directly can help improve mTHP allocation success rate when under pressure.

Signed-off-by Kairui Song <[email protected]>

Acked-by Barry Song <[email protected]>

I believe this is the right direction to take. Currently, entries are released one by one, even when they are contiguous in the swap file(those nr_pages entries are definitely in the same cluster and same si), leading to numerous lock and unlock operations.
This approach provides batched support.

free_swap_and_cache_nr() has the same issue, so I drafted a patch based on your code. I wonder if you can also help test and review before I send it officially:

From 4bed5c08bc0f7769ee2849812acdad70c4e32ead Mon Sep 17 00:00:00 2001
From: Barry Song <[email protected]>
Date: Sat, 3 Aug 2024 20:21:14 +1200
Subject: [PATCH RFC] mm: attempt to batch free swap entries for zap_pte_range()

Zhiguo reported that swap release could be a serious bottleneck during process exits[1]. With mTHP, we have the opportunity to batch free swaps.
Thanks to the work of Chris and Kairui[2], I was able to achieve this optimization with minimal code changes by building on their efforts.

[1] https://lore.kernel.org/linux-mm/[email protected]/
[2] https://lore.kernel.org/linux-mm/[email protected]/

Signed-off-by Barry Song <[email protected]>

---
 mm/swapfile.c | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

mm/swapfile.c +30 -0

index ea023fc25d08..9def6dba8d26 100644
@@ -156,6 +156,25 @@ static bool swap_is_has_cache(struct swap_info_struct *si,
        return true;
 }
 
+static bool swap_is_last_map(struct swap_info_struct *si,
+                             unsigned long offset, int nr_pages,
+                             bool *any_only_cache)
+{
+       unsigned char *map = si->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+       bool cached = false;
+
+       do {
+               if ((*map & ~SWAP_HAS_CACHE) != 1)
+                       return false;
+               if (*map & SWAP_HAS_CACHE)
+                       cached = true;
+       } while (++map < map_end);
+
+       *any_only_cache = cached;
+       return true;
+}
+
 /*
  * returns number of pages in the folio that backs the swap entry. If positive,
  * the folio was reclaimed. If negative, the folio was not reclaimed. If 0, no

@@ -1808,6 +1827,29 @@ void free_swap_and_cache_nr(swp_entry_t entry, int nr)
        if (WARN_ON(end_offset > si->max))
                goto out;
 
+       if (nr > 1) {
+               struct swap_cluster_info *ci;
+               bool batched_free;
+               int i;
+
+               ci = lock_cluster_or_swap_info(si, start_offset);
+               if ((batched_free = swap_is_last_map(si, start_offset, nr, &any_only_cache))) {
+                       for (i = 0; i < nr; i++)
+                               WRITE_ONCE(si->swap_map[start_offset + i], SWAP_HAS_CACHE);
+               }
+               unlock_cluster_or_swap_info(si, ci);

mm/swapfile.c +3 -1

+       }
+
        /*
         * First free all entries in the range.
         */

@@ -1828,6 +1870,7 @@ void free_swap_and_cache_nr(swp_entry_t entry, int nr)
        if (!any_only_cache)
                goto out;
 
+reclaim:
        /*
         * Now go back over the range trying to reclaim the swap cache. This is
         * more efficient for large folios because we will only try to reclaim
--

2.34.1

Quoted 135 lines

---
 mm/swapfile.c | 59 ++++++++++++++++++++++++++---------------------------------
 1 file changed, 26 insertions(+), 33 deletions(-)

mm/swapfile.c +26 -34

index 34e6ea13e8e4..9b63b2262cc2 100644
@@ -479,20 +479,21 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
 }
 
 /*
- * The cluster ci decreases one usage. If the usage counter becomes 0,
+ * The cluster ci decreases @nr_pages usage. If the usage counter becomes 0,
  * which means no page in the cluster is in use, 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 *ci)
+static void dec_cluster_info_page(struct swap_info_struct *p,
+                                 struct swap_cluster_info *ci, int nr_pages)
 {
        if (!p->cluster_info)
                return;
 
-       VM_BUG_ON(ci->count == 0);
+       VM_BUG_ON(ci->count < nr_pages);
        VM_BUG_ON(cluster_is_free(ci));
        lockdep_assert_held(&p->lock);
        lockdep_assert_held(&ci->lock);
-       ci->count--;
+       ci->count -= nr_pages;
 
        if (!ci->count) {
                free_cluster(p, ci);

@@ -998,19 +999,6 @@ static int scan_swap_map_slots(struct swap_info_struct *si,
        return n_ret;
 }
 
-static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx)
-{
-       unsigned long offset = idx * SWAPFILE_CLUSTER;
-       struct swap_cluster_info *ci;
-
-       ci = lock_cluster(si, offset);
-       memset(si->swap_map + offset, 0, SWAPFILE_CLUSTER);
-       ci->count = 0;
-       free_cluster(si, ci);
-       unlock_cluster(ci);
-       swap_range_free(si, offset, SWAPFILE_CLUSTER);
-}
-
 int get_swap_pages(int n_goal, swp_entry_t swp_entries[], int entry_order)
 {
        int order = swap_entry_order(entry_order);

@@ -1269,21 +1257,28 @@ static unsigned char __swap_entry_free(struct swap_info_struct *p,
        return usage;
 }
 
-static void swap_entry_free(struct swap_info_struct *p, swp_entry_t entry)
+/*
+ * Drop the last HAS_CACHE flag of swap entries, caller have to
+ * ensure all entries belong to the same cgroup.
+ */
+static void swap_entry_range_free(struct swap_info_struct *p, swp_entry_t entry,
+                                 unsigned int nr_pages)
 {
-       struct swap_cluster_info *ci;
        unsigned long offset = swp_offset(entry);
-       unsigned char count;
+       unsigned char *map = p->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+       struct swap_cluster_info *ci;
 
        ci = lock_cluster(p, offset);
-       count = p->swap_map[offset];
-       VM_BUG_ON(count != SWAP_HAS_CACHE);
-       p->swap_map[offset] = 0;
-       dec_cluster_info_page(p, ci);
+       do {
+               VM_BUG_ON(*map != SWAP_HAS_CACHE);
+               *map = 0;
+       } while (++map < map_end);
+       dec_cluster_info_page(p, ci, nr_pages);
        unlock_cluster(ci);
 
-       mem_cgroup_uncharge_swap(entry, 1);
-       swap_range_free(p, offset, 1);
+       mem_cgroup_uncharge_swap(entry, nr_pages);
+       swap_range_free(p, offset, nr_pages);
 }
 
 static void cluster_swap_free_nr(struct swap_info_struct *sis,

@@ -1343,7 +1338,6 @@ void swap_free_nr(swp_entry_t entry, int nr_pages)
 void put_swap_folio(struct folio *folio, swp_entry_t entry)
 {
        unsigned long offset = swp_offset(entry);
-       unsigned long idx = offset / SWAPFILE_CLUSTER;
        struct swap_cluster_info *ci;
        struct swap_info_struct *si;
        unsigned char *map;

@@ -1356,19 +1350,18 @@ void put_swap_folio(struct folio *folio, swp_entry_t entry)
                return;
 
        ci = lock_cluster_or_swap_info(si, offset);
-       if (size == SWAPFILE_CLUSTER) {
+       if (size > 1) {
                map = si->swap_map + offset;
-               for (i = 0; i < SWAPFILE_CLUSTER; i++) {
+               for (i = 0; i < size; i++) {
                        val = map[i];
                        VM_BUG_ON(!(val & SWAP_HAS_CACHE));
                        if (val == SWAP_HAS_CACHE)
                                free_entries++;
                }
-               if (free_entries == SWAPFILE_CLUSTER) {
+               if (free_entries == size) {
                        unlock_cluster_or_swap_info(si, ci);
                        spin_lock(&si->lock);
-                       mem_cgroup_uncharge_swap(entry, SWAPFILE_CLUSTER);
-                       swap_free_cluster(si, idx);
+                       swap_entry_range_free(si, entry, size);
                        spin_unlock(&si->lock);
                        return;
                }

@@ -1413,7 +1406,7 @@ void swapcache_free_entries(swp_entry_t *entries, int n)
        for (i = 0; i < n; ++i) {
                p = swap_info_get_cont(entries[i], prev);
                if (p)
-                       swap_entry_free(p, entries[i]);
+                       swap_entry_range_free(p, entries[i], 1);
                prev = p;
        }
        if (p)
 
--

Quoted 2 lines

2.46.0.rc1.232.g9752f9e123-goog

Thanks
Barry

From: Kairui Song <[email protected]>

Currently we free the reclaimed slots through slot cache even if the slot is required to be empty immediately. As a result the reclaim caller will see the slot still occupied even after a successful reclaim, and need to keep reclaiming until slot cache get flushed. This caused ineffective or over reclaim when SWAP is under stress.

So introduce a new flag allowing the slot to be emptied bypassing the slot cache.

Signed-off-by Kairui Song <[email protected]>

---
 mm/swapfile.c | 152 +++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 109 insertions(+), 43 deletions(-)

mm/swapfile.c +64 -10

index 9b63b2262cc2..4c0fc0409d3c 100644
@@ -53,8 +53,15 @@
 static bool swap_count_continued(struct swap_info_struct *, pgoff_t,
                                 unsigned char);
 static void free_swap_count_continuations(struct swap_info_struct *);
+static void swap_entry_range_free(struct swap_info_struct *si, swp_entry_t entry,
+                                 unsigned int nr_pages);
 static void swap_range_alloc(struct swap_info_struct *si, unsigned long offset,
                             unsigned int nr_entries);
+static bool folio_swapcache_freeable(struct folio *folio);
+static struct swap_cluster_info *lock_cluster_or_swap_info(
+               struct swap_info_struct *si, unsigned long offset);
+static void unlock_cluster_or_swap_info(struct swap_info_struct *si,
+                                       struct swap_cluster_info *ci);
 
 static DEFINE_SPINLOCK(swap_lock);
 static unsigned int nr_swapfiles;

@@ -129,8 +136,25 @@ static inline unsigned char swap_count(unsigned char ent)
  * corresponding page
  */
 #define TTRS_UNMAPPED          0x2
-/* Reclaim the swap entry if swap is getting full*/
+/* Reclaim the swap entry if swap is getting full */
 #define TTRS_FULL              0x4
+/* Reclaim directly, bypass the slot cache and don't touch device lock */
+#define TTRS_DIRECT            0x8
+
+static bool swap_is_has_cache(struct swap_info_struct *si,
+                             unsigned long offset, int nr_pages)
+{
+       unsigned char *map = si->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+
+       do {
+               VM_BUG_ON(!(*map & SWAP_HAS_CACHE));
+               if (*map != SWAP_HAS_CACHE)
+                       return false;
+       } while (++map < map_end);
+
+       return true;
+}
 
 /*
  * returns number of pages in the folio that backs the swap entry. If positive,

@@ -141,12 +165,22 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
                                 unsigned long offset, unsigned long flags)
 {
        swp_entry_t entry = swp_entry(si->type, offset);
+       struct address_space *address_space = swap_address_space(entry);
+       struct swap_cluster_info *ci;
        struct folio *folio;
-       int ret = 0;
+       int ret, nr_pages;
+       bool need_reclaim;
 
-       folio = filemap_get_folio(swap_address_space(entry), swap_cache_index(entry));
+       folio = filemap_get_folio(address_space, swap_cache_index(entry));
        if (IS_ERR(folio))
                return 0;
+
+       /* offset could point to the middle of a large folio */
+       entry = folio->swap;
+       offset = swp_offset(entry);
+       nr_pages = folio_nr_pages(folio);
+       ret = -nr_pages;
+
        /*
         * When this function is called from scan_swap_map_slots() and it's
         * called by vmscan.c at reclaiming folios. So we hold a folio lock

@@ -154,14 +188,50 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
         * case and you should use folio_free_swap() with explicit folio_lock()
         * in usual operations.
         */
-       if (folio_trylock(folio)) {
-               if ((flags & TTRS_ANYWAY) ||
-                   ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
-                   ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)))
-                       ret = folio_free_swap(folio);
-               folio_unlock(folio);
+       if (!folio_trylock(folio))
+               goto out;
+
+       need_reclaim = ((flags & TTRS_ANYWAY) ||
+                       ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
+                       ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)));
+       if (!need_reclaim || !folio_swapcache_freeable(folio))
+               goto out_unlock;
+
+       /*
+        * It's safe to delete the folio from swap cache only if the folio's
+        * swap_map is HAS_CACHE only, which means the slots have no page table
+        * reference or pending writeback, and can't be allocated to others.
+        */
+       ci = lock_cluster_or_swap_info(si, offset);
+       need_reclaim = swap_is_has_cache(si, offset, nr_pages);
+       unlock_cluster_or_swap_info(si, ci);
+       if (!need_reclaim)
+               goto out_unlock;
+
+       if (!(flags & TTRS_DIRECT)) {
+               /* Free through slot cache */
+               delete_from_swap_cache(folio);
+               folio_set_dirty(folio);
+               ret = nr_pages;
+               goto out_unlock;
        }
-       ret = ret ? folio_nr_pages(folio) : -folio_nr_pages(folio);
+

mm/swapfile.c +35 -34

+       swap_entry_range_free(si, entry, nr_pages);
+       spin_unlock(&si->lock);
+       ret = nr_pages;
+out_unlock:
+       folio_unlock(folio);
+out:
        folio_put(folio);
        return ret;
 }

@@ -903,7 +973,7 @@ static int scan_swap_map_slots(struct swap_info_struct *si,
        if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
                int swap_was_freed;
                spin_unlock(&si->lock);
-               swap_was_freed = __try_to_reclaim_swap(si, offset, TTRS_ANYWAY);
+               swap_was_freed = __try_to_reclaim_swap(si, offset, TTRS_ANYWAY | TTRS_DIRECT);
                spin_lock(&si->lock);
                /* entry was freed successfully, try to use this again */
                if (swap_was_freed > 0)

@@ -1340,9 +1410,6 @@ void put_swap_folio(struct folio *folio, swp_entry_t entry)
        unsigned long offset = swp_offset(entry);
        struct swap_cluster_info *ci;
        struct swap_info_struct *si;
-       unsigned char *map;
-       unsigned int i, free_entries = 0;
-       unsigned char val;
        int size = 1 << swap_entry_order(folio_order(folio));
 
        si = _swap_info_get(entry);

@@ -1350,23 +1417,14 @@ void put_swap_folio(struct folio *folio, swp_entry_t entry)
                return;
 
        ci = lock_cluster_or_swap_info(si, offset);
-       if (size > 1) {
-               map = si->swap_map + offset;
-               for (i = 0; i < size; i++) {
-                       val = map[i];
-                       VM_BUG_ON(!(val & SWAP_HAS_CACHE));
-                       if (val == SWAP_HAS_CACHE)
-                               free_entries++;
-               }
-               if (free_entries == size) {
-                       unlock_cluster_or_swap_info(si, ci);
-                       spin_lock(&si->lock);
-                       swap_entry_range_free(si, entry, size);
-                       spin_unlock(&si->lock);
-                       return;
-               }
+       if (size > 1 && swap_is_has_cache(si, offset, size)) {
+               unlock_cluster_or_swap_info(si, ci);
+               spin_lock(&si->lock);
+               swap_entry_range_free(si, entry, size);
+               spin_unlock(&si->lock);
+               return;
        }
-       for (i = 0; i < size; i++, entry.val++) {
+       for (int i = 0; i < size; i++, entry.val++) {
                if (!__swap_entry_free_locked(si, offset + i, SWAP_HAS_CACHE)) {
                        unlock_cluster_or_swap_info(si, ci);
                        free_swap_slot(entry);

@@ -1526,16 +1584,7 @@ static bool folio_swapped(struct folio *folio)
        return swap_page_trans_huge_swapped(si, entry, folio_order(folio));
 }
 
-/**
- * folio_free_swap() - Free the swap space used for this folio.
- * @folio: The folio to remove.
- *
- * If swap is getting full, or if there are no more mappings of this folio,
- * then call folio_free_swap to free its swap space.
- *
- * Return: true if we were able to release the swap space.
- */
-bool folio_free_swap(struct folio *folio)
+static bool folio_swapcache_freeable(struct folio *folio)
 {
        VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio);
 

@@ -1543,8 +1592,6 @@ bool folio_free_swap(struct folio *folio)
                return false;
        if (folio_test_writeback(folio))
                return false;
-       if (folio_swapped(folio))
-               return false;
 
        /*
         * Once hibernation has begun to create its image of memory,

@@ -1564,6 +1611,25 @@ bool folio_free_swap(struct folio *folio)
        if (pm_suspended_storage())
                return false;
 
+       return true;
+}
+
+/**
+ * folio_free_swap() - Free the swap space used for this folio.
+ * @folio: The folio to remove.
+ *
+ * If swap is getting full, or if there are no more mappings of this folio,
+ * then call folio_free_swap to free its swap space.
+ *
+ * Return: true if we were able to release the swap space.
+ */
+bool folio_free_swap(struct folio *folio)
+{
+       if (!folio_swapcache_freeable(folio))
+               return false;
+       if (folio_swapped(folio))
+               return false;
+
        delete_from_swap_cache(folio);
        folio_set_dirty(folio);
        return true;

@@ -1640,7 +1706,7 @@ void free_swap_and_cache_nr(swp_entry_t entry, int nr)
                         * to the next boundary.
                         */
                        nr = __try_to_reclaim_swap(si, offset,
-                                             TTRS_UNMAPPED | TTRS_FULL);
+                                                  TTRS_UNMAPPED | TTRS_FULL);
                        if (nr == 0)
                                nr = 1;
                        else if (nr < 0)
 
--

2.46.0.rc1.232.g9752f9e123-goog

Quoted 134 lines · On Wed, Jul 31, 2024 at 2:49 PM <[email protected]> wrote:

From: Kairui Song <[email protected]>

Currently we free the reclaimed slots through slot cache even if the slot is required to be empty immediately. As a result the reclaim caller will see the slot still occupied even after a successful reclaim, and need to keep reclaiming until slot cache get flushed. This caused ineffective or over reclaim when SWAP is under stress.

So introduce a new flag allowing the slot to be emptied bypassing the slot cache.

Signed-off-by Kairui Song <[email protected]>

---
 mm/swapfile.c | 152 +++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 109 insertions(+), 43 deletions(-)

mm/swapfile.c +69 -10

index 9b63b2262cc2..4c0fc0409d3c 100644
@@ -53,8 +53,15 @@
 static bool swap_count_continued(struct swap_info_struct *, pgoff_t,
                                 unsigned char);
 static void free_swap_count_continuations(struct swap_info_struct *);
+static void swap_entry_range_free(struct swap_info_struct *si, swp_entry_t entry,
+                                 unsigned int nr_pages);
 static void swap_range_alloc(struct swap_info_struct *si, unsigned long offset,
                             unsigned int nr_entries);
+static bool folio_swapcache_freeable(struct folio *folio);
+static struct swap_cluster_info *lock_cluster_or_swap_info(
+               struct swap_info_struct *si, unsigned long offset);
+static void unlock_cluster_or_swap_info(struct swap_info_struct *si,
+                                       struct swap_cluster_info *ci);
 
 static DEFINE_SPINLOCK(swap_lock);
 static unsigned int nr_swapfiles;

@@ -129,8 +136,25 @@ static inline unsigned char swap_count(unsigned char ent)
  * corresponding page
  */
 #define TTRS_UNMAPPED          0x2
-/* Reclaim the swap entry if swap is getting full*/
+/* Reclaim the swap entry if swap is getting full */
 #define TTRS_FULL              0x4
+/* Reclaim directly, bypass the slot cache and don't touch device lock */
+#define TTRS_DIRECT            0x8
+
+static bool swap_is_has_cache(struct swap_info_struct *si,
+                             unsigned long offset, int nr_pages)
+{
+       unsigned char *map = si->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+
+       do {
+               VM_BUG_ON(!(*map & SWAP_HAS_CACHE));
+               if (*map != SWAP_HAS_CACHE)
+                       return false;
+       } while (++map < map_end);
+
+       return true;
+}
 
 /*
  * returns number of pages in the folio that backs the swap entry. If positive,

@@ -141,12 +165,22 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
                                 unsigned long offset, unsigned long flags)
 {
        swp_entry_t entry = swp_entry(si->type, offset);
+       struct address_space *address_space = swap_address_space(entry);
+       struct swap_cluster_info *ci;
        struct folio *folio;
-       int ret = 0;
+       int ret, nr_pages;
+       bool need_reclaim;
 
-       folio = filemap_get_folio(swap_address_space(entry), swap_cache_index(entry));
+       folio = filemap_get_folio(address_space, swap_cache_index(entry));
        if (IS_ERR(folio))
                return 0;
+
+       /* offset could point to the middle of a large folio */
+       entry = folio->swap;
+       offset = swp_offset(entry);
+       nr_pages = folio_nr_pages(folio);
+       ret = -nr_pages;
+
        /*
         * When this function is called from scan_swap_map_slots() and it's
         * called by vmscan.c at reclaiming folios. So we hold a folio lock

@@ -154,14 +188,50 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
         * case and you should use folio_free_swap() with explicit folio_lock()
         * in usual operations.
         */
-       if (folio_trylock(folio)) {
-               if ((flags & TTRS_ANYWAY) ||
-                   ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
-                   ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)))
-                       ret = folio_free_swap(folio);
-               folio_unlock(folio);
+       if (!folio_trylock(folio))
+               goto out;
+
+       need_reclaim = ((flags & TTRS_ANYWAY) ||
+                       ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
+                       ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)));
+       if (!need_reclaim || !folio_swapcache_freeable(folio))
+               goto out_unlock;
+
+       /*
+        * It's safe to delete the folio from swap cache only if the folio's
+        * swap_map is HAS_CACHE only, which means the slots have no page table
+        * reference or pending writeback, and can't be allocated to others.
+        */
+       ci = lock_cluster_or_swap_info(si, offset);
+       need_reclaim = swap_is_has_cache(si, offset, nr_pages);
+       unlock_cluster_or_swap_info(si, ci);
+       if (!need_reclaim)
+               goto out_unlock;
+
+       if (!(flags & TTRS_DIRECT)) {
+               /* Free through slot cache */
+               delete_from_swap_cache(folio);
+               folio_set_dirty(folio);
+               ret = nr_pages;
+               goto out_unlock;
        }
-       ret = ret ? folio_nr_pages(folio) : -folio_nr_pages(folio);
+
+       xa_lock_irq(&address_space->i_pages);
+       __delete_from_swap_cache(folio, entry, NULL);
+       xa_unlock_irq(&address_space->i_pages);
+       folio_ref_sub(folio, nr_pages);
+       folio_set_dirty(folio);

mm/swapfile.c static int __try_to_reclaim_swap(struct swap_info_struct *si, · line 228

Quoted 5 lines

mm/swapfile.c +5 -0

+
+       spin_lock(&si->lock);
+       /* Only sinple page folio can be backed by zswap */
+       if (!nr_pages)
+               zswap_invalidate(entry);

I am trying to figure out if I am mad :-) Does nr_pages == 0 means single page folio?

Quoted 136 lines · Barry Song

Quoted 134 lines · On Wed, Jul 31, 2024 at 2:49 PM <[email protected]> wrote:

From: Kairui Song <[email protected]>

Currently we free the reclaimed slots through slot cache even if the slot is required to be empty immediately. As a result the reclaim caller will see the slot still occupied even after a successful reclaim, and need to keep reclaiming until slot cache get flushed. This caused ineffective or over reclaim when SWAP is under stress.

So introduce a new flag allowing the slot to be emptied bypassing the slot cache.

Signed-off-by Kairui Song <[email protected]>

---
 mm/swapfile.c | 152 +++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 109 insertions(+), 43 deletions(-)

mm/swapfile.c +69 -10

index 9b63b2262cc2..4c0fc0409d3c 100644
@@ -53,8 +53,15 @@
 static bool swap_count_continued(struct swap_info_struct *, pgoff_t,
                                 unsigned char);
 static void free_swap_count_continuations(struct swap_info_struct *);
+static void swap_entry_range_free(struct swap_info_struct *si, swp_entry_t entry,
+                                 unsigned int nr_pages);
 static void swap_range_alloc(struct swap_info_struct *si, unsigned long offset,
                             unsigned int nr_entries);
+static bool folio_swapcache_freeable(struct folio *folio);
+static struct swap_cluster_info *lock_cluster_or_swap_info(
+               struct swap_info_struct *si, unsigned long offset);
+static void unlock_cluster_or_swap_info(struct swap_info_struct *si,
+                                       struct swap_cluster_info *ci);
 
 static DEFINE_SPINLOCK(swap_lock);
 static unsigned int nr_swapfiles;

@@ -129,8 +136,25 @@ static inline unsigned char swap_count(unsigned char ent)
  * corresponding page
  */
 #define TTRS_UNMAPPED          0x2
-/* Reclaim the swap entry if swap is getting full*/
+/* Reclaim the swap entry if swap is getting full */
 #define TTRS_FULL              0x4
+/* Reclaim directly, bypass the slot cache and don't touch device lock */
+#define TTRS_DIRECT            0x8
+
+static bool swap_is_has_cache(struct swap_info_struct *si,
+                             unsigned long offset, int nr_pages)
+{
+       unsigned char *map = si->swap_map + offset;
+       unsigned char *map_end = map + nr_pages;
+
+       do {
+               VM_BUG_ON(!(*map & SWAP_HAS_CACHE));
+               if (*map != SWAP_HAS_CACHE)
+                       return false;
+       } while (++map < map_end);
+
+       return true;
+}
 
 /*
  * returns number of pages in the folio that backs the swap entry. If positive,

@@ -141,12 +165,22 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
                                 unsigned long offset, unsigned long flags)
 {
        swp_entry_t entry = swp_entry(si->type, offset);
+       struct address_space *address_space = swap_address_space(entry);
+       struct swap_cluster_info *ci;
        struct folio *folio;
-       int ret = 0;
+       int ret, nr_pages;
+       bool need_reclaim;
 
-       folio = filemap_get_folio(swap_address_space(entry), swap_cache_index(entry));
+       folio = filemap_get_folio(address_space, swap_cache_index(entry));
        if (IS_ERR(folio))
                return 0;
+
+       /* offset could point to the middle of a large folio */
+       entry = folio->swap;
+       offset = swp_offset(entry);
+       nr_pages = folio_nr_pages(folio);
+       ret = -nr_pages;
+
        /*
         * When this function is called from scan_swap_map_slots() and it's
         * called by vmscan.c at reclaiming folios. So we hold a folio lock

@@ -154,14 +188,50 @@ static int __try_to_reclaim_swap(struct swap_info_struct *si,
         * case and you should use folio_free_swap() with explicit folio_lock()
         * in usual operations.
         */
-       if (folio_trylock(folio)) {
-               if ((flags & TTRS_ANYWAY) ||
-                   ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
-                   ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)))
-                       ret = folio_free_swap(folio);
-               folio_unlock(folio);
+       if (!folio_trylock(folio))
+               goto out;
+
+       need_reclaim = ((flags & TTRS_ANYWAY) ||
+                       ((flags & TTRS_UNMAPPED) && !folio_mapped(folio)) ||
+                       ((flags & TTRS_FULL) && mem_cgroup_swap_full(folio)));
+       if (!need_reclaim || !folio_swapcache_freeable(folio))
+               goto out_unlock;
+
+       /*
+        * It's safe to delete the folio from swap cache only if the folio's
+        * swap_map is HAS_CACHE only, which means the slots have no page table
+        * reference or pending writeback, and can't be allocated to others.
+        */
+       ci = lock_cluster_or_swap_info(si, offset);
+       need_reclaim = swap_is_has_cache(si, offset, nr_pages);
+       unlock_cluster_or_swap_info(si, ci);
+       if (!need_reclaim)
+               goto out_unlock;
+
+       if (!(flags & TTRS_DIRECT)) {
+               /* Free through slot cache */
+               delete_from_swap_cache(folio);
+               folio_set_dirty(folio);
+               ret = nr_pages;
+               goto out_unlock;
        }
-       ret = ret ? folio_nr_pages(folio) : -folio_nr_pages(folio);
+
+       xa_lock_irq(&address_space->i_pages);
+       __delete_from_swap_cache(folio, entry, NULL);
+       xa_unlock_irq(&address_space->i_pages);
+       folio_ref_sub(folio, nr_pages);
+       folio_set_dirty(folio);

Quoted 9 lines

mm/swapfile.c static int __try_to_reclaim_swap(struct swap_info_struct *si, · line 228

Quoted 5 lines

mm/swapfile.c +5 -0

+
+       spin_lock(&si->lock);
+       /* Only sinple page folio can be backed by zswap */
+       if (!nr_pages)
+               zswap_invalidate(entry);

I am trying to figure out if I am mad :-) Does nr_pages == 0 means single page folio?

Hi Barry

I'm sorry, this should be nr_pages == 1, I messed up order and nr, as zswap only works for single page folios.

Quoted 10 lines

Quoted 9 lines

Quoted 5 lines

+
+       spin_lock(&si->lock);
+       /* Only sinple page folio can be backed by zswap */
+       if (!nr_pages)
+               zswap_invalidate(entry);

I am trying to figure out if I am mad :-)  Does nr_pages == 0 means single page folio?

Quoted 4 lines

Hi Barry

I'm sorry, this should be nr_pages == 1, I messed up order and nr, as zswap only works for single page folios.

Ack. Should be  nr_pages == 1.

Barry, thanks for catching that.

Chris

From: Kairui Song <[email protected]>

This commit implements reclaim during scan for cluster allocator.

Cluster scanning were unable to reuse SWAP_HAS_CACHE slots, which could result in low allocation success rate or early OOM.

So to ensure maximum allocation success rate, integrate reclaiming with scanning. If found a range of suitable swap slots but fragmented due to HAS_CACHE, just try to reclaim the slots.

Signed-off-by Kairui Song <[email protected]>

---
 include/linux/swap.h |   1 +
 mm/swapfile.c        | 140 +++++++++++++++++++++++++++++++++++++++------------
 2 files changed, 110 insertions(+), 31 deletions(-)

include/linux/swap.h +1 -0

index 5a14b6c65949..9eb740563d63 100644
@@ -302,6 +302,7 @@ struct swap_info_struct {
                                        /* list of cluster that contains at least one free slot */
        struct list_head frag_clusters[SWAP_NR_ORDERS];
                                        /* list of cluster that are fragmented or contented */
+       unsigned int frag_cluster_nr[SWAP_NR_ORDERS];
        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 */

mm/swapfile.c +76 -16

index eb3e387e86b2..50e7f600a9a1 100644
@@ -513,6 +513,10 @@ static void free_cluster(struct swap_info_struct *si, struct swap_cluster_info *
        VM_BUG_ON(ci->count != 0);
        lockdep_assert_held(&si->lock);
        lockdep_assert_held(&ci->lock);
+
+       if (ci->flags & CLUSTER_FLAG_FRAG)
+               si->frag_cluster_nr[ci->order]--;
+
        /*
         * If the swap is discardable, prepare discard the cluster
         * instead of free it immediately. The cluster will be freed

@@ -572,31 +576,84 @@ static void dec_cluster_info_page(struct swap_info_struct *p,
 
        if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
                VM_BUG_ON(ci->flags & CLUSTER_FLAG_FREE);
-               if (ci->flags & CLUSTER_FLAG_FRAG)
+               if (ci->flags & CLUSTER_FLAG_FRAG) {
+                       p->frag_cluster_nr[ci->order]--;
                        list_move_tail(&ci->list, &p->nonfull_clusters[ci->order]);
-               else
+               } else {
                        list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);
+               }
                ci->flags = CLUSTER_FLAG_NONFULL;
        }
 }
 
-static inline bool cluster_scan_range(struct swap_info_struct *si, unsigned int start,
-                                     unsigned int nr_pages)
+static bool cluster_reclaim_range(struct swap_info_struct *si,
+                                 struct swap_cluster_info *ci,
+                                 unsigned long start, unsigned long end)
 {
-       unsigned char *p = si->swap_map + start;
-       unsigned char *end = p + nr_pages;
+       unsigned char *map = si->swap_map;
+       unsigned long offset;
+
+       spin_unlock(&ci->lock);
+       spin_unlock(&si->lock);
+
+       for (offset = start; offset < end; offset++) {
+               switch (READ_ONCE(map[offset])) {
+               case 0:
+                       continue;
+               case SWAP_HAS_CACHE:
+                       if (__try_to_reclaim_swap(si, offset, TTRS_ANYWAY | TTRS_DIRECT) > 0)
+                               continue;
+                       goto out;
+               default:
+                       goto out;
+               }
+       }
+out:
+       spin_lock(&si->lock);
+       spin_lock(&ci->lock);
 
-       while (p < end)
-               if (*p++)
+       /*
+        * Recheck the range no matter reclaim succeeded or not, the slot
+        * could have been be freed while we are not holding the lock.
+        */
+       for (offset = start; offset < end; offset++)
+               if (READ_ONCE(map[offset]))
                        return false;
 
        return true;
 }
 
+static bool cluster_scan_range(struct swap_info_struct *si,
+                              struct swap_cluster_info *ci,
+                              unsigned long start, unsigned int nr_pages)
+{
+       unsigned long offset, end = start + nr_pages;
+       unsigned char *map = si->swap_map;
+       bool need_reclaim = false;
 
-static inline void cluster_alloc_range(struct swap_info_struct *si, struct swap_cluster_info *ci,
-                                               unsigned int start, unsigned char usage,
-                                               unsigned int order)
+       for (offset = start; offset < end; offset++) {
+               switch (READ_ONCE(map[offset])) {
+               case 0:
+                       continue;
+               case SWAP_HAS_CACHE:
+                       if (!vm_swap_full())
+                               return false;
+                       need_reclaim = true;
+                       continue;
+               default:
+                       return false;
+               }
+       }
+
+       if (need_reclaim)
+               return cluster_reclaim_range(si, ci, start, end);
+
+       return true;
+}
+
+static void cluster_alloc_range(struct swap_info_struct *si, struct swap_cluster_info *ci,
+                               unsigned int start, unsigned char usage,
+                               unsigned int order)
 {
        unsigned int nr_pages = 1 << order;
 

@@ -615,6 +672,8 @@ static inline void cluster_alloc_range(struct swap_info_struct *si, struct swap_
        if (ci->count == SWAPFILE_CLUSTER) {
                VM_BUG_ON(!(ci->flags &
                          (CLUSTER_FLAG_FREE | CLUSTER_FLAG_NONFULL | CLUSTER_FLAG_FRAG)));
+               if (ci->flags & CLUSTER_FLAG_FRAG)
+                       si->frag_cluster_nr[ci->order]--;
                list_del(&ci->list);
                ci->flags = 0;
        }

@@ -640,7 +699,7 @@ static unsigned int alloc_swap_scan_cluster(struct swap_info_struct *si, unsigne
        }
 
        while (offset <= end) {
-               if (cluster_scan_range(si, offset, nr_pages)) {
+               if (cluster_scan_range(si, ci, offset, nr_pages)) {
                        cluster_alloc_range(si, ci, offset, usage, order);
                        *foundp = offset;
                        if (ci->count == SWAPFILE_CLUSTER) {

@@ -668,9 +727,8 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o
                                              unsigned char usage)
 {
        struct percpu_cluster *cluster;
-       struct swap_cluster_info *ci, *n;
+       struct swap_cluster_info *ci;
        unsigned int offset, found = 0;
-       LIST_HEAD(fraged);
 
 new_cluster:
        lockdep_assert_held(&si->lock);

@@ -690,25 +748,42 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o
        }
 
        if (order < PMD_ORDER) {
-               list_for_each_entry_safe(ci, n, &si->nonfull_clusters[order], list) {
-                       list_move_tail(&ci->list, &fraged);
+               unsigned int frags = 0;
+
+               while (!list_empty(&si->nonfull_clusters[order])) {
+                       ci = list_first_entry(&si->nonfull_clusters[order],

mm/swapfile.c +12 -1

-                       list_for_each_entry_safe(ci, n, &si->frag_clusters[order], list) {
+                       /*
+                        * Nonfull clusters are moved to frag tail if we reached
+                        * here, count them too, don't over scan the frag list.
+                        */
+                       while (frags < si->frag_cluster_nr[order]) {
+                               ci = list_first_entry(&si->frag_clusters[order],
+                                                     struct swap_cluster_info, list);
+                               /*
+                                * Rotate the frag list to iterate, they were all failing
+                                * high order allocation or moved here due to per-CPU usage,
+                                * this help keeping usable cluster ahead.
+                                */

mm/swapfile.c +15 -13

        }
 
        if (found)

@@ -729,25 +804,28 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o
 
        /* Order 0 stealing from higher order */
        for (int o = 1; o < PMD_ORDER; o++) {
-               if (!list_empty(&si->frag_clusters[o])) {
+               /*
+                * Clusters here have at least one usable slots and can't fail order 0
+                * allocation, but reclaim may drop si->lock and race with another user.
+                */
+               while (!list_empty(&si->frag_clusters[o])) {
                        ci = list_first_entry(&si->frag_clusters[o],
                                              struct swap_cluster_info, list);
-                       offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci), &found,
-                                                        0, usage);
-                       VM_BUG_ON(!found);
-                       goto done;
+                       offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci),
+                                                        &found, 0, usage);
+                       if (found)
+                               goto done;
                }
 
-               if (!list_empty(&si->nonfull_clusters[o])) {
-                       ci = list_first_entry(&si->nonfull_clusters[o], struct swap_cluster_info,
-                                             list);
+               while (!list_empty(&si->nonfull_clusters[o])) {
+                       ci = list_first_entry(&si->nonfull_clusters[o],
+                                             struct swap_cluster_info, list);
                        offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci),
                                                         &found, 0, usage);
-                       VM_BUG_ON(!found);
-                       goto done;
+                       if (found)
+                               goto done;
                }
        }
-
 done:
        cluster->next[order] = offset;
        return found;

@@ -3053,6 +3131,7 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p,
        for (i = 0; i < SWAP_NR_ORDERS; i++) {
                INIT_LIST_HEAD(&p->nonfull_clusters[i]);
                INIT_LIST_HEAD(&p->frag_clusters[i]);
+               p->frag_cluster_nr[i] = 0;
        }
 
        for (i = 0; i < swap_header->info.nr_badpages; i++) {

@@ -3096,7 +3175,6 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p,
        if (!cluster_info)
                return nr_extents;
 
-
        /*
         * Reduce false cache line sharing between cluster_info and
         * sharing same address space.
 
--

2.46.0.rc1.232.g9752f9e123-goog