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


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

Submitter:  Ben Pfaff <blp>
Submitted:  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
* Mandatory Fields

Add a New Comment Rich Markup

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)

        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>
Group administrator


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

Attach Files:

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)

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    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 <jxie@tippingpoint.com>
        Attached File- Added prbtest.c, #18903
        Attached File- Added prb.c, #18902

    Back to the top

    Powered by Savane 3.13-0ba7.
    Corresponding source code