WebSVN – Kolibri OS – Diff – /kernel/trunk/core/slab.inc


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;                                                              ;;
;; Copyright (C) KolibriOS team 2013-2022. All rights reserved. ;;
;; Distributed under terms of the GNU General Public License    ;;
;;                                                              ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
$Revision: 9715 $
 
; Memory management for slab structures.
; The allocator meets special requirements:
; * memory blocks are properly aligned
; * memory blocks do not cross page boundary
; The allocator manages fixed-size blocks.
; Thus, the specific allocator works as follows:
; allocate one page, split into blocks, maintain the single-linked
; list of all free blocks in each page.
 
; Note: size must be a multiple of required alignment.
 
; Data for one pool: dd pointer to the first page, MUTEX lock.
 
; Allocator for fixed-size blocks: allocate a block.
; [ebx-4] = pointer to the first page, ebx = pointer to MUTEX structure.
proc slab_alloc
        push    edi     ; save used register to be stdcall
virtual at esp
        dd      ?       ; saved edi
        dd      ?       ; return address
.size   dd      ?
end virtual
; 1. Take the lock.
        mov     ecx, ebx
        call    mutex_lock
; 2. Find the first allocated page with a free block, if any.
; 2a. Initialize for the loop.
        mov     edx, ebx
.pageloop:
; 2b. Get the next page, keeping the current in eax.
        mov     eax, edx
        mov     edx, [edx-4]
; 2c. If there is no next page, we're out of luck; go to 4.
        test    edx, edx
        jz      .newpage
        add     edx, 0x1000
@@:
; 2d. Get the pointer to the first free block on this page.
; If there is no free block, continue to 2b.
        mov     eax, [edx-8]
        test    eax, eax
        jz      .pageloop
; 2e. Get the pointer to the next free block.
        mov     ecx, [eax]
; 2f. Update the pointer to the first free block from eax to ecx.
; Normally [edx-8] still contains eax, if so, atomically set it to ecx
; and proceed to 3.
; However, the price of simplicity of slab_free (in particular, it doesn't take
; the lock) is that [edx-8] could (rarely) be changed while we processed steps
; 2d+2e. If so, return to 2d and retry.
        lock cmpxchg [edx-8], ecx
        jnz     @b
.return:
; 3. Release the lock taken in step 1 and return.
        push    eax
        mov     ecx, ebx
        call    mutex_unlock
        pop     eax
        pop     edi     ; restore used register to be stdcall
        ret     4
.newpage:
; 4. Allocate a new page.
        push    eax
        stdcall kernel_alloc, 0x1000
        pop     edx
; If failed, say something to the debug board and return zero.
        test    eax, eax
        jz      .nomemory
; 5. Add the new page to the tail of list of allocated pages.
        mov     [edx-4], eax
; 6. Initialize two service dwords in the end of page:
; first free block is (start of page) + (block size)
; (we will return first block at (start of page), so consider it allocated),
; no next page.
        mov     edx, eax
        lea     edi, [eax+0x1000-8]
        add     edx, [.size]
        mov     [edi], edx
        and     dword [edi+4], 0
; 7. All blocks starting from edx are free; join them in a single-linked list.
@@:
        mov     ecx, edx
        add     edx, [.size]
        mov     [ecx], edx
        cmp     edx, edi
        jbe     @b
        sub     ecx, [.size]
        and     dword [ecx], 0
; 8. Return (start of page).
        jmp     .return
.nomemory:
        dbgstr 'no memory for slab allocation'
        xor     eax, eax
        jmp     .return
endp
 
; Allocator for fixed-size blocks: free a block.
proc slab_free
        push    ecx edx
virtual at esp
        rd      2       ; saved registers
        dd      ?       ; return address
.block  dd      ?
end virtual
; Insert the given block to the head of free blocks in this page.
        mov     ecx, [.block]
        mov     edx, ecx
        or      edx, 0xFFF
@@:
        mov     eax, [edx+1-8]
        mov     [ecx], eax
        lock cmpxchg [edx+1-8], ecx
        jnz     @b
        pop     edx ecx
        ret     4
endp

