annotate_rspec_v2.cc 28.4 KB
Newer Older
1
/*
Robert Ricci's avatar
Robert Ricci committed
2
 * Copyright (c) 2003-2010 University of Utah and the Flux Group.
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 * 
 * {{{EMULAB-LICENSE
 * 
 * This file is part of the Emulab network testbed software.
 * 
 * This file is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or (at
 * your option) any later version.
 * 
 * This file is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Affero General Public License
 * along with this file.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * }}}
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
 */

static const char rcsid[] = "$Id: annotate_rspec_v2.cc,v 1.9 2009-10-21 20:49:26 tarunp Exp $";

#ifdef WITH_XML

#include "annotate.h"
#include "annotate_rspec_v2.h"

#include <xercesc/util/PlatformUtils.hpp>

#include <xercesc/dom/DOM.hpp>

#include "xstr.h"
#include "xmlhelpers.h"

#include <iostream>
#include <utility>
#include <list>
#include <string>
				 
#define XMLDEBUG(x) (cerr << x);
				 
extern DOMDocument* doc;
extern DOMElement* request_root;
47 48
extern DOMElement* advt_root;

49
extern map<string, DOMElement*>* advertisement_elements;
50 51 52

extern map<string,string>* pIfacesMap;
extern map<string,string>* vIfacesMap;
53 54 55 56
				 
XERCES_CPP_NAMESPACE_USE
using namespace std;

57 58 59
// TODO: Link mapping has been disabled. Re-enable this when all bugs 
// related to interfaces on switches have been fixed.

60 61
annotate_rspec_v2 :: annotate_rspec_v2 ()
{
62
  this->document = doc;
63
  this->virtual_root = request_root;
64
  //  this->virtual_root = dynamic_cast<DOMElement*>(dynamic_cast<DOMNode*>(request_root)->cloneNode(true));
65
  this->physical_root = advt_root;
66
  this->physical_elements = advertisement_elements;
67 68 69 70 71

#ifdef DISABLE_LINK_ANNOTATION
    cerr << "WARNING: Annotation code will execute, "
	 << "but links will not be annotated" << endl;
#endif
72 73 74 75 76 77 78 79 80 81 82 83 84
  
  vector<DOMElement*> lan_links 
    = getElementsHavingAttribute(this->virtual_root, "link", "is_lan");
  vector<DOMElement*>::iterator it;
  for (it = lan_links.begin(); it < lan_links.end(); it++) {
    DOMElement* lan_link = *it;
    // Removing annotations inserted earlier
    lan_link->removeAttribute(XStr("is_lan").x());
    string lan_link_id 
      = string(XStr(lan_link->getAttribute(XStr("client_id").x())).c());
    set<string> virtual_interface_ids;
    DOMNodeList* interfaces 
      = lan_link->getElementsByTagName(XStr("interface_ref").x());
85
    for (unsigned int j = 0; j < interfaces->getLength(); j++) {
86 87 88 89 90 91 92 93
      DOMElement* interface = dynamic_cast<DOMElement*>(interfaces->item(j));
      virtual_interface_ids.insert
	(string(XStr(interface->getAttribute
		     (XStr("virtual_interface_id").x())).c()));
    }
    this->lan_links_map.insert
      (pair< string, set<string> >(lan_link_id, virtual_interface_ids));
  }
94 95 96

  this->vInterfaceMap = vIfacesMap;
  this->pInterfaceMap = pIfacesMap;
97 98 99 100 101 102 103 104 105 106
}

// Annotate a trivial link
void annotate_rspec_v2::annotate_element (const char* v_name)
{
  DOMElement* vlink 
    = getElementByAttributeValue(this->virtual_root, 
				 "link", "client_id", v_name);
  annotate_interface (vlink, 0);
  annotate_interface (vlink, 1);	
107
#ifndef DISABLE_LINK_ANNOTATION
108
  DOMElement* hop = create_component_hop(vlink);
109 110
    vlink->appendChild(hop);
#endif
111 112 113
}

