| 0,0 → 1,536 |
|---|
| format ELF |
| section '.text' executable |
| public malloc |
| public free |
| public realloc |
| public mf_init |
| ;multithread: ;uncomment this for thread-safe version |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; Memory allocator for MenuetOS ;; |
| ;; Halyavin Andrey halyavin@land.ru, 2006 ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; allocated mem block structure ;; |
| ;; +0: bit 0 - used flag ;; |
| ;; bits 31..1 - block size ;; |
| ;; +4: address of prev block ;; |
| ;; +8 .. +(blocksize) - allocated memory ;; |
| ;; +(blocksize) - next block ;; |
| ;; ;; |
| ;; free mem block structure ;; |
| ;; +0: bit 0 - used flag ;; |
| ;; bits 31..1 - block size ;; |
| ;; +4: address of prev block ;; |
| ;; +8: prev free block ;; |
| ;; +12: next free block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| memblock.size=0 |
| memblock.prevblock=4 |
| memblock.prevfreeblock=8 |
| memblock.nextfreeblock=12 |
| |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; mf_init ;; |
| ;; Initialize memory map for dynamic use ;; |
| ;; input: eax: starting address or 0 ;; |
| ;; output: none ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| mf_init: |
| push ebx |
| push ecx |
| test eax,eax |
| jnz .noautodet |
| sub esp,1024 |
| mov ebx,esp |
| mov ecx,-1 |
| mov eax,9 |
| int 0x40 |
| mov eax,[esp+26] |
| add esp,1024 |
| .noautodet: |
| add eax,15 |
| and eax,not 15 |
| mov [heapsmallblocks],eax |
| add eax,2048 |
| mov [heapstart],eax |
| mov [heapfreelist],eax |
| mov [heaplastblock],eax |
| |
| mov ecx,eax |
| if defined heapstartsize |
| add ecx,heapstartsize |
| else |
| add ecx,4096 |
| end if |
| add ecx,4095 |
| and ecx,not 4095 |
| push eax |
| mov eax,64 |
| mov ebx,1 |
| int 0x40 |
| pop eax |
| mov [eax+memblock.prevblock],dword 0 |
| mov [heapend],ecx |
| mov [eax+memblock.size],ecx |
| sub [eax+memblock.size],eax |
| xor ebx,ebx |
| mov dword [eax+memblock.prevfreeblock],heapfreelist-memblock.nextfreeblock |
| mov [eax+memblock.nextfreeblock],ebx |
| mov [heapmutex],ebx |
| push edi |
| mov edi,[heapsmallblocks] |
| mov ecx,512 |
| xor eax,eax |
| rep stosd |
| pop edi |
| pop ecx |
| pop ebx |
| ret |
| |
| if defined multithread |
| heaplock: |
| push eax |
| push ebx |
| push ecx |
| mov eax,68 |
| mov ebx,1 |
| .loop: |
| xchg ecx,[heapmutex] |
| test ecx,ecx |
| jz .endloop |
| int 0x40 ;change task |
| jmp .loop |
| .endloop: |
| pop ecx |
| pop ebx |
| pop eax |
| ret |
| |
| heapunlock: |
| mov [heapmutex],dword 0 |
| ret |
| end if |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_split_block ;; |
| ;; Split free block to allocated block and free one. ;; |
| ;; input: ;; |
| ;; eax - size of allocated block ;; |
| ;; ebx - block ;; |
| ;; output: ;; |
| ;; eax - real size of allocated block ;; |
| ;; ebx - pointer to new block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_split_block: |
| push ecx |
| mov ecx,[ebx+memblock.size] |
| sub ecx,16 |
| cmp ecx,eax |
| jge .norm |
| inc dword [ebx+memblock.size] |
| mov eax,ecx |
| xor ebx,ebx |
| pop ecx |
| ret |
| .norm: |
| add ecx,16 |
| mov [ebx+memblock.size],eax |
| inc dword [ebx+memblock.size] |
| mov [ebx+eax+memblock.prevblock],ebx |
| add ebx,eax |
| sub ecx,eax |
| mov [ebx+memblock.size],ecx |
| mov ecx,eax |
| mov eax,ebx |
| call heap_fix_right |
| mov eax,ecx |
| pop ecx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_add_free_block ;; |
| ;; Add free block to one of free block lists. ;; |
| ;; input: ;; |
| ;; eax - address of free block ;; |
| ;; output: ;; |
| ;; none ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_add_free_block: |
| cmp dword [eax+memblock.size],4096 |
| push ebx |
| jge .bigblock |
| mov ebx,[eax+memblock.size] |
| shr ebx,1 |
| add ebx,[heapsmallblocks] |
| push dword [ebx] |
| pop dword [eax+memblock.nextfreeblock] |
| mov [ebx],eax |
| mov dword [eax+memblock.prevfreeblock],ebx |
| sub dword [eax+memblock.prevfreeblock],memblock.nextfreeblock |
| mov ebx,[eax+memblock.nextfreeblock] |
| test ebx,ebx |
| jz .no_next_block |
| mov [ebx+memblock.prevfreeblock],eax |
| .no_next_block: |
| pop ebx |
| ret |
| .bigblock: |
| mov ebx,[heapfreelist] |
| mov [eax+memblock.nextfreeblock],ebx |
| mov [heapfreelist],eax |
| mov dword [eax+memblock.prevfreeblock],heapfreelist-memblock.nextfreeblock |
| ; mov ebx,[eax+memblock.nextfreeblock] |
| test ebx,ebx |
| jz .no_next_big_block |
| mov [ebx+memblock.prevfreeblock],eax |
| .no_next_big_block: |
| pop ebx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_remove_block ;; |
| ;; Remove free block from the list of free blocks. ;; |
| ;; input: ;; |
| ;; eax - free block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_remove_block: |
| push ebx |
| push ecx |
| mov ecx,[eax+memblock.prevfreeblock] |
| mov ebx,[eax+memblock.nextfreeblock] |
| mov [ecx+memblock.nextfreeblock],ebx |
| test ebx,ebx |
| jz .no_next_block |
| mov [ebx+memblock.prevfreeblock],ecx |
| .no_next_block: |
| pop ecx |
| pop ebx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; mf_alloc |
| ;; allocates a block of memory in heap |
| ;; intput: eax: size of block |
| ;; output: eax: address of allocated memory block or 0 if there's no mem. |
| ;; allocator will not create new nodes that contain less that 8b of space, |
| ;; and minimal allocation is actually 16 bytes - 8 for node and 8 for user. |
| ;; allocator will never create non-aligned memory blocks. |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| mf_alloc: |
| test eax,eax |
| jg .not_null ; test that we are not allocating null size block |
| xor eax,eax |
| ret |
| .not_null: |
| if defined multithread |
| call heaplock |
| end if |
| push edi |
| ; push edx |
| push ecx |
| push ebx |
| add eax,7 |
| and eax,not 7 ; make sure that block size is aligned |
| |
| lea edi,[eax+8] ; desired block size |
| cmp edi,4096 |
| jge .general_cycle |
| |
| mov ebx,[heapsmallblocks] |
| xor ecx,ecx |
| shr edi,1 |
| |
| .smallloop: |
| cmp [ebx+edi],ecx |
| jnz .smallblockfound |
| add edi,4 |
| cmp edi,2048 |
| jl .smallloop |
| lea edi,[eax+8] |
| jmp .general_cycle |
| |
| .smallblockfound: |
| lea ecx,[eax+8] |
| mov eax,[ebx+edi] |
| call heap_remove_block |
| mov ebx,eax |
| xchg eax,ecx |
| call heap_split_block |
| test ebx,ebx |
| jz .perfect_small_block |
| mov eax,ebx |
| call heap_add_free_block |
| .perfect_small_block: |
| lea eax,[ecx+8] |
| jmp .ret |
| |
| .general_cycle: |
| ;edi - size needed |
| mov eax,[heapfreelist] |
| |
| .loop: |
| test eax,eax |
| jz .new_mem |
| cmp [eax+memblock.size],edi |
| jge .blockfound |
| mov eax,[eax+memblock.nextfreeblock] |
| jmp .loop |
| |
| .blockfound: |
| call heap_remove_block |
| mov ebx,eax |
| mov ecx,eax |
| mov eax,edi |
| call heap_split_block |
| test ebx,ebx |
| jz .perfect_block |
| mov eax,ebx |
| call heap_add_free_block |
| .perfect_block: |
| lea eax,[ecx+8] |
| .ret: |
| if defined multithread |
| call heapunlock |
| end if |
| pop ebx |
| pop ecx |
| ; pop edx |
| pop edi |
| ret |
| |
| .new_mem: |
| mov eax,edi |
| add eax,4095 |
| and eax,not 4095 |
| mov ecx,[heapend] |
| add [heapend],eax |
| push eax |
| mov eax,64 |
| push ebx |
| push ecx |
| mov ecx,[heapend] |
| mov ebx,1 |
| int 0x40 |
| pop ecx |
| pop ebx |
| pop eax |
| mov [ecx+memblock.size],eax |
| mov eax,[heaplastblock] |
| mov [ecx+memblock.prevblock],eax |
| mov [heaplastblock],ecx |
| mov eax,ecx |
| call heap_add_free_block |
| jmp .general_cycle |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_fix_right ;; |
| ;; input: ;; |
| ;; eax - pointer to free block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_fix_right: |
| push ebx |
| mov ebx,eax |
| add ebx,[eax+memblock.size] |
| cmp ebx,[heapend] |
| jz .endblock |
| mov [ebx+memblock.prevblock],eax |
| pop ebx |
| ret |
| .endblock: |
| mov [heaplastblock],eax |
| pop ebx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_merge_left ;; |
| ;; input: ;; |
| ;; eax - pointer to free block ;; |
| ;; output: ;; |
| ;; eax - pointer to merged block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_merge_left: |
| push ebx |
| mov ebx,[eax+memblock.prevblock] |
| test ebx,ebx |
| jz .ret |
| test byte [ebx+memblock.size],1 |
| jnz .ret |
| xchg eax,ebx |
| call heap_remove_block |
| mov ebx,[ebx+memblock.size] |
| add [eax+memblock.size],ebx |
| call heap_fix_right |
| .ret: |
| pop ebx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_merge_right ;; |
| ;; input: ;; |
| ;; eax - pointer to free block ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_merge_right: |
| push ebx |
| mov ebx,eax |
| add ebx,[eax+memblock.size] |
| cmp ebx,[heapend] |
| jz .ret |
| test byte [ebx+memblock.size],1 |
| jnz .ret |
| xchg eax,ebx |
| call heap_remove_block |
| xchg eax,ebx |
| mov ebx,[ebx+memblock.size] |
| add [eax+memblock.size],ebx |
| call heap_fix_right |
| .ret: |
| pop ebx |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; mf_free ;; |
| ;; input: ;; |
| ;; eax - pointer ;; |
| ;; output: ;; |
| ;; eax=1 - ok ;; |
| ;; eax=0 - failed ;; |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| mf_free: |
| test eax,eax |
| jnz .no_null |
| inc eax |
| ret |
| .no_null: |
| if defined multithread |
| call heaplock |
| end if |
| sub eax,8 |
| dec dword [eax+memblock.size] |
| call heap_merge_left |
| call heap_merge_right |
| call heap_add_free_block |
| .ret: |
| if defined multithread |
| call heapunlock |
| end if |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; heap_try_reloc |
| ;; input: |
| ;; eax - address |
| ;; ebx - new size |
| ;; output: |
| ;; ebx=1 - ok |
| ;; ebx=0 - failed |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| heap_try_reloc: |
| push eax |
| sub eax,8 |
| add ebx,15 |
| dec dword [eax+memblock.size] |
| and ebx,not 7 |
| cmp [eax+memblock.size],ebx |
| jge .truncate |
| push ebx |
| mov ebx,eax |
| add ebx,[eax+memblock.size] |
| cmp ebx,[heapend] |
| jz .fail ;todo: we can allocate new mem here |
| test [ebx+memblock.size],byte 1 |
| jnz .fail |
| xchg eax,ebx |
| call heap_remove_block |
| mov eax,[eax+memblock.size] |
| add [ebx+memblock.size],eax |
| mov eax,ebx |
| call heap_fix_right |
| pop ebx |
| .truncate: |
| xchg eax,ebx |
| call heap_split_block |
| test ebx,ebx |
| jz .no_last_block |
| mov eax,ebx |
| call heap_add_free_block |
| call heap_merge_right |
| .no_last_block: |
| xor ebx,ebx |
| pop eax |
| inc ebx |
| ret |
| .fail: |
| pop ebx |
| xor ebx,ebx |
| pop eax |
| inc dword [eax-8+memblock.size] |
| ret |
| |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| ;; mf_realloc |
| ;; input: |
| ;; eax - pointer |
| ;; ebx - new size |
| ;; output: |
| ;; eax - new pointer |
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| mf_realloc: |
| push ebx |
| if defined multithread |
| call heaplock |
| end if |
| call heap_try_reloc |
| test ebx,ebx |
| jnz .ret |
| ;allocate new memory |
| push eax |
| mov eax,[esp+4] |
| call mf_alloc |
| test eax,eax |
| jz .fail |
| push esi |
| push edi |
| push ecx |
| mov edi,eax |
| mov esi,[esp+12] |
| mov ecx,[esi-8+memblock.size] |
| shr ecx,2 |
| rep movsd |
| pop ecx |
| pop edi |
| pop esi |
| xchg eax,[esp] |
| call mf_free |
| .fail: |
| pop eax |
| .ret: |
| if defined multithread |
| call heapunlock |
| end if |
| pop ebx |
| ret |
| ;C entries |
| malloc: |
| mov eax,[esp+4] |
| call mf_alloc |
| ret |
| free: |
| mov eax,[esp+4] |
| call mf_free |
| ret |
| realloc: |
| mov edx,ebx |
| mov eax,[esp+4] |
| mov ebx,[esp+8] |
| call mf_realloc |
| mov ebx,edx |
| ret |
| section '.bss' writeable |
| heapsmallblocks rd 1 |
| heapstart rd 1 |
| heapend rd 1 |
| heapfreelist rd 1 |
| heapmutex rd 1 |
| heaplastblock rd 1 |