swapfile.c 77.6 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 *  linux/mm/swapfile.c
 *
 *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
 *  Swap reorganised 29.12.95, Stephen Tweedie
 */

#include <linux/mm.h>
#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>
17
#include <linux/shmem_fs.h>
Linus Torvalds's avatar
Linus Torvalds committed
18
#include <linux/blkdev.h>
19
#include <linux/random.h>
Linus Torvalds's avatar
Linus Torvalds committed
20 21 22 23
#include <linux/writeback.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/init.h>
24
#include <linux/ksm.h>
Linus Torvalds's avatar
Linus Torvalds committed
25 26 27
#include <linux/rmap.h>
#include <linux/security.h>
#include <linux/backing-dev.h>
28
#include <linux/mutex.h>
29
#include <linux/capability.h>
Linus Torvalds's avatar
Linus Torvalds committed
30
#include <linux/syscalls.h>
31
#include <linux/memcontrol.h>
32
#include <linux/poll.h>
33
#include <linux/oom.h>
34 35
#include <linux/frontswap.h>
#include <linux/swapfile.h>
36
#include <linux/export.h>
Linus Torvalds's avatar
Linus Torvalds committed
37 38 39 40

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

43 44 45
static bool swap_count_continued(struct swap_info_struct *, pgoff_t,
				 unsigned char);
static void free_swap_count_continuations(struct swap_info_struct *);
46
static sector_t map_swap_entry(swp_entry_t, struct block_device**);
47

48
DEFINE_SPINLOCK(swap_lock);
49
static unsigned int nr_swapfiles;
50
atomic_long_t nr_swap_pages;
Chris Wilson's avatar
Chris Wilson committed
51 52 53 54 55 56
/*
 * 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);
57
/* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
Linus Torvalds's avatar
Linus Torvalds committed
58
long total_swap_pages;
59
static int least_priority;
Linus Torvalds's avatar
Linus Torvalds committed
60 61 62 63 64 65

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

66 67 68 69
/*
 * all active swap_info_structs
 * protected with swap_lock, and ordered by priority.
 */
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
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.
 */
static PLIST_HEAD(swap_avail_head);
static DEFINE_SPINLOCK(swap_avail_lock);
Linus Torvalds's avatar
Linus Torvalds committed
86

87
struct swap_info_struct *swap_info[MAX_SWAPFILES];
Linus Torvalds's avatar
Linus Torvalds committed
88

89
static DEFINE_MUTEX(swapon_mutex);
Linus Torvalds's avatar
Linus Torvalds committed
90

91 92 93 94
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);

95
static inline unsigned char swap_count(unsigned char ent)
96
{
97
	return ent & ~SWAP_HAS_CACHE;	/* may include SWAP_HAS_CONT flag */
98 99
}

100
/* returns 1 if swap entry is freed */
101 102 103
static int
__try_to_reclaim_swap(struct swap_info_struct *si, unsigned long offset)
{
104
	swp_entry_t entry = swp_entry(si->type, offset);
105 106 107
	struct page *page;
	int ret = 0;

108
	page = find_get_page(swap_address_space(entry), entry.val);
109 110 111 112 113 114 115 116 117 118 119 120 121
	if (!page)
		return 0;
	/*
	 * This function is called from scan_swap_map() 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
	 * case and you should use try_to_free_swap() with explicit lock_page()
	 * in usual operations.
	 */
	if (trylock_page(page)) {
		ret = try_to_free_swap(page);
		unlock_page(page);
	}
122
	put_page(page);
123 124
	return ret;
}
125

126 127 128 129 130 131 132
/*
 * 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;
133 134
	sector_t start_block;
	sector_t nr_blocks;
135 136
	int err = 0;

137 138 139 140 141 142
	/* Do not discard the swap header page! */
	se = &si->first_swap_extent;
	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,
143
				nr_blocks, GFP_KERNEL, 0);
144 145 146 147
		if (err)
			return err;
		cond_resched();
	}
148

