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

[nap]

Hi list,

I finish my patch for the host path part. I try to folow the
indentation and the coding style of nagios.
you can find test files with a lot of parent/childs at
http://zegabes.free.fr/nagios/ .

I try to generate a big configuration for service dependencies (4000
dependencies) but it's ok (0.2s). So I don't know if I'vegot to check
it if it's already ok. Someone got problem with this check or it's was
just with host path check?

Ask me if you have a question about my patch, or if it need more work
for include it into a official version of nagios.

Thanks,


Gabes Jean

On Jan 30, 2008 3:21 PM, nap <naparuba at gmail.com> wrote:
>
> 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
> >
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: circular-parents.patch
Type: text/x-patch
Size: 6441 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080131/d93c1a2e/attachment.bin>
-------------- next part --------------
-------------------------------------------------------------------------
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/
-------------- next part --------------
_______________________________________________
Nagios-devel mailing list
Nagios-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nagios-devel