Alokátor systémové paměti

Jedním z nejdůležitějších prostředků operačního systému je fyzická paměť RAM. Veškerá paměť RAM je systému k dispozici jako souvislý úsek paměti v prostoru operačního systému, tedy v oblasti horních 2 GB adresovatelného prostoru. Každá 4 KB stránka paměti může být díky stránkování paměti mapovatelná současně i do uživatelského adresového prostoru a tak přechodně "zapůjčena" uživatelským programům jako virtuální paměť.

Poznámka: Systém Litos nevyužívá paměť větší než 2 GB (tak jak to dělají jiné operační systémy) z důvodu nízké rychlosti přístupu k takové paměti a neúměrných komplikací při adresaci paměti. Využití většího rozsahu paměti je přenecháno na 64-bitovou verzi systému Litos.

K udržení přehledu o využití systémové paměti používá systém alokátor systémové paměti, který umožňuje označovat jednotlivé části paměti jako použité a vyhledávat volné úseky paměti. Alokátor paměti systému Litos rozděluje paměť na oblasti úseků s bloky stejné velikosti odvozené od mocniny dvou. Např. 64 KB úsek obsahuje 4 bloky o velikosti 16 KB, 1024 bloků o velikosti 64 bajtů atd. Díky této metodě je alokátor paměti velmi rychlý a efektivní a nedochází k fragmentaci paměti jako u jiných alokátorů. Další velkou předností tohoto alokátoru paměti je, že každý alokovaný blok je automaticky zarovnán na svou velikost. To znamená, že např. bloky 8 bajtů začínají na adresách, které jsou násobkem čísla 8, bloky 16 KB začínají na násobcích 16 K. Této přednosti je často využíváno, např. ukazatel na strukturu aktuálně běžící úlohy lze snadno zjistit zarovnáním adresy ukazatele zásobníku na 8 KB.

Základem evidence systémové paměti jsou 2 datová pole - mapa řádu bloků a pole čítačů použitých bloků. Každá položka pole popisuje jeden úsek paměti. Velikost jednoho úseku je typicky 64 KB (může být i 32 KB nebo 128 KB, v závislosti na překladu jádra systému Litos). Při přidělení nového bloku paměti je požadovaná velikost paměti nejdříve zaokrouhlena na nejbližší mocninu dvou a poté je buď nalezen volný blok o této velikosti nebo obsazen nový prázdný úsek, rozdělen na stejné bloky odpovídající velikosti a jednotlivé bloky zařazeny do zásobníku volných bloků.

Pole řádu bloků obsahuje řád velikosti bloku v příslušném úseku paměti (3=8 bajtů, 4=16 bajtů, .... 12=4 KB, ... 16=64 KB). Položka pole řádu bloků je nastavena při obsazení nového úseku. Pole čítačů použití obsahuje počet alokovaných paměťových bloků v úseku. U nově obsazeného úseku je tato hodnota 0, při postupné alokaci bloků se čítač zvyšuje až na maximální hodnotu. Při uvolňování bloků se hodnota čítače snižuje, po dosažení hodnoty 0 je úsek uvolněn.

Během inicializace alokátoru paměti se pole alokátoru inicializují podle bitové mapy zaplnění paměti, která byla naplněna během inicializace v reálném módu podle informací z BIOS. Bitová mapa označuje stav jednotlivých 4 KB stránek paměti, hodnota bitu 1 udává volnou stránku paměti. Nejdříve jsou všechny úseky paměti označeny jako obsazené stránkami 4 KB (řád úseku 12), poté jsou doplňováním volných stránek bloky uvolňovány a zařazovány do seznamu volných bloků a případně seznamu volných úseků.

Seznam volných úseků je seznam typu "doubly linked list" neboli seznam s dvojitými ukazateli. Každý volný úsek obsahuje na svém začátku ukazatele na následující a předcházející úsek v seznamu. Stejné ukazatele obsahuje i záhlaví seznamu. Tento typ seznamu umožňuje snadné a rychlé vkládání a vyjímání prvků a nevyžaduje žádné další pomocné struktury, je použita přímo oblast začátku úseku. Po vyjmutí úseku ze seznamu se ukazatele nadále již nepoužívají. Příslušná položka v poli řádů bloků je nastavena na odpovídající řád velikosti bloku (podle požadované velikosti bloku), úsek je rozdělen na bloky a jednotlivé bloky zařazeny do seznamů volných bloků.

