Go Down

Topic: modify freeRam() to find fragmentation (Read 10363 times) previous topic - next topic

Thomas499

#75
Dec 27, 2015, 09:20 pm Last Edit: Dec 27, 2015, 09:23 pm by Thomas499
Thats what I thought, but I saw that it was defined so I wasn't sure if the arduino library automatically reserved that space for it or not in the heap. If it was reserved, I wouldn't be able to do
Quote
int free=freeRam();
char Temp[free-2];
without the program crashing.

So to figure out if I truely understand this, would this way be more accurate?

Quote
(int)&v-&__bss_end-(int) &__heap_start-getMemoryUsed()
Also, is there a way to figure out the address of the next block using something like this?
Quote
// memory free'd by you is collected in the free list and
// compacted with adjacent blocks. This, combined with malloc's
// intelligent picking of candidate blocks drastically reduces
// heap fragmentation. Anyway, since blocks in the free list
// are available to you at no cost we need to take them off.
 
  for(fp=__flp;fp;fp=fp->next)
    used-=fp->sz+sizeof(size_t);

nickgammon

As I mentioned on this page:

Quote
The heap safety margin is a buffer between the top of the heap and the bottom of the stack. Without it, if you did a "malloc" and got all available memory, there would be no memory left for function calls and local variables in functions.
Effectively a malloc pretends that it can't use that part of memory, even though it isn't in use by the stack ... yet.
Please post technical questions on the forum, not by personal message. Thanks!

More info: http://www.gammon.com.au/electronics

Thomas499

Quote
The heap safety margin is a buffer between the top of the heap and the bottom of the stack. Without it, if you did a "malloc" and got all available memory, there would be no memory left for function calls and local variables in functions.
I read your page it was very helpful. I guess the words "__malloc_margin" didn't jump out at me when I read that. But aren't function calls and local variables assigned in
Quote
dataSize  = (int) &__data_end  - (int) &__data_start;  // fragmented SP-
 bssSize   = (int) &__bss_end   - (int) &__bss_start;
which is a lot more accurate than a the guess malloc_margin uses?


nickgammon

There is no guessing there. From the source in malloc.c:

Code: [Select]
/*
* Step 3: If the request could not be satisfied from a
* freelist entry, just prepare a new chunk.  This means we
* need to obtain more memory first.  The largest address just
* not allocated so far is remembered in the brkval variable.
* Under Unix, the "break value" was the end of the data
* segment as dynamically requested from the operating system.
* Since we don't have an operating system, just make sure
* that we don't collide with the stack.
*/
if (__brkval == 0)
__brkval = __malloc_heap_start;
cp = __malloc_heap_end;
if (cp == 0)
cp = STACK_POINTER() - __malloc_margin;
if (cp <= __brkval)
  /*
   * Memory exhausted.
   */
  return 0;


It subtracts __malloc_margin from the stack pointer, effectively giving exactly that amount of memory less for the heap. In other words, it allows for the stack to grow by that amount without growing into the heap, which would cause a crash.
Please post technical questions on the forum, not by personal message. Thanks!

More info: http://www.gammon.com.au/electronics

Thomas499

#79
Dec 28, 2015, 02:05 am Last Edit: Dec 28, 2015, 02:06 am by Thomas499
I just don't see the advantage of doing it that way, vrs showing and giving users access to all memory up front so they know what they are working with.

So in freeRam() do we need to factor that we need to subtract __malloc_margin from the number it gives us to figure out what we can really work with?
Quote
free size3=[791] bytes decimal   2287-128-1360-8
free size4=[919] bytes decimal   2287-1360-8
free size5=[920] bytes decimal   2288-1368
free size3 is the way andy calculates freeRam by walking through each byte. the 128 is the __mallac_margin

free size 5 is the way freeRam() calculates free ram, notice the mallac_margin is not automatically calculated into it. Does that mean that at the very least freeRam must return 128 or it will have problems?

nickgammon

#80
Dec 28, 2015, 05:01 am Last Edit: Dec 28, 2015, 05:02 am by Nick Gammon
I just don't see the advantage of doing it that way, vrs showing and giving users access to all memory up front so they know what they are working with.
I don't see why you don't see that.

Let's say you gave the users access to "all memory". And imagine that there are 2000 bytes free from the start of the heap (past the last global variable) to the bottom of the stack. And let's say they do this:

Code: [Select]

char * foo = (char *) calloc (2000, sizeof (char));

Serial.println ("hello");


Since the call to Serial.println uses memory on the stack, that has now corrupted the 2000 bytes which no longer contain all zeroes.

