Menu
▾
▴
[Devmon-devel] Topological sort
|
From: Nelis, W. <Wim...@nl...> - 2010-12-20 14:51:09
|
Hello,
when Devmon evaluates the transforms in a template, it uses a recursive algorithm to resolve the dependencies between the OIDs. In the patch below, the evaluation is divided into two steps. First the order of the evaluation of the OIDs is determined using a topological sort. Then, the OIDS are evaluated, without recursion, in the order determined in the previous step. An added benefit of a topological sort is that it detects any circular dependency chains in a simple and robust manner.
The patch on Devmon below is NOT complete: the implementation for a multinode environment is still missing, as I have no means to test it. Although it is possible to sort the OIDs just after reading them from the database, a better approach is probably to save the sorted list of OIDs in the database as well.
The patch is published in the hope that someone is both interested and willing to extend and test it in a multinode environment. The patch uses the "/trunk" Devmon version 187 as the base. It is in use at our site for over half a year, without apperent problems. I had the impression that the runtime of Devmon was lowered with about 1 second, on a total average run-time of about 70 seconds, but after a few days the total average run-time was back to it's original value.
Index: dm_templates.pm
===================================================================
--- dm_templates.pm (revision 9)
+++ dm_templates.pm (working copy)
@@ -439,7 +439,6 @@
# Define our valid transforms functions
my %trans = ();
my $deps = {};
- my $path = [];
# Define the file; make sure it exists and is readable
@@ -684,13 +683,15 @@
and delete $trans{$oid} and next
if !defined $tmpl->{'oids'}{$dep_oid} and !defined $trans{$dep_oid};
- $deps->{$oid}{$dep_oid} = {};
+ $deps->{$dep_oid}{$oid} = {};
}
}
- # Find dependency loops (tricky!)
- my $val = find_deps($deps, \%trans, $path);
- return 0 if $val == 0;
+ # Sort the OIDs in a order in which they need to be calculated. At the same
+ # time any dependency loop is found and reported.
+ my $val = sort_oid( $deps );
+ return 0 unless defined $val;
+ $tmpl->{'sort'} = $val;
# Now add the translations to the global hash
for my $oid (keys %trans) {
@@ -704,59 +705,65 @@
}
+ #
+ # Function sort-oid sorts the OIDs used in the transformations in a order
+ # in which they are to be calculated: each OID is sorted after the OIDs it
+ # depends on.
+ # At the same time, it checks the dependencies for any circular chains. If no
+ # such chain is found, this function returns a reference to the sorted list of
+ # OIDs. If at least one circular chain is found, the returned value is undef.
+ #
+ # This function uses the topological sort method.
+ #
+ sub sort_oid($) {
+ my $deps= $_[0] ;
+ my @Sorted= () ; # Sorted list of OIDs
+ my %Cnt= () ; # Dependency counters
+ my ($oid,$mods) ; # Loop control variables
+
+ #
+ # Build table %Cnt. It specifies for each OID the number of other OIDs which
+ # are needed to compute the OID.
+ #
+ foreach $oid ( keys %$deps ) {
+ $Cnt{$oid}= 0 unless defined $Cnt{$oid} ;
+ foreach ( keys %{$$deps{$oid}} ) {
+ $Cnt{$_}= 0 unless defined $Cnt{$_} ;
+ $Cnt{$_}++ ;
+ } # of foreach
+ } # of foreach
+
+ #
+ # Sort the OIDs. If for a given OID no other OIDs are needed to compute its
+ # value, move that OID to the sorted list and decrease the counts of each OID
+ # which is computed using this OID. This process is repeated until no OIDs can
+ # be moved any more. Any remaining OIDs, mentioned in %Cnt, must be in a
+ # circular chain of dependencies.
+ #
+ $mods= 1 ; # End-of-loop indicator
+ while ( $mods > 0 ) {
+ $mods= 0 ; # Preset mod-count of this pass
+ foreach $oid ( keys %Cnt ) {
+ next unless $Cnt{$oid} == 0 ;
+ if ( defined $$deps{$oid} ) {
+ $Cnt{$_}-- foreach keys %{$$deps{$oid}} ;
+ $mods++ ; # A counter is changed
+ } # of if
+ push @Sorted, $oid ; # Move OID to sorted list
+ delete $Cnt{$oid} ;
+ } # of foreach
+ } # of while
+
+ if ( keys %Cnt ) {
+ do_log( "The following OIDs are in one or more circular depency chains: " .
+ join(', ',sort keys %Cnt), 0 ) ;
+ return undef ; # Circular dependency chain found
+ } else {
+ return \@Sorted ; # No circular dependency chains found
+ } # of else
+ } # of sort_oid
- # Build a dependency tree for translated oids and find any loops
- # or missing oids that defined ones may be dependent on
- sub find_deps {
- my ($deps, $trans, $path) = @_;
- # Our path variable keeps track of where in the tree we are
- @$path = () if !defined $path;
-
- # pointer variable to act as a placeholder for our current spot in the tree
- my $pointer = \%{$deps};
- for my $pt (@$path) {$pointer = \%{$pointer->{$pt}}}
-
- # Now iterate through the oids in our current spot in the tree
- for my $oid (keys %$pointer) {
-
- # Update our path
- push @$path, $oid;
-
- # Determine our root id, used later for troubleshooting
- my $root_oid = $path->[0];
-
- # See if this variable is preset in the translation hash
- if(defined $trans->{$oid}) {
- # If it is, see if it has other oids that it depends on
- my $data = $trans->{$oid}{'data'};
- while($data =~ s/\{(.+?)\}//) {
-
- # It depends on other oids; iterate into them to make sure that
- # they are defined and that we dont loop back and depend on a
- # oid defined somewhere earlier in our path
- my $dep_oid = $1;
- my @temp = @$path;
- while (my $path_oid = shift @temp) {
- next if $path_oid ne $dep_oid;
- do_log("$root_oid has a looped dependency: " .
- join('->', @$path), 0);
- return 0;
- }
- $pointer->{$oid}{$dep_oid} = {}
- if !defined $pointer->{$oid}{$dep_oid};
- my $val = find_deps($deps, $trans, $path);
- return 0 if $val == 0;
- }
- }
- pop @$path;
- }
-
- return 1;
- }
-
-
-
# Subroutine to read in the thresholds file
sub read_thresholds_file {
my ($dir, $tmpl) = @_;
Index: dm_tests.pm
===================================================================
--- dm_tests.pm (revision 8)
+++ dm_tests.pm (working copy)
@@ -38,7 +38,6 @@
my %speeds = ( 1 => '[b/s]', 10**3 => '[kb/s]', 10**6 => '[Mb/s]',
10**9 => '[Gb/s]', 10**12 => '[Tb/s]', 10**15 => '[Pb/s]');
-
# Main test subroutine; parse data and feed it to the individual
# test-specific subs
sub tests {
@@ -95,19 +94,11 @@
$g{'hobbit_color'}{$device} eq 'green') {
# First transform any data and do threshold evaluations
- my @translist = keys %$oids;
- my %skiplist = ();
- for my $oid (@translist) {
+ for my $oid ( @{$$tmpl{'sort'}} ) {
# Only transform if we dont already have values for this oid
- next if !$oids->{$oid}{'transform'} or
- defined $oids->{$oid}{'val'};
- # Only transform if we have dependent value, otherwise push onto end of queue (not a perfect solution, but better than before)
- if(ref $oids->{$oid}{trans_data} eq "HASH" && ! defined $oids->{$oids->{$oid}{trans_data}{dep_oid}}{val}) {
- do_log("Skipping oid $oid until ".$oids->{$oid}{trans_data}{dep_oid}." defined for $device") if $g{debug};
- push @translist,($oid) unless $skiplist{$oid}++;
- } else {
- transform($device, $oids, $oid, $thr);
- }
+ next if !$oids->{$oid}{'transform'};
+ next if defined $oids->{$oid}{'val'};
+ transform($device, $oids, $oid, $thr);
}
}
@@ -220,17 +211,11 @@
sub transform {
my ($device, $oids, $oid, $thr) = @_;
- return if defined $oids->{$oid}{'val'};
+# return if defined $oids->{$oid}{'val'};
# Shortcut to our snmp data
my $trans_type = $oids->{$oid}{'trans_type'};
my $trans_data = $oids->{$oid}{'trans_data'};
- # Transform any oids that we depend on before we finish this one
- for my $dep_oid ($trans_data =~ /\{(.+?)\}/g) {
- transform($device, $oids, $dep_oid)
- if $oids->{$dep_oid}{'transform'};
- }
-
# Make sure we inherit repeatability from previous types
my $trans_sub = "trans_" . $trans_type;
no strict 'refs';
Regards,
Wim Nelis.
*******************************************************************************************************
The NLR disclaimer (http://www.nlr.nl/emaildisclaimer) is valid for NLR e-mail messages.
*******************************************************************************************************
|
