Re: [Nagios-devel] Patch for Circular Paths (new algo) 70s->0.007s
Posted: Wed Jan 30, 2008 6:21 am
On Jan 30, 2008 3:04 PM, Andreas Ericsson 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 speedu
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]
>
> 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 speedu
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]