Do opisu algorytmu refill_freelist
Skomentowane źródła funkcji refill_freelist()
i pomocniczych dla niej (fragment pliku buffer.c)
/* szukamy kandydata do usunięcia z listy lru */
/* (procedura pomocnicza dla refill_freelist) */
static struct buffer_head *find_candidate(struct buffer_head *bh,
int *list_len, int size)
{
int lookahead = 7; /* głębokość poszukiwań kandydata */
if (!bh) /* nie dostaliśmy głowy listy */
goto no_candidate;
/* przeszukuje listę lru w celu znalezienia kandydata */
for (; (*list_len) > 0; bh = bh->b_next_free, (*list_len)--) {
if (size != bh->b_size) {
/* this provides a mechanism for freeing blocks
of other sizes, this is necessary now that we
no longer have the lav code. */
try_to_free_buffer(bh,&bh,1);
if (!bh)
break;
lookahead = 7;
continue;
}
/* znaleziono bufor, ale on jest zajęty (LOCKED)*/
/* kończymy procedure */
else if (buffer_locked(bh) &&
(bh->b_list == BUF_LOCKED || bh->b_list == BUF_LOCKED1)) {
if (!--lookahead) {
(*list_len) = 0;
goto no_candidate;
}
}
/* znaleziono kandydata */
else if (can_reclaim(bh,size))
return bh;
}
no_candidate:
return NULL; /* nie udało się znaleźć kandydata */
}
/* odnów listę wolnych buforów o rozmiarze size */
/* główna procedura wywolływana w algorytmie getblk */
static void refill_freelist(int size)/* size - rozmiar bufora, który chcemy pozyskać*/
{
struct buffer_head * bh;
struct buffer_head * candidate[BUF_DIRTY];
extern struct task_struct *bdflush_tsk;
unsigned int best_time, winner;
int buffers[BUF_DIRTY];
int i, limit = ((min_free_pages + free_pages_low) >> 1);
int needed;
refilled = 1;
/* if there are too many dirty buffers, we wake up the update process
now so as to ensure that there are still clean buffers available
for user process to use (and dirty) */
/* We are going to locate this much memory */
/* obliczamy ilość pamięci potrzebnej do utworzenia buforów */
needed = bdf_prm.b_un.nrefill * size;
/* jeśli jest co najmniej dwa razy więcej stron pamięci, niż */
/* minimalna ilość wolnych stron, to tworzymy nowe bufory ze stron */
while (nr_free_pages > min_free_pages*2 && needed > 0 &&
grow_buffers(GFP_BUFFER, size)) {
needed -= PAGE_SIZE;
}
repeat: /* to jest etykieta - początek zasadniczej pętli funkcji */
allow_interrupts(); /* zezwala na przerwania */
recover_reusable_buffer_heads(); /* pozyskuje nagłowki buforów */
/* jeśli jest już wystarczająca ilość stworzonych buforów,
to kończymy działanie */
if(needed <= 0)
return;
/* OK, we cannot grow the buffer cache, now try to get some
from the lru list */
/* First set the candidate pointers to usable buffers. This
should be quick nearly all of the time. */
/* teraz próbujemy odzyskać bufory z list lru */
/* najpierw dla poszczególnych list lru wyznaczamy po jednym kandydacie, */
/* który był stosunkowo najdawniej ostatnio używany */
for(i=0; i < BUF_DIRTY; i++){
buffers[i] = nr_buffers_type[i];
candidate[i] = find_candidate(lru_list[i], &buffers[i], size);
}
/* Now see which candidate wins the election */
/* ustalamy zwycięzcę - bufor najdłużej
nieużywany spośród kandydatów */
winner = best_time = UINT_MAX;
for(i=0; i < BUF_DIRTY; i++){
if(!candidate[i]) continue; /* dla tej listy nie ma kandydata */
if(candidate[i]->b_lru_time < best_time){
best_time = candidate[i]->b_lru_time;
winner = i;
}
}
/* If we have a winner, use it, and then get a new candidate from that list */
/* jeśli udało się wybrać zwycięzcę, to pozyskujemy go i wstawiamy do */
/* listy wolnych buforów, a następnie wyznaczamy następnego kandydata */
if(winner != UINT_MAX) {
i = winner;
while (needed>0 && (bh=candidate[i])) {
candidate[i] = bh->b_next_free;
if(candidate[i] == bh) candidate[i] = NULL; /* Got last one */
remove_from_queues(bh); /* usuwamy z kolejki lru
i hash_table */
bh->b_dev = B_FREE;
put_last_free(bh); /* wstawiamy go na koniec listy wolnych */
needed -= bh->b_size; /* zmniejszamy zapotrzebowanie */
buffers[i]--;
/* wyczerpana została kolejka - nie ma nowego kandydata */
if(buffers[i] == 0) candidate[i] = NULL;
if (candidate[i] && !can_reclaim(candidate[i],size))
candidate[i] = find_candidate(candidate[i],&buffers[i], size);
}
goto repeat; /* szukamy nowych buforów */
}
/* Too bad, that was not enough. Try a little harder to grow some */
/* nie udało się w ten sposób pozyskać wystarczającej liczby nowych */
/* buforów - jeśli jest jeszcze trochę wolnych stron pamięci,
/* to robimy z nich nowe bufory */
if (nr_free_pages > limit) {
if (grow_buffers(GFP_BUFFER, size)) {
needed -= PAGE_SIZE;
goto repeat;
};
}
/* If we are not bdflush we should wake up bdflush and try it again. */
/* budzimy proces bdfluch zapisujący brudne bufory */
if (current != bdflush_tsk &&
(buffermem >> PAGE_SHIFT) > (MAP_NR(high_memory) >> 2) &&
nr_buffers_type[BUF_DIRTY] > bdf_prm.b_un.nref_dirt) {
wakeup_bdflush(1);
needed -= PAGE_SIZE; /* zmniejszamy zapotrzebowanie */
goto repeat;
}
/* w celu ochrony zasobów systemowych kończymy w tym momencie */
/* jeśli stworzyliśmy choć jeden bufor */
allow_interrupts();
if (free_list[BUFSIZE_INDEX(size)])
return;
/* staramy się wywołać funkcję grow_buffers z wyższym niż */
/* dotychczas priorytetem */
i = grow_buffers(GFP_BUFFER, size);
if (current != bdflush_tsk && !i && nr_buffers_type[BUF_DIRTY] > 0)
wakeup_bdflush(1);
else if (!i)
grow_buffers(GFP_IO, size);
/* decrease needed even if there is no success */
/* zmniejszamy nasze zapotrzebowanie na bufory */
needed -= PAGE_SIZE;
/* zaczynamy od początku */
goto repeat;
}
/*
* Create the appriopriate buffers when given a page for data area and
* the size of each buffer.. Use the bh->b_this_page linked list to
* follow the buffers created. Return NULL if unable to create more
* buffers.
*/
/* tworzy z podanej strony pamięci bufory o podanym rozmiarze */
/* procedura pomocnicza dla funkcji refill_freelist() */
static struct buffer_head * create_buffers(unsigned long page, unsigned long size)
{
struct buffer_head *bh, *head;
long offset;
head = NULL;
offset = PAGE_SIZE;
while ((offset -= size) >= 0) {
/* pobiera wolny nagłówek bufora */
bh = get_unused_buffer_head();
/* nie udało się pobrać nagłówka */
if (!bh)
goto no_grow;
bh->b_dev = B_FREE; /* ustalamy bufor jako wolny */
bh->b_this_page = head; /* dowiązujemy go do listy
buforów z jednej strony */
head = bh;
/* inicjujemy parametry nagłówka bufora */
bh->b_state = 0;
bh->b_next_free = NULL;
bh->b_count = 0;
bh->b_size = size;
bh->b_data = (char *) (page+offset);
bh->b_list = 0;
}
return head;
/*
* In case anything failed, we just free everything we got.
*/
/* nie udało się stworzyć buforów, więc porządkujemy to, co zmieniliśmy */
no_grow:
bh = head;
while (bh) {
head = bh;
bh = bh->b_this_page;
put_unused_buffer_head(head); /* zwalnia nagłówek bufora */
}
return NULL;
}
/*
* Try to increase the number of buffers available: the size argument
* is used to determine what kind of buffers we want.
*/
/* stara się zwiększyć ilość buforów o rozmiarze size */
/* tworzy bufory z wolnych stron pamięci */
/* pri - oznacza priorytet */
static int grow_buffers(int pri, int size)
{
unsigned long page;
struct buffer_head *bh, *tmp;
struct buffer_head * insert_point;
int isize;
if ((size & 511) || (size > PAGE_SIZE)) { /* błąd */
printk("VFS: grow_buffers: size = %d\n",size);
return 0;
}
/* ustala rodzaj buforów, jakie chcemy */
isize = BUFSIZE_INDEX(size);
/* bierzemy wolną stronę pamięci */
if (!(page = __get_free_page(pri)))
return 0;
/* dzieli stronę pamięci na bufory o rozmiarze size */
bh = create_buffers(page, size);
if (!bh) {
free_page(page); /* nie udało się - zwalniamy stronę */
return 0;
}
/* łączymy pozyskane bufory w listę */
insert_point = free_list[isize];
tmp = bh;
/* odpowiednio dowiązujemy wszystkie wskaźniki */
while (1) {
if (insert_point) {
tmp->b_next_free = insert_point->b_next_free;
tmp->b_prev_free = insert_point;
insert_point->b_next_free->b_prev_free = tmp;
insert_point->b_next_free = tmp;
} else {
tmp->b_prev_free = tmp;
tmp->b_next_free = tmp;
}
insert_point = tmp;
++nr_buffers;
if (tmp->b_this_page)
tmp = tmp->b_this_page;
else
break;
}
tmp->b_this_page = bh;
free_list[isize] = bh;
mem_map[MAP_NR(page)].buffers = bh;
buffermem += PAGE_SIZE; /* zwiększamy liczebność buforów */
return 1;
}
autor komentarza: Marek Czajkowski