x86_64 critiche nasm su malloc e implementazione gratuita
Ho realizzato la mia implementazione malloc utilizzando questa risorsa come guida https://danluu.com/malloc-tutorial/Speravo di ricevere qualche feedback su come posso migliorarlo e se ho fatto errori importanti. So che la mia implementazione ha molta frammentazione e praticamente non ho idea di come risolverla.
TLDR
- Feedback sulla mia implementazione _malloc e _free.
- Qualcuno ha un buon debugger che può essere utilizzato per eseguire il debug del codice 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
Risposte
Se ho fatto degli errori importanti.
Dipende dal fatto che tu voglia seguire o meno le convenzioni di chiamata a 64 bit di Linux. Attualmente si utilizza lo stack per il passaggio di parametri tra le funzioni, dove la normale convenzione di chiamata pone i primi 6 parametri nei registri RDI, RSI, RDX, RCX, R8, e R9. Credo che il tuo codice trarrebbe vantaggio dal seguire le convenzioni.
Dove devi seguire le convenzioni è nella tua funzione sbrk che esegue 2 chiamate di sistema Linux. Tra una chiamata e r8l'altra hai conservato un valore nel registro ma stai dimenticando che le convenzioni di chiamata a 64 bit di Linux dicono che questo è un registro zero che SYSCALL_BRK è libero di distruggere! Basta salvare il valore nello stack.
Errata corrige: A quanto pare SYSCALLnon è una "chiamata" nel senso tradizionale e sempre e solo clobbers RAX, RCXe R11. Ciò significa che la tua scelta R8va bene. Vedi la risposta di Peter Cordes sull'argomento.
Feedback sulla mia implementazione _free .
Questa è una versione davvero minimalista. Stai riponendo molta fiducia nell'utente (tu stesso). Come puoi essere sicuro che l'indirizzo che forniscono punti a un'assegnazione valida?
Un modo sicuro per farlo è seguire la catena di allocazioni e solo quando incontri l'indirizzo inviato liberi tale allocazione.
Feedback sulla mia implementazione di _malloc .
Questo d'altra parte è un codice eccessivamente complesso che dipende dall'uso ingegnoso di modificare e / o riciclare i parametri di input impilati.
È facile perdersi in questo codice.
Se si inizializzassero solo una volta le variabili global_base e current_sbrk all'avvio del programma, ridurrebbe già molto la complessità. es . Eliminerebbe le successive chiamate di sistema in ._sbrk .
E perché non utilizzare il puntatore dello stackframe _mallocRBP per le subroutine locali ._requestSpace , ._findFreeBlock e ._sbrk ? Quindi puoi fare a meno di tutti quei prologhi ed epiloghi.
Speravo di ricevere qualche feedback su come posso migliorarlo
Il miglioramento più grande che puoi apportare è strutturale e ti richiederà di riscrivere il lotto ma alla fine sarà molto gratificante ...
Sebbene il tutorial abbia utilizzato un elenco collegato, non è necessariamente il modo migliore per gestire i metadati. Avere sia un puntatore al blocco successivo che una dimensione del blocco, è come memorizzare due volte le stesse informazioni (e tenerle aggiornate anche!).
Se si mantiene solo il prossimo campo, allora si ottiene la dimensione tramite:
size = next - (current + META_SIZE)
Se mantieni solo un campo delle dimensioni , ottieni quello successivo tramite:
next = current + META_SIZE + size
Fatevi un favore e memorizzate solo le dimensioni del blocco. È la soluzione più semplice.
Poi viene l'allineamento. La tua attuale implementazione utilizza un META_SIZE di 17 byte. Questo è un vero disastro quando si tratta di prestazioni del programma! Avere sempre la memoria che il chiamante richiede allineata a un valore ottimale come ad esempio qword o dqword. Sceglierei quest'ultimo e userei next struc:
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
In questo modo è possibile rendere la dimensione del blocco richiesta un multiplo di 16 secondo il META_SIZE scelto (che deve essere una potenza di 2):
; RDI is the requested allocation size
add rdi, META_SIZE - 1
and rdi, -META_SIZE
Alcuni miglioramenti al codice includono
Codice come:
mov rdx, rax
add rdx, block_meta.free
mov byte[rdx], 0
...
mov r10, block_meta.free
cmp byte[rax + r10], 0
può essere scritto come:
mov byte[rax + block_meta.free], 0
...
cmp byte[rax + block_meta.free], 0
E nel tuo codice _printInt puoi eliminare alcune istruzioni controllando un numero negativo come ti ho mostrato in una mia risposta precedente . Raccogliendo il risultato del test una seconda volta dopo che la cifra è stata raccolta nella pila e anteponendo il carattere "-", è possibile emettere il lotto in un'operazione SYSCALL_WRITE invece di due.
E ovviamente rilascia i tag ridondanti delle dimensioni, metti le tue definizioni in cima in modo da poterle usare ovunque, non dimenticare global _free, cancellare un registro usando xor edi, edi, ecc ...
Ad esempio, questo è il modo in cui programmerei ._findFreeBlock . Il codice attraversa la memoria tra global_base e current_sbrk controllando un blocco libero che sia abbastanza grande. Se trovato, RAXcontiene l'indirizzo dei metadati e, se non trovato, RAXè 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 un blocco è libero, controlla i blocchi su entrambi i lati. Se un blocco adiacente non viene assegnato, uniscilo al blocco liberato. Questo dovrebbe aiutare con la frammentazione.