149 150 151
	list_for_each_entry(se, &si->first_swap_extent.list, list) {
		start_block = se->start_block << (PAGE_SHIFT - 9);
		nr_blocks = (sector_t)se->nr_pages << (PAGE_SHIFT - 9);
152 153

		err = blkdev_issue_discard(si->bdev, start_block,
154
				nr_blocks, GFP_KERNEL, 0);
155 156 157 158 159 160 161 162
		if (err)
			break;

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

163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
/*
 * 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)
{
	struct swap_extent *se = si->curr_swap_extent;
	int found_extent = 0;

	while (nr_pages) {
		if (se->start_page <= start_page &&
		    start_page < se->start_page + se->nr_pages) {
			pgoff_t offset = start_page - se->start_page;
			sector_t start_block = se->start_block + offset;
178
			sector_t nr_blocks = se->nr_pages - offset;
179 180 181 182 183 184 185 186 187 188 189 190

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

			if (!found_extent++)
				si->curr_swap_extent = se;

			start_block <<= PAGE_SHIFT - 9;
			nr_blocks <<= PAGE_SHIFT - 9;
			if (blkdev_issue_discard(si->bdev, start_block,
191
				    nr_blocks, GFP_NOIO, 0))
192 193 194
				break;
		}

195
		se = list_next_entry(se, list);
196 197 198
	}
}

199 200 201
#define SWAPFILE_CLUSTER	256
#define LATENCY_LIMIT		256

202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
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;
}

260 261 262 263 264 265 266 267 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 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343
/* 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);

	if (cluster_is_null(&si->discard_cluster_head)) {
		cluster_set_next_flag(&si->discard_cluster_head,
						idx, 0);
		cluster_set_next_flag(&si->discard_cluster_tail,
						idx, 0);
	} else {
		unsigned int tail = cluster_next(&si->discard_cluster_tail);
		cluster_set_next(&si->cluster_info[tail], idx);
		cluster_set_next_flag(&si->discard_cluster_tail,
						idx, 0);
	}

	schedule_work(&si->discard_work);
}

/*
 * 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)
{
	struct swap_cluster_info *info;
	unsigned int idx;

	info = si->cluster_info;

	while (!cluster_is_null(&si->discard_cluster_head)) {
		idx = cluster_next(&si->discard_cluster_head);

		cluster_set_next_flag(&si->discard_cluster_head,
						cluster_next(&info[idx]), 0);
		if (cluster_next(&si->discard_cluster_tail) == idx) {
			cluster_set_null(&si->discard_cluster_head);
			cluster_set_null(&si->discard_cluster_tail);
		}
		spin_unlock(&si->lock);

		discard_swap_cluster(si, idx * SWAPFILE_CLUSTER,
				SWAPFILE_CLUSTER);

		spin_lock(&si->lock);
		cluster_set_flag(&info[idx], CLUSTER_FLAG_FREE);
		if (cluster_is_null(&si->free_cluster_head)) {
			cluster_set_next_flag(&si->free_cluster_head,
						idx, 0);
			cluster_set_next_flag(&si->free_cluster_tail,
						idx, 0);
		} else {
			unsigned int tail;

			tail = cluster_next(&si->free_cluster_tail);
			cluster_set_next(&info[tail], idx);
			cluster_set_next_flag(&si->free_cluster_tail,
						idx, 0);
		}
		memset(si->swap_map + idx * SWAPFILE_CLUSTER,
				0, SWAPFILE_CLUSTER);
	}
}

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

344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
/*
 * 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;
	if (cluster_is_free(&cluster_info[idx])) {
		VM_BUG_ON(cluster_next(&p->free_cluster_head) != idx);
		cluster_set_next_flag(&p->free_cluster_head,
			cluster_next(&cluster_info[idx]), 0);
		if (cluster_next(&p->free_cluster_tail) == idx) {
			cluster_set_null(&p->free_cluster_tail);
			cluster_set_null(&p->free_cluster_head);
		}
		cluster_set_count_flag(&cluster_info[idx], 0, 0);
	}

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

	if (cluster_count(&cluster_info[idx]) == 0) {
389 390 391 392 393
		/*
		 * If the swap is discardable, prepare discard the cluster
		 * instead of free it immediately. The cluster will be freed
		 * after discard.
		 */
394 395
		if ((p->flags & (SWP_WRITEOK | SWP_PAGE_DISCARD)) ==
				 (SWP_WRITEOK | SWP_PAGE_DISCARD)) {
396 397 398 399
			swap_cluster_schedule_discard(p, idx);
			return;
		}

400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
		cluster_set_flag(&cluster_info[idx], CLUSTER_FLAG_FREE);
		if (cluster_is_null(&p->free_cluster_head)) {
			cluster_set_next_flag(&p->free_cluster_head, idx, 0);
			cluster_set_next_flag(&p->free_cluster_tail, idx, 0);
		} else {
			unsigned int tail = cluster_next(&p->free_cluster_tail);
			cluster_set_next(&cluster_info[tail], idx);
			cluster_set_next_flag(&p->free_cluster_tail, idx, 0);
		}
	}
}

/*
 * It's possible scan_swap_map() uses a free cluster in the middle of free
 * cluster list. Avoiding such abuse to avoid list corruption.
 */
