Alo Sarv
lead developer

Donate via
MoneyBookers

Latest Builds

version 0.3
tar.gz tar.bz2
Boost 1.33.1 Headers
MLDonkey Downloads Import Module Development
Payment completed
Development in progress.
Developer's Diary
irc.hydranode.com/#hydranode

Thursday, January 20, 2005

RangeList optimized, IpFilter engine implemented and tested

Optimizing RangeList logic was, as expected, the most time-consuming operation today. At the end, the key was to modify the sorting algorithm for the underlying rbtree to use the center-point of a range for comparing, e.g. (begin+end)/2. Based on that, I was able to optimize all of the remaining RangeList operations to take logarithmic time instead of former linear time.

Based on the new RangeList, I quickly threw together IPFilter API, as described in previous blog post. Currently, it's capable of loading only mldonkey format ipfilter file, I ran into some odd problems with parsing/loading emule-styled ipfilter.dat right now - hoping to get those fixed tomorrow.

Speed testing (46306 ranges)
Load time: 0.46s (0.33s in optimized build)
isAllowed() method lookup time: estimated 0.00005s per call
100'000 calls take 0.24s (0.17s in optimized build)
Memory usage: 1720 kb for 46306 entries

Madcat, ZzZz




Comments:
My thoughts about IPfilter file format...
You can implement a new (your) format or choose one of the existing ones to use (in the core) and we can create an import/export plug-in later for the rest of the available formats. I believe the core should have internal support for only the format it uses (support for more than one would be too much because we want to keep it small and fast, and this way you have less debugging in the core and make use of the plugins subsystem). This plug-in can have more features than just i/e like autoupdate from net etc.

One nice format should seperate the manual additions (and keep them after updates) from the downloaded plus incuding comments and be compressed XML file.

But all these should be implemented after the working core+ed2k release.

Keep up the good work and thanks for your time!
 
As i understand from the previous blog entry, you are now checking if ip is valid only before connecting to it. Wouldn't it be a better idea to check and drop blocked ips on receiving source list? this could *theoretically* reduce mem and cpu usage, couldn't it? :)
 
>---
> You can implement a new (your) format or choose one of the
> existing ones to use (in the core) and we can create an
> import/export plug-in later for the rest of the available
> formats. I believe the core should have internal support for
> only the format it uses (support for more than one would be
> too much because we want to keep it small and fast, and this
> way you have less debugging in the core and make use of the
> plugins subsystem). This plug-in can have more features than
> just i/e like autoupdate from net etc.
There are two arguments against this. First, parsing ipfilters is a very simple task (6 lines of code), so it causes no code bloat inside core. Secondly, when pushing ipfilter loading to a module, it could possibly introduce a race condition, where the ipfilter module is loaded after the p2p modules, in which case we might end up still connecting to blocked ip addresses. Thus, the ipfilter should be loaded when initializing networking subsystem, prior to modules loading. Nonetheless, modules can extend the ipfilter by submitting additional filters to networking subsystem.

>---
> One nice format should seperate the manual additions (and
> keep them after updates) from the downloaded plus incuding
> comments and be compressed XML file.
Yes. The scheduler supports multiple levels of ipfilters, and checks against all of those, so user-defined filters and filters downloaded from net can co-operate.

>---
> As i understand from the previous blog entry, you are now
> checking if ip is valid only before connecting to it.
> Wouldn't it be a better idea to check and drop blocked ips
> on receiving source list? this could *theoretically* reduce
> mem and cpu usage, couldn't it? :)
Yes, makes sense. The design allows such optimizations to be made inside modules, but the checks within the scheduler still remain.

Madcat.
 
Post a Comment



<< Home

This page is powered by Blogger. Isn't yours?