Seznam volných bloků využívá obdobný dvojitě linkovaný seznam volných bloků. Bloky stejné velikosti jsou seskupovány do řetězců připojených k příslušnému záhlaví seznamu. Takto lze velmi snadno a rychle vyhledat blok paměti požadované velikosti - postačí jej vyjmout z příslušného seznamu nebo vytvořit novou sadu volných bloků alokací nového úseku. Po alokaci bloku je inkrementován čítač použití úseku, do kterého blok patří.

Při uvolnění (dealokaci) paměťového bloku je zarovnáním adresy na velikost úseku nejdříve zjištěno, ke kterému úseku blok patří a jakou má velikost (podle řádu úseku). Poté je úsek zařazen do seznamu volných úseků patříčného záhlaví a dekrementován čítač použítí bloků v úseku. Dosáhne-li čítač použití bloků nuly, tedy všechny bloky byly do úseku navráceny, jsou příslušné bloky uvolněny ze seznamu volných bloků a úsek je zařazen zpět do seznamu volných úseků.

Zvláštní postavení má DMA paměť. DMA paměť je systémová paměť rezervovaná pro DMA operace, neboli přenosy dat s přímým přístupem k paměti. Je využívána některými ovladači zařízení. Jedná se o běžnou paměť s tím rozdílem, že architektura řadiče DMA přenosů vyžaduje, aby použitá paměť ležela v prvních 16 MB fyzické adresy paměti. Proto je malá část systémové paměti trvale vyhrazena jako DMA paměť a systém ji jinak nevyužívá. Druhou podmínkou DMA paměti je, že blok DMA paměti nesmí překrývat přelomy paměti 64 KB.

Poznámka: Veškerá fyzická paměť RAM (do velikosti 2 GB) je pomocí stránkování přemapována do oblasti systémové paměti, tj. od adresy 80000000h, proto DMA paměť nebude mít v systému adresu 0 až 1000000h (=fyzická adresa), ale 80000000h až 81000000h (=logická adresa).

Alokace DMA paměti nejsou časté operace a proto je obsluha alokace poměrně jednoduchá. Úseky volných oblastí DMA paměti jsou spřaženy pomocí dvojitě linkovaného seznamu, který je adresově setříděn. Při alokaci DMA bloku paměti je prohledán seznam volných bloků, až je nalezen blok dostačující velikosti, a ten je použit. Přitom je zajištěno, aby byla použita ta část bloku, která nepřekrývá přelom paměti 64 KB. Zbylá část bloku je navrácena zpět do seznamu volných bloků. Při uvolnění bloku je podle adresy vyhledáno místo, kam má být blok zařazen, a tam je blok zasunut. Pokud navazuje na předcházející nebo následující blok, jsou bloky spojeny do jednoho úseku.

Zde je několik základních definic struktur a konstant, které jsou v implementaci použity. Konstanty i funkce se mohou měnit v závislosti na překladu, ale pro zjednodušení budeme uvažovat nejtypičtější případ.


SYSTEM_ADDR	EQU	80000000h	; address of system area
SYSTEM_SIZE	EQU	80000000h	; size of system area

PageMemMap:	resb	SYSTEM_SIZE/4096/8 ; memory bit map of free pages


PAGE_SIZE	EQU	4096		; memory page size

DMAMAXMEM	EQU	1000000h	; maximal DMA memory size (16 MB)
DMAMINMEM	EQU	8000h		; minimal DMA memory size (32 KB)

MEMAREASHIFT	EQU	16		; bit shifts of memory area (64 KB)
MEMAREAMINSHIFT	EQU	3		; minimal order of memory block
MEMMINBLOCK	EQU	1<<MEMAREAMINSHIFT ; minimal memory block
MEMAREASIZE	EQU	1<<MEMAREASHIFT	; size of memory area (64 KB)
MEMAREAMASK	EQU	~(MEMAREASIZE-1) ; mask memory area
MEMAREAPAGES	EQU	MEMAREASIZE/PAGE_SIZE ; number of pages per area (16)
MEMAREANUM	EQU	SYSTEM_SIZE/MEMAREASIZE; number of memory areas(32K)
MEMNUMCORR	EQU	SYSTEM_ADDR >> MEMAREASHIFT ; area number correction


