swapfile.c 95.1 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0-only
Linus Torvalds's avatar
Linus Torvalds committed
2 3 4 5 6 7 8 9
/*
 *  linux/mm/swapfile.c
 *
 *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
 *  Swap reorganised 29.12.95, Stephen Tweedie
 */

#include <linux/mm.h>
10
#include <linux/sched/mm.h>
11
#include <linux/sched/task.h>
Linus Torvalds's avatar
Linus Torvalds committed
12 13 14 15 16 17 18 19
#include <linux/hugetlb.h>
#include <linux/mman.h>
#include <linux/slab.h>
#include <linux/kernel_stat.h>
#include <linux/swap.h>
#include <linux/vmalloc.h>
#include <linux/pagemap.h>
#include <linux/namei.h>
20
#include <linux/shmem_fs.h>
Linus Torvalds's avatar
Linus Torvalds committed
21
#include <linux/blkdev.h>
22
#include <linux/random.h>
Linus Torvalds's avatar
Linus Torvalds committed
23 24 25 26
#include <linux/writeback.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/init.h>
27
#include <linux/ksm.h>
Linus Torvalds's avatar
Linus Torvalds committed
28 29 30
#include <linux/rmap.h>
#include <linux/security.h>
#include <linux/backing-dev.h>
Ingo Molnar's avatar
Ingo Molnar committed
31
#include <linux/mutex.h>
32
#include <linux/capability.h>
Linus Torvalds's avatar
Linus Torvalds committed
33
#include <linux/syscalls.h>
34
#include <linux/memcontrol.h>
Kay Sievers's avatar
Kay Sievers committed
35
#include <linux/poll.h>
36
#include <linux/oom.h>
37 38
#include <linux/frontswap.h>
#include <linux/swapfile.h>
39
#include <linux/export.h>
40
#include <linux/swap_slots.h>
41
#include <linux/sort.h>
Linus Torvalds's avatar
Linus Torvalds committed
42 43 44 45

#include <asm/pgtable.h>
#include <asm/tlbflush.h>
#include <linux/swapops.h>
46
#include <linux/swap_cgroup.h>
Linus Torvalds's avatar
Linus Torvalds committed
47

48 49 50
static bool swap_count_continued(struct swap_info_struct *, pgoff_t,
				 unsigned char);
static void free_swap_count_continuations(struct swap_info_struct *);
51
static sector_t map_swap_entry(swp_entry_t, struct block_device**);
52

53
DEFINE_SPINLOCK(swap_lock);
Adrian Bunk's avatar
Adrian Bunk committed
54
static unsigned int nr_swapfiles;
55
atomic_long_t nr_swap_pages;
Chris Wilson's avatar
Chris Wilson committed
56 57 58 59 60 61
/*
 * Some modules use swappable objects and may try to swap them out under
 * memory pressure (via the shrinker). Before doing so, they may wish to
 * check to see if any swap space is available.
 */
EXPORT_SYMBOL_GPL(nr_swap_pages);
62
/* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
Linus Torvalds's avatar
Linus Torvalds committed
63
long total_swap_pages;
64
static int least_priority = -1;
Linus Torvalds's avatar
Linus Torvalds committed
65 66 67 68 69 70

static const char Bad_file[] = "Bad swap file entry ";
static const char Unused_file[] = "Unused swap file entry ";
static const char Bad_offset[] = "Bad swap offset entry ";
static const char Unused_offset[] = "Unused swap offset entry ";

71 72 73 74
/*
 * all active swap_info_structs
 * protected with swap_lock, and ordered by priority.
 */
75 76 77 78 79 80 81 82 83 84 85 86 87 88
PLIST_HEAD(swap_active_head);

/*
 * all available (active, not full) swap_info_structs
 * protected with swap_avail_lock, ordered by priority.
 * This is used by get_swap_page() instead of swap_active_head
 * because swap_active_head includes all swap_info_structs,
 * but get_swap_page() doesn't need to look at full ones.
 * This uses its own lock instead of swap_lock because when a
 * swap_info_struct changes between not-full/full, it needs to
 * add/remove itself to/from this list, but the swap_info_struct->lock
 * is held and the locking order requires swap_lock to be taken
 * before any swap_info_struct->lock.
 */
89
static struct plist_head *swap_avail_heads;
90
static DEFINE_SPINLOCK(swap_avail_lock);
Linus Torvalds's avatar
Linus Torvalds committed
91

92
struct swap_info_struct *swap_info[MAX_SWAPFILES];
Linus Torvalds's avatar
Linus Torvalds committed
93

Ingo Molnar's avatar
Ingo Molnar committed
94
static DEFINE_MUTEX(swapon_mutex);
Linus Torvalds's avatar
Linus Torvalds committed
95

Kay Sievers's avatar
Kay Sievers committed
96 97 98 99
static DECLARE_WAIT_QUEUE_HEAD(proc_poll_wait);
/* Activity counter to indicate that a swapon or swapoff has occurred */
static atomic_t proc_poll_event = ATOMIC_INIT(0);

