Patch for Circular Paths (new algo) 70s->0.007s :)
Andreas Ericsson
ae at op5.se
Wed Jan 30 15:04:55 CET 2008
nap wrote:
> Hi Ethan,
> Hi Everyone,
>
> I already send this message to the list by another adresse, but it
> failed (exchange server...), so I resend it.
>
>
> I saw on the documentation:
> "That means all you CompSci graduate students who have been emailing
> me about doing your thesis on Nagios can contribute some code back.
> :-)"
> I don't know who they are, but I try to do the job: change the
> algorithm of the circular check in order to have a O(n) complexity.
>
> My algo can optimise the circular check (for the moment, only the host
> part, but I'm working on the services part too). I use a personal
> modified version of the Deep First Search
> (http://en.wikipedia.org/wiki/Depth-first_search) (DFS)
>
> The hard work is already done: we've got link between parents->childs
> (the childs->parents link are not used). We "just" have to follow
> theses links.
>
> It's a recursive algo.
>
> All node are in the beginning unchecked (value =0), when we began to
> check them, it's temporary_checked (value=1). We check all childs if
> they are not already checked (here is the recursive part :) ).
> If a child is in state temporary_checked, there is a loop, not follow
> the link, make our status loop_inside (value=3),and return it.
> If the child is a ok state (value=2), ok no problem with the child.
> If the child is LOOP_DETECTED (value=3), do not follow the link, and
> we return our status=loop_inside.
> If all childs are OK or if we don't have child (no childs, no loop :)
> ), we are OK an return.
>
> The algo is ok for code with #ifdef NSCORE (I need the host link).
> If we does not have NSCORE, we can't use it. But in the major system
> it's ok isn't it?
>
Yes, the CGI's shouldn't ever read the un-expanded objects anyway, and
Nagios should never write circular parent chains to the objects.cache-
file, so whatever code there should be simply never kicks in.
> The modifications are in the files:
> *objects.h (to add macro DFS STATUS and add dfsCheckedStatus to host structure)
> *objects.c (to add DFS_UNCHECKED at the initialisation of host->
> dfsCheckedStatus)
> *config.c (add 2 fonctions: dfsStatus to get the status of a host, dfs
> for make the dfs algo for a host (and it's childs), and modifie the
> pre_flight_circular_check for call dfs on all node that need it (not
> already checked)).
>
> I know that the 2 function need to be in the objects.c, but I'll move
> them in the final patch.
>
> I generated a "big" conf to test it: 10000 hosts (milleservers.cfg),
> dependant of 100 parents (parents.cfg). The 10000 are not all looped.
> The loop are in the test.cfg file: 5 hosts, in a circular way.
>
> You can find the files (objects.c,h and config.c), the patch and the samples at:
> http://zegabes.free.fr/nagios/
>
> I put in this mail the code files and the patchs. The original files
> are from 2 hours ago.
>
> I try to make diff, but I don't know if they are ok with "patch"
>
They are, but such diffs are really hard to read. If you could redo the
patches like this:
cp -a nagios nagios.orig
cd nagios
# (hack, hack, hack)
diff -urN ../nagios.orig . > circular-parents.patch
and then send the file circular-parents.patch to this list, it'll be
a lot easier to review and apply.
Judging from what I've seen so far though, I have a few issues with
the code. It's only style so far. My head hurts when trying to review
diffs in non-unified format.
* Nagios code doesn't use CamelCase. Stick to snake_case for variables
and suchlike (it's actually proven that CamelCase is harder to read for
a majority of people and is much more often misspelled or misread).
* Indentation doesn't follow that which already exists in Nagios.
>
> CONFIG VERIFICATION TIMES (* = Potential for speedup with -x option)
> ----------------------------------
> Object Relationships: 0.972514 sec
> Circular Paths: 70.060319 sec *
> Misc: 0.004837 sec
> ============
> TOTAL: 71.037670 sec * = 70.060319 sec (98.6%) estimated savings
>
That's not entirely true though, as you aren't removing the circular paths
check entirely, just optimizing it. Anyways, this looks really good. Barring
any breakage in currently grok'ed config syntax, I think this is a really
nice optimization.
--
Andreas Ericsson andreas.ericsson at op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
More information about the Developers
mailing list