Rev 8037	Rev 9715
1	;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;	1	;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
2	;; ;;	2	;; ;;
3	;; Copyright (C) KolibriOS team 2013-2015. All rights reserved. ;;	3	;; Copyright (C) KolibriOS team 2013-2022. All rights reserved. ;;
4	;; Distributed under terms of the GNU General Public License ;;	4	;; Distributed under terms of the GNU General Public License ;;
5	;; ;;	5	;; ;;
6	;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;	6	;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
7		7
8	$Revision: 8037 $	8	$Revision: 9715 $
9		9
10	; Memory management for slab structures.	10	; Memory management for slab structures.
11	; The allocator meets special requirements:	11	; The allocator meets special requirements:
12	; * memory blocks are properly aligned	12	; * memory blocks are properly aligned
13	; * memory blocks do not cross page boundary	13	; * memory blocks do not cross page boundary
14	; The allocator manages fixed-size blocks.	14	; The allocator manages fixed-size blocks.
15	; Thus, the specific allocator works as follows:	15	; Thus, the specific allocator works as follows:
16	; allocate one page, split into blocks, maintain the single-linked	16	; allocate one page, split into blocks, maintain the single-linked
17	; list of all free blocks in each page.	17	; list of all free blocks in each page.
18		18
19	; Note: size must be a multiple of required alignment.	19	; Note: size must be a multiple of required alignment.
20		20
21	; Data for one pool: dd pointer to the first page, MUTEX lock.	21	; Data for one pool: dd pointer to the first page, MUTEX lock.
22		22
23	; Allocator for fixed-size blocks: allocate a block.	23	; Allocator for fixed-size blocks: allocate a block.
24	; [ebx-4] = pointer to the first page, ebx = pointer to MUTEX structure.	24	; [ebx-4] = pointer to the first page, ebx = pointer to MUTEX structure.
25	proc slab_alloc	25	proc slab_alloc
26	push edi ; save used register to be stdcall	26	push edi ; save used register to be stdcall
27	virtual at esp	27	virtual at esp
28	dd ? ; saved edi	28	dd ? ; saved edi
29	dd ? ; return address	29	dd ? ; return address
30	.size dd ?	30	.size dd ?
31	end virtual	31	end virtual
32	; 1. Take the lock.	32	; 1. Take the lock.
33	mov ecx, ebx	33	mov ecx, ebx
34	call mutex_lock	34	call mutex_lock
35	; 2. Find the first allocated page with a free block, if any.	35	; 2. Find the first allocated page with a free block, if any.
36	; 2a. Initialize for the loop.	36	; 2a. Initialize for the loop.
37	mov edx, ebx	37	mov edx, ebx
38	.pageloop:	38	.pageloop:
39	; 2b. Get the next page, keeping the current in eax.	39	; 2b. Get the next page, keeping the current in eax.
40	mov eax, edx	40	mov eax, edx
41	mov edx, [edx-4]	41	mov edx, [edx-4]
42	; 2c. If there is no next page, we're out of luck; go to 4.	42	; 2c. If there is no next page, we're out of luck; go to 4.
43	test edx, edx	43	test edx, edx
44	jz .newpage	44	jz .newpage
45	add edx, 0x1000	45	add edx, 0x1000
46	@@:	46	@@:
47	; 2d. Get the pointer to the first free block on this page.	47	; 2d. Get the pointer to the first free block on this page.
48	; If there is no free block, continue to 2b.	48	; If there is no free block, continue to 2b.
49	mov eax, [edx-8]	49	mov eax, [edx-8]
50	test eax, eax	50	test eax, eax
51	jz .pageloop	51	jz .pageloop
52	; 2e. Get the pointer to the next free block.	52	; 2e. Get the pointer to the next free block.
53	mov ecx, [eax]	53	mov ecx, [eax]
54	; 2f. Update the pointer to the first free block from eax to ecx.	54	; 2f. Update the pointer to the first free block from eax to ecx.
55	; Normally [edx-8] still contains eax, if so, atomically set it to ecx	55	; Normally [edx-8] still contains eax, if so, atomically set it to ecx
56	; and proceed to 3.	56	; and proceed to 3.
57	; However, the price of simplicity of slab_free (in particular, it doesn't take	57	; However, the price of simplicity of slab_free (in particular, it doesn't take
58	; the lock) is that [edx-8] could (rarely) be changed while we processed steps	58	; the lock) is that [edx-8] could (rarely) be changed while we processed steps
59	; 2d+2e. If so, return to 2d and retry.	59	; 2d+2e. If so, return to 2d and retry.
60	lock cmpxchg [edx-8], ecx	60	lock cmpxchg [edx-8], ecx
61	jnz @b	61	jnz @b
62	.return:	62	.return:
63	; 3. Release the lock taken in step 1 and return.	63	; 3. Release the lock taken in step 1 and return.
64	push eax	64	push eax
65	mov ecx, ebx	65	mov ecx, ebx
66	call mutex_unlock	66	call mutex_unlock
67	pop eax	67	pop eax
68	pop edi ; restore used register to be stdcall	68	pop edi ; restore used register to be stdcall
69	ret 4	69	ret 4
70	.newpage:	70	.newpage:
71	; 4. Allocate a new page.	71	; 4. Allocate a new page.
72	push eax	72	push eax
73	stdcall kernel_alloc, 0x1000	73	stdcall kernel_alloc, 0x1000
74	pop edx	74	pop edx
75	; If failed, say something to the debug board and return zero.	75	; If failed, say something to the debug board and return zero.
76	test eax, eax	76	test eax, eax
77	jz .nomemory	77	jz .nomemory
78	; 5. Add the new page to the tail of list of allocated pages.	78	; 5. Add the new page to the tail of list of allocated pages.
79	mov [edx-4], eax	79	mov [edx-4], eax
80	; 6. Initialize two service dwords in the end of page:	80	; 6. Initialize two service dwords in the end of page:
81	; first free block is (start of page) + (block size)	81	; first free block is (start of page) + (block size)
82	; (we will return first block at (start of page), so consider it allocated),	82	; (we will return first block at (start of page), so consider it allocated),
83	; no next page.	83	; no next page.
84	mov edx, eax	84	mov edx, eax
85	lea edi, [eax+0x1000-8]	85	lea edi, [eax+0x1000-8]
86	add edx, [.size]	86	add edx, [.size]
87	mov [edi], edx	87	mov [edi], edx
88	and dword [edi+4], 0	88	and dword [edi+4], 0
89	; 7. All blocks starting from edx are free; join them in a single-linked list.	89	; 7. All blocks starting from edx are free; join them in a single-linked list.
90	@@:	90	@@:
91	mov ecx, edx	91	mov ecx, edx
92	add edx, [.size]	92	add edx, [.size]
93	mov [ecx], edx	93	mov [ecx], edx
94	cmp edx, edi	94	cmp edx, edi
95	jbe @b	95	jbe @b
96	sub ecx, [.size]	96	sub ecx, [.size]
97	and dword [ecx], 0	97	and dword [ecx], 0
98	; 8. Return (start of page).	98	; 8. Return (start of page).
99	jmp .return	99	jmp .return
100	.nomemory:	100	.nomemory:
101	dbgstr 'no memory for slab allocation'	101	dbgstr 'no memory for slab allocation'
102	xor eax, eax	102	xor eax, eax
103	jmp .return	103	jmp .return
104	endp	104	endp
105		105
106	; Allocator for fixed-size blocks: free a block.	106	; Allocator for fixed-size blocks: free a block.
107	proc slab_free	107	proc slab_free
108	push ecx edx	108	push ecx edx
109	virtual at esp	109	virtual at esp
110	rd 2 ; saved registers	110	rd 2 ; saved registers
111	dd ? ; return address	111	dd ? ; return address
112	.block dd ?	112	.block dd ?
113	end virtual	113	end virtual
114	; Insert the given block to the head of free blocks in this page.	114	; Insert the given block to the head of free blocks in this page.
115	mov ecx, [.block]	115	mov ecx, [.block]
116	mov edx, ecx	116	mov edx, ecx
117	or edx, 0xFFF	117	or edx, 0xFFF
118	@@:	118	@@:
119	mov eax, [edx+1-8]	119	mov eax, [edx+1-8]
120	mov [ecx], eax	120	mov [ecx], eax
121	lock cmpxchg [edx+1-8], ecx	121	lock cmpxchg [edx+1-8], ecx
122	jnz @b	122	jnz @b
123	pop edx ecx	123	pop edx ecx
124	ret 4	124	ret 4
125	endp	125	endp

Subversion Repositories Kolibri OS

(root)/kernel/trunk/core/slab.inc – Rev 8037 → 9715