100 101
atomic_t nr_rotate_swap = ATOMIC_INIT(0);

102 103 104 105 106 107 108 109 110
static struct swap_info_struct *swap_type_to_swap_info(int type)
{
	if (type >= READ_ONCE(nr_swapfiles))
		return NULL;

	smp_rmb();	/* Pairs with smp_wmb in alloc_swap_info. */
	return READ_ONCE(swap_info[type]);
}

111
static inline unsigned char swap_count(unsigned char ent)
112
{
113
	return ent & ~SWAP_HAS_CACHE;	/* may include COUNT_CONTINUED flag */
114 115
}

116 117 118 119 120 121 122 123 124 125
/* Reclaim the swap entry anyway if possible */
#define TTRS_ANYWAY		0x1
/*
 * Reclaim the swap entry if there are no more mappings of the
 * corresponding page
 */
#define TTRS_UNMAPPED		0x2
/* Reclaim the swap entry if swap is getting full*/
#define TTRS_FULL		0x4

126
/* returns 1 if swap entry is freed */
127 128
static int __try_to_reclaim_swap(struct swap_info_struct *si,
				 unsigned long offset, unsigned long flags)
129
{
130
	swp_entry_t entry = swp_entry(si->type, offset);
131 132 133
	struct page *page;
	int ret = 0;

134
	page = find_get_page(swap_address_space(entry), offset);
135 136 137
	if (!page)
		return 0;
	/*
138 139 140
	 * When this function is called from scan_swap_map_slots() and it's
	 * called by vmscan.c at reclaiming pages. So, we hold a lock on a page,
	 * here. We have to use trylock for avoiding deadlock. This is a special
141 142 143 144
	 * case and you should use try_to_free_swap() with explicit lock_page()
	 * in usual operations.
	 */
	if (trylock_page(page)) {
145 146 147 148
		if ((flags & TTRS_ANYWAY) ||
		    ((flags & TTRS_UNMAPPED) && !page_mapped(page)) ||
		    ((flags & TTRS_FULL) && mem_cgroup_swap_full(page)))
			ret = try_to_free_swap(page);
149 150
		unlock_page(page);
	}
151
	put_page(page);
152 153
	return ret;
}
154

155 156 157 158 159 160 161 162 163 164 165 166
static inline struct swap_extent *first_se(struct swap_info_struct *sis)
{
	struct rb_node *rb = rb_first(&sis->swap_extent_root);
	return rb_entry(rb, struct swap_extent, rb_node);
}

static inline struct swap_extent *next_se(struct swap_extent *se)
{
	struct rb_node *rb = rb_next(&se->rb_node);
	return rb ? rb_entry(rb, struct swap_extent, rb_node) : NULL;
}

167 168 169 170 171 172 173
/*
 * swapon tell device that all the old swap contents can be discarded,
 * to allow the swap device to optimize its wear-levelling.
 */
static int discard_swap(struct swap_info_struct *si)
{
	struct swap_extent *se;
174 175
	sector_t start_block;
	sector_t nr_blocks;
176 177
	int err = 0;

178
	/* Do not discard the swap header page! */
179
	se = first_se(si);
180 181 182 183
	start_block = (se->start_block + 1) << (PAGE_SHIFT - 9);
	nr_blocks = ((sector_t)se->nr_pages - 1) << (PAGE_SHIFT - 9);
	if (nr_blocks) {
		err = blkdev_issue_discard(si->bdev, start_block,
184
				nr_blocks, GFP_KERNEL, 0);
185 186 187 188
		if (err)
			return err;
		cond_resched();
	}
189

190
	for (se = next_se(se); se; se = next_se(se)) {
191 192
		start_block = se->start_block << (PAGE_SHIFT - 9);
		nr_blocks = (sector_t)se->nr_pages << (PAGE_SHIFT - 9);
193 194

		err = blkdev_issue_discard(si->bdev, start_block,
195
				nr_blocks, GFP_KERNEL, 0);
196 197 198 199 200 201 202 203
		if (err)
			break;

		cond_resched();
	}
	return err;		/* That will often be -EOPNOTSUPP */
}

204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
static struct swap_extent *
offset_to_swap_extent(struct swap_info_struct *sis, unsigned long offset)
{
	struct swap_extent *se;
	struct rb_node *rb;

	rb = sis->swap_extent_root.rb_node;
	while (rb) {
		se = rb_entry(rb, struct swap_extent, rb_node);
		if (offset < se->start_page)
			rb = rb->rb_left;
		else if (offset >= se->start_page + se->nr_pages)
			rb = rb->rb_right;
		else
			return se;
	}
	/* It *must* be present */
	BUG();
}

224 225 226 227 228 229 230
/*
 * swap allocation tell device that a cluster of swap can now be discarded,
 * to allow the swap device to optimize its wear-levelling.
 */
