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

[nap]

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?

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"


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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: config.c
Type: text/x-c
Size: 93706 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: config.c.patch
Type: application/octet-stream
Size: 4026 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: objects.c
Type: text/x-c
Size: 141746 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: objects.c.patch
Type: application/octet-stream
Size: 150 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: objects.h
Type: application/octet-stream
Size: 29558 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: objects.h.patch
Type: application/octet-stream
Size: 459 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20080130/1aaecb06/attachment-0003.obj>
-------------- 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