struc		LIST

LIST_Next:	resd	1		; 0: pointer to next (first) entry
LIST_Prev:	resd	1		; 4: pointer to previous (last) entry

endstruc				; size 8 bytes

%define		LISTHEAD dd	$,$

; ------------- Macro - link two entries together (%1=1st entry, %2=2nd entry)

%macro		LINKLINK 2
		mov	[%1+LIST_Next],%2 ; link second entry after first one
		mov	[%2+LIST_Prev],%1 ; link first entry previous second
%endmacro


; ------------- Block descriptor

struc		BLOCK

		resb	LIST_size	; 0: chain of free memory blocks
BLOCK_Order:	resd	1		; 8: order of memory block
BLOCK_Size:	resd	1		; 0Ch: size of one memory block
BLOCK_Blocks:	resd	1		; 10h: number of blocks per one area
BLOCK_Last:	resd	1		; 14h: offset of last memory block
		resd	2		; 18h: ...reserved (for align)

endstruc				; size 32 bytes

BLOCKSIZE_BITS	EQU	5		; size of BLOCK in bits

; ------------- Initialized block descriptor (%1=order of block)

%macro		BLOCKHEAD 1

		LISTHEAD		; chain of free memory blocks
		dd	%1		; order of memory block
		dd	(1 << %1)	; size of one memory block
		dd	MEMAREASIZE / (1 << %1) ; number of blocks per one area
		dd	MEMAREASIZE - (1 << %1) ; offset of last memory block
		dd	0,0		; reserved (for align)
%endmacro

; ------------- DMA memory free block

struc		DMAMEM

		resb	LIST_size	; 0: list of DMA memory free blocks
DMAMEM_Size:	resd	1		; 8: size of DMA memory block (bytes)

endstruc				; size 12 bytes

; ------------- System memory lock

SysMemLock:	SPINLOCK

; ------------- Free areas

SysMemFreeArea:	LISTHEAD

; ------------- Table of memory blocks

		align	8, db 0
SysMemBlocks:
%assign BLOCKNUM MEMAREAMINSHIFT
%rep MEMAREASHIFT-MEMAREAMINSHIFT+1
		BLOCKHEAD BLOCKNUM	; block size 8 B to 64 KB (32 KB)
%assign BLOCKNUM BLOCKNUM+1
%endrep

SysMemAreas:	resb	MEMAREANUM	; size 32 KB
SysMemUsed:	resw	MEMAREANUM	; size 64 KB

Inicializace alokátoru systémové paměti se provádí na začátku startu jádra systému, brzy po inicializaci chráněného módu, funkcí SysMemInit. Funkce přebírá informace o obsazení paměti z bitové mapy PageMemMap, která bitem 1 indikuje volnou 4 KB stránku paměti. Bitová mapa je inicializovaná informacemi o paměti z BIOS. Kromě toho zahrnuje obsazené stránky jádra systému, mapovací tabulky stránek systémové paměti a tabulky popisovačů stránek paměti.


; ------------- Mark all areas as page-sized

		mov	edi,SysMemAreas	; EDI <- map of order of memory areas
		mov	eax,0c0c0c0ch	; all pages are 12-bits (= 4 KB)
		mov	ecx,MEMAREANUM/4 ; ECX <- size of map / 4
		rep	stosd		; initialize map

; ------------- Mark all pages as used

		mov	edi,SysMemUsed	; EDI <- counters of memory areas
		push	edi		; push EDI
		mov	eax,(MEMAREAPAGES<<16) + MEMAREAPAGES ; num. of pages
		mov	ecx,MEMAREANUM/2 ; ECX <- size of map / 2
		rep	stosd		; initialize counters
		pop	edi		; pop EDI (counters)

