[SCM] Samba Shared Repository - branch master updated
Andrew Bartlett
abartlet at samba.org
Fri May 29 05:56:03 MDT 2015
The branch, master has been updated
via 29546f2 KCC: test suite for the graph_utils
via b08f454 KCC: rename 'repsFrom_%s_all' graphs --> 'all-repsFrom_%s' for better sort order
via 2f3ce17 KCC: more debugging changes
via c3dc87e KCC: (doc) explain intrasite max edge count a bit better
via 87c68e0 KCC: remove print statements from kcc_utils
via 898d8b3 KCC: pep8/flake8 fixes for samba_kcc
via 08e41b4 KCC: more pep8 for kcc_utils
via edacc03 KCC: pep8 pass over graph_utils.py
via 4e78185 KCC: add graph tests of robustness against edge and vertex failure
via cb8b99e KCC: improve directed_double_ring graph check
via 75eedf8 KCC: --test-all-reps-from uses same random seed for all DSAs
via 326c503 KCC: RODCs are their own bridgeheads
via 722e6fa KCC: ignore non-IP transports more thoroughly
via b9f75c8 KCC: don't create duplicate DSA objects
via f7b088e KCC: Add more debugging and fix a comment
via fa3c552 KCC: use 75% fewer lines to assign a Boolean to a variable
via 7a6d0b6 KCC: A woeful warning comment about the state of our code
via 4c5761c KCC: Debugging changes -- including DEBUG_FN() function
via d0f9f32 KCC: Fail earlier if there is no IP transport
via 7ac5974 KCC: graph the result of partial edge reversal
via 8c8acd2 KCC: merge copy_output_edges into get_spanning_tree_edges
via 91d87ca KCC: move get_spanning_tree_edges out of KCC object
via 04c678f KCC: slight rewrite for the sake of pep8
via 6200432 KCC: remove essentially dead code
via b75ec6d KCC: add a warning about repsFRom magic objects
via 4ffd37d KCC: more pep8, using temp variables in places
via 4770bc0 KCC: fix square bracket padding for pep8
via 15dfb58 KCC: deduplicate connection schedule creation
via 768d79c KCC: reformat kcc_util object __str__ for pep8
via e33fe2b KCC: pep8 conformance
via f023409 KCC: raise KCCError instead of vanilla Exception
via 5546f84 KCC: Adds some comments and rearrange translate_ntdsconn()
via b4e4f8a KCC: remove another needless loop variable
via 39da46e KCC: Help RW DCs to ignore RODCs when doing kcc
via ceb6ab9 KCC: use less verbose constructions in a few places
via 13388e3 KCC: produce fewer dot graphs unless --debug is used
from d6f1215 KCC: avoid (so far harmless) variable name clash
https://git.samba.org/?p=samba.git;a=shortlog;h=master
- Log -----------------------------------------------------------------
commit 29546f2f9fe96e28dfab88ae84269758d6e9e3e7
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Apr 14 14:46:12 2015 +1200
KCC: test suite for the graph_utils
This found a few bugs in the tests which were fixed.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
Autobuild-User(master): Andrew Bartlett <abartlet at samba.org>
Autobuild-Date(master): Fri May 29 13:55:54 CEST 2015 on sn-devel-104
commit b08f4541962f70121c32f17ee1b5d59ef86baa7e
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Apr 14 14:35:15 2015 +1200
KCC: rename 'repsFrom_%s_all' graphs --> 'all-repsFrom_%s' for better sort order
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 2f3ce1753ae6b1af9986c2ed3b3d7fe8272700c2
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Apr 14 14:31:05 2015 +1200
KCC: more debugging changes
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit c3dc87eac021fdb6c942a512429ed6ca973e32b0
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Apr 14 10:12:48 2015 +1200
KCC: (doc) explain intrasite max edge count a bit better
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 87c68e0bc9e1b41755bb549d17ee1d9ed43ed980
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 15:04:44 2015 +1200
KCC: remove print statements from kcc_utils
debug noise should not go to stdout
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 898d8b39876373002466b5e2b7efd58dbcc192cd
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 15:02:00 2015 +1200
KCC: pep8/flake8 fixes for samba_kcc
Also note a couple of unused variables. I am not removing them yet
in case their intended use turns up.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 08e41b42af6a5e4f3c1252e55cc78aa5994ca083
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 15:00:55 2015 +1200
KCC: more pep8 for kcc_utils
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit edacc0314f6a76735304aded58f7530d6801621e
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 14:45:08 2015 +1200
KCC: pep8 pass over graph_utils.py
Using the `flake8` tool, which also spots e.g. unused imports.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 4e781857e3d682e0012ff340ad1e9b199c723b67
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 14:31:17 2015 +1200
KCC: add graph tests of robustness against edge and vertex failure
These tests are themselves tested in a later patch.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit cb8b99e335101c5454a1e448275993aa18f77e10
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 9 13:55:40 2015 +1200
KCC: improve directed_double_ring graph check
The previous test assumed there would be only a double directed ring
but in fact there could be other edges. In large graphs there are
certain to be more edges.
Now we want to be sure there is a complete ring apart from any other
connections. This is called the Hamiltonian path problem and takes
exponential time in general, so now our test is that it looks *quite*
a lot like a complete ring.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 75eedf85b1516f0b2370d23d6ff1058a70b093b0
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 8 13:40:53 2015 +1200
KCC: --test-all-reps-from uses same random seed for all DSAs
Otherwise some of the links end up different for each KCC run. That is
expected and proper, but it is confusing.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 326c503925eb93e46fd1def01a465e5f6dbe3d66
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 15:50:40 2015 +1300
KCC: RODCs are their own bridgeheads
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 722e6fa900736f686ed60126a92aa56b7ef51400
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 15:46:55 2015 +1300
KCC: ignore non-IP transports more thoroughly
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit b9f75c8f1a1b28f7a6ae8ab36e970a0e120f1cb6
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 15:11:12 2015 +1300
KCC: don't create duplicate DSA objects
load_site() returns the canonical site even if it didn't make it
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit f7b088efa522d75365b64baf17d1d4f8e1a26e25
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 11:15:58 2015 +1300
KCC: Add more debugging and fix a comment
It seems I lost my train of thought in that comment.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit fa3c552d3a4ef0f2214af6f5fbbeb618ce5350bd
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 11:12:13 2015 +1300
KCC: use 75% fewer lines to assign a Boolean to a variable
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 7a6d0b637a9547aa0b7ae3d794338140fa6322f5
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 11:04:28 2015 +1300
KCC: A woeful warning comment about the state of our code
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 4c5761c057be345d64e6d4e14924f9cad4d51f62
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Apr 2 11:03:42 2015 +1300
KCC: Debugging changes -- including DEBUG_FN() function
DEBUG_FN(msg) prefixes the msg with the function name and line no.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit d0f9f32d0a912972b5b23a4c9015a706d539b638
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 17:46:43 2015 +1300
KCC: Fail earlier if there is no IP transport
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 7ac59745b399740b675d4cf9e635c709c7ac67ae
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed May 20 13:01:55 2015 +1200
KCC: graph the result of partial edge reversal
What it shows is we don't ever reverse an edge because we have no
partial replica in our test.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 8c8acd22a6335ace24998293476dba2c0427d04f
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed May 20 12:59:31 2015 +1200
KCC: merge copy_output_edges into get_spanning_tree_edges
copy_output_edges() was rearranging the edges, not copying them, and
it wasn't used elsewhere.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 91d87cae3603a3b559708ac884d2e821448a4dbc
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 16:33:10 2015 +1300
KCC: move get_spanning_tree_edges out of KCC object
It doesn't use the object parameters, and might be better in another
module (e.g. graph_utils) with the other graph stuff.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 04c678fd0858a21241b81746184e110791799137
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 15:29:14 2015 +1300
KCC: slight rewrite for the sake of pep8
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 6200432d85a212b81687eefc53e96129a4388a07
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 15:28:26 2015 +1300
KCC: remove essentially dead code
As the removed comment noted, the logic goes:
if partial: # ~60 lines up
if not partial:
...
and we have kept it there for this long because the spec implies it.
(As a matter of fact I can't see how this entire `if partial` loop does
anything of consequence, given the previous loop didn't exclude the
partial case).
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit b75ec6d7fa645ef9e648842f70c1c26446219b32
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed May 20 12:29:17 2015 +1200
KCC: add a warning about repsFRom magic objects
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 4ffd37df5e4a080af4aa2ab409b26cc0bded9ec4
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed May 20 12:28:17 2015 +1200
KCC: more pep8, using temp variables in places
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 4770bc0f62e99614220f95a964dcfe4e5d0fdc9c
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 14:05:04 2015 +1300
KCC: fix square bracket padding for pep8
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 15dfb58424d65d88e32fdc4ca778764ac6a5817d
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 14:04:16 2015 +1300
KCC: deduplicate connection schedule creation
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 768d79c7037aa5c959e5e93644fbaa0b4b17db68
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 13:49:24 2015 +1300
KCC: reformat kcc_util object __str__ for pep8
Many lines were too long, which is to a large extent fixed by replacing
`text = text +` with `text +=`.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit e33fe2bf2435763382a2251d3ddb5ddcdb0aabbb
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 13:46:32 2015 +1300
KCC: pep8 conformance
I ran the files through the pep8 command-line tool.
Most changes are for line length, inline comment formatting, adjusting
numbers of blank lines, and the indentation of conditions on if
statements.
This is pretty useless work, but I thought I would have a go with the
pep8 tool, and it came up with a lot of complaints.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit f02340979141ebd7659fa9a19ccb9f0a5c592463
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Apr 1 10:46:29 2015 +1300
KCC: raise KCCError instead of vanilla Exception
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 5546f846e26f9110a04210c96a79918fb1b0865f
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Mar 27 18:12:20 2015 +1300
KCC: Adds some comments and rearrange translate_ntdsconn()
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit b4e4f8ae3b7e3963a5fe904951ba6024a90c6221
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Mar 27 18:10:34 2015 +1300
KCC: remove another needless loop variable
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 39da46e72c20a089efe2a2c66bca7342b87bec13
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Mar 27 18:08:53 2015 +1300
KCC: Help RW DCs to ignore RODCs when doing kcc
As far as writable DCs are concerned, RODCs don't even exist. So we make
tables that leave out the RO ones.
An RODC needs to know itself as well as writable DCs, so we add it in
that case.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit ceb6ab99b5b352ebcdf648581ec92ae34e236ba5
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Mar 27 17:54:50 2015 +1300
KCC: use less verbose constructions in a few places
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 13388e3fced000de1522ce044bad9d8b09f35a5d
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Mar 27 17:52:47 2015 +1300
KCC: produce fewer dot graphs unless --debug is used
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Garming Sam <garming at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
-----------------------------------------------------------------------
Summary of changes:
python/samba/graph_utils.py | 252 ++++++----
python/samba/kcc_utils.py | 531 ++++++++++-----------
python/samba/tests/graph_utils.py | 162 +++++++
selftest/tests.py | 1 +
source4/scripting/bin/samba_kcc | 963 +++++++++++++++++++++-----------------
5 files changed, 1112 insertions(+), 797 deletions(-)
create mode 100644 python/samba/tests/graph_utils.py
Changeset truncated at 500 lines:
diff --git a/python/samba/graph_utils.py b/python/samba/graph_utils.py
index 9e97c62..a01e068 100644
--- a/python/samba/graph_utils.py
+++ b/python/samba/graph_utils.py
@@ -18,35 +18,36 @@
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
-import sys
import itertools
#colours for prettier logs
-C_NORMAL = "\033[00m"
-DARK_RED = "\033[00;31m"
+C_NORMAL = "\033[00m"
+DARK_RED = "\033[00;31m"
RED = "\033[01;31m"
-DARK_GREEN = "\033[00;32m"
-GREEN = "\033[01;32m"
-YELLOW = "\033[01;33m"
-DARK_YELLOW = "\033[00;33m"
-DARK_BLUE = "\033[00;34m"
-BLUE = "\033[01;34m"
-PURPLE = "\033[00;35m"
-MAGENTA = "\033[01;35m"
-DARK_CYAN = "\033[00;36m"
-CYAN = "\033[01;36m"
-GREY = "\033[00;37m"
-WHITE = "\033[01;37m"
+DARK_GREEN = "\033[00;32m"
+GREEN = "\033[01;32m"
+YELLOW = "\033[01;33m"
+DARK_YELLOW = "\033[00;33m"
+DARK_BLUE = "\033[00;34m"
+BLUE = "\033[01;34m"
+PURPLE = "\033[00;35m"
+MAGENTA = "\033[01;35m"
+DARK_CYAN = "\033[00;36m"
+CYAN = "\033[01;36m"
+GREY = "\033[00;37m"
+WHITE = "\033[01;37m"
REV_RED = "\033[01;41m"
-def write_dot_file(basename, edge_list, vertices=None, label=None, destdir=None,
- reformat_labels=True, directed=False, debug=None, edge_colors=None,
- edge_labels=None, vertex_colors=None):
+def write_dot_file(basename, edge_list, vertices=None, label=None,
+ destdir=None, reformat_labels=True, directed=False,
+ debug=None, edge_colors=None, edge_labels=None,
+ vertex_colors=None):
from tempfile import NamedTemporaryFile
if label:
- basename += '_' + label.translate(None, ', ') #fix DN, guid labels
- f = NamedTemporaryFile(suffix='.dot', prefix=basename + '_', delete=False, dir=destdir)
+ basename += '_' + label.translate(None, ', ') # fix DN, guid labels
+ f = NamedTemporaryFile(suffix='.dot', prefix=basename + '_', delete=False,
+ dir=destdir)
if debug is not None:
debug(f.name)
graphname = ''.join(x for x in basename if x.isalnum())
@@ -72,10 +73,10 @@ def write_dot_file(basename, edge_list, vertices=None, label=None, destdir=None,
f.close()
-
class GraphError(Exception):
pass
+
def verify_graph_complete(edges, vertices, edge_vertices):
"""The graph is complete, which is to say there is an edge between
every pair of nodes."""
@@ -95,8 +96,9 @@ def verify_graph_connected(edges, vertices, edge_vertices):
if not edges:
if len(vertices) <= 1:
return
- raise GraphError("disconnected vertices were found:\nvertices: %s\n edges: %s" %
- (sorted(vertices), sorted(edges)))
+ raise GraphError("disconnected vertices were found:\n"
+ "vertices: %s\n edges: %s" %
+ (sorted(vertices), sorted(edges)))
remaining_edges = list(edges)
reached = set(remaining_edges.pop())
@@ -115,10 +117,26 @@ def verify_graph_connected(edges, vertices, edge_vertices):
for i in reversed(doomed):
del remaining_edges[i]
- if remaining_edges or reached != vertices:
- raise GraphError("graph is not connected:\nvertices: %s\n edges: %s" %
- (sorted(vertices), sorted(edges)))
+ if remaining_edges or reached != set(vertices):
+ raise GraphError("graph is not connected:\n vertices: %s\n edges: %s\n"
+ " reached: %s\n remaining edges: %s" %
+ (sorted(vertices), sorted(edges),
+ sorted(reached), sorted(remaining_edges)))
+
+
+def verify_graph_connected_under_edge_failures(edges, vertices, edge_vertices):
+ """The graph stays connected when any single edge is removed."""
+ for subset in itertools.combinations(edges, len(edges) - 1):
+ verify_graph_connected(subset, vertices, edge_vertices)
+
+def verify_graph_connected_under_vertex_failures(edges, vertices,
+ edge_vertices):
+ """The graph stays connected when any single vertex is removed."""
+ for v in vertices:
+ sub_vertices = [x for x in vertices if x is not v]
+ sub_edges = [x for x in edges if v not in x]
+ verify_graph_connected(sub_edges, sub_vertices, sub_vertices)
def verify_graph_forest(edges, vertices, edge_vertices):
@@ -134,7 +152,10 @@ def verify_graph_forest(edges, vertices, edge_vertices):
trees.remove(b)
break
else:
- raise GraphError("there is a loop in the graph")
+ raise GraphError("there is a loop in the graph\n"
+ " vertices %s\n edges %s\n"
+ " intersection %s" %
+ (vertices, edges, intersection))
else:
# no break in itertools.combinations loop means no
# further mergers, so we're done.
@@ -144,6 +165,7 @@ def verify_graph_forest(edges, vertices, edge_vertices):
# tells us that.
return
+
def verify_graph_multi_edge_forest(edges, vertices, edge_vertices):
"""This allows a forest with duplicate edges. That is if multiple
edges go between the same two vertices, they are treated as a
@@ -178,16 +200,18 @@ def verify_graph_forest_of_rings(edges, vertices, edge_vertices):
def verify_graph_no_lonely_vertices(edges, vertices, edge_vertices):
"""There are no vertices without edges."""
- lonely = vertices - edge_vertices
+ lonely = set(vertices) - set(edge_vertices)
if lonely:
- raise GraphError("some vertices are not connected:\n%s" % '\n'.join(sorted(lonely)))
+ raise GraphError("some vertices are not connected:\n%s" %
+ '\n'.join(sorted(lonely)))
def verify_graph_no_unknown_vertices(edges, vertices, edge_vertices):
"""The edge endpoints contain no vertices that are otherwise unknown."""
- unknown = edge_vertices - vertices
+ unknown = set(edge_vertices) - set(vertices)
if unknown:
- raise GraphError("some edge vertices are seemingly unknown:\n%s" % '\n'.join(sorted(unknown)))
+ raise GraphError("some edge vertices are seemingly unknown:\n%s" %
+ '\n'.join(sorted(unknown)))
def verify_graph_directed_double_ring(edges, vertices, edge_vertices):
@@ -197,70 +221,105 @@ def verify_graph_directed_double_ring(edges, vertices, edge_vertices):
touches every vertex and form a loop.
There might be other connections that *aren't* part of the ring.
+
+ Deciding this for sure is NP-complete (the Hamiltonian path
+ problem), but there are some easy failures that can be detected.
+ So far we check for:
+ - leaf nodes
+ - disjoint subgraphs
+ - robustness against edge and vertex failure
"""
- #XXX 1 and 2 vertex cases are special cases.
- if not edges:
+ # a zero or one node graph is OK with no edges.
+ # The two vertex case is special. Use
+ # verify_graph_directed_double_ring_or_small() to allow that.
+ if not edges and len(vertices) <= 1:
return
if len(edges) < 2 * len(vertices):
- raise GraphError("directed double ring requires at least twice as many edges as vertices")
-
- exits = {}
- for start, end in edges:
- s = exits.setdefault(start, [])
- s.append(end)
-
- try:
- #follow both paths at once -- they should be the same length
- #XXX there is probably a simpler way.
- forwards, backwards = exits[start]
- fprev, bprev = (start, start)
- f_path = [start]
- b_path = [start]
- for i in range(len(vertices)):
- a, b = exits[forwards]
- if a == fprev:
- fnext = b
- else:
- fnext = a
- f_path.append(forwards)
- fprev = forwards
- forwards = fnext
-
- a, b = exits[backwards]
- if a == bprev:
- bnext = b
- else:
- bnext = a
- b_path.append(backwards)
- bprev = backwards
- backwards = bnext
-
- except ValueError, e:
- raise GraphError("wrong number of exits '%s'" % e)
-
- f_set = set(f_path)
- b_set = set(b_path)
-
- if (f_path != list(reversed(b_path)) or
- len(f_path) != len(f_set) + 1 or
- len(f_set) != len(vertices)):
- raise GraphError("doesn't seem like a double ring to me!")
+ raise GraphError("directed double ring requires at least twice "
+ "as many edges as vertices")
+
+ # Reduce the problem space by looking only at bi-directional links.
+ half_duplex = set(edges)
+ duplex_links = set()
+ for edge in edges:
+ rev_edge = (edge[1], edge[0])
+ if edge in half_duplex and rev_edge in half_duplex:
+ duplex_links.add(edge)
+ half_duplex.remove(edge)
+ half_duplex.remove(rev_edge)
+
+ # the Hamiltonian cycle problem is NP-complete in general, but we
+ # can cheat a bit and prove a less strong result.
+ #
+ # We declutter the graph by replacing nodes with edges connecting
+ # their neighbours.
+ #
+ # A-B-C --> A-C
+ #
+ # -A-B-C- --> -A--C-
+ # `D_ `D'_
+ #
+ # In the end there should be a single 2 vertex graph.
+
+ edge_map = {}
+ for a, b in duplex_links:
+ edge_map.setdefault(a, set()).add(b)
+ edge_map.setdefault(b, set()).add(a)
+
+ # an easy to detect failure is a lonely leaf node
+ for vertex, neighbours in edge_map.items():
+ if len(neighbours) == 1:
+ raise GraphError("wanted double directed ring, found a leaf node"
+ "(%s)" % vertex)
+
+ for vertex in edge_map.keys():
+ nset = edge_map[vertex]
+ if not nset:
+ continue
+ for n in nset:
+ n_neighbours = edge_map[n]
+ n_neighbours.remove(vertex)
+ n_neighbours.update(x for x in nset if x != n)
+ del edge_map[vertex]
+
+ if len(edge_map) > 1:
+ raise GraphError("wanted double directed ring, but "
+ "this looks like a split graph\n"
+ "(%s can't reach each other)" %
+ ', '.join(edge_map.keys()))
+
+ verify_graph_connected_under_edge_failures(duplex_links, vertices,
+ edge_vertices)
+ verify_graph_connected_under_vertex_failures(duplex_links, vertices,
+ edge_vertices)
def verify_graph_directed_double_ring_or_small(edges, vertices, edge_vertices):
- if len(vertices) < 3:
+ """This performs the directed_double_ring test but makes special
+ concessions for small rings where the strict rules don't really
+ apply."""
+ if len(vertices) < 2:
return
- return verify_graph_directed_double_ring(edges, vertices, edge_vertices)
+ if len(vertices) == 2:
+ """With 2 nodes there should be a single link in each directions."""
+ if (len(edges) == 2 and
+ edges[0][0] == edges[1][1] and
+ edges[0][1] == edges[1][0]):
+ return
+ raise GraphError("A two vertex graph should have an edge each way.")
+ return verify_graph_directed_double_ring(edges, vertices, edge_vertices)
-def verify_graph(title, edges, vertices=None, directed=False, properties=(), fatal=True,
- debug=None):
+def verify_graph(title, edges, vertices=None, directed=False, properties=(),
+ fatal=True, debug=None):
errors = []
if debug is None:
- def debug(*args): pass
+ def debug(*args):
+ pass
- debug("%sStarting verify_graph for %s%s%s" % (PURPLE, MAGENTA, title, C_NORMAL))
+ debug("%sStarting verify_graph for %s%s%s" % (PURPLE, MAGENTA, title,
+ C_NORMAL))
properties = [x.replace(' ', '_') for x in properties]
@@ -291,35 +350,36 @@ def verify_graph(title, edges, vertices=None, directed=False, properties=(), fat
if errors:
if fatal:
- raise GraphError("The '%s' graph lacks the following properties:\n%s" %
- (title, '\n'.join('%s: %s' % x for x in errors)))
+ raise GraphError("The '%s' graph lacks the following properties:"
+ "\n%s" %
+ (title, '\n'.join('%s: %s' % x for x in errors)))
debug(("%s%s%s FAILED:" % (MAGENTA, title, RED)))
for p, e in errors:
- debug(" %18s: %s%s%s" %(p, DARK_YELLOW, e, RED))
+ debug(" %18s: %s%s%s" % (p, DARK_YELLOW, e, RED))
debug(C_NORMAL)
-
def verify_and_dot(basename, edges, vertices=None, label=None, destdir=None,
- reformat_labels=True, directed=False, properties=(), fatal=True,
- debug=None, verify=True, dot_files=False, edge_colors=None,
- edge_labels=None, vertex_colors=None):
+ reformat_labels=True, directed=False, properties=(),
+ fatal=True, debug=None, verify=True, dot_files=False,
+ edge_colors=None, edge_labels=None, vertex_colors=None):
title = '%s %s' % (basename, label or '')
if verify:
- verify_graph(title, edges, vertices, properties=properties, fatal=fatal,
- debug=debug)
+ verify_graph(title, edges, vertices, properties=properties,
+ fatal=fatal, debug=debug)
if dot_files:
- write_dot_file(basename, edges, vertices=vertices, label=label, destdir=destdir,
- reformat_labels=reformat_labels, directed=directed, debug=debug,
- edge_colors=edge_colors, edge_labels=edge_labels,
- vertex_colors=vertex_colors)
+ write_dot_file(basename, edges, vertices=vertices, label=label,
+ destdir=destdir, reformat_labels=reformat_labels,
+ directed=directed, debug=debug, edge_colors=edge_colors,
+ edge_labels=edge_labels, vertex_colors=vertex_colors)
+
def list_verify_tests():
for k, v in sorted(globals().items()):
if k.startswith('verify_graph_'):
print k.replace('verify_graph_', '')
if v.__doc__:
- print ' %s%s%s' %(GREY, v.__doc__, C_NORMAL)
+ print ' %s%s%s' % (GREY, v.__doc__.rstrip(), C_NORMAL)
else:
print
diff --git a/python/samba/kcc_utils.py b/python/samba/kcc_utils.py
index 210bcdd..f45a972 100644
--- a/python/samba/kcc_utils.py
+++ b/python/samba/kcc_utils.py
@@ -22,9 +22,6 @@
import ldb
import uuid
-import time
-import sys
-import itertools
from samba import dsdb, unix2nttime
from samba.dcerpc import (
@@ -35,14 +32,17 @@ from samba.dcerpc import (
from samba.common import dsdb_Dn
from samba.ndr import (ndr_unpack, ndr_pack)
+
class KCCError(Exception):
pass
+
class NCType(object):
(unknown, schema, domain, config, application) = range(0, 5)
# map the NCType enum to strings for debugging
-nctype_lut = {v:k for k, v in NCType.__dict__.items() if k[:2] != '__'}
+nctype_lut = {v: k for k, v in NCType.__dict__.items() if k[:2] != '__'}
+
class NamingContext(object):
"""Base class for a naming context.
@@ -65,19 +65,20 @@ class NamingContext(object):
'''Debug dump string output of class'''
text = "%s:" % (self.__class__.__name__,)
text = text + "\n\tnc_dnstr=%s" % self.nc_dnstr
- text = text + "\n\tnc_guid=%s" % str(self.nc_guid)
+ text = text + "\n\tnc_guid=%s" % str(self.nc_guid)
if self.nc_sid is None:
text = text + "\n\tnc_sid=<absent>"
else:
text = text + "\n\tnc_sid=<present>"
- text = text + "\n\tnc_type=%s (%s)" % (nctype_lut[self.nc_type], self.nc_type)
+ text = text + "\n\tnc_type=%s (%s)" % (nctype_lut[self.nc_type],
+ self.nc_type)
return text
def load_nc(self, samdb):
- attrs = [ "objectGUID",
- "objectSid" ]
+ attrs = ["objectGUID",
+ "objectSid"]
try:
res = samdb.search(base=self.nc_dnstr,
scope=ldb.SCOPE_BASE, attrs=attrs)
@@ -185,7 +186,7 @@ class NCReplica(NamingContext):
"""
self.rep_dsa_dnstr = dsa_dnstr
self.rep_dsa_guid = dsa_guid
- self.rep_default = False # replica for DSA's default domain
+ self.rep_default = False # replica for DSA's default domain
self.rep_partial = False
self.rep_ro = False
self.rep_instantiated_flags = 0
@@ -208,12 +209,12 @@ class NCReplica(NamingContext):
def __str__(self):
'''Debug dump string output of class'''
text = "%s:" % self.__class__.__name__
- text = text + "\n\tdsa_dnstr=%s" % self.rep_dsa_dnstr
- text = text + "\n\tdsa_guid=%s" % str(self.rep_dsa_guid)
- text = text + "\n\tdefault=%s" % self.rep_default
- text = text + "\n\tro=%s" % self.rep_ro
- text = text + "\n\tpartial=%s" % self.rep_partial
- text = text + "\n\tpresent=%s" % self.is_present()
+ text = text + "\n\tdsa_dnstr=%s" % self.rep_dsa_dnstr
+ text = text + "\n\tdsa_guid=%s" % self.rep_dsa_guid
+ text = text + "\n\tdefault=%s" % self.rep_default
+ text = text + "\n\tro=%s" % self.rep_ro
+ text = text + "\n\tpartial=%s" % self.rep_partial
+ text = text + "\n\tpresent=%s" % self.is_present()
text = text + "\n\tfsmo_role_owner=%s" % self.rep_fsmo_role_owner
for rep in self.rep_repsFrom:
@@ -310,7 +311,7 @@ class NCReplica(NamingContext):
"""
try:
res = samdb.search(base=self.nc_dnstr, scope=ldb.SCOPE_BASE,
- attrs=[ "repsFrom" ])
+ attrs=["repsFrom"])
except ldb.LdbError, (enum, estr):
raise Exception("Unable to find NC for (%s) - (%s)" %
@@ -390,13 +391,15 @@ class NCReplica(NamingContext):
def load_replUpToDateVector(self, samdb):
"""Given an NC replica which has been discovered thru the nTDSDSA
- database object, load the replUpToDateVector attribute for the local replica.
- held by my dsa. The replUpToDateVector attribute is not replicated so this
- attribute is relative only to the local DSA that the samdb exists on
+ database object, load the replUpToDateVector attribute for the
+ local replica. held by my dsa. The replUpToDateVector
+ attribute is not replicated so this attribute is relative only
+ to the local DSA that the samdb exists on
+
"""
try:
res = samdb.search(base=self.nc_dnstr, scope=ldb.SCOPE_BASE,
- attrs=[ "replUpToDateVector" ])
+ attrs=["replUpToDateVector"])
except ldb.LdbError, (enum, estr):
raise Exception("Unable to find NC for (%s) - (%s)" %
@@ -407,13 +410,14 @@ class NCReplica(NamingContext):
# Possibly no replUpToDateVector if this is a singleton DC
if "replUpToDateVector" in msg:
value = msg["replUpToDateVector"][0]
- replUpToDateVectorBlob = ndr_unpack(drsblobs.replUpToDateVectorBlob, value)
- if replUpToDateVectorBlob.version != 2:
+ blob = ndr_unpack(drsblobs.replUpToDateVectorBlob,
+ value)
+ if blob.version != 2:
# Samba only generates version 2, and this runs locally
raise AttributeError("Unexpected replUpToDateVector version %d"
- % replUpToDateVectorBlob.version)
+ % blob.version)
- self.rep_replUpToDateVector_cursors = replUpToDateVectorBlob.ctr.cursors
+ self.rep_replUpToDateVector_cursors = blob.ctr.cursors
else:
self.rep_replUpToDateVector_cursors = []
--
Samba Shared Repository
More information about the samba-cvs
mailing list