root/mm/memory.c

/* */

DEFINITIONS

1. oom
2. get_free_page
3. free_page
4. free_page_tables
5. copy_page_tables
6. put_page
7. un_wp_page
8. do_wp_page
9. write_verify
10. get_empty_page
11. try_to_share
12. share_page
13. do_no_page
14. mem_init
15. calc_mem

   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 #include <signal.h>
  24 
  25 #include <asm/system.h>
  26 
  27 #include <linux/sched.h>
  28 #include <linux/head.h>
  29 #include <linux/kernel.h>
  30 
  31 volatile void do_exit(long code);
  32 
  33 static inline volatile void oom(void)
     /*  */
  34 {
  35         printk("out of memory\n\r");
  36         do_exit(SIGSEGV);
  37 }
  38 
  39 #define invalidate() \
  40 __asm__("movl %%eax,%%cr3"::"a" (0))
  41 
  42 /* these are not to be changed without changing head.s etc */
  43 #define LOW_MEM 0x100000
  44 #define PAGING_MEMORY (15*1024*1024)
  45 #define PAGING_PAGES (PAGING_MEMORY>>12)
  46 #define MAP_NR(addr) (((addr)-LOW_MEM)>>12)
  47 #define USED 100
  48 
  49 #define CODE_SPACE(addr) ((((addr)+4095)&~4095) < \
  50 current->start_code + current->end_code)
  51 
  52 static long HIGH_MEMORY = 0;
  53 
  54 #define copy_page(from,to) \
  55 __asm__("cld ; rep ; movsl"::"S" (from),"D" (to),"c" (1024):"cx","di","si")
  56 
  57 static unsigned char mem_map [ PAGING_PAGES ] = {0,};
  58 
  59 /*
  60  * Get physical address of first (actually last :-) free page, and mark it
  61  * used. If no free pages left, return 0.
  62  */
  63 unsigned long get_free_page(void)
     /*  */
  64 {
  65 register unsigned long __res asm("ax");
  66 
  67 __asm__("std ; repne ; scasb\n\t"
  68         "jne 1f\n\t"
  69         "movb $1,1(%%edi)\n\t"
  70         "sall $12,%%ecx\n\t"
  71         "addl %2,%%ecx\n\t"
  72         "movl %%ecx,%%edx\n\t"
  73         "movl $1024,%%ecx\n\t"
  74         "leal 4092(%%edx),%%edi\n\t"
  75         "rep ; stosl\n\t"
  76         "movl %%edx,%%eax\n"
  77         "1:"
  78         :"=a" (__res)
  79         :"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES),
  80         "D" (mem_map+PAGING_PAGES-1)
  81         :"di","cx","dx");
  82 return __res;
  83 }
  84 
  85 /*
  86  * Free a page of memory at physical address 'addr'. Used by
  87  * 'free_page_tables()'
  88  */
  89 void free_page(unsigned long addr)
     /*  */
  90 {
  91         if (addr < LOW_MEM) return;
  92         if (addr >= HIGH_MEMORY)
  93                 panic("trying to free nonexistent page");
  94         addr -= LOW_MEM;
  95         addr >>= 12;
  96         if (mem_map[addr]--) return;
  97         mem_map[addr]=0;
  98         panic("trying to free free page");
  99 }
 100 
 101 /*
 102  * This function frees a continuos block of page tables, as needed
 103  * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
 104  */
 105 int free_page_tables(unsigned long from,unsigned long size)
     /*  */
 106 {
 107         unsigned long *pg_table;
 108         unsigned long * dir, nr;
 109 
 110         if (from & 0x3fffff)
 111                 panic("free_page_tables called with wrong alignment");
 112         if (!from)
 113                 panic("Trying to free up swapper memory space");
 114         size = (size + 0x3fffff) >> 22;
 115         dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
 116         for ( ; size-->0 ; dir++) {
 117                 if (!(1 & *dir))
 118                         continue;
 119                 pg_table = (unsigned long *) (0xfffff000 & *dir);
 120                 for (nr=0 ; nr<1024 ; nr++) {
 121                         if (1 & *pg_table)
 122                                 free_page(0xfffff000 & *pg_table);
 123                         *pg_table = 0;
 124                         pg_table++;
 125                 }
 126                 free_page(0xfffff000 & *dir);
 127                 *dir = 0;
 128         }
 129         invalidate();
 130         return 0;
 131 }
 132 
 133 /*
 134  *  Well, here is one of the most complicated functions in mm. It
 135  * copies a range of linerar addresses by copying only the pages.
 136  * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
 137  *
 138  * Note! We don't copy just any chunks of memory - addresses have to
 139  * be divisible by 4Mb (one page-directory entry), as this makes the
 140  * function easier. It's used only by fork anyway.
 141  *
 142  * NOTE 2!! When from==0 we are copying kernel space for the first
 143  * fork(). Then we DONT want to copy a full page-directory entry, as
 144  * that would lead to some serious memory waste - we just copy the
 145  * first 160 pages - 640kB. Even that is more than we need, but it
 146  * doesn't take any more memory - we don't copy-on-write in the low
 147  * 1 Mb-range, so the pages can be shared with the kernel. Thus the
 148  * special case for nr=xxxx.
 149  */
 150 int copy_page_tables(unsigned long from,unsigned long to,long size)
     /*  */
 151 {
 152         unsigned long * from_page_table;
 153         unsigned long * to_page_table;
 154         unsigned long this_page;
 155         unsigned long * from_dir, * to_dir;
 156         unsigned long nr;
 157 
 158         if ((from&0x3fffff) || (to&0x3fffff))
 159                 panic("copy_page_tables called with wrong alignment");
 160         from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
 161         to_dir = (unsigned long *) ((to>>20) & 0xffc);
 162         size = ((unsigned) (size+0x3fffff)) >> 22;
 163         for( ; size-->0 ; from_dir++,to_dir++) {
 164                 if (1 & *to_dir)
 165                         panic("copy_page_tables: already exist");
 166                 if (!(1 & *from_dir))
 167                         continue;
 168                 from_page_table = (unsigned long *) (0xfffff000 & *from_dir);
 169                 if (!(to_page_table = (unsigned long *) get_free_page()))
 170                         return -1;      /* Out of memory, see freeing */
 171                 *to_dir = ((unsigned long) to_page_table) | 7;
 172                 nr = (from==0)?0xA0:1024;
 173                 for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
 174                         this_page = *from_page_table;
 175                         if (!(1 & this_page))
 176                                 continue;
 177                         this_page &= ~2;
 178                         *to_page_table = this_page;
 179                         if (this_page > LOW_MEM) {
 180                                 *from_page_table = this_page;
 181                                 this_page -= LOW_MEM;
 182                                 this_page >>= 12;
 183                                 mem_map[this_page]++;
 184                         }
 185                 }
 186         }
 187         invalidate();
 188         return 0;
 189 }
 190 
 191 /*
 192  * This function puts a page in memory at the wanted address.
 193  * It returns the physical address of the page gotten, 0 if
 194  * out of memory (either when trying to access page-table or
 195  * page.)
 196  */
 197 unsigned long put_page(unsigned long page,unsigned long address)
     /*  */
 198 {
 199         unsigned long tmp, *page_table;
 200 
 201 /* NOTE !!! This uses the fact that _pg_dir=0 */
 202 
 203         if (page < LOW_MEM || page >= HIGH_MEMORY)
 204                 printk("Trying to put page %p at %p\n",page,address);
 205         if (mem_map[(page-LOW_MEM)>>12] != 1)
 206                 printk("mem_map disagrees with %p at %p\n",page,address);
 207         page_table = (unsigned long *) ((address>>20) & 0xffc);
 208         if ((*page_table)&1)
 209                 page_table = (unsigned long *) (0xfffff000 & *page_table);
 210         else {
 211                 if (!(tmp=get_free_page()))
 212                         return 0;
 213                 *page_table = tmp|7;
 214                 page_table = (unsigned long *) tmp;
 215         }
 216         page_table[(address>>12) & 0x3ff] = page | 7;
 217 /* no need for invalidate */
 218         return page;
 219 }
 220 
 221 void un_wp_page(unsigned long * table_entry)
     /*  */
 222 {
 223         unsigned long old_page,new_page;
 224 
 225         old_page = 0xfffff000 & *table_entry;
 226         if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
 227                 *table_entry |= 2;
 228                 invalidate();
 229                 return;
 230         }
 231         if (!(new_page=get_free_page()))
 232                 oom();
 233         if (old_page >= LOW_MEM)
 234                 mem_map[MAP_NR(old_page)]--;
 235         *table_entry = new_page | 7;
 236         invalidate();
 237         copy_page(old_page,new_page);
 238 }       
 239 
 240 /*
 241  * This routine handles present pages, when users try to write
 242  * to a shared page. It is done by copying the page to a new address
 243  * and decrementing the shared-page counter for the old page.
 244  *
 245  * If it's in code space we exit with a segment error.
 246  */
 247 void do_wp_page(unsigned long error_code,unsigned long address)
     /*  */
 248 {
 249 #if 0
 250 /* we cannot do this yet: the estdio library writes to code space */
 251 /* stupid, stupid. I really want the libc.a from GNU */
 252         if (CODE_SPACE(address))
 253                 do_exit(SIGSEGV);
 254 #endif
 255         un_wp_page((unsigned long *)
 256                 (((address>>10) & 0xffc) + (0xfffff000 &
 257                 *((unsigned long *) ((address>>20) &0xffc)))));
 258 
 259 }
 260 
 261 void write_verify(unsigned long address)
     /*  */
 262 {
 263         unsigned long page;
 264 
 265         if (!( (page = *((unsigned long *) ((address>>20) & 0xffc)) )&1))
 266                 return;
 267         page &= 0xfffff000;
 268         page += ((address>>10) & 0xffc);
 269         if ((3 & *(unsigned long *) page) == 1)  /* non-writeable, present */
 270                 un_wp_page((unsigned long *) page);
 271         return;
 272 }
 273 
 274 void get_empty_page(unsigned long address)
     /*  */
 275 {
 276         unsigned long tmp;
 277 
 278         if (!(tmp=get_free_page()) || !put_page(tmp,address)) {
 279                 free_page(tmp);         /* 0 is ok - ignored */
 280                 oom();
 281         }
 282 }
 283 
 284 /*
 285  * try_to_share() checks the page at address "address" in the task "p",
 286  * to see if it exists, and if it is clean. If so, share it with the current
 287  * task.
 288  *
 289  * NOTE! This assumes we have checked that p != current, and that they
 290  * share the same executable.
 291  */
 292 static int try_to_share(unsigned long address, struct task_struct * p)
     /*  */
 293 {
 294         unsigned long from;
 295         unsigned long to;
 296         unsigned long from_page;
 297         unsigned long to_page;
 298         unsigned long phys_addr;
 299 
 300         from_page = to_page = ((address>>20) & 0xffc);
 301         from_page += ((p->start_code>>20) & 0xffc);
 302         to_page += ((current->start_code>>20) & 0xffc);
 303 /* is there a page-directory at from? */
 304         from = *(unsigned long *) from_page;
 305         if (!(from & 1))
 306                 return 0;
 307         from &= 0xfffff000;
 308         from_page = from + ((address>>10) & 0xffc);
 309         phys_addr = *(unsigned long *) from_page;
 310 /* is the page clean and present? */
 311         if ((phys_addr & 0x41) != 0x01)
 312                 return 0;
 313         phys_addr &= 0xfffff000;
 314         if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)
 315                 return 0;
 316         to = *(unsigned long *) to_page;
 317         if (!(to & 1))
 318                 if (to = get_free_page())
 319                         *(unsigned long *) to_page = to | 7;
 320                 else
 321                         oom();
 322         to &= 0xfffff000;
 323         to_page = to + ((address>>10) & 0xffc);
 324         if (1 & *(unsigned long *) to_page)
 325                 panic("try_to_share: to_page already exists");
 326 /* share them: write-protect */
 327         *(unsigned long *) from_page &= ~2;
 328         *(unsigned long *) to_page = *(unsigned long *) from_page;
 329         invalidate();
 330         phys_addr -= LOW_MEM;
 331         phys_addr >>= 12;
 332         mem_map[phys_addr]++;
 333         return 1;
 334 }
 335 
 336 /*
 337  * share_page() tries to find a process that could share a page with
 338  * the current one. Address is the address of the wanted page relative
 339  * to the current data space.
 340  *
 341  * We first check if it is at all feasible by checking executable->i_count.
 342  * It should be >1 if there are other tasks sharing this inode.
 343  */
 344 static int share_page(unsigned long address)
     /*  */
 345 {
 346         struct task_struct ** p;
 347 
 348         if (!current->executable)
 349                 return 0;
 350         if (current->executable->i_count < 2)
 351                 return 0;
 352         for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
 353                 if (!*p)
 354                         continue;
 355                 if (current == *p)
 356                         continue;
 357                 if ((*p)->executable != current->executable)
 358                         continue;
 359                 if (try_to_share(address,*p))
 360                         return 1;
 361         }
 362         return 0;
 363 }
 364 
 365 void do_no_page(unsigned long error_code,unsigned long address)
     /*  */
 366 {
 367         int nr[4];
 368         unsigned long tmp;
 369         unsigned long page;
 370         int block,i;
 371 
 372         address &= 0xfffff000;
 373         tmp = address - current->start_code;
 374         if (!current->executable || tmp >= current->end_data) {
 375                 get_empty_page(address);
 376                 return;
 377         }
 378         if (share_page(tmp))
 379                 return;
 380         if (!(page = get_free_page()))
 381                 oom();
 382 /* remember that 1 block is used for header */
 383         block = 1 + tmp/BLOCK_SIZE;
 384         for (i=0 ; i<4 ; block++,i++)
 385                 nr[i] = bmap(current->executable,block);
 386         bread_page(page,current->executable->i_dev,nr);
 387         i = tmp + 4096 - current->end_data;
 388         tmp = page + 4096;
 389         while (i-- > 0) {
 390                 tmp--;
 391                 *(char *)tmp = 0;
 392         }
 393         if (put_page(page,address))
 394                 return;
 395         free_page(page);
 396         oom();
 397 }
 398 
 399 void mem_init(long start_mem, long end_mem)
     /*  */
 400 {
 401         int i;
 402 
 403         HIGH_MEMORY = end_mem;
 404         for (i=0 ; i<PAGING_PAGES ; i++)
 405                 mem_map[i] = USED;
 406         i = MAP_NR(start_mem);
 407         end_mem -= start_mem;
 408         end_mem >>= 12;
 409         while (end_mem-->0)
 410                 mem_map[i++]=0;
 411 }
 412 
 413 void calc_mem(void)
     /*  */
 414 {
 415         int i,j,k,free=0;
 416         long * pg_tbl;
 417 
 418         for(i=0 ; i<PAGING_PAGES ; i++)
 419                 if (!mem_map[i]) free++;
 420         printk("%d pages free (of %d)\n\r",free,PAGING_PAGES);
 421         for(i=2 ; i<1024 ; i++) {
 422                 if (1&pg_dir[i]) {
 423                         pg_tbl=(long *) (0xfffff000 & pg_dir[i]);
 424                         for(j=k=0 ; j<1024 ; j++)
 425                                 if (pg_tbl[j]&1)
 426                                         k++;
 427                         printk("Pg-dir[%d] uses %d pages\n",i,k);
 428                 }
 429         }
 430 }

/* */