Na začátku funkce inicializuje pole mapy řádů úseků a pole čítačů použití bloků. Včechny řády jsou na staveny na hodnotu 12, což odpovídá blokům o velikosti 4 KB (tedy jedna stránka paměti). Čítače jsou nastaveny na maximální hodnotu odpovídající plně obsazeným úsekům s bloky 4 KB. Pro úsek 64 KB to odpovídá hodnotě 16.


; ------------- Prepare required DMA memory (-> EBP)

		mov	ebp,[TotalMemory] ; EBP <- total memory
		shr	ebp,7		; EBP <- required DMA memory size
		cmp	ebp,DMAMAXMEM	; overflow DMA maximal address?
		jbe	SysMemInit1	; not overflow
		mov	ebp,DMAMAXMEM	; EBP <- limit max. DMA memory size
SysMemInit1:	cmp	ebp,DMAMINMEM	; check minimal DMA buffer
		jae	SysMemInit12	; buffer is OK
		mov	ebp,DMAMINMEM	; EBP <- limit min. DMA memory size
SysMemInit12:	and	ebp,PAGE_MASK	; round down to pages

Do registru EBP je připravena požadovaná velikost DMA paměti, která má být rezervována. Během inicializace jsou stránky paměti přidělovány buď do oblasti DMA paměti nebo jako běžná paměť, v závislosti na hodnotě tohoto registru. Velikost požadované DMA paměti je zhruba 1% z celkové paměti v systému, hodnota je omezena maximální a minimální hranicí.


; ------------- Prepare pointers to regions (it uses EAX, ESI, EBP)

		mov	esi,PageMemMap	; ESI <- page memory map
		mov	eax,SYSTEM_ADDR	; EAX <- address of memory area

; ------------- Check if this area has any usable pages

SysMemInit2:	cmp	word [esi],byte 0 ; area has any free pages?
		je	SysMemInit8	; area has no free pages

; ------------- Check if this memory area is whole free

		cmp	word [esi],byte -1 ; is whole memory area free?
		jne	SysMemInit4	; whole memory area is not free

; ------------- Check if this area should be added to the DMA memory

		cmp	eax,DMAMAXMEM+SYSTEM_ADDR ; is it valid DMA address?
		jae	SysMemInit3	; it is not valid DMA memory
		cmp	ebp,PAGE_SIZE	; required any next DMA memory?
		jb	SysMemInit3	; no other DMA memory required
		mov	edx,MEMAREASIZE	; EDX <- size of memory area
		cmp	ebp,edx		; required whole DMA area?
		jb	SysMemInit4	; add this area per pages

; ------------- Add area into DMA memory

		sub	ebp,edx		; EBP <- decrease required memory
		xchg	eax,edx		; EDX <- address of area, EAX <- size
		call	DMAMemFree	; free DMA memory area
		xchg	eax,edx		; EAX <- address of area
		jmp	short SysMemInit8 ; next memory area

; ------------- Add whole area into free area chain

SysMemInit3:	mov	ebx,SysMemFreeArea ; free memory areas
		call	ListAdd		; free memory area
		and	word [edi],byte 0 ; all pages are free
		add	dword [TotalMemFree],MEMAREASIZE; increase total memory
		jmp	short SysMemInit8 ; next memory area

Nyní funkce prochází bitovou mapu zaplnění paměti PageMemMap a označuje volné bloky paměti. Inicializace po jednotlivých bitech a stránkách paměti by při velké paměti zabrala mnoho času a zpomalil by se tak náběh systému. Proto se, pokud možno, inicializuje paměť zrychleně, po celých úsecích. V bitové mapě odpovídá jednomu 64 KB úseku 1 slovo (2 bajty, 16 bitů, 16 stránek po 4 KB). Je-li obsah slova nulový, neobsahuje příslušný úsek ani jednu volnou stránku a je přeskočen. Jsou-li všechny bity úseku nastaveny, znamená to, že celý úsek je volný a může být zahrnut do volné paměti. Podle adresy úseku a podle čítače požadované velikosti DMA paměti je rozlišeno, zda úsek bude zahrnut do DMA paměti nebo do běžné paměti. Do DMA paměti je úsek přidán funkcí DMAMemFree. Do běžné paměti je úsek přidán zrychleně - je zahrnut přímo do seznamu volných úseků, jeho čítač použití bloků je vynulován a velikost bloku je přidána k ukazateli volné paměti TotalMemFree.


