Menu
i am quite desparate on an error i am not able to get over.
For my C programming class at university, i had to implement a parser for GML (Graph Modeling Language) input streams.
On success, the parser returns an Abstract Datatype to the caller, which is an Adjacency Matrix as representation of the graph.
Okay, the parser works flawlessly, wouldnt there be a problem reducing me to despair over the last few days. In the parser, there is one function call which in turn calls malloc. malloc is called quite often during the scanner delivers symbol by symbol to the parser. But the malloc´d mem chunks are ALWAYS freed by calling free() before leaving the scanner routine.
But there is one fatal function call quite deep inside the parser, which, in turn calls a function that uses malloc to reserve 12 bytes of memory (three integer properties) for saving a struct. The struct is needed to store information about a single edge within the graph (source node, target node, weight).
This call is made two times. the first time, all goes well. Then, as there can occur 1 to n edges according to the gml syntax, the code enters a while loop, where the same pointer is assigned with a pointer to a new Edge Struct, as long as there are Edges found in the input stream. The first call of the Edge recognition routine within the loop, wich is the second in total (the first one happens before entering the loop, see m.a.), fails constantly by malloc returning NULL.
I simply have no idea why.
Its not about a memory shortage issue, because when i malloc 1000 bytes in the main() function of that program, just for fun, it works fine.
I use Code::Blocks and DevCPP as IDEs. In both, the program encounters the same problem.
Here´s my main parsing routine:
DirectedGraph Graph(char* sourceString, int*currentPosition){
int sym;
int restartPosition = 0;
int* backupPosition;
char* backupString;
int nodeCount = 0;
int currentSrc = -1;
int currentTgt = -1;
int currentWgt = -1;
EdgeDescription e;
DirectedGraph correctMatrix;
MatrixStruct* errorMatrix = NULL;
/*begin parsing*/
bool isGraphHeader = GraphHdr(sourceString, currentPosition);
if(isGraphHeader == true){
bool isNode = Node(sourceString, currentPosition);
if(isNode == true){
while(isNode == true){
nodeCount++;
restartPosition = *currentPosition;
isNode = Node(sourceString, currentPosition);
}
*currentPosition = restartPosition;
/*now get edge information (from-to-weight)*/
/*as we have already read the next symbol, we have to reset*/
/*our read position by one symbol backwards*/
e = Edge(sourceString, &restartPosition); /*<======== HERE I CALL THE FATAL ROUTINE FOR THE FIRST TIME - EVERYTHING´s JUST FINE, PROGRAM PROCEEDS*/
restartPosition = 0;
/*just for clearer coding in if statement*/
currentSrc = e->source;
currentTgt = e->target;
currentWgt = e->weight;
destroyEdge(e);
if(currentSrc != -1 && currentTgt != -1 && currentWgt != -1){
/*initialize matrix with counted number of nodes*/
correctMatrix = CreateNewGraph(nodeCount);
/*the edge is inserted only when it lies within the boundaries*/
/*of our graph. but we do not interrupt the whole processing, we just skip it.*/
while(currentSrc != -1 && currentTgt != -1 && currentWgt != -1){
if(currentSrc <= nodeCount && currentTgt <= nodeCount){
InsertEdge(correctMatrix, currentSrc, currentTgt, currentWgt);
restartPosition = *currentPosition;
}
e = Edge(sourceString, currentPosition); /* <============== THIS IS THE CALL THAT FAILS*/
currentSrc = e->source;
currentTgt = e->target;
currentWgt = e->weight;
}
/*as we have read over the next symbol in the loop, reset the position to read*/
*currentPosition = *currentPosition - 1;
sym = GetNextSymbol(sourceString,currentPosition);
if(sym == rightBrace){
sym = GetNextSymbol(sourceString, currentPosition);
if(sym == eot){
return correctMatrix;
}
else{
return errorMatrix;
}
}
else{
return errorMatrix;
}
}
else{
return errorMatrix;
}
}
else{
return errorMatrix;
}
}
else{
return errorMatrix;
}
}
Here the GetNextSymbol (the scanner, that delivers the symbols to the parser):
/**
* DOCUMENTATION
* ============================
* This is the main scanning function
* which is used by the parser to recognize
* terminal symbols and valid literals.
*
* RETURNS: the enum code for the recognized symbol.
* or an error code, when invalid symbol encountered.
*/
int GetNextSymbol(char* sourceString, int* currentPosition){
int symbolCode;
int loopCounter = 0;
char* currentIdentifier = (char*)malloc(10);
char* currentNumber = (char*)malloc(10);
int identifierPosition = 0;
int numberPos = 0;
int numericVal = 0;
char currentChar;
currentChar = getNextChar(sourceString, currentPosition);
/*skip all blanks, empty chars,
linefeeds, carriage returns*/
while(currentChar == ' '
|| currentChar == 11
|| currentChar == 10
|| currentChar == 13
|| currentChar == '\t')
{
currentChar = getNextChar(sourceString, currentPosition);
}
/*=====================================*/
/*Section 1: scan for terminal symbols */
/*====================================*/
if(currentChar == '['){
symbolCode = leftBrace;
}
else if(currentChar == ']'){
symbolCode = rightBrace;
}
/*=====================================*/
/*Section 2: scan for valid literals */
/*====================================*/
else if(isdigit(currentChar)){
/*here we calculate the numeric value of a number expression*/
/*when calculated, we assign the numeric value to the symCode variable*/
/*this works out because the values for a real symbol are always negative*/
symbolCode = digit;
while(isdigit(currentChar)){
currentNumber[numberPos] = currentChar;
currentChar = getNextChar(sourceString, currentPosition);
loopCounter++;
numberPos++;
}
currentNumber[numberPos] = '\0';
numericVal = atoi(currentNumber);
symbolCode = numericVal;
/*when identifier or braces follow number without space: reset currentPos*/
/*to the position of the previous char*/
if(isalpha(currentChar)){
*currentPosition = *currentPosition - loopCounter;
}
else if(currentChar == ']'){
*currentPosition = *currentPosition - loopCounter;
}
else if(currentChar == '['){
*currentPosition = *currentPosition - loopCounter;
}
}
else if(isalpha(currentChar)){
while(isalpha(currentChar)){
currentIdentifier[identifierPosition] = currentChar;
currentChar = getNextChar(sourceString, currentPosition);
loopCounter++;
identifierPosition++;
}
/*check wether we have found a valid identifying label*/
/*and deallocate the reserved mem space*/
currentIdentifier[identifierPosition] = '\0';
symbolCode = recognizeIdentifier(currentIdentifier);
/*when number or braces follow identifier without space: reset currentPos*/
/*to the position of the previous char*/
if(isdigit(currentChar)){
*currentPosition = *currentPosition - 1;
}
else if(currentChar == ']'){
*currentPosition = *currentPosition - 1;
}
else if(currentChar == '['){
*currentPosition = *currentPosition - 1;
}
}
else if(currentChar=='\0'){
symbolCode = eot;
}
/*neither terminal symbol nor end of text found on current position --> illegal symbol*/
else{
symbolCode = error;
}
free(currentIdentifier);
free(currentNumber);
return symbolCode;
}
and now the fatal call in the "Edge" recognition routine. First, the header for the struct
#ifndef GML_EDGE_STRUCT_H_INCLUDED
#define GML_EDGE_STRUCT_H_INCLUDED
typedef struct EdgeStruct* EdgeObj;
typedef struct EdgeStruct {
int source;
int target;
int weight;
} EdgeStruct;
typedef EdgeObj EdgeDescription;
EdgeDescription createNewEdge(int src, int tgt, int wgt);
void destroyEdge(EdgeObj);
#endif // GML_EDGE_STRUCT_H_INCLUDED
The implementation
#include "GML_EDGE_STRUCT.h"
#include <stdio.h>
#include <stdlib.h>
EdgeDescription createNewEdge(int source, int target, int weight){
EdgeDescription e;
int bytesRequested = sizeof(EdgeStruct);
e = malloc(bytesRequested);
e->source = source;
e->target = target;
e->weight = weight;
return e;
}
I know, that´s pretty much code ;) Just to show, that everything that can be freed, i freed.
I googled my problem for the last two days, of course also here at stack overflow, and there are hundreds of sites, postings et cetera concerning malloc returning null. They all say basically the same: not enough memory (which is, lets call it unlikely), or fragmented heap, so there are no mem chunks of sufficient size available.
but: all i request for are 12 (in words: twelve) bytes to store three int properties. which seems to be too much.
Have i exceeded some internal limits i don´t know about?
Help would be greatly appreciated.
Thanks in advance Roland
EDIT 2012-11-24:
thanks for your answers. but. the problem must be of more basic nature.
because: when i tested the other parts of my program (file I/O) etc. which are far less complex than the parser and go just one call deep from the main(), i also cannot malloc. The file i read has roughly 140 bytes. Even when i test the I/O part isolated from all the other parts, even when i outsource them in a different project, i get no memory from the system. by no means. i´ve restarted the computer, everything. absolutely. no. change.
any ideas? in the meantime i´ve put far too many hours in this project, the most of which are tracking those f***ing memory errors... :-(((
225
Malloc will return NULL when the kernel/system lib are certain that no memory can be allocated. The reason you typically don't see this on modern machines is that Malloc doesn't really allocate memory, but rather it requests some “virtual address space” be reserved for your program so you might write in it.
For some programs, simply aborting is the right thing to do. For some applications, the right thing to do is to shrink caches and try the malloc again. For some multithreaded programs, just waiting (to give other threads a chance to free memory) and retrying will work.
malloc tries to allocate a given number of bytes and returns a pointer to the first address of the allocated region. If malloc fails then a NULL pointer is returned.
If you suspect you application of using too much memory or fragmenting all available memory then you can check memory usage by your application while running. If it eats all system memory then malloc returned NULL because of this.
If the above is not your case then I would check your application for heap corruption. Usually when you overwrite heap structures very bad things happen. In debug mode compiler adds some extra checks and red zones for heap corruption detection. In release mode breaking heap structures usually lead to access violation. I can imagine that in very rare cases heap structures can be damaged and the damage can be interpreted as out of space so NULL is returned by malloc.
One way or another I would employ memory debugger. Valgrind saved me many times, but it may not be available in your environment. There are many topics here on stackoverflow about memory debuggers.
63
I can't say much, just one observation. In GetNextSymbol(), I see no restriction on the number of digits read, so there's the possibility of a buffer overflow. The same goes for reading an identifier.
Another one in Graph(), the failing Edge(sourceString, currentPosition) call is in a while loop and the result is never freed, AFAICS.
20
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
