WebSVN – Kolibri OS – Diff – /kernel/branches/flat_kernel/core/malloc.inc


; Small heap based on malloc/free/realloc written by Doug Lea
; Version 2.8.3 Thu Sep 22 11:16:15 2005  Doug Lea  (dl at gee)
; Source ftp://gee.cs.oswego.edu/pub/misc/malloc.c
; License http://creativecommons.org/licenses/publicdomain.
 
 
; eax= size
 
; temp
;  esi= nb
;  ebx= idx
;
malloc:
           push esi
 
; nb = ((size+7)&~7)+8;
 
           mov esi, eax    ;size
           add esi, 7
           and esi, -8
           add esi, 8
 
           mov ebx, mst.mutex
           call wait_mutex    ;ebx
 
           cmp esi, 256
           jae .large
 
           mov ecx, esi
           shr ecx, 3
           or eax, -1
           shl eax, cl
           and eax, [mst.smallmap]
           jz .small
 
           push ebp
           push edi
 
           bsf eax, eax
           mov ebx, eax
 
; psize= idx<<3;
; B = &ms.smallbins[idx];
; p = B->fd;
; F = p->fd;
; rsize= psize-nb;
 
           lea ebp, [eax*8]               ;ebp= psize
           shl eax, 4
           lea edi, [mst.smallbins+eax]   ;edi= B
           mov edx, [edi+8]               ;edx= p
           mov eax, [edx+8]               ;eax= F
           mov ecx, ebp
           sub ecx, esi                   ;ecx= rsize
 
; if (B == F)
           cmp edi, eax
           jne @F
 
           btr [mst.smallmap], ebx
@@:
 
; B->fd = F;
; F->bk = B;
; if(rsize<16)
 
           cmp ecx, 16
           mov [edi+8], eax
           mov [eax+12], edi
           jae .split
 
; p->head = psize|PINUSE_BIT|CINUSE_BIT;
; (p + psize)->head |= PINUSE_BIT;
 
           lea eax, [edx+8]
           or dword [edx+ebp+4], 1
 
           or ebp, 3
           mov [edx+4], ebp
 
           pop edi
           pop ebp
.done:
           pop esi
           mov [mst.mutex], 0
           ret
.split:
           lea ebx, [edx+8]               ;ebx=mem
 
; r = chunk_plus_offset(p, nb);
; p->head = nb|PINUSE_BIT|CINUSE_BIT;
; r->head = rsize|PINUSE_BIT;
 
           lea eax, [edx+esi]             ;eax= r
           or esi, 3
           mov [edx+4], esi
 
           mov edx, ecx
           or edx, 1
           mov [eax+4], edx
 
; (r + rsize)->prev_foot = rsize;
 
           mov [eax+ecx], ecx
 
; I  = rsize>>3;
 
           shr ecx, 3
 
;      ms.smallmap |=  1<< I;
           bts [mst.smallmap], ecx
 
; B = &ms.smallbins[I];
 
           shl ecx, 4
           pop edi
           pop ebp
           add ecx, mst.smallbins         ;ecx= B
 
           mov edx, [ecx+8]               ; F = B->fd;
           mov [ecx+8], eax               ; B->fd = r;
           mov [edx+12], eax              ; F->bk = r;
           mov [eax+8], edx               ; r->fd = F;
           mov [eax+12], ecx              ; r->bk = B;
           mov eax, ebx
           pop esi
           ret
.small:
 
; if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)
 
           cmp [mst.treemap], 0
           je .from_top
           mov eax, esi
           call malloc_small
           test eax, eax
           jz .from_top
           pop esi
           and [mst.mutex], 0
           ret
.large:
 
; if (ms.treemap != 0 && (mem = malloc_large(nb)) != 0)
 
           cmp [mst.treemap], 0
           je .from_top
 
           call malloc_large  ;esi= nb
           test eax, eax
           jne .done
.from_top:
 
; if (nb < ms.topsize)
 
           mov eax, [mst.topsize]
           cmp esi, eax
           jae .fail
 
; rsize = ms.topsize -= nb;
; p = ms.top;
 
           mov ecx, [mst.top]
           sub eax, esi
           mov [mst.topsize], eax
 
; r = ms.top = chunk_plus_offset(p, nb);
; r->head = rsize | PINUSE_BIT;
; p->head = nb |PINUSE_BIT|CINUSE_BIT;
 
           lea edx, [ecx+esi]
           or eax, 1
           mov [mst.top], edx
           or esi, 3
           mov [edx+4], eax
           mov [ecx+4], esi
           lea eax, [ecx+8]
           pop esi
           and [mst.mutex], 0
           ret
.fail:
           xor eax, eax
           pop esi
           and [mst.mutex], 0
           ret
 
; param
;  eax= mem
 
align 4
free:
           push edi
           mov edi, eax
           add edi, -8
 
; if(p->head & CINUSE_BIT)
 
           test byte [edi+4], 2
           je .fail
 
           mov ebx, mst.mutex
           call wait_mutex    ;ebx
 
; psize = p->head & (~3);
 
           mov eax, [edi+4]
           push esi
           mov esi, eax
           and esi, -4
 
; next = chunk_plus_offset(p, psize);
; if(!(p->head & PINUSE_BIT))
 
           test al, 1
           lea ebx, [esi+edi]
           jne .next
 
; prevsize = p->prev_foot;
; prev=p - prevsize;
; psize += prevsize;
; p = prev;
 
           mov ecx, [edi]  ;ecx= prevsize
           add esi, ecx              ;esi= psize
           sub edi, ecx              ;edi= p
 
; if (prevsize < 256)
 
           cmp ecx, 256
           jae .unlink_large
 
           mov eax, [edi+8]          ;F = p->fd;
           mov edx, [edi+12]         ;B = p->bk;
 
; if (F == B)
; ms.smallmap &=  ~(1<< I);
           shr ecx, 3
           cmp eax, edx
           jne @F
           and [mst.smallmap], ecx
