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


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;                                                              ;;
;; Copyright (C) KolibriOS team 2004-2007. All rights reserved. ;;
;; Distributed under terms of the GNU General Public License    ;;
;;                                                              ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
$Revision: 753 $
 
 
; 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, 0x40000
 
           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
           jb @B
 
           ret
>
>
>
>
 
>
;>
;>

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

Subversion Repositories Kolibri OS

(root)/kernel/trunk/core/malloc.inc – Rev 750 → 753