[asterisk-bugs] [Asterisk 0017277]: [patch] The heap data structure can't cope with a removal and reinsert

[Asterisk Bug Tracker]

A NOTE has been added to this issue. 
====================================================================== 
https://issues.asterisk.org/view.php?id=17277 
====================================================================== 
Reported By:                cappucinoking
Assigned To:                russell
====================================================================== 
Project:                    Asterisk
Issue ID:                   17277
Category:                   Tests/General
Reproducibility:            always
Severity:                   block
Priority:                   normal
Status:                     assigned
Asterisk Version:           SVN 
JIRA:                       SWP-1405 
Regression:                 No 
Reviewboard Link:            
SVN Branch (only for SVN checkouts, not tarball releases): 1.6.2 
SVN Revision (number only!):  
Request Review:              
====================================================================== 
Date Submitted:             2010-05-03 12:42 CDT
Last Modified:              2010-05-06 08:58 CDT
====================================================================== 
Summary:                    [patch] The heap data structure can't cope with a
removal and reinsert
Description: 
Whilst looking into why qualify events are being scheduled out of sequence
I started looking into why items on the maxheap weren't in the correct
order.
The qualify code is a different use case then the current tests allow for.
When a response to a qualify request is made, the event is rescheduled via
a remove and re-add to the maxheap structure.
I have written a test to demonstrate the failure of the heap to keep the
items in order when removing and re-inserting items.

======================================================================
Relationships       ID      Summary
----------------------------------------------------------------------
related to          0016936 [patch] Qualify frequency has big pause...
====================================================================== 

---------------------------------------------------------------------- 
 (0121466) svnbot (reporter) - 2010-05-06 08:58
 https://issues.asterisk.org/view.php?id=17277#c121466 
---------------------------------------------------------------------- 
Repository: asterisk
Revision: 261496

U   trunk/main/heap.c

------------------------------------------------------------------------
r261496 | russell | 2010-05-06 08:58:07 -0500 (Thu, 06 May 2010) | 40
lines

Fix handling of removing nodes from the middle of a heap.

This bug surfaced in 1.6.2 and does not affect code in any other released
version of Asterisk.  It manifested itself as SIP qualify not happening
when
it should, causing peers to go unreachable.  This was debugged down to
scheduler
entries sometimes not getting executed when they were supposed to, which
was in
turn caused by an error in the heap code.

The problem only sometimes occurs, and it is due to the logic for removing
an entry
in the heap from an arbitrary location (not just popping off the top). 
The scheduler
performs this operation frequently when entries are removed before they
run (when
ast_sched_del() is used).

In a normal pop off of the top of the heap, a node is taken off the
bottom,
placed at the top, and then bubbled down until the max heap property is
restored
(see max_heapify()).  This same logic was used for removing an arbitrary
node
from the middle of the heap.  Unfortunately, that logic is full of fail. 
This
patch fixes that by fully restoring the max heap property when a node is
thrown
into the middle of the heap.  Instead of just pushing it down as
appropriate, it
first pushes it up as high as it will go, and _then_ pushes it down.

Lastly, fix a minor problem in ast_heap_verify(), which is only used for
debugging.  If a parent and child node have the same value, that is not an
error.  The only error is if a parent's value is less than its children.

A huge thanks goes out to cappucinoking for debugging this down to the
scheduler,
and then producing an ast_heap test case that demonstrated the breakage. 
That
made it very easy for me to focus on the heap logic and produce a fix. 
Open source
projects are awesome.

(closes issue https://issues.asterisk.org/view.php?id=16936)
Reported by: ib2
Tested by: cappucinoking, crjw

(closes issue https://issues.asterisk.org/view.php?id=17277)
Reported by: cappucinoking
Patches:
      heap-fix.rev2.diff uploaded by russell (license 2)
Tested by: cappucinoking, russell

------------------------------------------------------------------------

http://svn.digium.com/view/asterisk?view=rev&revision=261496 

Issue History 
Date Modified    Username       Field                    Change               
====================================================================== 
2010-05-06 08:58 svnbot         Checkin                                      
2010-05-06 08:58 svnbot         Note Added: 0121466                          
======================================================================