/*
* linux/mm/kmalloc.c
*
* Copyright (C) 1991, 1992 Linus Torvalds & Roger Wolff.
*
* Written by R.E. Wolff Sept/Oct '93.
*
*/
/*
* Modified by Alex Bligh (alex@cconcepts.co.uk) 4 Apr 1994 to use multiple
* pages. So for 'page' throughout, read 'area'.
*
* Largely rewritten.. Linus
*/
#include <linux/mm.h>
#include <linux/delay.h>
#include <linux/interrupt.h>
#include <asm/system.h>
#include <asm/dma.h>
/*
* Do zdefiniowania w celu zpowolnienia procedur przydziału pamięci dla
* wychwycenia błędów.
*/
#undef SADISTIC_KMALLOC
/* Flagi określające stan bloku w polu block_header.bh_flags */
#define MF_USED 0xffaa0055 /* blok zajęty, nie wymagany dostęp przez kanały DMA */
kanały DMA */
#define MF_DMA 0xff00aa55 /* blok zajęty, ale położony w obszarze stron DMA */
ramek dostępnych przez DMA */
#define MF_FREE 0x0055ffaa /* blok wolny */
/*
* Much care has gone into making these routines in this file reentrant.
*
* The fancy bookkeeping of nbytesmalloced and the like are only used to
* report them to the user (oooohhhhh, aaaaahhhhh....) are not
* protected by cli(). (If that goes wrong. So what?)
*
* These routines restore the interrupt status to allow calling with ints
* off.
*/
/*
* block_header znajduje się na początku każdego bloku, bezwzględu na to czy
* jest pusty czy nie.
*/
struct block_header {
unsigned long bh_flags;
/* flagi MF_... */
union {
unsigned long ubh_length;
/* gdy zajęty, rozmiar alokacji, nie faktycznie zarezerwowanej
* pamięci (pole tylko do statystyki) */
struct block_header *fbh_next;
/* gdy wolny, następny blok takiego samego rozmiaru */
} vp;
};
#define bh_length vp.ubh_length
#define bh_next vp.fbh_next
#define BH(p) ((struct block_header *)(p))
/*
* page_descriptor znajduje się na początku każdej strony
* (lub zestawu stron) używanych przez jądro.
*/
struct page_descriptor {
struct page_descriptor *next;
/* następna strona zawierająca wolne bloki */
struct block_header *firstfree;
/* pierwszy wolny blok */
int order;
/* wartość odpowiadająca indeksowi grupy stron, do której dana strona
* przynależy, w tablicy sizes[]. Niezbędne gdy strona została
* odłączona z listy sizes[indeks].firstfree/dmafree (patrz niżej) */
int nfree;
/* liczba wolnych bloków na stronie */
};
/*
* PAGE_DESC(adr) znajduje początek strony dla danego adresu adr
*/
#define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))
/*
* size_descriptor opisuje klasę bloków danego rozmiaru. Związane są z tym
* dowiązania do list wolnych bloków, rozmiar bloków itp.
*/
struct size_descriptor {
struct page_descriptor *firstfree;
/* ramki zawierające wolne bloki dostępne dla jądra, zapełniona ramka
* jest usuwana z tej listy i podłączana na powrót przy pierwszym
* zwolnieniu bloku zgodnie z jej polem page_descriptor.order */
struct page_descriptor *dmafree;
/* j.w. tylko pamięć z dostępem DMA */
int nblocks;
/* ilość bloków mieszczących się na stronie, to pole jest
* wykorzystywane przy inicjalizacji nowej strony danej grupy */
/*
* Poniższe 4 pola są tylko statystyczne, nigdzie nie sprawdzane, ale
* przydatne być może kiedyś, albo później przy testowaniu procedur jądra
*/
int nmallocs;
/* liczba allokacji zakończona sukcesem dla bloków danego rozmiaru */
int nfrees;
/* liczba poprawnych zwolnień bloków */
int nbytesmalloced;
/* suma aktualnych allokacji, nie faktycznie przydzielonej pamięci */
int npages;
/* liczba zestawów stron, w których system przechowuje bloki odp.
* rozmiaru */
unsigned long gfporder;
/* za pomocą tego pola uzyskamy liczbę stron do stworzenia jednego
* bloku oraz rozmiar wymaganej pamieci, np.
* liczba stron = 1 << gfporder (przydatne gdy blok jest większy od
* strony) */
};
/*
* For now it is unsafe to allocate bucket sizes between n and
* n-sizeof(page_descriptor) where n is PAGE_SIZE * any power of two
*
* The blocksize and sizes arrays _must_ match!
*/
#if PAGE_SIZE == 4096
static const unsigned int blocksize[] = {
32,
64,
128,
252,
508,
1020,
2040,
4096 - 16,
8192 - 16,
16384 - 16,
32768 - 16,
65536 - 16,
131072 - 16,
0
};
static struct size_descriptor sizes[] =
{
{NULL, NULL, 127, 0, 0, 0, 0, 0},
{NULL, NULL, 63, 0, 0, 0, 0, 0},
{NULL, NULL, 31, 0, 0, 0, 0, 0},
{NULL, NULL, 16, 0, 0, 0, 0, 0},
{NULL, NULL, 8, 0, 0, 0, 0, 0},
{NULL, NULL, 4, 0, 0, 0, 0, 0},
{NULL, NULL, 2, 0, 0, 0, 0, 0},
{NULL, NULL, 1, 0, 0, 0, 0, 0},
{NULL, NULL, 1, 0, 0, 0, 0, 1},
{NULL, NULL, 1, 0, 0, 0, 0, 2},
{NULL, NULL, 1, 0, 0, 0, 0, 3},
{NULL, NULL, 1, 0, 0, 0, 0, 4},
{NULL, NULL, 1, 0, 0, 0, 0, 5},
{NULL, NULL, 0, 0, 0, 0, 0, 0}
};
#elif PAGE_SIZE == 8192
static const unsigned int blocksize[] = {
64,
128,
248,
504,
1016,
2040,
4080,
8192 - 32,
16384 - 32,
32768 - 32,
65536 - 32,
131072 - 32,
262144 - 32,
0
};
struct size_descriptor sizes[] =
{
{NULL, NULL, 127, 0, 0, 0, 0, 0},
{NULL, NULL, 63, 0, 0, 0, 0, 0},
{NULL, NULL, 31, 0, 0, 0, 0, 0},
{NULL, NULL, 16, 0, 0, 0, 0, 0},
{NULL, NULL, 8, 0, 0, 0, 0, 0},
{NULL, NULL, 4, 0, 0, 0, 0, 0},
{NULL, NULL, 2, 0, 0, 0, 0, 0},
{NULL, NULL, 1, 0, 0, 0, 0, 0},
{NULL, NULL, 1, 0, 0, 0, 0, 1},
{NULL, NULL, 1, 0, 0, 0, 0, 2},
{NULL, NULL, 1, 0, 0, 0, 0, 3},
{NULL, NULL, 1, 0, 0, 0, 0, 4},
{NULL, NULL, 1, 0, 0, 0, 0, 5},
{NULL, NULL, 0, 0, 0, 0, 0, 0}
};
#else
#error you need to make a version for your pagesize
#endif
#define NBLOCKS(order) (sizes[order].nblocks)
#define BLOCKSIZE(order) (blocksize[order])
#define AREASIZE(order) (PAGE_SIZE<<(sizes[order].gfporder))
/*
* kmalloc_cache[] przechowuje po jednym zestawie wielkości 1,2 i 4 ramek
* (dla MAX_ORDER=3). Zgodnie z tym co napisał autor ma to pomóc przy
* allokacjach z ustawioną flaga GFP_NFS w priority.
*/
#define MAX_CACHE_ORDER 3
struct page_descriptor * kmalloc_cache[MAX_CACHE_ORDER];
static inline struct page_descriptor * get_kmalloc_pages(unsigned long priority,
unsigned long order, int dma)
{
return (struct page_descriptor *) __get_free_pages(priority, order, dma);
}
static inline void free_kmalloc_pages(struct page_descriptor * page,
unsigned long order, int dma)
/*
* Zwolnij jedną(lub zestaw) ramkę do przestrzeni użytkownika. Strony nie
* obsługiwane przez DMA są wcześniej przekazywane do kmalloc_cache[].
*/
{
if (!dma && order < MAX_CACHE_ORDER) {
page = xchg(kmalloc_cache+order, page);
if (!page)
return;
}
free_pages((unsigned long) page, order);
}
long kmalloc_init(long start_mem, long end_mem)
/*
* Funkcja kmalloc_init() sprawdza czy tablica sizes[] została powprawnie
* zainicjowana, wykonywana przy starcie systemu.
*/
{
int order;
for (order = 0; BLOCKSIZE(order); order++) {
if ((NBLOCKS(order) * BLOCKSIZE(order) + sizeof(struct page_descriptor)) >
AREASIZE(order)) {
printk("Cannot use %d bytes out of %d in order = %d block mallocs\n",
(int) (NBLOCKS(order) * BLOCKSIZE(order) +
sizeof(struct page_descriptor)),
(int) AREASIZE(order),
BLOCKSIZE(order));
panic("This only happens if someone messes with kmalloc");
}
}
return start_mem;
}
void *kmalloc(size_t size, int priority)
/*
* Funkcja kmalloc() ma za zadanie przydzielić obszar wielkości size
* wybranego rodzaju pamięci (DMA lub nie - informacja w priority).
*/
{
unsigned long flags;
unsigned long type;
int order, dma;
struct block_header *p;
struct page_descriptor *page, **pg;
struct size_descriptor *bucket = sizes;
/*
* poniżej: znajdowanie minimalnego bloku mieszczącego zadany obszar
* oraz związanej z tym wartości order
*/
order = 0;
{
unsigned int realsize = size + sizeof(struct block_header);
for (;;) {
int ordersize = BLOCKSIZE(order);
if (realsize <= ordersize)
break;
order++;
bucket++;
if (ordersize)
continue;
/* Zażądano przydziału zbyt dużego obszaru */
printk("kmalloc of too large a block (%d bytes).\n", (int) size);
return NULL;
}
}
dma = 0;
type = MF_USED;
pg = &bucket->firstfree;
if (priority & GFP_DMA) {
dma = 1;
type = MF_DMA;
pg = &bucket->dmafree;
}
priority &= GFP_LEVEL_MASK;
/* Sanity check... */
if (intr_count && priority != GFP_ATOMIC) {
static int count = 0;
if (++count < 5) {
printk("kmalloc called nonatomically from interrupt %p\n",
__builtin_return_address(0));
priority = GFP_ATOMIC;
}
}
save_flags(flags);
cli();
page = *pg;
if (!page)
goto no_bucket_page;
p = page->firstfree;
if (p->bh_flags != MF_FREE)
goto not_free_on_freelist;
found_it:
/*
* Znaleziono ramkę z wolnymi blokami. Zmniejsz liczbę wolnych bloków na
* ramce, ewentualnie przejdź do następnej ramki na liście (gdy brak wolnych
* bloków), zamarkuj blok.
*/
page->firstfree = p->bh_next;
page->nfree--;
if (!page->nfree)
*pg = page->next;
restore_flags(flags);
bucket->nmallocs++;
bucket->nbytesmalloced += size;
p->bh_flags = type;
p->bh_length = size;
#ifdef SADISTIC_KMALLOC
memset(p+1, 0xf0, size);
#endif
/*
* Zwracamy adres wolnej pamięci znajdujący się bezpośrednio po block_header
*/
return p + 1;
no_bucket_page:
/*
* Na liście z tablicy sizes[] nie było ramki z wolnymi blokami,
* należy ją przydzielić z przestrzeni użytkownika
*/
restore_flags(flags);
{
int i, sz;
/* sz is the size of the blocks we're dealing with */
sz = BLOCKSIZE(order);
page = get_kmalloc_pages(priority, bucket->gfporder, dma);
if (!page)
goto no_free_page;
found_cached_page:
/*
* Nowa strona dostępna dla jądra (lub z kmalloc_cache[]).
* Trzeba ją przygotować.
*/
bucket->npages++;
page->order = order;
/* Pętla dla wszystkich poza ostatnim blokiem: */
i = (page->nfree = bucket->nblocks) - 1;
p = BH(page + 1);
while (i > 0) {
i--;
p->bh_flags = MF_FREE;
p->bh_next = BH(((long) p) + sz);
p = p->bh_next;
}
/* Ostatni blok: */
p->bh_flags = MF_FREE;
p->bh_next = NULL;
p = BH(page+1);
}
/*
* Nowo przygotowaną ramkę należy dołączyć do listy wolnych ramek tablicy
* sizes[].
* Ta operacja nie może być przerwana.
*/
cli();
page->next = *pg;
*pg = page;
goto found_it;
no_free_page:
/*
* Nie można użytkownikowi wyrwać żadnej ramki, w tym przypadku jedyną nadzieją
* jest kmalloc_cache[] ramek.
*/
if (!dma && order < MAX_CACHE_ORDER) {
page = xchg(kmalloc_cache+order, page);
if (page)
goto found_cached_page;
}
{
static unsigned long last = 0;
if (priority != GFP_BUFFER && (last + 10 * HZ < jiffies)) {
last = jiffies;
printk("Couldn't get a free page.....\n");
}
return NULL;
}
not_free_on_freelist:
/*
* Nie ma wolnego bloku na stronie, która znajdowała się na liście wolnych
* system się poważnie sypnął
*/
restore_flags(flags);
printk("Problem: block on freelist at %08lx isn't free.\n", (long) p);
return NULL;
}
void kfree(void *__ptr)
/*
* Procedura kfree() zwalnia obszar pamięci zaczynający się od adresu __ptr
*/
{
int dma;
unsigned long flags;
unsigned int order;
struct page_descriptor *page, **pg;
struct size_descriptor *bucket;
/*
* Sprawdź czy istnieją pola identyfikacyjne bloku i strony dla danego
* adresu oraz czy są sensowne, jeżeli nie - wyjdź z błędem
*/
if (!__ptr)
goto null_kfree;
#define ptr ((struct block_header *) __ptr)
page = PAGE_DESC(ptr);
__ptr = ptr - 1;
if (~PAGE_MASK & (unsigned long)page->next)
goto bad_order;
order = page->order;
if (order >= sizeof(sizes) / sizeof(sizes[0]))
goto bad_order;
bucket = sizes + order;
dma = 0;
pg = &bucket->firstfree;
if (ptr->bh_flags == MF_DMA) {
dma = 1;
ptr->bh_flags = MF_USED;
pg = &bucket->dmafree;
}
if (ptr->bh_flags != MF_USED)
goto bad_order;
ptr->bh_flags = MF_FREE;
#ifdef SADISTIC_KMALLOC
memset(ptr+1, 0xe0, ptr->bh_length);
#endif
save_flags(flags);
cli();
bucket->nfrees++;
bucket->nbytesmalloced -= ptr->bh_length;
/*
* Dopisz zwalniany blok do odpowiadającej mu strony
*/
ptr->bh_next = page->firstfree;
page->firstfree = ptr;
if (!page->nfree++) {
/*
* Strona wcześniej była pełna, zwolniliśmy jeden blok. Należy dołączyć
* ją na listę wolnych w tablicy sizes[] (do firstfree/dmafree)
*/
if (bucket->nblocks == 1)
goto free_page;
page->next = *pg;
*pg = page;
}
if (page->nfree == bucket->nblocks) {
/*
* Strona jest zupełnie pusta, należy ją zwolnić, wcześniej sprawdzając
* poprawność dowiązań.
*/
for (;;) {
struct page_descriptor *tmp = *pg;
if (!tmp)
goto not_on_freelist;
if (tmp == page)
break;
pg = &tmp->next;
}
*pg = page->next;
free_page:
bucket->npages--;
free_kmalloc_pages(page, bucket->gfporder, dma);
}
restore_flags(flags);
null_kfree:
return;
bad_order:
/*
* Ten adres na pewno nie wskazuje na początek następnej strony,
* lub niewłaściwa wartość order.
*/
printk("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
ptr+1, page->next, page->order);
return;
not_on_freelist:
printk("Ooops. page %p doesn't show on freelist.\n", page);
restore_flags(flags);
}