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

[Gabes Jean]

Hi Ethan,
Hi Everyone,


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? 

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 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) and the samples at:
http://zegabes.free.fr/nagios/

I put in this mail the code files. The original files are from 2 hours
ago.

Can you say me how we can make a "real" patch? Diff? but how can I have
the modified version and the original version in the same directory?
Thanks.

I hope this patch can help you, like Nagios help me every days :)

I'm working for make this algo for services, them clean all (in the good
files...) and apply the code typing of Nagios (here it's emacs one).

To find modification: search jean or Jean on the code ;)
*objects.h: L382 and the begining for DEFINE DFS*
*objects.c : L922 for default value for host
*config.c: the very end, before the pre_flight_circular_check

Here is a launch of Nagios -v with milleservers, parents and test.cfg:

My algo begin
Big problem on child :srv0 with root:srv4
Part of the loop problem on child :srv4 with root:srv3
Part of the loop problem on child :srv3 with root:srv2
Part of the loop problem on child :srv2 with root:srv1
Part of the loop problem on child :srv1 with root:srv0
My algo end
My Circular Paths:       0.006864 sec  *
Error: There is a circular parent/child path that exists for host
'srv0'!
Error: There is a circular parent/child path that exists for host
'srv1'!
Error: There is a circular parent/child path that exists for host
'srv2'!
Error: There is a circular parent/child path that exists for host
'srv3'!
Error: There is a circular parent/child path that exists for host
'srv4'!
Timing information on configuration verification is listed below.

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


***> One or more problems was encountered while running the pre-flight
check...


Great isn't it? original way:71.037670 new way: 0.006864 sec   (My
Circular Paths).

Let me know if you want more information, I'll say you when I'll finish
the services dependencies :)


Jean Gabes (alias: naparuba)

Ps: sorry for my english, I'm French, but I really try.

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