Author Topic: ATMega RAM management  (Read 2353 times)

0 Members and 1 Guest are viewing this topic.

Offline mstachoTopic starter

  • Supreme Robot
  • *****
  • Posts: 376
  • Helpful? 10
ATMega RAM management
« on: December 08, 2014, 03:50:25 PM »
Hi all,

this is a weird question, so please read the asterisk* at the end of the post before telling me it's not necessary to do this way :-)

If I write code like this (in Arduino, to make life easy):

int x = analogRead(A0);

then a new variable, x, is created.  x is of type int, and stores whatever value is read by the ADC on channel 0 somewhere in RAM.  My question is: what is it that allocates that memory?  I know that you can directly access and modify RAM just by using pointers, but what is the mechanism on the chip that does it?

I ask because I want to write my own little OS, and I feel like it will be fun to make my own memory manager so that people can script on it (like MATLAB, I want people to write their own little programs in a small environment, then have it run by allocating memory and following a program counter etc).  I know that this is painful, but I just want to know how these things are done, not to necessarily make a practical OS.  Any thoughts?

*Yes, I know, there is rarely a practical reason to do this.  I am more interested in writing this MMU because I want to see how hard it is and what things I need to consider, not because I think I can do better than the chip does it.
Current project: tactile sensing systems for multifingered robot hands

Offline Webbot

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,165
  • Helpful? 111
Re: ATMega RAM management
« Reply #1 on: December 11, 2014, 01:19:05 PM »
Big subject !

If you define a variable outside of any function it is called a 'global' variable - ie it exists, in the same memory slot, forever. The compiler will allocate a permanent location of it (and all others) starting from memory address 0 and growing upwards towards the end of memory. But there is one subtlety -   global variables come in two flavours: initialised and un-initiailised.

An initialised variable looks like this - ie you give it an initial value:
Code: [Select]
int x = 6;

whereas an unitialised variable looks like this:
Code: [Select]
int x;
In order to give 'initialised' variables their starting value then the compiler groups all of these variables together ie they stored one after the other starting from address 0 of the RAM. It then stores their initial values into a 'same size' block of flash/code memory. The compiler adds code that is executed when you boot up that copies these initial values from flash/code into RAM. Hence giving global variables an initial value will mean that not only do you need to  have RAM to store the changing value but it will also make your flash/code size bigger as it needs to store the initial values.

Unitialised variables on the other hand only require RAM and don't make your flash/code size any bigger. The compiler will group all global uninitialised variables together - starting after all of the initialised ones.

The compiler always adds magic variables to the flash/code saying how big the total size of all the initilised varbles is and also all the unitialised variables.

Hence when you turn on your board it will:
  • Copy x bytes from flash to RAM - starting at RAM address 0 - to give initialised variables their start value
  • Set the next y bytes - ie starting at RAM address x for the next y bytes - to zero. ie uninitialised variables are set to zero
  • The total size of your global variables is therefore x+y and marks the start of the 'heap'
  • If you dynamically allocate stuff using 'new' then it will start at the current value of 'heap' and 'heap' will be increased by the size of the thing you have created. NB to discuss the real workings of the heap would require a book sized reply!

Ok that's it for Global variables.

The next is 'Local' variables. ie variables defined  within a block (normally identified by matching open/close curly braces). This could be a function but could also be a for loop, while loop, etc or just braes with the code. The variable is only visible/referable within the block (else you get a compiler error). The variable therefore only really exists for the duration of the execution of the block.
Consider the following code:
Code: [Select]
void myFunction(void)
{ // Start block  level 1
    int x;
   {  // Start block level 2
       int y;
      // do something with 'y'
   } // End block level 2

  {  // Start block level 2
       int z;
      // do something with 'z'
   } // End block level 2

} // End block level 1

Whilst the variable 'x' is accessible everywhere in the function (block level 1) the variables y and z can never exist at the same time so they could use the same location in memory - ie by the time you get to using 'z' then 'y' is no longer required.

