segfault in free while deleting data in binary tree

Question

0.00/5 (No votes)

See more:

Hi ,
I am getting segfault on free while deleting some data in binary search tree.
The back trace from gdb is as follows.

#1 0x0036fe30 in raise () from /lib/libc.so.6
(gdb) up
#2 0x00371741 in abort () from /lib/libc.so.6
(gdb) up
#3 0x003a88cb in __libc_message () from /lib/libc.so.6
(gdb) up
#4 0x003b0c65 in _int_free () from /lib/libc.so.6
(gdb) up
#5 0x003b4c59 in free () from /lib/libc.so.6
(gdb) up
#6 0x0804a014 in Delete_Node (dest=4854128, del_trav_node=0x1804e158, dest_std=4854128) at src/smsc_bintree_operation.c:297
297 src/smsc_bintree_operation.c: No such file or directory.
in src/smsc_bintree_operation.c
(gdb) p del_trav_node->left
$1 = (struct bst *) 0x0
(gdb) p del_trav_node->right
$2 = (struct bst *) 0xebb000

For a reference the code for deletion is as follows

C++

NODE Delete_Node(U32bit dest,NODE del_trav_node, U32bit dest_std)
{
        NODE del_trav_temp,del_trav_prev;

        if(del_trav_node == NULL)
        {
                LOG("\nelement not found\n");
        }
        else
        {
                if(dest < del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->left = Delete_Node(dest,del_trav_node->left,dest_std);

                }
                else if(dest > del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->right = Delete_Node(dest,del_trav_node->right,dest_std);

                }
                else //if the node to be deleted is the root node
                {
                        if((del_trav_node->left == NULL) && (del_trav_node->right == NULL))
                        {
                               
                                free(del_trav_node);
                               
                          return(NULL);
                      }
                      else if((del_trav_node->left != NULL) &&(del_trav_node->right != NULL))
                      {
                             
                        del_trav_temp = Find_Min(del_trav_node->right);
                        del_trav_node->key_val = del_trav_temp->key_val;
                        memcpy(&del_trav_node->value,&del_trav_temp->value,sizeof(SMSC_DATA_ARRAY));
del_trav_node->right = Delete_Node(del_trav_node->key_val,del_trav_node->right,dest_std);
                            
                            

                      }
                      else if(del_trav_node->left == NULL)
                      {
                             del_trav_temp = del_trav_node;

                              del_trav_node = del_trav_node->right;

                              if(del_trav_temp != NULL)
                                      free(del_trav_temp);  line no  ---297
                              
                      }
                       else if(del_trav_node->right == NULL)
                        {
                               

                                del_trav_temp = del_trav_node;

                                del_trav_node = del_trav_node->left;

                                if(del_trav_temp != NULL)
                                        free(del_trav_temp);
                            
                        }
                        else;
                }
        }
        return del_trav_node;
};

Any help will be appreciated .

Thanks
SP

[edit]Code block added - OriginalGriff[/edit]

Posted 29-Nov-13 21:40pm

saroj kymar panda

Updated 29-Nov-13 21:44pm

OriginalGriff

v2

Add a Solution

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2013-11-29T21:52:00

First off, what are you doing with del_trav_prev? You presumably meant to do something with it, but you assign a value, and then ignore it completely. Don't know if that is relevant, but either you need to do something with it, or get rid off it.

Secondly, this is going to depend on your data to a large extent - it may be that one "branch" or the other is the problem, or it may be that your code to set up the tree is faulty. I can't tell in either case, because I don't have access to your completed tree.

So, its going to be up to you.
Put a breakpoint on the first line in the function, and run your code through the debugger. Then look at your code, and at your data and work out what should happen manually. Then single step each line checking that what you expected to happen is exactly what did. When it isn't, that's when you have a problem, and you can back-track (or run it again and look more closely) to find out why.

Sorry, but we can't do that for you - time for you to leans a new (and very, very useful) skill: debugging!

nv3 · Answer 2 · 2013-11-29T22:44:00

If you are getting a seg fault in the free call, it is likely that the heap or your tree has been corrupted and that means: The problem can just be anywhere in your program. It will not necessarily be found in your Delete_Node function.

My suggestions:

(a) Review your entire tree code thoroughly; do a dry run or step to a couple of meaningful test cases statement by statement.

If that didn't help:

(b) Write a tree check function that traverses the entire tree and checks all your links and the consistency of the tree. Put a call to that tree check function at the end of every tree operation. Thereby you might be able to find the operation that corrupts your tree and from there you can narrow the search area.

