mm/memory.c

/* */
This source file includes following definitions.
free_page
free_page_tables
copy_page_tables
put_page
put_dirty_page
un_wp_page
do_wp_page
write_verify
get_empty_page
try_to_share
share_page
do_no_page
mem_init
show_mem
do_page_fault
   1 /*
   2  *  linux/mm/memory.c
   3  *
   4  *  (C) 1991  Linus Torvalds
   5  */
   6 
   7 /*
   8  * demand-loading started 01.12.91 - seems it is high on the list of
   9  * things wanted, and it should be easy to implement. - Linus
  10  */
  11 
  12 /*
  13  * Ok, demand-loading was easy, shared pages a little bit tricker. Shared
  14  * pages started 02.12.91, seems to work. - Linus.
  15  *
  16  * Tested sharing by executing about 30 /bin/sh: under the old kernel it
  17  * would have taken more than the 6M I have free, but it worked well as
  18  * far as I could see.
  19  *
  20  * Also corrected some "invalidate()"s - I wasn't doing enough of them.
  21  */
  22 
  23 /*
  24  * Real VM (paging to/from disk) started 18.12.91. Much more work and
  25  * thought has to go into this. Oh, well..
  26  * 19.12.91  -  works, somewhat. Sometimes I get faults, don't know why.
  27  *              Found it. Everything seems to work now.
  28  * 20.12.91  -  Ok, making the swap-device changeable like the root.
  29  */
  30 
  31 #include <signal.h>
  32 
  33 #include <asm/system.h>
  34 
  35 #include <linux/sched.h>
  36 #include <linux/head.h>
  37 #include <linux/kernel.h>
  38 
  39 #define CODE_SPACE(addr) ((((addr)+4095)&~4095) < \
  40 current->start_code + current->end_code)
  41 
  42 unsigned long HIGH_MEMORY = 0;
  43 
  44 #define copy_page(from,to) \
  45 __asm__("cld ; rep ; movsl"::"S" (from),"D" (to),"c" (1024):"cx","di","si")
  46 
  47 #define CHECK_LAST_NR   16
  48 
  49 static unsigned long last_pages[CHECK_LAST_NR] = { 0, };
  50 
  51 unsigned char mem_map [ PAGING_PAGES ] = {0,};
  52 
  53 /*
  54  * Free a page of memory at physical address 'addr'. Used by
  55  * 'free_page_tables()'
  56  */
  57 void free_page(unsigned long addr)
     /*  */
  58 {
  59         if (addr < LOW_MEM) return;
  60         if (addr < HIGH_MEMORY) {
  61                 addr -= LOW_MEM;
  62                 addr >>= 12;
  63                 if (mem_map[addr]--)
  64                         return;
  65                 mem_map[addr]=0;
  66         }
  67         printk("trying to free free page: memory probably corrupted");
  68 }
  69 
  70 /*
  71  * This function frees a continuos block of page tables, as needed
  72  * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
  73  */
  74 int free_page_tables(unsigned long from,unsigned long size)
     /*  */
  75 {
  76         unsigned long page;
  77         unsigned long page_dir;
  78         unsigned long *pg_table;
  79         unsigned long * dir, nr;
  80 
  81         if (from & 0x3fffff)
  82                 panic("free_page_tables called with wrong alignment");
  83         if (!from)
  84                 panic("Trying to free up swapper memory space");
  85         size = (size + 0x3fffff) >> 22;
  86         dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
  87         for ( ; size-->0 ; dir++) {
  88                 if (!(page_dir = *dir))
  89                         continue;
  90                 *dir = 0;
  91                 if (!(page_dir & 1)) {
  92                         printk("free_page_tables: bad page directory.");
  93                         continue;
  94                 }
  95                 pg_table = (unsigned long *) (0xfffff000 & page_dir);
  96                 for (nr=0 ; nr<1024 ; nr++,pg_table++) {
  97                         if (!(page = *pg_table))
  98                                 continue;
  99                         *pg_table = 0;
 100                         if (1 & page)
 101                                 free_page(0xfffff000 & page);
 102                         else
 103                                 swap_free(page >> 1);
 104                 }
 105                 free_page(0xfffff000 & page_dir);
 106         }
 107         invalidate();
 108         for (page = 0; page < CHECK_LAST_NR ; page++)
 109                 last_pages[page] = 0;
 110         return 0;
 111 }
 112 
 113 /*
 114  *  Well, here is one of the most complicated functions in mm. It
 115  * copies a range of linerar addresses by copying only the pages.
 116  * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
 117  *
 118  * Note! We don't copy just any chunks of memory - addresses have to
 119  * be divisible by 4Mb (one page-directory entry), as this makes the
 120  * function easier. It's used only by fork anyway.
 121  *
 122  * NOTE 2!! When from==0 we are copying kernel space for the first
 123  * fork(). Then we DONT want to copy a full page-directory entry, as
 124  * that would lead to some serious memory waste - we just copy the
 125  * first 160 pages - 640kB. Even that is more than we need, but it
 126  * doesn't take any more memory - we don't copy-on-write in the low
 127  * 1 Mb-range, so the pages can be shared with the kernel. Thus the
 128  * special case for nr=xxxx.
 129  */
 130 int copy_page_tables(unsigned long from,unsigned long to,long size)
     /*  */
 131 {
 132         unsigned long * from_page_table;
 133         unsigned long * to_page_table;
 134         unsigned long this_page;
 135         unsigned long * from_dir, * to_dir;
 136         unsigned long new_page;
 137         unsigned long nr;
 138 
 139         if ((from&0x3fffff) || (to&0x3fffff))
 140                 panic("copy_page_tables called with wrong alignment");
 141         from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
 142         to_dir = (unsigned long *) ((to>>20) & 0xffc);
 143         size = ((unsigned) (size+0x3fffff)) >> 22;
 144         for( ; size-->0 ; from_dir++,to_dir++) {
 145                 if (*to_dir)
 146                         printk("copy_page_tables: already exist, "
 147                                 "probable memory corruption\n");
 148                 if (!*from_dir)
 149                         continue;
 150                 if (!(1 & *from_dir)) {
 151                         printk("copy_page_tables: page table swapped out, "
 152                                 "probable memory corruption");
 153                         *from_dir = 0;
 154                         continue;
 155                 }
 156                 from_page_table = (unsigned long *) (0xfffff000 & *from_dir);
 157                 if (!(to_page_table = (unsigned long *) get_free_page()))
 158                         return -1;      /* Out of memory, see freeing */
 159                 *to_dir = ((unsigned long) to_page_table) | 7;
 160                 nr = (from==0)?0xA0:1024;
 161                 for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
 162                         this_page = *from_page_table;
 163                         if (!this_page)
 164                                 continue;
 165                         if (!(1 & this_page)) {
 166                                 if (!(new_page = get_free_page()))
 167                                         return -1;
 168                                 ++current->rss;
 169                                 read_swap_page(this_page>>1, (char *) new_page);
 170                                 *to_page_table = this_page;
 171                                 *from_page_table = new_page | (PAGE_DIRTY | 7);
 172                                 continue;
 173                         }
 174                         this_page &= ~2;
 175                         *to_page_table = this_page;
 176                         if (this_page > LOW_MEM) {
 177                                 *from_page_table = this_page;
 178                                 this_page -= LOW_MEM;
 179                                 this_page >>= 12;
 180                                 mem_map[this_page]++;
 181                         }
 182                 }
 183         }
 184         invalidate();
 185         return 0;
 186 }
 187 
 188 /*
 189  * This function puts a page in memory at the wanted address.
 190  * It returns the physical address of the page gotten, 0 if
 191  * out of memory (either when trying to access page-table or
 192  * page.)
 193  */
 194 static unsigned long put_page(unsigned long page,unsigned long address)
     /*  */
 195 {
 196         unsigned long tmp, *page_table;
 197 
 198 /* NOTE !!! This uses the fact that _pg_dir=0 */
 199 
 200         if (page < LOW_MEM || page >= HIGH_MEMORY) {
 201                 printk("put_page: trying to put page %p at %p\n",page,address);
 202                 return 0;
 203         }
 204         if (mem_map[(page-LOW_MEM)>>12] != 1) {
 205                 printk("mem_map disagrees with %p at %p\n",page,address);
 206                 return 0;
 207         }
 208         page_table = (unsigned long *) ((address>>20) & 0xffc);
 209         if ((*page_table)&1)
 210                 page_table = (unsigned long *) (0xfffff000 & *page_table);
 211         else {
 212                 if (!(tmp=get_free_page()))
 213                         return 0;
 214                 *page_table = tmp | 7;
 215                 page_table = (unsigned long *) tmp;
 216         }
 217         page_table += (address>>12) & 0x3ff;
 218         if (*page_table) {
 219                 printk("put_page: page already exists\n");
 220                 *page_table = 0;
 221                 invalidate();
 222         }
 223         *page_table = page | 7;
 224 /* no need for invalidate */
 225         return page;
 226 }
 227 
 228 /*
 229  * The previous function doesn't work very well if you also want to mark
 230  * the page dirty: exec.c wants this, as it has earlier changed the page,
 231  * and we want the dirty-status to be correct (for VM). Thus the same
 232  * routine, but this time we mark it dirty too.
 233  */
 234 unsigned long put_dirty_page(unsigned long page, unsigned long address)
     /*  */
 235 {
 236         unsigned long tmp, *page_table;
 237 
 238 /* NOTE !!! This uses the fact that _pg_dir=0 */
 239 
 240         if (page < LOW_MEM || page >= HIGH_MEMORY)
 241                 printk("put_dirty_page: trying to put page %p at %p\n",page,address);
 242         if (mem_map[(page-LOW_MEM)>>12] != 1)
 243                 printk("mem_map disagrees with %p at %p\n",page,address);
 244         page_table = (unsigned long *) ((address>>20) & 0xffc);
 245         if ((*page_table)&1)
 246                 page_table = (unsigned long *) (0xfffff000 & *page_table);
 247         else {
 248                 if (!(tmp=get_free_page()))
 249                         return 0;
 250                 *page_table = tmp|7;
 251                 page_table = (unsigned long *) tmp;
 252         }
 253         page_table += (address>>12) & 0x3ff;
 254         if (*page_table) {
 255                 printk("put_dirty_page: page already exists\n");
 256                 *page_table = 0;
 257                 invalidate();
 258         }
 259         *page_table = page | (PAGE_DIRTY | 7);
 260 /* no need for invalidate */
 261         return page;
 262 }
 263 
 264 void un_wp_page(unsigned long * table_entry)
     /*  */
 265 {
 266         unsigned long old_page;
 267         unsigned long new_page = 0;
 268         unsigned long dirty;
 269 
 270 repeat:
 271         old_page = *table_entry;
 272         dirty = old_page & PAGE_DIRTY;
 273         if (!(old_page & 1)) {
 274                 if (new_page)
 275                         free_page(new_page);
 276                 return;
 277         }
 278         old_page &= 0xfffff000;
 279         if (old_page >= HIGH_MEMORY) {
 280                 if (new_page)
 281                         free_page(new_page);
 282                 printk("bad page address\n\r");
 283                 do_exit(SIGSEGV);
 284         }
 285         if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
 286                 *table_entry |= 2;
 287                 invalidate();
 288                 if (new_page)
 289                         free_page(new_page);
 290                 return;
 291         }
 292         if (!new_page) {
 293                 if (!(new_page=get_free_page()))
 294                         oom();
 295                 goto repeat;
 296         }
 297         copy_page(old_page,new_page);
 298         *table_entry = new_page | dirty | 7;
 299         free_page(old_page);
 300         invalidate();
 301 }       
 302 
 303 /*
 304  * This routine handles present pages, when users try to write
 305  * to a shared page. It is done by copying the page to a new address
 306  * and decrementing the shared-page counter for the old page.
 307  *
 308  * If it's in code space we exit with a segment error.
 309  */
 310 void do_wp_page(unsigned long error_code,unsigned long address)
     /*  */
 311 {
 312         if (address < TASK_SIZE) {
 313                 printk("\n\rBAD! KERNEL MEMORY WP-ERR!\n\r");
 314                 do_exit(SIGSEGV);
 315         }
 316         if (address - current->start_code >= TASK_SIZE) {
 317                 printk("Bad things happen: page error in do_wp_page\n\r");
 318                 do_exit(SIGSEGV);
 319         }
 320         ++current->min_flt;
 321         un_wp_page((unsigned long *)
 322                 (((address>>10) & 0xffc) + (0xfffff000 &
 323                 *((unsigned long *) ((address>>20) &0xffc)))));
 324 }
 325 
 326 void write_verify(unsigned long address)
     /*  */
 327 {
 328         unsigned long page;
 329 
 330         if (!( (page = *((unsigned long *) ((address>>20) & 0xffc)) )&1))
 331                 return;
 332         page &= 0xfffff000;
 333         page += ((address>>10) & 0xffc);
 334         if ((3 & *(unsigned long *) page) == 1)  /* non-writeable, present */
 335                 un_wp_page((unsigned long *) page);
 336         return;
 337 }
 338 
 339 void get_empty_page(unsigned long address)
     /*  */
 340 {
 341         unsigned long tmp;
 342 
 343         if (!(tmp=get_free_page()) || !put_page(tmp,address)) {
 344                 free_page(tmp);         /* 0 is ok - ignored */
 345                 oom();
 346         }
 347 }
 348 
 349 /*
 350  * try_to_share() checks the page at address "address" in the task "p",
 351  * to see if it exists, and if it is clean. If so, share it with the current
 352  * task.
 353  *
 354  * NOTE! This assumes we have checked that p != current, and that they
 355  * share the same executable or library.
 356  */
 357 static int try_to_share(unsigned long address, struct task_struct * p)
     /*  */
 358 {
 359         unsigned long from;
 360         unsigned long to;
 361         unsigned long from_page;
 362         unsigned long to_page;
 363         unsigned long phys_addr;
 364 
 365         from_page = to_page = ((address>>20) & 0xffc);
 366         from_page += ((p->start_code>>20) & 0xffc);
 367         to_page += ((current->start_code>>20) & 0xffc);
 368 /* is there a page-directory at from? */
 369         from = *(unsigned long *) from_page;
 370         if (!(from & 1))
 371                 return 0;
 372         from &= 0xfffff000;
 373         from_page = from + ((address>>10) & 0xffc);
 374         phys_addr = *(unsigned long *) from_page;
 375 /* is the page clean and present? */
 376         if ((phys_addr & 0x41) != 0x01)
 377                 return 0;
 378         phys_addr &= 0xfffff000;
 379         if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)
 380                 return 0;
 381         to = *(unsigned long *) to_page;
 382         if (!(to & 1)) {
 383                 if (to = get_free_page())
 384                         *(unsigned long *) to_page = to | 7;
 385                 else
 386                         oom();
 387         }
 388         to &= 0xfffff000;
 389         to_page = to + ((address>>10) & 0xffc);
 390         if (1 & *(unsigned long *) to_page)
 391                 panic("try_to_share: to_page already exists");
 392 /* share them: write-protect */
 393         *(unsigned long *) from_page &= ~2;
 394         *(unsigned long *) to_page = *(unsigned long *) from_page;
 395         invalidate();
 396         phys_addr -= LOW_MEM;
 397         phys_addr >>= 12;
 398         mem_map[phys_addr]++;
 399         return 1;
 400 }
 401 
 402 /*
 403  * share_page() tries to find a process that could share a page with
 404  * the current one. Address is the address of the wanted page relative
 405  * to the current data space.
 406  *
 407  * We first check if it is at all feasible by checking executable->i_count.
 408  * It should be >1 if there are other tasks sharing this inode.
 409  */
 410 static int share_page(struct inode * inode, unsigned long address)
     /*  */
 411 {
 412         struct task_struct ** p;
 413 
 414         if (inode->i_count < 2 || !inode)
 415                 return 0;
 416         for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
 417                 if (!*p)
 418                         continue;
 419                 if (current == *p)
 420                         continue;
 421                 if (address < LIBRARY_OFFSET) {
 422                         if (inode != (*p)->executable)
 423                                 continue;
 424                 } else {
 425                         if (inode != (*p)->library)
 426                                 continue;
 427                 }
 428                 if (try_to_share(address,*p))
 429                         return 1;
 430         }
 431         return 0;
 432 }
 433 
 434 void do_no_page(unsigned long error_code, unsigned long address,
     /*  */
 435         struct task_struct *tsk)
 436 {
 437         static unsigned int last_checked = 0;
 438         int nr[4];
 439         unsigned long tmp;
 440         unsigned long page;
 441         int block,i;
 442         struct inode * inode;
 443 
 444         /* Thrashing ? Make it interruptible, but don't penalize otherwise */
 445         for (i = 0; i < CHECK_LAST_NR; i++)
 446                 if ((address & 0xfffff000) == last_pages[i]) {
 447                         current->counter = 0;
 448                         schedule();
 449                 }
 450         last_checked++;
 451         if (last_checked >= CHECK_LAST_NR)
 452                 last_checked = 0;
 453         last_pages[last_checked] = address & 0xfffff000;
 454         if (address < TASK_SIZE) {
 455                 printk("\n\rBAD!! KERNEL PAGE MISSING\n\r");
 456                 do_exit(SIGSEGV);
 457         }
 458         if (address - tsk->start_code >= TASK_SIZE) {
 459                 printk("Bad things happen: nonexistent page error in do_no_page\n\r");
 460                 do_exit(SIGSEGV);
 461         }
 462         ++tsk->rss;
 463         page = *(unsigned long *) ((address >> 20) & 0xffc);
 464 /* check the page directory: make a page dir entry if no such exists */
 465         if (page & 1) {
 466                 page &= 0xfffff000;
 467                 page += (address >> 10) & 0xffc;
 468                 tmp = *(unsigned long *) page;
 469                 if (tmp && !(1 & tmp)) {
 470                         ++tsk->maj_flt;
 471                         swap_in((unsigned long *) page);
 472                         return;
 473                 }
 474         } else {
 475                 if (page)
 476                         printk("do_no_page: bad page directory\n");
 477                 if (!(page = get_free_page()))
 478                         oom();
 479                 page |= 7;
 480                 *(unsigned long *) ((address >> 20) & 0xffc) = page;
 481         }
 482         address &= 0xfffff000;
 483         tmp = address - tsk->start_code;
 484         if (tmp >= LIBRARY_OFFSET ) {
 485                 inode = tsk->library;
 486                 block = 1 + (tmp-LIBRARY_OFFSET) / BLOCK_SIZE;
 487         } else if (tmp < tsk->end_data) {
 488                 inode = tsk->executable;
 489                 block = 1 + tmp / BLOCK_SIZE;
 490         } else {
 491                 inode = NULL;
 492                 block = 0;
 493         }
 494         if (!inode) {
 495                 ++tsk->min_flt;
 496                 if (tmp > tsk->brk && tsk == current && 
 497                         LIBRARY_OFFSET - tmp > tsk->rlim[RLIMIT_STACK].rlim_max)
 498                                 do_exit(SIGSEGV);
 499                 get_empty_page(address);
 500                 return;
 501         }
 502         if (tsk == current)
 503                 if (share_page(inode,tmp)) {
 504                         ++tsk->min_flt;
 505                         return;
 506                 }
 507         ++tsk->maj_flt;
 508         if (!(page = get_free_page()))
 509                 oom();
 510 /* remember that 1 block is used for header */
 511         for (i=0 ; i<4 ; block++,i++)
 512                 nr[i] = bmap(inode,block);
 513         bread_page(page,inode->i_dev,nr);
 514         i = tmp + 4096 - tsk->end_data;
 515         if (i>4095)
 516                 i = 0;
 517         tmp = page + 4096;
 518         while (i-- > 0) {
 519                 tmp--;
 520                 *(char *)tmp = 0;
 521         }
 522         if (put_page(page,address))
 523                 return;
 524         free_page(page);
 525         oom();
 526 }
 527 
 528 void mem_init(long start_mem, long end_mem)
     /*  */
 529 {
 530         int i;
 531 
 532         swap_device = 0;
 533         swap_file = NULL;
 534         HIGH_MEMORY = end_mem;
 535         for (i=0 ; i<PAGING_PAGES ; i++)
 536                 mem_map[i] = USED;
 537         i = MAP_NR(start_mem);
 538         end_mem -= start_mem;
 539         end_mem >>= 12;
 540         while (end_mem-->0)
 541                 mem_map[i++]=0;
 542 }
 543 
 544 void show_mem(void)
     /*  */
 545 {
 546         int i,j,k,free=0,total=0;
 547         int shared = 0;
 548         unsigned long * pg_tbl;
 549         static int lock = 0;
 550 
 551         cli();
 552         if (lock) {
 553                 sti();
 554                 return;
 555         }
 556         lock = 1;
 557         sti();
 558         printk("Mem-info:\n\r");
 559         for(i=0 ; i<PAGING_PAGES ; i++) {
 560                 if (mem_map[i] == USED)
 561                         continue;
 562                 total++;
 563                 if (!mem_map[i])
 564                         free++;
 565                 else
 566                         shared += mem_map[i]-1;
 567         }
 568         printk("%d free pages of %d\n\r",free,total);
 569         printk("%d pages shared\n\r",shared);
 570         k = 0;
 571         for(i=4 ; i<1024 ;) {
 572                 if (1&pg_dir[i]) {
 573                         if (pg_dir[i]>HIGH_MEMORY) {
 574                                 printk("page directory[%d]: %08X\n\r",
 575                                         i,pg_dir[i]);
 576                                 i++;
 577                                 continue;
 578                         }
 579                         if (pg_dir[i]>LOW_MEM)
 580                                 free++,k++;
 581                         pg_tbl=(unsigned long *) (0xfffff000 & pg_dir[i]);
 582                         for(j=0 ; j<1024 ; j++)
 583                                 if ((pg_tbl[j]&1) && pg_tbl[j]>LOW_MEM)
 584                                         if (pg_tbl[j]>HIGH_MEMORY)
 585                                                 printk("page_dir[%d][%d]: %08X\n\r",
 586                                                         i,j, pg_tbl[j]);
 587                                         else
 588                                                 k++,free++;
 589                 }
 590                 i++;
 591                 if (!(i&15) && k) {
 592                         k++,free++;     /* one page/process for task_struct */
 593                         printk("Process %d: %d pages\n\r",(i>>4)-1,k);
 594                         k = 0;
 595                 }
 596         }
 597         printk("Memory found: %d (%d)\n\r",free-shared,total);
 598         lock = 0;
 599 }
 600 
 601 
 602 /* This routine handles page faults.  It determines the address,
 603    and the problem then passes it off to one of the appropriate
 604    routines. */
 605 void do_page_fault(unsigned long *esp, unsigned long error_code)
     /*  */
 606 {
 607         unsigned long address;
 608         /* get the address */
 609 
 610         __asm__("movl %%cr2,%0":"=r" (address));
 611         if (!(error_code & 1)) {
 612                 do_no_page(error_code, address, current);
 613                 return;
 614         } else {
 615                 do_wp_page(error_code, address);
 616                 return;
 617         }
 618 }
/* */
root/mm/memory.c

DEFINITIONS