static void discard_swap_cluster(struct swap_info_struct *si,
				 pgoff_t start_page, pgoff_t nr_pages)
{
231
	struct swap_extent *se = offset_to_swap_extent(si, start_page);
232 233

	while (nr_pages) {
234 235 236 237 238 239 240 241 242 243 244 245 246 247
		pgoff_t offset = start_page - se->start_page;
		sector_t start_block = se->start_block + offset;
		sector_t nr_blocks = se->nr_pages - offset;

		if (nr_blocks > nr_pages)
			nr_blocks = nr_pages;
		start_page += nr_blocks;
		nr_pages -= nr_blocks;

		start_block <<= PAGE_SHIFT - 9;
		nr_blocks <<= PAGE_SHIFT - 9;
		if (blkdev_issue_discard(si->bdev, start_block,
					nr_blocks, GFP_NOIO, 0))
			break;
248

249
		se = next_se(se);
250 251 252
	}
}

253 254
#ifdef CONFIG_THP_SWAP
#define SWAPFILE_CLUSTER	HPAGE_PMD_NR
255 256

#define swap_entry_size(size)	(size)
257
#else
258
#define SWAPFILE_CLUSTER	256
259 260 261 262 263 264

/*
 * Define swap_entry_size() as constant to let compiler to optimize
 * out some code if !CONFIG_THP_SWAP
 */
#define swap_entry_size(size)	1
265
#endif
266 267
#define LATENCY_LIMIT		256

268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
static inline void cluster_set_flag(struct swap_cluster_info *info,
	unsigned int flag)
{
	info->flags = flag;
}

static inline unsigned int cluster_count(struct swap_cluster_info *info)
{
	return info->data;
}

static inline void cluster_set_count(struct swap_cluster_info *info,
				     unsigned int c)
{
	info->data = c;
}

static inline void cluster_set_count_flag(struct swap_cluster_info *info,
					 unsigned int c, unsigned int f)
{
	info->flags = f;
	info->data = c;
}

static inline unsigned int cluster_next(struct swap_cluster_info *info)
{
	return info->data;
}

static inline void cluster_set_next(struct swap_cluster_info *info,
				    unsigned int n)
{
	info->data = n;
}

static inline void cluster_set_next_flag(struct swap_cluster_info *info,
					 unsigned int n, unsigned int f)
{
	info->flags = f;
	info->data = n;
}

static inline bool cluster_is_free(struct swap_cluster_info *info)
{
	return info->flags & CLUSTER_FLAG_FREE;
}

static inline bool cluster_is_null(struct swap_cluster_info *info)
{
	return info->flags & CLUSTER_FLAG_NEXT_NULL;
}

static inline void cluster_set_null(struct swap_cluster_info *info)
{
	info->flags = CLUSTER_FLAG_NEXT_NULL;
	info->data = 0;
}

326 327
static inline bool cluster_is_huge(struct swap_cluster_info *info)
{
328 329 330
	if (IS_ENABLED(CONFIG_THP_SWAP))
		return info->flags & CLUSTER_FLAG_HUGE;
	return false;
331 332 333 334 335 336 337
}

static inline void cluster_clear_huge(struct swap_cluster_info *info)
{
	info->flags &= ~CLUSTER_FLAG_HUGE;
}

Huang, Ying's avatar
Huang, Ying committed
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
static inline struct swap_cluster_info *lock_cluster(struct swap_info_struct *si,
						     unsigned long offset)
{
	struct swap_cluster_info *ci;

	ci = si->cluster_info;
	if (ci) {
		ci += offset / SWAPFILE_CLUSTER;
		spin_lock(&ci->lock);
	}
	return ci;
}

static inline void unlock_cluster(struct swap_cluster_info *ci)
{
	if (ci)
		spin_unlock(&ci->lock);
}

357 358 359 360
/*
 * Determine the locking method in use for this device.  Return
 * swap_cluster_info if SSD-style cluster-based locking is in place.
 */
Huang, Ying's avatar
Huang, Ying committed
361
static inline struct swap_cluster_info *lock_cluster_or_swap_info(
362
		struct swap_info_struct *si, unsigned long offset)
Huang, Ying's avatar
Huang, Ying committed
363 364 365
{
	struct swap_cluster_info *ci;

366
	/* Try to use fine-grained SSD-style locking if available: */
Huang, Ying's avatar
Huang, Ying committed
367
	ci = lock_cluster(si, offset);
368
	/* Otherwise, fall back to traditional, coarse locking: */
Huang, Ying's avatar
Huang, Ying committed
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
	if (!ci)
		spin_lock(&si->lock);

	return ci;
}

static inline void unlock_cluster_or_swap_info(struct swap_info_struct *si,
					       struct swap_cluster_info *ci)
{
	if (ci)
		unlock_cluster(ci);
	else
		spin_unlock(&si->lock);
}