416 417
static bool
scan_swap_map_ssd_cluster_conflict(struct swap_info_struct *si,
418 419
	unsigned long offset)
{
420 421 422
	struct percpu_cluster *percpu_cluster;
	bool conflict;

423
	offset /= SWAPFILE_CLUSTER;
424
	conflict = !cluster_is_null(&si->free_cluster_head) &&
425 426
		offset != cluster_next(&si->free_cluster_head) &&
		cluster_is_free(&si->cluster_info[offset]);
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487

	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.
 */
static void scan_swap_map_try_ssd_cluster(struct swap_info_struct *si,
	unsigned long *offset, unsigned long *scan_base)
{
	struct percpu_cluster *cluster;
	bool found_free;
	unsigned long tmp;

new_cluster:
	cluster = this_cpu_ptr(si->percpu_cluster);
	if (cluster_is_null(&cluster->index)) {
		if (!cluster_is_null(&si->free_cluster_head)) {
			cluster->index = si->free_cluster_head;
			cluster->next = cluster_next(&cluster->index) *
					SWAPFILE_CLUSTER;
		} else if (!cluster_is_null(&si->discard_cluster_head)) {
			/*
			 * 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
			return;
	}

	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;
	while (tmp < si->max && tmp < (cluster_next(&cluster->index) + 1) *
	       SWAPFILE_CLUSTER) {
		if (!si->swap_map[tmp]) {
			found_free = true;
			break;
		}
		tmp++;
	}
	if (!found_free) {
		cluster_set_null(&cluster->index);
		goto new_cluster;
	}
	cluster->next = tmp + 1;
	*offset = tmp;
	*scan_base = tmp;
488 489
}

490 491
static unsigned long scan_swap_map(struct swap_info_struct *si,
				   unsigned char usage)
Linus Torvalds's avatar
Linus Torvalds committed
492
{
493
	unsigned long offset;
494
	unsigned long scan_base;
495
	unsigned long last_in_cluster = 0;
496
	int latency_ration = LATENCY_LIMIT;
497

498
	/*
499 500 501 502 503 504 505
	 * 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
506
	 * And we let swap pages go all over an SSD partition.  Hugh
507 508
	 */

509
	si->flags += SWP_SCANNING;
510
	scan_base = offset = si->cluster_next;
511

512 513 514 515 516 517
	/* SSD algorithm */
	if (si->cluster_info) {
		scan_swap_map_try_ssd_cluster(si, &offset, &scan_base);
		goto checks;
	}

518 519 520 521 522
	if (unlikely(!si->cluster_nr--)) {
		if (si->pages - si->inuse_pages < SWAPFILE_CLUSTER) {
			si->cluster_nr = SWAPFILE_CLUSTER - 1;
			goto checks;
		}
523

524
		spin_unlock(&si->lock);
525

526 527 528
		/*
		 * If seek is expensive, start searching for new cluster from
		 * start of partition, to minimize the span of allocated swap.
529 530
		 * If seek is cheap, that is the SWP_SOLIDSTATE si->cluster_info
		 * case, just handled by scan_swap_map_try_ssd_cluster() above.
531
		 */
532
		scan_base = offset = si->lowest_bit;
533 534 535 536
		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
537
			if (si->swap_map[offset])
538 539
				last_in_cluster = offset + SWAPFILE_CLUSTER;
			else if (offset == last_in_cluster) {
540
				spin_lock(&si->lock);
541 542 543
				offset -= SWAPFILE_CLUSTER - 1;
				si->cluster_next = offset;
				si->cluster_nr = SWAPFILE_CLUSTER - 1;
544 545 546 547 548 549 550 551 552
				goto checks;
			}
			if (unlikely(--latency_ration < 0)) {
				cond_resched();
				latency_ration = LATENCY_LIMIT;
			}
		}

		offset = scan_base;
553
		spin_lock(&si->lock);
554
		si->cluster_nr = SWAPFILE_CLUSTER - 1;
Linus Torvalds's avatar
Linus Torvalds committed
555
	}
556

557
checks:
558 559 560 561
	if (si->cluster_info) {
		while (scan_swap_map_ssd_cluster_conflict(si, offset))
			scan_swap_map_try_ssd_cluster(si, &offset, &scan_base);
	}
562
	if (!(si->flags & SWP_WRITEOK))
563
		goto no_page;
564 565
	if (!si->highest_bit)
		goto no_page;
566
	if (offset > si->highest_bit)
567
		scan_base = offset = si->lowest_bit;
568

569 570
	/* reuse swap entry of cache-only swap if not busy. */
	if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
571
		int swap_was_freed;
572
		spin_unlock(&si->lock);
573
		swap_was_freed = __try_to_reclaim_swap(si, offset);
574
		spin_lock(&si->lock);
575 576 577 578 579 580
		/* entry was freed successfully, try to use this again */
		if (swap_was_freed)
			goto checks;
		goto scan; /* check next one */
	}

581 582 583 584 585 586 587 588 589 590 591
	if (si->swap_map[offset])
		goto scan;

	if (offset == si->lowest_bit)
		si->lowest_bit++;
	if (offset == si->highest_bit)
		si->highest_bit--;
	si->inuse_pages++;
	if (si->inuse_pages == si->pages) {
		si->lowest_bit = si->max;
		si->highest_bit = 0;
592 593 594
		spin_lock(&swap_avail_lock);
		plist_del(&si->avail_list, &swap_avail_head);
		spin_unlock(&swap_avail_lock);
Linus Torvalds's avatar
Linus Torvalds committed
595
	}
596
	si->swap_map[offset] = usage;
597
	inc_cluster_info_page(si, si->cluster_info, offset);
598 599
	si->cluster_next = offset + 1;
	si->flags -= SWP_SCANNING;
600

601
	return offset;
602

603
scan:
604
	spin_unlock(&si->lock);
605
	while (++offset <= si->highest_bit) {
606
		if (!si->swap_map[offset]) {
607
			spin_lock(&si->lock);
608 609
			goto checks;
		}
610
		if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
611
			spin_lock(&si->lock);
612 613
			goto checks;
		}
614 615 616 617
		if (unlikely(--latency_ration < 0)) {
			cond_resched();
			latency_ration = LATENCY_LIMIT;
		}
618
	}
619
	offset = si->lowest_bit;
620
	while (offset < scan_base) {
621
		if (!si->swap_map[offset]) {
622
			spin_lock(&si->lock);
623 624
			goto checks;
		}
625
		if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
626
			spin_lock(&si->lock);
627 628
			goto checks;
		}
629 630 631 632
		if (unlikely(--latency_ration < 0)) {
			cond_resched();
			latency_ration = LATENCY_LIMIT;
		}
633
		offset++;
634
	}
635
	spin_lock(&si->lock);
636 637

no_page:
638
	si->flags -= SWP_SCANNING;
Linus Torvalds's avatar
Linus Torvalds committed
639 640 641 642 643
	return 0;
}

swp_entry_t get_swap_page(void)
{
644
	struct swap_info_struct *si, *next;
645
	pgoff_t offset;
Linus Torvalds's avatar
Linus Torvalds committed
646

647
	if (atomic_long_read(&nr_swap_pages) <= 0)
648
		goto noswap;
649
	atomic_long_dec(&nr_swap_pages);
650

651 652 653 654 655 656 657
	spin_lock(&swap_avail_lock);

start_over:
	plist_for_each_entry_safe(si, next, &swap_avail_head, avail_list) {
		/* requeue si to after same-priority siblings */
		plist_requeue(&si->avail_list, &swap_avail_head);
		spin_unlock(&swap_avail_lock);
658
		spin_lock(&si->lock);
659
		if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
660 661 662 663 664 665 666 667 668 669 670 671
			spin_lock(&swap_avail_lock);
			if (plist_node_empty(&si->avail_list)) {
				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);
			plist_del(&si->avail_list, &swap_avail_head);
672
			spin_unlock(&si->lock);
673
			goto nextsi;
674
		}
675

676
		/* This is called for allocating swap entry for cache */
677
		offset = scan_swap_map(si, SWAP_HAS_CACHE);
678 679
		spin_unlock(&si->lock);
		if (offset)
680
			return swp_entry(si->type, offset);
681 682 683 684
		pr_debug("scan_swap_map of si %d failed to find offset\n",
		       si->type);
		spin_lock(&swap_avail_lock);
nextsi:
685 686 687 688
		/*
		 * 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
689 690 691 692 693
		 * 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
		 * swap_avail_head list then try it, otherwise start over.
694
		 */
695 696
		if (plist_node_empty(&next->avail_list))
			goto start_over;
Linus Torvalds's avatar
Linus Torvalds committed
697
	}
