Re: [Nagios-devel] Patch for Circular Paths (new algo) 70s->0.007s
Posted: Tue Jan 29, 2008 1:18 am
------_=_NextPart_001_01C86257.7F65A6D1
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Oups, I forgot the files :p
Jean
-----Message d'origine-----
De=A0: [email protected] =
[mailto:[email protected]] De la part de Gabes =
Jean
Envoy=E9=A0: mardi 29 janvier 2008 10:06
=C0=A0: Nagios Developers List; [email protected]
Objet=A0: [Nagios-devel] Patch for Circular Paths (new algo) 70s->0.007s =
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 =3D0), when we began to
check them, it's temporary_checked (value=3D1). We check all childs if
they are not already checked (here is the recursive part ).=20
If a child is in state temporary_checked, there is a loop, not follow
the link, make our status loop_inside (value=3D3),and return it.
If the child is a ok state (value=3D2), ok no problem with the child.
If the child is LOOP_DETECTED (value=3D3), do not follow the link, and =
we
return our status=3Dloop_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?=20
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
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Oups, I forgot the files :p
Jean
-----Message d'origine-----
De=A0: [email protected] =
[mailto:[email protected]] De la part de Gabes =
Jean
Envoy=E9=A0: mardi 29 janvier 2008 10:06
=C0=A0: Nagios Developers List; [email protected]
Objet=A0: [Nagios-devel] Patch for Circular Paths (new algo) 70s->0.007s =
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 =3D0), when we began to
check them, it's temporary_checked (value=3D1). We check all childs if
they are not already checked (here is the recursive part
).=20If a child is in state temporary_checked, there is a loop, not follow
the link, make our status loop_inside (value=3D3),and return it.
If the child is a ok state (value=3D2), ok no problem with the child.
If the child is LOOP_DETECTED (value=3D3), do not follow the link, and =
we
return our status=3Dloop_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?=20
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
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]