Patch for Circular Paths (new algo) 70s->0.007s :)

[Andreas Ericsson]

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/