698

699 700
	spin_unlock(&swap_avail_lock);

701
	atomic_long_inc(&nr_swap_pages);
702 703
noswap:
	return (swp_entry_t) {0};
Linus Torvalds's avatar
Linus Torvalds committed
704 705
}

706
/* The only caller of this function is now suspend routine */
707 708 709 710 711 712
swp_entry_t get_swap_page_of_type(int type)
{
	struct swap_info_struct *si;
	pgoff_t offset;

	si = swap_info[type];
713
	spin_lock(&si->lock);
714
	if (si && (si->flags & SWP_WRITEOK)) {
715
		atomic_long_dec(&nr_swap_pages);
716 717 718
		/* This is called for allocating swap entry, not cache */
		offset = scan_swap_map(si, 1);
		if (offset) {
719
			spin_unlock(&si->lock);
720 721
			return swp_entry(type, offset);
		}
722
		atomic_long_inc(&nr_swap_pages);
723
	}
724
	spin_unlock(&si->lock);
725 726 727
	return (swp_entry_t) {0};
}

728
static struct swap_info_struct *swap_info_get(swp_entry_t entry)
Linus Torvalds's avatar
Linus Torvalds committed
729
{
730
	struct swap_info_struct *p;
Linus Torvalds's avatar
Linus Torvalds committed
731 732 733 734 735 736 737
	unsigned long offset, type;

	if (!entry.val)
		goto out;
	type = swp_type(entry);
	if (type >= nr_swapfiles)
		goto bad_nofile;
738
	p = swap_info[type];
Linus Torvalds's avatar
Linus Torvalds committed
739 740 741 742 743 744 745
	if (!(p->flags & SWP_USED))
		goto bad_device;
	offset = swp_offset(entry);
	if (offset >= p->max)
		goto bad_offset;
	if (!p->swap_map[offset])
		goto bad_free;
746
	spin_lock(&p->lock);
Linus Torvalds's avatar
Linus Torvalds committed
747 748 749
	return p;

bad_free:
750
	pr_err("swap_free: %s%08lx\n", Unused_offset, entry.val);
Linus Torvalds's avatar
Linus Torvalds committed
751 752
	goto out;
bad_offset:
753
	pr_err("swap_free: %s%08lx\n", Bad_offset, entry.val);
Linus Torvalds's avatar
Linus Torvalds committed
754 755
	goto out;
bad_device:
756
	pr_err("swap_free: %s%08lx\n", Unused_file, entry.val);
Linus Torvalds's avatar
Linus Torvalds committed
757 758
	goto out;
bad_nofile:
759
	pr_err("swap_free: %s%08lx\n", Bad_file, entry.val);
Linus Torvalds's avatar
Linus Torvalds committed
760 761
out:
	return NULL;
762
}
Linus Torvalds's avatar
Linus Torvalds committed
763

764 765
static unsigned char swap_entry_free(struct swap_info_struct *p,
				     swp_entry_t entry, unsigned char usage)
Linus Torvalds's avatar
Linus Torvalds committed
766
{
767
	unsigned long offset = swp_offset(entry);
768 769
	unsigned char count;
	unsigned char has_cache;
770

771 772 773
	count = p->swap_map[offset];
	has_cache = count & SWAP_HAS_CACHE;
	count &= ~SWAP_HAS_CACHE;
774

775
	if (usage == SWAP_HAS_CACHE) {
776
		VM_BUG_ON(!has_cache);
777
		has_cache = 0;
778 779 780 781 782 783
	} else if (count == SWAP_MAP_SHMEM) {
		/*
		 * Or we could insist on shmem.c using a special
		 * swap_shmem_free() and free_shmem_swap_and_cache()...
		 */
		count = 0;
784 785 786 787 788 789 790 791 792
	} else if ((count & ~COUNT_CONTINUED) <= SWAP_MAP_MAX) {
		if (count == COUNT_CONTINUED) {
			if (swap_count_continued(p, offset, count))
				count = SWAP_MAP_MAX | COUNT_CONTINUED;
			else
				count = SWAP_MAP_MAX;
		} else
			count--;
	}
793 794 795

	usage = count | has_cache;
	p->swap_map[offset] = usage;
796 797

	/* free if no reference */
798
	if (!usage) {
799
		mem_cgroup_uncharge_swap(entry);
800
		dec_cluster_info_page(p, p->cluster_info, offset);
801 802
		if (offset < p->lowest_bit)
			p->lowest_bit = offset;
803 804
		if (offset > p->highest_bit) {
			bool was_full = !p->highest_bit;
805
			p->highest_bit = offset;
806 807 808 809 810 811 812 813 814
			if (was_full && (p->flags & SWP_WRITEOK)) {
				spin_lock(&swap_avail_lock);
				WARN_ON(!plist_node_empty(&p->avail_list));
				if (plist_node_empty(&p->avail_list))
					plist_add(&p->avail_list,
						  &swap_avail_head);
				spin_unlock(&swap_avail_lock);
			}
		}
815
		atomic_long_inc(&nr_swap_pages);
816
		p->inuse_pages--;
817
		frontswap_invalidate_page(p->type, offset);
818 819 820 821 822 823
		if (p->flags & SWP_BLKDEV) {
			struct gendisk *disk = p->bdev->bd_disk;
			if (disk->fops->swap_slot_free_notify)
				disk->fops->swap_slot_free_notify(p->bdev,
								  offset);
		}
Linus Torvalds's avatar
Linus Torvalds committed
824
	}
825 826

	return usage;
Linus Torvalds's avatar
Linus Torvalds committed
827 828 829
}