@@:
           mov [eax+12], edx           ;F->bk = B;
           mov [edx+8], eax            ;B->fd = F
           jmp .next
.unlink_large:
           mov edx, edi
           call unlink_large_chunk
.next:
 
; if(next->head & PINUSE_BIT)
 
           mov eax, [ebx+4]
           test al, 1
           jz .fail2
 
; if (! (next->head & CINUSE_BIT))
 
           test al, 2
           jnz .fix_next
 
; if (next == ms.top)
 
           cmp ebx, [mst.top]
           jne @F
 
; tsize = ms.topsize += psize;
 
           mov eax, [mst.topsize]
           add eax, esi
           mov [mst.topsize], eax
 
; ms.top = p;
; p->head = tsize | PINUSE_BIT;
 
           or eax, 1
           mov [mst.top], edi
           mov [edi+4], eax
.fail2:
           and [mst.mutex], 0
           pop esi
.fail:
           pop edi
           ret
@@:
 
; nsize = next->head & ~INUSE_BITS;
 
           and eax, -4
           add esi, eax                ;psize += nsize;
 
; if (nsize < 256)
 
           cmp eax, 256
           jae .unl_large
 
           mov edx, [ebx+8]            ;F = next->fd
           mov ebx, [ebx+12]           ;B = next->bk
 
; if (F == B)
 
           cmp edx, ebx
           jne @F
           mov ecx, eax
           shr ecx, 3
           btr [mst.smallmap], ecx
@@:
           mov [edx+12], ebx           ;F->bk = B
 
; p->head = psize|PINUSE_BIT;
 
           mov ecx, esi
           mov [ebx+8], edx
           or ecx, 1
           mov [edi+4], ecx
 
; (p+psize)->prev_foot = psize;
 
           mov [esi+edi], esi
 
; insert_chunk(p,psize);
 
           mov eax, esi
           pop esi
           mov ecx, edi
           pop edi
           jmp insert_chunk
.unl_large:
 
; unlink_large_chunk((tchunkptr)next);
 
           mov edx, ebx
           call unlink_large_chunk
; p->head = psize|PINUSE_BIT;
 
           mov ecx, esi
           or ecx, 1
           mov [edi+4], ecx
 
; (p+psize)->prev_foot = psize;
 
           mov [esi+edi], esi
 
; insert_chunk(p,psize);
 
           mov eax, esi
           pop esi
           mov ecx, edi
           pop edi
           jmp insert_chunk
.fix_next:
 
; (p+psize)->prev_foot = psize;
; next->head &= ~PINUSE_BIT;
; p->head = psize|PINUSE_BIT;
 
           and eax, -2
           mov edx, esi
           mov [ebx+4], eax
           or edx, 1
           mov [edi+4], edx
 
; (p+psize)->prev_foot = psize;
 
           mov [esi+edi], esi
; insert_chunk(p,psize);
 
           mov eax, esi
           pop esi
           mov ecx, edi
           pop edi
           jmp insert_chunk
 
; param
;  ecx = chunk
;  eax = size
 
align 4
insert_chunk:
 
           cmp eax, 256
           push esi
           mov esi, ecx
           jae .large
 
; I  = S>>3;
; ms.smallmap |=  1<< I;
 
           shr eax, 3
           bts [mst.smallmap], eax
 
; B = &ms.smallbins[I];
 
           shl eax, 4
           add eax, mst.smallbins
           mov edx, [eax+8]            ;F = B->fd
           mov [eax+8], esi            ;B->fd = P
           mov [edx+12], esi           ;F->bk = P
           mov [esi+8], edx            ;P->fd = F
           mov [esi+12], eax           ;P->bk = B
           pop esi
           and [mst.mutex], 0
           ret
.large:
           mov ebx, eax
           call insert_large_chunk
           pop esi
           and [mst.mutex], 0
           ret
 
align 4
 
; param
;  esi= chunk
;  ebx= size
 
align 4
insert_large_chunk:
 
; I = compute_tree_index(S);
 
           mov edx, ebx
           shr edx, 8
           bsr eax, edx
           lea ecx, [eax+7]
           mov edx, ebx
           shr edx, cl
           and edx, 1
           lea ecx, [edx+eax*2]
 
; X->index = I;
           mov dword [esi+28], ecx
 
; X->child[0] = X->child[1] = 0;
           and dword [esi+20], 0
           and dword [esi+16], 0
 
; H = &ms.treebins[I];
 
           mov eax, ecx
           lea edx, [mst.treebins+eax*4]
 
