[tor-bugs] #10116 [Tor]: Avoid memory allocation in OOM handler

[Tor Bug Tracker & Wiki]

#10116: Avoid memory allocation in OOM handler
---------------------------+------------------------------------
 Reporter:  nickm          |          Owner:
     Type:  enhancement    |         Status:  new
 Priority:  normal         |      Milestone:  Tor: 0.2.5.x-final
Component:  Tor            |        Version:
 Keywords:  tor-relay oom  |  Actual Points:
Parent ID:                 |         Points:
---------------------------+------------------------------------
 Right now, the OOM handler allocates an array of size(n_circs *
 sizeof(void*)) to figure out which circuits to kill.  That's probably not
 a good idea.  Instead, it would be better to select the select circuits
 from the circuitlist.

 Options here include:
   * Turn global_circuitlist into an array (smartlist) structure.
   * Retain the linked-list structure, but do one of these:
     * Use a merge sort to sort the circuitlist in place.
     * Do an O(N^2) algorithm to walk the circuitlist to find the worst
 circuit, delete that, and then do it over and over until we have killed
 enough circuits.
     * Do an O(Nk) algorithm to walk the circuitlist to find the k worst
 circuits; kill them; repeat until we have killed enough circuits. This
 still turns out to O(N^2)

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