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 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 |  26 +++---
 mm/swapfile.c        | 225 ++++++++++++++-------------------------------------
 2 files changed, 70 insertions(+), 181 deletions(-)

include/linux/swap.h +1 -3

index e473fe6cfb7a..e9be95468fc7 100644
@@ -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

include/linux/swap.h +2 -7

 /*
  * 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.
  */

@@ -301,7 +295,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 +326,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 +3 -73

index f7224bc1320c..f70d25005d2c 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);

mm/swapfile.c +15 -38

-		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);
+		idx = cluster_index(si, ci);
 		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);
+		spin_unlock(&ci->lock);
 	}
 }
 

mm/swapfile.c +13 -13

-	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 +439,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 +456,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;
 }
 
 /*

mm/swapfile.c +7 -10

+ * 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);
 }
 
 /*

mm/swapfile.c +17 -15

 	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 +548,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 +963,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 +1238,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 +2916,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 +2968,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;

Quoted 52 lines · Chris Li

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

---
 include/linux/swap.h |  26 +++---
 mm/swapfile.c        | 225 ++++++++++++++-------------------------------------
 2 files changed, 70 insertions(+), 181 deletions(-)

include/linux/swap.h +2 -3

index e473fe6cfb7a..e9be95468fc7 100644
@@ -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;        /*

include/linux/swap.h enum { · line 253

Quoted 6 lines

include/linux/swap.h +2 -3

                               * 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.

nit: correspond -> corresponding

include/linux/swap.h enum { · line 255

Quoted 5 lines

include/linux/swap.h +1 -2

                               */
-     unsigned int data:24;
-     unsigned int flags:8;
+     u16 count;

Just to make sure I've understood correctly; count can safely be 16 bit (down from previous 24 bit) because the max it will ever be is the number of swap

entries in the cluster, and that's currently no bigger than 512, and in future we wouldn't expect it to ever get bigger than 8192 (number of pages in PMD-order for arm64 64K base pages). 8192 is represented in 14 bits.

include/linux/swap.h enum { · line 260

Quoted 7 lines

include/linux/swap.h +3 -1

+     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 */
+

nit: why the blank line?

Quoted 139 lines

include/linux/swap.h +2 -7

 /*
  * 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.
  */

@@ -301,7 +295,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 +326,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 +3 -81

index f7224bc1320c..f70d25005d2c 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
-              */

mm/swapfile.c static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si, · line 429

Quoted 2 lines

mm/swapfile.c +0 -2

-             ci_tail = ci + tail;
-             spin_lock_nested(&ci_tail->lock, SINGLE_DEPTH_NESTING);

Just to confirm my understanding, there was never previously any list manipulation where the si->lock wasn't held, so this ensuring that both clusters were locked for list manipulation was unnecessary? I don't see any extra places where you are taking si->lock, so I guess that must be the case (or your new regime is unsafe...).

Quoted 92 lines

mm/swapfile.c +15 -38

-             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);
+             idx = cluster_index(si, ci);
              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);
+             spin_unlock(&ci->lock);
      }
 }
 

@@ -521,20 +418,20 @@ static void swap_users_ref_free(struct percpu_ref *ref)
      complete(&si->comp);
 }
 

mm/swapfile.c static void swap_users_ref_free(struct percpu_ref *ref) · line 423

Quoted 5 lines

mm/swapfile.c +2 -2

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

nit: long line; consider separating the variable declaration and assignment?

Quoted 59 lines

mm/swapfile.c +13 -13

-     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 +439,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 +456,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 +478,20 @@ static void inc_cluster_info_page(struct swap_info_struct *p,
 }
 

mm/swapfile.c static void inc_cluster_info_page(struct swap_info_struct *p, · line 482

Quoted 6 lines

mm/swapfile.c +2 -3

 /*
- * 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

nit: "in using" -> "in use"

Quoted 25 lines

mm/swapfile.c +7 -10

+ * 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);
 }
 

mm/swapfile.c scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si, · line 507

Quoted 7 lines

mm/swapfile.c +1 -1

 /*

@@ -611,10 +504,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);

nit: long line; consider splitting variable declaration and assignment.

nit: You're removed the blank line between variable declarations and statements; did you run checkpatch.pl?

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

---
 include/linux/swap.h |  26 +++---
 mm/swapfile.c        | 225 ++++++++++++++-------------------------------------
 2 files changed, 70 insertions(+), 181 deletions(-)

include/linux/swap.h +10 -16

index e473fe6cfb7a..e9be95468fc7 100644
@@ -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.
  */

@@ -301,7 +295,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 +326,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 +42 -149

index f7224bc1320c..f70d25005d2c 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);
+		idx = cluster_index(si, ci);
 		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);
