x86_64 nasm criticism on malloc e implementação gratuita
Eu fiz minha própria implementação de malloc usando este recurso como um guia https://danluu.com/malloc-tutorial/Eu esperava receber algum feedback sobre como posso melhorar isso e se cometi algum erro grave. Sei que minha implementação tem muita fragmentação e não tenho ideia de como consertá-la.
TLDR
- Feedback sobre minha implementação _malloc e _free.
- Alguém tem algum bom depurador que possa ser usado para depurar código nasm x86_64
bits 64
%define NULL 0
%define SYSCALL_BRK 12
struc block_meta
.next resq 1 ;pointer to the next block of "block_mata" struct
.size resq 1 ;how many bytes can this block hold
.free resb 1 ;is this block free (0 == no its not free) (1 == yes its is free)
endstruc
META_SIZE equ 17 ;the size of block_meta in bytes
section .data
global_base dq NULL ;pointer to the first "block_meta" struct
current_sbrk dq 0
section .text
global _start
global _malloc
_start:
push 400
call _malloc ;allocationg 100 dwords aka 400 bytes(array of 100 dwords). rax contains pointer
mov r15, rax ;saving pointer of array
;test program where we loop through the array and store 0 - 99 in each pos
xor ebx, ebx
._L1:
mov [r15 + rbx * 4], ebx
._L1Cond:
inc ebx
cmp ebx, 100 ;when ebx reaches 100 we have reached the end of the array
jl ._L1
xor ebx, ebx
;print out the array
._L2:
mov eax, [r15 + rbx * 4]
push rax
call _printInt
add rsp, 8
call _endl
._L2Cond:
inc ebx
cmp ebx, 100
jl ._L2
push r15
call _free
add rsp, 16 ;clear the stack
mov rax, 60 ;SYSCALL_EXIT
mov rdi, 0
syscall
;(first)last argument pused onto the stack must be the amount of bytes
;if successfull then rax will contain pointer to the memory
_malloc:
;prolog
push rbp
mov rbp, rsp
;actual code
cmp qword[rbp + 16], 0 ;compare with first argument
jle ._mallocEpilog ;if zero of negetive exit
cmp qword[global_base], NULL ;if the global_base pointer is "NULL" aka 0 allocate space
jz ._setGlobal_Base
;if global_base is not "NULL"
push qword[rbp + 16] ;how many bytes big does the block need to be
push qword[global_base] ;pointer to "meta_data" struct
call ._findFreeBlock
test rax, rax ;if zero no block was found. need to call ._requestSpace if zero
jz ._needMoreSpace
;found free block
mov rdx, rax ;save the pointer to memory block
add rdx, block_meta.free ;set the block to be not free
mov byte[rdx], 0
jmp ._mallocExit
._needMoreSpace:
call ._requestSpace ;we did not find a big enoug block. so make sapce
jmp ._mallocExit
._setGlobal_Base: ;will be used first time malloc is called
push qword[rbp + 16] ;how many bytes does the user want to reserve
push NULL ;the global_base pointer has not been set
call ._requestSpace
mov [global_base], rax ;save the pointer
._mallocExit:
add rsp, 16 ;clean the stack
add rax, META_SIZE ;add offset because of the "meta_block" struct
._mallocEpilog:
;epilog
pop rbp
ret
;(fist)last agument on the stack must be pointer to the last "block_meta" struct
;second argument must be the size in bytes that need to be allocated
;returns pointer to memory block in rax
._requestSpace:
;prolog
push rbp
mov rbp, rsp
mov rdi, [rbp + 24] ;how many bytes for the user
add rdi, META_SIZE ;extra bytes for meta data
push rdi
call ._sbrk ;rax will contain the pointer
add rsp, 8 ;clear stack
mov r8, block_meta.next ;putting the offsets in the register for later use
mov r9, block_meta.size
mov r10, block_meta.free
mov qword[rax + r8], NULL ;just setting it to NULL to get rid of garbage data for the next
cmp qword[rbp + 16], NULL ;the last "block_meta" pointer is NULL then jmp
jz ._fillMetaData
mov rcx, [rbp + 16] ;the current last "block_meta" struct in the list
mov qword[rcx + r8], rax ;mov pointer of allocated memory into next pointer of struct
._fillMetaData: ;setting all the other fields in the struct
mov rdi, [rbp + 24] ;how many bytes for the user
mov qword[rax + r9], rdi ;setting the size field of the struct
mov byte[rax + r10], 0 ;setting the free field to be 0 of struct
;epilog
pop rbp
ret
;(fist)last argument on the stack must be pointer to "block_meta" struct
;second argument is how big the block needs to be
;if successfull then rax will contain pointer to the block
;if failure the rax will contain pointer to the last block of "block_meta" struct
._findFreeBlock:
;prolog
push rbp
mov rbp, rsp
mov rax, [rbp + 16] ;pointer to the "block_meta" struct
mov rdx, [rbp + 24] ;how big do you need the block to be
mov r8, block_meta.next ;offset
mov r9, block_meta.size
mov r10, block_meta.free
jmp ._findFreeBlockLoopCond
._findFreeBlockLoop:
mov [rbp + 16], rax ;save current pointer in argument 1
mov rax, [rax + r8] ;go to the next "block_meta" struct
._findFreeBlockLoopCond:
test rax, rax ;if rax is zero we have reached the end of the linked list. exit
jz ._findFreeBlockExit
cmp byte[rax + r10], 0 ;if zero then block is not empty. loop again
jz ._findFreeBlockLoop
cmp [rax + r9], rdx ;if the current block has does not have enough space loop again.
jl ._findFreeBlockLoop
._findFreeBlockExit:
;epilog
pop rbp
ret
;(fist)last argument must be how much space do you want to reserve
;return pointer in rax
._sbrk:
;prolog
push rbp
mov rbp, rsp
;actual code
mov rax, SYSCALL_BRK ;using brk to get initilial address
mov rdi, [current_sbrk] ;starts at 0. gets updated later
syscall
mov r8, rax ;save for later
mov rax, SYSCALL_BRK
mov rdi, [rbp + 16] ;first argument (how many bytes)
add rdi, r8 ;needs to start at teh address we saved
syscall
mov [current_sbrk], rax ;next time will start at this address
mov rax, r8 ;restore pointer to the memory
;epilog
pop rbp
ret
;(first)last arguemnt on the stack must be the pointer you want to deallocate memory for
_free:
;prolog
push rbp
mov rbp, rsp
;I will be calling the pointer in rax to be the "original block"
mov rax, [rbp + 16] ;pointer to memory that needs to be deallocated
sub rax, META_SIZE ;offset to find the "block_meta" struct
mov rcx, rax
add rcx, block_meta.free ;offset to set free to be 1
mov byte[rcx], 1
._freeEpilog:
;epilog
pop rbp
ret
;print methods for testing!
%define STDIN 0
%define STDOUT 1
%define STDERR 2
%define SYSCALL_READ 0
%define SYSCALL_WRITE 1
%define SYSCALL_EXIT 60
section .data
endl db 10
endlLength equ $ - endl
;no input needed
;just an end line "method"
_endl:
mov rax, SYSCALL_WRITE
mov rdi, STDOUT
mov rsi, endl
mov edx, endlLength
syscall
ret
;last value pushed to stack will be printed
_printInt:
;prolog
push rbp
mov rbp, rsp
;save registers
push rbx
;actual code
mov rsi, rsp
mov rax, [rbp + 16] ;get the value that user wants to print
mov rbx, 10 ;will be used to divide by 10 later
xor rcx, rcx
cqo
cmp rdx, -1 ;check to see if negetive
jne _divisionLoop ;if not negetive jump
;print negetive sign
dec rsi
mov [rsi], byte '-'
mov rax, SYSCALL_WRITE
mov rdi, STDOUT
mov rdx, 1
syscall
inc rsi
;convert to positive number
mov rax, [rbp + 16] ;get the value that needs to be printed
neg rax ;make it a positive
xor rcx, rcx
_divisionLoop:
xor rdx, rdx
div rbx ;divides number by 10 to move over last digit into rdx reg
add dl, '0' ;add the '0' to ascii to convert into ascii val
dec rsi
mov [rsi], dl
inc rcx ;count for how many digits added to stack
test rax, rax
jnz _divisionLoop ;jump if the division did not result in a zero
;print all the values
mov rax, SYSCALL_WRITE
mov rdi, STDOUT
mov rdx, rcx
syscall
;restore register
pop rbx
;epilog
pop rbp
ret
Respostas
Se cometi algum erro grave.
Depende se você deseja seguir as convenções de chamada do Linux de 64 bits ou não. Atualmente você está usando a pilha para passagem de parâmetros entre suas funções, onde a convenção de chamada normal, coloca a primeira 6 parâmetros nos registros RDI, RSI, RDX, RCX, R8, e R9. Acredito que seu código se beneficiaria em seguir as convenções.
Onde você deve seguir as convenções está em sua função sbrk que faz 2 syscalls do Linux. Entre as chamadas, você preservou um valor no r8registro, mas está se esquecendo de que as convenções de chamada do Linux de 64 bits dizem que este é um registro de rascunho que o SYSCALL_BRK está livre para derrubar! Basta salvar o valor na pilha.
Errata: Aparentemente SYSCALLnão é uma "chamada" no sentido tradicional e sempre apenas clobbers RAX, RCXe R11. Isso significa que sua escolha de R8está bem. Veja a resposta de Peter Cordes sobre o assunto.
Dê feedback sobre minha implementação _free .
Esta é uma versão verdadeiramente minimalista disso. Você está colocando muita confiança no usuário (você mesmo). Como você pode ter certeza de que o endereço que eles fornecem apontará para uma alocação válida?
Uma maneira segura de fazer isso é seguir a cadeia de alocações e somente quando você encontrar o endereço enviado, você liberará essa alocação.
Feed back on my _malloc implementação.
Por outro lado, este é um código excessivamente complexo que depende do uso engenhoso de modificação e / ou reciclagem dos parâmetros de entrada empilhados.
É fácil se perder neste código.
Se você inicializar apenas uma vez as variáveis global_base e current_sbrk na inicialização do programa, isso já diminuiria muito a complexidade. por exemplo, eliminaria as sucessivas chamadas em ._sbrk .
E por que não usar o ponteiro _malloc stackframe RBPpara as sub-rotinas locais ._requestSpace , ._findFreeBlock e ._sbrk ? Então você pode passar sem todos esses prólogos e epílogos.
Eu esperava receber algum feedback sobre como posso melhorar isso
A maior melhoria que você pode fazer é estrutural e vai exigir que você reescreva o lote, mas no final será muito recompensador ...
Embora o tutorial use uma lista vinculada, essa não é necessariamente a melhor maneira de gerenciar seus metadados. Ter um ponteiro para o próximo bloco e também um tamanho de bloco é como armazenar a mesma informação duas vezes (e mantê-la atualizada também!).
Se você mantiver apenas um próximo campo, obterá o tamanho por meio de:
size = next - (current + META_SIZE)
Se você mantiver apenas um campo de tamanho, obterá o próximo por meio de:
next = current + META_SIZE + size
Faça um favor a si mesmo e guarde apenas o tamanho do bloco. É a solução mais simples.
Em seguida, vem o alinhamento. Sua implementação atual usa um META_SIZE de 17 bytes. Este é um verdadeiro desastre quando se trata de desempenho do programa! Sempre tenha a memória que o chamador solicita alinhada em um valor ideal, como dizer qword ou dqword. Eu escolheria o último e usaria a próxima estrutura:
struc block_meta
.size resq 1 ; how many bytes can this block hold
.free resb 1 ; (0 == it's not free) (1 == it's free)
.pad resb 7
endstruc
META_SIZE equ 16
É assim que você pode tornar o tamanho do bloco solicitado um múltiplo de 16 de acordo com o META_SIZE escolhido (que deve ser uma potência de 2):
; RDI is the requested allocation size
add rdi, META_SIZE - 1
and rdi, -META_SIZE
Algumas melhorias de código incluem
Código como:
mov rdx, rax
add rdx, block_meta.free
mov byte[rdx], 0
...
mov r10, block_meta.free
cmp byte[rax + r10], 0
pode ser escrito como:
mov byte[rax + block_meta.free], 0
...
cmp byte[rax + block_meta.free], 0
E em seu código _printInt você pode eliminar algumas instruções, verificando se há um número negativo da maneira que mostrei em uma resposta minha anterior . Pegando o resultado do teste uma segunda vez depois que o dígito foi coletado na pilha e acrescentando o caractere "-", você pode enviar o lote em uma operação SYSCALL_WRITE em vez de duas.
E, claro, elimine as tags de tamanho redundante, coloque suas definições no topo para que possa usá-las em qualquer lugar, não se esqueça global _free, limpe um registro usando xor edi, edi, etc ...
Por exemplo, é assim que eu programaria ._findFreeBlock . O código percorre a memória entre global_base e current_sbrk, verificando se há um bloco livre grande o suficiente. Se for encontrado, RAXcontém o endereço dos metadados e, se não for encontrado, RAXserá zero.
; IN (rdi) OUT (rax) MOD (rdx)
._findFreeBlock:
mov rax, [global_base]
jmp .Start
.Loop:
mov rdx, [rax + block_meta.size]
cmp byte [rax + block_meta.free], 1 ; (1 == it's free)
jne .Next ; Block is not free
cmp rdx, rdi
jae .Exit ; Free block is large enough
.Next:
lea rax, [rax + META_SIZE + rdx]
.Start:
cmp rax, [current_sbrk]
jb .Loop
xor eax, eax ; Not found
.Exit:
ret
Quando um bloco é liberado, verifique os blocos de cada lado. Se um bloco adjacente não estiver alocado, mescle-o com o bloco livre. Isso deve ajudar na fragmentação.