; ------------- Prepare to free single pages

SysMemInit4:    xor	ecx,ecx		; ECX <- 0
		inc	ecx		; ECX <- B0, bit mask
		push	eax		; push EAX

; ------------- Check if this page is available

SysMemInit5:	test	[esi],cx	; is this page available?
		jz	SysMemInit7	; this page is not available

; ------------- Free this page as DMA memory

		cmp	eax,DMAMAXMEM+SYSTEM_ADDR ; is it valid DMA address?
		jae	SysMemInit6	; it is not valid DMA memory
		mov	edx,PAGE_SIZE	; EDX <- page size
		cmp	ebp,edx		; required next page?
		jb	SysMemInit6	; no other DMA required
		sub	ebp,edx		; decrease DMA counter
		xchg	eax,edx		; EDX <- address of page, EAX <- size
		call	DMAMemFree	; free DMA page
		xchg	eax,edx		; EAX <- address of page
		jmp	short SysMemInit7 ; next page

; ------------- Free this page

SysMemInit6:	push	eax		; push EAX
		call	SysMemFree	; free this memory page
		pop	eax		; pop EAX

; ------------- Next page

SysMemInit7:    add	eax,PAGE_SIZE	; EAX <- increase page address
		shl	cx,1		; rotate mask
		jnc	SysMemInit5	; next memory page
		pop	eax		; pop EAX

Nelze-li inicializovat úsek paměti zrychleně (tj. obsahuje obsazené i volné stránky), je inicializován po jednotlivých stránkách. Postupným testováním slova z bitové mapy je rozlišeno, zda je příslušná stránka volná. Pokud ano (tj. bit je nastaven na 1), je stránka zařazena do volných bloků pomocí funkcí DMAMemFree nebo SysMemFree, podle adresy a čítače velikosti DMA paměti.


; ------------- Next memory area

SysMemInit8:	add	esi,byte (1<< (MEMAREASHIFT-15)) ; ESI <- increase map
		add	eax,MEMAREASIZE	; EAX <- increase memory area address
		inc	edi
		inc	edi		; EDI <- next counter of memory area
		cmp	edi,SysMemUsed+MEMAREANUM*2 ; end of memory?
		jb	SysMemInit2	; initialize next memory area

Po zahrnutí všech stránek z jednoho slova bitové mapy pokračuje funkce dalším slovem, až po konec systémové paměti.


; ------------- Check if this page is available

		xor	ecx,ecx		; ECX <- 0
SysMemInit5:	bt	dword [esi],ecx	; is this page available?
		jnc	SysMemInit7	; this page is not available

; ------------- Free this page as DMA memory

		cmp	eax,DMAMAXMEM+SYSTEM_ADDR ; is it valid DMA address?
		jae	SysMemInit6	; it is not valid DMA memory
		mov	edx,PAGE_SIZE	; EDX <- page size
		cmp	ebp,edx		; required next page?
		jb	SysMemInit6	; no other DMA required
		sub	ebp,edx		; decrease DMA counter
		xchg	eax,edx		; EDX <- address of page, EAX <- size
		call	DMAMemFree	; free DMA page
		xchg	eax,edx		; EAX <- address of page
		jmp	short SysMemInit7 ; next page

; ------------- Free this page

SysMemInit6:	push	eax		; push EAX
		call	SysMemFree	; free this memory page
		pop	eax		; pop EAX

; ------------- Next page

SysMemInit7:    add	eax,PAGE_SIZE	; EAX <- increase page address
		inc	ecx		; increase bit counter
		cmp	ecx,PAGE_MAX	; end of memory?
		jbe	SysMemInit5	; next page

Není-li při překladu jádra systému použit řád velikosti úseku paměti MEMAREASHIFT v rozsahu 16 až 17, nelze použít zrychlenou inicializaci paměti a použije se funkce pracující pouze se stránkami paměti. Tato funkce pracuje pomalu, což se může projevit pomalejším startem systému.


