ClusterShell.Topology

1 #!/usr/bin/env python 2 # 3 # Copyright (C) 2010-2016 CEA/DAM 4 # Copyright (C) 2010-2011 Henri Doreau <henri.doreau@cea.fr> 5 # Copyright (C) 2015-2016 Stephane Thiell <sthiell@stanford.edu> 6 # 7 # This file is part of ClusterShell. 8 # 9 # ClusterShell is free software; you can redistribute it and/or 10 # modify it under the terms of the GNU Lesser General Public 11 # License as published by the Free Software Foundation; either 12 # version 2.1 of the License, or (at your option) any later version. 13 # 14 # ClusterShell is distributed in the hope that it will be useful, 15 # but WITHOUT ANY WARRANTY; without even the implied warranty of 16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 # Lesser General Public License for more details. 18 # 19 # You should have received a copy of the GNU Lesser General Public 20 # License along with ClusterShell; if not, write to the Free Software 21 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 22 23 """ 24 ClusterShell topology module 25 26 This module contains the network topology parser and its related 27 classes. These classes are used to build a topology tree of nodegroups 28 according to the configuration file. 29 30 This file must be written using the following syntax: 31 32 # for now only [routes] tree is taken in account: 33 [routes] 34 admin: first_level_gateways[0-10] 35 first_level_gateways[0-10]: second_level_gateways[0-100] 36 second_level_gateways[0-100]: nodes[0-2000] 37 ... 38 """ 39 40 import ConfigParser 41 42 from ClusterShell.NodeSet import NodeSet 43 44

45 -class TopologyError(Exception):

46 """topology parser error to report invalid configurations or parsing 47 errors 48 """

49

50 -class TopologyNodeGroup(object):

51 """Base element for in-memory representation of the propagation tree. 52 Contains a nodeset, with parent-children relationships with other 53 instances. 54 """

55 - def __init__(self, nodeset=None):

56 """initialize a new TopologyNodeGroup instance.""" 57 # Base nodeset 58 self.nodeset = nodeset 59 # Parent TopologyNodeGroup (TNG) instance 60 self.parent = None 61 # List of children TNG instances 62 self._children = [] 63 self._children_len = 0 64 # provided for convenience 65 self._children_ns = None

66

67 - def printable_subtree(self, prefix=''):

68 """recursive method that returns a printable version the subtree from 69 the current node with a nice presentation 70 """ 71 res = '' 72 # For now, it is ok to use a recursive method here as we consider that 73 # tree depth is relatively small. 74 if self.parent is None: 75 # root 76 res = '%s\n' % str(self.nodeset) 77 elif self.parent.parent is None: 78 # first level 79 if not self._is_last(): 80 res = '|- %s\n' % str(self.nodeset) 81 else: 82 res = '`- %s\n' % str(self.nodeset) 83 else: 84 # deepest levels... 85 if not self.parent._is_last(): 86 prefix += '| ' 87 else: 88 # fix last line 89 prefix += ' ' 90 if not self._is_last(): 91 res = '%s|- %s\n' % (prefix, str(self.nodeset)) 92 else: 93 res = '%s`- %s\n' % (prefix, str(self.nodeset)) 94 # perform recursive calls to print out every node 95 for child in self._children: 96 res += child.printable_subtree(prefix) 97 return res

98

99 - def add_child(self, child):

100 """add a child to the children list and define the current instance as 101 its parent 102 """ 103 assert isinstance(child, TopologyNodeGroup) 104 105 if child in self._children: 106 return 107 child.parent = self 108 self._children.append(child) 109 if self._children_ns is None: 110 self._children_ns = NodeSet() 111 self._children_ns.add(child.nodeset)

112

113 - def clear_child(self, child, strict=False):

114 """remove a child""" 115 try: 116 self._children.remove(child) 117 self._children_ns.difference_update(child.nodeset) 118 if len(self._children_ns) == 0: 119 self._children_ns = None 120 except ValueError: 121 if strict: 122 raise

123

124 - def clear_children(self):

125 """delete all children""" 126 self._children = [] 127 self._children_ns = None

128

129 - def children(self):

130 """get the children list""" 131 return self._children

132

133 - def children_ns(self):

134 """return the children as a nodeset""" 135 return self._children_ns

136

137 - def children_len(self):

138 """returns the number of children as the sum of the size of the 139 children's nodeset 140 """ 141 if self._children_ns is None: 142 return 0 143 else: 144 return len(self._children_ns)

145

146 - def _is_last(self):

147 """used to display the subtree: we won't prefix the line the same way if 148 the current instance is the last child of the children list of its 149 parent. 150 """ 151 return self.parent._children[-1::][0] == self

152

153 - def __str__(self):

154 """printable representation of the nodegroup""" 155 return '<TopologyNodeGroup (%s)>' % str(self.nodeset)

156

157 -class TopologyTree(object):

158 """represent a simplified network topology as a tree of machines to use to 159 connect to other ones 160 """

161 - class TreeIterator(object):

162 """efficient tool for tree-traversal"""

163 - def __init__(self, tree):

