/* *  linux/mm/swap.c * *  Copyright (C) 1991, 1992  Linus Torvalds *//* * This file should contain most things doing the swapping from/to disk. * Started 18.12.91 */#include <linux/mm.h>#include <linux/sched.h>#include <linux/head.h>#include <linux/kernel.h>#include <linux/kernel_stat.h>#include <linux/errno.h>#include <linux/string.h>#include <linux/stat.h>#include <asm/system.h> /* for cli()/sti() */#include <asm/bitops.h>#define MAX_SWAPFILES 8#define SWP_USED	1#define SWP_WRITEOK	3#define SWP_TYPE(entry) (((entry) & 0xfe) >> 1)#define SWP_OFFSET(entry) ((entry) >> PAGE_SHIFT)#define SWP_ENTRY(type,offset) (((type) << 1) | ((offset) << PAGE_SHIFT))static int nr_swapfiles = 0;static struct wait_queue * lock_queue = NULL;static struct swap_info_struct {	unsigned long flags;	struct inode * swap_file;	unsigned int swap_device;	unsigned char * swap_map;	unsigned char * swap_lockmap;	int pages;	int lowest_bit;	int highest_bit;	unsigned long max;} swap_info[MAX_SWAPFILES];extern unsigned long free_page_list;extern int shm_swap (int);/* * The following are used to make sure we don't thrash too much... * NOTE!! NR_LAST_FREE_PAGES must be a power of 2... */#define NR_LAST_FREE_PAGES 32static unsigned long last_free_pages[NR_LAST_FREE_PAGES] = {0,};void rw_swap_page(int rw, unsigned long entry, char * buf){	unsigned long type, offset;	struct swap_info_struct * p;	type = SWP_TYPE(entry);	if (type >= nr_swapfiles) {		printk("Internal error: bad swap-device\n");		return;	}	p = &swap_info[type];	offset = SWP_OFFSET(entry);	if (offset >= p->max) {		printk("rw_swap_page: weirdness\n");		return;	}	if (!(p->flags & SWP_USED)) {		printk("Trying to swap to unused swap-device\n");		return;	}	while (set_bit(offset,p->swap_lockmap))		sleep_on(&lock_queue);	if (rw == READ)		kstat.pswpin++;	else		kstat.pswpout++;	if (p->swap_device) {		ll_rw_page(rw,p->swap_device,offset,buf);	} else if (p->swap_file) {		unsigned int zones[8];		unsigned int block;		int i, j;		block = offset << (12 - p->swap_file->i_sb->s_blocksize_bits);		for (i=0, j=0; j< PAGE_SIZE ; i++, j +=p->swap_file->i_sb->s_blocksize)			if (!(zones[i] = bmap(p->swap_file,block++))) {				printk("rw_swap_page: bad swap file\n");				return;			}		ll_rw_swap_file(rw,p->swap_file->i_dev, zones, i,buf);	} else		printk("re_swap_page: no swap file or device\n");	if (offset && !clear_bit(offset,p->swap_lockmap))		printk("rw_swap_page: lock already cleared\n");	wake_up(&lock_queue);}unsigned int get_swap_page(void){	struct swap_info_struct * p;	unsigned int offset, type;	p = swap_info;	for (type = 0 ; type < nr_swapfiles ; type++,p++) {		if ((p->flags & SWP_WRITEOK) != SWP_WRITEOK)			continue;		for (offset = p->lowest_bit; offset <= p->highest_bit ; offset++) {			if (p->swap_map[offset])				continue;			p->swap_map[offset] = 1;			nr_swap_pages--;			if (offset == p->highest_bit)				p->highest_bit--;			p->lowest_bit = offset;			return SWP_ENTRY(type,offset);		}	}	return 0;}unsigned long swap_duplicate(unsigned long entry){	struct swap_info_struct * p;	unsigned long offset, type;	if (!entry)		return 0;	offset = SWP_OFFSET(entry);	type = SWP_TYPE(entry);	if (type == SHM_SWP_TYPE)		return entry;	if (type >= nr_swapfiles) {		printk("Trying to duplicate nonexistent swap-page\n");		return 0;	}	p = type + swap_info;	if (offset >= p->max) {		printk("swap_free: weirdness\n");		return 0;	}	if (!p->swap_map[offset]) {		printk("swap_duplicate: trying to duplicate unused page\n");		return 0;	}	p->swap_map[offset]++;	return entry;}void swap_free(unsigned long entry){	struct swap_info_struct * p;	unsigned long offset, type;	if (!entry)		return;	type = SWP_TYPE(entry);	if (type == SHM_SWP_TYPE)		return;	if (type >= nr_swapfiles) {		printk("Trying to free nonexistent swap-page\n");		return;	}	p = & swap_info[type];	offset = SWP_OFFSET(entry);	if (offset >= p->max) {		printk("swap_free: weirdness\n");		return;	}	if (!(p->flags & SWP_USED)) {		printk("Trying to free swap from unused swap-device\n");		return;	}	while (set_bit(offset,p->swap_lockmap))		sleep_on(&lock_queue);	if (offset < p->lowest_bit)		p->lowest_bit = offset;	if (offset > p->highest_bit)		p->highest_bit = offset;	if (!p->swap_map[offset])		printk("swap_free: swap-space map bad (entry %08lx)\n",entry);	else		if (!--p->swap_map[offset])			nr_swap_pages++;	if (!clear_bit(offset,p->swap_lockmap))		printk("swap_free: lock already cleared\n");	wake_up(&lock_queue);}void swap_in(unsigned long *table_ptr){	unsigned long entry;	unsigned long page;	entry = *table_ptr;	if (PAGE_PRESENT & entry) {		printk("trying to swap in present page\n");		return;	}	if (!entry) {		printk("No swap page in swap_in\n");		return;	}	if (SWP_TYPE(entry) == SHM_SWP_TYPE) {		shm_no_page ((unsigned long *) table_ptr);		return;	}	if (!(page = get_free_page(GFP_KERNEL))) {		oom(current);		page = BAD_PAGE;	} else			read_swap_page(entry, (char *) page);	if (*table_ptr != entry) {		free_page(page);		return;	}	*table_ptr = page | (PAGE_DIRTY | PAGE_PRIVATE);	swap_free(entry);}static inline int try_to_swap_out(unsigned long * table_ptr){	int i;	unsigned long page;	unsigned long entry;	page = *table_ptr;	if (!(PAGE_PRESENT & page))		return 0;	if (page >= high_memory)		return 0;	if (mem_map[MAP_NR(page)] & MAP_PAGE_RESERVED)		return 0;	if (PAGE_ACCESSED & page) {		*table_ptr &= ~PAGE_ACCESSED;		return 0;	}	for (i = 0; i < NR_LAST_FREE_PAGES; i++)		if (last_free_pages[i] == (page & PAGE_MASK))			return 0;	if (PAGE_DIRTY & page) {		page &= PAGE_MASK;		if (mem_map[MAP_NR(page)] != 1)			return 0;		if (!(entry = get_swap_page()))			return 0;		*table_ptr = entry;		invalidate();		write_swap_page(entry, (char *) page);		free_page(page);		return 1;	}	page &= PAGE_MASK;	*table_ptr = 0;	invalidate();	free_page(page);	return 1 + mem_map[MAP_NR(page)];}/* * sys_idle() does nothing much: it just searches for likely candidates for * swapping out or forgetting about. This speeds up the search when we * actually have to swap. */asmlinkage int sys_idle(void){	need_resched = 1;	return 0;}/* * A new implementation of swap_out().  We do not swap complete processes, * but only a small number of blocks, before we continue with the next * process.  The number of blocks actually swapped is determined on the * number of page faults, that this process actually had in the last time, * so we won't swap heavily used processes all the time ... * * Note: the priority argument is a hint on much CPU to waste with the *       swap block search, not a hint, of how much blocks to swap with *       each process. * * (C) 1993 Kai Petzke, wpp@marie.physik.tu-berlin.de */#ifdef NEW_SWAP/* * These are the miminum and maximum number of pages to swap from one process, * before proceeding to the next: */#define SWAP_MIN	4#define SWAP_MAX	32/* * The actual number of pages to swap is determined as: * SWAP_RATIO / (number of recent major page faults) */#define SWAP_RATIO	128static int swap_out(unsigned int priority){    static int swap_task;    int table;    int page;    long pg_table;    int loop;    int counter = NR_TASKS * 2 >> priority;    struct task_struct *p;    counter = NR_TASKS * 2 >> priority;    for(; counter >= 0; counter--, swap_task++) {	/*	 * Check that swap_task is suitable for swapping.  If not, look for	 * the next suitable process.	 */	loop = 0;	while(1) {	    if(swap_task >= NR_TASKS) {		swap_task = 1;		if(loop)		    /* all processes are unswappable or already swapped out */		    return 0;		loop = 1;	    }	    p = task[swap_task];	    if(p && p->swappable && p->rss)		break;	    swap_task++;	}	/*	 * Determine the number of pages to swap from this process.	 */	if(! p -> swap_cnt) {	    p->dec_flt = (p->dec_flt * 3) / 4 + p->maj_flt - p->old_maj_flt;	    p->old_maj_flt = p->maj_flt;	    if(p->dec_flt >= SWAP_RATIO / SWAP_MIN) {		p->dec_flt = SWAP_RATIO / SWAP_MIN;		p->swap_cnt = SWAP_MIN;	    } else if(p->dec_flt <= SWAP_RATIO / SWAP_MAX)		p->swap_cnt = SWAP_MAX;	    else		p->swap_cnt = SWAP_RATIO / p->dec_flt;	}	/*	 * Go through process' page directory.	 */	for(table = p->swap_table; table < 1024; table++) {	    pg_table = ((unsigned long *) p->tss.cr3)[table];	    if(pg_table >= high_memory)		    continue;	    if(mem_map[MAP_NR(pg_table)] & MAP_PAGE_RESERVED)		    continue;	    if(!(PAGE_PRESENT & pg_table)) {		    printk("swap_out: bad page-table at pg_dir[%d]: %08lx\n",			    table, pg_table);		    ((unsigned long *) p->tss.cr3)[table] = 0;		    continue;	    }	    pg_table &= 0xfffff000;	    /*	     * Go through this page table.	     */	    for(page = p->swap_page; page < 1024; page++) {		switch(try_to_swap_out(page + (unsigned long *) pg_table)) {		    case 0:			break;		    case 1:			p->rss--;			/* continue with the following page the next time */			p->swap_table = table;			p->swap_page  = page + 1;			if((--p->swap_cnt) == 0)			    swap_task++;			return 1;		    default:			p->rss--;			break;		}	    }	    p->swap_page = 0;	}	/*	 * Finish work with this process, if we reached the end of the page	 * directory.  Mark restart from the beginning the next time.	 */	p->swap_table = 0;    }    return 0;}#else /* old swapping procedure *//* * Go through the page tables, searching for a user page that * we can swap out. *  * We now check that the process is swappable (normally only 'init' * is un-swappable), allowing high-priority processes which cannot be * swapped out (things like user-level device drivers (Not implemented)). */static int swap_out(unsigned int priority){	static int swap_task = 1;	static int swap_table = 0;	static int swap_page = 0;	int counter = NR_TASKS*8;	int pg_table;	struct task_struct * p;	counter >>= priority;check_task:	if (counter-- < 0)		return 0;	if (swap_task >= NR_TASKS) {