// This will get called when a node or a direct link needs to be annotated
114 115
void 
annotate_rspec_v2::annotate_element (const char* v_name, const char* p_name)
116 117 118
{
  DOMElement* vnode 
    = getElementByAttributeValue(this->virtual_root, 
119
                                 "node", "client_id", v_name);
120 121 122 123 124 125 126 127
  // If a vnode by that name was found, then go ahead. 
  // If not, that element should be a link
  // We are not terribly concerned about 
  // having to scan the entire physical topology twice
  // because direct links are never really going to happen
  if (vnode != NULL) {
    if (!vnode->hasAttribute(XStr("generated_by_assign").x())) {
      DOMElement* pnode = (this->physical_elements->find(p_name))->second;
128
      vnode->setAttribute(XStr("component_id").x(),
129
                          pnode->getAttribute(XStr("component_id").x()));
130
      vnode->setAttribute(XStr("component_manager_id").x(),
131
                          pnode->getAttribute(XStr("component_manager_id").x()));
132 133 134 135 136
    }
  }
  else {
    DOMElement* vlink 
      = getElementByAttributeValue(this->virtual_root, 
137
                                   "link", "client_id", v_name);
138 139 140
    DOMElement* plink = (this->physical_elements->find(p_name))->second;
    
    // If plink is NULL, then it must be a trivial link
141
    // XXX: Add trivial link support?
142
    if (plink == NULL) {
143
      
144 145 146 147
    }
    annotate_interface (plink, vlink, 0);
    annotate_interface (plink, vlink, 1);
    
148
    DOMElement* hop = create_component_hop(plink, vlink, BOTH, NULL);
149
#ifndef DISABLE_LINK_ANNOTATION
150
    vlink->appendChild(hop);
151
#endif    
152 153 154
    
    if (vlink->hasAttribute(XStr("generated_by_assign").x())) {
      string str_lan_link 
155
        = string(XStr(vlink->getAttribute(XStr("lan_link").x())).c());
156
      DOMElement* lan_link 
157 158 159
        = getElementByAttributeValue(this->virtual_root, "link", 
                                     "client_id", 
                                     str_lan_link.c_str());
160
      DOMNodeList* component_hops 
161 162 163 164 165
        = vlink->getElementsByTagName(XStr("component_hop").x());
      for (unsigned int i = 0; i < component_hops->getLength(); i++) {
        DOMElement* component_hop 
          = dynamic_cast<DOMElement*>(component_hops->item(i));
        copy_component_hop(lan_link, component_hop);
166 167 168 169 170 171 172
      }
    }
  }
}

// This is called when an intraswitch or interswitch link has to be annotated
void annotate_rspec_v2::annotate_element (const char* v_name, 
173
                                          list<const char*>* unordered)
174
{
175 176 177 178
  // We can't locate interfaces on the switches, so we don't add those 
  // to the annotation. The warning is only given the one time
  static bool gave_apology = false;

179 180 181
  // Re-order links to ensure that they are all head-to-tail.
  list<const char*>* links = this->reorderLinks(unordered);

182 183 184 185 186 187 188 189 190 191 192 193 194
  // These are the paths from the source to the first switch
  // and from the last switch to the destination
  const char* psrc_name = links->front();	
  const char* pdst_name = links->back();	
  DOMElement* p_src_switch_link 
    = (this->physical_elements->find(psrc_name))->second;
  DOMElement* p_switch_dst_link 
    = (this->physical_elements->find(pdst_name))->second;
  
  // Remove these links from the list
  // If it is an intra-switch link, the list should now be empty.
  links->pop_front();
  links->pop_back();
195

196 197
  DOMElement* vlink 
    = getElementByAttributeValue (this->virtual_root, "link", 
198
                                  "client_id", v_name);
199 200 201
  annotate_interface(p_src_switch_link, vlink, 0);
  annotate_interface(p_switch_dst_link, vlink, 1);
  
202
  vector<DOMElement*> componentHops;
203
  DOMElement* prevComponentHop 
204
    = create_component_hop (p_src_switch_link, vlink, SOURCE, NULL);
205
  componentHops.push_back(prevComponentHop);
206

207 208 209 210 211 212
  for (DOMElement *prevLinkInPath = p_src_switch_link; !links->empty(); ) {
#ifndef DISABLE_LINK_ANNOTATION
    if (!gave_apology) { 
      gave_apology = true;
      cerr << endl << "\nWARNING: Unable to locate interfaces on "
	"switch/switch links; omitting those from the annotation" << endl;
213 214
    }
#endif
215
    DOMElement* pSwitchSwitchLink 
216
      //      = ((this->physical_elements)->find(*it))->second;
217 218
      = find_next_link_in_path (prevLinkInPath, links);
    prevComponentHop = create_component_hop (pSwitchSwitchLink, vlink, 
219
                                             NEITHER, prevComponentHop);
220 221 222
    prevLinkInPath = pSwitchSwitchLink;
    //    componentHops.push_back(prevComponentHop);
  }
223
  
224
  DOMElement* hop = create_component_hop (p_switch_dst_link, vlink, 
225
                                          DESTINATION, prevComponentHop);
226 227
  componentHops.push_back(hop);
#ifndef DISABLE_LINK_ANNOTATION
228
  for (unsigned int i = 0; i < componentHops.size(); i++) {
229
    vlink->appendChild(componentHops[i]);
230
  }
231
#endif
232 233 234 235 236
}