164 """we do simply manage a stack with the remaining nodes""" 165 self._stack = [tree.root]

166

167 - def next(self):

168 """return the next node in the stack or raise a StopIteration 169 exception if the stack is empty 170 """ 171 if len(self._stack) > 0 and self._stack[0] is not None: 172 node = self._stack.pop() 173 self._stack += node.children() 174 return node 175 else: 176 raise StopIteration()

177

178 - def __init__(self):

179 """initialize a new TopologyTree instance.""" 180 self.root = None 181 self.groups = []

182

183 - def load(self, rootnode):

184 """load topology tree""" 185 self.root = rootnode 186 187 stack = [rootnode] 188 while len(stack) > 0: 189 curr = stack.pop() 190 self.groups.append(curr) 191 if curr.children_len() > 0: 192 stack += curr.children()

193

194 - def __iter__(self):

195 """provide an iterator on the tree's elements""" 196 return TopologyTree.TreeIterator(self)

197

198 - def __str__(self):

199 """printable representation of the tree""" 200 if self.root is None: 201 return '<TopologyTree instance (empty)>' 202 return self.root.printable_subtree()

203

204 - def find_nodegroup(self, node):

205 """Find TopologyNodeGroup from given node (helper to find new root)""" 206 for group in self.groups: 207 if node in group.nodeset: 208 return group 209 raise TopologyError('TopologyNodeGroup not found for node %s' % node)

210

211 - def inner_node_count(self):

212 """helper to get inner node count (root and gateway nodes)""" 213 return sum(len(group.nodeset) for group in self.groups 214 if group.children_len() > 0)

215

216 - def leaf_node_count(self):

217 """helper to get leaf node count""" 218 return sum(len(group.nodeset) for group in self.groups 219 if group.children_len() == 0)

220

221 -class TopologyRoute(object):

222 """A single route between two nodesets"""

223 - def __init__(self, src_ns, dst_ns):

224 """both src_ns and dst_ns are expected to be non-empty NodeSet 225 instances 226 """ 227 self.src = src_ns 228 self.dst = dst_ns 229 if len(src_ns & dst_ns) != 0: 230 raise TopologyError( 231 'Source and destination nodesets overlap')

232

233 - def dest(self, nodeset=None):

234 """get the route's destination. The optionnal argument serves for 235 convenience and provides a way to use the method for a subset of the 236 whole source nodeset 237 """ 238 if nodeset is None or nodeset in self.src: 239 return self.dst 240 else: 241 return None

242

243 - def __str__(self):

244 """printable representation""" 245 return '%s -> %s' % (str(self.src), str(self.dst))

246

247 -class TopologyRoutingTable(object):

248 """This class provides a convenient way to store and manage topology 249 routes 250 """

251 - def __init__(self):

252 """Initialize a new TopologyRoutingTable instance.""" 253 self._routes = [] 254 self.aggregated_src = NodeSet() 255 self.aggregated_dst = NodeSet()

256

257 - def add_route(self, route):

258 """add a new route to the table. The route argument is expected to be a 259 TopologyRoute instance 260 """ 261 if self._introduce_circular_reference(route): 262 raise TopologyError( 263 'Loop detected! Cannot add route %s' % str(route)) 264 if self._introduce_convergent_paths(route): 265 raise TopologyError( 266 'Convergent path detected! Cannot add route %s' % str(route)) 267 268 self._routes.append(route) 269 270 self.aggregated_src.add(route.src) 271 self.aggregated_dst.add(route.dst)

272

273 - def connected(self, src_ns):

274 """find out and return the aggregation of directly connected children 275 from src_ns. 276 Argument src_ns is expected to be a NodeSet instance. Result is returned 277 as a NodeSet instance 278 """ 279 next_hop = NodeSet.fromlist([dst for dst in \ 280 [route.dest(src_ns) for route in self._routes] if dst is not None]) 281 if len(next_hop) == 0: 282 return None 283 return next_hop

284

285 - def __str__(self):

286 """printable representation""" 287 return '\n'.join([str(route) for route in self._routes])

288

289 - def __iter__(self):

290 """return an iterator over the list of rotues""" 291 return iter(self._routes)

292

293 - def _introduce_circular_reference(self, route):

294 """check whether the last added route adds a topology loop or not""" 295 current_ns = route.dst 296 # iterate over the destinations until we find None or we come back on 297 # the src 298 while True: 299 _dest = self.connected(current_ns) 300 if _dest is None or len(_dest) == 0: 301 return False 302 if len(_dest & route.src) != 0: 303 return True 304 current_ns = _dest

305

306 - def _introduce_convergent_paths(self, route):

307 """check for undesired convergent paths""" 308 for known_route in self._routes: 309 # source cannot be a superset of an already known destination 310 if route.src > known_route.dst: 311 return True 312 # same thing... 313 if route.dst < known_route.src: 314 return True 315 # two different nodegroups cannot point to the same one 316 if len(route.dst & known_route.dst) != 0 \ 317 and route.src != known_route.src: 318 return True 319 return False

320