Huang Ying's avatar
Huang Ying committed
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
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 {
Huang, Ying's avatar
Huang, Ying committed
408
		struct swap_cluster_info *ci_tail;
Huang Ying's avatar
Huang Ying committed
409 410
		unsigned int tail = cluster_next(&list->tail);

Huang, Ying's avatar
Huang, Ying committed
411 412 413 414 415 416 417
		/*
		 * 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);
418
		spin_unlock(&ci_tail->lock);
Huang Ying's avatar
Huang Ying committed
419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
		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;
}

Shaohua Li's avatar
Shaohua Li committed
439 440 441 442 443 444 445 446 447 448 449 450 451
/* 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)
{
	/*
	 * If scan_swap_map() can't find a free cluster, it will check
	 * si->swap_map directly. To make sure the discarding cluster isn't
	 * taken by scan_swap_map(), mark the swap entries bad (occupied). It
	 * will be cleared after discard
	 */
	memset(si->swap_map + idx * SWAPFILE_CLUSTER,
			SWAP_MAP_BAD, SWAPFILE_CLUSTER);

Huang Ying's avatar
Huang Ying committed
452
	cluster_list_add_tail(&si->discard_clusters, si->cluster_info, idx);
Shaohua Li's avatar
Shaohua Li committed
453 454 455 456

	schedule_work(&si->discard_work);
}

457 458 459 460 461 462 463 464
static void __free_cluster(struct swap_info_struct *si, unsigned long idx)
{
	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);
}

Shaohua Li's avatar
Shaohua Li committed
465 466 467 468 469 470
/*
 * Doing discard actually. After a cluster discard is finished, the cluster
 * will be added to free cluster list. caller should hold si->lock.
*/
static void swap_do_scheduled_discard(struct swap_info_struct *si)
{
Huang, Ying's avatar
Huang, Ying committed
471
	struct swap_cluster_info *info, *ci;
Shaohua Li's avatar
Shaohua Li committed
472 473 474 475
	unsigned int idx;

	info = si->cluster_info;

Huang Ying's avatar
Huang Ying committed
476 477
	while (!cluster_list_empty(&si->discard_clusters)) {
		idx = cluster_list_del_first(&si->discard_clusters, info);
Shaohua Li's avatar
Shaohua Li committed
478 479 480 481 482 483
		spin_unlock(&si->lock);

		discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
				SWAPFILE_CLUSTER);

		spin_lock(&si->lock);
Huang, Ying's avatar
Huang, Ying committed
484
		ci = lock_cluster(si, idx * SWAPFILE_CLUSTER);
485
		__free_cluster(si, idx);
Shaohua Li's avatar
Shaohua Li committed
486 487
		memset(si->swap_map + idx * SWAPFILE_CLUSTER,
				0, SWAPFILE_CLUSTER);
Huang, Ying's avatar
Huang, Ying committed
488
		unlock_cluster(ci);
Shaohua Li's avatar
Shaohua Li committed
489 490 491 492 493 494 495 496 497 498 499 500 501 502
	}
}

static void swap_discard_work(struct work_struct *work)
{
	struct swap_info_struct *si;

	si = container_of(work, struct swap_info_struct, discard_work);

	spin_lock(&si->lock);
	swap_do_scheduled_discard(si);
	spin_unlock(&si->lock);
}

