LXR linux-old/mm/page

   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/sched.h>
  11#include <linux/head.h>
  12#include <linux/kernel.h>
  13#include <linux/kernel_stat.h>
  14#include <linux/errno.h>
  15#include <linux/string.h>
  16#include <linux/stat.h>
  17#include <linux/swap.h>
  18#include <linux/fs.h>
  19#include <linux/swapctl.h>
  20#include <linux/interrupt.h>
  21#include <linux/init.h>
  22
  23#include <asm/dma.h>
  24#include <asm/system.h> /* for cli()/sti() */
  25#include <asm/uaccess.h> /* for copy_to/from_user */
  26#include <asm/bitops.h>
  27#include <asm/pgtable.h>
  28#include <asm/spinlock.h>
  29
  30int nr_swap_pages = 0;
  31int nr_free_pages = 0;
  32
  33/*
  34 * Free area management
  35 *
  36 * The free_area_list arrays point to the queue heads of the free areas
  37 * of different sizes
  38 */
  39
  40#if CONFIG_AP1000
  41/* the AP+ needs to allocate 8MB contiguous, aligned chunks of ram
  42   for the ring buffers */
  43#define NR_MEM_LISTS 12
  44#else
  45#define NR_MEM_LISTS 6
  46#endif
  47
  48/* The start of this MUST match the start of "struct page" */
  49struct free_area_struct {
  50        struct page *next;
  51        struct page *prev;
  52        unsigned int * map;
  53};
  54
  55#define memory_head(x) ((struct page *)(x))
  56
  57static struct free_area_struct free_area[NR_MEM_LISTS];
  58
  59static inline void init_mem_queue(struct free_area_struct * head)
  60{
  61        head->next = memory_head(head);
  62        head->prev = memory_head(head);
  63}
  64
  65static inline void add_mem_queue(struct free_area_struct * head, struct page * entry)
  66{
  67        struct page * next = head->next;
  68
  69        entry->prev = memory_head(head);
  70        entry->next = next;
  71        next->prev = entry;
  72        head->next = entry;
  73}
  74
  75static inline void remove_mem_queue(struct page * entry)
  76{
  77        struct page * next = entry->next;
  78        struct page * prev = entry->prev;
  79        next->prev = prev;
  80        prev->next = next;
  81}
  82
  83/*
  84 * Free_page() adds the page to the free lists. This is optimized for
  85 * fast normal cases (no error jumps taken normally).
  86 *
  87 * The way to optimize jumps for gcc-2.2.2 is to:
  88 *  - select the "normal" case and put it inside the if () { XXX }
  89 *  - no else-statements if you can avoid them
  90 *
  91 * With the above two rules, you get a straight-line execution path
  92 * for the normal case, giving better asm-code.
  93 */
  94
  95/*
  96 * Buddy system. Hairy. You really aren't expected to understand this
  97 *
  98 * Hint: -mask = 1+~mask
  99 */
 100#ifdef __SMP__
 101static spinlock_t page_alloc_lock;
 102#endif
 103
 104static inline void free_pages_ok(unsigned long map_nr, unsigned long order)
 105{
 106        struct free_area_struct *area = free_area + order;
 107        unsigned long index = map_nr >> (1 + order);
 108        unsigned long mask = (~0UL) << order;
 109        unsigned long flags;
 110
 111        spin_lock_irqsave(&page_alloc_lock, flags);
 112
 113#define list(x) (mem_map+(x))
 114
 115        map_nr &= mask;
 116        nr_free_pages -= mask;
 117        while (mask + (1 << (NR_MEM_LISTS-1))) {
 118                if (!test_and_change_bit(index, area->map))
 119                        break;
 120                remove_mem_queue(list(map_nr ^ -mask));
 121                mask <<= 1;
 122                area++;
 123                index >>= 1;
 124                map_nr &= mask;
 125        }
 126        add_mem_queue(area, list(map_nr));
 127
 128#undef list
 129
 130        spin_unlock_irqrestore(&page_alloc_lock, flags);
 131}
 132
 133void __free_page(struct page *page)
 134{
 135        if (!PageReserved(page) && atomic_dec_and_test(&page->count)) {
 136                delete_from_swap_cache(page);
 137                free_pages_ok(page->map_nr, 0);
 138        }
 139}
 140
 141void free_pages(unsigned long addr, unsigned long order)
 142{
 143        unsigned long map_nr = MAP_NR(addr);
 144
 145        if (map_nr < max_mapnr) {
 146                mem_map_t * map = mem_map + map_nr;
 147                if (PageReserved(map))
 148                        return;
 149                if (atomic_dec_and_test(&map->count)) {
 150                        delete_from_swap_cache(map);
 151                        free_pages_ok(map_nr, order);
 152                        return;
 153                }
 154        }
 155}
 156
 157/*
 158 * Some ugly macros to speed up __get_free_pages()..
 159 */
 160#define MARK_USED(index, order, area) \
 161        change_bit((index) >> (1+(order)), (area)->map)
 162#define CAN_DMA(x) (PageDMA(x))
 163#define ADDRESS(x) (PAGE_OFFSET + ((x) << PAGE_SHIFT))
 164#define RMQUEUE(order, dma) \
 165do { struct free_area_struct * area = free_area+order; \
 166     unsigned long new_order = order; \
 167        do { struct page *prev = memory_head(area), *ret; \
 168                while (memory_head(area) != (ret = prev->next)) { \
 169                        if (!dma || CAN_DMA(ret)) { \
 170                                unsigned long map_nr = ret->map_nr; \
 171                                (prev->next = ret->next)->prev = prev; \
 172                                MARK_USED(map_nr, new_order, area); \
 173                                nr_free_pages -= 1 << order; \
 174                                EXPAND(ret, map_nr, order, new_order, area); \
 175                                spin_unlock_irqrestore(&page_alloc_lock, flags); \
 176                                return ADDRESS(map_nr); \
 177                        } \
 178                        prev = ret; \
 179                } \
 180                new_order++; area++; \
 181        } while (new_order < NR_MEM_LISTS); \
 182} while (0)
 183
 184#define EXPAND(map,index,low,high,area) \
 185do { unsigned long size = 1 << high; \
 186        while (high > low) { \
 187                area--; high--; size >>= 1; \
 188                add_mem_queue(area, map); \
 189                MARK_USED(index, high, area); \
 190                index += size; \
 191                map += size; \
 192        } \
 193        atomic_set(&map->count, 1); \
 194        map->age = PAGE_INITIAL_AGE; \
 195} while (0)
 196
 197unsigned long __get_free_pages(int priority, unsigned long order, int dma)
 198{
 199        unsigned long flags;
 200        int reserved_pages;
 201
 202        if (order >= NR_MEM_LISTS)
 203                return 0;
 204
 205        if (in_interrupt() && priority != GFP_ATOMIC) {
 206                static int count = 0;
 207                if (++count < 5) {
 208                        printk("gfp called nonatomically from interrupt %p\n",
 209                                __builtin_return_address(0));
 210                        priority = GFP_ATOMIC;
 211                }
 212        }
 213
 214        reserved_pages = 5;
 215        if (priority != GFP_NFS)
 216                reserved_pages = min_free_pages;
 217repeat:
 218        spin_lock_irqsave(&page_alloc_lock, flags);
 219        if ((priority==GFP_ATOMIC) || nr_free_pages > reserved_pages) {
 220                RMQUEUE(order, dma);
 221                spin_unlock_irqrestore(&page_alloc_lock, flags);
 222                return 0;
 223        }
 224        spin_unlock_irqrestore(&page_alloc_lock, flags);
 225        if (priority != GFP_BUFFER && try_to_free_page(priority, dma, 1))
 226                goto repeat;
 227        return 0;
 228}
 229
 230/*
 231 * Show free area list (used inside shift_scroll-lock stuff)
 232 * We also calculate the percentage fragmentation. We do this by counting the
 233 * memory on each free list with the exception of the first item on the list.
 234 */
 235void show_free_areas(void)
 236{
 237        unsigned long order, flags;
 238        unsigned long total = 0;
 239
 240        printk("Free pages:      %6dkB\n ( ",nr_free_pages<<(PAGE_SHIFT-10));
 241        spin_lock_irqsave(&page_alloc_lock, flags);
 242        for (order=0 ; order < NR_MEM_LISTS; order++) {
 243                struct page * tmp;
 244                unsigned long nr = 0;
 245                for (tmp = free_area[order].next ; tmp != memory_head(free_area+order) ; tmp = tmp->next) {
 246                        nr ++;
 247                }
 248                total += nr * ((PAGE_SIZE>>10) << order);
 249                printk("%lu*%lukB ", nr, (unsigned long)((PAGE_SIZE>>10) << order));
 250        }
 251        spin_unlock_irqrestore(&page_alloc_lock, flags);
 252        printk("= %lukB)\n", total);
 253#ifdef SWAP_CACHE_INFO
 254        show_swap_cache_info();
 255#endif  
 256}
 257
 258#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
 259
 260/*
 261 * set up the free-area data structures:
 262 *   - mark all pages reserved
 263 *   - mark all memory queues empty
 264 *   - clear the memory bitmaps
 265 */
 266__initfunc(unsigned long free_area_init(unsigned long start_mem, unsigned long end_mem))
 267{
 268        mem_map_t * p;
 269        unsigned long mask = PAGE_MASK;
 270        int i;
 271
 272        /*
 273         * select nr of pages we try to keep free for important stuff
 274         * with a minimum of 48 pages. This is totally arbitrary
 275         */
 276        i = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT+7);
 277        if (i < 48)
 278                i = 48;
 279        min_free_pages = i;
 280        free_pages_low = i + (i>>1);
 281        free_pages_high = i + i;
 282        mem_map = (mem_map_t *) LONG_ALIGN(start_mem);
 283        p = mem_map + MAP_NR(end_mem);
 284        start_mem = LONG_ALIGN((unsigned long) p);
 285        memset(mem_map, 0, start_mem - (unsigned long) mem_map);
 286        do {
 287                --p;
 288                atomic_set(&p->count, 0);
 289                p->flags = (1 << PG_DMA) | (1 << PG_reserved);
 290                p->map_nr = p - mem_map;
 291        } while (p > mem_map);
 292
 293        for (i = 0 ; i < NR_MEM_LISTS ; i++) {
 294                unsigned long bitmap_size;
 295                init_mem_queue(free_area+i);
 296                mask += mask;
 297                end_mem = (end_mem + ~mask) & mask;
 298                bitmap_size = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT + i);
 299                bitmap_size = (bitmap_size + 7) >> 3;
 300                bitmap_size = LONG_ALIGN(bitmap_size);
 301                free_area[i].map = (unsigned int *) start_mem;
 302                memset((void *) start_mem, 0, bitmap_size);
 303                start_mem += bitmap_size;
 304        }
 305        return start_mem;
 306}
 307
 308/*
 309 * The tests may look silly, but it essentially makes sure that
 310 * no other process did a swap-in on us just as we were waiting.
 311 *
 312 * Also, don't bother to add to the swap cache if this page-in
 313 * was due to a write access.
 314 */
 315void swap_in(struct task_struct * tsk, struct vm_area_struct * vma,
 316        pte_t * page_table, unsigned long entry, int write_access)
 317{
 318        unsigned long page = __get_free_page(GFP_KERNEL);
 319
 320        if (pte_val(*page_table) != entry) {
 321                free_page(page);
 322                return;
 323        }
 324        if (!page) {
 325                set_pte(page_table, BAD_PAGE);
 326                swap_free(entry);
 327                oom(tsk);
 328                return;
 329        }
 330        read_swap_page(entry, (char *) page);
 331        if (pte_val(*page_table) != entry) {
 332                free_page(page);
 333                return;
 334        }
 335        vma->vm_mm->rss++;
 336        tsk->maj_flt++;
 337        if (!write_access && add_to_swap_cache(&mem_map[MAP_NR(page)], entry)) {
 338                /* keep swap page allocated for the moment (swap cache) */
 339                set_pte(page_table, mk_pte(page, vma->vm_page_prot));
 340                return;
 341        }
 342        set_pte(page_table, pte_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot))));
 343        swap_free(entry);
 344        return;
 345}
 346