Track contiguous free clusters at the tail of the mapped range in si->nr_free_tail, maintained across alloc/free/grow paths. This eliminates the backwards scan on every shrink check. Three paths maintain the counter: 1. xswap_update_free_tail(): called on cluster free. If the freed cluster is adjacent to the existing tail boundary, increment and extend backwards to include already-free clusters now connected. 2. xswap_trim_free_tail(): called on cluster allocation. If the allocated cluster lies within the tail free region, truncate the count to end just before it. 3. Grow path: nr_free_tail += nr_new — all newly mapped clusters are immediately free. xswap_try_shrink() simplifies to a threshold check: if nr_free_tail >= XSWAP_GROW_CLUSTERS → unmap Setup initializes nr_free_tail = nr_clusters_mapped - 1 (all but cluster 0 are free at the tail). Signed-off-by: Baoquan He --- include/linux/swap.h | 1 + mm/swapfile.c | 121 +++++++++++++++++++++++++++++++++++++------ 2 files changed, 105 insertions(+), 17 deletions(-) diff --git a/include/linux/swap.h b/include/linux/swap.h index 536b0e989c48..72b28116ed0f 100644 --- a/include/linux/swap.h +++ b/include/linux/swap.h @@ -252,6 +252,7 @@ struct swap_info_struct { struct vm_struct *cluster_vm; /* VM_SPARSE area for xswap dynamic cluster_info */ unsigned long nr_clusters; /* total cluster count for xswap */ unsigned long nr_clusters_mapped; /* currently mapped cluster count */ + unsigned long nr_free_tail; /* contiguous free clusters at tail */ struct mutex xswap_lock; /* serialize map/unmap operations */ #endif struct list_head free_clusters; /* free clusters list */ diff --git a/mm/swapfile.c b/mm/swapfile.c index c43c8746378e..3f536495b8cf 100644 --- a/mm/swapfile.c +++ b/mm/swapfile.c @@ -68,6 +68,9 @@ static int xswap_map_clusters(struct swap_info_struct *si, static void xswap_unmap_clusters(struct swap_info_struct *si, unsigned long start_idx, unsigned long nr); static int xswap_check_mapped(pte_t *pte, unsigned long addr, void *data); +static void xswap_trim_free_tail(struct swap_info_struct *si, unsigned long idx); +static void xswap_update_free_tail(struct swap_info_struct *si, + unsigned long freed_idx); static void xswap_try_shrink(struct swap_info_struct *si); #endif @@ -633,6 +636,7 @@ static void __free_cluster(struct swap_info_struct *si, struct swap_cluster_info move_cluster(si, ci, &si->free_clusters, CLUSTER_FLAG_FREE); ci->order = 0; #ifdef CONFIG_XSWAP + xswap_update_free_tail(si, ci - si->cluster_info); xswap_try_shrink(si); #endif } @@ -981,6 +985,9 @@ static bool __swap_cluster_alloc_entries(struct swap_info_struct *si, if (cluster_is_empty(ci)) ci->order = order; ci->count += nr_pages; +#ifdef CONFIG_XSWAP + xswap_trim_free_tail(si, cluster_index(si, ci)); +#endif swap_range_alloc(si, nr_pages); return true; @@ -1246,6 +1253,8 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, spin_unlock(&ci->lock); } spin_unlock(&si->lock); + WRITE_ONCE(si->nr_free_tail, + READ_ONCE(si->nr_free_tail) + nr_new); /* Retry allocation from the free list */ found = alloc_swap_scan_list(si, &si->free_clusters, @@ -3883,37 +3892,115 @@ static int xswap_check_mapped(pte_t *pte, unsigned long addr, void *data) } /* - * Try to shrink the cluster_info tail: unmap contiguous free clusters - * at the end of the mapped range. + * Maintain si->nr_free_tail, the number of contiguous free clusters at + * the tail of the mapped range. Called when a cluster at @freed_idx is + * freed. Provides O(1) shrink detection: if nr_free_tail is non-zero, + * the tail can be unmapped without scanning cluster_info[]. + * + * Only increments when @freed_idx is the cluster immediately before the + * existing tail region. Then scans backwards for already-free clusters + * now connected to the tail, bounded by XSWAP_GROW_CLUSTERS at a time. */ -static void xswap_try_shrink(struct swap_info_struct *si) +static void xswap_update_free_tail(struct swap_info_struct *si, + unsigned long freed_idx) { + unsigned long nr_mapped, nr_tail, tid, i; struct swap_cluster_info *ci; - unsigned long last, idx; if (!(si->flags & SWP_XSWAP)) return; - if (READ_ONCE(si->nr_clusters_mapped) <= 1) /* keep cluster 0 */ + + nr_mapped = READ_ONCE(si->nr_clusters_mapped); + nr_tail = READ_ONCE(si->nr_free_tail); + + /* Protect against concurrent shrink that races past us */ + if (nr_tail >= nr_mapped) return; - /* Find the last non-free cluster from the tail */ - last = READ_ONCE(si->nr_clusters_mapped); - while (last > 1) { - idx = last - 1; - ci = &si->cluster_info[idx]; - if (ci->count || ci->flags != CLUSTER_FLAG_FREE) + tid = nr_mapped - nr_tail - 1; + + /* Only the cluster immediately before the tail region counts */ + if (freed_idx != tid) + return; + + nr_tail++; + WRITE_ONCE(si->nr_free_tail, nr_tail); + + /* Extend: include already-free clusters now connected to the tail */ + for (i = 1; i < XSWAP_GROW_CLUSTERS; i++) { + nr_mapped = READ_ONCE(si->nr_clusters_mapped); + nr_tail = READ_ONCE(si->nr_free_tail); + if (nr_tail >= nr_mapped - 1) + break; /* reached cluster 0 */ + tid = nr_mapped - nr_tail - 1; + ci = &si->cluster_info[tid]; + + if (READ_ONCE(ci->count) || + READ_ONCE(ci->flags) != CLUSTER_FLAG_FREE) break; - last = idx; + nr_tail++; + WRITE_ONCE(si->nr_free_tail, nr_tail); } +} + +/* + * Trim si->nr_free_tail when a cluster in the tail region is allocated. + * @idx: index of the cluster being allocated. + */ +static void xswap_trim_free_tail(struct swap_info_struct *si, unsigned long idx) +{ + unsigned long nr_mapped, nr_tail, tail_start; - if (last == si->nr_clusters_mapped) - return; /* nothing to shrink */ + if (!(si->flags & SWP_XSWAP)) + return; + + /* + * nr_clusters_mapped and nr_free_tail are read locklessly; + * concurrent updates may cause nr_free_tail to be trimmed + * slightly less than ideally, which is harmless. + */ + nr_mapped = READ_ONCE(si->nr_clusters_mapped); + nr_tail = READ_ONCE(si->nr_free_tail); + tail_start = nr_mapped - nr_tail; + if (idx >= tail_start) + WRITE_ONCE(si->nr_free_tail, nr_mapped - idx - 1); +} + +/* + * Try to shrink the cluster_info tail. Uses si->nr_free_tail which + * is maintained incrementally during alloc/free — no scanning needed. + */ +static void xswap_try_shrink(struct swap_info_struct *si) +{ + unsigned long start_idx, nr_unmap, i; + struct swap_cluster_info *ci; + + if (!(si->flags & SWP_XSWAP)) + return; + if (si->nr_free_tail < XSWAP_GROW_CLUSTERS) + return; + + nr_unmap = round_down(si->nr_free_tail, XSWAP_GROW_CLUSTERS); + start_idx = si->nr_clusters_mapped - nr_unmap; + + /* Verify the tail clusters are still free before unmapping */ + spin_lock(&si->lock); + for (i = start_idx; i < si->nr_clusters_mapped; i++) { + ci = &si->cluster_info[i]; + if (ci->flags != CLUSTER_FLAG_FREE) { + nr_unmap = i - start_idx; + break; + } + list_del(&ci->list); + ci->flags = CLUSTER_FLAG_NONE; + } + spin_unlock(&si->lock); - /* Only unmap if we can free at least one full page of clusters */ - if (si->nr_clusters_mapped - last < XSWAP_GROW_CLUSTERS) + if (nr_unmap < XSWAP_GROW_CLUSTERS) return; - xswap_unmap_clusters(si, last, si->nr_clusters_mapped - last); + xswap_unmap_clusters(si, start_idx, nr_unmap); + si->nr_free_tail -= nr_unmap; } #endif /* CONFIG_XSWAP */ -- 2.54.0