; ------------- Free memory bit map

		mov	eax,PageMemMap	; EAX <- memory map buffer
		mov	ecx,(SYSTEM_SIZE/PAGE_SIZE/8+PAGE_SIZE-1)/PAGE_SIZE
		mov	edx,PAGE_SIZE	; EDX <- page size
SysMemInit9:	cmp	ebp,edx		; required next DMA page?
		jb	SysMemInit92	; no other DMA memory required
		sub	ebp,edx		; decrease DMA counter
		xchg	eax,edx		; EDX <- address of page, EAX <- size
		call	DMAMemFree	; free DMA page
		xchg	eax,edx		; EAX <- address of page, EDX <- size
		jmp	short SysMemInit94

SysMemInit92:	push	eax		; push EAX
		call	SysMemFree	; free this memory page
		pop	eax		; pop EAX
 
SysMemInit94:	add	eax,edx		; EAX <- address of next page
		loop	SysMemInit9	; next page

; ------------- Total DMA memory

SysMemInit95:	mov	eax,[TotalDMAMemFree] ; EAX <- free DMA memory
		mov	[TotalDMAMemory],eax ; total DMA memory
		ret

Po dokončení inicializace alokátoru paměti není již nadále potřebná bitová mapa zaplnění stránek paměti (zabírající 64 KB paměti) a může být uvolněna a zahrnuta do volných bloků paměti. Uvolnění proběhne obdobně jako v předešlých případech.

Alokace (přidělení) bloku systémové paměti je zajištěno funkcí SysMemAlloc. Vstupními parametry funkce je požadovaná velikost bloku paměti, předávaná v registru EAX. Maximální velikost bloku systémové paměti odpovídá velikosti úseku paměti, tedy 64 KB. Je-li blok úspěšně alokován, je jeho adresa navrácena v registru EAX a příznak CF je vynulován. V případě chyby je příznak CF nastaven a registr EAX obsahuje nulu. Velikost přiděleného paměťového bloku je zaokrouhlena na nejbližší vyšší mocninu 2 a adresa bloku je zarovnána podle velikosti bloku. Pro bloky menší než 8 bajtů je přidělen blok o velikosti 8 bajtů.


; ------------- Push registers

		push	ebx		; push EBX
		push	ecx		; push ECX
		pushf			; push flags
		cli			; disable interrupts

; ------------- Lock access to system memory allocator

		mov	ebx,SysMemLock	; system memory lock
		LOCK_Lock ebx		; lock system memory allocator

; ------------- Minimal size of memory block (8 bytes is size of LINK entry)

		cmp	eax,byte MEMMINBLOCK ; minimal size of memory block
		jae	short SysMemAlloc2 ; memory block size is OK
		mov	al,MEMMINBLOCK	; EAX <- minimal size of memory block

V přípravné fázi funkce jsou uchovány některé registry, uchován registr příznaků a zakázáno přerušení a uzamknut přístup k alokátoru paměti. Velikost požadované velikosti bloku je omezen na minimální velikost (8 bajtů).


; ------------- Transfer size of memory block to its order

SysMemAlloc2:	dec	eax		; EAX <- block size - 1
		bsr	eax,eax		; find order of memory block - 1
		cmp	al,MEMAREASHIFT ; maximal order of memory block
		jae	short SysMemAlloc4 ; invalid size of memory block

; ------------- Prepare pointer to block descriptor (-> EBX)

		shl	eax,BLOCKSIZE_BITS ; (order of memory block-1) * 32
		lea	ebx,[SysMemBlocks+eax-(MEMAREAMINSHIFT-1)*BLOCK_size]

Následuje převod velikosti bloku na řád. K tomu je využita instrukce BSR, která vyhledává pozici nejvyššího bitu 1 v registru. Zjištěná hodnota odpovídá řádu velikosti bloku - 1. Po kontrole překročení velikosti bloku je připravena adresa odpovídajícího seznamu volných bloků.


; ------------- Check if any free memory block is available

SysMemAlloc3:	mov	eax,[ebx+LIST_Next] ; first free memory block
		cmp	eax,ebx		; is it valid memory block?
		je	short SysMemAlloc6 ; it is not valid memory block

; ------------- Detach block from free memory block chain

		LISTDELPREV eax,ebx,ecx	; detach block

