Skomentowany kod źródłowy pliku page_alloc.c


/*  *  linux/mm/page_alloc.c  *  *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds  *  Swap reorganised 29.12.95, Stephen Tweedie  */ #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 <linux/swap.h> #include <linux/fs.h> #include <linux/swapctl.h> #include <linux/interrupt.h> #include <asm/dma.h> #include <asm/system.h> /* for cli()/sti() */ #include <asm/segment.h> /* for memcpy_to/fromfs */ #include <asm/bitops.h> #include <asm/pgtable.h> int nr_swap_pages = 0;      int nr_free_pages = 0;     /* Liczba wolnych ramek */ /*  * Free area management  *  * The free_area_list arrays point to the queue heads of the free areas  * of different sizes  */ #define NR_MEM_LISTS 6 /* The start of this MUST match the start of "struct page" */ /* Struktura służy do przechowywania początków cyklicznych list spójnych   * wolnych obszarów pamięci */         struct free_area_struct {         struct page *next;       /*  Pierwszy element listy */         struct page *prev;       /*  Ostatni element listy */         unsigned int * map; }; #define memory_head(x) ((struct page *)(x)) /* Tablica której pola zawierają początki cyklicznych list spójnych   * wolnych obszarów pamięci. Lista o początku free_area[i] zawiera   * spójne obszary wielkości PAGE_SIZE*(2i) */ static struct free_area_struct free_area[NR_MEM_LISTS]; /* Funkcja inicjująca pustą listę (parametr head - początek listy)*/ static inline void init_mem_queue(struct free_area_struct * head) {         head->next = memory_head(head);         head->prev = memory_head(head); } /* Funkcja dodająca jedną ramkę (parametr entry - dodawana do listy ramka)  * do listy wolnych ramek (parametr head)   */ static inline void add_mem_queue(struct free_area_struct * head, struct page * entry) {         struct page * next = head->next;         entry->prev = memory_head(head);         entry->next = next;         next->prev = entry;         head->next = entry; } /* Funkcja usuwa jedną ramkę (parametr entry) z listy */ static inline void remove_mem_queue(struct page * entry) {         struct page * next = entry->next;         struct page * prev = entry->prev;         next->prev = prev;         prev->next = next; } /*  * Free_page() adds the page to the free lists. This is optimized for  * fast normal cases (no error jumps taken normally).  *  * The way to optimize jumps for gcc-2.2.2 is to:  *  - select the "normal" case and put it inside the if () { XXX }  *  - no else-statements if you can avoid them  *  * With the above two rules, you get a straight-line execution path  * for the normal case, giving better asm-code.  *  * free_page() may sleep since the page being freed may be a buffer  * page or present in the swap cache. It will not sleep, however,  * for a freshly allocated page (get_free_page()).  */ /*  * Buddy system. Hairy. You really aren't expected to understand this  *  * Hint: -mask = 1+~mask  */ /* Funkcja wywoływana przez funkcje __free_page oraz free_pages  * jest odpowiedzialna za dołączanie zwalnianych ramek do odpowiedniej   * listy free_area[i].Realizuje ona algorytm bliźniaków ("Buddy"),  * w którym zajmowanie i zwalnianie ramek łączy się odpowiednio z  * rozbijaniem i łączeniem bloków. Przy czym rozbijając bloki, tworzymy   * jedynie bloki o rozmiarze równym:(potęga dwójki)*PAGE_SIZE,natomiast  * łączymy tylko te bloki które przedtem rozbijaliśmy .   * Parametry:  * map_nr - numer pierwszej ramki w zwalnianym spójnym obszarze pamięci  *          w tablicy mem_map   * order - liczba zwalnianych ramek = 2(order) , zwykle order = 0  */  static inline void free_pages_ok(unsigned long map_nr, unsigned long order) {         struct free_area_struct *area = free_area + order;         unsigned long index = map_nr >> (1 + order);  /* mask = - liczba zwalnianych ramek */         unsigned long mask = (~0UL) << order;         unsigned long flags;         save_flags(flags);         cli(); #define list(x) (mem_map+(x))         map_nr &= mask; /* aktualizacja liczby wolnych ramek */         nr_free_pages -= mask;
/* W każdym obrocie tej pętli sprawdzamy czy odpowiadający
 * naszemu obszar pamięci jest wolny. Jeśli tak to łączymy oba obszary 
 * w jeden dwa razy większy i w następnym obrocie pętli sprawdzamy czy  
 * obszar odpowiadający otrzymanemu z połączenia jest wolny. */
        while (mask + (1 << (NR_MEM_LISTS-1))) {
                if (!change_bit(index, area->map))
                        break;
/* usuwamy znaleziony obszar pamięci z listy wolnych obszarów o tej
 * wielkości */
                remove_mem_queue(list(map_nr ^ -mask)); 
                mask <<= 1; // mamy dwa razy więcej ramek w połączonym 
                               obszarze
                area++;     // teraz szukamy obszaru dwa razy większego
                index >>= 1;
                map_nr &= mask;
        }
/* dodajemy utworzony obszar pamięci do odpowiedniej listy wolnych 
 * obszarów */
        add_mem_queue(area, list(map_nr)); 