Quote
So in freeRam() do we need to factor that we need to subtract __malloc_margin from the number it gives us to figure out what we can really work with?
No, because you can't "really work with" the memory set out for the safety margin. As I explained.
Please post technical questions on the forum, not by personal message. Thanks!

More info: http://www.gammon.com.au/electronics

Thomas499

Quote
Since the call to Serial.println uses memory on the stack, that has now corrupted the 2000 bytes which no longer contain all zeroes.
I get what they were trying to do, but if stack runs into heap it crashes, and if you go over the stack size it will crash... that malloc_margin isn't going to help if you go over the stack size regardless. I would prefer to know an exact number of what I have to work with. now if it took 128 bytes in the program to "free" a block in the memory, then malloc_margin would be practical. It just seems like malloc_margin really only makes a crash more likely to happen.

So in freeRam() do we need to factor that we need to subtract __malloc_margin from the number it gives us to figure out what we can really work with?

Quote
No, because you can't "really work with" the memory set out for the safety margin. As I explained.
maybe something isn't clicking.
Quote
free size3=[791] bytes decimal   2287-128-1360-8
free size4=[919] bytes decimal   2287-1360-8
free size5=[920] bytes decimal   2288-1368

free size3 is the way andy calculates freeRam by walking through each byte. the 128 is the __mallac_margin

free size 5 is the way freeRam() calculates free ram, notice the mallac_margin is not automatically calculated into it. Does that mean that at the very least freeRam must return 128 or it will have problems?
Notice that the difference in andys method (free size3)and freeRam() method (free size5) is freeRam() does not facture in mallac_margin.

if you can't "really work with" the memory set out for the safety margin.... wouldn't it be a good idea for freeRam to take away the number you can't "really work with" so we don't get the impression we have that memory available to do whatever we want with?

You said you can't really work with mallac_margin... does freeRam() return a number that includes mallac_margin (which is memory we can't use ... aka might as well not exists?


Thomas499

if you run this on an uno it will cause a crash. In loop 1 it finds free ram and creates an array that is the length of freeRam-105. This works fine. In the second loop around it finds freeRam and creates an array that is the lenght of freeRam-85. This time it crashes. I don't understand why this happens.
Code: [Select]
extern unsigned int __heap_start;
extern char *__brkval;
bool Switch=0;
char Demo[]="does it work or will it fail";
int DemoSize=sizeof(Demo);

void setup() {
Serial.begin(115200);
}

void loop() {
  int K;
  int Ghost=SP; /* this isn't used so it shouldn't even compile. The ghost in the arduino will cause the program to run differently if you comment this out. Even though it isn't used and shouldn't compile either way*/
  int NN=0;
K=SP- (__brkval == 0 ? (int)&__heap_start : (int)__brkval);
  Serial.print(F("Free Ram is "));
  Serial.println(K);
  if (Switch==0){
  char temp[K-105];
  while (NN!=DemoSize+1)
  { temp[NN]=Demo[NN];
    NN++;
  }
  Serial.println(F("freeRam-105 works see"));
  Serial.println(temp);
  K=SP- (__brkval == 0 ? (int)&__heap_start : (int)__brkval);
  Serial.print(F("and we supposivivly have "));
  Serial.print(K);
  Serial.println(F(" remaining"));
  }else
  {
    char temp[K-80];
  Serial.println(F("Good luck with this one though!"));
  while (NN!=DemoSize+1)
  { temp[NN]=Demo[NN];
  NN++;
   
  }
  Serial.println(temp);
  K=SP- (__brkval == 0 ? (int)&__heap_start : (int)__brkval);
  Serial.println(K);
  Serial.println(F("didn't work... very sad face"));
  Serial.print(F("even though we supposivivly have "));
  Serial.print(K);
  Serial.println(F(" remaining"));
  }
  Switch=!Switch;
  Serial.println();
}

msssltd

I would prefer to know an exact number of what I have to work with.
Keep in mind that C and C++, were not developed for programming micro-controllers, specifically.  The development of Unix, C and C++ are inherently linked to the development of AT&Ts digital telephone (exchange) switches - Highly dynamic, multi tasking platforms, where the sort of byte critical control you would prefer, offers no practical utility.

Quote
It just seems like malloc_margin really only makes a crash more likely to happen. So in freeRam() do we need to factor that we need to subtract __malloc_margin from the number it gives us to figure out what we can really work with?
You can't really work with it.  When the top of the heap is well away from the top of the stack, the margin is moot.  When the top of the heap is near to the top of the stack, the margin prevents an interrupt causing a stack overflow. 128 bytes _should_ be enough stack space for an interrupt.