503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530
static void alloc_cluster(struct swap_info_struct *si, unsigned long idx)
{
	struct swap_cluster_info *ci = si->cluster_info;

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

static void free_cluster(struct swap_info_struct *si, unsigned long idx)
{
	struct swap_cluster_info *ci = si->cluster_info + idx;

	VM_BUG_ON(cluster_count(ci) != 0);
	/*
	 * If the swap is discardable, prepare discard the cluster
	 * instead of free it immediately. The cluster will be freed
	 * after discard.
	 */
	if ((si->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
	    (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
		swap_cluster_schedule_discard(si, idx);
		return;
	}

	__free_cluster(si, idx);
}

531 532 533 534 535 536 537 538 539 540 541
/*
 * The cluster corresponding to page_nr will be used. The cluster will be
 * removed from free cluster list and its usage counter will be increased.
 */
static void inc_cluster_info_page(struct swap_info_struct *p,
	struct swap_cluster_info *cluster_info, unsigned long page_nr)
{
	unsigned long idx = page_nr / SWAPFILE_CLUSTER;

	if (!cluster_info)
		return;
542 543
	if (cluster_is_free(&cluster_info[idx]))
		alloc_cluster(p, idx);
544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566

	VM_BUG_ON(cluster_count(&cluster_info[idx]) >= SWAPFILE_CLUSTER);
	cluster_set_count(&cluster_info[idx],
		cluster_count(&cluster_info[idx]) + 1);
}

/*
 * 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.
 */
static void dec_cluster_info_page(struct swap_info_struct *p,
	struct swap_cluster_info *cluster_info, unsigned long page_nr)
{
	unsigned long idx = page_nr / SWAPFILE_CLUSTER;

	if (!cluster_info)
		return;

	VM_BUG_ON(cluster_count(&cluster_info[idx]) == 0);
	cluster_set_count(&cluster_info[idx],
		cluster_count(&cluster_info[idx]) - 1);

567 568
	if (cluster_count(&cluster_info[idx]) == 0)
		free_cluster(p, idx);
569 570 571 572 573 574
}

/*
 * It's possible scan_swap_map() uses a free cluster in the middle of free
 * cluster list. Avoiding such abuse to avoid list corruption.
 */
575 576
static bool
scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
577 578
	unsigned long offset)
{
579 580 581
	struct percpu_cluster *percpu_cluster;
	bool conflict;

582
	offset /= SWAPFILE_CLUSTER;
Huang Ying's avatar
Huang Ying committed
583 584
	conflict = !cluster_list_empty(&si->free_clusters) &&
		offset != cluster_list_first(&si->free_clusters) &&
585
		cluster_is_free(&si->cluster_info[offset]);
586 587 588 589 590 591 592 593 594 595 596 597 598

	if (!conflict)
		return false;

	percpu_cluster = this_cpu_ptr(si->percpu_cluster);
	cluster_set_null(&percpu_cluster->index);
	return true;
}

/*
 * Try to get a swap entry from current cpu's swap entry pool (a cluster). This
 * might involve allocating a new cluster for current CPU too.
 */
599
static bool scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
600 601 602
	unsigned long *offset, unsigned long *scan_base)
{
	struct percpu_cluster *cluster;
Huang, Ying's avatar
Huang, Ying committed
603
	struct swap_cluster_info *ci;
604
	bool found_free;
Huang, Ying's avatar
Huang, Ying committed
605
	unsigned long tmp, max;
606 607 608 609

new_cluster:
	cluster = this_cpu_ptr(si->percpu_cluster);
	if (cluster_is_null(&cluster->index)) {
Huang Ying's avatar
Huang Ying committed
610 611
		if (!cluster_list_empty(&si->free_clusters)) {
			cluster->index = si->free_clusters.head;
612 613
			cluster->next = cluster_next(&cluster->index) *
					SWAPFILE_CLUSTER;
Huang Ying's avatar
Huang Ying committed
614
		} else if (!cluster_list_empty(&si->discard_clusters)) {
615 616 617 618 619 620 621 622
			/*
			 * we don't have free cluster but have some clusters in
			 * discarding, do discard now and reclaim them
			 */
			swap_do_scheduled_discard(si);
			*scan_base = *offset = si->cluster_next;
			goto new_cluster;
		} else
623
			return false;
624 625 626 627 628 629 630 631 632
	}

	found_free = false;

	/*
	 * Other CPUs can use our cluster if they can't find a free cluster,
	 * check if there is still free entry in the cluster
	 */
	tmp = cluster->next;
Huang, Ying's avatar
Huang, Ying committed
633 634 635 636 637 638 639 640
	max = min_t(unsigned long, si->max,
		    (cluster_next(&cluster->index) + 1) * SWAPFILE_CLUSTER);
	if (tmp >= max) {
		cluster_set_null(&cluster->index);
		goto new_cluster;
	}
	ci = lock_cluster(si, tmp);
	while (tmp < max) {
641 642 643 644 645 646
		if (!si->swap_map[tmp]) {
			found_free = true;
			break;
		}
		tmp++;
	}
Huang, Ying's avatar
Huang, Ying committed
647
	unlock_cluster(ci);
648 649 650 651 652 653 654
	if (!found_free) {
		cluster_set_null(&cluster->index);
		goto new_cluster;
	}
	cluster->next = tmp + 1;
	*offset = tmp;
	*scan_base = tmp;
655
	return found_free;
656 657
}

658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
static void __del_from_avail_list(struct swap_info_struct *p)
{
	int nid;

	for_each_node(nid)
		plist_del(&p->avail_lists[nid], &swap_avail_heads[nid]);
}

static void del_from_avail_list(struct swap_info_struct *p)
{
	spin_lock(&swap_avail_lock);
	__del_from_avail_list(p);
	spin_unlock(&swap_avail_lock);
}

673 674 675 676 677 678 679 680 681 682 683 684 685
static void swap_range_alloc(struct swap_info_struct *si, unsigned long offset,
			     unsigned int nr_entries)
{
	unsigned int end = offset + nr_entries - 1;

	if (offset == si->lowest_bit)
		si->lowest_bit += nr_entries;
	if (end == si->highest_bit)
		si->highest_bit -= nr_entries;
	si->inuse_pages += nr_entries;
	if (si->inuse_pages == si->pages) {
		si->lowest_bit = si->max;
		si->highest_bit = 0;
686
		del_from_avail_list(si);
687 688 689
	}
}

690 691 692 693 694 695 696 697 698 699 700 701
static void add_to_avail_list(struct swap_info_struct *p)
{
	int nid;

	spin_lock(&swap_avail_lock);
	for_each_node(nid) {
		WARN_ON(!plist_node_empty(&p->avail_lists[nid]));
		plist_add(&p->avail_lists[nid], &swap_avail_heads[nid]);
	}
	spin_unlock(&swap_avail_lock);
}

702 703 704 705 706 707 708 709 710 711 712 713
static void swap_range_free(struct swap_info_struct *si, unsigned long offset,
			    unsigned int nr_entries)
{
	unsigned long end = offset + nr_entries - 1;
	void (*swap_slot_free_notify)(struct block_device *, unsigned long);

	if (offset < si->lowest_bit)
		si->lowest_bit = offset;
	if (end > si->highest_bit) {
		bool was_full = !si->highest_bit;

		si->highest_bit = end;
714 715
		if (was_full && (si->flags & SWP_WRITEOK))
			add_to_avail_list(si);
716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731
	}
	atomic_long_add(nr_entries, &nr_swap_pages);
	si->inuse_pages -= nr_entries;
	if (si->flags & SWP_BLKDEV)
		swap_slot_free_notify =
			si->bdev->bd_disk->fops->swap_slot_free_notify;
	else
		swap_slot_free_notify = NULL;
	while (offset <= end) {
		frontswap_invalidate_page(si->type, offset);
		if (swap_slot_free_notify)
			swap_slot_free_notify(si->bdev, offset);
		offset++;
	}
}

732 733 734
static int scan_swap_map_slots(struct swap_info_struct *si,
			       unsigned char usage, int nr,
			       swp_entry_t slots[])
Linus Torvalds's avatar
Linus Torvalds committed
735
{
Huang, Ying's avatar
Huang, Ying committed
736
	struct swap_cluster_info *ci;
737
	unsigned long offset;
738
	unsigned long scan_base;
739
	unsigned long last_in_cluster = 0;
740
	int latency_ration = LATENCY_LIMIT;
741 742 743 744
	int n_ret = 0;

	if (nr > SWAP_BATCH)
		nr = SWAP_BATCH;
745

746
	/*
747 748 749 750 751 752 753
	 * We try to cluster swap pages by allocating them sequentially
	 * in swap.  Once we've allocated SWAPFILE_CLUSTER pages this
	 * way, however, we resort to first-free allocation, starting
	 * a new cluster.  This prevents us from scattering swap pages
	 * all over the entire swap partition, so that we reduce
	 * overall disk seek times between swap pages.  -- sct
	 * But we do now try to find an empty cluster.  -Andrea
754
	 * And we let swap pages go all over an SSD partition.  Hugh
755 756
	 */

757
	si->flags += SWP_SCANNING;
758
	scan_base = offset = si->cluster_next;
759

760 761
	/* SSD algorithm */
	if (si->cluster_info) {
762 763 764 765
		if (scan_swap_map_try_ssd_cluster(si, &offset, &scan_base))
			goto checks;
		else
			goto scan;
766 767
	}

768 769 770 771 772
	if (unlikely(!si->cluster_nr--)) {
		if (si->pages - si->inuse_pages < SWAPFILE_CLUSTER) {
			si->cluster_nr = SWAPFILE_CLUSTER - 1;
			goto checks;
		}
773

774
		spin_unlock(&si->lock);
775

776 777 778
		/*
		 * If seek is expensive, start searching for new cluster from
		 * start of partition, to minimize the span of allocated swap.
779 780
		 * If seek is cheap, that is the SWP_SOLIDSTATE si->cluster_info
		 * case, just handled by scan_swap_map_try_ssd_cluster() above.
781
		 */
782
		scan_base = offset = si->lowest_bit;
783 784 785 786
		last_in_cluster = offset + SWAPFILE_CLUSTER - 1;

		/* Locate the first empty (unaligned) cluster */
		for (; last_in_cluster <= si->highest_bit; offset++) {
Linus Torvalds's avatar
Linus Torvalds committed
787
			if (si->swap_map[offset])
788 789
				last_in_cluster = offset + SWAPFILE_CLUSTER;
			else if (offset == last_in_cluster) {
790
				spin_lock(&si->lock);
791 792 793
				offset -= SWAPFILE_CLUSTER - 1;
				si->cluster_next = offset;
				si->cluster_nr = SWAPFILE_CLUSTER - 1;
794 795 796 797 798 799 800 801 802
				goto checks;
			}
			if (unlikely(--latency_ration < 0)) {
				cond_resched();
				latency_ration = LATENCY_LIMIT;
			}
		}

		offset = scan_base;
803
		spin_lock(&si->lock);
804
		si->cluster_nr = SWAPFILE_CLUSTER - 1;
Linus Torvalds's avatar
Linus Torvalds committed
805
	}
806

807
checks:
808
	if (si->cluster_info) {
809 810 811 812 813 814 815 816
		while (scan_swap_map_ssd_cluster_conflict(si, offset)) {
		/* take a break if we already got some slots */
			if (n_ret)
				goto done;
			if (!scan_swap_map_try_ssd_cluster(si, &offset,
							&scan_base))
				goto scan;
		}
817
	}
818
	if (!(si->flags & SWP_WRITEOK))
819
		goto no_page;
820 821
	if (!si->highest_bit)
		goto no_page;
822
	if (offset > si->highest_bit)
823
		scan_base = offset = si->lowest_bit;
824

Huang, Ying's avatar
Huang, Ying committed
825
	ci = lock_cluster(si, offset);
826 827
	/* reuse swap entry of cache-only swap if not busy. */
	if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
828
		int swap_was_freed;
Huang, Ying's avatar
Huang, Ying committed
829
		unlock_cluster(ci);
830
		spin_unlock(&si->lock);
831
		swap_was_freed = __try_to_reclaim_swap(si, offset, TTRS_ANYWAY);
832
		spin_lock(&si->lock);
833 834 835 836 837 838
		/* entry was freed successfully, try to use this again */
		if (swap_was_freed)
			goto checks;
		goto scan; /* check next one */
	}

Huang, Ying's avatar
Huang, Ying committed
839 840
	if (si->swap_map[offset]) {
		unlock_cluster(ci);
841 842 843 844
		if (!n_ret)
			goto scan;
		else
			goto done;
Huang, Ying's avatar
Huang, Ying committed
845
	}
846 847 848
	si->swap_map[offset] = usage;
	inc_cluster_info_page(si, si->cluster_info, offset);
	unlock_cluster(ci);
849

850
	swap_range_alloc(si, offset, 1);
851
	si->cluster_next = offset + 1;
852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884
	slots[n_ret++] = swp_entry(si->type, offset);

	/* got enough slots or reach max slots? */
	if ((n_ret == nr) || (offset >= si->highest_bit))
		goto done;

	/* search for next available slot */

	/* time to take a break? */
	if (unlikely(--latency_ration < 0)) {
		if (n_ret)
			goto done;
		spin_unlock(&si->lock);
		cond_resched();
		spin_lock(&si->lock);
		latency_ration = LATENCY_LIMIT;
	}

	/* try to get more slots in cluster */
	if (si->cluster_info) {
		if (scan_swap_map_try_ssd_cluster(si, &offset, &scan_base))
			goto checks;
		else
			goto done;
	}
	/* non-ssd case */
	++offset;

	/* non-ssd case, still more slots in cluster? */
	if (si->cluster_nr && !si->swap_map[offset]) {
		--si->cluster_nr;
		goto checks;
	}
885

886 887 888
done:
	si->flags -= SWP_SCANNING;
	return n_ret;
889

890
scan:
891
	spin_unlock(&si->lock);
892
	while (++offset <= si->highest_bit) {
893
		if (!si->swap_map[offset]) {
894
			spin_lock(&si->lock);
895 896
			goto checks;
		}
897
		if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
898
			spin_lock(&si->lock);
899 900
			goto checks;
		}
901 902 903 904
		if (unlikely(--latency_ration < 0)) {
			cond_resched();
			latency_ration = LATENCY_LIMIT;
		}
905
	}
