Why does my atmega32's malloc function returning me the pointer address in multiple of 4?

Question

I am in a learing phase so I am no pro when it comes to understanding the memory and hence I am having a little trouble in understanding few things

1. The datasheet of atmega32 says that it comes with 2K of SRAM

How does this make 2k?

2. When I ran the following code in an infinite loop until it returns 0, the malloc function returned me with addresses in multiples of 4 for Atmega32.

   p = (char*)malloc(sizeof(char));
   

   From what I am understanding , the char is of 1 Byte hence it should be giving me the adjacent addrresses instead?

Answer 1

For the first question:

There is 2kB of SRAM. There is an additional 32bytes of CPU registers, and a further 64bytes of I/O registers (things like the PORTA/DDRA/etc. registers).

Add these all up we get 2048+32+64 = 2144bytes of addressable memory. Convert that to hexadecimal you get 0x860 - or in address terms 0x000 to 0x85F.

The SRAM memory itself is the 2kB block from 0x060 to 0x85F.

For the second question:

malloc uses a so called "freelist" which maintains which chunks of memory are available to allocate or reallocated. This list is stored in the same SRAM as the memory you are allocating, and is updated on the fly as you use allocate memory.

Each entry in the freelist is a 16bit pointer, which points to the next entry forming a chain - each entry keeps track of where the next entry is - and a 16bit size which says how big the current block is.

As a result, each block of memory allocated using malloc must be at least 4 bytes in size in order to store the list entry. When you request a single byte of memory, it has to round that up to 4 bytes so that when that memory is deallocated, there is room for a list entry to be stored there.

Rather than go into exact details, the freelist approach is explained in the avr-libc documentation here. The following quote explains the need

The freelist itself is not maintained as a separate data structure, but rather by modifying the contents of the freed memory to contain pointers chaining the pieces together. That way, no additional memory is reqired to maintain this list except for a variable that keeps track of the lowest memory segment available for reallocation. Since both, a chain pointer and the size of the chunk need to be recorded in each chunk, the minimum chunk size on the freelist is four bytes

If you can't get your head around it (the process is not immediately obvious), you need not worry. The simple thing to remember is that each chunk you malloc will be at least 4 bytes in size, even if you only want 1.

---

Also worth noting after a bit of experimentation, the amount of memory allocated appears to always be the larger of either 4 bytes, or the requested amount + 2bytes. For example if you ask for 3 bytes, then 5 bytes will be allocated. If you ask for 8 bytes you will get 10.

As to why the extra 2 bytes are allocated, I am unsure. I cannot find reference to this in the avr-libc documentation.

Answer 2

Let me explain the more detailed results noted by Tom Carpenter in comments:

any request to malloc appears to allocate the larger of either 4 bytes or the required amount + 2 bytes

Any request needs an extra 2 bytes of overhead. This will record the size of the block, so free knows what exactly to reclaim. With 1-byte granularity and 2K to keep track of, you need 14 bits for this size. That fits in 2 bytes.

A node on the free list uses the free memory itself to keep track of the free memory. It needs the size, same as the allocated node. But it also needs a pointer to the next free node, which takes another 2 bytes. So, any block that is to be freed must be at least 4 bytes total (2 bytes given to use and 2 for the size of the allocated block).

So, if you ask for 1 byte, it must allocate 2 and take another 2 for overhead. More generally, it takes an extra 2 bytes for overhead and it never leaves a free block that would be too small for a free node. That is, if you asked for (say) 19 bytes and the free list had a node 24 bytes, it could not carve off 19+2 and leave 2+1 behind: it would allocate the whole thing even though it’s 3 bytes more than requested.

---

I’m familiar with how the heap works because back in 1983 or so I read Knuth’s The Art of Computer Programming and have implemented this on multiple occasions.

Answer 3

The issue is related to memory alignment. Often processors have a limitation that, when accessing a 32-bit data type, they must do so using an address which is a multiple of 4. This is just one example of an alignment constraint.

malloc() is required by the C standard to return an address with maximal alignment so that ANY data type can be stored at that address. malloc() does not know what data type you will use the address for.

So probably, malloc() is returning multiples of 4 because this processor requires it for some data types.

This question might actually be a better fit for a programming forum.