; if (!(ms.treemap & 1<
           bt [mst.treemap], ecx
           jc .tree
 
; ms.treemap |= 1<
           bts [mst.treemap], ecx
; *H = X;
           mov dword [edx], esi
           jmp .done
.tree:
 
; T = *H;
           mov edx, [edx]
 
; K = S << leftshift_for_tree_index(I);
           mov eax, ecx
           shr eax, 1
           sub ecx, 31
           mov edi, 37
           sub edi, eax
           neg ecx
           sbb ecx, ecx
           and ecx, edi
           mov eax, ebx
           shl eax, cl     ;eax= K
 
           jmp .loop
 
.not_eq_size:
 
; C = &(T->child[(K >> 31) & 1]);
           mov ecx, eax
           shr ecx, 31
           lea ecx, [edx+ecx*4+16]
 
; K <<= 1;
; if (*C != 0)
           mov edi, [ecx]
           add eax, eax
           test edi, edi
           jz .insert_child
 
; T = *C;
           mov edx, edi
.loop:
 
; for (;;)
; if ((T->head & ~INUSE_BITS) != S)
 
           mov ecx, [edx+4]
           and ecx, not 3
           cmp ecx, ebx
           jne .not_eq_size
 
; F = T->fd;
           mov eax, [edx+8]
 
; T->fd = F->bk = X;
           mov [eax+12], esi
           mov [edx+8], esi
 
; X->fd = F;
; X->bk = T;
; X->parent = 0;
 
           and dword [esi+24], 0
           mov [esi+8], eax
           mov [esi+12], edx
           ret
 
.insert_child:
 
; *C = X;
           mov [ecx], esi
.done:
 
; X->parent = T;
           mov [esi+24], edx
 
; X->fd = X->bk = X;
           mov [esi+12], esi
           mov [esi+8], esi
           ret
 
 
; param
;  edx= chunk
 
align 4
unlink_large_chunk:
 
           mov eax, [edx+12]
           cmp eax, edx
           push edi
           mov edi, [edx+24]
           je @F
 
           mov ecx, [edx+8]           ;F = X->fd
           mov [ecx+12], eax          ;F->bk = R;
           mov [eax+8], ecx           ;R->fd = F
           jmp .parent
@@:
           mov eax, [edx+20]
           test eax, eax
           push esi
           lea esi, [edx+20]
           jne .loop
 
           mov eax, [edx+16]
           test eax, eax
           lea esi, [edx+16]
           je .l2
.loop:
           cmp dword [eax+20], 0
           lea ecx, [eax+20]
           jne @F
 
           cmp dword [eax+16], 0
           lea ecx, [eax+16]
           je .l1
@@:
           mov eax, [ecx]
           mov esi, ecx
           jmp .loop
.l1:
           mov dword [esi], 0
.l2:
           pop esi
.parent:
           test edi, edi
           je .done
 
           mov ecx, [edx+28]
           cmp edx, [mst.treebins+ecx*4]
           lea ecx, [mst.treebins+ecx*4]
           jne .l3
 
           test eax, eax
           mov [ecx], eax
           jne .l5
 
           mov ecx, [edx+28]
           btr [mst.treemap], ecx
           pop edi
           ret
.l3:
           cmp [edi+16], edx
           jne @F
 
           mov [edi+16], eax
           jmp .l4
@@:
           mov [edi+20], eax
.l4:
           test eax, eax
           je .done
.l5:
           mov [eax+24], edi
           mov ecx, [edx+16]
           test ecx, ecx
           je .l6
 
           mov [eax+16], ecx
           mov [ecx+24], eax
.l6:
           mov edx, [edx+20]
           test edx, edx
           je .done
 
           mov [eax+20], edx
           mov [edx+24], eax
.done:
           pop edi
           ret
 
; param
;  esi= nb
 
align 4
malloc_small:
           push ebp
           mov ebp, esi
 
           push edi
 
           bsf eax,[mst.treemap]
           mov ecx, [mst.treebins+eax*4]
 
; rsize = (t->head & ~INUSE_BITS) - nb;
 
           mov edi, [ecx+4]
           and edi, -4
           sub edi, esi
.loop:
           mov ebx, ecx
.loop_1:
 
; while ((t = leftmost_child(t)) != 0)
 
           mov eax, [ecx+16]
           test eax, eax
           jz @F
           mov ecx, eax
           jmp .l1
@@:
           mov ecx, [ecx+20]
.l1:
           test ecx, ecx
           jz .unlink
 
; trem = (t->head & ~INUSE_BITS) - nb;
 
           mov eax, [ecx+4]
           and eax, -4
           sub eax, ebp
 
; if (trem < rsize)
 
           cmp eax, edi
           jae .loop_1
 
; rsize = trem;
 
           mov edi, eax
           jmp .loop
.unlink:
 
 
; r = chunk_plus_offset((mchunkptr)v, nb);
; unlink_large_chunk(v);
 
           mov edx, ebx
           lea esi, [ebx+ebp]
           call unlink_large_chunk
 
; if (rsize < 16)
 
           cmp edi, 16
           jae .split
 
; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
 
           lea ecx, [edi+ebp]
 
; (v+rsize + nb)->head |= PINUSE_BIT;
 
           add edi, ebx
           lea eax, [edi+ebp+4]
           pop edi
           or ecx, 3
           mov [ebx+4], ecx
           or dword [eax], 1
           pop ebp
 
           lea eax, [ebx+8]
           ret
.split:
 
; v->head = nb|PINUSE_BIT|CINUSE_BIT;
; r->head = rsize|PINUSE_BIT;
; (r+rsize)->prev_foot = rsize;
 
           or ebp, 3
           mov edx, edi
           or edx, 1
 
           cmp edi, 256
           mov [ebx+4], ebp
           mov [esi+4], edx
           mov [esi+edi], edi
           jae .large
 
           shr edi, 3
           bts [mst.smallmap], edi
 
           mov eax, edi
           shl eax, 4
           add eax, mst.smallbins
 
           mov edx, [eax+8]
           mov [eax+8], esi
           mov [edx+12], esi
           pop edi
           mov [esi+12], eax
           mov [esi+8], edx
           pop ebp
           lea eax, [ebx+8]
           ret
.large:
           lea eax, [ebx+8]
           push eax
           mov ebx, edi
           call insert_large_chunk
           pop eax
           pop edi
           pop ebp
           ret
 
 
; param
;  esi= nb
 
align 4
malloc_large:
.idx equ esp+4
.rst equ esp
 
           push ebp
           push edi
           sub esp, 8
; v = 0;
; rsize = -nb;
 
           mov edi, esi
           mov ebx, esi
           xor ebp, ebp
           neg edi
 
; idx = compute_tree_index(nb);
 
           mov edx, esi
           shr edx, 8
           bsr eax, edx
           lea ecx, [eax+7]
           shr esi, cl
           and esi, 1
           lea ecx, [esi+eax*2]
           mov [.idx], ecx
 
; if ((t = ms.treebins[idx]) != 0)
 
           mov eax, [mst.treebins+ecx*4]
           test eax, eax
           jz .l3
 
; sizebits = nb << leftshift_for_tree_index(idx);
 
           cmp ecx, 31
           jne @F
           xor ecx, ecx
           jmp .l1
@@:
           mov edx, ecx
           shr edx, 1
           mov ecx, 37
           sub ecx, edx
.l1:
           mov edx, ebx
           shl edx, cl
 
; rst = 0;
           mov [.rst], ebp
.loop:
 
; trem = (t->head & ~INUSE_BITS) - nb;
 
           mov ecx, [eax+4]
           and ecx, -4
           sub ecx, ebx
 
; if (trem < rsize)
 
           cmp ecx, edi
           jae @F
; v = t;
; if ((rsize = trem) == 0)
 
           test ecx, ecx
           mov ebp, eax
           mov edi, ecx
           je .l2
@@:
 
; rt = t->child[1];
 
           mov ecx, [eax+20]
 
; t = t->child[(sizebits >> 31) & 1];
 
           mov esi, edx
           shr esi, 31
 
; if (rt != 0 && rt != t)
 
           test ecx, ecx
           mov eax, [eax+esi*4+16]
           jz @F
           cmp ecx, eax
           jz @F
 
; rst = rt;
           mov [.rst], ecx
@@:
; if (t == 0)
 
           test eax, eax
           jz @F
 
; sizebits <<= 1;
 
           add edx, edx
           jmp .loop
@@:
; t = rst;
           mov eax, [.rst]
.l2:
; if (t == 0 && v == 0)
 
           test eax, eax
           jne .l4
           test ebp, ebp
           jne .l7
           mov ecx, [.idx]
.l3:
 
; leftbits = (-1<
; if (leftbits != 0)
 
           or edx, -1
           shl edx, cl
           and edx, [mst.treemap]
           jz @F
 
           bsf eax, edx
; t = ms.treebins[i];
           mov eax, [mst.treebins+eax*4]
@@:
 
; while (t != 0)
           test eax, eax
           jz .l5
.l4:
 
; trem = (t->head & ~INUSE_BITS) - nb;
 
           mov ecx, [eax+4]
           and ecx, -4
           sub ecx, ebx
 
; if (trem < rsize)
 
           cmp ecx, edi
           jae @F
; rsize = trem;
 
           mov edi, ecx
; v = t;
           mov ebp, eax
@@:
 
; t = leftmost_child(t);
 
           mov ecx, [eax+16]
           test ecx, ecx
           je @F
           mov eax, ecx
           jmp .l6
@@:
           mov eax, [eax+20]
.l6:
 
; while (t != 0)
 
           test eax, eax
           jne .l4
.l5:
 
; if (v != 0)
 
           test ebp, ebp
           jz .done
.l7:
 
; r = chunk_plus_offset((mchunkptr)v, nb);
; unlink_large_chunk(v);
 
           mov edx, ebp
           lea esi, [ebx+ebp]
           call unlink_large_chunk
 
; if (rsize < 16)
 
           cmp edi, 16
           jae .large
 
; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
 
           lea ecx, [edi+ebx]
 
; (v+rsize + nb)->head |= PINUSE_BIT;
 
           add edi, ebp
           lea eax, [edi+ebx+4]
           or ecx, 3
           mov [ebp+4], ecx
           or dword [eax], 1
           lea eax, [ebp+8]
           add esp, 8
           pop edi
           pop ebp
           ret
.large:
 
; v->head = nb|PINUSE_BIT|CINUSE_BIT;
; r->head = rsize|PINUSE_BIT;
 
           mov edx, edi
           or ebx, 3
           mov [ebp+4], ebx
           or edx, 1
           mov [esi+4], edx
 
; (r+rsize)->prev_foot = rsize;
; insert_large_chunk((tchunkptr)r, rsize);
 
           mov [esi+edi], edi
           mov eax, edi
           mov ecx, esi
           call insert_chunk
 
           lea eax, [ebp+8]
           add esp, 8
           pop edi
           pop ebp
           ret
.done:
           add esp, 8
           pop edi
           pop ebp
           xor eax, eax
           ret
 
align 4
init_malloc:
 
           stdcall kernel_alloc, 0x20000
 
           mov [mst.top], eax
           mov [mst.topsize], 128*1024
           mov dword [eax+4], (128*1024) or 1
           mov eax, mst.smallbins
@@:
           mov [eax+8], eax
           mov [eax+12], eax
           add eax, 16
           cmp eax, mst.smallbins+512
           jl @B
 
           ret
>
>
>
>
 
>
;>
;>

Rev 387	Rev 394
1	; Small heap based on malloc/free/realloc written by Doug Lea	1	; Small heap based on malloc/free/realloc written by Doug Lea
2	; Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)	2	; Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
3	; Source ftp://gee.cs.oswego.edu/pub/misc/malloc.c	3	; Source ftp://gee.cs.oswego.edu/pub/misc/malloc.c
4	; License http://creativecommons.org/licenses/publicdomain.	4	; License http://creativecommons.org/licenses/publicdomain.
5		5
6		6
7	; eax= size	7	; eax= size
8		8
9	; temp	9	; temp
10	; esi= nb	10	; esi= nb
11	; ebx= idx	11	; ebx= idx
12	;	12	;
13	malloc:	13	malloc:
14	push esi	14	push esi
15		15
16	; nb = ((size+7)&~7)+8;	16	; nb = ((size+7)&~7)+8;
17		17
18	mov esi, eax ;size	18	mov esi, eax ;size
19	add esi, 7	19	add esi, 7
20	and esi, -8	20	and esi, -8
21	add esi, 8	21	add esi, 8
22		22
23	mov ebx, mst.mutex	23	mov ebx, mst.mutex
24	call wait_mutex ;ebx	24	call wait_mutex ;ebx
25		25
26	cmp esi, 256	26	cmp esi, 256
27	jae .large	27	jae .large
28		28
29	mov ecx, esi	29	mov ecx, esi
30	shr ecx, 3	30	shr ecx, 3
31	or eax, -1	31	or eax, -1
32	shl eax, cl	32	shl eax, cl
33	and eax, [mst.smallmap]	33	and eax, [mst.smallmap]
34	jz .small	34	jz .small
35		35
36	push ebp	36	push ebp
37	push edi	37	push edi
38		38
39	bsf eax, eax	39	bsf eax, eax
40	mov ebx, eax	40	mov ebx, eax
41		41
42	; psize= idx<<3;	42	; psize= idx<<3;
43	; B = &ms.smallbins[idx];	43	; B = &ms.smallbins[idx];
44	; p = B->fd;	44	; p = B->fd;
45	; F = p->fd;	45	; F = p->fd;
46	; rsize= psize-nb;	46	; rsize= psize-nb;
47		47
48	lea ebp, [eax*8] ;ebp= psize	48	lea ebp, [eax*8] ;ebp= psize
49	shl eax, 4	49	shl eax, 4
50	lea edi, [mst.smallbins+eax] ;edi= B	50	lea edi, [mst.smallbins+eax] ;edi= B
51	mov edx, [edi+8] ;edx= p	51	mov edx, [edi+8] ;edx= p
52	mov eax, [edx+8] ;eax= F	52	mov eax, [edx+8] ;eax= F
53	mov ecx, ebp	53	mov ecx, ebp
54	sub ecx, esi ;ecx= rsize	54	sub ecx, esi ;ecx= rsize
55		55
56	; if (B == F)	56	; if (B == F)
57	cmp edi, eax	57	cmp edi, eax
58	jne @F	58	jne @F
59		59
60	btr [mst.smallmap], ebx	60	btr [mst.smallmap], ebx
61	@@:	61	@@:
62		62
63	; B->fd = F;	63	; B->fd = F;
64	; F->bk = B;	64	; F->bk = B;
65	; if(rsize<16)	65	; if(rsize<16)
66		66
67	cmp ecx, 16	67	cmp ecx, 16
68	mov [edi+8], eax	68	mov [edi+8], eax
69	mov [eax+12], edi	69	mov [eax+12], edi
70	jae .split	70	jae .split
71		71
72	; p->head = psize\|PINUSE_BIT\|CINUSE_BIT;	72	; p->head = psize\|PINUSE_BIT\|CINUSE_BIT;
73	; (p + psize)->head \|= PINUSE_BIT;	73	; (p + psize)->head \|= PINUSE_BIT;
74		74
75	lea eax, [edx+8]	75	lea eax, [edx+8]
76	or dword [edx+ebp+4], 1	76	or dword [edx+ebp+4], 1
77		77
78	or ebp, 3	78	or ebp, 3
79	mov [edx+4], ebp	79	mov [edx+4], ebp
80		80
81	pop edi	81	pop edi
82	pop ebp	82	pop ebp
83	.done:	83	.done:
84	pop esi	84	pop esi
85	mov [mst.mutex], 0	85	mov [mst.mutex], 0
86	ret	86	ret
87	.split:	87	.split:
88	lea ebx, [edx+8] ;ebx=mem	88	lea ebx, [edx+8] ;ebx=mem
89		89
90	; r = chunk_plus_offset(p, nb);	90	; r = chunk_plus_offset(p, nb);
91	; p->head = nb\|PINUSE_BIT\|CINUSE_BIT;	91	; p->head = nb\|PINUSE_BIT\|CINUSE_BIT;
92	; r->head = rsize\|PINUSE_BIT;	92	; r->head = rsize\|PINUSE_BIT;
93		93
94	lea eax, [edx+esi] ;eax= r	94	lea eax, [edx+esi] ;eax= r
95	or esi, 3	95	or esi, 3
96	mov [edx+4], esi	96	mov [edx+4], esi
97		97
98	mov edx, ecx	98	mov edx, ecx
99	or edx, 1	99	or edx, 1
100	mov [eax+4], edx	100	mov [eax+4], edx
101		101
102	; (r + rsize)->prev_foot = rsize;	102	; (r + rsize)->prev_foot = rsize;
103		103
104	mov [eax+ecx], ecx	104	mov [eax+ecx], ecx
105		105
106	; I = rsize>>3;	106	; I = rsize>>3;
107		107
108	shr ecx, 3	108	shr ecx, 3
109		109
110	; ms.smallmap \|= 1<< I;	110	; ms.smallmap \|= 1<< I;
111	bts [mst.smallmap], ecx	111	bts [mst.smallmap], ecx
112		112
113	; B = &ms.smallbins[I];	113	; B = &ms.smallbins[I];
114		114
115	shl ecx, 4	115	shl ecx, 4
116	pop edi	116	pop edi
117	pop ebp	117	pop ebp
118	add ecx, mst.smallbins ;ecx= B	118	add ecx, mst.smallbins ;ecx= B
119		119
120	mov edx, [ecx+8] ; F = B->fd;	120	mov edx, [ecx+8] ; F = B->fd;
121	mov [ecx+8], eax ; B->fd = r;	121	mov [ecx+8], eax ; B->fd = r;
122	mov [edx+12], eax ; F->bk = r;	122	mov [edx+12], eax ; F->bk = r;
123	mov [eax+8], edx ; r->fd = F;	123	mov [eax+8], edx ; r->fd = F;
124	mov [eax+12], ecx ; r->bk = B;	124	mov [eax+12], ecx ; r->bk = B;
125	mov eax, ebx	125	mov eax, ebx
126	pop esi	126	pop esi
127	ret	127	ret
128	.small:	128	.small:
129		129
130	; if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)	130	; if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)
131		131
132	cmp [mst.treemap], 0	132	cmp [mst.treemap], 0
133	je .from_top	133	je .from_top
134	mov eax, esi	134	mov eax, esi
135	call malloc_small	135	call malloc_small
136	test eax, eax	136	test eax, eax
137	jz .from_top	137	jz .from_top
138	pop esi	138	pop esi
139	and [mst.mutex], 0	139	and [mst.mutex], 0
140	ret	140	ret
141	.large:	141	.large:
142		142
143	; if (ms.treemap != 0 && (mem = malloc_large(nb)) != 0)	143	; if (ms.treemap != 0 && (mem = malloc_large(nb)) != 0)
144		144
145	cmp [mst.treemap], 0	145	cmp [mst.treemap], 0
146	je .from_top	146	je .from_top
147		147
148	call malloc_large ;esi= nb	148	call malloc_large ;esi= nb
149	test eax, eax	149	test eax, eax
150	jne .done	150	jne .done
151	.from_top:	151	.from_top:
152		152
153	; if (nb < ms.topsize)	153	; if (nb < ms.topsize)
154		154
155	mov eax, [mst.topsize]	155	mov eax, [mst.topsize]
156	cmp esi, eax	156	cmp esi, eax
157	jae .fail	157	jae .fail
158		158
159	; rsize = ms.topsize -= nb;	159	; rsize = ms.topsize -= nb;
160	; p = ms.top;	160	; p = ms.top;
161		161
162	mov ecx, [mst.top]	162	mov ecx, [mst.top]
163	sub eax, esi	163	sub eax, esi
164	mov [mst.topsize], eax	164	mov [mst.topsize], eax
165		165
166	; r = ms.top = chunk_plus_offset(p, nb);	166	; r = ms.top = chunk_plus_offset(p, nb);
167	; r->head = rsize \| PINUSE_BIT;	167	; r->head = rsize \| PINUSE_BIT;
168	; p->head = nb \|PINUSE_BIT\|CINUSE_BIT;	168	; p->head = nb \|PINUSE_BIT\|CINUSE_BIT;
169		169
170	lea edx, [ecx+esi]	170	lea edx, [ecx+esi]
171	or eax, 1	171	or eax, 1
172	mov [mst.top], edx	172	mov [mst.top], edx
173	or esi, 3	173	or esi, 3
174	mov [edx+4], eax	174	mov [edx+4], eax
175	mov [ecx+4], esi	175	mov [ecx+4], esi
176	lea eax, [ecx+8]	176	lea eax, [ecx+8]
177	pop esi	177	pop esi
178	and [mst.mutex], 0	178	and [mst.mutex], 0
179	ret	179	ret
180	.fail:	180	.fail:
181	xor eax, eax	181	xor eax, eax
182	pop esi	182	pop esi
183	and [mst.mutex], 0	183	and [mst.mutex], 0
184	ret	184	ret
185		185
186	; param	186	; param
187	; eax= mem	187	; eax= mem
188		188
189	align 4	189	align 4
190	free:	190	free:
191	push edi	191	push edi
192	mov edi, eax	192	mov edi, eax
193	add edi, -8	193	add edi, -8
194		194
195	; if(p->head & CINUSE_BIT)	195	; if(p->head & CINUSE_BIT)
196		196
197	test byte [edi+4], 2	197	test byte [edi+4], 2
198	je .fail	198	je .fail
199		199
200	mov ebx, mst.mutex	200	mov ebx, mst.mutex
201	call wait_mutex ;ebx	201	call wait_mutex ;ebx
202		202
203	; psize = p->head & (~3);	203	; psize = p->head & (~3);
204		204
205	mov eax, [edi+4]	205	mov eax, [edi+4]
206	push esi	206	push esi
207	mov esi, eax	207	mov esi, eax
208	and esi, -4	208	and esi, -4
209		209
210	; next = chunk_plus_offset(p, psize);	210	; next = chunk_plus_offset(p, psize);
211	; if(!(p->head & PINUSE_BIT))	211	; if(!(p->head & PINUSE_BIT))
212		212
213	test al, 1	213	test al, 1
214	lea ebx, [esi+edi]	214	lea ebx, [esi+edi]
215	jne .next	215	jne .next
216		216
217	; prevsize = p->prev_foot;	217	; prevsize = p->prev_foot;
218	; prev=p - prevsize;	218	; prev=p - prevsize;
219	; psize += prevsize;	219	; psize += prevsize;
220	; p = prev;	220	; p = prev;
221		221
222	mov ecx, [edi] ;ecx= prevsize	222	mov ecx, [edi] ;ecx= prevsize
223	add esi, ecx ;esi= psize	223	add esi, ecx ;esi= psize
224	sub edi, ecx ;edi= p	224	sub edi, ecx ;edi= p
225		225
226	; if (prevsize < 256)	226	; if (prevsize < 256)
227		227
228	cmp ecx, 256	228	cmp ecx, 256
229	jae .unlink_large	229	jae .unlink_large
230		230
231	mov eax, [edi+8] ;F = p->fd;	231	mov eax, [edi+8] ;F = p->fd;
232	mov edx, [edi+12] ;B = p->bk;	232	mov edx, [edi+12] ;B = p->bk;
233		233
234	; if (F == B)	234	; if (F == B)
235	; ms.smallmap &= ~(1<< I);	235	; ms.smallmap &= ~(1<< I);
236	shr ecx, 3	236	shr ecx, 3
237	cmp eax, edx	237	cmp eax, edx
238	jne @F	238	jne @F
239	and [mst.smallmap], ecx	239	and [mst.smallmap], ecx
240	@@:	240	@@:
241	mov [eax+12], edx ;F->bk = B;	241	mov [eax+12], edx ;F->bk = B;
242	mov [edx+8], eax ;B->fd = F	242	mov [edx+8], eax ;B->fd = F
243	jmp .next	243	jmp .next
244	.unlink_large:	244	.unlink_large:
245	mov edx, edi	245	mov edx, edi
246	call unlink_large_chunk	246	call unlink_large_chunk
247	.next:	247	.next:
248		248
249	; if(next->head & PINUSE_BIT)	249	; if(next->head & PINUSE_BIT)
250		250
251	mov eax, [ebx+4]	251	mov eax, [ebx+4]
252	test al, 1	252	test al, 1
253	jz .fail2	253	jz .fail2
254		254
255	; if (! (next->head & CINUSE_BIT))	255	; if (! (next->head & CINUSE_BIT))
256		256
257	test al, 2	257	test al, 2
258	jnz .fix_next	258	jnz .fix_next
259		259
260	; if (next == ms.top)	260	; if (next == ms.top)
261		261
262	cmp ebx, [mst.top]	262	cmp ebx, [mst.top]
263	jne @F	263	jne @F
264		264
265	; tsize = ms.topsize += psize;	265	; tsize = ms.topsize += psize;
266		266
267	mov eax, [mst.topsize]	267	mov eax, [mst.topsize]
268	add eax, esi	268	add eax, esi
269	mov [mst.topsize], eax	269	mov [mst.topsize], eax
270		270
271	; ms.top = p;	271	; ms.top = p;
272	; p->head = tsize \| PINUSE_BIT;	272	; p->head = tsize \| PINUSE_BIT;
273		273
274	or eax, 1	274	or eax, 1
275	mov [mst.top], edi	275	mov [mst.top], edi
276	mov [edi+4], eax	276	mov [edi+4], eax
277	.fail2:	277	.fail2:
278	and [mst.mutex], 0	278	and [mst.mutex], 0
279	pop esi	279	pop esi
280	.fail:	280	.fail:
281	pop edi	281	pop edi
282	ret	282	ret
283	@@:	283	@@:
284		284
285	; nsize = next->head & ~INUSE_BITS;	285	; nsize = next->head & ~INUSE_BITS;
286		286
287	and eax, -4	287	and eax, -4
288	add esi, eax ;psize += nsize;	288	add esi, eax ;psize += nsize;
289		289
290	; if (nsize < 256)	290	; if (nsize < 256)
291		291
292	cmp eax, 256	292	cmp eax, 256
293	jae .unl_large	293	jae .unl_large
294		294
295	mov edx, [ebx+8] ;F = next->fd	295	mov edx, [ebx+8] ;F = next->fd
296	mov ebx, [ebx+12] ;B = next->bk	296	mov ebx, [ebx+12] ;B = next->bk
297		297
298	; if (F == B)	298	; if (F == B)
299		299
300	cmp edx, ebx	300	cmp edx, ebx
301	jne @F	301	jne @F
302	mov ecx, eax	302	mov ecx, eax
303	shr ecx, 3	303	shr ecx, 3
304	btr [mst.smallmap], ecx	304	btr [mst.smallmap], ecx
305	@@:	305	@@:
306	mov [edx+12], ebx ;F->bk = B	306	mov [edx+12], ebx ;F->bk = B
307		307
308	; p->head = psize\|PINUSE_BIT;	308	; p->head = psize\|PINUSE_BIT;
309		309
310	mov ecx, esi	310	mov ecx, esi
311	mov [ebx+8], edx	311	mov [ebx+8], edx
312	or ecx, 1	312	or ecx, 1
313	mov [edi+4], ecx	313	mov [edi+4], ecx
314		314
315	; (p+psize)->prev_foot = psize;	315	; (p+psize)->prev_foot = psize;
316		316
317	mov [esi+edi], esi	317	mov [esi+edi], esi
318		318
319	; insert_chunk(p,psize);	319	; insert_chunk(p,psize);
320		320
321	mov eax, esi	321	mov eax, esi
322	pop esi	322	pop esi
323	mov ecx, edi	323	mov ecx, edi
324	pop edi	324	pop edi
325	jmp insert_chunk	325	jmp insert_chunk
326	.unl_large:	326	.unl_large:
327		327
328	; unlink_large_chunk((tchunkptr)next);	328	; unlink_large_chunk((tchunkptr)next);
329		329
330	mov edx, ebx	330	mov edx, ebx
331	call unlink_large_chunk	331	call unlink_large_chunk
332	; p->head = psize\|PINUSE_BIT;	332	; p->head = psize\|PINUSE_BIT;
333		333
334	mov ecx, esi	334	mov ecx, esi
335	or ecx, 1	335	or ecx, 1
336	mov [edi+4], ecx	336	mov [edi+4], ecx
337		337
338	; (p+psize)->prev_foot = psize;	338	; (p+psize)->prev_foot = psize;
339		339
340	mov [esi+edi], esi	340	mov [esi+edi], esi
341		341
342	; insert_chunk(p,psize);	342	; insert_chunk(p,psize);
343		343
344	mov eax, esi	344	mov eax, esi
345	pop esi	345	pop esi
346	mov ecx, edi	346	mov ecx, edi
347	pop edi	347	pop edi
348	jmp insert_chunk	348	jmp insert_chunk
349	.fix_next:	349	.fix_next:
350		350
351	; (p+psize)->prev_foot = psize;	351	; (p+psize)->prev_foot = psize;
352	; next->head &= ~PINUSE_BIT;	352	; next->head &= ~PINUSE_BIT;
353	; p->head = psize\|PINUSE_BIT;	353	; p->head = psize\|PINUSE_BIT;
354		354
355	and eax, -2	355	and eax, -2
356	mov edx, esi	356	mov edx, esi
357	mov [ebx+4], eax	357	mov [ebx+4], eax
358	or edx, 1	358	or edx, 1
359	mov [edi+4], edx	359	mov [edi+4], edx
360		360
361	; (p+psize)->prev_foot = psize;	361	; (p+psize)->prev_foot = psize;
362		362
363	mov [esi+edi], esi	363	mov [esi+edi], esi
364	; insert_chunk(p,psize);	364	; insert_chunk(p,psize);
365		365
366	mov eax, esi	366	mov eax, esi
367	pop esi	367	pop esi
368	mov ecx, edi	368	mov ecx, edi
369	pop edi	369	pop edi
370	jmp insert_chunk	370	jmp insert_chunk
371		371
372	; param	372	; param
373	; ecx = chunk	373	; ecx = chunk
374	; eax = size	374	; eax = size
375		375
376	align 4	376	align 4
377	insert_chunk:	377	insert_chunk:
378		378
379	cmp eax, 256	379	cmp eax, 256
380	push esi	380	push esi
381	mov esi, ecx	381	mov esi, ecx
382	jae .large	382	jae .large
383		383
384	; I = S>>3;	384	; I = S>>3;
385	; ms.smallmap \|= 1<< I;	385	; ms.smallmap \|= 1<< I;
386		386
387	shr eax, 3	387	shr eax, 3
388	bts [mst.smallmap], eax	388	bts [mst.smallmap], eax
389		389
390	; B = &ms.smallbins[I];	390	; B = &ms.smallbins[I];
391		391
392	shl eax, 4	392	shl eax, 4
393	add eax, mst.smallbins	393	add eax, mst.smallbins
394	mov edx, [eax+8] ;F = B->fd	394	mov edx, [eax+8] ;F = B->fd
395	mov [eax+8], esi ;B->fd = P	395	mov [eax+8], esi ;B->fd = P
396	mov [edx+12], esi ;F->bk = P	396	mov [edx+12], esi ;F->bk = P
397	mov [esi+8], edx ;P->fd = F	397	mov [esi+8], edx ;P->fd = F
398	mov [esi+12], eax ;P->bk = B	398	mov [esi+12], eax ;P->bk = B
399	pop esi	399	pop esi
400	and [mst.mutex], 0	400	and [mst.mutex], 0
401	ret	401	ret
402	.large:	402	.large:
403	mov ebx, eax	403	mov ebx, eax
404	call insert_large_chunk	404	call insert_large_chunk
405	pop esi	405	pop esi
406	and [mst.mutex], 0	406	and [mst.mutex], 0
407	ret	407	ret
408		408
409	align 4	409	align 4
410		410
411	; param	411	; param
412	; esi= chunk	412	; esi= chunk
413	; ebx= size	413	; ebx= size
414		414
415	align 4	415	align 4
416	insert_large_chunk:	416	insert_large_chunk:
417		417
418	; I = compute_tree_index(S);	418	; I = compute_tree_index(S);
419		419
420	mov edx, ebx	420	mov edx, ebx
421	shr edx, 8	421	shr edx, 8
422	bsr eax, edx	422	bsr eax, edx
423	lea ecx, [eax+7]	423	lea ecx, [eax+7]
424	mov edx, ebx	424	mov edx, ebx
425	shr edx, cl	425	shr edx, cl
426	and edx, 1	426	and edx, 1
427	lea ecx, [edx+eax*2]	427	lea ecx, [edx+eax*2]
428		428
429	; X->index = I;	429	; X->index = I;
430	mov dword [esi+28], ecx	430	mov dword [esi+28], ecx
431		431
432	; X->child[0] = X->child[1] = 0;	432	; X->child[0] = X->child[1] = 0;
433	and dword [esi+20], 0	433	and dword [esi+20], 0
434	and dword [esi+16], 0	434	and dword [esi+16], 0
435		435
436	; H = &ms.treebins[I];	436	; H = &ms.treebins[I];
437		437
438	mov eax, ecx	438	mov eax, ecx
439	lea edx, [mst.treebins+eax*4]	439	lea edx, [mst.treebins+eax*4]
440		440
441	; if (!(ms.treemap & 1<	441	; if (!(ms.treemap & 1<
442	bt [mst.treemap], ecx	442	bt [mst.treemap], ecx
443	jc .tree	443	jc .tree
444		444
445	; ms.treemap \|= 1<	445	; ms.treemap \|= 1<
446	bts [mst.treemap], ecx	446	bts [mst.treemap], ecx
447	; *H = X;	447	; *H = X;
448	mov dword [edx], esi	448	mov dword [edx], esi
449	jmp .done	449	jmp .done
450	.tree:	450	.tree:
451		451
452	; T = *H;	452	; T = *H;
453	mov edx, [edx]	453	mov edx, [edx]
454		454
455	; K = S << leftshift_for_tree_index(I);	455	; K = S << leftshift_for_tree_index(I);
456	mov eax, ecx	456	mov eax, ecx
457	shr eax, 1	457	shr eax, 1
458	sub ecx, 31	458	sub ecx, 31
459	mov edi, 37	459	mov edi, 37
460	sub edi, eax	460	sub edi, eax
461	neg ecx	461	neg ecx
462	sbb ecx, ecx	462	sbb ecx, ecx
463	and ecx, edi	463	and ecx, edi
464	mov eax, ebx	464	mov eax, ebx
465	shl eax, cl ;eax= K	465	shl eax, cl ;eax= K
466		466
467	jmp .loop	467	jmp .loop
468		468
469	.not_eq_size:	469	.not_eq_size:
470		470
471	; C = &(T->child[(K >> 31) & 1]);	471	; C = &(T->child[(K >> 31) & 1]);
472	mov ecx, eax	472	mov ecx, eax
473	shr ecx, 31	473	shr ecx, 31
474	lea ecx, [edx+ecx*4+16]	474	lea ecx, [edx+ecx*4+16]
475		475
476	; K <<= 1;	476	; K <<= 1;
477	; if (*C != 0)	477	; if (*C != 0)
478	mov edi, [ecx]	478	mov edi, [ecx]
479	add eax, eax	479	add eax, eax
480	test edi, edi	480	test edi, edi
481	jz .insert_child	481	jz .insert_child
482		482
483	; T = *C;	483	; T = *C;
484	mov edx, edi	484	mov edx, edi
485	.loop:	485	.loop:
486		486
487	; for (;;)	487	; for (;;)
488	; if ((T->head & ~INUSE_BITS) != S)	488	; if ((T->head & ~INUSE_BITS) != S)
489		489
490	mov ecx, [edx+4]	490	mov ecx, [edx+4]
491	and ecx, not 3	491	and ecx, not 3
492	cmp ecx, ebx	492	cmp ecx, ebx
493	jne .not_eq_size	493	jne .not_eq_size
494		494
495	; F = T->fd;	495	; F = T->fd;
496	mov eax, [edx+8]	496	mov eax, [edx+8]
497		497
498	; T->fd = F->bk = X;	498	; T->fd = F->bk = X;
499	mov [eax+12], esi	499	mov [eax+12], esi
500	mov [edx+8], esi	500	mov [edx+8], esi

Subversion Repositories Kolibri OS

(root)/kernel/branches/flat_kernel/core/malloc.inc – Rev 387 → 394