// Creates a component_hop for a trivial link
DOMElement* annotate_rspec_v2::create_component_hop (DOMElement* vlink)
{
237 238 239 240 241 242 243
  DOMNodeList* ifaces = vlink->getElementsByTagName(XStr("interface_ref").x());
  DOMElement* srcIface = dynamic_cast<DOMElement*>(ifaces->item(0));
  DOMElement* dstIface = dynamic_cast<DOMElement*>(ifaces->item(1));
  string srcIfaceId = XStr(srcIface->getAttribute(XStr("client_id").x())).c();
  string dstIfaceId = XStr(dstIface->getAttribute(XStr("client_id").x())).c();

  bool fnd;
244 245
  string srcIfaceNodeId =this->lookupIface(this->vInterfaceMap,srcIfaceId,fnd);
  string dstIfaceNodeId =this->lookupIface(this->vInterfaceMap,dstIfaceId,fnd);
246 247

  DOMElement* srcIfaceClone 
248
    = dynamic_cast<DOMElement*>(doc->importNode
249 250
				(dynamic_cast<DOMNode*>(srcIface),true));
  srcIfaceClone->setAttribute(XStr("component_id").x(), XStr("loopback").x()); 
251
  
252 253 254 255 256 257 258 259 260 261
  DOMElement* dstIfaceClone
    = dynamic_cast<DOMElement*>(doc->importNode
				(dynamic_cast<DOMNode*>(dstIface),true));
  dstIfaceClone->setAttribute(XStr("component_id").x(), XStr("loopback").x());

  DOMElement* hop = doc->createElement(XStr("component_hop").x());  
  hop->appendChild(srcIfaceClone);
  hop->appendChild(dstIfaceClone);

  return hop;
262 263 264 265 266
}

// Creates a hop from a switch till the next end point. 
DOMElement* 
annotate_rspec_v2::create_component_hop (const DOMElement* plink, 
267 268 269
                                         DOMElement* vlink, 
                                         int endpointIface, 
                                         const DOMElement* prevHop)
