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