bugGNU libavl - Bugs: bug #27754, corner case in prb_copy() when...

 
 

bug #27754: corner case in prb_copy() when memory runs out

Submitted by:  Ben Pfaff <blp>
Submitted on:  Mon 19 Oct 2009 04:32:23 PM UTC  
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  None
Privacy:  Public Assigned to:  None
Open/Closed:  Open

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Mon 19 Oct 2009 05:01:37 PM UTC, comment #1: 

I found the following changeset would fix the bug:

static void
copy_error_recovery (struct prb_node *q,
                     struct prb_table new, prb_item_func destroy)
{
  assert (q != NULL && new != NULL);

  /*                                                             
   * The parent pointer of the root node is not set to null if prb_copy
   * failed in the second for loop.                                                                
   */
  if (new->prb_root) {
     new->prb_root->prb_parent = NULL;
  }

  /*                                                             
   * fix the node pointers only if there are nodes in the tree                                                               
   */
  if ((void )q != (void )new)
     {
     for (;;)
       {
        struct prb_node *p = q;
        q = q->prb_parent;
        if (q == NULL)
        break;

        if (p == q->prb_link[0])
          q->prb_link[1] = NULL;
      }
    }

  prb_destroy (new, destroy);
}

JOshua Xie <jxie>
Mon 19 Oct 2009 04:32:23 PM UTC, original submission:  

From Joshua Xie <jxie@tippingpoint.com>:

First, thank you for your excellent libavl. I find it tremendously useful.

I noticed a bug in the prb tree code. This bug is a corner case which happens only if memory is run out while calling prb_copy. Attached please find my test code (prb.c, prb.h, and prbtest.c). The following is my simple test steps:

[jxie@hp15 test]$ gcc -o prb prb.c prbtest.c
[jxie@hp15 test]$ ./prb
tree created
Segmentation fault

If I take out the SetFailAlloc(50) function call from the main(), everything is good. The SetFailAlloc(50) forces malloc and calloc to return null pointers 50 percent of times. My analysis indicates that the segment fault happens when copy_error_recovery traverses from a leaf node one step beyond the root_node because the prb_parent of the root_node is not NULL.

Please fell free to let me know if I can provide any further assistance.

Ben Pfaff <blp>
Project Administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #18903:  prbtest.c added by blp (3KiB - text/x-csrc)
file #18904:  prb.h added by blp (4KiB - text/x-chdr)
file #18902:  prb.c added by blp (26KiB - text/x-csrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jxie (Posted a comment)
  • -email is unavailable- added by blp (Submitted the item)
  • -email is unavailable- added by blp (submitter)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-10-19 blp Attached File- => Added prb.h, #18904
        Carbon-Copy- => Added joshua xie
        Attached File- => Added prbtest.c, #18903
        Attached File- => Added prb.c, #18902

    Back to the top


    Powered by Savane 3.7