270 271
{
  // We assume the first interface is the source and the second the dest
272 273 274
  DOMNodeList* pIfaces =plink->getElementsByTagName(XStr("interface_ref").x());
  DOMElement* plinkSrcIface = dynamic_cast<DOMElement*>(pIfaces->item(0));
  DOMElement* plinkDstIface = dynamic_cast<DOMElement*>(pIfaces->item(1));
275
  
276 277 278 279 280 281 282 283 284
  DOMNodeList* vIfaces =vlink->getElementsByTagName(XStr("interface_ref").x());
  DOMElement* vlinkSrcIface = dynamic_cast<DOMElement*>(vIfaces->item(0));
  DOMElement* vlinkDstIface = dynamic_cast<DOMElement*>(vIfaces->item(1));

  string vlinkSrcIfaceId 
    = XStr(vlinkSrcIface->getAttribute(XStr("client_id").x())).c();

  string vlinkDstIfaceId 
    = XStr(vlinkDstIface->getAttribute(XStr("client_id").x())).c();
285

286 287 288
  // If the previous component hop is not specified (NULL),
  // then the link is either direct 
  // or the direction is guaranteed to be from the node to the switch
289
  DOMElement* plinkSrcIfaceClone 
290
    = dynamic_cast<DOMElement*>(doc->importNode
291
                                (dynamic_cast<DOMNode*>(plinkSrcIface),true));
292
  DOMElement* plinkDstIfaceClone
293
    = dynamic_cast<DOMElement*>(doc->importNode
294
                                (dynamic_cast<DOMNode*>(plinkDstIface),true));
295 296 297 298 299 300 301 302 303 304 305
  
  string plinkSrcIfaceId 
    = XStr(plinkSrcIface->getAttribute(XStr("component_id").x())).c();
  string plinkDstIfaceId 
    = XStr(plinkDstIface->getAttribute(XStr("component_id").x())).c();
  
  bool found = false;
  string plinkSrcNodeId = this->lookupIface(this->pInterfaceMap,
					    plinkSrcIfaceId, found);
  string plinkDstNodeId = this->lookupIface(this->pInterfaceMap, 
					    plinkDstIfaceId, found);
306

307 308
  // If the previous component is specified,
  // the link specification could be the opposite of what we need
309
  if (prevHop != NULL)  {
310
    // Find the destination of the previous component hop
311 312
    DOMElement* prevHopDstIface
      = dynamic_cast<DOMElement*>((prevHop->getElementsByTagName
313
                                   (XStr("interface_ref").x()))->item(1));
314 315 316 317 318 319

    string prevHopDstIfaceId 
      = XStr(prevHopDstIface->getAttribute(XStr("component_id").x())).c();
    string prevHopDstNodeId = this->lookupIface(this->pInterfaceMap, 
						prevHopDstIfaceId, found);

320 321 322 323 324 325
    // We need to do this because in advertisements, 
    // all links are from nodes to switches
    // and we need to reverse this for the last hop of a multi-hop path
    // This is slightly more expensive, 
    // but definitely more robust than checking based on 
    // whether a destination interface was specified
326
    if (prevHopDstNodeId == plinkDstNodeId) {
327
      plinkSrcIfaceClone 
328 329 330
        = dynamic_cast<DOMElement*>(doc->importNode
                                    (dynamic_cast<DOMNode*>(plinkDstIface), 
                                     true));
331
      plinkDstIfaceClone 
332 333 334
        = dynamic_cast<DOMElement*>(doc->importNode
                                    (dynamic_cast<DOMNode*>(plinkSrcIface), 
                                     true));
335 336 337
    }
  }
  
338 339 340 341 342 343 344 345 346 347 348
  //Annotate the link endpoint 
  if (endpointIface != NEITHER) {
    bool annotated;
    annotated = this->annotate_endpoint(plinkSrcIfaceClone, vlinkSrcIfaceId);
    if (!annotated) {
      this->annotate_endpoint(plinkDstIfaceClone, vlinkSrcIfaceId);
    }
    annotated = this->annotate_endpoint(plinkDstIfaceClone, vlinkDstIfaceId);
    if (!annotated) {
      this->annotate_endpoint(plinkSrcIfaceClone, vlinkDstIfaceId);
    }
349
  }
350

351 352 353 354 355 356 357 358 359 360 361 362 363 364
  // Find the physical nodes for the source and destination interfaces
  // We need these to determine the component manager IDs.
  DOMElement* plinkSrcNode 
    = ((this->physical_elements)->find(plinkSrcNodeId))->second;
  DOMElement* plinkDstNode
    = ((this->physical_elements)->find(plinkDstNodeId))->second;

  plinkSrcIfaceClone->setAttribute
    (XStr("component_manager_id").x(),
     plinkSrcNode->getAttribute(XStr("component_manager_id").x()));
  plinkDstIfaceClone->setAttribute
    (XStr("component_manager_id").x(),
     plinkDstNode->getAttribute(XStr("component_manager_id").x()));

365 366 367
  // Create a single_hop_link element
  DOMElement* hop = doc->createElement(XStr("component_hop").x());
  copy_component_spec(plink, hop);
368 369
  
  // Add interface specifications to the link in the single hop element
370 371
  hop->appendChild(plinkSrcIfaceClone);
  hop->appendChild(plinkDstIfaceClone);
372
  
373
  return hop;
374 375 376 377 378 379 380 381 382 383 384 385
}