+		spin_unlock(&ci->lock);
 	}
 }
 

@@ -521,20 +418,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(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 +439,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 +456,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 +478,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);
 }
 
 /*

mm/swapfile.c +12 -10

 		cluster_is_free(&si->cluster_info[offset]);
 
 	if (!conflict)

@@ -655,10 +548,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 +963,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 +1238,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 +2916,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 +2968,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]))

Quoted 19 lines · Chris Li

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.

Quoted 5 lines

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

                             ~~~~
                             swap_cluster_info ?

Quoted 369 lines

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 |  26 +++---
 mm/swapfile.c        | 225 ++++++++++++++-------------------------------------
 2 files changed, 70 insertions(+), 181 deletions(-)

include/linux/swap.h +10 -16

index e473fe6cfb7a..e9be95468fc7 100644
@@ -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.
  */

@@ -301,7 +295,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 +326,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 +42 -149

index f7224bc1320c..f70d25005d2c 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);
+             idx = cluster_index(si, ci);
              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);
+             spin_unlock(&ci->lock);
      }
 }
 

@@ -521,20 +418,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(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 +439,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 +456,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 +478,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);
 }
 

mm/swapfile.c scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si, · line 508

Quoted 8 lines

mm/swapfile.c +1 -1

 /*

@@ -611,10 +504,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;

mm/swapfile.c scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si, · line 510

Quoted 4 lines

mm/swapfile.c +2 -2

-     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 &&

offset != cluster_index(si, first) ?

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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644

mm/swapfile.c +4 -1

 	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);
 }
 
 /*

mm/swapfile.c +14 -0

+		ci->flags |= CLUSTER_FLAG_NONFULL;
+	}
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+			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)) {
 			/*

mm/swapfile.c +3 -0

 	free_cluster(si, ci);
 	unlock_cluster(ci);

@@ -2919,6 +2944,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)

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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644
@@ -361,14 +361,21 @@ 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 364

Quoted 2 lines

mm/swapfile.c +1 -1

-     list_add_tail(&ci->list, &si->discard_clusters);
+     if (ci->flags)

I'm not sure this is future proof; what happens if a flag is added in future that does not indicate that the cluster is on a list. Perhaps explicitly check CLUSTER_FLAG_NONFULL? Or if (!list_empty(&ci->list)).

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

Quoted 5 lines

mm/swapfile.c +4 -0

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

Bug: (I think?) the cluster ends up on the discard_clusters list and swap_do_scheduled_discard() calls __free_cluster() which will then call

list_add_tail() to put it on the free_clusters list. But since it is on the discard_list at that point, shouldn't it call list_move_tail()?

Quoted 18 lines

mm/swapfile.c +4 -1

      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,7 +498,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      ci->count--;
 

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 501

Quoted 3 lines

mm/swapfile.c +1 -1

      if (!ci->count)
-             free_cluster(p, ci);
+             return free_cluster(p, ci);

nit: I'm not sure what the kernel style guide says about this, but I'm not a huge fan of returning void. I'd find it clearer if you just turn the below if into an else if.

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 504

Quoted 4 lines

mm/swapfile.c +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

Quoted 25 lines

mm/swapfile.c +14 -0

+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+                     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)) {
                      /*

mm/swapfile.c static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx) · line 992

Quoted 6 lines

mm/swapfile.c +1 -0

@@ -964,6 +988,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;

Wonder if it would be better to put this in __free_cluster()?

Quoted 60 lines · Ryan Roberts

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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644
@@ -361,14 +361,21 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
      memset(si->swap_map + idx * SWAPFILE_CLUSTER,
                      SWAP_MAP_BAD, SWAPFILE_CLUSTER);
 

Quoted 6 lines

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

Quoted 2 lines

mm/swapfile.c +1 -1

-     list_add_tail(&ci->list, &si->discard_clusters);
+     if (ci->flags)

I'm not sure this is future proof; what happens if a flag is added in future that does not indicate that the cluster is on a list. Perhaps explicitly check CLUSTER_FLAG_NONFULL? Or if (!list_empty(&ci->list)).

Currently flags are only used to track which list it is on.

BTW, this
line has changed to check for explicite which list in patch 3 the big rewrite. I can move that line change to patch 2 if you want.

Quoted 9 lines

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

Quoted 6 lines

mm/swapfile.c +4 -0

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

Bug: (I think?) the cluster ends up on the discard_clusters list and swap_do_scheduled_discard() calls __free_cluster() which will then call

swap_do_scheduled_discard() delete the entry from discard list.

The flag does not track the discard list state.

Quoted 2 lines

list_add_tail() to put it on the free_clusters list. But since it is on the discard_list at that point, shouldn't it call list_move_tail()?

See above. Call list_move_tail() would be a mistake.

Quoted 18 lines

Quoted 18 lines

mm/swapfile.c +4 -1

      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,7 +498,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      ci->count--;
 

Quoted 7 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 501

Quoted 3 lines

mm/swapfile.c +1 -1

      if (!ci->count)
-             free_cluster(p, ci);
+             return free_cluster(p, ci);

nit: I'm not sure what the kernel style guide says about this, but I'm not a huge fan of returning void. I'd find it clearer if you just turn the below if into an else if.

I try to avoid 'else if' if possible.
Changed to

if (!ci->count) {
              free_cluster(p, ci);
              return;
}

Quoted 19 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 504

Quoted 5 lines

mm/swapfile.c +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

Quoted 3 lines

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

Those behaviors will be fine
tuned after the patch 3 big rewrite. Try to make this patch simple.

Quoted 4 lines

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

That is in patch 3 as well. This patch is just doing the bare minimum to introduce the nonfull list.

Quoted 25 lines

Quoted 25 lines

mm/swapfile.c +14 -0

+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+                     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)) {
                      /*

Quoted 8 lines

mm/swapfile.c static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx) · line 992

Quoted 6 lines

mm/swapfile.c +1 -0

@@ -964,6 +988,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;

Wonder if it would be better to put this in __free_cluster()?

Both flags and order were moved to __free_cluster() in patch 3 of this series. The order is best assigned together with flags when the cluster changes the list.

Thanks for the review. The patch 3 big rewrite is the heavy lifting.

Chris

Quoted 68 lines · Chris Li

Quoted 66 lines · Ryan Roberts

Quoted 55 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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644

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

Quoted 5 lines

mm/swapfile.c +1 -1

@@ -361,14 +361,21 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
      memset(si->swap_map + idx * SWAPFILE_CLUSTER,
                      SWAP_MAP_BAD, SWAPFILE_CLUSTER);
 
-     list_add_tail(&ci->list, &si->discard_clusters);
+     if (ci->flags)

I'm not sure this is future proof; what happens if a flag is added in future that does not indicate that the cluster is on a list. Perhaps explicitly check CLUSTER_FLAG_NONFULL? Or if (!list_empty(&ci->list)).

Quoted 1 line

Currently flags are only used to track which list it is on.

Yes, I get that it works correctly at the moment. I just don't think it's wise for the code to assume that any flag being set means its on a list; that feels fragile for future.

Quoted 4 lines

BTW, this
line has changed to check for explicite which list in patch 3 the big rewrite. I can move that line change to patch 2 if you want.

That would get my vote; let's make every patch as good as it can be.

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

mm/swapfile.c +4 -0

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

Quoted 4 lines

Quoted 2 lines

Bug: (I think?) the cluster ends up on the discard_clusters list and swap_do_scheduled_discard() calls __free_cluster() which will then call

swap_do_scheduled_discard() delete the entry from discard list.

Ahh yes, my bad!

Quoted 33 lines

The flag does not track the discard list state.

Quoted 2 lines

list_add_tail() to put it on the free_clusters list. But since it is on the discard_list at that point, shouldn't it call list_move_tail()?

See above. Call list_move_tail() would be a mistake.

Quoted 18 lines

Quoted 18 lines

mm/swapfile.c +4 -1

      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,7 +498,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      ci->count--;
 

Quoted 7 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 501

Quoted 3 lines

mm/swapfile.c +1 -1

      if (!ci->count)
-             free_cluster(p, ci);
+             return free_cluster(p, ci);

nit: I'm not sure what the kernel style guide says about this, but I'm not a huge fan of returning void. I'd find it clearer if you just turn the below if into an else if.

Quoted 6 lines

I try to avoid 'else if' if possible.
Changed to

if (!ci->count) {
              free_cluster(p, ci);
              return;
}

ok

Quoted 23 lines

Quoted 22 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 504

Quoted 5 lines

mm/swapfile.c +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

Quoted 2 lines

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

Oh, from the title, "RFC: mm: swap: seperate SSD allocation from scan_swap_map_slots()" I assumed that was just a refactoring of the code to separate the SSD and HDD code paths. Personally I'd prefer to see the refactoring separated from behavioural changes.

Since the patch was titled RFC and I thought it was just refactoring, I was deferring review. But sounds like it is actually required to realize the test results quoted on the cover letter?

Quoted 9 lines

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

Quoted 3 lines

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

But if 2 CPUs have the same cluster, isn't there a pathalogical case where cpuA could be slightly ahead of cpuB so that cpuA allocates all the free pages and

cpuB just ends up scanning and finding nothing to allocate. I think do want to share the cluster when you really need to, but try to avoid it if there are other options, and I think moving the cluster to the end of the list might be a way to help that?

Quoted 2 lines

Those behaviors will be fine
tuned after the patch 3 big rewrite. Try to make this patch simple.

Quoted 42 lines

Quoted 4 lines

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

That is in patch 3 as well. This patch is just doing the bare minimum to introduce the nonfull list.

Quoted 33 lines

Quoted 26 lines

mm/swapfile.c +14 -0

+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+                     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)) {
                      /*

mm/swapfile.c static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx) · line 992

Quoted 5 lines

mm/swapfile.c +1 -0

@@ -964,6 +988,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;

Wonder if it would be better to put this in __free_cluster()?

Quoted 5 lines

Both flags and order were moved to __free_cluster() in patch 3 of this series. The order is best assigned together with flags when the cluster changes the list.

Thanks for the review. The patch 3 big rewrite is the heavy lifting.

OK, but sounds like patch 3 isn't really RFC after all, but a crucial part of the series? I'll try to take a look at it today.

Quoted 70 lines · Ryan Roberts

Quoted 68 lines · Chris Li

Quoted 66 lines · Ryan Roberts

Quoted 55 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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644

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

Quoted 5 lines

mm/swapfile.c +1 -1

@@ -361,14 +361,21 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
      memset(si->swap_map + idx * SWAPFILE_CLUSTER,
                      SWAP_MAP_BAD, SWAPFILE_CLUSTER);
 
-     list_add_tail(&ci->list, &si->discard_clusters);
+     if (ci->flags)

I'm not sure this is future proof; what happens if a flag is added in future that does not indicate that the cluster is on a list. Perhaps explicitly check CLUSTER_FLAG_NONFULL? Or if (!list_empty(&ci->list)).

Quoted 5 lines

Quoted 1 line

Currently flags are only used to track which list it is on.

Yes, I get that it works correctly at the moment. I just don't think it's wise for the code to assume that any flag being set means its on a list; that feels fragile for future.

ACK.

Quoted 6 lines

Quoted 4 lines

BTW, this
line has changed to check for explicite which list in patch 3 the big rewrite. I can move that line change to patch 2 if you want.

That would get my vote; let's make every patch as good as it can be.

Done.

Quoted 80 lines

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

mm/swapfile.c +4 -0

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

Quoted 4 lines

Quoted 2 lines

Bug: (I think?) the cluster ends up on the discard_clusters list and swap_do_scheduled_discard() calls __free_cluster() which will then call

swap_do_scheduled_discard() delete the entry from discard list.

Ahh yes, my bad!

Quoted 33 lines

The flag does not track the discard list state.

Quoted 2 lines

list_add_tail() to put it on the free_clusters list. But since it is on the discard_list at that point, shouldn't it call list_move_tail()?

See above. Call list_move_tail() would be a mistake.

Quoted 18 lines

Quoted 18 lines

mm/swapfile.c +4 -1

      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,7 +498,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      ci->count--;
 

Quoted 7 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 501

Quoted 3 lines

mm/swapfile.c +1 -1

      if (!ci->count)
-             free_cluster(p, ci);
+             return free_cluster(p, ci);

nit: I'm not sure what the kernel style guide says about this, but I'm not a huge fan of returning void. I'd find it clearer if you just turn the below if into an else if.

Quoted 6 lines

I try to avoid 'else if' if possible.
Changed to

if (!ci->count) {
              free_cluster(p, ci);
              return;
}

ok

Quoted 23 lines

Quoted 22 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 504

Quoted 5 lines

mm/swapfile.c +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

Quoted 7 lines

Quoted 2 lines

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

Oh, from the title, "RFC: mm: swap: seperate SSD allocation from scan_swap_map_slots()" I assumed that was just a refactoring of the code to separate the SSD and HDD code paths. Personally I'd prefer to see the refactoring separated from behavioural changes.

It is not a refactoring. It is a big rewrite of the swap allocator using the cluster. Behavior change is expected. The goal is completely removing the brute force scanning of swap_map[] array for cluster swap allocation.

Quoted 4 lines

Since the patch was titled RFC and I thought it was just refactoring, I was deferring review. But sounds like it is actually required to realize the test results quoted on the cover letter?

Yes, required because it handles the previous fall out case try_ssd() failed. This big rewrite has gone through a lot of testing and bug fix. It is pretty stable now. The only reason I keep it as RFC is because it is not feature complete. Currently it does not do swap cache reclaim. The next version will have swap cache reclaim and remove the RFC.

Quoted 13 lines

Quoted 12 lines

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

Quoted 2 lines

But if 2 CPUs have the same cluster, isn't there a pathalogical case where cpuA could be slightly ahead of cpuB so that cpuA allocates all the free pages and

That happens to exist per cpu next pointer already. When the other CPU advances to the next cluster pointer, it can cross with the other CPU's next cluster pointer.

Quoted 4 lines

cpuB just ends up scanning and finding nothing to allocate. I think do want to share the cluster when you really need to, but try to avoid it if there are other options, and I think moving the cluster to the end of the list might be a way to help that?

Simply moving to the end of the list can create a possible deadloop when all clusters have been scanned and not available swap range found.

We have tried many different approaches including moving to the end of the list. It can cause more fragmentation because each CPU allocates their swap slot cache (64 entries) from a different cluster.

Quoted 2 lines

Quoted 2 lines

Those behaviors will be fine
tuned after the patch 3 big rewrite. Try to make this patch simple.

Again, I want to keep it simple here so patch 3 can land.

Quoted 46 lines

Quoted 46 lines

Quoted 4 lines

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

That is in patch 3 as well. This patch is just doing the bare minimum to introduce the nonfull list.

Quoted 25 lines

Quoted 25 lines

mm/swapfile.c +14 -0

+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+                     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)) {
                      /*

Quoted 8 lines

mm/swapfile.c static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx) · line 992

Quoted 6 lines

mm/swapfile.c +1 -0

@@ -964,6 +988,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;

Wonder if it would be better to put this in __free_cluster()?

Both flags and order were moved to __free_cluster() in patch 3 of this series. The order is best assigned together with flags when the cluster changes the list.

Quoted 4 lines

Quoted 1 line

Thanks for the review. The patch 3 big rewrite is the heavy lifting.

OK, but sounds like patch 3 isn't really RFC after all, but a crucial part of the series? I'll try to take a look at it today.

Yes, it is the cluster swap allocator big rewrite.

Thank you for taking a look.

Quoted 206 lines · Chris Li

Quoted 70 lines · Ryan Roberts

Quoted 68 lines · Chris Li

Quoted 66 lines · Ryan Roberts

Quoted 55 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        | 34 +++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 3 deletions(-)

include/linux/swap.h +4 -0

index e9be95468fc7..db8d6000c116 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 */
 
 
 /*

@@ -296,6 +298,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 f70d25005d2c..e13a33664cfa 100644

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

Quoted 5 lines

mm/swapfile.c +1 -1

@@ -361,14 +361,21 @@ static void swap_cluster_schedule_discard(struct swap_info_struct *si,
      memset(si->swap_map + idx * SWAPFILE_CLUSTER,
                      SWAP_MAP_BAD, SWAPFILE_CLUSTER);
 
-     list_add_tail(&ci->list, &si->discard_clusters);
+     if (ci->flags)

I'm not sure this is future proof; what happens if a flag is added in future that does not indicate that the cluster is on a list. Perhaps explicitly check CLUSTER_FLAG_NONFULL? Or if (!list_empty(&ci->list)).

Quoted 5 lines

Quoted 1 line

Currently flags are only used to track which list it is on.

Yes, I get that it works correctly at the moment. I just don't think it's wise for the code to assume that any flag being set means its on a list; that feels fragile for future.

ACK.

Quoted 6 lines

Quoted 4 lines

BTW, this
line has changed to check for explicite which list in patch 3 the big rewrite. I can move that line change to patch 2 if you want.

That would get my vote; let's make every patch as good as it can be.

Done.

Quoted 80 lines

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

mm/swapfile.c +4 -0

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

Quoted 4 lines

Quoted 2 lines

Bug: (I think?) the cluster ends up on the discard_clusters list and swap_do_scheduled_discard() calls __free_cluster() which will then call

swap_do_scheduled_discard() delete the entry from discard list.

Ahh yes, my bad!

Quoted 33 lines

The flag does not track the discard list state.

Quoted 2 lines

list_add_tail() to put it on the free_clusters list. But since it is on the discard_list at that point, shouldn't it call list_move_tail()?

See above. Call list_move_tail() would be a mistake.

Quoted 18 lines

Quoted 18 lines

mm/swapfile.c +4 -1

      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,7 +498,12 @@ static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste
      ci->count--;
 

Quoted 7 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 501

Quoted 3 lines

mm/swapfile.c +1 -1

      if (!ci->count)
-             free_cluster(p, ci);
+             return free_cluster(p, ci);

nit: I'm not sure what the kernel style guide says about this, but I'm not a huge fan of returning void. I'd find it clearer if you just turn the below if into an else if.

Quoted 6 lines

I try to avoid 'else if' if possible.
Changed to

if (!ci->count) {
              free_cluster(p, ci);
              return;
}

ok

Quoted 23 lines

Quoted 22 lines

mm/swapfile.c static void dec_cluster_info_page(struct swap_info_struct *p, struct swap_cluste · line 504

Quoted 5 lines

mm/swapfile.c +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

Quoted 7 lines

Quoted 2 lines

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

Oh, from the title, "RFC: mm: swap: seperate SSD allocation from scan_swap_map_slots()" I assumed that was just a refactoring of the code to separate the SSD and HDD code paths. Personally I'd prefer to see the refactoring separated from behavioural changes.

It is not a refactoring. It is a big rewrite of the swap allocator using the cluster. Behavior change is expected. The goal is completely removing the brute force scanning of swap_map[] array for cluster swap allocation.

Quoted 4 lines

Since the patch was titled RFC and I thought it was just refactoring, I was deferring review. But sounds like it is actually required to realize the test results quoted on the cover letter?

Yes, required because it handles the previous fall out case try_ssd() failed. This big rewrite has gone through a lot of testing and bug fix. It is pretty stable now. The only reason I keep it as RFC is because it is not feature complete. Currently it does not do swap cache reclaim. The next version will have swap cache reclaim and remove the RFC.

Quoted 13 lines

Quoted 12 lines

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

Quoted 6 lines

Quoted 2 lines

But if 2 CPUs have the same cluster, isn't there a pathalogical case where cpuA could be slightly ahead of cpuB so that cpuA allocates all the free pages and

That happens to exist per cpu next pointer already. When the other CPU advances to the next cluster pointer, it can cross with the other CPU's next cluster pointer.

No. si->percpu_cluster[cpu].next will keep in the current per cpu cluster only. If it doesn't do that, we should fix it.

I agree with Ryan that we should make per cpu cluster correct. A cluster in per cpu cluster shouldn't be put in nonfull list. When we scan to the end of a per cpu cluster, we can put the cluster in nonfull list if necessary. And, we should make it correct in this patch instead of later in series. I understand that you want to make the patch itself simple, but it's important to make code simple to be understood too. Consistent design choice will do that.

Quoted 9 lines

Quoted 5 lines

cpuB just ends up scanning and finding nothing to allocate. I think do want to share the cluster when you really need to, but try to avoid it if there are other options, and I think moving the cluster to the end of the list might be a way to help that?

Simply moving to the end of the list can create a possible deadloop when all clusters have been scanned and not available swap range found.

This is another reason that we should put the cluster in nonfull_clusters[order--] if there are no free swap entry with "order" in the cluster. It makes design complex to keep it in nonfull_clusters[order].

Quoted 55 lines

We have tried many different approaches including moving to the end of the list. It can cause more fragmentation because each CPU allocates their swap slot cache (64 entries) from a different cluster.

Quoted 2 lines

Quoted 2 lines

Those behaviors will be fine
tuned after the patch 3 big rewrite. Try to make this patch simple.

Again, I want to keep it simple here so patch 3 can land.

Quoted 46 lines

Quoted 46 lines

Quoted 4 lines

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

That is in patch 3 as well. This patch is just doing the bare minimum to introduce the nonfull list.

Quoted 25 lines

Quoted 25 lines

mm/swapfile.c +14 -0

+             ci->flags |= CLUSTER_FLAG_NONFULL;
+     }
 }
 
 /*

@@ -550,6 +562,18 @@ 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);
+                     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)) {
                      /*

Quoted 8 lines

mm/swapfile.c static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx) · line 992

Quoted 6 lines

mm/swapfile.c +1 -0

@@ -964,6 +988,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;

Wonder if it would be better to put this in __free_cluster()?

Both flags and order were moved to __free_cluster() in patch 3 of this series. The order is best assigned together with flags when the cluster changes the list.

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

Thanks for the review. The patch 3 big rewrite is the heavy lifting.

OK, but sounds like patch 3 isn't really RFC after all, but a crucial part of the series? I'll try to take a look at it today.

Yes, it is the cluster swap allocator big rewrite.

Thank you for taking a look.

--
Best Regards,
Huang, Ying

Quoted 8 lines · Ying

Quoted 6 lines · Chris Li

Quoted 5 lines · Ryan Roberts

Quoted 3 lines · Chris Li

Quoted 2 lines · Ryan Roberts

On 11/07/2024 08:29, Chris Li wrote:

Quoted 69 lines

Quoted 59 lines

Quoted 21 lines

Quoted 21 lines

Quoted 20 lines

Review

Quoted 3 lines

(quoted diff) +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

Quoted 7 lines

Quoted 2 lines

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

Oh, from the title, "RFC: mm: swap: seperate SSD allocation from scan_swap_map_slots()" I assumed that was just a refactoring of the code to separate the SSD and HDD code paths. Personally I'd prefer to see the refactoring separated from behavioural changes.

It is not a refactoring. It is a big rewrite of the swap allocator using the cluster. Behavior change is expected. The goal is completely removing the brute force scanning of swap_map[] array for cluster swap allocation.

Quoted 4 lines

Since the patch was titled RFC and I thought it was just refactoring, I was deferring review. But sounds like it is actually required to realize the test results quoted on the cover letter?

Yes, required because it handles the previous fall out case try_ssd() failed. This big rewrite has gone through a lot of testing and bug fix. It is pretty stable now. The only reason I keep it as RFC is because it is not feature complete. Currently it does not do swap cache reclaim. The next version will have swap cache reclaim and remove the RFC.

Quoted 13 lines

Quoted 12 lines

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

Quoted 6 lines

Quoted 2 lines

But if 2 CPUs have the same cluster, isn't there a pathalogical case where cpuA could be slightly ahead of cpuB so that cpuA allocates all the free pages and

That happens to exist per cpu next pointer already. When the other CPU advances to the next cluster pointer, it can cross with the other CPU's next cluster pointer.

No. si->percpu_cluster[cpu].next will keep in the current per cpu cluster only. If it doesn't do that, we should fix it.

Quoted 7 lines

I agree with Ryan that we should make per cpu cluster correct. A cluster in per cpu cluster shouldn't be put in nonfull list. When we scan to the end of a per cpu cluster, we can put the cluster in nonfull list if necessary. And, we should make it correct in this patch instead of later in series. I understand that you want to make the patch itself simple, but it's important to make code simple to be understood too. Consistent design choice will do that.

I think I'm actually arguing for the opposite of what you suggest here.

As I see it, there are 2 possible approaches; either a cluster is always considered exclusive to a single cpu when its set as a per-cpu cluster, so it does not appear on the nonfull list. Or a cluster is considered sharable in this case, in which case it should be added to the nonfull list.

The code at the moment sort of does both; when a cpu decides to use a cluster in the nonfull list, it removes it from that list to make it exclusive. But as soon as a single swap entry is freed from that cluster it is put back on the list. This neither-one-policy-nor-the-other seems odd to me.

I think Huang, Ying is arguing to keep it always exclusive while installed as a per-cpu cluster.

I was arguing to make it always shared. Perhaps the best
approach is to implement the exclusive policy in this patch (you'd need a flag to note if any pages were freed while in exclusive use, then when exclusive use completes, put it back on the nonfull list if the flag was set). Then migrate to the shared approach as part of the "big rewrite"?

Quoted 9 lines

Quoted 9 lines

Quoted 5 lines

cpuB just ends up scanning and finding nothing to allocate. I think do want to share the cluster when you really need to, but try to avoid it if there are other options, and I think moving the cluster to the end of the list might be a way to help that?

Simply moving to the end of the list can create a possible deadloop when all clusters have been scanned and not available swap range found.

Quoted 14 lines

This is another reason that we should put the cluster in nonfull_clusters[order--] if there are no free swap entry with "order" in the cluster. It makes design complex to keep it in nonfull_clusters[order].

Quoted 9 lines

We have tried many different approaches including moving to the end of the list. It can cause more fragmentation because each CPU allocates their swap slot cache (64 entries) from a different cluster.

Quoted 2 lines

Quoted 2 lines

Those behaviors will be fine
tuned after the patch 3 big rewrite. Try to make this patch simple.

Again, I want to keep it simple here so patch 3 can land.

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

Another potential optimization (which was in my hacked version IIRC) is to only add/remove from nonfull list when total - count crosses the (1 << order) boundary rather than when becoming completely full. You definitely won't be able to allocate order-2 if there are only 3 pages available, for example.

That is in patch 3 as well. This patch is just doing the bare minimum to introduce the nonfull list.

Quoted 9 lines · Ryan Roberts

Quoted 8 lines · Ying

Quoted 6 lines · Chris Li

Quoted 5 lines · Ryan Roberts

Quoted 3 lines · Chris Li

Quoted 2 lines · Ryan Roberts

On 11/07/2024 08:29, Chris Li wrote:

[snip]

Quoted 77 lines

Quoted 69 lines

Quoted 59 lines

Quoted 21 lines

Quoted 21 lines

Quoted 20 lines

Review

Quoted 3 lines

(quoted diff) +3 -0

+
+     if (!(ci->flags & CLUSTER_FLAG_NONFULL)) {
+             list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]);

I find the transitions when you add and remove a cluster from the nonfull_clusters list a bit strange (if I've understood correctly): It is added to the list whenever there is at least one free swap entry if not already on the list. But you take it off the list when assigning it as the current cluster for a cpu in scan_swap_map_try_ssd_cluster().

So you could have this situation:

- cpuA allocs cluster from free list (exclusive to that cpu)
- cpuA allocs 1 swap entry from current cluster
- swap entry is freed; cluster added to nonfull_clusters
- cpuB "allocs" cluster from nonfull_clusters

At this point both cpuA and cpuB share the same cluster as their current cluster. So why not just put the cluster on the nonfull_clusters list at allocation time (when removed from free_list) and only remove it from the

Quoted 7 lines

Quoted 2 lines

The big rewrite on patch 3 does that, taking it off the free list and moving it into nonfull.

Oh, from the title, "RFC: mm: swap: seperate SSD allocation from scan_swap_map_slots()" I assumed that was just a refactoring of the code to separate the SSD and HDD code paths. Personally I'd prefer to see the refactoring separated from behavioural changes.

It is not a refactoring. It is a big rewrite of the swap allocator using the cluster. Behavior change is expected. The goal is completely removing the brute force scanning of swap_map[] array for cluster swap allocation.

Quoted 4 lines

Since the patch was titled RFC and I thought it was just refactoring, I was deferring review. But sounds like it is actually required to realize the test results quoted on the cover letter?

Yes, required because it handles the previous fall out case try_ssd() failed. This big rewrite has gone through a lot of testing and bug fix. It is pretty stable now. The only reason I keep it as RFC is because it is not feature complete. Currently it does not do swap cache reclaim. The next version will have swap cache reclaim and remove the RFC.

Quoted 13 lines

Quoted 12 lines

I am only making the minimal change in this step so the big rewrite can land.

Quoted 5 lines

nonfull_clusters list when it is completely full (or at least definitely doesn't have room for an order allocation)? Then you allow "stealing" always instead of just sometimes. You would likely want to move the cluster to the end of the nonfull list when selecting it in scan_swap_map_try_ssd_cluster() to reduce the chances of multiple CPUs using the same cluster.

For nonfull clusters it is less important to avoid multiple CPU sharing the cluster. Because the cluster already has previous swap entries allocated from the previous CPU.

Quoted 6 lines

Quoted 2 lines

But if 2 CPUs have the same cluster, isn't there a pathalogical case where cpuA could be slightly ahead of cpuB so that cpuA allocates all the free pages and

That happens to exist per cpu next pointer already. When the other CPU advances to the next cluster pointer, it can cross with the other CPU's next cluster pointer.

No. si->percpu_cluster[cpu].next will keep in the current per cpu cluster only. If it doesn't do that, we should fix it.

Quoted 7 lines

I agree with Ryan that we should make per cpu cluster correct. A cluster in per cpu cluster shouldn't be put in nonfull list. When we scan to the end of a per cpu cluster, we can put the cluster in nonfull list if necessary. And, we should make it correct in this patch instead of later in series. I understand that you want to make the patch itself simple, but it's important to make code simple to be understood too. Consistent design choice will do that.

Quoted 1 line

I think I'm actually arguing for the opposite of what you suggest here.

Sorry, I misunderstood your words.

Quoted 5 lines

As I see it, there are 2 possible approaches; either a cluster is always considered exclusive to a single cpu when its set as a per-cpu cluster, so it does not appear on the nonfull list. Or a cluster is considered sharable in this case, in which case it should be added to the nonfull list.

Quoted 7 lines

The code at the moment sort of does both; when a cpu decides to use a cluster in the nonfull list, it removes it from that list to make it exclusive. But as soon as a single swap entry is freed from that cluster it is put back on the list. This neither-one-policy-nor-the-other seems odd to me.

I think Huang, Ying is arguing to keep it always exclusive while installed as a per-cpu cluster.

Yes.

Quoted 11 lines

I was arguing to make it always shared. Perhaps the best
approach is to implement the exclusive policy in this patch (you'd need a flag to note if any pages were freed while in exclusive use, then when exclusive use completes, put it back on the nonfull list if the flag was set). Then migrate to the shared approach as part of the "big rewrite"?

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

cpuB just ends up scanning and finding nothing to allocate. I think do want to share the cluster when you really need to, but try to avoid it if there are other options, and I think moving the cluster to the end of the list might be a way to help that?