/*
830
 * Caller has made sure that the swap device corresponding to entry
Linus Torvalds's avatar
Linus Torvalds committed
831 832 833 834
 * is still around or has not been recycled.
 */
void swap_free(swp_entry_t entry)
{
835
	struct swap_info_struct *p;
Linus Torvalds's avatar
Linus Torvalds committed
836 837 838

	p = swap_info_get(entry);
	if (p) {
839
		swap_entry_free(p, entry, 1);
840
		spin_unlock(&p->lock);
Linus Torvalds's avatar
Linus Torvalds committed
841 842 843
	}
}

844 845 846
/*
 * Called after dropping swapcache to decrease refcnt to swap entries.
 */
847
void swapcache_free(swp_entry_t entry)
848
{
849 850 851 852
	struct swap_info_struct *p;

	p = swap_info_get(entry);
	if (p) {
853
		swap_entry_free(p, entry, SWAP_HAS_CACHE);
854
		spin_unlock(&p->lock);
855
	}
856 857
}

Linus Torvalds's avatar
Linus Torvalds committed
858
/*
859
 * How many references to page are currently swapped out?
860 861
 * This does not give an exact answer when swap count is continued,
 * but does include the high COUNT_CONTINUED flag to allow for that.
Linus Torvalds's avatar
Linus Torvalds committed
862
 */
