[tor-bugs] #7912 [Tor]: Cells that don't get inserted into cell queues can clog connection flushing

[Tor Bug Tracker & Wiki]

#7912: Cells that don't get inserted into cell queues can clog connection flushing
------------------------------------+---------------------------------------
 Reporter:  asn                     |          Owner:                    
     Type:  defect                  |         Status:  needs_review      
 Priority:  normal                  |      Milestone:  Tor: 0.2.4.x-final
Component:  Tor                     |        Version:                    
 Keywords:  tor-relay 023-backport  |         Parent:                    
   Points:                          |   Actualpoints:                    
------------------------------------+---------------------------------------
Changes (by nickm):

  * keywords:  tor-relay => tor-relay 023-backport


Comment:

 IMO this should be a backport candidate for 0.2.3.x.  We need to trade-off
 two factors there: the risk of not fixing it immediately, versus the risk
 of backporting a fix that isn't correct or tested too early.  Marking as
 "023-backport" -- let's do a fix in 0.2.4 and make sure nothing breaks
 before we backport.

 > It need to parse all queue to find any a queued destroy cell that has
 some circuitID, if queue huge enough then it leads to DoS. It's possible
 to create bitfield with present ID in the destroy queue but that req 4KB
 per conn.

 Hm. A linear search over 32K of cells does seem pretty excessive at first
 glance.  I ran a quick test, to see how slow a linear search over 65535
 cells would be (yes, I made sure the cells were fragmented in memory).  On
 my laptop, it took 4.6 msec per worst-case search.  Compare that to 2.4
 msec per old-style onion handshake, and we're feeling some pain there.

 There's an easier way to hold this stuff, so long as we're : Just use an
 array of uint16_t.  When I tried that, I got decent performance.  If we
 fake it with a smartlist holding uint16_t values in its void*s, we still
 only get 40 usec per worst-case search and 25 usec per worst-case memmove
 when removing the first entry.  The maximum size is higher, but less than
 would be needed for a cell queue.

 > The best fix in theory is to detach cell queues to independent creature
 and to use it as pipe that every time attached by one end to conn and
 another end attached to circuit if needed

 I agree that's a good design; let's save it for 0.2.5.

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