aarg

With some code, in theory you could calculate the exact maximum stack usage. You would do that by examining the call tree and the interrupt complement. Then you could eliminate or minimize the safety margin. But it would be a painstaking task and risk catastrophic failure if it was incorrect in any way.
  ... with a transistor and a large sum of money to spend ...
Please don't PM me with technical questions. Post them in the forum.

Thomas499

#85
Dec 29, 2015, 05:35 pm Last Edit: Dec 29, 2015, 05:36 pm by Thomas499
Quote
With some code, in theory you could calculate the exact maximum stack usage. You would do that by examining the call tree and the interrupt complement. Then you could eliminate or minimize the safety margin. But it would be a painstaking task and risk catastrophic failure if it was incorrect in any way.
Interesting. If you did that, would it move it the minimized safety margin below SP where the rest of dynamic memory is used? I have no idea how to do that, but i'm surprised someone didn't build that into the IDE library already. Seems like it would be helpful.

Does the safety margin need to be increased? The reason I ask is because of the code and problem that I documented on post 82. I can't figure out why that code causes a crash.

Where is the call tree by the way Is it one of these?
Quote
ramSize   = (int) RAMEND       - (int) &__data_start;
 dataSize  = (int) &__data_end  - (int) &__data_start;
 bssSize   = (int) &__bss_end   - (int) &__bss_start;
 heapSize  = (int) __brkval     - (int) &__heap_start;
 stackSize = (int) RAMEND       - (int) SP; //SP-data_start
Quote
The development of Unix, C and C++ are inherently linked to the development of AT&Ts digital telephone (exchange) switches - Highly dynamic, multi tasking platforms, where the sort of byte critical control you would prefer, offers no practical utility.
I'm not really worried about this for my project at the moment, but if I were in charge of security for a communications company like AT&T I would flip out if anyone told me every byte involved in communications wasn't accounted for. If you don't know how many are supposed to be used, how can you know if anything was added?




msssltd

but i'm surprised someone didn't build that into the IDE library already. Seems like it would be helpful.
The heap margin can be adjusted by editing source files.

Quote
Where is the call tree by the way Is it one of these?
The call tree is embedded in the stack.  Some practical experience writing assembly language would provide answers to many of the questions you are asking.

Quote
I'm not really worried about this for my project at the moment, but if I were in charge of security for a communications company like AT&T I would flip out if anyone told me every byte involved in communications wasn't accounted for. If you don't know how many are supposed to be used, how can you know if anything was added?
Nobody said the bytes were not accounted for.

I said, the development of Unix, C and C++ is inherently linked, to the development of AT&T's digital telco switches. Within a telephony switch, there is an overriding need to dynamically allocate and deallocate, a very large number of structures, in a very short period of time; more calls + smarter routing = more revenue.  Unlike a micro-controller, RAM within a digital switch is modular, and relatively cheap and plentiful. 

During the 80s and 90s, security really was not the issue it is today.  Even so, as I understand it, critical application coding standards, do not (normally) allow dynamic heap allocation at runtime.

I think I am going to leave you to it now, as I no longer see what you hope to achieve.  As I alluded to earlier, as far as I am concerned, heap fragmentation is to be avoided rather than measured.

Thomas499

Quote
Some practical experience writing assembly language would provide answers to many of the questions you are asking.
I took the code academy classes on php and python. I bought the book C++ for dummys and have been reading it. I have not found any code academy like classes that let you do hands on practical experience writing assembly language but if you can think of any good references I would be very interested in a link or recommendation.

Quote
I think I am going to leave you to it now, as I no longer see what you hope to achieve.  As I alluded to earlier, as far as I am concerned, heap fragmentation is to be avoided rather than measured.
I was learning how to write a library, and wanted to see if I could do it in practice. I wanted to write one for something useful, and I had been told that using Strings was a terrible idea in regards to memory management. People that don't have much experience in coding (at least myself) learn quicker by seeing for themselves what happens.

I thought if I could measure fragmentation, then it would be easier for a beginner to learn why Strings are so bad, as that seems to be the reason that the experts advice not to use them. I no longer use Strings, but I wanted to see if I could make a library, and I wanted to make it on something that I was interested in, and hoped it would have useful application helping others learn and understand.

If anything, freeRam() is not accurate as the experiment I listed on post 82 points out. If you trust freeRam() then why doesn't post 82 work? What I am trying to do is figure that out.

I have learned a lot from this thread, I should be finished with the library by tonight. I will post it once I have it working if anyone would like to double check it.

Go Up