[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 andrea):

 Replying to [comment:5 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")

 Okay.

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

 Hmm - if we adopt a policy like that, won't it make it a pain in the ass
 to change all asserts to LD_BUG logs when dev branches become stable in
 the future?  Maybe we should have a macro that turns into an assert or an
 LD_BUG as appropriate?

 > 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?

 I've attached gcov output; looks like the only case we still need is a
 list element that compares less than the search key at the end of the list
 (line 620, etc.); I think that'll need a longer list to test.  I'll add
 something to the test suite for it.

 > 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.

 Hmm - I didn't look.  Possible.

 > 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.

 Yeah.

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