; ------------- Increase used counter

		mov	ecx,eax		; ECX <- address of memory block
		shr	ecx,MEMAREASHIFT ; ECX <- memory area number
		inc 	word [SysMemUsed+ecx*2-MEMNUMCORR*2] ; increase counter

; ------------- Unlock access to system memory allocator

		LOCK_Unlock SysMemLock	; unlock system memory allocator

; ------------- Pop registers (and clear error flag)

		popf			; pop flags
		clc			; clear error flag
		pop	ecx		; pop ECX
		pop	ebx		; pop EBX
		ret

Seznam volných bloků je zkontrolován, zda obsahuje volný blok paměti. Pokud ano, je blok vyjmut ze seznamu, zvýšen čítač použití bloků v úseku, odemknut zámek přístupu k paměťovému alokátoru, navráceny registry a funkce je ukončena.


; ------------- Error - insufficient memory

SysMemAlloc4:	xor	eax,eax		; EAX <- 0, invalid pointer

; ------------- Unlock access to system memory allocator (it saves CF)
%ifdef	SMP
		LOCK_Unlock SysMemLock	; unlock system memory allocator
%endif
; ------------- Pop registers (and set error flag)

		popf			; pop flags
		stc			; set error flag
		pop	ecx		; pop ECX
		pop	ebx		; pop EBX
		ret

; ------------- Get next free memory area

SysMemAlloc6:	mov	ecx,SysMemFreeArea ; free memory areas
		mov	eax,[ecx+LIST_Next] ; EAX <- next memory area
		cmp	eax,ecx		; is any area available?
		je	short SysMemAlloc4 ; there is no area available

; ------------- Push registers 2

		push	edx		; push EDX
		push	esi		; push ESI
			
; ------------- Detach memory area from the list

		LISTDELPREV eax,ecx,edx	; detach memory area from the list

; ------------- Decrease free memory counter

		sub	dword [TotalMemFree],MEMAREASIZE

; ------------- Set order to the map

		mov	edx,eax		; EDX <- address of the area
		shr	edx,MEMAREASHIFT ; EDX <- memory area number
		mov	cl,[ebx+BLOCK_Order] ; CL <- order of memory block
		mov	[SysMemAreas+edx-MEMNUMCORR],cl ; store order of area

Není-li k dospozici odpovídající volný blok paměti, je nutno alokovat nový úsek paměti. Není-li úsek nalezen v seznamu volných úseků, navrátí se funkce s chybou. Je-li úsek k dispozici, uvolní se ze seznamu volných úseků, sníží se ukazatel volné paměti a uschová se řád velikosti bloku. Ten bude potřeba během uvolňování paměťového bloku ke zjištění řádu bloku.


; ------------- Link first block to the head

		LINKLINK ebx,eax	; link EAX after EBX

; ------------- Prepare registers to initialize memory blocks

		mov	ecx,[ebx+BLOCK_Blocks] ; ECX <- number of blocks
		dec	ecx		; without one block
		jz	short SysMemAlloc8 ; only one block is used
		mov	esi,[ebx+BLOCK_Size] ; ESI <- size of a block

; ------------- Initialize chain of memory blocks

SysMemAlloc7:	lea	edx,[eax+esi]	; EDX <- address of next memory block
		LINKLINK eax,edx	; link EDX after EAX
		xchg	eax,edx		; EAX <- next block
		loop	SysMemAlloc7	; next memory block

; ------------- Link last block to the head

SysMemAlloc8:	LINKLINK eax,ebx	; link EBX after EAX

; ------------- Pop registers 2

		pop	esi		; pop ESI
		pop	edx		; pop EDX
		jmp	near SysMemAlloc3 ; get new entry

Nyní je potřeba rozdělit úsek na samostatné paměťové bloky a zařadit je do seznamu volných bloků. Pro zrychlení jsou bloky napojovány do seznamu žetězcově, pouze v jednom směru. Nejdříve je k záhlaví seznamu napojen první blok, který odpovídá adrese začátku úseku. V cyklu jsou postupně s rostoucí adresou napojovány další bloky. Na závěr je poslední z bloků připojen k záhlaví seznamu bloků a funkce pokračuje opětovnou alokací bloku paměti.