#undef list

        restore_flags(flags);
}

/* Funkcja zwalniająca pojedynczą ramkę pamięci. 
 * Parametr page - struktura odpowiadająca zwalnianej ramce */
void __free_page(struct page *page)
{
        if (!PageReserved(page) && atomic_dec_and_test(&page->count)) {
                unsigned long map_nr = page->map_nr;
                delete_from_swap_cache(map_nr);
                free_pages_ok(map_nr, 0);
        }
}

/* Funkcja zwalniająca obszar pamięci wielkości 2(order)*PAGE_SIZE.
 * addr - numer pierwszej zwalnianej ramki */ 
void free_pages(unsigned long addr, unsigned long order)
{
        unsigned long map_nr = MAP_NR(addr);

        if (map_nr < MAP_NR(high_memory)) {
                mem_map_t * map = mem_map + map_nr;
                if (PageReserved(map))
                        return;
                if (atomic_dec_and_test(&map->count)) {
                        delete_from_swap_cache(map_nr);
                        free_pages_ok(map_nr, order);
                        return;
                }
        }
}

/*
 * Some ugly macros to speed up __get_free_pages()..
 */
#define MARK_USED(index, order, area) \
        change_bit((index) >> (1+(order)), (area)->map)
#define CAN_DMA(x) (PageDMA(x))
#define ADDRESS(x) (PAGE_OFFSET + ((x) << PAGE_SHIFT))

/* Makro służące do znalezienia wolnego obszaru pamięci i odpowiedniej
 * modyfikacji struktur przechowywujących wolne ramki .
 * (Zgodnie ze strategią Buddy) 
 * Parametry:
 * order - określa wielkość poszukiwanego obszaru:(2(order) ramek)
 * dma - tryb przydzielania ramek */
#define RMQUEUE(order, dma) \
do { struct free_area_struct * area = free_area+order; \
/* new_order określa wielkość wolnego obszaru jakiego właśnie szukamy: 
 *           (2(new_order) ramek)
     unsigned long new_order = order; \
        do { struct page *prev = memory_head(area), *ret; \
                while (memory_head(area) != (ret = prev->next)) { \
                        if (!dma || CAN_DMA(ret)) { \
/* Znaleźliśmy obszar o wielkości nie mniejszej od poszukiwanej */
                                unsigned long map_nr = ret->map_nr; \
/* Usuwamy go z listy wolnych obszarów pamięci */
                                (prev->next = ret->next)->prev = prev; \
                                MARK_USED(map_nr, new_order, area); \
/* Aktualizujemy liczbę wolnych ramek */
                                nr_free_pages -= 1 << order; \
/* Ponieważ znaleziony spójny, wolny obszar pamięci może być większy niż
 * potrzebujemy, musimy zająć się jej resztą. Zajmuje się tym makro
 * EXPAND (opis poniżej) */
                                EXPAND(ret, map_nr, order, new_order, area); \
                                restore_flags(flags); \
                                return ADDRESS(map_nr); \
                        } \
                        prev = ret; \
                } \
                new_order++; area++; \
        } while (new_order < NR_MEM_LISTS); \
} while (0)

/* Makro zajmujące się podziałem i zapisaniem w odpowiednich listach
 * nadmiaru pamięci w znalezionym obszarze. 
 * Parametry:
 * map - pierwsza ramka znalezionego obszaru
 * index - numer pierwszej w znalezionym obszarze ramki
 * ilość ramek jaką chcieliśmy zająć = 2(low)
 * ilość ramek jaką znaleźliśmy = 2(high)
 * area - lista w której znaleźliśmy obszar */
#define EXPAND(map,index,low,high,area) \
do { unsigned long size = 1 << high; \
        while (high > low) { \
                area--; high--; size >>= 1; \
                add_mem_queue(area, map); \
                MARK_USED(index, high, area); \
                index += size; \
                map += size; \
        } \
        map->count = 1; \
        map->age = PAGE_INITIAL_AGE; \
} while (0)
/* Funkcja służąca do alokowania wolnych ramek 
 * Parametry:

 *  priority i dma - służą do sprawdzania trybu przydzielania ramki 
 *  wielkość poszukiwanego obszaru = 2(order) */
unsigned long __get_free_pages(int priority, unsigned long order, int dma)
{
        unsigned long flags;
        int reserved_pages;

        if (order >= NR_MEM_LISTS)
                return 0;
        if (intr_count && priority != GFP_ATOMIC) {
                static int count = 0;
                if (++count < 5) {
                        printk("gfp called nonatomically from interrupt %p\n",
                                __builtin_return_address(0));
                        priority = GFP_ATOMIC;
                }
        }
        reserved_pages = 5;
        if (priority != GFP_NFS)
                reserved_pages = min_free_pages;
        if ((priority == GFP_BUFFER || priority == GFP_IO) && reserved_pages >= 48)
                reserved_pages -= (12 + (reserved_pages>>3));
        save_flags(flags);
repeat:
        cli();
        if ((priority==GFP_ATOMIC) || nr_free_pages > reserved_pages) {
/* tu wywoływane jest makro odnajdujące poszukiwany obszar */
                RMQUEUE(order, dma);
                restore_flags(flags);
                return 0;
        }
        restore_flags(flags);
        if (priority != GFP_BUFFER && try_to_free_page(priority, dma, 1))
                goto repeat;
        return 0;
}

