source: fedd/compose.py @ 2c51061

axis_examplecompt_changesinfo-opsversion-3.01version-3.02
Last change on this file since 2c51061 was 2c51061, checked in by Ted Faber <faber@…>, 14 years ago

Make it easier to follow compositions by using the non-numeric stems of user specified node names as the basis for names in the composed experiment.

Also added an option to output textbed commands in the ns2 output.

  • Property mode set to 100644
File size: 22.4 KB
Line 
1#!/usr/local/bin/python
2
3import sys
4import re
5import os
6import random
7import copy
8
9import xml.parsers.expat
10
11from optparse import OptionParser, OptionValueError
12from federation.remote_service import service_caller
13from federation.service_error import service_error
14from federation import topdl
15
16class constraint:
17    """
18    This is mainly a struct to hold constraint fields and convert to XML output
19    """
20    def __init__(self, name=None, required=False, accepts=None, provides=None,
21            topology=None, match=None):
22        self.name = name
23        self.required = required
24        self.accepts = accepts or []
25        self.provides = provides or []
26        self.topology = None
27        self.match = match
28
29    def __str__(self):
30        return "%s:%s:%s:%s" % (self.name, self.required,
31                ",".join(self.provides), ",".join(self.accepts))
32
33    def to_xml(self):
34        rv = "<constraint>"
35        rv += "<name>%s</name>" % self.name
36        rv += "<required>%s</required>" % self.required
37        for p in self.provides:
38            rv += "<provides>%s</provides>" % p
39        for a in self.accepts:
40            rv += "<accepts>%s</accepts>" % a
41        rv+= "</constraint>"
42        return rv
43
44def constraints_from_xml(string=None, file=None, filename=None, 
45        top="constraints"):
46    """
47    Pull constraints from an xml file.  Only constraints in the top element are
48    recognized.  A constraint consists of a constraint element with one name,
49    one required, and multiple accepts nd provides elements.  Each contains a
50    string.  A list of constraints is returned.
51    """
52    class parser:
53        """
54        A little class to encapsulate some state used to parse the constraints.
55        The methods are all bound to the analogous handlers in an XML parser.
56        It collects the constraints in self.constraint.
57        """
58        def __init__(self, top):
59            self.top = top
60            self.constraints = [ ]
61            self.chars = None
62            self.current = None
63            self.in_top = False
64       
65        def start_element(self, name, attrs):
66            # Clear any collected strings (from inside elements)
67            self.chars = None
68            self.key = str(name)
69           
70            # See if we've entered the containing context
71            if name == self.top:
72                self.in_top = True
73
74            # Entering a constraint, create the object which also acts as a
75            # flag to indicate we're collecting constraint data.
76            if self.in_top:
77                if name == 'constraint':
78                    self.current = constraint()
79
80        def end_element(self, name):
81            if self.current:
82                # In a constraint and leaving an element.  Clean up any string
83                # we've collected and process elements we know.
84                if self.chars is not None:
85                    self.chars = self.chars.strip()
86
87                if name == 'required':
88                    if self.chars is None:
89                        self.current.required = False
90                    else:
91                        self.current.required = (self.chars.lower() == 'true')
92                elif name == 'name':
93                    self.current.name = self.chars
94                elif name == 'accepts':
95                    self.current.accepts.append(self.chars)
96                elif name == 'provides':
97                    self.current.provides.append(self.chars)
98                elif name == 'constraint':
99                    # Leaving this constraint.  Record it and clear the flag
100                    self.constraints.append(self.current)
101                    self.current = None
102                else:
103                    print >>sys.stderr, \
104                            "Unexpected element in constraint: %s" % name
105            elif name == self.top:
106                # We've left the containing context
107                self.in_top = False
108
109
110        def char_data(self, data):
111            # Collect strings if we're in the overall context
112            if self.in_top:
113                if self.chars is None: self.chars = data
114                else: self.chars += data
115
116    # Beginning of constraints_from_xml.  Connect up the parser and call it
117    # properly for the kind of input supplied.
118    p = parser(top=top)
119    xp = xml.parsers.expat.ParserCreate()
120
121    xp.StartElementHandler = p.start_element
122    xp.EndElementHandler = p.end_element
123    xp.CharacterDataHandler = p.char_data
124
125    if len([x for x in (string, filename, file) if x is not None])!= 1:
126        raise RuntimeError("Exactly one one of file, filename and string " + \
127                "must be set")
128    elif filename:
129        f = open(filename, "r")
130        xp.ParseFile(f)
131        f.close()
132    elif file:
133        xp.ParseFile(file)
134    elif string:
135        xp.Parse(string, isfinal=True)
136    else:
137        return []
138
139    return p.constraints
140
141
142class ComposeOptionParser(OptionParser):
143    """
144    This class encapsulates the options to this script in one place.  It also
145    holds the callback for the multifile choice.
146    """
147    def __init__(self):
148        OptionParser.__init__(self)
149        self.add_option('--url', dest='url', default="http://localhost:13235",
150                help='url of ns2 to topdl service')
151        self.add_option('--certfile', dest='cert', default=None,
152                help='Certificate to use as identity')
153        self.add_option('--seed', dest='seed', type='int', default=None,
154                help='Random number seed')
155        self.add_option('--multifile', dest='files', default=[], type='string', 
156                action='callback', callback=self.multi_callback, 
157                help="Include file multiple times")
158        self.add_option('--output', dest='outfile', default=None,
159                help='Output file name')
160        self.add_option("--format", dest="format", type="choice", 
161                choices=("xml", "topdl", "tcl", "ns"),
162                help="Output file format")
163        self.add_option('--add_testbeds', dest='add_testbeds', default=False,
164                action='store_true',
165                help='add testbed attributes to each component')
166        self.add_option('--output_testbeds', dest='output_testbeds', 
167                default=False, action='store_true',
168                help='Output tb-set-node-testbed commands to ns2')
169        self.add_option('--lax', dest='lax', default=False,
170                action='store_true',
171                help='allow solutions where unrequired constraints fail')
172        self.add_option('--same_node', dest='same_node', action='store_true',
173                default=False, 
174                help='Allow loops to the same node to be created.')
175        self.add_option('--same_topology', dest='same_topo',
176                action='store_true', default=False, 
177                help='Allow links within the same topology to be created.')
178        self.add_option('--same_pair', dest='multi_pair',
179                action='store_true', default=False, 
180                help='Allow multiple links between the same nodes " + \
181                        "to be created.')
182
183    @staticmethod
184    def multi_callback(option, opt_str, value, parser):
185        """
186        Parse a --multifile command line option.  The parameter is of the form
187        filename,count.  This splits the argument at the rightmost comma and
188        inserts the filename, count tuple into the "files" option.  It handles
189        a couple error cases, too.
190        """
191        idx = value.rfind(',')
192        if idx != -1:
193            try:
194                parser.values.files.append((value[0:idx], int(value[idx+1:])))
195            except ValueError, e:
196                raise OptionValueError(
197                        "Can't convert %s to int in multifile (%s)" % \
198                                (value[idx+1:], value))
199        else:
200            raise OptionValueError(
201                    "Bad format (need a comma) for multifile: %s" % value)
202
203def warn(msg):
204    """
205    Exactly what you think.  Print a message to stderr
206    """
207    print >>sys.stderr, msg
208
209
210def make_new_name(names, prefix="name"):
211    """
212    Generate an identifier not present in names by appending an integer to
213    prefix.  The new name is inserted into names and returned.
214    """
215    i = 0
216    n = "%s%d" % (prefix,i)
217    while n in names:
218        i += 1
219        n = "%s%d" % (prefix,i)
220    names.add(n)
221    return n
222
223def base_name(n):
224    """
225    Extract a base name of the node to use for constructing a non-colliding
226    name.  This makes the composed topologies a little more readable.  It's a
227    single regexp, but the function name is more meaningful.
228    """
229    return re.sub('\d+$', '',n)
230
231
232
233def localize_names(top, names, marks):
234    """
235    Take a topology and rename any substrates or elements that share a name
236    with an existing computer or substrate.  Keep the original name as a
237    localized_name attribute.  In addition, remap any constraints or interfaces
238    that point to the old name over to the new one.  Constraints are found in
239    the marks dict, indexed by node name.  Those constraints name attributes
240    have already been converted to triples (node name, interface name,
241    topology) so only the node name needs to be changed.
242    """
243    sub_map = { }
244    for s in top.substrates:
245        s.set_attribute('localized_name', s.name)
246        if s.name in names:
247            sub_map[s.name] = n = make_new_name(names, base_name(s.name))
248            s.name = n
249        else:
250            names.add(s.name)
251
252    for e in [ e for e in top.elements if isinstance(e, topdl.Computer)]:
253        e.set_attribute('localized_name', e.name)
254        if e.name in names:
255            nn= make_new_name(names, base_name(e.name))
256            for c in marks.get(e.name, []):
257                c.name = nn
258            e.name = nn
259        else:
260            names.add(e.name)
261
262        # Interface mapping.  The list comprehension creates a list of
263        # substrate names where each element in the list is replaced by the
264        # entry in sub_map indexed by it if present and left alone otherwise.
265        for i in e.interface:
266            i.substrate = [ sub_map.get(ii, ii) for ii in i.substrate ]
267
268def meet_constraints(candidates, provides, accepts, 
269        same_node=False, same_topo=False, multi_pair=False):
270    """
271    Try to meet all the constraints in candidates using the information in the
272    provides and accepts dicts (which index constraints that provide or accept
273    the given attribute). A constraint is met if it can be matched with another
274    constraint that provides an attribute that the first constraint accepts.
275    Only one match per pair is allowed, and we always prefer matching a
276    required constraint to an unreqired one.  If all the candidates can be
277    matches, return True and return False otherwise.
278    """
279    got_all = True
280    node_match = { }
281    for c in candidates:
282        if not c.match:
283            rmatch = None   # Match to a required constraint
284            umatch = None   # Match to an unrequired constraint
285            for a in c.accepts:
286                for can in provides.get(a,[]):
287                    # A constraint cannot satisfy itself nor can it match
288                    # multiple times.
289                    if can != c and not can.match:
290                        # Unless same_node is true disallow nodes satisfying
291                        # their own constraints.
292                        if not same_node and can.name == c.name:
293                            continue
294                        # Unless same_topo is true, exclude nodes in the same
295                        # topology.
296                        if not same_topo and can.topology == c.topology:
297                            continue
298                        # Don't allow multiple matches between the same nodes
299                        if not multi_pair and c.name in node_match and \
300                                can.name in node_match[c.name]:
301                            continue
302                        # Now check that can also accepts c
303                        for ca in can.accepts:
304                            if ca in c.provides:
305                                if can.required: rmatch = can
306                                else: umatch = can
307                                break
308                       
309                        # Within providers, prefer matches against required
310                        # composition points.
311                        if rmatch:
312                            break
313                # Within acceptance categories, prefer matches against required
314                # composition points
315                if rmatch:
316                    break
317
318            # Move the better match over to the match variable
319            if rmatch: match = rmatch
320            elif umatch: match = umatch
321            else: match = None
322
323            # Done checking all possible matches.  Record the match or note an
324            # unmatched candidate.
325            if match:
326                match.match = c
327                c.match = match
328                # Note the match of the nodes
329                for a, b in ((c.name, match.name), (match.name, c.name)):
330                    if a in node_match: node_match[a].append(b)
331                    else: node_match[a] = [ b]
332            else:
333                got_all = False
334    return got_all
335
336def randomize_constraint_order(indexes):
337    """
338    Randomly reorder the lists of constraints that provides and accepts hold.
339    """
340    if not isinstance(indexes, tuple):
341        indexes = (indexes,)
342
343    for idx in indexes:
344        for k in idx.keys():
345            random.shuffle(idx[k])
346
347def remote_ns2topdl(uri, desc, cert):
348    """
349    Call a remote service to convert the ns2 to topdl (and in fact all the way
350    to a topdl.Topology.
351    """
352
353    req = { 'description' : { 'ns2description': desc }, }
354
355    r = service_caller('Ns2Topdl')(uri, req, cert)
356
357    if r.has_key('Ns2TopdlResponseBody'):
358        r = r['Ns2TopdlResponseBody']
359        ed = r.get('experimentdescription', None)
360        if 'topdldescription' in ed:
361            return topdl.Topology(**ed['topdldescription'])
362        else:
363            return None
364    else:
365        return None
366
367def connect_composition_points(top, contraints, names):
368    """
369    top is a topology containing copies of all the topologies represented in
370    the contsraints, flattened into one name space.  This routine inserts the
371    additional substrates required to interconnect the topology as described by
372    the constraints.  After the links are made, unused connection points are
373    purged.
374    """
375    done = set()
376    for c in constraints:
377        if c not in done and c.match:
378            # c is an unprocessed matched constraint.  Create a substrate
379            # and attach it to the interfaces named by c and c.match.
380            sn = make_new_name(names, "sub")
381            s = topdl.Substrate(name=sn)
382
383            # These are the nodes that need to be connected.  Put an new
384            # interface on each one and hook them to the new substrate.
385            for e in [ e for e in top.elements \
386                    if isinstance(e, topdl.Computer) \
387                        and e.name in (c.name, c.match.name)]:
388                ii = make_new_name(set([x.name for x in e.interface]), "inf")
389                e.interface.append(
390                        topdl.Interface(substrate=[sn], name=ii, element=e))
391
392
393            # c and c.match have been processed, so add them to the done set,
394            # and add the substrate
395            top.substrates.append(s)
396            done.add(c)
397            done.add(c.match)
398
399    top.incorporate_elements()
400
401def import_ns2_constraints(contents):
402    """
403    Contents is a list containing the lines of an annotated ns2 file.  This
404    routine extracts the constraint comment lines and convertes them into
405    constraints in the namespace of the tcl experiment, as well as inserting
406    them in the accepts and provides indices.
407
408    Constraints are given in lines of the form
409        name:required:provides:accepts
410    where name is the name of the node in the current topology, if the second
411    field is "required" this is a required constraint, a list of attributes
412    that this connection point provides and a list that it accepts.  The
413    provides and accepts lists are comma-separated.  The constraint is added to
414    the marks dict under the name key and that dict is returned.
415    """
416
417    const_re = re.compile("\s*#\s*COMPOSITION:\s*([^:]+:[^:]+:.*)")
418
419    constraints = [ ]
420    for l in contents:
421        m = const_re.search(l)
422        if m:
423            exp = re.sub('\s', '', m.group(1))
424            nn, r, p, a = exp.split(":")
425            if nn.find('(') != -1:
426                # Convert array references into topdl names
427                nn = re.sub('\\((\\d)\\)', '-\\1', nn)
428            p = p.split(",")
429            a = a.split(",")
430            constraints.append(constraint(name=nn, required=(r == 'required'),
431                    provides=p, accepts=a))
432    return constraints
433
434def import_ns2_component(fn):
435    """
436    Pull a composition component in from an ns2 description.  The Constraints
437    are parsed from the comments using import_ns2_constraints and the topology
438    is created using a call to a fedd exporting the Ns2Topdl function.  A
439    topdl.Topology object rempresenting the component's topology and a dict
440    mapping constraints from the components names to the conttraints is
441    returned.  If either the file read or the conversion fails, appropriate
442    Exceptions are thrown.
443    """
444    f = open(fn, "r")
445    contents = [ l for l in f ]
446
447    marks = import_ns2_constraints(contents)
448    top = remote_ns2topdl(opts.url, "".join(contents), cert)
449    if not top:
450        raise RuntimeError("Cannot create topology from: %s" % fn)
451
452    return (top, marks)
453
454def import_xml_component(fn):
455    """
456    Pull a component in from a topdl description.
457    """
458    return (topdl.topology_from_xml(filename=fn, top='experiment'), 
459            constraints_from_xml(filename=fn, top='constraints'))
460
461def index_constraints(constraints, provides, accepts, names):
462    """
463    Add constraints to the provides and accepts indices based on the attributes
464    of the contstraints.  Also index by name.
465    """
466    for c in constraints:
467        for attr, dict in ((c.provides, provides), (c.accepts, accepts)):
468            for a in attr:
469                if a not in dict: dict[a] = [c]
470                else: dict[a].append(c)
471        if c.name in names: names[c.name].append(c)
472        else: names[c.name]= [ c ]
473
474def get_suffix(fn):
475    """
476    We get filename suffixes a couple places.  It;s worth using the same code.
477    This gets the shortest . separated suffix from a filename, or None.
478    """
479    idx = fn.rfind('.')
480    if idx != -1: return fn[idx+1:]
481    else: return None
482
483
484def output_composition(top, constraints, outfile=None, format=None, 
485        output_testbeds=False):
486    """
487    Output the composition to the file named by outfile (if any) in the format
488    given by format if any.  If both are None, output to stdout in topdl
489    """
490    def xml_out(f, top, constraints, output_testbeds):
491        """
492        Output into topdl.  Just call the topdl output, as the constraint
493        attributes should be in the topology.
494        """
495        print >>f, "<component>"
496        if constraints:
497            print >>f, "<constraints>"
498            for c in constraints:
499                print >>f, c.to_xml()
500            print >>f, "</constraints>"
501        print >>f, topdl.topology_to_xml(comp, top='experiment')
502        print >>f, "</component>"
503
504    def ns2_out(f, top, constraints, output_testbeds):
505        """
506        Reformat the constraint data structures into ns2 constraint comments
507        and output the ns2 using the topdl routine.
508        """
509        # Inner routines
510        # Deal with the possibility that the single string name is still in the
511        # constraint.
512        def name_format(n):
513            if isinstance(n, tuple): return n[0]
514            else: return n
515           
516           
517        # Format the required field back into a string. (ns2_out inner
518        def required_format(x):
519            if x: return "required"
520            else: return "optional"
521
522        def testbed_filter(e):
523            if isinstance(e, topdl.Computer) and e.get_attribute('testbed'):
524                return 'tb-set-node-testbed ${%s} "%s"' % \
525                        (topdl.to_tcl_name(e.name), e.get_attribute('testbed'))
526            else:
527                return ""
528
529        if output_testbeds: filters = [ testbed_filter ] 
530        else: filters = [ ] 
531       
532        # ns2_out main line
533        for c in constraints:
534            print >>f, "# COMPOSITION: %s:%s:%s:%s" % (
535                    topdl.to_tcl_name(name_format(c.name)),
536                    required_format(c.required), ",".join(c.provides),
537                    ",".join(c.accepts))
538        print >>f, topdl.topology_to_ns2(top, filters=filters)
539
540    # Info to map from format to output routine. 
541    exporters = {
542            'xml':xml_out, 'topdl':xml_out,
543            'tcl': ns2_out, 'ns': ns2_out,
544            }
545
546    if format:
547        # Explicit format set, use it
548        if format in exporters:
549            exporter = exporters[format]
550        else:
551            raise RuntimeError("Unknown format %s" % format)
552    elif outfile:
553        # Determine the format from the suffix (if any)
554        s = get_suffix(outfile)
555        if s and s in exporters:
556            exporter = exporters[s]
557        else:
558            raise RuntimeError("Unknown format (suffix) %s" % outfile)
559    else:
560        # Both outfile and format are empty
561        exporter = xml_out
562
563    # The actual output.  Open the file, if any, and call the exporter
564    if outfile: f = open(outfile, "w")
565    else: f = sys.stdout
566    exporter(f, top, constraints, output_testbeds)
567    if outfile: f.close()
568
569def import_components(files):
570    """
571    Pull in the components.  The input is a sequence of tuples where each tuple
572    includes the name of the file to pull the component from and the number of
573    copies to make of it.  The routine to read a file is picked by its suffix.
574    On completion, a tuple containing the number of components successfully
575    read, a list of the topologies, a set of names in use accross all
576    topologies (for inserting later names), the constraints extracted, and
577    indexes mapping the attribute provices and accepted tinto the lists of
578    constraints that provide or accept them is returned.
579    """
580    importers = {
581            'tcl': import_ns2_component, 
582            'ns': import_ns2_component, 
583            'xml':import_xml_component,
584            'topdl':import_xml_component,
585            }
586    names = set()
587    constraints = [ ]
588    provides = { }
589    accepts = { }
590    components = 0
591    topos = [ ]
592
593    for fn, cnt in files:
594        try:
595            s = get_suffix(fn)
596            if s and s in importers:
597                top, cons = importers[s](fn)
598            else:
599                warn("Unknown suffix on file %s.  Ignored" % fn)
600                continue
601        except service_error, e:
602            warn("Remote error on %s: %s" % (fn, e))
603            continue
604        except EnvironmentError, e:
605            warn("Error on %s: %s" % (fn, e))
606            continue
607
608        # Parsed the component and sonctraints, now work through the rest of
609        # the pre-processing.  We do this once per copy of the component
610        # requested, cloning topologies and constraints each time.
611        for i in range(0, cnt):
612            components += 1
613            t = top.clone()
614            c = copy.deepcopy(cons)
615            marks = { }
616            # Bind the constraints in m (the marks copy) to this topology
617            for cc in c:
618                cc.topology = t
619            index_constraints(c, provides, accepts, marks)
620            localize_names(t, names, marks)
621            constraints.extend(c)
622            topos.append(t)
623
624    return (components, topos, names, constraints, provides, accepts)
625
626# Main line begins
627parser = ComposeOptionParser()
628
629opts, args = parser.parse_args()
630
631if opts.cert:
632    cert = opts.cert
633elif os.access(os.path.expanduser("~/.ssl/emulab.pem"), os.R_OK):
634    cert = os.path.expanduser("~/.ssl/emulab.pem")
635else:
636    cert = None
637
638random.seed(opts.seed)
639
640files = opts.files
641files.extend([ (a, 1) for a in args])
642
643# Pull 'em in.
644components, topos, names, constraints, provides, accepts = \
645        import_components(files)
646
647# If more than one component was given, actually do the composition, otherwise
648# this is probably a format conversion.
649if components > 1:
650    # Mix up the constraint indexes
651    randomize_constraint_order((provides, accepts))
652
653    # Now the various components live in the same namespace and are marked with
654    # their composition requirements.
655
656    if not meet_constraints([c for c in constraints if c.required], 
657            provides, accepts, opts.same_node, opts.same_topo, opts.multi_pair):
658        if opts.lax:
659            warn("warning: could not meet all required constraints")
660        else:
661            sys.exit("Failed: could not meet all required constraints")
662
663    meet_constraints([ c for c in constraints if not c.match ], 
664            provides, accepts, opts.same_node, opts.same_topo, opts.multi_pair)
665
666    # Add testbed attributes if requested
667    if opts.add_testbeds:
668        for i, t in enumerate(topos):
669            for e in [ e for e in t.elements if isinstance(e, topdl.Computer)]:
670                e.set_attribute('testbed', 'testbed%03d' % i)
671
672    # Make a topology containing all elements and substrates from components
673    # that had matches.
674    comp = topdl.Topology()
675    for t in set([ c.topology for c in constraints if c.match]):
676        comp.elements.extend([e.clone() for e in t.elements])
677        comp.substrates.extend([s.clone() for s in t.substrates])
678
679    # Add substrates and connections corresponding to composition points
680    connect_composition_points(comp, constraints, names)
681
682elif components == 1:
683    comp = topos[0]
684    if opts.add_testbeds:
685        for e in [ e for e in comp.elements if isinstance(e, topdl.Computer)]:
686            e.set_attribute('testbed', 'testbed001')
687
688else:
689    sys.exit("Did not read any components.")
690
691# Put out the composition with only the unmatched constraints
692output_composition(comp, [c for c in constraints if not c.match], 
693        opts.outfile, opts.format, opts.output_testbeds)
694
695sys.exit(0)
Note: See TracBrowser for help on using the repository browser.