906
	offset = si->lowest_bit;
907
	while (offset < scan_base) {
908
		if (!si->swap_map[offset]) {
909
			spin_lock(&si->lock);
910 911
			goto checks;
		}
912
		if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
913
			spin_lock(&si->lock);
914 915
			goto checks;
		}
916 917 918 919
		if (unlikely(--latency_ration < 0)) {
			cond_resched();
			latency_ration = LATENCY_LIMIT;
		}
920
		offset++;
921
	}
922
	spin_lock(&si->lock);
923 924

no_page:
925
	si->flags -= SWP_SCANNING;
926
	return n_ret;
Linus Torvalds's avatar
Linus Torvalds committed
927 928
}

929 930 931 932 933 934 935
static int swap_alloc_cluster(struct swap_info_struct *si, swp_entry_t *slot)
{
	unsigned long idx;
	struct swap_cluster_info *ci;
	unsigned long offset, i;
	unsigned char *map;

936 937 938 939 940 941 942 943 944
	/*
	 * Should not even be attempting cluster allocations when huge
	 * page swap is disabled.  Warn and fail the allocation.
	 */
	if (!IS_ENABLED(CONFIG_THP_SWAP)) {
		VM_WARN_ON_ONCE(1);
		return 0;
	}

945 946 947 948 949 950 951
	if (cluster_list_empty(&si->free_clusters))
		return 0;

	idx = cluster_list_first(&si->free_clusters);
	offset = idx * SWAPFILE_CLUSTER;
	ci = lock_cluster(si, offset);
	alloc_cluster(si, idx);
952
	cluster_set_count_flag(ci, SWAPFILE_CLUSTER, CLUSTER_FLAG_HUGE);
953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969

	map = si->swap_map + offset;
	for (i = 0; i < SWAPFILE_CLUSTER; i++)
		map[i] = SWAP_HAS_CACHE;
	unlock_cluster(ci);
	swap_range_alloc(si, offset, SWAPFILE_CLUSTER);
	*slot = swp_entry(si->type, offset);

	return 1;
}