863
int page_swapcount(struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
864
{
865 866
	int count = 0;
	struct swap_info_struct *p;
Linus Torvalds's avatar
Linus Torvalds committed
867 868
	swp_entry_t entry;

869
	entry.val = page_private(page);
Linus Torvalds's avatar
Linus Torvalds committed
870 871
	p = swap_info_get(entry);
	if (p) {
872
		count = swap_count(p->swap_map[swp_offset(entry)]);
873
		spin_unlock(&p->lock);
Linus Torvalds's avatar
Linus Torvalds committed
874
	}
875
	return count;
Linus Torvalds's avatar
Linus Torvalds committed
876 877
}

878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906
/*
 * How many references to @entry are currently swapped out?
 * This considers COUNT_CONTINUED so it returns exact answer.
 */
int swp_swapcount(swp_entry_t entry)
{
	int count, tmp_count, n;
	struct swap_info_struct *p;
	struct page *page;
	pgoff_t offset;
	unsigned char *map;

	p = swap_info_get(entry);
	if (!p)
		return 0;

	count = swap_count(p->swap_map[swp_offset(entry)]);
	if (!(count & COUNT_CONTINUED))
		goto out;

	count &= ~COUNT_CONTINUED;
	n = SWAP_MAP_MAX + 1;

	offset = swp_offset(entry);
	page = vmalloc_to_page(p->swap_map + offset);
	offset &= ~PAGE_MASK;
	VM_BUG_ON(page_private(page) != SWP_CONTINUED);

	do {
907
		page = list_next_entry(page, lru);
908 909 910 911 912 913 914 915 916 917 918 919
		map = kmap_atomic(page);
		tmp_count = map[offset];
		kunmap_atomic(map);

		count += (tmp_count & ~COUNT_CONTINUED) * n;
		n *= (SWAP_CONT_MAX + 1);
	} while (tmp_count & COUNT_CONTINUED);
out:
	spin_unlock(&p->lock);
	return count;
}

Linus Torvalds's avatar
Linus Torvalds committed
920
/*
921 922 923 924
 * We can write to an anon page without COW if there are no other references
 * to it.  And as a side-effect, free up its swap: because the old content
 * on disk will never be read, and seeking back there to write new content
 * later would only waste time away from clustering.
925 926 927 928
 *
 * NOTE: total_mapcount should not be relied upon by the caller if
 * reuse_swap_page() returns false, but it may be always overwritten
 * (see the other implementation for CONFIG_SWAP=n).
Linus Torvalds's avatar
Linus Torvalds committed
929
 */
930
bool reuse_swap_page(struct page *page, int *total_mapcount)
Linus Torvalds's avatar
Linus Torvalds committed
931
{
932 933
	int count;

934
	VM_BUG_ON_PAGE(!PageLocked(page), page);
935
	if (unlikely(PageKsm(page)))
936 937
		return false;
	count = page_trans_huge_mapcount(page, total_mapcount);
938
	if (count <= 1 && PageSwapCache(page)) {
939
		count += page_swapcount(page);
940 941 942 943 944
		if (count == 1 && !PageWriteback(page)) {
			delete_from_swap_cache(page);
			SetPageDirty(page);
		}
	}
945
	return count <= 1;
Linus Torvalds's avatar
Linus Torvalds committed
946 947 948
}

/*
949 950
 * If swap is getting full, or if there are no more mappings of this page,
 * then try_to_free_swap is called to free its swap space.
Linus Torvalds's avatar
Linus Torvalds committed
951
 */
952
int try_to_free_swap(struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
953
{
954
	VM_BUG_ON_PAGE(!PageLocked(page), page);
Linus Torvalds's avatar
Linus Torvalds committed
955 956 957 958 959

	if (!PageSwapCache(page))
		return 0;
	if (PageWriteback(page))
		return 0;
960
	if (page_swapcount(page))
Linus Torvalds's avatar
Linus Torvalds committed
961 962
		return 0;

963 964 965 966 967 968 969 970 971 972 973 974
	/*
	 * Once hibernation has begun to create its image of memory,
	 * there's a danger that one of the calls to try_to_free_swap()
	 * - most probably a call from __try_to_reclaim_swap() while
	 * hibernation is allocating its own swap pages for the image,
	 * but conceivably even a call from memory reclaim - will free
	 * the swap from a page which has already been recorded in the
	 * image as a clean swapcache page, and then reuse its swap for
	 * another page of the image.  On waking from hibernation, the
	 * original page might be freed under memory pressure, then
	 * later read back in from swap, now with the wrong data.
	 *
975
	 * Hibernation suspends storage while it is writing the image
976
	 * to disk so check that here.
977
	 */
978
	if (pm_suspended_storage())
979 980
		return 0;

981 982 983
	delete_from_swap_cache(page);
	SetPageDirty(page);
	return 1;
984 985
}

Linus Torvalds's avatar
Linus Torvalds committed
986 987 988 989
/*
 * Free the swap entry like above, but also try to
 * free the page cache entry if it is the last user.
 */
990
int free_swap_and_cache(swp_entry_t entry)
Linus Torvalds's avatar
Linus Torvalds committed
991
{
992
	struct swap_info_struct *p;
Linus Torvalds's avatar
Linus Torvalds committed
993 994
	struct page *page = NULL;

995
	if (non_swap_entry(entry))
996
		return 1;
997

Linus Torvalds's avatar
Linus Torvalds committed
998 999
	p = swap_info_get(entry);
	if (p) {
1000
		if (swap_entry_free(p, entry, 1) == SWAP_HAS_CACHE) {
1001 1002
			page = find_get_page(swap_address_space(entry),
						entry.val);
1003
			if (page && !trylock_page(page)) {
1004
				put_page(page);
1005 1006 1007
				page = NULL;
			}
		}
1008
		spin_unlock(&p->lock);
Linus Torvalds's avatar
Linus Torvalds committed
1009 1010
	}
	if (page) {
1011 1012 1013 1014
		/*
		 * Not mapped elsewhere, or swap space full? Free it!
		 * Also recheck PageSwapCache now page is locked (above).
		 */
1015
		if (PageSwapCache(page) && !PageWriteback(page) &&
1016
		    (!page_mapped(page) || mem_cgroup_swap_full(page))) {
Linus Torvalds's avatar
Linus Torvalds committed
1017 1018 1019 1020
			delete_from_swap_cache(page);
			SetPageDirty(page);
		}
		unlock_page(page);
1021
		put_page(page);
Linus Torvalds's avatar
Linus Torvalds committed
1022
	}
1023
	return p != NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1024 1025
}

1026
#ifdef CONFIG_HIBERNATION
1027
/*
1028
 * Find the swap type that corresponds to given device (if any).
1029
 *
1030 1031 1032 1033
 * @offset - number of the PAGE_SIZE-sized block of the device, starting
 * from 0, in which the swap header is expected to be located.
 *
 * This is needed for the suspend to disk (aka swsusp).
1034
 */
1035
int swap_type_of(dev_t device, sector_t offset, struct block_device **bdev_p)
1036
{
1037
	struct block_device *bdev = NULL;
1038
	int type;
1039

1040 1041 1042
	if (device)
		bdev = bdget(device);

1043
	spin_lock(&swap_lock);
1044 1045
	for (type = 0; type < nr_swapfiles; type++) {
		struct swap_info_struct *sis = swap_info[type];
1046

1047
		if (!(sis->flags & SWP_WRITEOK))
1048
			continue;
1049

1050
		if (!bdev) {
1051
			if (bdev_p)
1052
				*bdev_p = bdgrab(sis->bdev);
1053

1054
			spin_unlock(&swap_lock);
1055
			return type;
1056
		}
1057
		if (bdev == sis->bdev) {
1058
			struct swap_extent *se = &sis->first_swap_extent;
1059 1060

			if (se->start_block == offset) {
1061
				if (bdev_p)
1062
					*bdev_p = bdgrab(sis->bdev);
1063

1064 1065
				spin_unlock(&swap_lock);
				bdput(bdev);
1066
				return type;
1067
			}
1068 1069 1070
		}
	}
	spin_unlock(&swap_lock);
1071 1072 1073
	if (bdev)
		bdput(bdev);

1074 1075 1076
	return -ENODEV;
}

1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088
/*
 * Get the (PAGE_SIZE) block corresponding to given offset on the swapdev
 * corresponding to given index in swap_info (swap type).
 */
sector_t swapdev_block(int type, pgoff_t offset)
{
	struct block_device *bdev;

	if ((unsigned int)type >= nr_swapfiles)
		return 0;
	if (!(swap_info[type]->flags & SWP_WRITEOK))
		return 0;
1089
	return map_swap_entry(swp_entry(type, offset), &bdev);
1090 1091
}

1092 1093 1094 1095 1096 1097 1098 1099 1100 1101
/*
 * Return either the total number of swap pages of given type, or the number
 * of free pages of that type (depending on @free)
 *
 * This is needed for software suspend
 */
unsigned int count_swap_pages(int type, int free)
{
	unsigned int n = 0;

1102 1103 1104 1105
	spin_lock(&swap_lock);
	if ((unsigned int)type < nr_swapfiles) {
		struct swap_info_struct *sis = swap_info[type];

1106
		spin_lock(&sis->lock);
1107 1108
		if (sis->flags & SWP_WRITEOK) {
			n = sis->pages;
1109
			if (free)
1110
				n -= sis->inuse_pages;
1111
		}
1112
		spin_unlock(&sis->lock);
1113
	}
1114
	spin_unlock(&swap_lock);
1115 1116
	return n;
}
1117
#endif /* CONFIG_HIBERNATION */
1118

1119
static inline int pte_same_as_swp(pte_t pte, pte_t swp_pte)
1120
{
1121
	return pte_same(pte_swp_clear_soft_dirty(pte), swp_pte);
1122 1123
}

Linus Torvalds's avatar
Linus Torvalds committed
1124
/*
1125 1126 1127
 * No need to decide whether this PTE shares the swap entry with others,
 * just let do_wp_page work it out if a write is requested later - to
 * force COW, vm_page_prot omits write permission from any private vma.
Linus Torvalds's avatar
Linus Torvalds committed
1128
 */
1129
static int unuse_pte(struct vm_area_struct *vma, pmd_t *pmd,
Linus Torvalds's avatar
Linus Torvalds committed
1130 1131
		unsigned long addr, swp_entry_t entry, struct page *page)
{
1132
	struct page *swapcache;
1133
	struct mem_cgroup *memcg;
1134 1135 1136 1137
	spinlock_t *ptl;
	pte_t *pte;
	int ret = 1;

1138 1139 1140 1141 1142
	swapcache = page;
	page = ksm_might_need_to_copy(page, vma, addr);
	if (unlikely(!page))
		return -ENOMEM;

1143 1144
	if (mem_cgroup_try_charge(page, vma->vm_mm, GFP_KERNEL,
				&memcg, false)) {
1145
		ret = -ENOMEM;
1146 1147
		goto out_nolock;
	}
1148 1149

	pte = pte_offset_map_lock(vma->vm_mm, pmd, addr, &ptl);
1150
	if (unlikely(!pte_same_as_swp(*pte, swp_entry_to_pte(entry)))) {
1151
		mem_cgroup_cancel_charge(page, memcg, false);
1152 1153 1154
		ret = 0;
		goto out;
	}
1155

KAMEZAWA Hiroyuki's avatar
KAMEZAWA Hiroyuki committed
1156
	dec_mm_counter(vma->vm_mm, MM_SWAPENTS);
1157
	inc_mm_counter(vma->vm_mm, MM_ANONPAGES);
Linus Torvalds's avatar
Linus Torvalds committed
1158 1159 1160
	get_page(page);
	set_pte_at(vma->vm_mm, addr, pte,
		   pte_mkold(mk_pte(page, vma->vm_page_prot)));
1161
	if (page == swapcache) {
1162
		page_add_anon_rmap(page, vma, addr, false);
1163
		mem_cgroup_commit_charge(page, memcg, true, false);
1164
	} else { /* ksm created a completely new copy */
1165
		page_add_new_anon_rmap(page, vma, addr, false);
1166
		mem_cgroup_commit_charge(page, memcg, false, false);
1167 1168
		lru_cache_add_active_or_unevictable(page, vma);
	}
Linus Torvalds's avatar
Linus Torvalds committed
1169 1170 1171 1172 1173 1174
	swap_free(entry);
	/*
	 * Move the page to the active list so it is not
	 * immediately swapped out again after swapon.
	 */
	activate_page(page);
1175 1176
out:
	pte_unmap_unlock(pte, ptl);
1177
out_nolock:
1178 1179 1180 1181
	if (page != swapcache) {
		unlock_page(page);
		put_page(page);
	}
1182
	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1183 1184 1185 1186 1187 1188 1189
}

static int unuse_pte_range(struct vm_area_struct *vma, pmd_t *pmd,
				unsigned long addr, unsigned long end,
				swp_entry_t entry, struct page *page)
{
	pte_t swp_pte = swp_entry_to_pte(entry);
1190
	pte_t *pte;
1191
	int ret = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1192

1193 1194 1195 1196 1197 1198 1199
	/*
	 * We don't actually need pte lock while scanning for swp_pte: since
	 * we hold page lock and mmap_sem, swp_pte cannot be inserted into the
	 * page table while we're scanning; though it could get zapped, and on
	 * some architectures (e.g. x86_32 with PAE) we might catch a glimpse
	 * of unmatched parts which look like swp_pte, so unuse_pte must
	 * recheck under pte lock.  Scanning without pte lock lets it be
1200
	 * preemptable whenever CONFIG_PREEMPT but not CONFIG_HIGHPTE.
1201 1202
	 */
	pte = pte_offset_map(pmd, addr);
Linus Torvalds's avatar
Linus Torvalds committed
1203 1204 1205 1206 1207
	do {
		/*
		 * swapoff spends a _lot_ of time in this loop!
		 * Test inline before going to call unuse_pte.
		 */
1208
		if (unlikely(pte_same_as_swp(*pte, swp_pte))) {
1209 1210 1211 1212 1213
			pte_unmap(pte);
			ret = unuse_pte(vma, pmd, addr, entry, page);
			if (ret)
				goto out;
			pte = pte_offset_map(pmd, addr);
Linus Torvalds's avatar
Linus Torvalds committed
1214 1215
		}
	} while (pte++, addr += PAGE_SIZE, addr != end);
1216 1217
	pte_unmap(pte - 1);
out:
1218
	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1219 1220 1221 1222 1223 1224 1225 1226
}

static inline int unuse_pmd_range(struct vm_area_struct *vma, pud_t *pud,
				unsigned long addr, unsigned long end,
				swp_entry_t entry, struct page *page)
{
	pmd_t *pmd;
	unsigned long next;
1227
	int ret;
Linus Torvalds's avatar
Linus Torvalds committed
1228 1229 1230 1231

	pmd = pmd_offset(pud, addr);
	do {
		next = pmd_addr_end(addr, end);
1232
		if (pmd_none_or_trans_huge_or_clear_bad(pmd))
Linus Torvalds's avatar
Linus Torvalds committed
1233
			continue;
1234 1235 1236
		ret = unuse_pte_range(vma, pmd, addr, next, entry, page);
		if (ret)
			return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1237 1238 1239 1240 1241 1242 1243 1244 1245 1246
	} while (pmd++, addr = next, addr != end);
	return 0;
}

static inline int unuse_pud_range(struct vm_area_struct *vma, pgd_t *pgd,
				unsigned long addr, unsigned long end,
				swp_entry_t entry, struct page *page)
{
	pud_t *pud;
	unsigned long next;
1247
	int ret;
Linus Torvalds's avatar
Linus Torvalds committed
1248 1249 1250 1251 1252 1253

	pud = pud_offset(pgd, addr);
	do {
		next = pud_addr_end(addr, end);
		if (pud_none_or_clear_bad(pud))
			continue;
1254 1255 1256
		ret = unuse_pmd_range(vma, pud, addr, next, entry, page);
		if (ret)
			return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1257 1258 1259 1260 1261 1262 1263 1264 1265
	} while (pud++, addr = next, addr != end);
	return 0;
}

static int unuse_vma(struct vm_area_struct *vma,
				swp_entry_t entry, struct page *page)
{
	pgd_t *pgd;
	unsigned long addr, end, next;
1266
	int ret;
Linus Torvalds's avatar
Linus Torvalds committed
1267

1268
	if (page_anon_vma(page)) {
Linus Torvalds's avatar
Linus Torvalds committed
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
		addr = page_address_in_vma(page, vma);
		if (addr == -EFAULT)
			return 0;
		else
			end = addr + PAGE_SIZE;
	} else {
		addr = vma->vm_start;
		end = vma->vm_end;
	}

	pgd = pgd_offset(vma->vm_mm, addr);
	do {
		next = pgd_addr_end(addr, end);
		if (pgd_none_or_clear_bad(pgd))
			continue;
1284 1285 1286
		ret = unuse_pud_range(vma, pgd, addr, next, entry, page);
		if (ret)
			return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1287 1288 1289 1290 1291 1292 1293 1294
	} while (pgd++, addr = next, addr != end);
	return 0;
}

static int unuse_mm(struct mm_struct *mm,
				swp_entry_t entry, struct page *page)
{
	struct vm_area_struct *vma;
1295
	int ret = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1296 1297 1298

	if (!down_read_trylock(&mm->mmap_sem)) {
		/*
1299 1300
		 * Activate page so shrink_inactive_list is unlikely to unmap
		 * its ptes while lock is dropped, so swapoff can make progress.
Linus Torvalds's avatar
Linus Torvalds committed
1301
		 */
1302
		activate_page(page);
Linus Torvalds's avatar
Linus Torvalds committed
1303 1304 1305 1306 1307
		unlock_page(page);
		down_read(&mm->mmap_sem);
		lock_page(page);
	}
	for (vma = mm->mmap; vma; vma = vma->vm_next) {
1308
		if (vma->anon_vma && (ret = unuse_vma(vma, entry, page)))
Linus Torvalds's avatar
Linus Torvalds committed
1309 1310 1311
			break;
	}
	up_read(&mm->mmap_sem);
1312
	return (ret < 0)? ret: 0;
Linus Torvalds's avatar
Linus Torvalds committed
1313 1314 1315
}

/*
1316 1317
 * Scan swap_map (or frontswap_map if frontswap parameter is true)
 * from current position to next entry still in use.
Linus Torvalds's avatar
Linus Torvalds committed
1318 1319
 * Recycle to start on reaching the end, returning 0 when empty.
 */
1320
static unsigned int find_next_to_unuse(struct swap_info_struct *si,
1321
					unsigned int prev, bool frontswap)
Linus Torvalds's avatar
Linus Torvalds committed
1322
{
1323 1324
	unsigned int max = si->max;
	unsigned int i = prev;
1325
	unsigned char count;
Linus Torvalds's avatar
Linus Torvalds committed
1326 1327

	/*
1328
	 * No need for swap_lock here: we're just looking
Linus Torvalds's avatar
Linus Torvalds committed
1329 1330
	 * for whether an entry is in use, not modifying it; false
	 * hits are okay, and sys_swapoff() has already prevented new
1331
	 * allocations from this area (while holding swap_lock).
Linus Torvalds's avatar
Linus Torvalds committed
1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346
	 */
	for (;;) {
		if (++i >= max) {
			if (!prev) {
				i = 0;
				break;
			}
			/*
			 * No entries in use at top of swap_map,
			 * loop back to start and recheck there.
			 */
			max = prev + 1;
			prev = 0;
			i = 1;
		}
1347 1348 1349 1350 1351 1352
		if (frontswap) {
			if (frontswap_test(si, i))
				break;
			else
				continue;
		}
1353
		count = READ_ONCE(si->swap_map[i]);
1354
		if (count && swap_count(count) != SWAP_MAP_BAD)
Linus Torvalds's avatar
Linus Torvalds committed
1355 1356 1357 1358 1359 1360 1361 1362 1363
			break;
	}
	return i;
}

/*
 * We completely avoid races by reading each swap page in advance,
 * and then search for the process using it.  All the necessary
 * page table adjustments can then be made atomically.
1364 1365 1366
 *
 * if the boolean frontswap is true, only unuse pages_to_unuse pages;
 * pages_to_unuse==0 means all pages; ignored if frontswap is false
Linus Torvalds's avatar
Linus Torvalds committed
1367
 */
1368 1369
int try_to_unuse(unsigned int type, bool frontswap,
		 unsigned long pages_to_unuse)
Linus Torvalds's avatar
Linus Torvalds committed
1370
{
1371
	struct swap_info_struct *si = swap_info[type];
Linus Torvalds's avatar
Linus Torvalds committed
1372
	struct mm_struct *start_mm;
1373 1374 1375 1376 1377
	volatile unsigned char *swap_map; /* swap_map is accessed without
					   * locking. Mark it as volatile
					   * to prevent compiler doing
					   * something odd.
					   */
1378
	unsigned char swcount;
Linus Torvalds's avatar
Linus Torvalds committed
1379 1380
	struct page *page;
	swp_entry_t entry;
1381
	unsigned int i = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395
	int retval = 0;

	/*
	 * When searching mms for an entry, a good strategy is to
	 * start at the first mm we freed the previous entry from
	 * (though actually we don't notice whether we or coincidence
	 * freed the entry).  Initialize this start_mm with a hold.
	 *
	 * A simpler strategy would be to start at the last mm we
	 * freed the previous entry from; but that would take less
	 * advantage of mmlist ordering, which clusters forked mms
	 * together, child after parent.  If we race with dup_mmap(), we
	 * prefer to resolve parent before child, lest we miss entries
	 * duplicated after we scanned child: using last mm would invert