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

nap naparuba at gmail.com
Wed Jan 30 15:21:16 CET 2008


On Jan 30, 2008 3:04 PM, Andreas Ericsson <ae at op5.se> wrote:
>
> 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.

Ok

>
> > 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

Thanks, I'll do like this for the final 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).
Ok, I'll change this.

>
> * Indentation doesn't follow that which already exists in Nagios.
Ok, I'll change this too.

>
> >
> > 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.
Thanks.
Yes, I just optimize it. And it's just for host path for now. I'm
working for host, services and notifications dependencies.


Jean

>
> --
> 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/
> _______________________________________________
> Nagios-devel mailing list
> Nagios-devel at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/nagios-devel
>

-------------------------------------------------------------------------
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