[tor-bugs] #7191 [Tor]: smartlist_bsearch_idx() is broken for short lists

[Tor Bug Tracker & Wiki]

#7191: smartlist_bsearch_idx() is broken for short lists
--------------------+-------------------------------------------------------
 Reporter:  andrea  |          Owner:  andrea            
     Type:  defect  |         Status:  needs_review      
 Priority:  major   |      Milestone:  Tor: 0.2.3.x-final
Component:  Tor     |        Version:  Tor: 0.2.4.3-alpha
 Keywords:          |         Parent:                    
   Points:          |   Actualpoints:                    
--------------------+-------------------------------------------------------

Comment(by nickm):

 Needs to be rebased onto maint-0.2.3.  (Example sequence: "git fetch
 origin ; git checkout -b bug7191_023; git rebase master --onto
 origin/maint-0.2.3")

 For 0.2.3 purposes, I wonder if some of the assertions couldn't turn into
 LD_BUG entries.  What do you think?

 I'd like to see the unit tests expanded to the point where every branch of
 this function is covered (as tested with gcov); is that now the case?

 Is there some well-documented binary search whose implementation we now
 match? It seems silly not to crib from Dijkstra or Knuth or whomever,
 given that we already screwed this up once, unless there's a great reason.

 While we're bulletproofing this, it looks like (lo + hi)/2 will hit an
 integer overflow if we get an array of over one billion elements on an
 architecture where int is 32 bits.  Might as well fix that too.

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/7191#comment:5>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online