In C you could think of this as a struct/union (google is your friend) ie:
Code: [Select]
struct myFunctionData {
   int x; // always existss
   union {
      int y;
      int z;
   };
}
Assuming an 'int' is 2 bytes then the size of the 'union' is the size of its largesst member. Given that y and z are both 2 bytes then the answer is 2.  The total size of the struct is the sum of the things it contains ie 'int x'=2 bytes and the 'union' is 2 bytes - so only 4 bytes are needed (rather than 6 - because y and z can overwrite each other).

So the compiler works all of this out based on blocks of code.  ie 'x' is at block+0 length = 2, 'y' is t block+2 length =2, 'z' is t block +2 length =2.

But where does it get stored?

All this transient stuf gets stored on the stack.  The stack begins at the end of RAM and grows downwards. The current stack position is called the stack pointer (or SP for short) and is a special AVR register(s). The C compiler adds magic code to the start up to set the stack pointer to the end of RAM ie if your chip has 8kb then it sets it to 8kb ie  RAM Location 0 + 8192 = 8192.

When compiling the above function we have already discussed that only 4 bytes are required for the local variables. So the compiler adds code to reduce the SP by 4 ie SP=SP-4. The local/temporary variable 'x' is therefore at SP+0 and both 'y' and 'z' are at SP+2. The compiler also adds magic code to the end of the function to throw these variables away. By doing SP=SP+4. ie when exiting the function the SP is the same as it was before it was called. This is important as it may be called from another function which is accessing its own variables via the SP.

Of course if you nest function calls to umpteen levels then the SP will get lower and lower in RAM towards the end of the global variables tht have grown up from the start of RAM.  If the two overlap then you will start to corrupt the global variables. On PC compilers, where you always have a screen/output device, you can make a function check if this has occurred and you get the dreaded 'Stack Overflow' error at runtime. On a microcontroller the compiler cannot assume you have any display device connected so it can't send this error message anywhere sensible and hence doesn't bother  it will just let you corrupt stuff. This also keeps the code smaller as the compiler doesn't even bother adding the code to check if a collision has happened.

Function parameters add a further twist. In effect they are similar to block level 0 temporary variables in that they are accessible throughout the function. The difference is that the calling code will push their values onto (and hence reduce) the SP. So they become initialised local variables to the function on entry. This begs the question as to who/what removes them from the SP and this can be compiler specific. In theory - if the parameters are of a fixed total size, lets say 12 bytes, then the compiler can add magic code to the called function so that it always sets SP=SP+12 before it exits to remove the parameters. This is more efficient as it only adds the overhead of this code once - whereas if the caller had to do it, and it was called from 100 different places, then code would be added 100 times.

Hopefully that makes some sort of sense. Feel free to ask some questions but if its all nonsense then you may need to research compiler design.


« Last Edit: December 11, 2014, 02:00:46 PM by Webbot »
Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

Offline mstachoTopic starter

  • Supreme Robot
  • *****
  • Posts: 376
  • Helpful? 10
Re: ATMega RAM management
« Reply #2 on: December 11, 2014, 02:22:12 PM »
Wow, that was great!  Thanks a lot.  I'm starting to realize the authority that the compiler has in these matters (so yes, the next step is to better research compilers).

If I understood all of this correctly, then:

1) If I never use dynamic memory allocation, then the heap will only store global variables.
2) All local variables are pushed onto the stack.  The "magic code" you were talking about, I assume, deals with what happens when the "RET" instruction is called, is that right?  Is it something like this:

a) Make all local variables
b) run the function appropriately
c) upon encountering a RET instruction...I assume that the program memory contains things like how far to move the stack pointer to get to the return address of the function?
d) The above assumed that no dynamic memory allocation occurred

3) There is no memory manager on an ATMega, so I assume that this is all handled at compile time.  This means that dynamic memory allocation *and deallocation* will eventually use up all the memory even though there is still space available in the freed spots on the heap, right?  I assume this because of my (perhaps flawed) understanding:

a) malloc makes a new variable
b) dealloc/free frees that memory, but the heap pointer has already moved on
c) if we then malloc a few new variables, the original variable's space is a "hole" in the heap.  but there is nothing in the processor telling us that, so it just assumes that the heap is filling up (dealloc did nothing?)

Definitely time to keep reading.

