5

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 Page 17 of Datasheet explaining SRAM

How does this make 2k?

  1. 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?

Bence Kaulics
  • 6,353
  • 12
  • 33
  • 60
MaNyYaCk
  • 1,448
  • 1
  • 13
  • 28
  • 3
    0060 to 085F is 2K. As to why malloc insists on word aligning, you'd have to read the avr-libc documentation or source code. (Freeing and re-allocating single bytes would leave hopeless fragmentation, so that's the probable reason). But using malloc doesn't make much sense with only 2K memory. –  Dec 03 '16 at 18:04
  • EDIT: Just my guess. The architecture follows little Endian so the value starts getting stored from higher to lower address. Since it is a 8 bit controller, the data gets stored in address that is multiple of 8. – user3219492 Dec 03 '16 at 18:05
  • 2
    It's not unusual for C libraries to allocate in multiples of 4 or even larger. Especially on a 32-bit system. – pjc50 Dec 03 '16 at 18:08
  • Be careful about terminology - the ATMEGA32 doesn't know anything about malloc or dynamic memory management this is purely a function of the compiler. Other compilers than gcc may work differently. – Kevin White Dec 04 '16 at 00:12
  • @KevinWhite Noted. But I architecture makes a difference? – MaNyYaCk Dec 04 '16 at 06:49
  • @BrianDrummond What does that last statement mean? – MaNyYaCk Dec 04 '16 at 07:59
  • 3
    Using malloc on a microcontroller is nearly nonsensical. – whatsisname Dec 04 '16 at 09:04
  • @whatsisname Why is that so? – MaNyYaCk Dec 04 '16 at 09:10
  • Because http://electronics.stackexchange.com/questions/146298/what-happens-when-microcontrollers-run-out-of-ram/146364#146364 –  Dec 04 '16 at 10:38
  • Basically: because the standard says so – PlasmaHH Dec 04 '16 at 13:13
  • Noted. But I architecture makes a difference? – MaNyYaCk. @MaNyYaCk - Yes but the AVR architecture would allow 8bit granularity. The 32 bit granularity probably comes from other processors such as ARM/Intel that GCC is used for. – Kevin White Dec 04 '16 at 18:41
  • @MaNyYaCk: because microcontrollers, especially ones with 2k ram, are used in applications where all your memory usage should be known at design time, and statically allocated. – whatsisname Dec 04 '16 at 19:01
  • 1
    @MaNyYaCk Using malloc on a small microcontroller like this doesn't make any sense, [see this](http://electronics.stackexchange.com/questions/171257/realloc-wasting-lots-of-space-in-my-mcu/171581#171581). – Lundin Dec 05 '16 at 09:14

3 Answers3

10

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.

Tom Carpenter
  • 63,168
  • 3
  • 139
  • 196
  • 1
    I believe the extra two bytes are for the `sz` field which stores the size of the allocated chunk (which may be different from the requested size). See avr-libc-2.0.0 `malloc.c:176-179` where a new chunk is created. – Los Frijoles Dec 03 '16 at 21:49
  • So what's the way to calculate Stack and Heap available to me? I mean there's some documentation in AVR-Libc but I am finding hard to understand from where the head start and Heap end variables come and how to tune it. – MaNyYaCk Dec 04 '16 at 07:55
  • There would be a (non-standard) library function provided that traverses the freelist and provides statistics including the total size and largest block size. – JDługosz Dec 04 '16 at 08:27
  • @MaNyYaCk: look at the source code of the malloc function. – whatsisname Dec 04 '16 at 09:06
  • @JDługosz It seems like what I asked for is a lot deep subject and I need to read more. All help appreciated. Thanks :) – MaNyYaCk Dec 04 '16 at 09:11
  • I still recommend Knuth’s *The Art of Computer Programming*, §2.5. You can also start with [Wikipedia](https://en.wikipedia.org/wiki/Memory_management#DYNAMIC). – JDługosz Dec 04 '16 at 09:29
3

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.

JDługosz
  • 675
  • 1
  • 4
  • 12
1

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.

zx485
  • 230
  • 4
  • 9
user57037
  • 28,915
  • 1
  • 28
  • 81
  • 3
    For avr-libc, it's not actually returning multiples of 4. If I try to `malloc` on a non multiple of 4, it will increment by a non multiple of 4. For example if I call `malloc` three times in a row for 5 bytes each, the pointers will have incremented by 7 each time. In fact any request to `malloc` appears to allocate the larger of either 4 bytes or the required amount + 2 bytes. – Tom Carpenter Dec 03 '16 at 20:49
  • 1
    @TomCarpenter, very interesting. I am going to leave my answer up, though, because even if it doesn't apply in this case, I believe it may be a useful answer for others who find this question by search. – user57037 Dec 03 '16 at 21:04
  • @TomCarpenter Could you help me explaining why does it consume those extra bytes? I had tried that. What is extra two bytes for specifically? – MaNyYaCk Dec 04 '16 at 07:57