saroj kymar panda · Answer 3 · 2013-11-29T23:25:00

Solution 3

If it happens always then it will be easy through single stepping through the code
through a debugger but you know this is in a production system and it happens sometimes only. In every second am inserting and deleting some 1000 data into the binary tree.

Posted 29-Nov-13 23:25pm

saroj kymar panda

Comments

nv3 30-Nov-13 5:58am

Please don't post comments or additions to your question as a solution! Use the "Have a question or comment" or the "Improve question" button instead.

Now to your problem: What you describe tells us that the problem occurs intermittently and probably depends on the sequence of data you enter into the tree. And for that reason I think that the two suggestions I gave will be your best bet in finding the bug.

Stefan_Lang · Answer 4 · 2013-12-02T02:45:00

Solution 4

In one of the cases where you relink your branches, you check and correct the key value, but not in the other two. I don't see how that would lead to a seg fault (in fact I believe that would be caught by the first if, since the key you're looking for is no longer there), but without correcting the keys, how will you ever be able to free those nodes that you elevated into the deleted nodes' position?

Posted 2-Dec-13 2:45am

Stefan_Lang

Comments

saroj kymar panda 6-Dec-13 8:27am

I tried all possible scenarios but unable to find a solution
for it. Let me elaborate the situation in which am getting the fault.

The scenarion is like this

1. Am fetching data from db--->(ex key = 13245)
2. inserting into a tree--(key = 12345 inserted )
3. sending some message to outside ( with key = 12345)
5. Got response from outside( with key = 12345);
6. delete the data from tree (with key = 12345);

....
7. Every 5 minutes will generate an alarm which will traverse the tree and for
the node which I dint get response for more than 10 min(I have insert time in
value of the node) will delete it.

mutex_lock is implemented.

so while traversing the tree and deleting sometime I get the SEGFAULT/SIGABRT

for reference let me paste the code

NODE Traverse_Node(NODE trav_node)
{
char tim[32];
long int utc=0,cur_utc=0;

memset(tim,'\0',sizeof(tim));
Get_Curr_Time_Traverse(tim);
cur_utc = Get_UTC_Time(tim);
utc = Get_UTC_Time(trav_node->value.ntime);

if((cur_utc-utc) >= DELETE_TIME_OUT) // DELETE TIMEOUT IS THE TIMEOUT VALUE
{

printf("Node_Delete_CID::%d\n",trav_node->key_val);
trav_node = Delete_Node(trav_node->key_val,trav_node,trav_node->key_val);

if(trav_node!=NULL)
trav_node = Traverse_Node(trav_node);
}

if(trav_node != NULL)
{
if(trav_node->left != NULL)
trav_node->left = Traverse_Node(trav_node->left);

if(trav_node->right != NULL)
trav_node->right = Traverse_Node(trav_node->right);
}
return trav_node;
}

and Delete_Node code is whatever i posted before and bt from the core file is
#0 0xffffe410 in __kernel_vsyscall ()
#1 0x0036fe30 in raise () from /lib/libc.so.6
#2 0x00371741 in abort () from /lib/libc.so.6
#3 0x003a88cb in __libc_message () from /lib/libc.so.6
#4 0x003b0c65 in _int_free () from /lib/libc.so.6
#5 0x003b4c59 in free () from /lib/libc.so.6
#6 0x0804a044 in Delete_Node (dest=357727216, del_trav_node=0xfb1b230, dest_std=68677603) at src/smsc_bintree_operation.c:297
#7 0x08049fc1 in Delete_Node (dest=68677603, del_trav_node=0xc389e98, dest_std=68677603) at src/smsc_bintree_operation.c:275
#8 0x0804a1c4 in Traverse_Node (trav_node=0xc389e98) at src/smsc_bintree_operation.c:490

and i cant run the program in gdb as it is in production system

Any idea to solve it.

Stefan_Lang 9-Dec-13 3:25am

Hmm, this is odd: according to your call stack Traverse_Node calls Delete_Node(68677603,...) and that function recursively calls it self with Delete_Node(357727216,...)
I don't see how dest could be changed before the recursive call, so who meddled with it? Did you clip some code that you thought irrelevant?

Also, the code you posted doesn't match literally the info from the backtrace: according to bt the call to free is in line 297 which you marked in the code, and the call to Delete_Node one step up in the call stack happened at line 275, so 22 lines up in the code. There is no call to Delete_Node 22 lines up in the code however, so either there are some extra linebreaks that were not in the original code or you've clipped some of it. Can you please check the code at line 275 and mark the corresponding line in your code snippet?

segfault in free while deleting data in binary tree

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0