static void swap_free_cluster(struct swap_info_struct *si, unsigned long idx)
{
	unsigned long offset = idx * SWAPFILE_CLUSTER;
	struct swap_cluster_info *ci;

	ci = lock_cluster(si, offset);
970
	memset(si->swap_map + offset, 0, SWAPFILE_CLUSTER);
971 972 973 974 975 976
	cluster_set_count_flag(ci, 0, 0);
	free_cluster(si, idx);
	unlock_cluster(ci);
	swap_range_free(si, offset, SWAPFILE_CLUSTER);
}

977 978 979 980 981 982 983 984 985 986 987 988 989 990 991
static unsigned long scan_swap_map(struct swap_info_struct *si,
				   unsigned char usage)
{
	swp_entry_t entry;
	int n_ret;

	n_ret = scan_swap_map_slots(si, usage, 1, &entry);

	if (n_ret)
		return swp_offset(entry);
	else
		return 0;

}

992
int get_swap_pages(int n_goal, swp_entry_t swp_entries[], int entry_size)
Linus Torvalds's avatar
Linus Torvalds committed
993
{
994
	unsigned long size = swap_entry_size(entry_size);
995
	struct swap_info_struct *si, *next;
996 997
	long avail_pgs;
	int n_ret = 0;
998
	int node;
Linus Torvalds's avatar
Linus Torvalds committed
999

1000
	/* Only single cluster request supported */
1001
	WARN_ON_ONCE(n_goal > 1 && size == SWAPFILE_CLUSTER);
1002

1003
	avail_pgs = atomic_long_read(&nr_swap_pages) / size;
1004
	if (avail_pgs <= 0)
1005
		goto noswap;
1006 1007 1008 1009 1010 1011 1012

	if (n_goal > SWAP_BATCH)
		n_goal = SWAP_BATCH;

	if (n_goal > avail_pgs)
		n_goal = avail_pgs;

1013
	atomic_long_sub(n_goal * size, &nr_swap_pages);
1014

1015 1016 1017
	spin_lock(&swap_avail_lock);

start_over:
1018 1019
	node = numa_node_id();
	plist_for_each_entry_safe(si, next, &swap_avail_heads[node], avail_lists[node]) {
1020
		/* requeue si to after same-priority siblings */
1021
		plist_requeue(&si->avail_lists[node], &swap_avail_heads[node]);
1022
		spin_unlock(&swap_avail_lock);
1023
		spin_lock(&si->lock);
1024
		if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
1025
			spin_lock(&swap_avail_lock);
1026
			if (plist_node_empty(&si->avail_lists[node])) {
1027 1028 1029 1030 1031 1032 1033 1034 1035
				spin_unlock(&si->lock);
				goto nextsi;
			}
			WARN(!si->highest_bit,
			     "swap_info %d in list but !highest_bit\n",
			     si->type);
			WARN(!(si->flags & SWP_WRITEOK),
			     "swap_info %d in list but !SWP_WRITEOK\n",
			     si->type);
1036
			__del_from_avail_list(si);
1037
			spin_unlock(&si->lock);
1038
			goto nextsi;
1039
		}
1040
		if (size == SWAPFILE_CLUSTER) {
1041
			if (!(si->flags & SWP_FS))
1042 1043
				n_ret = swap_alloc_cluster(si, swp_entries);
		} else
1044 1045
			n_ret = scan_swap_map_slots(si, SWAP_HAS_CACHE,
						    n_goal, swp_entries);
1046
		spin_unlock(&si->lock);
1047
		if (n_ret || size == SWAPFILE_CLUSTER)
1048
			goto check_out;
1049
		pr_debug("scan_swap_map of si %d failed to find offset\n",
1050 1051
			si->type);

1052 1053
		spin_lock(&swap_avail_lock);
nextsi:
1054 1055 1056 1057
		/*
		 * if we got here, it's likely that si was almost full before,
		 * and since scan_swap_map() can drop the si->lock, multiple
		 * callers probably all tried to get a page from the same si
1058 1059 1060 1061
		 * and it filled up before we could get one; or, the si filled
		 * up between us dropping swap_avail_lock and taking si->lock.
		 * Since we dropped the swap_avail_lock, the swap_avail_head
		 * list may have been modified; so if next is still in the
1062 1063
		 * swap_avail_head list then try it, otherwise start over
		 * if we have not gotten any slots.
1064
		 */
1065
		if (plist_node_empty(&next->avail_lists[node]))
1066
			goto start_over;
Linus Torvalds's avatar
Linus Torvalds committed
1067
	}
1068

1069 1070
	spin_unlock(&swap_avail_lock);

1071 1072
check_out:
	if (n_ret < n_goal)
1073
		atomic_long_add((long)(n_goal - n_ret) * size,
1074
				&nr_swap_pages);
1075
noswap:
1076 1077 1078
	return n_ret;
}

1079
/* The only caller of this function is now suspend routine */
1080 1081
swp_entry_t get_swap_page_of_type(int type)
{
1082
	struct swap_info_struct *si = swap_type_to_swap_info(type);
1083 1084
	pgoff_t offset;

1085 1086 1087
	if (!si)
		goto fail;

1088
	spin_lock(&si->lock);
1089
	if (si->flags & SWP_WRITEOK) {
1090
		atomic_long_dec(&nr_swap_pages);
1091 1092 1093
		/* This is called for allocating swap entry, not cache */
		offset = scan_swap_map(si, 1);
		if (offset) {
1094
			spin_unlock(&si->lock);
1095 1096
			return swp_entry(type, offset);
		}
1097
		atomic_long_inc(&nr_swap_pages);
1098
	}
1099
	spin_unlock(&si->lock);
1100
fail:
1101