/*
 * Show free area list (used inside shift_scroll-lock stuff)
 * We also calculate the percentage fragmentation. We do this by counting the
 * memory on each free list with the exception of the first item on the list.
 */
/* Funkcja ma za zadanie wypisywać na ekran informacje o aktualnym stanie
 * wolnej pamięci. */
void show_free_areas(void)
{
        unsigned long order, flags;
        unsigned long total = 0;

        printk("Free pages:      %6dkB\n ( ",nr_free_pages<<(PAGE_SHIFT-10));
        save_flags(flags);
        cli();
        for (order=0 ; order < NR_MEM_LISTS; order++) {
                struct page * tmp;
                unsigned long nr = 0;
                for (tmp = free_area[order].next ; tmp != memory_head(free_area+order) ; tmp = tmp->next) {
                       nr ++;
                }
                total += nr * ((PAGE_SIZE>>10) << order);
                printk("%lu*%lukB ", nr, (PAGE_SIZE>>10) << order);
        }
        restore_flags(flags);
        printk("= %lukB)\n", total);
#ifdef SWAP_CACHE_INFO
        show_swap_cache_info();
#endif  
}

#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))

/*
 * set up the free-area data structures:
 *   - mark all pages reserved
 *   - mark all memory queues empty
 *   - clear the memory bitmaps
 */
/* Funkcja uruchamiana podczas startu systemu. 
 * Inicjuje struktury służące do zarządzania ramkami. */
unsigned long free_area_init(unsigned long start_mem, unsigned long end_mem)
{
        mem_map_t * p;
        unsigned long mask = PAGE_MASK;
        int i;

        /*
         * select nr of pages we try to keep free for important stuff
         * with a minimum of 48 pages. This is totally arbitrary
         */
        i = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT+7);
        if (i < 24)
                i = 24;
        i += 24;   /* The limit for buffer pages in __get_free_pages is
                    * decreased by 12+(i>>3) */
/* ustalenie wartości zmiennych min_free_pages, free_pages_low, 
 * free_pages_high. Decydują one przy jakiej ilości wolnych ramek
 * jak bardzo system będzie się starał zwalniać ramki */
        min_free_pages = i;
        free_pages_low = i + (i>>1);
        free_pages_high = i + i;
        start_mem = init_swap_cache(start_mem, end_mem);
        mem_map = (mem_map_t *) start_mem;
        p = mem_map + MAP_NR(end_mem);
        start_mem = LONG_ALIGN((unsigned long) p);
        memset(mem_map, 0, start_mem - (unsigned long) mem_map);
        do {
                --p;
                p->flags = (1 << PG_DMA) | (1 << PG_reserved);
                p->map_nr = p - mem_map;
        } while (p > mem_map);

        for (i = 0 ; i < NR_MEM_LISTS ; i++) {
                unsigned long bitmap_size;
                init_mem_queue(free_area+i);
                mask += mask;
                end_mem = (end_mem + ~mask) & mask;
                bitmap_size = (end_mem - PAGE_OFFSET) >> (PAGE_SHIFT + i);
                bitmap_size = (bitmap_size + 7) >> 3;
                bitmap_size = LONG_ALIGN(bitmap_size);
                free_area[i].map = (unsigned int *) start_mem;
                memset((void *) start_mem, 0, bitmap_size);
                start_mem += bitmap_size;
        }
        return start_mem;
}

/*
 * The tests may look silly, but it essentially makes sure that
 * no other process did a swap-in on us just as we were waiting.
 *
 * Also, don't bother to add to the swap cache if this page-in
 * was due to a write access.
 */
void swap_in(struct task_struct * tsk, struct vm_area_struct * vma,
        pte_t * page_table, unsigned long entry, int write_access)
{
        unsigned long page = __get_free_page(GFP_KERNEL);

        if (pte_val(*page_table) != entry) {
                if (page)
                        free_page(page);
                return;
        }
        if (!page) {
                set_pte(page_table, BAD_PAGE);
                swap_free(entry);
                oom(tsk);
                return;
        }
        read_swap_page(entry, (char *) page);
        if (pte_val(*page_table) != entry) {
                free_page(page);
                return;
        }
        vma->vm_mm->rss++;
        tsk->maj_flt++;

        /* Give the physical reallocated page a bigger start */
        if (vma->vm_mm->rss < (MAP_NR(high_memory) >> 2))
                mem_map[MAP_NR(page)].age = (PAGE_INITIAL_AGE + PAGE_ADVANCE);

        if (!write_access && add_to_swap_cache(MAP_NR(page), entry)) {
                /* keep swap page allocated for the moment (swap cache) */
                set_pte(page_table, mk_pte(page, vma->vm_page_prot));
                return;
        }
        set_pte(page_table, pte_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot))));
        swap_free(entry);
        return;
}


Autor : Radosław Rudzki