// Copies the component_hop from the generated_link to the requsted_link
// Also strips the unnecessary annotations from the component_hop after copying
// The "unnecessary annotations" 
// specify the end point of the link to be the auto-generated lan node
// We could just assume that the second interface_ref in the hop contains these
// "unnecessary annotations" since we have generated it in the first place
// and we can sure that it will always be in exactly that same position,
// but it sounds like a dirty way of doing it and is not exactly robust,
// so we shall use the slower, but more robust method
void annotate_rspec_v2::copy_component_hop(DOMElement* lan_link, 
386
                                           DOMElement* component_hop)
387 388 389 390 391
{
  string lan_link_id 
    = string(XStr(lan_link->getAttribute(XStr("client_id").x())).c());
  DOMNodeList* interfaces 
    = component_hop->getElementsByTagName(XStr("interface_ref").x());
392
  for (unsigned int i = 0; i < interfaces->getLength(); i++) {
393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424
    DOMElement* interface = dynamic_cast<DOMElement*>(interfaces->item(i));
    if (interface->hasAttribute(XStr("virtual_interface_id").x())) {
      string str_virtual_interface_id 
	= string(XStr(interface->getAttribute
		      (XStr("virtual_interface_id").x())).c());
      if (!has_interface_with_id (lan_link_id, str_virtual_interface_id)) {
	interface->removeAttribute(XStr("virtual_interface_id").x());
	interface->removeAttribute(XStr("virtual_node_id").x());
      }	
    }
  }
  lan_link->appendChild(dynamic_cast<DOMElement*>
			(doc->importNode(component_hop, true)));
}

// Checks if the link contains an interface with virtual_interface_id = id
bool annotate_rspec_v2::has_interface_with_id (string link_client_id, string id)
{
  map< string, set<string> >::iterator map_it;
  set<string>::iterator set_it;
  map_it = lan_links_map.find(link_client_id);
  if (map_it == this->lan_links_map.end())
    return false;
  set<string> client_ids = map_it->second;
  set_it = client_ids.find(id);
  if (set_it == client_ids.end())
    return false;
  return true;
}

// Annotates the interfaces on a node making up the end points of a trivial link
void annotate_rspec_v2::annotate_interface (const DOMElement* vlink, 
425
                                            int interface_number)
426 427 428 429 430 431
{
  this->annotate_interface (NULL, vlink, interface_number, true);
}

// Annotates the interfaces on a non-trivial link
void annotate_rspec_v2::annotate_interface (const DOMElement* plink,
432 433
                                            const DOMElement* vlink,
                                            int interface_number)
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
{
  this->annotate_interface (plink, vlink, interface_number, false);
}

// Updates the node which is the end point of the link
// 1) Find the interface_ref from the list of interface_refs on the link 
//    and it's virtual_interface_id
// 2) Find the virtual node to which the interface_ref is referring 
//    and its corresponding interface
// 3) Use this to find the physical node (component_node_uuid/urn) to which 
//    the virtual node has been mapped
// 4) Find the corresponding interface_ref on the physical link to which 
//    the virtual link has been mapped and get its component_interface_id
// 5) Annotate the interface on the virtual node obtained in 2) 
//    with the interface_id obtained in 4)
void annotate_rspec_v2::annotate_interface (const DOMElement* plink, 
450 451 452
                                            const DOMElement* vlink, 
                                            int ifaceNumber,
                                            bool isTrivialLink)
