For the version 0.6.0 of the EDDI Compiler, I have written a simple dynamic memory allocation function in assembly. I did that to avoid using malloc in my assembly code. As this is not an easy subject, this article will explain the main parts of writing this function.
As the EDDI Compiler creates program for Linux platform, this article will focus on writing a little memory allocator for Linux in Intel Assembly.
In this article I will follow the AT&T notation.
The function works like malloc but is simpler. The specifications are the following ones:
- We call the function with one argument: the dynamic memory size we need
- The function returns the start address of the allocated memory in the %eax register
- There is no need to deallocate the allocated memory
- The size that we ask will generally small and always less than 16384 octets
- Having some gaps in the memory is not a problem for now
So as you can see there are several limitations to this memory allocator. These limitations are the one I had for EDDI, so I'll follow them in this article.
Dynamic memory allocation
In Linux, there are two ways for performing dynamic memory allocation:
- brk: Increment the size of the data segment after the end of the program. This memory is directly after the program and is always contiguous. It's the easiest way for allocating memory. This technique is not perfect for large blocks of data.
- mmap: Creates a new memory mapping in the virtual address space. The kernel gives you memory in virtually every place of the memory.
In our case, as we need only small blocks, we will use brk to dynamically allocate memory.
We can call these procedures using system calls. In assembly, you can use system calls with interruptions (0x80).
We need two variables for this function. One to keep track of the remaining size and another one to keep track of the current address of the allocated memory.
.data .size VIeddi_remaining, 4 VIeddi_remaining: .long 0 .size VIeddi_current, 4 VIeddi_current: .long 0
Both variables are initialized to 0.
And here is the function I've developed :
eddi_alloc: pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx movl VIeddi_remaining, %ebx cmpl %ebx, %ecx jle alloc_normal movl $45, %eax xorl %ebx, %ebx int $0x80 movl %eax, %esi movl %eax, %ebx addl $16384, %ebx movl $45, %eax int $0x80 movl %esi, %eax movl $16384, VIeddi_remaining movl %esi, VIeddi_current alloc_normal: movl VIeddi_current, %eax movl VIeddi_current, %ebx addl %ecx, %ebx movl %ebx, VIeddi_current movl VIeddi_remaining, %ebx subl %ecx, %ebx movl %ebx, VIeddi_remaining leave ret
I will describe now each part of the alloc function.
movl 8(%ebp), %ecx movl VIeddi_remaining, %ebx cmpl %ebx, %ecx jle alloc_normal
In this part we test if there is enough remaining size for the dynamic memory allocation request. It's equivalent to if(remaining >= size). If there is enough size, we jump to the normal allocation part :
alloc_normal: movl VIeddi_current, %eax movl VIeddi_current, %ebx addl %ecx, %ebx movl %ebx, VIeddi_current movl VIeddi_remaining, %ebx subl %ecx, %ebx movl %ebx, VIeddi_remaining
First, we move the current address of memory into the %eax register for the return value. Then we add the size of the new allocated block to the current address. Finally we remove the size of the new allocated block from the remaining size. After that, we can leave the function.
The most interesting part is what we do when we have to allocate more memory :
movl $45, %eax xorl %ebx, %ebx int $0x80 movl %eax, %esi movl %eax, %ebx addl $16384, %ebx movl $45, %eax int $0x80 movl $16384, VIeddi_remaining movl %esi, VIeddi_current
We start by doing an interruption to execute a system call. The 45 in the %eax register indicates a sys_brk call. The 0 in the %ebx register, indicates that we want the current position of brk space. We save this current position into the %esi register. Then we add 16384 bits (4K octets) to this address. We call again the sys_brk routine to set the address of the brk space to the calculated address. This is the way to dynamically allocates 4K of memory. Finally, we add 4K to the remaining size in octets and we put the current address (before the add) as the current address.
We should make some optimization if this function has to be invoked frequently. The first interruption (call to sys_brk) has only to be done once. The very first time we need to get the start address. Then, we can use the current address as the base address when we do the new allocation.
Another improvement is to avoid having gaps between the used blocks. For that, we can avoid setting the current address directly to the newly allocated address but just add 4K to the remaining size. The blocks will overlap 2 allocated blocks.
We could also check that the value returned by the sys_brk is valid. On error, the procedure can return -1.
In this post, we developed a basic dynamic memory allocation function in Intel assembly on the Linux platform. I hope that this information can helps some of you.
Don't hesitate if you have a question or a comment on my implementation.