Dynamic memory allocation in Intel Assembly on Linux

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.

Specifications

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).

Implementation

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.

Possible improvements

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.

Conclusion

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.

Related articles