453
{
454 455 456
  DOMNodeList* refs = vlink->getElementsByTagName(XStr("interface_ref").x());
  DOMElement* ref = dynamic_cast<DOMElement*>(refs->item(ifaceNumber));
  string ifaceId = XStr(ref->getAttribute(XStr("client_id").x())).c();
457
  //  cerr << endl << "Interface: " << ifaceId << endl;
458 459
  
  // Get the client_id of the node to which the interface belongs
460 461 462
  bool found = false;
  string nodeId = this->lookupIface(this->vInterfaceMap, ifaceId, found);
  DOMElement* vnode = getElementByAttributeValue(this->virtual_root, "node", 
463
                                                 "client_id", nodeId.c_str());
464
  DOMElement* decl = getElementByAttributeValue(vnode, "interface", 
465
                                                "client_id", ifaceId.c_str());
466 467 468

  string physNodeId = XStr(vnode->getAttribute(XStr("component_id").x())).c();

469 470 471 472 473 474 475 476 477 478
  // When the link is a trivial link, the interface name is loopback
  string interface = "loopback";
  string shortName = "";

  // This entire block is ifdef'ed because we have trouble annotating 
  // interfaces when a requested lan node is mapped to a switch
  // Once we have support for interfaces on switches, this problem will go away
  // XXX: While link mapping is disabled, node annotations will be 
  // inconsistent when any one node is mapped onto a switch
#ifndef DISABLE_LINK_ANNOTATION
479 480 481 482 483
  if (!isTrivialLink) {
    // Find the interface on the physical link which is situated
    // on the physical node to which the vnode has been mapped
    const DOMElement* pIface = this->getIfaceOnNode(plink, physNodeId);
    if (pIface == NULL) {
484
      cerr << "\n\n*** No interface on " 
485
	   << XStr(plink->getAttribute(XStr("component_id").x())).c()
486 487 488 489 490 491 492 493 494
	   << " is declared on node " << physNodeId << endl << endl;
      cerr << "*** Additional information: " << endl;
      cerr << "Virtual link ID: "
	   << XStr(vlink->getAttribute(XStr("client_id").x())).c() << endl;
      cerr << "Interface ID on vlink: " << ifaceId << endl;
      cerr << "Interface declared on vnode: " << nodeId << endl;
      cerr << "Virtual node mapped to: " << physNodeId << endl;
      cerr << "Physical link ID: " 
	   << XStr(plink->getAttribute(XStr("component_id").x())).c() << endl;
495
      exit(EXIT_FATAL);
496
    }
497 498
    interface = XStr(pIface->getAttribute(XStr("component_id").x())).c();
    shortName = this->getShortInterfaceName(interface);
499
  }
500 501 502 503 504 505 506 507 508 509

  // We also need to add the fixedinterface element to this
  // since we need to ensure that when a partially mapped request is fed
  // back into assign, the link isn't mapped to a different set of interfaces
  
  // XXX: This is not robust at all since it assumes that assign's output 
  // will always have the interface name at the end with the form: *:<iface>
  decl->setAttribute(XStr("component_id").x(), XStr(interface).x());
  this->addFixedInterface(decl, shortName);
#endif
510 511 512
}

// Copies the component spec from the source to the destination
513 514
void 
annotate_rspec_v2::copy_component_spec(const DOMElement* src, DOMElement* dst)
515
{
516 517 518 519 520
  dst->setAttribute(XStr("component_id").x(), 
		    XStr(src->getAttribute(XStr("component_id").x())).x());
  dst->setAttribute(XStr("component_manager_id").x(), 
		    XStr(src->getAttribute
			 (XStr("component_manager_id").x())).x());
521 522 523 524 525 526
}

// Finds the next link in the path returned by assign
// Assign sometimes reverses the links on the path 
// from the source to destination, 
// so you need to look at the entire path to find the next link
527 528 529 530
// WARNING: This removes the link in the path from the list of link
DOMElement* 
annotate_rspec_v2::find_next_link_in_path (DOMElement *prev, 
                                           list<const char*>* links)