Mike
Current project: tactile sensing systems for multifingered robot hands

Offline Webbot

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,165
  • Helpful? 111
Re: ATMega RAM management
« Reply #3 on: December 11, 2014, 03:14:35 PM »
Quote
1) If I never use dynamic memory allocation, then the heap will only store global variables.
- Correct

Quote
2) All local variables are pushed onto the stack
etc. Correct other than
Quote
d) The above assumed that no dynamic memory allocation occurred
. Magic code will clean up the SP for local vars but if you have dynamically created  stuff via malloc(C) or 'new'(C++) then it is up to you to manage its life-cycle and make sure you free/delete it when needed. This dynamic stuff is on the heap - ie consider a function that contains:
Code: [Select]
foo = malloc(10); where 'foo' is a global variable. ie the function will not clean up these 10 bytes as they have been given to global 'foo' that may be accessed in other functions. So any dynamic malloc/calloc/new things then its your responsibility to free them at athe appropriate time. Compiler only auto-tidies local vars and function parameters.

Quote
3) There is no memory manager on an ATMega
You are correct. Because of the 'block' nature of local variables/parameters then its like a stack of plates - you push on - and pull off - and the compiler does this for you on the stack. Dynamic allocation on the heap via malloc/calloc/new is way more complex (as I said - it's a book). The implementation is up to the compiler - it nrmally uses a linked list to iterate the used memory blocks and another linked list of previously allocated, but now freed, blocks. You are right in that freeing blocks may create holes. The allocation process will often try to find an existing 'hole' of the required size and then re-use it. But this isn't a simple choice. Say you need 10 new bytes and there is a hole of 12 bytes. Do you grab 10 and leave 2 or do you extend the heap for a fresh 12 bytes. This is all very compiler specific in implementation - and since AVR has no MMC - you can ednd up, over time, with memory fragmentation (just like a hard drive) - ie you need 100 bytes but all you've got is 50 x fragmented blocks of 2 bytes ie 100 bytes in total but not contiguous. This is a very complex issue - and hence why many folk say don't use dynamic allocation on a microcontroller - as the logic to handle it can be bigger than the total flash/code space on the chip!!

I note that Arduino now has a String class that uses dynamic allocation- which IMHO is suicide, as if your prog runs for a long time then it will eventually fail due to fragmentation.

If you want I can describe how a MMU works - ie change from early 8086 chips (no MMU)  to newer 80x86 chips (with hardware MM). The 'sad' news is that there is no way (I know of) to achieve the same thing in software other than at O/S hardware level. eg the Java JVM does its own memory allocation and so suffers the exact same frag issue. eg if the JVM needs 100Mb then the host O/S MMU can give it a logical block of 100Mb (which may be mapped all over the place in physical memory) but Java then handles the breakdown (dynamic allocation) of this via software and is therefore subject to fragmentation - and hence you get the Java 'stop the world' events when it cannot honour a new memory allocation. Everything freezes whilst it does a software de-frag to slide all the used RAM together and consolidate the total unused RAM into one block.
Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

Offline mstachoTopic starter

  • Supreme Robot
  • *****
  • Posts: 376
  • Helpful? 10
Re: ATMega RAM management
« Reply #4 on: December 11, 2014, 03:25:04 PM »
Again, this is great. Thanks for all this.

One nagging question I still have and can't quite answer is this:

Let's say that the heap is indeed allocated as you say: two linked lists. Now, if I do this:

int *x = malloc(sizeof(int));
*x = 4;
int y = *x;

x is a new variable, but its name was known at compile time...I'm not even sure how to ask this question, but: what is it that stores the symbols and their addresses?  That is, in the third line above, is it hard coded by the compiler where the program should look for the variables x and y?  Is it different for variables that are dynamically allocated compared to statically allocated?

I can imagine that y, being statically allocated, always resides in a known address and so the hex file may contain a static reference to it.  But x, being dynamic, will have a new memory address that isn't known at compile time.  Since the third line above requires the processor to load y and x into registers, what is it that stores this new memory address for x and, more important, how is that indicated at compile-time?  Is there some sort of memory space that holds uninitialized pointers that the program then looks up once they are used?

Does that question make any sense?

Oh, and a final question so I stop bugging you :-P Where do you learn all of this?  I've been searching for information on the atmel website about this, but all they say is that there is such a thing as the stack and the heap, but not much else.  is there a fundamental topic I'm missing that I can go find a good book on?

Mike
« Last Edit: December 11, 2014, 03:27:00 PM by mstacho »
Current project: tactile sensing systems for multifingered robot hands

Offline Webbot

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,165
  • Helpful? 111
Re: ATMega RAM management
« Reply #5 on: December 11, 2014, 03:40:14 PM »
Is this code inside a function? ie are x and y local to the function - I'm guesing that they are ie
Code: [Select]
void foo(void)
{
   int *x = malloc(sizeof(int));   
   *x = 4;
i  nt y = *x;
}
Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

Offline mstachoTopic starter

  • Supreme Robot
  • *****
  • Posts: 376
  • Helpful? 10
Re: ATMega RAM management
« Reply #6 on: December 11, 2014, 03:45:48 PM »
Yes, let's assume they are local.  I suspect that makes it weirder?

Mike
Current project: tactile sensing systems for multifingered robot hands

Offline Webbot

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,165
  • Helpful? 111
Re: ATMega RAM management
« Reply #7 on: December 11, 2014, 04:20:34 PM »
The compiler knows there are two local variables in the function block called:-
x - who's size is that of an (int *). For ATtinys this may be 8 bit, for other AVRs is probably 16 bit (thats why you need to tell the compiler the mcu !). But lets assume its a 16 bit  (2 byte) address.
y - is just a local variable of type 'int' -say 2 bytes.

So it knows their name - but has no idea where in (absolute) memory they will be stored as they are not global. As locals then all the compiler can infer is their offset from the SP - ie they are relative to whatever the SP is - and is indirected via this register(s)
Assume x is at SP+0 and y is at SP+2 then the compiler will produce something like (in very rough pseudo code)
Code: [Select]
  SP = SP-4; // make space on the stack for local vars x and y
  SP[0] = malloc(2); // x = malloc
  *(SP[0]) = 4;  // assign value to x
  SP[2] = *(SP[0]);  // y = *x
  SP = SP + 4; // Discard local x,y variables

So to summarise: local vars have no 'fixed' address they are only relative to the SP. If in doubt then think of recursion - where a function can call itself but the caller and the callee need their own values of the variables.

Quote
I can imagine that y, being statically allocated, always resides in a known address and so the hex file may contain a static reference to it
Nope - y is 'local' to the function so its address is relative to SP and not fixed. Only global vars have a fixed address and, since they permanently hold onto memory, then you should use as few of them as possible! Global vars, especialy when using an OO lang like C++, are a debugging nightmare - I never use them.

Quote
Where do I learn this stuff?
- 30 years of writing it ! micro-controllers are just smaller PC's after all. And a heck of a lot of assembler/low level coding, blood, sweat and tears!

A slightly more helpful answer would be: turn off all code optimisations in your compiler (or WebbotLib Studio). Write a very simple program. Compile it. Look at the .lst file which will show the assembly language op-codes. Refer to the Atmel datasheets to understand what the generated instructions are actually doing. Tweak th coe - analyse chnges. Once you ot your head around it - turn on optimisation. You may see that if a variable is never read then all of the code that writes new values to it gets removed - ie whats the point!
« Last Edit: December 11, 2014, 04:31:33 PM by Webbot »
Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

Offline mstachoTopic starter

  • Supreme Robot
  • *****
  • Posts: 376
  • Helpful? 10
Re: ATMega RAM management
« Reply #8 on: December 12, 2014, 08:30:06 AM »
Fascinating stuff.  thanks for your help.  I'll start playing around soon :-)

Mike
Current project: tactile sensing systems for multifingered robot hands

Offline mklrobo

  • Supreme Robot
  • *****
  • Posts: 516
  • Helpful? 14
  • From Dream to Design at the speed of Imagination!
Re: ATMega RAM management
« Reply #9 on: March 29, 2015, 08:23:00 AM »
 :) good information! I will have to look into this!

 


Get Your Ad Here