Malloc failure to allocate memory

Hello,

I am having a memory allocation error, and will post some code, but some context first is important. My program, on certain problem instances, will run out of memory, regardless of any type of memory leaks which may or may not occur. I am purposefully pushing the limits of my machine, and will always be in the situation where it is possible that memory will run out no matter how I update my code.

That said, here is the function causing me problems (I will post my solution to it later):
(on a side note, I know I should be using C++ for this - it's a really, really long story. this is on my to do list but I need this code to work asap. however, if you have details as to why new is a better choice than malloc, I would love to know this - i only know this to be fact).

Code:

---

typedef struct Tree_Node{
  int size;
  struct Tree_Node** children;
}

Tree_Node* New_Child( int size){

  int i;
  Tree_Node* node = malloc(sizeof(Tree_Node));
  node->size = size;

  if( size != 0 )
    node->children = malloc(sizeof(Tree_Node)*size);
  else
    node->children = NULL;

  for(i = 0; i < size; i++)
    node->children[i] = NULL;

  return node;

}

---

The code will seg fault in the for loop. Gdb showed that even though size was non-zero, node->children was NULL, causing the seg fault.

This is my fix:

Code:

---

typedef struct Tree_Node{
  int size;
  struct Tree_Node** children;
}

Tree_Node* New_Child( int size){

  int i;
  Tree_Node* node = malloc(sizeof(Tree_Node));
  node->size = size;

  if( size != 0 )
  {
    node->children = malloc(sizeof(Tree_Node)*size);
    if( node->children == NULL )
    {
      perror("Memory not allocated in New_Child. Exiting\n");
      exit(0);
    }
  }
  else
    node->children = NULL;

  for(i = 0; i < size; i++)
    node->children[i] = NULL;

  return node;

}

---

I'm assuming that what's going on is that malloc is returning a NULL pointer when it is out of memory, but this is counter-intuitive as normally when my program runs out of memory Ubuntu will kill the process. I did not have the chance to check if size had been altered by the time new->children was allocating memory. Could it be that my heap is growing too large and overwriting the size variable in the stack? If this were the case, it seems like Ubuntu would kill the process before it got to this point (I'm just conjecturing - I know very little to nothing about operating systems).

All this aside, under what conditions does malloc return a NULL pointer?


Any help would be appreciated. Cheers,

Rob

Quote:

---

Originally Posted by rsgysel

All this aside, under what conditions does malloc return a NULL pointer?

---

"The malloc function returns either a null pointer or a pointer to the allocated space."

That is, according to the text of the C standard, malloc will return a null pointer when it was unable to allocate space as requested.

What happens is that when you malloc/new very often, the user space memory can become fragmented, so that you may have 1GB free, but no single block large enough to satisfy the malloc/new call, so the call fails. Also note that the memory block needed may be larger than just what you specify due to overhead. Usually some additional memory is needed to keep track of the size of the allocated block.

new isn't better than malloc, both use the exact same methods to allocate memory.
malloc is superior in some instances because, at least under VS, it also provides error information other than simply returning a null pointer on failure. malloc is part of the CRT so every standard compliant compiler will support it. It is also available on C only compilers, while new is not. So for writing portable code which works on both C and C++ compilers, malloc is the only method. This level of portability may not be an issue if your code is never intended to be compiled on C compilers.

'new is better than malloc' is a prejudice perpetuated by C++ snobs in academia that have no clue what they are talking about.

Probably the new was just a keyword-maloc(). The good thing is that it is a keyword, which is nicer. The bad thing is that if when you use C-code in C++ you will end up with new and malloc() in the same code. Which is worse than using one method, whichever that is.

But don't forget that the idea was to use new with a constructor. Meaning that the function-like part would be the parameters of the constructor. With malloc() you cannot to so. You would need to lines. One for allocation and one for initialization. With new you can do this in one line.

Overloading malloc would be one solution. But not a good one, cause it would probably cause more confusion.

Quote:

---

Originally Posted by C_ntua

Probably the new was just a keyword-maloc(). The good thing is that it is a keyword, which is nicer. The bad thing is that if when you use C-code in C++ you will end up with new and malloc() in the same code. Which is worse than using one method, whichever that is.

---

Code that needs to be portable between C and C++ compilers cannot use C++ only features and uses C++ compliant C (e.g. explicit typecasting malloc'd allocations). This is common practice for software that needs to compile on both types of compilers. Some architectures have only one or the other compiler type available and need to use a common code base for interoperability between the target systems. An example would be the microcontrollers in a LAN switch. A low end product may use one brand and type of microcontroller while a higher end version may use a better brand with higher performance. The low end version may only have a C compiler available for it. A company typically would not want to develop separate code bases for its products if it doesn't need to.

Nobody seems to have noticed the problem on this line:

Code:

---

    node->children = malloc(sizeof(Tree_Node)*size);

---

It should be the size of Tree_Node*:

Code:

---

    node->children = malloc(sizeof(Tree_Node*)*size);

---

Otherwise you're allocating twice as much as you need to, or three times as much as you need to on a 64-bit machine.

Quote:

---

Originally Posted by iMalc

Nobody seems to have noticed the problem on this line:

---

I did, but for some reason it did not click that it was really a problem...

Quote:

---

Originally Posted by iMalc

It should be the size of Tree_Node*:

---

Yes, but better yet:

Code:

---

node->children = malloc(sizeof(node->children[0]) * size);

---

Quote:

---

Originally Posted by abachler

What happens is that when you malloc/new very often, the user space memory can become fragmented, so that you may have 1GB free, but no single block large enough to satisfy the malloc/new call, so the call fails. Also note that the memory block needed may be larger than just what you specify due to overhead. Usually some additional memory is needed to keep track of the size of the allocated block.

new isn't better than malloc, both use the exact same methods to allocate memory.
malloc is superior in some instances because, at least under VS, it also provides error information other than simply returning a null pointer on failure. malloc is part of the CRT so every standard compliant compiler will support it. It is also available on C only compilers, while new is not. So for writing portable code which works on both C and C++ compilers, malloc is the only method. This level of portability may not be an issue if your code is never intended to be compiled on C compilers.

'new is better than malloc' is a prejudice perpetuated by C++ snobs in academia that have no clue what they are talking about.

---

Thanks for the great info, makes a lot of sense. What I had to sort out was whether I should count the process as killed and call it quits (which is what I'm going to do) or if there was more work to be done.

Also, thanks for replying about my malloc vs. new question - interesting stuff, as of course, I have not been in industry and always been told in academia that new is better. I'll stick to malloc when I need portability. Cheers!
-rob

Quote:

---

Originally Posted by iMalc

Nobody seems to have noticed the problem on this line:

Code:

---

    node->children = malloc(sizeof(Tree_Node)*size);

---

It should be the size of Tree_Node*:

Code:

---

    node->children = malloc(sizeof(Tree_Node*)*size);

---

Otherwise you're allocating twice as much as you need to, or three times as much as you need to on a 64-bit machine.

---

wow - thanks for catching this. I generate tons and tons of these nodes, so this will help.

Quote:

---

Originally Posted by laserlight

I did, but for some reason it did not click that it was really a problem...


Yes, but better yet:

Code:

---

node->children = malloc(sizeof(node->children[0]) * size);

---

---

interesting - so I'd be doing this to avoid type errors which lead to over-allocation (and I suppose under-allocation in other situations) as above? or is there another reason to do this?

Quote:

---

Originally Posted by rsgysel

Also, thanks for replying about my malloc vs. new question - interesting stuff, as of course, I have not been in industry and always been told in academia that new is better. I'll stick to malloc when I need portability. Cheers!
-rob

---

Well, that depends.
It depends on whether you use C, C++ or need to use both.
If you use C, obviously new isn't available, so no loss there. Using malloc in C++ is a very bad idea. Bad practice due to that it isn't strict with types and it doesn't call the constructor. If you need your C++ code to compile on C, then obviously you cannot use any C++ functions, so you have to use malloc.

Quote:

---

Originally Posted by rsgysel

interesting - so I'd be doing this to avoid type errors which lead to over-allocation (and I suppose under-allocation in other situations) as above? or is there another reason to do this?

---

The advantage is that it's less error-prone. sizeof will determine the type of the variable and return the correct size. That means that even if you change the type later, it will work without manually having to attune the sizeof.
Also note that you really should use the edit button instead of posing 3 replies in a row.