321 -class TopologyGraph(object):

322 """represent a complete network topology by storing every "can reach" 323 relations between nodes. 324 """

325 - def __init__(self):

326 """initialize a new TopologyGraph instance.""" 327 self._routing = TopologyRoutingTable() 328 self._nodegroups = {} 329 self._root = ''

330

331 - def add_route(self, src_ns, dst_ns):

332 """add a new route from src nodeset to dst nodeset. The destination 333 nodeset must not overlap with already known destination nodesets 334 (otherwise a TopologyError is raised) 335 """ 336 assert isinstance(src_ns, NodeSet) 337 assert isinstance(dst_ns, NodeSet) 338 339 #print 'adding %s -> %s' % (str(src_ns), str(dst_ns)) 340 self._routing.add_route(TopologyRoute(src_ns, dst_ns))

341

342 - def dest(self, from_nodeset):

343 """return the aggregation of the destinations for a given nodeset""" 344 return self._routing.connected(from_nodeset)

345

346 - def to_tree(self, root):

347 """convert the routing table to a topology tree of nodegroups""" 348 # convert the routing table into a table of linked TopologyNodeGroup's 349 self._routes_to_tng() 350 # ensure this is a valid pseudo-tree 351 self._validate(root) 352 tree = TopologyTree() 353 tree.load(self._nodegroups[self._root]) 354 return tree

355

356 - def __str__(self):

357 """printable representation of the graph""" 358 res = '<TopologyGraph>\n' 359 res += '\n'.join(['%s: %s' % (str(k), str(v)) for k, v in \ 360 self._nodegroups.iteritems()]) 361 return res

362

363 - def _routes_to_tng(self):

364 """convert the routing table into a graph of TopologyNodeGroup 365 instances. Loops are not very expensive here as the number of routes 366 will always be much lower than the number of nodes. 367 """ 368 # instanciate nodegroups as biggest groups of nodes sharing both parent 369 # and destination 370 aggregated_src = self._routing.aggregated_src 371 for route in self._routing: 372 self._nodegroups[str(route.src)] = TopologyNodeGroup(route.src) 373 # create a nodegroup for the destination if it is a leaf group. 374 # Otherwise, it will be created as src for another route 375 leaf = route.dst - aggregated_src 376 if len(leaf) > 0: 377 self._nodegroups[str(leaf)] = TopologyNodeGroup(leaf) 378 379 # add the parent <--> children relationships 380 for group in self._nodegroups.itervalues(): 381 dst_ns = self._routing.connected(group.nodeset) 382 if dst_ns is not None: 383 for child in self._nodegroups.itervalues(): 384 if child.nodeset in dst_ns: 385 group.add_child(child)

386

387 - def _validate(self, root):

388 """ensure that the graph is valid for conversion to tree""" 389 if len(self._nodegroups) == 0: 390 raise TopologyError("No route found in topology definition!") 391 392 # ensure that every node is reachable 393 src_all = self._routing.aggregated_src 394 dst_all = self._routing.aggregated_dst 395 396 res = [(k, v) for k, v in self._nodegroups.items() if root in v.nodeset] 397 if len(res) > 0: 398 kgroup, group = res[0] 399 del self._nodegroups[kgroup] 400 self._nodegroups[root] = group 401 else: 402 raise TopologyError('"%s" is not a valid root node!' % root) 403 404 self._root = root

405

406 -class TopologyParser(ConfigParser.ConfigParser):

407 """This class offers a way to interpret network topologies supplied under 408 the form : 409 410 # Comment 411 <these machines> : <can reach these ones> 412 """

413 - def __init__(self, filename=None):

414 """instance wide variables initialization""" 415 ConfigParser.ConfigParser.__init__(self) 416 self.optionxform = str # case sensitive parser 417 418 self._topology = {} 419 self.graph = None 420 self._tree = None 421 422 if filename: 423 self.load(filename)

424

425 - def load(self, filename):

426 """read a given topology configuration file and store the results in 427 self._routes. Then build a propagation tree. 428 """ 429 try: 430 self.read(filename) 431 if self.has_section("routes"): 432 self._topology = self.items("routes") 433 else: 434 # compat routes section [deprecated since v1.7] 435 self._topology = self.items("Main") 436 except ConfigParser.Error: 437 raise TopologyError( 438 'Invalid configuration file: %s' % filename) 439 self._build_graph()

440

441 - def _build_graph(self):

442 """build a network topology graph according to the information we got 443 from the configuration file. 444 """ 445 self.graph = TopologyGraph() 446 for src, dst in self._topology: 447 self.graph.add_route(NodeSet(src), NodeSet(dst))

448

449 - def tree(self, root, force_rebuild=False):

450 """Return a previously generated propagation tree or build it if 451 required. As rebuilding tree can be quite expensive, once built, 452 the propagation tree is cached. you can force a re-generation 453 using the optionnal `force_rebuild' parameter. 454 """ 455 if self._tree is None or force_rebuild: 456 self._tree = self.graph.to_tree(root) 457 return self._tree

458

Source Code for Module ClusterShell.Topology