[Nsock] Scalable event handling

[Henri Doreau <henri.doreau () gmail com>]

Hello,

TL;DR:
Here is a (big) patch that makes nsock considerably faster by reducing
the overhead of spawning timers, and by extensively using them.
Testing would be much appreciated, especially on windows, where I
became quite good at breaking things recently.

Longer version:
I'm working on cleaning and optimizing nsock, for the fun of it and
because of the plans we have to add features (like proper ssl proxy
support) and to eventually use nsock for connect scan. I'd eventually
like to introduce a hooking framework into nsock, so that both proxy
handlers and SSL code could transparently intercept and overload
connect/read/write operations. Overloading would consist in adding
events internally.

The problem is that adding many events is currently quite expensive.
You can easily observe it by stressing nsock a bit, via nping[1] for
instance. The reason why it's that slow is because each iteration of
the runloop goes through _all_ events and check for completion (I/O or
timeout).

This big patch (it'd be complicated to split it...) I'm proposing here
makes nsock iterate over the active events only. IOW only IODs that
either have I/Os to handle or expired events are processed at each
iteration. I had to change the internal data structures for that:

  * Introduced a gh_heap data structure, to efficiently make priority
queues. All "expirables" (timers and timeouts) are now handled via
such a tree. So that we don't need to iterate over _all_ elements at
each nsock loop, only the active I/O events and the expired timers and
I/O events are processed. Needless to say that the difference is
noticeable when you have tens of thousands of events queued!

  * Replaced gh_lists containers by embedded objects (intrusive data
structure). All operations are inline, and adding an item to a list
doesn't allocate extra memory. It's needed so that we can manipulate
the events lists simply from events that we extract from the gh_heap.

  * Added corresponding unit tests.

Canceling events remains a slow operation (gh_radix_tree is to come
and fix that).


nping_tcp_connect_high.png (attached) is a graph of nping execution
times obtained by pingflooding a loopback interface[1] w/ and w/o the
patch, showing what the speedup can be.

I have gprof results, that I can send if desired, but I don't want to
flood the list with too many attachments. I would also encourage
testers to give it a try themselves.

Patch generated via git, let me know if you prefer another format or
if you want me to open a dedicated branch on nmap-exp.

Regards

[1] nping --tcp-connect -p 4444 --delay 0 -c 10000 localhost

--
Henri

Attachment: nsock_gh_heap.patch
Description:

_______________________________________________
Sent through the dev mailing list
http://nmap.org/mailman/listinfo/dev
Archived at http://seclists.org/nmap-dev/