C++ : memory related error

Discussion in 'Mac Programming' started by neowin, Nov 24, 2011.

  1. macrumors newbie

    Joined:
    Jun 27, 2011
    #1
    Hi guys,

    I am implementing a singly linked list. The thing is whenever my str_temp goes above 12-15 elements, i get this error

    malloc: *** error for object 0x1099008b8: incorrect checksum for freed object - object was probably modified after being freed.
    *** set a breakpoint in malloc_error_break to debug
    Run Command: line 1: 7322 Abort trap: 6 ./"$2"

    The error is happening in AppendNode method. Can you please tell me where I might be going wrong.
    Code snippet is given below. Please let me know if you need more info.


    Code:
    class node{
        public:    
        int data;
        class node* next;
        
    };
    
    class IO{
        public:
        int numReq;
        class node *head;
        class node *tail;
        
        IO(int);
        void makeList(int*);
        void makeSorted(int*);    
        void printList();
        void SortedInsert(class node*&,int); 
        void InsertSort();
        void AppendNode(int);
           
    };
    
    void IO::makeList(int str_temp[]){
        int i;
        cout<<"NUMREQ "<<numReq<<endl;
        for (i=0;i<numReq;i++) {
        cout<<str_temp[i]<<endl;
            AppendNode(str_temp[i]);
        }
    }
    
    
    void IO::AppendNode(int num) {
       class node* current = head;
       class node* newNode;
       newNode = new node();
       newNode->data = num;
       newNode->next = NULL;
    
       // special case for length 0
       if (current == NULL) {
          head = newNode;
       }
       else {
          // Locate the last node
          while (current->next != NULL) {
             current = current->next;
          }
          current->next = newNode;
       }
    
    }
     
  2. macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #2
    Assuming an IO constructor like:
    Code:
    IO::IO(int a)
    : numReq(a), head(NULL), tail(NULL)
    {
    }
    
    This code works for me. I can create list of any size. I've tried up to 10,000.

    Anything beyond that is too slow because instead of maintaining and taking advantage of the tail member in AppendNode, you're walking through the list. So to add the 1,000,000th item, for example, your code needs to walk along the existing 999,999 items.


    So the error is not were you think it is. How are you calling makeList?
     
  3. neowin, Nov 25, 2011
    Last edited: Nov 25, 2011

    thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #3
    I am using an app called code runner. I just press run in that to run the program.

    ----------

    I tried using terminal just now. g++ filename. i still get the same error.

    And yes, my constructor is the same as you have mentioned.
    I am using this string - 89 92 201 128 10 1 2 3 4 5 6 6 7 7 23 and i get the error mentioned.

    I am calling makelist like this -

    Code:
    int main(int argc, char *argv[]) {
    int i;
    FlagReader(argc,argv);
    Init();
    IO str(refStringLen);
    str.makeList(refString);
    str.printList();
    
    //str.makeSorted(refString);
    //str.printList();
    
    return 0;    
    }
     
  4. macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #4
    You passing a string containing the numbers separated by space?!

    Your makeList member function is not expecting a string containing the numbers. It's expecting an array of integers. This is why your program is failing.

    You need to get the numbers out of the string and convert them from text to integers.

    For example, I called makeList with this code:
    Code:
    int main (int argc, const char * argv[])
    {
        const int count = 10000;
        int *nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = i;
        }
        
        IO io(count);    
        io.makeList(nums);
        
        delete[] nums;
        
        return 0;
    }
    
     
  5. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #5
    I am tokenizing it and the reference string will have integers correctly.
    Thats not the problem.

    Code:
    cout << "Please type the reference string and press Enter" <<endl; 
            getline(cin,str);
    
            temp= new char [str.size()+1];
            strcpy(temp,str.c_str());
            pch = strtok(temp," ");        
            refString =(int*)malloc(sizeof(str)*sizeof(int));
            
            while (pch != NULL)
            {
                refString[refStringLen]=atoi(pch);
                pch = strtok (NULL, " ");
                refStringLen++;
            }
    
    The problem occurs whenever the control goes to AppendNode method, the line

    class node* newNode;
    newNode = new node();

    Thats where the error occurs .
     
  6. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #6
    i tried using your main, and it works. But my main is not working/ I am clueless where i am going wrong.
     
  7. chown33, Nov 25, 2011
    Last edited: Nov 25, 2011

    macrumors 603

    Joined:
    Aug 9, 2009
    #7
    Post the complete code of your main(). You've only posted part of your code. We need to see it all. Pretend we want to compile and run it, just like you did with jiminaus's code.

    For example, I'd like to know the starting value of refStringLen. If it's not 0, then think very carefully about what your while loop will do. Question to ask yourself: At what index are the first and second ints stored?

    You should also think about what size you're passing to malloc(). Better still, think why you're using malloc() at all, if you could be using new int[someCount].
     
  8. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #8
    Here is all the code

    Code:
    
    #include<iostream>
    #include<string>
    
    
    
    using namespace std;
    
    int numCylin=200;
    char *inputFile;
    int iFlag,FIFOFlag,SSTFFlag,CSCANFlag,LOOKFlag;
    int *refString,refStringLen;
    
    
    class node{
        public:    
        int data;
        class node* next;
        
    };
    
    class IO{
        public:
        int numReq;
        class node *head;
        class node *tail;
        
        IO(int);
        void makeList(int*);
        void makeSorted(int*);    
        void printList();
        void SortedInsert(class node*&,int); 
        void InsertSort();
        void AppendNode(int);
           
    };
    
    void IO::printList(){
        int i;
        class node *lnode=head;
        for (i=0;i<numReq;i++) {
            cout<<i<<" "<<lnode->data<<endl;
            lnode=lnode->next;
        }
    }
    
    void IO::makeList(int str_temp[]){
        int i;
        cout<<"NUMREQ "<<numReq<<endl;
        for (i=0;i<numReq;i++) {
        cout<<str_temp[i]<<endl;
            AppendNode(str_temp[i]);
        }
    }
    
    
    void IO::AppendNode(int num) {
        cout<<"-----"<<endl;
        node* current = head;
        cout<<"-----"<<endl;
    
        node* newNode = new node();
        cout<<"-----"<<endl;
    
       newNode->data = num;
       newNode->next = NULL;
        cout<<"-----"<<endl;
       // special case for length 0
       if (current == NULL) {
          head = newNode;
        cout<<"-----"<<endl;
       }
       else {
          // Locate the last node
          while (current->next != NULL) {
             current = current->next;
          }
          current->next = newNode;
       }
    
    }
    
    void IO::makeSorted(int *str_temp){
        int i;
        for (i=0;i<numReq;i++) {
            SortedInsert(head,str_temp[i]);
        }
    }
    
    void IO::SortedInsert(class node*& headRef,int num) {
        class node* newNode;
       newNode = new node();
       newNode->data = num;
       newNode->next = NULL;
    
       // Special case for the head end
       if (head == NULL || headRef->data >= newNode->data) {
          newNode->next = headRef;
          headRef = newNode;
       }
       else {
          // Locate the node before the point of insertion
          class node* current = headRef;
          while (current->next!=NULL && current->next->data<newNode->data) {
             current = current->next;
          }
          newNode->next = current->next;
          current->next = newNode;
       }
    }
    
    
    IO::IO(int num):numReq(num),head(NULL),tail(NULL){
        }
    
        
    void PrintHelp(){
        cout << "-h                     : Print a usage summary with all options and exit." <<endl;
        exit(0);
    }
    
    void FlagReader(int argc, char** argv){
            int i;
            for(i=1;i<argc;i++){
                if(!strcmp(argv[i],"-h")){
                    PrintHelp();
                }else
                if(!strcmp(argv[i],"-n")){
                    i++;
                    numCylin = atoi(argv[i]);
                    continue;
                }else
                if(!strcmp(argv[i],"-d")){
                    FIFOFlag=0;
                    i++;
                    if (!strcmp(argv[i],"SSTF")) {
                        SSTFFlag=1;    
                    }
                    if (!strcmp(argv[i],"FIFO")){
                        FIFOFlag=1;
                    }
                    if (!strcmp(argv[i],"C-SCAN")) {
                        CSCANFlag=1;    
                    }
                    if (!strcmp(argv[i],"LOOK")) {
                        LOOKFlag=1;    
                    }
                    continue;
                }else
                if(!strcmp(argv[i],"-i")){
                    iFlag=1;
                    i++;
                    inputFile=(char*)malloc(sizeof(argv[i]));
                    strcpy(inputFile,argv[i]);
                    continue;
                }
                        }
                    
    }
    
    int Init(){
        int i;
        
        if (iFlag==1) {
            
            FILE *file = NULL;
            unsigned long fileLen;
            char filenames[1000]="",f1[9000]="";
            file = fopen(inputFile,"rb");
            char *pch;
            int num=0;
    
            if(file==NULL){
                printf("cant open file\n");
                return 0;
            }
            //To find file length
            fseek(file, 0, SEEK_END);
            fileLen=ftell(file);
            fseek(file,0,SEEK_SET);
        
            //Read file contents into buffer
            fread(f1,fileLen, 1, file);
            fclose(file);
            
            refString =(int*)malloc(sizeof(f1));
            pch = strtok (f1," ");
            while (pch != NULL)
            {
                refString[refStringLen]=atoi(pch);
                pch = strtok (NULL, " ");
                refStringLen++;
            }
            
        }
        else
        {
            string str;
            char *temp;
            char *pch;
            cout << "Please type the reference string and press Enter" <<endl; 
            getline(cin,str);
    
            temp= new char [str.size()+1];
            strcpy(temp,str.c_str());
            pch = strtok(temp," ");        
            refString =(int*)malloc(sizeof(str)*sizeof(int));
            
            while (pch != NULL)
            {
                refString[refStringLen]=atoi(pch);
                pch = strtok (NULL, " ");
                refStringLen++;
            }
        }
    }
    
    
    int main(int argc, char *argv[]) {
    int i;
    
    FlagReader(argc,argv);
    Init();
    
    IO io(refStringLen);
    io.makeList(refString);
    
    io.printList();
    
    //str.makeSorted(refString);
    //str.printList();
    
    //89 92 201 128 10 1 2 3 4 5 6 6 7 7 23
    return 0;    
    }
    
    
    
    
     
  9. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #9
    What exactly does the sizeof operator return? For example, what is sizeof(argv) ? Hint: It's not what you think it is.

    First rule of debugging: The bug is not where you think it is. So if you post the code where you think the bug is, you will not post the code containing the bug.
     
  10. chown33, Nov 25, 2011
    Last edited: Nov 25, 2011

    macrumors 603

    Joined:
    Aug 9, 2009
    #10
    What have you done to test the components of this code?

    Have you tested Init() and FlagReader() independently? Are you certain that they're known working? Building things from untested large components is risky.

    What evidence do you have that they work? Evidence means things like debugger observation, log or console output, etc. If you haven't tested them, you need to break the problem down and do those tests. If you don't have evidence, you need to add printf's or cout's that produce such evidence.


    What have you done to debug the components of this code?

    Given that jiminaus's main() worked, and assuming you understand what his code does, what does that suggest about your non-working code?

    To me, it suggests the real problem might not be where you think it is. Or it might not be what you think it is. For example, a bad value of refStringLen.


    I guarantee that you have some serious buffer overflow bugs. Like this:
    Code:
            //Read file contents into buffer
            fread(f1,fileLen, 1, file);
    
    f1 is a local 9000-char buffer. fileLen can be anything. You haven't limited fileLen in any way, so if it's larger than 9000, you just overflowed a stack-resident buffer. Boom.
     
  11. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #11
    @chown33-
    Before posting the code I have printed to find till where the code works .
    I have printed the contents of RefStringLen and the refString just before it enters AppendNode(). The contents of refString is coming correctly.
    I have tried printing the contents of str_temp too.It comes correctly.

    Yea,error is happening in refString. i dont know how though.
    I tried giviing this and it works

    Code:
    int refString[]={89,92,201,128,10,1,2,3,4,5,6,6,7,7,23};
    int refStringLen = 15;
    
    IO io(refStringLen);
    io.makeList(refString);
    
    io.printList();
    What might be happening? When i print the contents of refString it comes correctly. 9000 is more than enough for f1.

    @gnasher729
    Ok will give it a look. But currently i am not facing any music from that end. But will give it a look and correct it.
     
  12. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #12
    I told you how. If the user uses the -i option, then you ********* up the memory much much much much earlier. Remember the golden rule: The bug is not where you think it is.
     
  13. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #13
    lets consider that i am not using -i flag. Still the error occurs. I will correct it though.
     
  14. macrumors 603

    Joined:
    Aug 9, 2009
    #14
    Then post your log. We'd like to see your evidence. Frankly, I'd also like to see the code with the extra logging in it. Because that way we know where the evidence comes from. Because if you log the wrong thing, the logged data isn't worthwhile.


    Consider this code:
    Code:
            cout << "Please type the reference string and press Enter" <<endl; 
            getline(cin,str);
    
    [COLOR="Red"]        fprintf( stderr, "str size: %d, sizeof: %d\n", str.size(), sizeof(str) );
    [/COLOR]
            temp= new char [str.size()+1];
            strcpy(temp,str.c_str());
            pch = strtok(temp," ");        
    [COLOR="Blue"]        refString =(int*)malloc(sizeof(str)*sizeof(int));
    [/COLOR]
    I added the one line in red.

    Run it, enter this text:
    Code:
    12 34 56 78 90 11
    
    Output from the newly added fprintf() is:
    Code:
    str size: 17, sizeof: 8
    
    (You'll see a sizeof of 8 if you're running 64-bit code, 4 if running 32-bit code.)

    Try running it again and typing in your input that causes a failure.

    What does this say about the other uses of sizeof in your code? For example, the sizeof(str) in your call to malloc() as hilited in blue above?
     
  15. macrumors newbie

    Joined:
    Jan 9, 2011
    Location:
    Chicago
    #15
    Why are you using malloc, this isn't C. Use a vector and the methods it provides to dynamically grow the array instead of tinkering around with memory allocation on your own would be my suggestion.
     
  16. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #16
    In that case you run into exactly the same bug:

    Code:
            string str;
            refString =(int*)malloc(sizeof(str)*sizeof(int));
    
    Wouldn't it be common sense that after identifying one horrible bug you would check whether the same blunder has happened in another place?
     
  17. thread starter macrumors newbie

    Joined:
    Jun 27, 2011
    #17
    I got what was going wrong :D.
    I was not allocating sufficient memory space in refString malloc.
    I increased the memory and it works!

    Any suggestion on how to calculate the exact number of integers to be allocate when read from the stdin?

    Thanks for all your answers @chown33 , @gnasher729 and @jiminaus

    Happy holidays!
     
  18. chown33, Nov 25, 2011
    Last edited: Nov 26, 2011

    macrumors 603

    Joined:
    Aug 9, 2009
    #18
    Think through what you're asking.

    Your question is basically one of the following:
    1. How can I predict, with perfect accuracy, the number of integers that a user hasn't typed in yet?
    2. How can I accurately predict, without parsing or otherwise looking at the string typed in, exactly how many integers the string will be parsed into?

    This question seems silly, because the code implements a linked list. One property of a linked list is that it's of arbitrary length (any number of nodes). Another property is that it can easily be grown or shrunk by adding or deleting nodes. So in a practical sense, one easy way to parse input of unpredictable length is to use a linked list in the proper way. That would be:
    1. Read a number.
    2. Create a node containing the number.
    3. Add node to linked list.
    4. Repeat until input is consumed.

    If step 3 adds nodes at the head, then the list is in LIFO order. If it adds at the tail, it's in FIFO order. In any case, walk the list counting nodes. Make an array of that length. Remove node from list, storing number in array. Repeat until list is empty.

    Or you could not use an array at all, and simply parse the numbers, appending to the linked list using, for example, IO::AppendNode(num).
     

Share This Page