Dealokace (uvolnění) bloku systémové paměti zajišťuje funkce SysMemFree. Vstupním parametrem funkce je adresa uvolňovaného bloku paměti v registru EAX, ale může se jednat i o hodnotu 0. Lze uvolnit pouze bloky přidělené funkcí SysMemAlloc (výjimkou jsou stránky paměti během inicializace systému), adresa bloku paměti není nijak kontrolována vyjma hodnoty 0. Po uvolnění bloku paměti již nesmí být proveden žádný zápis do bloku. Z toho důvodu funkce navrací v registru EAX hodnotu 0, kterou ruší adresu bloku předávanou funkci.


; ------------- Check if it is NULL pointer

		or	eax,eax		; is it NULL pointer?
		jz	short SysMemFree9 ; it is NULL pointer

; ------------- Push registers

		push	ebx		; push EBX
		push	ecx		; push ECX
		push	edx		; push EDX
		pushf			; push flags
		cli			; disable interrupts

; ------------- Lock access to system memory allocator

		mov	ebx,SysMemLock	; system memory lock
		LOCK_Lock ebx		; lock system memory allocator

Na začátku funkce je nejdříve zkontrolováno, zda adresa bloku není nula, tato hodnota se ignoruje. Následuje úschova některých registrů a uzamknutí přístup k alokátoru paměti.


; ------------- Memory area number (-> EDX)

		mov	edx,eax		; EDX <- address of memory block
		shr	edx,MEMAREASHIFT ; EDX <- memory area number

; ------------- Pointer to block descriptor (-> EBX)

		movzx	ebx,byte [SysMemAreas+edx-MEMNUMCORR] ; order
		shl	ebx,BLOCKSIZE_BITS ; EBX * 32, offset of descriptor
		add	ebx,SysMemBlocks - MEMAREAMINSHIFT*BLOCK_size

; ------------- Attach memory block to block descriptor

		LISTADD	ebx,eax,ecx	; attach block to descriptor

; ------------- Decrease counter of used blocks

		dec 	word [SysMemUsed+edx*2-MEMNUMCORR*2] ; decrease counter
		jnz	short SysMemFree8 ; area is not free

Zarovnáním adresy bloku na velikost úseku paměti je odvozen index úseku. Ten je použit ke zjištění řádu bloku. Blok je zařazen do seznamu volných bloků a je dekrementován počet použitých bloků úseku paměti. Pokud čítač použitých bloků nedosáhl nuly, funkce je ukončena.


; ------------- Push registers 2

		push	esi		; push ESI

; ------------- Free block in this memory area

		and	eax,MEMAREAMASK	; mask memory area
		push	eax		; push EAX (address of memory area)
		mov	ecx,[ebx+BLOCK_Blocks] ; ECX <- number of blocks
		mov	esi,[ebx+BLOCK_Size] ; ESI <- size of a block
SysMemFree4:	LISTDEL	eax,ebx,edx	; detach memory block
		add	eax,esi		; EAX <- next memory block
		loop	SysMemFree4	; next memory block
		pop	eax		; pop EAX (address of memory area)

; ------------- Free memory area

		mov	ebx,SysMemFreeArea ; free memory areas
		LISTADD ebx,eax,ecx	; free memory area

; ------------- Increase free memory counter

		add	dword [TotalMemFree],MEMAREASIZE ; increase free memory

; ------------- Pop registers 2

		pop	esi		; pop ESI

; ------------- Unlock access to system memory allocator

SysMemFree8:

		LOCK_Unlock SysMemLock	; unlock system memory allocator

; ------------- Pop registers

		popf			; pop flags
		pop	edx		; pop EDX
		pop	ecx		; pop ECX
		pop	ebx		; pop EBX
		xor	eax,eax		; EAX <- 0, invalid pointer
		ret

Pokud čítač dosáhl nuly, bude celý úsek uvolněn. Nejdříve jsou ze seznamu volných bloků vyjmuty všechny bloky, které do úseku patří. Poté je úsek paměti zařazen do seznamu volných úseků, zvýšen ukazatel volné paměti, odemknut přístup k alokátoru paměti a navráceny registry.