Author Topic: Heap and stack  (Read 1649 times)

0 Members and 1 Guest are viewing this topic.

Offline rakeshm55

  • Regular Contributor
  • *
  • Posts: 187
Heap and stack
« on: April 25, 2017, 04:42:17 pm »
In embedded system what is the difference between a heap and stack....Both would be residing in RAM...what are the variable stored in stack and heap.....Where does  store global variables get stored...
 

Offline rstofer

  • Super Contributor
  • ***
  • Posts: 6654
  • Country: us
Re: Heap and stack
« Reply #1 on: April 25, 2017, 06:09:50 pm »
Yes, it gets confusing, hoping I don't mess it up...

Starting at low RAM, there is a block of memory called .data for initialized global variables.  This is followed by a block of memory called .bss for uninitialized global variables.  The heap is assigned a block of memory just after the .bss variables.  The heap grows toward higher addresses and, hopefully, it doesn't grow without bound.

The stack grows from the top of RAM down (toward the heap).  It is used for all locally allocated variables such as those defined within a function.  When the function returns, the stack is cut back to where it was when the function was called.  Parameters are also passed on the stack as they are temporary as far as the function is concerned.  There's a bit more to the way function calls are made but this covers the high points.

The problem comes about when the heap and stack collide.  For that reason, I prefer to not have a heap.  That can be problematic because the GCC library uses the heap for string functions and things like printf() which uses string functions.  There are libraries around that do not assume the existence of a heap.  Personally, I rewrite the few string functions I need and write a little string->uart library.  Since I don't provide a heap manager, if GCC assumes its existence, I get a link error.

« Last Edit: April 25, 2017, 06:16:07 pm by rstofer »
 
The following users thanked this post: rakeshm55

Offline Fgrir

  • Regular Contributor
  • *
  • Posts: 113
  • Country: us
Re: Heap and stack
« Reply #2 on: April 25, 2017, 06:36:55 pm »
In embedded system what is the difference between a heap and stack....Both would be residing in RAM...what are the variable stored in stack and heap.....Where does  store global variables get stored...

It really depends a little bit on the particular environment but in general stack is implemented in the CPU and is used for temporarily storing data during function/interrupt calls.  Heap is implemented by the compiler/libraries and is used for dynamic memory allocation like malloc or new.  Global variables go somewhere else entirely...

 
The following users thanked this post: rakeshm55

Offline helius

  • Super Contributor
  • ***
  • Posts: 2859
  • Country: us
Re: Heap and stack
« Reply #3 on: April 25, 2017, 06:37:36 pm »
The heap is for dynamically allocated memory (malloc etc). You may be using malloc even if you don't call it directly, because library functions are using it. The heap arrangement can be different each time the system runs, depending on the order of calls to malloc and possible random inputs to the allocator.
The heap will be organized in blocks, some of which contain objects, and others being free/empty. Each block also contains housekeeping, like a pointer to the free block list. When you call malloc, it searches the heap for an empty block large enough to hold your requested object and allocates it. That's why you can run out of heap space even if you aren't using all the available memory: malloc searched for a large enough block but it wasn't found because the heap was fragmented into small empty regions.
These problems are sometimes enough to justify doing without dynamic allocation altogether (as would be the case in Fortran-77). For simple microcontroller programs it can sometimes be feasible.

The problem where the stack collides with the heap happens because stack operations are built into the processor and don't check their bounds (for typical processors). The heap won't be allowed to grow too much because the library (malloc) knows what size it can be and won't outgrow that size. But the processor will change the stack pointer as much as you ask it to, without checking whether that's a good thing to do. If you have a MMU, one solution is to make a "guard page" that occupies the lowest sensible stack address (the largest sensible stack) and faults to an error handler.
« Last Edit: April 25, 2017, 06:50:43 pm by helius »
 
The following users thanked this post: rakeshm55

Offline Cupcakus

  • Contributor
  • Posts: 43
  • Country: us
Re: Heap and stack
« Reply #4 on: April 26, 2017, 02:53:53 am »
To summarize all the responses here hopefully more clearly:

1. All embedded micros have some amount of RAM
2. All memory lives in RAM, all the heaps and the Stack
3. The stack is usually located at the end of memory, and grows backwards
4. Heaps are usually allocated starting from the beginning of memory and grow forward
5. The CPU has a special hardware register where it stores the current address of the stack
6. Values can be pushed onto the stack which will write to the end of RAM and then decrement the stack pointer.
7. Values can be read back off the stack by popping them back off which increments the stack pointer
8. This is typically what a C compiler does with local temporary values, it stores them on the stack.
9. The stack also holds all the function pointers so the CPU knows where in the code to jump back to when the current function returns.
10. A heap can be anything, typically it's just means all the memory in the device including the stack.
11. Standard C malloc manages one such heap and is fine for most purposes and will give you access to all of memory.  The disadvantage is memory fragmentation and excessive overhead for tracking the allocated blocks.
12. There are other types of heaps, but we can save that for later.
13.  A heap can grow into the stack, or vice versa.  The CPU does not track the heap, so it has no idea.  This is called a stack overflow and is very bad, and can be difficult to debug.
 
The following users thanked this post: rakeshm55

Offline jamie297

  • Contributor
  • Posts: 10
  • Country: gb
  • Factory tech & student
Re: Heap and stack
« Reply #5 on: April 26, 2017, 09:06:19 am »
Thanks all - this is useful stuff for me too. I'm learning C to start playing with PICs.

Can anyone recommend any good introductory article/textbook to memory management etc for embedded micros?
 

Offline rstofer

  • Super Contributor
  • ***
  • Posts: 6654
  • Country: us
Re: Heap and stack
« Reply #6 on: April 26, 2017, 08:32:39 pm »
That's a bit difficult without knowing which PIC and which toolchain.  For example, compilers for 16F chips are a lot less capable than compilers for the PIC32.  By capable, I mean feature rich.

If your compiler generates a .map file, look at it.  You will see where code is placed, where .data and .bss are placed and there is some equate that sets the value for the initial SP.

If your toolchain uses a linker script, there will be some great information in there regarding the size of RAM and FLASH as well as some reserved memory (sometimes).

I suspect that GCC is the most common compiler used for embedded programming even if it is wrapped up in a proprietary IDE.  You should be able to find a great deal of information on the Internet.  I don't think GCC supports PIC 16F.  If it does, it is more recent than the last time I played with the 16Fs.

Why use a PIC?  The ARM chips have more memory, a better toolchain, they're far faster and have better peripherals.  Considering volume manufactured, I suspect they are cheaper.  OTOH, they tend to be pretty complex.  The older ARM7-TDMI are pretty approachable - LPC2106, LPC 2148.  If you want to see some sample code for the LPC2148, wander over to www.jcwren.com/arm.  Sure, it isn't one of the newer Cortex ARMs but it's a pretty competent chip.
 
The following users thanked this post: jamie297

Offline jamie297

  • Contributor
  • Posts: 10
  • Country: gb
  • Factory tech & student
Re: Heap and stack
« Reply #7 on: April 27, 2017, 05:31:27 am »
Thanks  :-+  useful info. I am pretty much starting from scratch so it all helps.

Why use a PIC?  The ARM chips have more memory, a better toolchain, they're far faster and have better peripherals.
Honestly because I spent too long reading views on both sides instead of starting my learning, so I just bought one!
Eventually hope I'll try both but I'm at total basics right now so performance isn't going to be a problem.  :-/O
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf