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.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> Autobuild-User(master): Andrew Bartlett <abart...@samba.org> Autobuild-Date(master): Fri May 29 13:55:54 CEST 2015 on sn-devel-104 commit b08f4541962f70121c32f17ee1b5d59ef86baa7e Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 2f3ce1753ae6b1af9986c2ed3b3d7fe8272700c2 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Tue Apr 14 14:31:05 2015 +1200 KCC: more debugging changes Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit c3dc87eac021fdb6c942a512429ed6ca973e32b0 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 87c68e0bc9e1b41755bb549d17ee1d9ed43ed980 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 898d8b39876373002466b5e2b7efd58dbcc192cd Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 08e41b42af6a5e4f3c1252e55cc78aa5994ca083 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Thu Apr 9 15:00:55 2015 +1200 KCC: more pep8 for kcc_utils Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit edacc0314f6a76735304aded58f7530d6801621e Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 4e781857e3d682e0012ff340ad1e9b199c723b67 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit cb8b99e335101c5454a1e448275993aa18f77e10 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 75eedf85b1516f0b2370d23d6ff1058a70b093b0 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 326c503925eb93e46fd1def01a465e5f6dbe3d66 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Thu Apr 2 15:50:40 2015 +1300 KCC: RODCs are their own bridgeheads Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 722e6fa900736f686ed60126a92aa56b7ef51400 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit b9f75c8f1a1b28f7a6ae8ab36e970a0e120f1cb6 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit f7b088efa522d75365b64baf17d1d4f8e1a26e25 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit fa3c552d3a4ef0f2214af6f5fbbeb618ce5350bd Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 7a6d0b637a9547aa0b7ae3d794338140fa6322f5 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 4c5761c057be345d64e6d4e14924f9cad4d51f62 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit d0f9f32d0a912972b5b23a4c9015a706d539b638 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 7ac59745b399740b675d4cf9e635c709c7ac67ae Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 8c8acd22a6335ace24998293476dba2c0427d04f Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 91d87cae3603a3b559708ac884d2e821448a4dbc Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 04c678fd0858a21241b81746184e110791799137 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 6200432d85a212b81687eefc53e96129a4388a07 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit b75ec6d7fa645ef9e648842f70c1c26446219b32 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 4ffd37df5e4a080af4aa2ab409b26cc0bded9ec4 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 4770bc0f62e99614220f95a964dcfe4e5d0fdc9c Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 15dfb58424d65d88e32fdc4ca778764ac6a5817d Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed Apr 1 14:04:16 2015 +1300 KCC: deduplicate connection schedule creation Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 768d79c7037aa5c959e5e93644fbaa0b4b17db68 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit e33fe2bf2435763382a2251d3ddb5ddcdb0aabbb Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit f02340979141ebd7659fa9a19ccb9f0a5c592463 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 5546f846e26f9110a04210c96a79918fb1b0865f Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit b4e4f8ae3b7e3963a5fe904951ba6024a90c6221 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Fri Mar 27 18:10:34 2015 +1300 KCC: remove another needless loop variable Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 39da46e72c20a089efe2a2c66bca7342b87bec13 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit ceb6ab99b5b352ebcdf648581ec92ae34e236ba5 Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 13388e3fced000de1522ce044bad9d8b09f35a5d Author: Douglas Bagnall <douglas.bagn...@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.bagn...@catalyst.net.nz> Reviewed-by: Garming Sam <garm...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@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