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

 
 

bug #26377: trb_delete() makes bad memory access

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

Add a New Comment Rich Markup
   

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

 

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

Attach Files:
   
   
Comment:
   

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
  •  

    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.

     

    Follows 1 latest change.

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

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code