bugGNU libavl - Bugs: bug #26377, trb_delete() makes bad memory...


bug #26377: trb_delete() makes bad memory access

Submitted by:  Ben Pfaff <blp>
Submitted on:  Tue 28 Apr 2009 03:10:27 AM UTC  
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Confirmed
Privacy:  Public Assigned to:  Ben Pfaff <blp>
Open/Closed:  Open

Add a New Comment (Rich Markup)

You are not logged in

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


Tue 04 May 2021 06:45:31 PM UTC, comment #5: 

libavl definitely needs to change to fix this problem.

Until then, GCC or Clang users can use -fno-strict-aliasing.

Ben Pfaff <blp>
Project AdministratorIn charge of this item.
Mon 03 May 2021 05:33:37 PM UTC, comment #4: 

Yes, this bug is caused by the practice described as a "dirty trick" in bst.w.  That section describes one way this kind of trick can cause undefined behavior, correctly, but misses the fact that this technique almost always causes undefined behavior.  In C referring to the same memory through two different "incompatible" types is undefined behavior.  The two structures here are incompatible because they aren't comprised of the same number of fields.  In this case the compiler is not obligated to produce a correct program.

I know that so much C and C++ code is written in this way that it feels normal to some people, but this has been "undefined behavior" for decades, and code that happens to work does so only by accident -- i.e. the optimizer hasn't produced bad code only by hapenstance.

I see this bug manifest with crahes in the lavl and lrb implementations, where codes use the dirty trick but also refers to table->root within the same function.

In this case, I think the compiler makes the assumption that table->root hasn't been modified because it has only been modified through a completely different type (node->links[0]).  The compiler is allowed to do this.

bst.w mentions my preferred alternative:

> As an alternative, we can declare an actual instance of |struct bst_node|, store the tree's |bst_root| into its |bst_link[0]|, and copy its possibly updated value back into |bst_root| when done.  This isn't very elegant, but it works.  This technique is used much later in this book, in @<TBST main copy function@>.  A different kind of alternative approach is used in @value{bstprobedblptrbrief}. @end exercise

Perhaps all of libavl should move to this approach?

Matt Armstrong <matta>
Sat 09 Jul 2011 05:45:47 PM UTC, comment #3: 

Steven Noonan <steven@uplinklabs.net> also reported this bug, on June 30, 2011.

Ben Pfaff <blp>
Project AdministratorIn charge of this item.
Tue 15 Feb 2011 05:35:14 PM UTC, comment #2: 

James Howse <jhowse@lanl.gov> also reported this bug, on Feb. 14, 2011.

Ben Pfaff <blp>
Project AdministratorIn charge of this item.
Tue 12 May 2009 01:29:03 AM UTC, comment #1: 

I found the reason, the problem is caused by aliasing, compiler optimization, when in debug mode, all are ok. when compile with full optimization, it cause error. &tree->trb_root is modified by another pointer[(struct trb_node*)&tree->trb_root], after *)&tree->trb_root was modified, compiler use the old value of it. then the error appeared.

leipeng <rockeet>
Tue 28 Apr 2009 03:10:27 AM UTC, original submission:  

From Shaun Sharples <shaun.sharples@gmail.com>:

[in trb_delete]

&tree->trb_root points to trb_tree, not trb_node which works for the
rb_tree case (only comparing rb_link which mirrors rb_root), but for
trb_tree 'p->trg_tag[dir] == TRB_THREAD' doesn't make sense

Ben Pfaff <blp>
Project AdministratorIn charge of this item.


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

Attach Files:

No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


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

    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.




    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-04-28 blp Carbon-Copy- => Added shaun sharples

    Back to the top

    Powered by Savane 3.7