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


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;                                                              ;;
;; Copyright (C) KolibriOS team 2004-2015. All rights reserved. ;;
;; Distributed under terms of the GNU General Public License    ;;
;;                                                              ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
$Revision: 5363 $
 
 
; 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
;
align 4
malloc:
        push    ebx esi
 
; nb = ((size+7)&~7)+8;
 
        mov     esi, eax   ;size
        add     esi, 7
        and     esi, -8
        add     esi, 8
 
        mov     ecx, mst.mutex
        call    mutex_lock
 
        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:
        mov     esi, eax
        mov     ecx, mst.mutex
        call    mutex_unlock
        mov     eax, esi
        pop     esi ebx
        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
        jmp     .done
 
.small:
 
; if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)
;;;;;;;;;;; start a change 
        mov     eax, [mst.treemap]
        test    eax, eax
;;;;;;;;;;; end the change 
;           cmp [mst.treemap], 0
        jz      .from_top
        mov     eax, esi
        call    malloc_small
        test    eax, eax
        jz      .from_top
        jmp     .done
 
.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]
        jmp     .done
 
.fail:
        xor     eax, eax
        jmp     .done
 
; param
;  eax= mem
align 4
free:
        test    eax, eax
        jz      .exit
 
        push    ebx edi
        mov     edi, eax
        add     edi, -8
 
; if(p->head & CINUSE_BIT)
 
        test    byte [edi+4], 2
        je      .fail
 
        mov     ecx, mst.mutex
        call    mutex_lock
 
; 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
        btr     [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:
        mov     esi, eax
        mov     ecx, mst.mutex
        call    mutex_unlock
        mov     eax, esi
        pop     esi
.fail:
        pop     edi ebx
.exit:
        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
        mov     ecx, edi
        call    insert_chunk
        jmp     .fail2
.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
        mov     ecx, edi
        call    insert_chunk
        jmp     .fail2
.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
        mov     ecx, edi
        call    insert_chunk
        jmp     .fail2
 
; param
;  ecx = chunk
;  eax = size
 
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
        ret
.large:
        mov     ebx, eax
        call    insert_large_chunk
        pop     esi
        ret
 
 
; param
;  esi= chunk
;  ebx= size
 
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
 
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
 
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
 
malloc_large:
.idx equ esp+4
.rst equ esp
 
        push    ebp
        push    esi
        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     esi
        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     esi
        pop     ebp
        ret
 
.done:
        add     esp, 8
        pop     edi
        pop     esi
        pop     ebp
        xor     eax, eax
        ret
 
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
 
        mov     ecx, mst.mutex
        call    mutex_init
 
        ret
>
>
>
>
 
>
;>
;>

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

Subversion Repositories Kolibri OS

(root)/kernel/trunk/core/malloc.inc – Rev 3681 → 5363