mm/page_alloc.c

   1 /*
   2  *  linux/mm/page_alloc.c
   3  *
   4  *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
   5  *  Swap reorganised 29.12.95, Stephen Tweedie
   6  */
   7
   8 #include <linux/config.h>
   9 #include <linux/mm.h>
  10 #include <linux/kernel_stat.h>
  11 #include <linux/swap.h>
  12 #include <linux/swapctl.h>
  13 #include <linux/interrupt.h>
  14 #include <linux/init.h>
  15 #include <linux/pagemap.h>
  16
  17 #include <asm/dma.h>
  18 #include <asm/uaccess.h> /* for copy_to/from_user */
  19 #include <asm/pgtable.h>
  20
  21 int nr_swap_pages = 0;
  22 int nr_free_pages = 0;
  23
  24 /*
  25  * Free area management
  26  *
  27  * The free_area_list arrays point to the queue heads of the free areas
  28  * of different sizes
  29  */
  30
  31 #if CONFIG_AP1000
  32 /* the AP+ needs to allocate 8MB contiguous, aligned chunks of ram
  33    for the ring buffers */
  34 #define NR_MEM_LISTS 12
  35 #else
  36 #define NR_MEM_LISTS 6
  37 #endif
  38
  39 /* The start of this MUST match the start of "struct page" */
  40 struct free_area_struct {
  41         struct page *next;
  42         struct page *prev;
  43         unsigned int * map;
  44 };
  45
  46 #define memory_head(x) ((struct page *)(x))
  47
  48 static struct free_area_struct free_area[NR_MEM_LISTS];
  49
  50 static inline void init_mem_queue(struct free_area_struct * head)
  51 {
  52         head->next = memory_head(head);
  53         head->prev = memory_head(head);
  54 }
  55
  56 static inline void add_mem_queue(struct free_area_struct * head, struct page * entry)
  57 {
  58         struct page * next = head->next;
  59
  60         entry->prev = memory_head(head);
  61         entry->next = next;
  62         next->prev = entry;
  63         head->next = entry;
  64 }
  65
  66 static inline void remove_mem_queue(struct page * entry)
  67 {
  68         struct page * next = entry->next;
  69         struct page * prev = entry->prev;
  70         next->prev = prev;
  71         prev->next = next;
  72 }
  73
  74 /*
  75  * Free_page() adds the page to the free lists. This is optimized for
  76  * fast normal cases (no error jumps taken normally).
  77  *
  78  * The way to optimize jumps for gcc-2.2.2 is to:
  79  *  - select the "normal" case and put it inside the if () { XXX }
  80  *  - no else-statements if you can avoid them
  81  *
  82  * With the above two rules, you get a straight-line execution path
  83  * for the normal case, giving better asm-code.
  84  */
  85
  86 /*
  87  * Buddy system. Hairy. You really aren't expected to understand this
  88  *
  89  * Hint: -mask = 1+~mask
  90  */
  91 spinlock_t page_alloc_lock = SPIN_LOCK_UNLOCKED;
  92
  93 static inline void free_pages_ok(unsigned long map_nr, unsigned long order)
  94 {
  95         struct free_area_struct *area = free_area + order;
  96         unsigned long index = map_nr >> (1 + order);
  97         unsigned long mask = (~0UL) << order;
  98         unsigned long flags;
  99
 100         spin_lock_irqsave(&page_alloc_lock, flags);
 101
 102 #define list(x) (mem_map+(x))
 103
 104         map_nr &= mask;
 105         nr_free_pages -= mask;
 106         while (mask + (1 << (NR_MEM_LISTS-1))) {
 107                 if (!test_and_change_bit(index, area->map))
 108                         break;
 109                 remove_mem_queue(list(map_nr ^ -mask));
 110                 mask <<= 1;
 111                 area++;
 112                 index >>= 1;
 113                 map_nr &= mask;
 114         }
 115         add_mem_queue(area, list(map_nr));
 116
 117 #undef list
 118
 119         spin_unlock_irqrestore(&page_alloc_lock, flags);
 120 }
 121
 122 void __free_page(struct page *page)
 123 {
 124         if (!PageReserved(page) && atomic_dec_and_test(&page->count)) {
 125                 if (PageSwapCache(page))
 126                         panic ("Freeing swap cache page");
 127                 page->flags &= ~(1 << PG_referenced);
 128                 free_pages_ok(page - mem_map, 0);
 129                 return;
 130         }
 131 }
 132
 133 void free_pages(unsigned long addr, unsigned long order)
 134 {
 135         unsigned long map_nr = MAP_NR(addr);
 136
 137         if (map_nr < max_mapnr) {
 138                 mem_map_t * map = mem_map + map_nr;
 139                 if (PageReserved(map))
 140                         return;
 141                 if (atomic_dec_and_test(&map->count)) {
 142                         if (PageSwapCache(map))
 143                                 panic ("Freeing swap cache pages");
 144                         map->flags &= ~(1 << PG_referenced);
 145                         free_pages_ok(map_nr, order);
 146                         return;
 147                 }
 148         }
 149 }
 150
 151 /*
 152  * Some ugly macros to speed up __get_free_pages()..
 153  */
 154 #define MARK_USED(index, order, area) \
 155         change_bit((index) >> (1+(order)), (area)->map)
 156 #define CAN_DMA(x) (PageDMA(x))
 157 #define ADDRESS(x) (PAGE_OFFSET + ((x) << PAGE_SHIFT))
 158 #define RMQUEUE(order, gfp_mask) \
 159 do { struct free_area_struct * area = free_area+order; \
 160      unsigned long new_order = order; \
 161         do { struct page *prev = memory_head(area), *ret = prev->next; \
 162                 while (memory_head(area) != ret) { \
 163                         if (!(gfp_mask & __GFP_DMA) || CAN_DMA(ret)) { \
 164                                 unsigned long map_nr; \
 165                                 (prev->next = ret->next)->prev = prev; \
 166                                 map_nr = ret - mem_map; \
 167                                 MARK_USED(map_nr, new_order, area); \
 168                                 nr_free_pages -= 1 << order; \
 169                                 EXPAND(ret, map_nr, order, new_order, area); \
 170                                 spin_unlock_irqrestore(&page_alloc_lock, flags); \
 171                                 return ADDRESS(map_nr); \
 172                         } \
 173                         prev = ret; \
 174                         ret = ret->next; \
 175                 } \
 176                 new_order++; area++; \
 177         } while (new_order < NR_MEM_LISTS); \
 178 } while (0)
 179
 180 #define EXPAND(map,index,low,high,area) \
 181 do { unsigned long size = 1 << high; \
 182         while (high > low) { \
 183                 area--; high--; size >>= 1; \
 184                 add_mem_queue(area, map); \
 185                 MARK_USED(index, high, area); \
 186                 index += size; \
 187                 map += size; \
 188         } \
 189         atomic_set(&map->count, 1); \
 190 } while (0)
 191
 192 int low_on_memory = 0;
 193
 194 unsigned long __get_free_pages(int gfp_mask, unsigned long order)
 195 {
 196         unsigned long flags;
 197
 198         if (order >= NR_MEM_LISTS)
 199                 goto nopage;
 200
 201 #ifdef ATOMIC_MEMORY_DEBUGGING
 202         if ((gfp_mask & __GFP_WAIT) && in_interrupt()) {
 203                 static int count = 0;
 204                 if (++count < 5) {
 205                         printk("gfp called nonatomically from interrupt %p\n",
 206                                 __builtin_return_address(0));
 207                 }
 208                 goto nopage;
 209         }
 210 #endif
 211
 212         /*
 213          * If this is a recursive call, we'd better
 214          * do our best to just allocate things without
 215          * further thought.
 216          */
 217         if (!(current->flags & PF_MEMALLOC)) {
 218                 int freed;
 219
 220                 if (nr_free_pages > freepages.min) {
 221                         if (!low_on_memory)
 222                                 goto ok_to_allocate;
 223                         if (nr_free_pages >= freepages.high) {
 224                                 low_on_memory = 0;
 225                                 goto ok_to_allocate;
 226                         }
 227                 }
 228
 229                 low_on_memory = 1;
 230                 current->flags |= PF_MEMALLOC;
 231                 freed = try_to_free_pages(gfp_mask);
 232                 current->flags &= ~PF_MEMALLOC;
 233
 234                 if (!freed && !(gfp_mask & (__GFP_MED | __GFP_HIGH)))
 235                         goto nopage;
 236         }
 237 ok_to_allocate:
 238         spin_lock_irqsave(&page_alloc_lock, flags);
 239         RMQUEUE(order, gfp_mask);
 240         spin_unlock_irqrestore(&page_alloc_lock, flags);
 241
 242         /*
 243          * If we can schedule, do so, and make sure to yield.
 244          * We may be a real-time process, and if kswapd is
 245          * waiting for us we need to allow it to run a bit.
 246          */
 247         if (gfp_mask & __GFP_WAIT) {
 248                 current->policy |= SCHED_YIELD;
 249                 schedule();
 250         }
 251
 252 nopage:
 253         return 0;
 254 }
 255
 256 /*
 257  * Show free area list (used inside shift_scroll-lock stuff)
 258  * We also calculate the percentage fragmentation. We do this by counting the
 259  * memory on each free list with the exception of the first item on the list.
 260  */
 261 void show_free_areas(void)
 262 {
 263         unsigned long order, flags;
 264         unsigned long total = 0;
 265
 266         printk("Free pages:      %6dkB\n ( ",nr_free_pages<<(PAGE_SHIFT-10));
 267         printk("Free: %d (%d %d %d)\n",
 268                 nr_free_pages,
 269                 freepages.min,
 270                 freepages.low,
 271                 freepages.high);
 272         spin_lock_irqsave(&page_alloc_lock, flags);
 273         for (order=0 ; order < NR_MEM_LISTS; order++) {
 274                 struct page * tmp;
 275                 unsigned long nr = 0;
 276                 for (tmp = free_area[order].next ; tmp != memory_head(free_area+order) ; tmp = tmp->next) {
 277                         nr ++;
 278                 }
 279                 total += nr * ((PAGE_SIZE>>10) << order);
 280                 printk("%lu*%lukB ", nr, (unsigned long)((PAGE_SIZE>>10) << order));
 281         }
 282         spin_unlock_irqrestore(&page_alloc_lock, flags);
 283         printk("= %lukB)\n", total);
 284 #ifdef SWAP_CACHE_INFO
 285         show_swap_cache_info();
 286 #endif
 287 }
 288
 289 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
 290
 291 /*
 292  * set up the free-area data structures:
 293  *   - mark all pages reserved
 294  *   - mark all memory queues empty
 295  *   - clear the memory bitmaps
 296  */
 297 unsigned long __init free_area_init(unsigned long start_mem, unsigned long end_mem)
 298 {
 299         mem_map_t * p;
 300         unsigned long mask = PAGE_MASK;
 301         unsigned long i;
 302
 303         /*
 304          * Select nr of pages we try to keep free for important stuff
 305          * with a minimum of 10 pages and a maximum of 256 pages, so
 306          * that we don't waste too much memory on large systems.
 307          * This is fairly arbitrary, but based on some behaviour
 308          * analysis.
 309          */
 310         i = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT+7);
 311         if (i < 10)
 312                 i = 10;
 313         if (i > 256)
 314                 i = 256;
 315         freepages.min = i;
 316         freepages.low = i * 2;
 317         freepages.high = i * 3;
 318         mem_map = (mem_map_t *) LONG_ALIGN(start_mem);
 319         p = mem_map + MAP_NR(end_mem);
 320         start_mem = LONG_ALIGN((unsigned long) p);
 321         memset(mem_map, 0, start_mem - (unsigned long) mem_map);
 322         do {
 323                 --p;
 324                 atomic_set(&p->count, 0);
 325                 p->flags = (1 << PG_DMA) | (1 << PG_reserved);
 326         } while (p > mem_map);
 327
 328         for (i = 0 ; i < NR_MEM_LISTS ; i++) {
 329                 unsigned long bitmap_size;
 330                 init_mem_queue(free_area+i);
 331                 mask += mask;
 332                 end_mem = (end_mem + ~mask) & mask;
 333                 bitmap_size = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT + i);
 334                 bitmap_size = (bitmap_size + 7) >> 3;
 335                 bitmap_size = LONG_ALIGN(bitmap_size);
 336                 free_area[i].map = (unsigned int *) start_mem;
 337                 memset((void *) start_mem, 0, bitmap_size);
 338                 start_mem += bitmap_size;
 339         }
 340         return start_mem;
 341 }
 342
 343 /*
 344  * Primitive swap readahead code. We simply read an aligned block of
 345  * (1 << page_cluster) entries in the swap area. This method is chosen
 346  * because it doesn't cost us any seek time.  We also make sure to queue
 347  * the 'original' request together with the readahead ones...
 348  */
 349 void swapin_readahead(unsigned long entry)
 350 {
 351         int i;
 352         struct page *new_page;
 353         unsigned long offset = SWP_OFFSET(entry);
 354         struct swap_info_struct *swapdev = SWP_TYPE(entry) + swap_info;
 355
 356         offset = (offset >> page_cluster) << page_cluster;
 357
 358         i = 1 << page_cluster;
 359         do {
 360                 /* Don't read-ahead past the end of the swap area */
 361                 if (offset >= swapdev->max)
 362                         break;
 363                 /* Don't block on I/O for read-ahead */
 364                 if (atomic_read(&nr_async_pages) >= pager_daemon.swap_cluster)
 365                         break;
 366                 /* Don't read in bad or busy pages */
 367                 if (!swapdev->swap_map[offset])
 368                         break;
 369                 if (swapdev->swap_map[offset] == SWAP_MAP_BAD)
 370                         break;
 371                 if (test_bit(offset, swapdev->swap_lockmap))
 372                         break;
 373
 374                 /* Ok, do the async read-ahead now */
 375                 new_page = read_swap_cache_async(SWP_ENTRY(SWP_TYPE(entry), offset), 0);
 376                 if (new_page != NULL)
 377                         __free_page(new_page);
 378                 offset++;
 379         } while (--i);
 380         return;
 381 }
 382
 383 /*
 384  * The tests may look silly, but it essentially makes sure that
 385  * no other process did a swap-in on us just as we were waiting.
 386  *
 387  * Also, don't bother to add to the swap cache if this page-in
 388  * was due to a write access.
 389  */
 390 void swap_in(struct task_struct * tsk, struct vm_area_struct * vma,
 391         pte_t * page_table, unsigned long entry, int write_access)
 392 {
 393         unsigned long page;
 394         struct page *page_map = lookup_swap_cache(entry);
 395
 396         if (!page_map) {
 397                 swapin_readahead(entry);
 398                 page_map = read_swap_cache(entry);
 399         }
 400         if (pte_val(*page_table) != entry) {
 401                 if (page_map)
 402                         free_page_and_swap_cache(page_address(page_map));
 403                 return;
 404         }
 405         if (!page_map) {
 406                 set_pte(page_table, BAD_PAGE);
 407                 swap_free(entry);
 408                 oom(tsk);
 409                 return;
 410         }
 411
 412         page = page_address(page_map);
 413         vma->vm_mm->rss++;
 414         tsk->min_flt++;
 415         swap_free(entry);
 416
 417         if (!write_access || is_page_shared(page_map)) {
 418                 set_pte(page_table, mk_pte(page, vma->vm_page_prot));
 419                 return;
 420         }
 421
 422         /* The page is unshared, and we want write access.  In this
 423            case, it is safe to tear down the swap cache and give the
 424            page over entirely to this process. */
 425
 426         if (PageSwapCache(page_map))
 427                 delete_from_swap_cache(page_map);
 428         set_pte(page_table, pte_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot))));
 429         return;
 430 }