531 532 533
{
  list<const char*>::iterator it;
  DOMElement* link = NULL;
534

535 536
  for (it = links->begin(); it != links->end(); ++it) {
    link = (this->physical_elements->find(*it))->second;
537 538 539 540

    // We assume as we have done throughout that the first interface 
    // represents the source of the link and the second interface
    // is the destination.
541 542 543 544 545 546 547 548 549
    string linkSrc = this->getNthInterface(link, 0);
    string linkDst = this->getNthInterface(link, 1);
    string prevSrc = this->getNthInterface(prev, 0);
    string prevDst = this->getNthInterface(prev, 1);

    if ((linkSrc == prevDst && linkDst != prevSrc)
        || (linkSrc == prevSrc && linkDst != prevDst)
        || (linkDst == prevSrc && linkSrc != prevDst)
        || (linkDst == prevDst && linkSrc != prevSrc)) {
550 551 552 553 554 555 556 557 558 559 560 561 562 563
      links->remove(*it);
      break;
    }
  }
  return link;
}

void annotate_rspec_v2::cleanup()
{
  vector<DOMElement*>::iterator it;
  
  // Remove generated links
  vector<DOMElement*> generated_links 
    = getElementsHavingAttribute(this->virtual_root, "link", 
564
                                 "generated_by_assign");
565 566 567 568 569 570 571 572
  for (it = generated_links.begin(); it < generated_links.end(); it++) {
    DOMNode* generated_link = dynamic_cast<DOMNode*>(*it);
    dynamic_cast<DOMNode*>(this->virtual_root)->removeChild(generated_link);
  }
  
  // Remove generated nodes
  vector<DOMElement*> generated_nodes 
    = getElementsHavingAttribute(this->virtual_root, "node", 
573
                                 "generated_by_assign");
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
  for (it = generated_nodes.begin(); it < generated_nodes.end(); it++) {
    DOMNode* generated_link = dynamic_cast<DOMNode*>(*it);
    dynamic_cast<DOMNode*>(this->virtual_root)->removeChild(generated_link);
  }
  
  // Remove additional attributes added to elements
  
  // Remove the is_lan attribute
  vector<DOMElement*> lan_links 
    = getElementsHavingAttribute(this->virtual_root, "link", "is_lan");
  for (it = lan_links.begin(); it < lan_links.end(); it++) {
    DOMElement* lan_link = *it;
    lan_link->removeAttribute(XStr("is_lan").x());
  }
}

bool annotate_rspec_v2::is_generated_element(const char* tag, 
					     const char* attr_name, 
					     const char* attr_value)
{
  DOMElement* element 
    = getElementByAttributeValue(this->virtual_root, tag, 
				 attr_name, attr_value);
  if (element == NULL)
    return false;
  return (element->hasAttribute(XStr("generated_by_assign").x()));
}

602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621
string annotate_rspec_v2::lookupIface (map<string,string>* ifacesMap, 
				       string ifaceId,
				       bool& found) 
{
  string nodeId = "";
  found = false;
  map<string, string>::iterator it = ifacesMap->find(ifaceId);
  if (it != ifacesMap->end()) {
    nodeId = it->second;
    found = true;
  }
  return nodeId;
}

// Returns that interface on the physical link which is declared in 
// the physical node nodeId
const DOMElement* 
annotate_rspec_v2::getIfaceOnNode(const DOMElement* plink, string nodeId)
{
  DOMNodeList* refs = plink->getElementsByTagName(XStr("interface_ref").x());
622
  for (unsigned int i = 0; i < refs->getLength(); i++) {
623 624 625 626 627 628 629 630 631 632 633
    bool found = false;
    DOMElement* ref = dynamic_cast<DOMElement*>(refs->item(i));
    string ifaceId = XStr(ref->getAttribute(XStr("component_id").x())).c();
    string declNodeId = this->lookupIface(this->pInterfaceMap, ifaceId, found);
    if (found && (declNodeId == nodeId)) {
      return ref;
    }
  }
  return NULL;
}

