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


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

Subversion Repositories Kolibri OS

(root)/kernel/branches/flat_kernel/core/malloc.inc – Rev 438 → 444