[Kos-dev] Allocateur de memoire virtuelle pour le noyau

[Thomas Petazzoni]

bonjour a tous,

je veux par ce mail exposer le probleme de l'Allocateur de memoire
virtuelle pour le noyau.

Probleme : jusqu'a maintenant le noyau tournait dans l'identity mapping,
ce qui n'est plus le cas depuis les vacances de paques. Toutefois, le
kmalloc continue a retourner des adresses dans l'identity mapping, car
il realise pour se procurer des nouvelles pages, un simple
get_physical_page, sans les mapper en memoire virtuelle. Nous souhaitons
donc changer ca.


Proposition de solution :

au lieu d'appeler directement get_physical_page, kmalloc pourrait
appeler un allocateur de memoire virtuelle pour le noyau, le kvalloc.
Cet allocateur est un allocateur par taille multiple de la taille d'une
page. Il doit pouvoir allouer des pages contigues en memoire virtuelle.
Rappel : la zone du noyau est comprise entre 512M et 768M, et l'espace
utilise au moment du lancement du noyau peut etre connu : 512M est le
debut, et l'adresse de fin des sections .init se trouve dans les
kernel_parameters, passees a chaque init_module.

Notre kvalloc doit donc trouver un espace d'adresse suffisamment grand
et libre, allouer suffisamment de pages physiques, et les mapper dans
l'espace virtuel trouve precedemment.

kvalloc(n*PAGE_SIZE) =>	1. recherche d'un "range" virtuel assez grand et
libre, de n pages
			2. allocation de n pages physiques, pas forcement contigues (c'est
l'interet du truc)
			3. mapping de ces n pages physiques dans le range virtuel

on peut aussi envisager de laisser faire l'allocation a la demande, pour
pas a avoir a allouer d'un coup n pages physiques, ca peut etre lourd.
le handler de page fault peut s'en charger.

Kvalloc peut etre utilise dans 2 cas, soit indirectement par kmalloc qui
ne fera que des requetes pour des tailles d'une page, soit directement
pour allouer des tailles plus grande en memoire virtuelle (pour des
bitmap, ou autre).

L'idee d'implementation du kvalloc pour la recherche d'un "range"
virtuel assez grand

A l'initialisation on cree une liste qui contient 2 ranges :
	premier range : de 512M a endof(.init sections), etat USED
	second range  : de endof(.init sections), etat FREE
Deja, premier probleme : pour creer des range, on a besoin de faire un
kmalloc (new_range = (chained_range_t *)
kmalloc(sizeof(chained_range_t)); ), qui a besoin de faire des appels au
kvalloc pour avoir des pages virtuelles (mappe si on decide de le faire
directement, ou qui seront mappes lors du premier acces). deja il y a un
probleme. celui ci peut etre resolu simplement car comme on sait qu'au
depart on aura que 2 ranges, on peut les allouer en statique.

ensuite lorsqu'on veut un range, on splitte un range a l'etat FREE : on
alloue un range, qu'on mettra a l'etat USED, et l'autre range, on
modifie son start pour qu'il soit reduit du nombre de pages qu'on a mis
dans le nouveau range.

les ranges a l'etat FREE et a l'etat USED sont dans la meme liste, car
c'est bien plus facile pour les trier par adresse croissante, ce qui est
indispensable pour eviter la fragmentation de la memoire.

le hic c'est que quand on va vouloir allouer un range pour le mettre a
l'etat USED, bin il va falloir faire kmalloc, qui aura besoin de
kvalloc, et on sera bloque.

on peut se passer de maintenir les blocs a l'etat USED, ca simplifierait
tout, il n'y aurait alors pas besoin de faire d'allocation lors du
kvalloc, et tout marcherait nickel, le seul probleme c'est qu'a partir
de l'adresse de debut d'un range, on pourra pas determiner l'adresse de
fin lors de la liberation. il faudra donc la preciser en argument a
kvfree.

La solution que je propose :

	addr_t kvalloc(size_t size) {
		pour tous les range de la liste faire {
			si range->end - range->start < size faire continue;

			si range->end - range->start = size faire supprimer le range de la
liste (il fait pil poil la bonne taille) et retourner l'adresse
range->start

			si range->end - range->start > size faire {
				adresse_allouee = range->start;
				range->start += size;
			}

			si le range courant est voisin de celui d'avant ou celui d'apres, le
merger avec pour eviter la fragmentation en tout petits blocs.
	}

ca c'est la solution ou la handler de page fault se charge de faire lui
meme les allocations comme il faut. bien sur il verifie dans la liste de
ces blocs que la page qui a genere le page fault a bien ete allouee
auparavant.

ensuite

	int kvfree(addr_t start, addr_t end) {
		scanner la liste pour trouver la bonne place {
			si le range passe en argument est voisin (a gauche ou a droite) d'un
range existant, le merger

			sinon allouer un nouveau range, et l'ajouter a la liste
		}
	}

honnetement je trouve pas ca trop contraignant de devoir passer
l'adresse de debut et l'adresse de fin. kmalloc lui fait des allocations
par page unique, donc c'est pas dur kvfree(addr, addr+PAGE_SIZE), puis
dans les rares autres cas y'aura qu'a se souvenir de la taille.

qu'en penses-tu d2 ?

thomas

-- 
PETAZZONI Thomas
thomas.petazzoni@meridon.com     UIN : 34937744
Projet KOS : http://kos.enix.org
Page Perso : http://www.enix.org/~thomas/