Ćwiczenie 1
Napisać treść funkcji find_vma(), która dla danego argumentu mm_struct i addr znajduje pierwszy obszar VM, dla którego vm_end jest większe od addr.
Rozwiązanie
Rozwiązanie pochodzi z pliku mm/mmap.c
struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
{
struct vm_area_struct *vma = NULL;
if (mm) {
/* Check the cache first. */
/* (Cache hit rate is typically around 35%.) */
vma = mm->mmap_cache;
if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
struct rb_node * rb_node;
rb_node = mm->mm_rb.rb_node;
vma = NULL;
while (rb_node) {
struct vm_area_struct * vma_tmp;
vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
if (vma_tmp->vm_end > addr) {
vma = vma_tmp;
if (vma_tmp->vm_start <= addr)
break;
rb_node = rb_node->rb_left;
} else
rb_node = rb_node->rb_right;
}
if (vma)
mm->mmap_cache = vma;
}
}
return vma;
}
Ta część jest tylko dla wytrwałych. Zawiera materiał uzupełniający. Zawarte tutaj informacje nie zostały dostosowane do wersji jądra 2.6.
Podstawową literaturą do dalszej części ćwiczeń jest opis alokatora płytowego zamieszczony w rozdziale 3 dokumentacji Memory Management in Linux (dostępnej ze strony wykładowej) oraz kod źródłowy z pliku mm/slab.c.
Na potrzeby ćwiczeń załóżmy, że wymienione stałe mają podane wartości:
SLAB_HWCACHE_ALIGN = 1
(czy zastosować wyrównanie dla sprzętowej pamięci podręcznej)
L1_CACHE_BYTES = 32 (bajty)
(wielkość wyrównania dla sprzętowej pamięci podręcznej w i386)
BYTES_PER_WORD = sizeof(void *)= 4 (bajty)
(wyrównanie dla obiektu)
typedef unsigned int kmem_bufctl_t
sizeof(kmem_bufctl_t) = 4 (bajty)
Podczas analizy działania alokatora można abstrahować od różnych drugorzędnych szczegółów (jak np. ochrony przed wyciekaniem pamięci i błędnym dostępem do pamięci). W przypadkach wątpliwych można przyjmować zdroworozsądkowe założenia.
Kolejne ćwiczenia dotyczą funkcji kmem_cache_create, czyli tworzenia pamięci podręcznej. Oto nagłówek i przykładowe wywołania tej funkcji (dostarczą przykładowych wartości parametrów wejściowych):
struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags,
void (*ctor)(void*, struct kmem_cache *, unsigned long),
void (*dtor)(void*, struct kmem_cache *, unsigned long))
dentry_cache = kmem_cache_create("dentry_cache",
sizeof(struct dentry),
0,SLAB_HWCACHE_ALIGN,NULL, NULL);
Ćwiczenie 2
(Dalszy fragment kmem_cache_create)
Jaki jest sens podanego wyrażenia. Policz jego wartość dla dwóch
wybranych wartości size, będącej i nie będącej wielokrotnością
BYTES_PER_WORD.
if (size & (BYTES_PER_WORD-1)) {
size += (BYTES_PER_WORD-1);
size &=~(BYTES_PER_WORD-1);
}
Rozwiązanie
Komentarz w kodzie mówi sam za siebie: Forcing size word alignment
Ćwiczenie 3
(Dalszy fragment kmem_cache_create)
Jaki jest sens podanego wyrażenia. Policz jego wartość dla dwóch
wybranych wartości size, mniejszej i dużo mniejszej niż
32 bajty (wcześniej wyliczone wyrównanie).
align = BYTES_PER_WORD;
if (flags & SLAB_HWCACHE_ALIGN)
align = L1_CACHE_BYTES;
if (flags & SLAB_HWCACHE_ALIGN) {
while (size < align/2)
align /= 2;
size = (size+align-1) & (~(align-1));;
}
Rozwiązanie
Jeśli jest ustawiona flaga SLAB_HWCACHE_ALIGN, to wyrównanie jest na granicy 32 bajtów, czyli bardzo duże. Jeśli rozmiar obiektu jest niewielki, to próbujemy zmieścić dwa obiekty w jednej linii sprzętowej pamięci podręcznej. Jeśli dwa się zmieszczą, to próbujemy zmieścić cztery itd.
Ćwiczenie 4
(Dalszy fragment kmem_cache_create)
Wyjaśnij wyrażenie wyliczające wartość slab_size. Oblicz
ją dla kilku przykładowych wartości. Pamiętaj, że slab_t to
deskryptor płyty, kmem_bufctl_t to deskryptor pojedynczego
obiektu (a ściślej dowiązanie do następnego wolnego obiektu na
płycie), a num to liczba obiektów na płycie. Funkcja
kmem_cache_estimate wylicza liczbę obiektów na płycie i
pozostałą pamięć. 2^gfporder to liczba spójnych stron,
pobieranych z systemu bliźniaków.
kmem_cache_estimate(cachep->gfporder, size, flags,
&left_over, &cachep->num);
/* tutaj jeszcze kilka drobnych aktualizacji, od których abstrahujemy */
slab_size = L1_CACHE_ALIGN(cachep->num*sizeof(kmem_bufctl_t)+
sizeof(slab_t));
/*
* If the slab has been placed off-slab, and we have enough space then
* move it on-slab. This is at the expense of any extra colouring.
*/
if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
flags &= ~CFLGS_OFF_SLAB;
left_over -= slab_size;
}
Ćwiczenie 5
(Dalszy fragment kmem_cache_create)
Dla wyliczonych wcześniej przykładowych wartości align oblicz
offset - przesunięcie pomiędzy obiektami (parametr wejściowy funkcji
kmem_cache_create),
colour - liczbę dostępnych kolorów (przesunięć na różnych płytach),
colour_off - kolejne przesunięcie.
zgodnie z następującym algorytmem:
/* Offset must be a multiple of the alignment. */
offset += (align-1);
offset &= ~(align-1);
if (!offset)
offset = L1_CACHE_BYTES;
cachep->colour_off = offset;
cachep->colour = left_over/offset;
cachep->objsize = size;
Ćwiczenie 6
Załóżmy, że:
Jakie będą adresy pierwszych obiektów na kolejnych płytach w tej pamięci podręcznej?
Rozwiązanie
Pierwsza płyta: adres 0,
Druga płyta: adres 32,
Trzecia płyta: adres 64,
Czwarta płyta: adres 96,
Piąta płyta: adres 0
itd
Dzięki takiemu ułożeniu obiektów na płytach obiekty z różnych płyt będą trafiały do innego wiersza sprzętowej pamięci podręcznej procesora.
Ćwiczenie 7
Teraz przyjrzyjmy się dokładniej działaniu funkcji kmem_cache_estimate.
static void kmem_cache_estimate (unsigned long gfporder, size_t size,
int flags, size_t *left_over, unsigned int *num)
{
int i;
size_t wastage = PAGE_SIZE<<gfporder;
size_t extra = 0;
size_t base = 0;
if (!(flags & CFLGS_OFF_SLAB)) {
base = sizeof(slab_t);
extra = sizeof(kmem_bufctl_t);
}
i = 0;
while (i*size + L1_CACHE_ALIGN(base+i*extra) <= wastage)
i++;
if (i > 0)
i--;
if (i > SLAB_LIMIT)
i = SLAB_LIMIT;
*num = i;
wastage -= i*size;
wastage -= L1_CACHE_ALIGN(base+i*extra);
*left_over = wastage;
}
i = 0;
}
Na każdą płytę alokujemy 2^gfporder stron. size to rozmiar obiektu, left-over to pozostała w płycie liczba bajtów, num> to liczba obiektów, które da się upchnąć na płycie. Sprawdź efekt jej działania dla kilku przykładowych zestawów wartości parametrów.
Ćwiczenie 8
Załóżmy teraz, że mamy już pustą pamięć podręczną. Teraz możemy w niej umieszczać obiekty. W sytuacji, gdy w żadnej z list dostępnych z deskryptora pamięci podręcznej nie ma miejsca na nowy obiekt, jest wołana funkcja kmem_cache_grow(), która przydziela i inicjuje nową płytę. Prowadzi do niej następujący ciąg wywołań: kmem_cache_alloc() woła __kmem_cache_alloc(), które wchodzi do kmem_cache_alloc_one() (makro), skąd jest skok do wywołania kmem_cache_grow() Oto jej główne fragmenty:
static int kmem_cache_grow (kmem_cache_t * cachep, int flags)
{
slab_t *slabp;
struct page *page;
void *objp;
size_t offset;
unsigned int i, local_flags;
unsigned long ctor_flags;
unsigned long save_flags;
/* Get colour for the slab, and cal the next value. */
offset = cachep->colour_next;
cachep->colour_next++;
if (cachep->colour_next >= cachep->colour)
cachep->colour_next = 0;
offset *= cachep->colour_off;
/* Get mem for the objs. */
if (!(objp = kmem_getpages(cachep, flags)))
goto failed;
/* Get slab management. */
if (!(slabp = kmem_cache_slabmgmt(cachep, objp, offset, local_flags)))
goto opps1;
/* Nasty!!!!!! I hope this is OK. */
i = 1 << cachep->gfporder;
page = virt_to_page(objp);
do {
SET_PAGE_CACHE(page, cachep);
SET_PAGE_SLAB(page, slabp);
PageSetSlab(page);
page++;
} while (--i);
kmem_cache_init_objs(cachep, slabp, ctor_flags);
Funkcja kmem_getpages() sprowadza się zasadniczo do wywołania __get_free_pages() (znanego z algorytmu bliźniaków). Funkcja kmem_cache_slabmgmt() ma za zadanie wypełnić deskryptor płyty:
static inline slab_t * kmem_cache_slabmgmt (kmem_cache_t *cachep,
void *objp, int colour_off, int local_flags)
{
slab_t *slabp;
if (OFF_SLAB(cachep)) {
/* Slab management obj is off-slab. */
slabp = kmem_cache_alloc(cachep->slabp_cache, local_flags);
if (!slabp)
return NULL;
} else {
slabp = objp+colour_off;
colour_off += L1_CACHE_ALIGN(cachep->num *
sizeof(kmem_bufctl_t) + sizeof(slab_t));
}
slabp->inuse = 0;
slabp->colouroff = colour_off;
slabp->s_mem = objp+colour_off;
return slabp;
}
A funkcja kmem_cache_init_objs() inicjuje część płyty przeznaczoną na obiekty (woła dla każdego konstruktor i wypełnia dowiązania do następnego wolnego).
static inline void kmem_cache_init_objs (kmem_cache_t * cachep,
slab_t * slabp, unsigned long ctor_flags)
{
int i;
for (i = 0; i < cachep->num; i++) {
void* objp = slabp->s_mem+cachep->objsize*i;
/*
* Constructors are not allowed to allocate memory from
* the same cache which they are a constructor for.
* Otherwise, deadlock. They must also be threaded.
*/
if (cachep->ctor)
cachep->ctor(objp, cachep, ctor_flags);
slab_bufctl(slabp)[i] = i+1;
}
slab_bufctl(slabp)[i-1] = BUFCTL_END;
slabp->free = 0;
}
Teraz na tablicy powinniśmy już mieć obrazek nowej zainicjowanej pustej pamięci podręcznej z jedną płytą.
Ćwiczenie 9
Oczywiście funkcja kmem_cache_alloc() będzie także wywoływana podczas przydziału nowego obiektu, gdy struktury danych pamięci podręcznej są już zainicjowane. Wtedy wystarczy pobrać z płyty następny wolny obiekt. Oto stosowny fragment kodu funkcji kmem_cache_alloc:
/* get obj pointer */
slabp->inuse++;
objp = slabp->s_mem + slabp->free*cachep->objsize;
slabp->free=slab_bufctl(slabp)[slabp->free];
Prześledzić jego działanie.
Ćwiczenie 10
Oto przykładowa zawartość /proc/slabinfo. W kolejnych kolumnach znajdują się:
| cache-name | nazwa pamięci podręcznej |
| num-active-obj | liczba obiektów w użyciu |
| total-objs | łączna liczba dostępnych obiektów (także nieużywanych) |
| obj-size | rozmiar obiektu |
| num-active-slabs | liczba płyt zawierających aktywne obiekty |
| total-slabs | łączna liczba płyt |
| num-pages-per-slabs | liczba stron na jedną płytę |
kmem_cache 61 68 112 2 2 1
fib6_nodes 1 113 32 1 1 1
ip6_dst_cache 1 20 192 1 1 1
ndisc_cache 1 30 128 1 1 1
ip_fib_hash 4 113 32 1 1 1
clip_arp_cache 0 0 128 0 0 1
ip_mrt_cache 0 0 96 0 0 1
tcp_tw_bucket 0 30 128 0 1 1
tcp_bind_bucket 2 113 32 1 1 1
tcp_open_request 0 40 96 0 1 1
inet_peer_cache 0 0 64 0 0 1
ip_dst_cache 0 20 192 0 1 1
arp_cache 0 30 128 0 1 1
blkdev_requests 128 160 96 4 4 1
devfsd_event 0 0 20 0 0 1
dnotify cache 0 0 20 0 0 1
file lock cache 3 42 92 1 1 1
fasync cache 1 202 16 1 1 1
uid_cache 2 113 32 1 1 1
skbuff_head_cache 52 60 192 3 3 1
sock 40 45 1280 14 15 1
sigqueue 0 29 132 0 1 1
cdev_cache 1881 1888 64 32 32 1
bdev_cache 3 59 64 1 1 1
mnt_cache 11 59 64 1 1 1
inode_cache 83974 83979 512 11997 11997 1
dentry_cache 87337 87360 128 2912 2912 1
dquot 0 0 128 0 0 1
filp 683 690 128 23 23 1
names_cache 0 10 4096 0 10 1
buffer_head 24662 24680 96 617 617 1
mm_struct 38 48 160 2 2 1
vm_area_struct 1899 1920 96 48 48 1
fs_cache 37 59 64 1 1 1
files_cache 37 45 416 5 5 1
signal_act 39 45 1312 13 15 1
size-131072(DMA) 0 0 131072 0 0 32
size-131072 0 0 131072 0 0 32
size-65536(DMA) 0 0 65536 0 0 16
size-65536 0 0 65536 0 0 16
size-32768(DMA) 0 0 32768 0 0 8
size-32768 0 1 32768 0 1 8
size-16384(DMA) 0 0 16384 0 0 4
size-16384 0 4 16384 0 4 4
size-8192(DMA) 0 0 8192 0 0 2
size-8192 2 3 8192 2 3 2
size-4096(DMA) 0 0 4096 0 0 1
size-4096 24 48 4096 24 48 1
size-2048(DMA) 0 0 2048 0 0 1
size-2048 7 40 2048 5 20 1
size-1024(DMA) 0 0 1024 0 0 1
size-1024 38 44 1024 10 11 1
size-512(DMA) 0 0 512 0 0 1
size-512 19 40 512 3 5 1
size-256(DMA) 0 0 256 0 0 1
size-256 12 30 256 1 2 1
size-128(DMA) 0 0 128 0 0 1
size-128 967 1020 128 34 34 1
size-64(DMA) 0 0 64 0 0 1
size-64 658 708 64 12 12 1
size-32(DMA) 0 0 32 0 0 1
size-32 9504 9605 32 85 85 1
Dla dwóch przykładów wybranych z podanej listy, odpowiadających dwóm różnym sposobom alokacji deskryptorów alokatora płytowego (na płycie i poza płytą) rozrysować dokładnie układ wszystkich struktur danych występujących w implementacji alokatora. Wskazać położenie deskryptora płyty, deskryptorów obiektów, kolorowanie na kolejnych płytach.
Rozwiązanie
Spróbujmy np. coś policzyć/sprawdzić dla size-64:
na jednej płycie jest 708/12 = 59 obiektów
59 * 64 = 3776 bajtów na obiekty
4096 - 3776 = 320 zostaje na stronie
59 * 4 = 236 na tablice dowiązań
236 + 22 = 258 na tablicę dowiązań i slab_t
320 - 258 = 62
czyli za mało na kolejny obiekt
32 * 9 = 288
czyli obiekty mogą się zacząć od adresu 288
Czy obszar nieużywany będzie tylko między tablicą wskaźników do następnego wolnego a pierwszym obiektem, czy też może zarówno za tą tablicą, jak i na końcu płyty?
Wyliczyć kolorowanie dla kolejnych płyt.
A teraz spróbujmy np. dla fib6_nodes
strona ma 4096 bajtów
113 * 32 = 3616 bajtów na obiekty
113 * 4 = 452 bajty na dowiązania
size(slab_t) = 22 ?
W sumie = 4090
Czyli zostaje nieużywanych 6 bajtów
22 + 452 = 474 bajtów na slab_t i dowiązania
czyli pierwszy obiekt może się zacząć od adresu 480 (= 15 * 32)
Czyli tylko jeden kolor?
| Janina Mincer-Daszkiewicz |