634 635
// Returns the component id for the nth interface on a link
string annotate_rspec_v2::getNthInterface (const DOMElement* link, int number)
636 637
{
  DOMNodeList* ifaces = link->getElementsByTagName(XStr("interface_ref").x());
638
  if ((int)ifaces->getLength() < number) {
639
    cerr << "*** Link " 
640 641 642
         << XStr(link->getAttribute(XStr("component_id").x())).c()
         << " has only " << ifaces->getLength() << " interfaces. "
         << "Interface number " << number << " requested." << endl;
643 644
    exit(EXIT_FATAL);
  }
645 646
  DOMElement* iface = dynamic_cast<DOMElement*>(ifaces->item(number));
  return string(XStr(iface->getAttribute(XStr("component_id").x())).c());
647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
}

// Annotates the end point interface if found
bool annotate_rspec_v2::annotate_endpoint(DOMElement* iface, string virtId) 
{
  bool found = false;
  bool annotated = false;
  string ifaceId = XStr(iface->getAttribute(XStr("component_id").x())).c();
  string physNodeId = this->lookupIface(this->pInterfaceMap, ifaceId, found);
  string virtNodeId = this->lookupIface(this->vInterfaceMap, virtId, found);
  DOMElement* virtNode
    = getElementByAttributeValue(this->virtual_root, "node", "client_id", 
				 virtNodeId.c_str());
  string mappedTo = XStr(virtNode->getAttribute(XStr("component_id").x())).c();
  if (mappedTo == physNodeId) {
    annotated = true;
    iface->setAttribute(XStr("client_id").x(), XStr(virtId).x());
  }
  return annotated;
}

// Adds a fixed interface element to an interface
void annotate_rspec_v2::addFixedInterface (DOMElement* iface, string shortName)
{
  DOMNodeList* fixedIfaces 
    = iface->getElementsByTagName(XStr("emulab:fixedinterface").x());
  // If a fixed interface is not present, we add one.
  if (fixedIfaces->getLength() == 0) {
    DOMElement* fixedIfaceNode 
      = doc->createElement(XStr("emulab:fixedinterface").x());
    fixedIfaceNode->setAttribute(XStr("name").x(), XStr(shortName).x());
    iface->appendChild(fixedIfaceNode);
  }
}

// Extracts the short interface name from the interface URN
string annotate_rspec_v2::getShortInterfaceName (string interface)
{
  int loc = interface.find_last_of(":");
  return interface.substr(loc+1);
}

689 690 691
// Re-orders the links so that all the links on an interswitch link
// are in the correct order
// WARNING: This will distroy the input list
692 693
// NOTE: The caller has the responsibility to return the freed list and all
// char*s it contains
694 695 696 697 698
list<const char*>* 
annotate_rspec_v2::reorderLinks (list<const char*>* links)
{
  list<const char*> *ordered = new list<const char*>();
  //  list<const char*>::iterator it;
699 700 701 702 703 704

  // IMPORTANT: The *only* reason we can push this char* directly into ordered
  // (instead of making a copy) is that we know that it came from an fstring
  // when the 'links' structure was created, and fstring never frees its
  // strings. If that were not true, this code could produce dangling pointers
  const char *link = links->front();
705
  links->pop_front();
706 707 708
  DOMElement* prev = (this->physical_elements)->find(link)->second;
  ordered->push_back(link);

709 710
  while(!links->empty()) {
    prev = this->find_next_link_in_path(prev, links);
711 712 713 714 715

    // TODO: This is a minor memory leak - we keep the pointer to the char*
    // inside the string, but not the pointer to the string object itself, so
    // it cannot be freed. The best way to clean this up would be to make links
    // and ordered lists of fstrings (not pointers to fstrings)
716 717
    string* link 
      = new string(XStr(prev->getAttribute(XStr("component_id").x())).c());
718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738

    // Remove this link from the list - would rather use links->remove(), but
    // it doesn't seem to be able to compare strings
    list<const char*>::iterator it;
    bool found = false;
    for (it = links->begin(); it != links->end(); it++) {
        if (!strcmp(link->c_str(),*it)) {
            found = true;
            links->erase(it);
            break;
        }
    }

    if (found) {
        ordered->push_back(link->c_str());
    } else {
        // Sanity check 
        cerr << "Error annotating link: couldn't find link (" <<
            link->c_str() << ")" << endl;
        exit(EXIT_FATAL);
    }
739 740 741 742 743
  }
  
  return ordered;
}

744
#endif