All new accounts created on Gitlab now require administrator approval. If you invite any collaborators, please let Flux staff know so they can approve the accounts.

assign.cc 33.9 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1 2
/*
 * EMULAB-COPYRIGHT
3
 * Copyright (c) 2000-2006 University of Utah and the Flux Group.
Robert Ricci's avatar
Robert Ricci committed
4 5 6
 * All rights reserved.
 */

7 8 9 10 11 12 13 14
#include "port.h"

#include <boost/config.hpp>
#include <boost/utility.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
15
#ifdef GRAPHVIZ_SUPPORT
16
#include <boost/graph/graphviz.hpp>
17
#endif
18

19 20
#include <fstream>
#include <iostream>
21
#include <time.h>
Mac Newbold's avatar
Mac Newbold committed
22
#include <stdlib.h>
23
#include <math.h>
Mac Newbold's avatar
Mac Newbold committed
24 25
#include <sys/types.h>
#include <sys/time.h>
26
#include <sys/resource.h>
27 28
#include <signal.h>
#include <sys/signal.h>
29
#include <queue>
30
#include <algorithm>
31 32

using namespace boost;
Mac Newbold's avatar
Mac Newbold committed
33

34 35
#include <stdio.h>

Mac Newbold's avatar
Mac Newbold committed
36
#include "common.h"
37
#include "delay.h"
Mac Newbold's avatar
Mac Newbold committed
38
#include "physical.h"
39
#include "virtual.h"
40
#include "vclass.h"
41
#include "pclass.h"
42
#include "score.h"
43 44 45
#include "solution.h"
#include "maps.h"
#include "anneal.h"
46 47
#include "config.h"

48 49
#ifdef WITH_XML
#include "parse_ptop_xml.h"
50 51 52
#include "parse_vtop_xml.h"
#include "parse_advertisement_rspec.h"
#include "parse_request_rspec.h"
53
#endif
54 55 56

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
57
tb_pgraph PG;
58 59 60 61 62 63 64 65 66 67
tb_pgraph_vertex_pmap pvertex_pmap = get(vertex_data, PG);
tb_pgraph_edge_pmap pedge_pmap = get(edge_data, PG);
tb_sgraph SG;
tb_sgraph_vertex_pmap svertex_pmap = get(vertex_data, SG);
tb_sgraph_edge_pmap sedge_pmap = get(edge_data, SG);
tb_vgraph VG;
tb_vgraph_vertex_pmap vvertex_pmap = get(vertex_data, VG);
tb_vgraph_edge_pmap vedge_pmap = get(edge_data, VG);

// List of virtual types by name.
68
name_count_map vtypes;
69
name_list_map vclasses;
70 71

// A list of all pclasses.
72
pclass_list pclasses;
73 74 75
 	
// Map from a pnode* to the the corresponding pvertex.
pnode_pvertex_map pnode2vertex;
76 77 78

// Map of a type to a tt_entry, a vector of pclasses and the size of
// the vector.
79
pclass_types type_table;
80 81 82
#ifdef PER_VNODE_TT
pclass_types vnode_type_table;
#endif
83

84 85 86 87 88
// This datastructure contains all the information needed to calculate
// the shortest path between any two switches.  Indexed by svertex,
// the value will be a predicate map (indexed by svertex as well) of
// the shortest paths for the given vertex.
switch_pred_map_map switch_preds;
89

90 91
// Same, but for distances 
switch_dist_map_map switch_dist;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
92

93 94
// Time started, finished, and the time limit
double timestart, timeend, timelimit, timetarget;
95

96 97 98
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

99 100 101 102 103
#ifdef GNUPLOT_OUTPUT
FILE *scoresout, *tempout, *deltaout;
#endif
// Whether or not assign is allowed to generate trivial links
bool allow_trivial_links = true;
104

105
// Whether or not assign should use pclasses
106
bool disable_pclasses = false;
107

Robert Ricci's avatar
Robert Ricci committed
108 109 110
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
111 112 113

// Whether or not we should use the experimental support for dynamic pclasses
bool dynamic_pclasses = false;
114 115 116

// Whether or not to allow assign to temporarily over-subscribe pnodes
bool allow_overload = false;
Robert Ricci's avatar
Robert Ricci committed
117 118 119 120

// Forces assign to do greedy link assignment, by chosing the first link in its
// list, which is usually the lowest-cost
bool greedy_link_assignment = false;
Robert Ricci's avatar
Robert Ricci committed
121 122 123 124 125

// Forces assign to skip melting, and, instead, use the temperature given as
// the initial temperature
bool no_melting = false;
double initial_temperature = 0.0f;
126 127 128 129 130 131

// Print out a summary of the solution in addition to the solution itself
bool print_summary = false;

// Use the 'connected' find algorithm
double use_connected_pnode_find = 0.0f;
132

133 134 135
// Whether or not to perform all checks on fixed nodes
bool check_fixed_nodes = false;

136
// Use XML for file input
137 138 139 140 141 142
// bool xml_input = false;
#ifdef WITH_XML
bool ptop_xml_input = false;
bool vtop_xml_input = false;
bool ptop_rspec_input = false;
bool vtop_rspec_input = false;
143
#endif
144

145 146 147
// XXX - shouldn't be in this file
double absbest;
int absbestviolated, iters, iters_to_best;
Robert Ricci's avatar
Robert Ricci committed
148

149 150 151
// Map of all physical types in use in the system
tb_ptype_map ptypes;

152 153 154
/*
 * Internal functions
 */
Mac Newbold's avatar
Mac Newbold committed
155

Robert Ricci's avatar
Robert Ricci committed
156
// Return the CPU time (in seconds) used by this process
157
float used_time() {
158 159 160 161 162 163
  struct rusage ru;
  getrusage(RUSAGE_SELF,&ru);
  return ru.ru_utime.tv_sec+ru.ru_utime.tv_usec/1000000.0+
    ru.ru_stime.tv_sec+ru.ru_stime.tv_usec/1000000.0;
}

164 165 166 167 168 169 170 171 172 173 174 175
// Constructs the output file name for the annotated rspec
string annotated_filename (const char* filepath)
{
	string input_filepath = string(filepath);
	int pos_last_backslash = input_filepath.find_last_of("/");
	string input_filename = input_filepath.substr(pos_last_backslash+1, input_filepath.length()-pos_last_backslash-1);
	string output_filepath = input_filepath.substr(0, pos_last_backslash+1);
	output_filepath.append("annotated-");
	output_filepath.append(input_filename);
	return (output_filepath);
}

Robert Ricci's avatar
Robert Ricci committed
176
// Read in the .ptop file
177
void read_physical_topology(char *filename) {
178 179
  ifstream ptopfile;
  ptopfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
180
  if (!ptopfile.is_open()) {
181
      cout << "*** Unable to open ptop file " << filename << endl;
182
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
183
  }
184 185
  
#ifdef WITH_XML
186 187 188 189 190 191
  if (ptop_xml_input) {
		cout << "Physical Graph: " << parse_ptop_xml(PG,SG,filename) << endl;
  } else if (ptop_rspec_input) {
	  cout << "Physical Graph: " << parse_ptop_rspec (PG, SG, filename) << endl;
	}
	else {
192 193 194
      cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
  }
#else
195
	cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
196
#endif
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218

#ifdef DUMP_GRAPH
  {
    cout << "Physical Graph:" << endl;
    
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
    
    for (;vit != vendit;vit++) {
      tb_pnode *p = get(pvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    pedge_iterator eit,eendit;
    tie(eit,eendit) = edges(PG);

    for (;eit != eendit;eit++) {
      tb_plink *p = get(pedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,PG) << " <-> " <<
	target(*eit,PG) << ")\t" << *p;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
219
#endif // DUMP_GRAPH
220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242

#ifdef GRAPH_DEBUG
  {
    cout << "Switch Graph:" << endl;
    

    svertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(SG);
    
    for (;vit != vendit;vit++) {
      tb_switch *p = get(svertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    sedge_iterator eit,eendit;
    tie(eit,eendit) = edges(SG);

    for (;eit != eendit;eit++) {
      tb_slink *p = get(sedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,SG) << " <-> " <<
	target(*eit,SG) << ")\t" << *p;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
243
#endif // GRAPH_DEBUG
244

Robert Ricci's avatar
Robert Ricci committed
245 246
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
247 248 249 250 251 252 253 254
  pvertex_iterator pvit,pvendit;
  tie(pvit,pvendit) = vertices(PG);
  for (;pvit != pvendit;pvit++) {
    pnode2vertex[get(pvertex_pmap,*pvit)]=*pvit;
  }

}

Robert Ricci's avatar
Robert Ricci committed
255 256
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
257
// XXX: Should soon be replaced by calculate_shortest_routes()
258
void calculate_switch_MST() {
259
  cout << "Calculating shortest paths on switch fabric." << endl;
Robert Ricci's avatar
Robert Ricci committed
260 261

  // Set up the weight map for Dijkstra's
262 263 264 265 266 267 268 269 270 271
  tb_sgraph_weight_pmap sweight_pmap = get(edge_weight, SG);
  sedge_iterator seit,seendit;
  tie(seit,seendit) = edges(SG);
  for (;seit != seendit;seit++) {
    tb_slink *slink = get(sedge_pmap,*seit);
    // XXX should we make this more complicated depending on
    // latency/loss as well?
    put(sweight_pmap,*seit,
	100000000-get(pedge_pmap,slink->mate)->delay_info.bandwidth);
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
272

Robert Ricci's avatar
Robert Ricci committed
273
  // Let boost do the Disjktra's for us, from each switch
274 275 276 277 278 279 280 281
  svertex_iterator svit,svendit;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    switch_preds[*svit] = new switch_pred_map(num_vertices(SG));
    switch_dist[*svit] = new switch_dist_map(num_vertices(SG));
    dijkstra_shortest_paths(SG,*svit,
    			    predecessor_map(&((*switch_preds[*svit])[0])).
			    distance_map(&((*switch_dist[*svit])[0])));
Christopher Alfeld's avatar
 
Christopher Alfeld committed
282 283
  }

284 285 286 287 288 289 290 291 292
#ifdef GRAPH_DEBUG
  cout << "Shortest paths" << endl;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    cout << *svit << ":" << endl;
    for (unsigned int i = 0;i<num_vertices(SG);++i) {
      cout << i << " " << (*switch_dist[*svit])[i] << endl;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
293
#endif // GRAPH_DEBUG
294 295
}

Robert Ricci's avatar
Robert Ricci committed
296
// Read in the .top file
297
void read_virtual_topology(char *filename) {
298 299
  ifstream topfile;
  topfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
300
  if (!topfile.is_open()) {
301
      cout << "*** Unable to open top file " << filename << endl;
302
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
303
  }
304
  
305 306 307 308 309 310 311 312
#ifdef WITH_XML  
  if (vtop_xml_input) {
	cout << "Virtual Graph: " << parse_vtop_xml(VG,filename) << endl;
  }
  else if (vtop_rspec_input){
  	  cout << "Virtual Graph: " << parse_vtop_rspec (VG, filename) << endl ;
  }
  else {
313 314 315
      cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
  }
#else
316
	cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
317
#endif
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342

#ifdef DUMP_GRAPH
  {
    cout << "Virtual Graph:" << endl;
    

    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
    
    for (;vit != vendit;vit++) {
      tb_vnode *p = get(vvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    vedge_iterator eit,eendit;
    tie(eit,eendit) = edges(VG);

    for (;eit != eendit;eit++) {
      tb_vlink *p = get(vedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,VG) << " <-> " <<
	target(*eit,VG) << ")\t" << *p;
    }
  }  
#endif
}
Robert Ricci's avatar
Robert Ricci committed
343 344 345 346 347 348 349 350 351 352
/*
 * Make a pass through the pclasses, looking for ones that no node can use, and
 * nuking them.
 */
void prune_unusable_pclasses() {
    cout << "Pruning pclasses." << endl;
    int pruned = 0;
    pclass_list::iterator pclass_iterator = pclasses.begin();
    while (pclass_iterator != pclasses.end()) {
	if ((*pclass_iterator)->refcount == 0) {
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370
            /*
             * Remove the nodes in the pclass we're removing from the slot
             * counts for their ptypes
             */
            tb_pclass::pclass_members_map::iterator ptype_iterator;
            ptype_iterator = (*pclass_iterator)->members.begin();
            while (ptype_iterator != (*pclass_iterator)->members.end()) {
                /*
                 * Find the recort for this type in the ptypes structure
                 */
                fstring this_type = ptype_iterator->first;
                tb_ptype_map::iterator ptype = ptypes.find(this_type);
                assert(ptype != ptypes.end());
                tb_ptype *this_type_p = ptype->second;

                /*
                 * For every node with this type, we want to remove its slot
                 * count from the total slot count for the type, since we know
371 372 373
                 * we will never use this particular node.
                 * Note: We only have to do this for pclasses that are "real",
                 * not dynamic ones.
374
                 */
375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
                if (!(*pclass_iterator)->is_dynamic) {
                    tb_pnodelist::list_iter pnode_iterator =
                        ptype_iterator->second->L.begin();
                    while (pnode_iterator != ptype_iterator->second->L.end()) {
                        /*
                         * Get the slotcount for this ptype
                         */
                        tb_pnode::types_map::iterator tm_iterator;
                        tm_iterator = (*pnode_iterator)->types.find(this_type);
                        assert(tm_iterator != (*pnode_iterator)->types.end());

                        /*
                         * Remove it from the current ptype
                         */
                        this_type_p->remove_slots(
                                tm_iterator->second->get_max_load());

                        /*
                         * Move on to the next node
                         */
                        pnode_iterator++;
                    }
397 398 399 400
                }
                ptype_iterator++;
            }

Robert Ricci's avatar
Robert Ricci committed
401 402 403 404 405 406
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
407

Robert Ricci's avatar
Robert Ricci committed
408 409 410 411 412 413 414 415 416 417
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

418
void print_help() {
419 420
  cout << "assign [options] ptopfile topfile [config params]" << endl;
  cout << "Options: " << endl;
421
#ifdef TIME_TERMINATE
422
  cout << "  -l <time>   - Limit runtime." << endl;
Mac Newbold's avatar
Mac Newbold committed
423
#endif
424
  cout << "  -s <seed>   - Set the seed." << endl;
425
#ifdef GRAPHVIZ_SUPPORT
426
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
427
    endl;
428
#endif
429 430 431
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
432
#ifdef PER_VNODE_TT
433
  cout << "  -P          - Prune unusable pclasses." << endl;
434
#endif
435 436 437
  cout << "  -T          - Doing some scoring self-testing." << endl;
  cout << "  -H <float>  - Try <float> times harder." << endl;
  cout << "  -o          - Allow overloaded pnodes to be considered." << endl;
Robert Ricci's avatar
Robert Ricci committed
438 439
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
440 441
  cout << "  -u          - Print a summary of the solution." << endl;
  cout << "  -c <float>  - Use the 'connected' pnode finding algorithm " <<
442 443
      "<float>*100% of the time." << endl;
  cout << "  -n          - Don't anneal - just do the prechecks." << endl;
444 445 446 447 448 449

  cout << "  -x <file>   - Specify a text ptop file" << endl;
#ifdef WITH_XML
  cout << "  -X <file>   - Specify a XML ptop file" << endl;
#endif
  cout << "  -y <file>   - Specify a text top file" << endl;
450
#ifdef WITH_XML
451
  cout << "  -Y <file>   - Specify a XML vtop file" << endl;
452
#endif
453 454 455 456 457
#ifdef WITH_XML
  cout << "  -q <file>   - Specify a rspec ptop file" << endl;
  cout << "  -w <file>   - Specify a rspec vtop file" << endl;
#endif
  cout << "  -F          - Apply additional checking to fixed noded" << endl;
458
  exit(EXIT_FATAL);
459 460 461 462 463
}
 
// Perfrom a pre-cehck to make sure that there are enough free nodes of the
// proper types. Returns 1 if the proper types exist, 0 if they do not.
// TODO - move away from using global variables
464
int type_precheck(int round) {
465
    cout << "Type precheck:" << endl;
466

467
    bool ok = true;
Mac Newbold's avatar
Mac Newbold committed
468

469 470 471 472 473 474 475 476 477 478 479
    /*
     * Tailor our error messages, depending on the round - the first round of
     * the precheck is looking for available pnodes, the second is looking for
     * sutiable nodes (ie. at least one vnode could map to it)
     */
    char *round_str;
    if (round == 1) {
        round_str = "available";
    } else {
        round_str = "suitable";
    }
480
    // First, check the regular types
481 482
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
483

484
	// Check to see if there were any pnodes of the type at all
485
	tb_ptype_map::iterator ptype_it = ptypes.find(vtype_it->first);
486
	if (ptype_it == ptypes.end()) {
487
	    cout << "  *** No " << round_str << " physical nodes of type "
488 489
                << vtype_it->first << " found (" << vtype_it->second
                << " requested)" << endl;
490
	    ok = false;
491
	} else {
492
	    // Okay, there are some - are there enough?
493
	    if (ptype_it->second->pnode_slots() < vtype_it->second) {
494
		cout << "  *** " << vtype_it->second << " nodes of type " <<
495 496 497
                    vtype_it->first << " requested, but only " <<
                    ptype_it->second->pnode_slots() << " " << round_str <<
                    " nodes of type " << vtype_it->first<< " found" << endl;
498 499 500 501 502 503 504 505
		ok = false;
	    }
	    // Okay, there are enough - but are we allowed to use them?
	    if (ptype_it->second->maxusers() &&
		    (ptype_it->second->maxusers() < vtype_it->second)) {
		cout << "  *** " << vtype_it->second << " nodes of type " <<
		    vtype_it->first << " requested, but you are only " <<
		    "allowed to use " << ptype_it->second->maxusers() << endl;
506 507
		ok = false;
	    }
508
	}
509
    }
510 511 512 513

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
514
	bool found_match = false;
515
        // Make sure we actually use this vclass
516
        name_vclass_map::iterator dit = vclass_map.find(vclass_it->first);
517 518 519 520 521 522 523 524 525 526 527
        if (dit == vclass_map.end()) {
            cout << "***: Internal error - unable to find vtype " <<
                vclass_it->first << endl;
            exit(EXIT_FATAL);
        } else {
            if (dit->second->empty()) {
                // Nobody uses it, don't check
                continue;
            }
        }

528
	for (vector<fstring>::iterator vtype_it = vclass_it->second.begin();
529
		vtype_it != vclass_it->second.end(); vtype_it++) {
530 531
	    tb_ptype_map::iterator mit = ptypes.find(*vtype_it);
	    if ((mit != ptypes.end()) && (mit->second->pnode_slots() != 0)) {
532 533 534 535 536 537
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
538 539
	    cout << "  *** No " << round_str <<
                " physical nodes can satisfy vclass " << vclass_it->first << endl;
540 541 542 543
	    ok = false;
	}
    }

544
    if (ok) {
545
      cout << "Type precheck passed." << endl;
546 547
      return 1;
    } else {
548
      cout << "*** Type precheck failed!" << endl;
549 550 551
      return 0;
    }
}
552

553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568
// Perfrom a pre-cehck to make sure that every vnode has at least one possible
// mapping.  Returns 1 if this is the case, 0 if not.
// TODO - move away from using global variables
int mapping_precheck() {
#ifdef PER_VNODE_TT
    cout << "Node mapping precheck:" << endl;
    /*
     * Build up an entry in the type table for each vnode, by first looking at
     * the type table entry for the vnode's type, then checking each entry to
     * make sure that it:
     * (1) Has enough interfaces
     * (2) Has enough total bandwidth (for emulated links)
     * (3) Meets any 1.0-weight features and/or desires
     */
    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
569

570 571 572 573
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
574

575 576
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
577

578 579 580 581 582 583 584 585
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

	// This constitutes a list of the number of ptypes that matched the
	// criteria. We use to guess what's wrong with the vnode.
	int matched_bw = 0;
	// Keep track of desires had how many 'hits', so that we can tell
	// if any simply were not matched
586
	map<fstring,int> matched_desires;
587

588 589 590
	// Keep track of which link types had how many 'hits', so that we can
	// tell which type(s) caused this node to fail
	tb_vnode::link_counts_map matched_link_counts;
591 592
        hash_map<fstring,int> max_links;
        hash_map<fstring,int> desired_links;
593
	map<fstring,bool> matched_links;
594

595
	tb_vclass *vclass = v->vclass;
596
	tb_vclass::members_map::const_iterator mit;
597
	if (vclass) {
598
	    mit = vclass->get_members().begin();
599
	}
600 601 602
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
603
	    fstring this_type;
604 605 606 607 608
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
609

610 611 612 613 614 615 616 617
            // Check to make sure there are actually nodes of this type in the
            // physical topology
            if (type_table.find(this_type) == type_table.end()) {
                // Yes, I know, goto is evil. But I'm not gonna indent the next
                // 100 lines of code for this error case
                goto nosuchtype;
            }

618 619
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
620

621 622
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
623
	 	tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
624 625 626

		// Check to see if any of the link that this pnode has are of
		// the correct type for the virtual node
Mac Newbold's avatar
Mac Newbold committed
627

628 629 630 631
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
632
			potential_match = false;
633
		}
Mac Newbold's avatar
Mac Newbold committed
634

635 636
		// Check to see if if the pnode has enough slots of the
		// appropriate type available
637 638 639
		tb_pnode::types_map::iterator type_iterator =
		    pnode->types.find(v->type);
		if (type_iterator == pnode->types.end()) {
640 641
		    // Must have been a vtype to get here - ignore it
		} else {
642
		    if (v->typecount > type_iterator->second->get_max_load()) {
643 644 645 646 647
			// Nope, this vnode is too demanding
			potential_match = false;
		    }
		}

648 649 650 651 652 653 654
		/*
		 * Check features and desires
		*/
		tb_featuredesire_set_iterator
		    fdit(v->desires.begin(),v->desires.end(),
			 pnode->features.begin(),pnode->features.end());
		for (;!fdit.done();fdit++) {
655
		    // Skip 'local' and 'global' features
656
		    if (fdit->is_global() || fdit->is_local()) {
657 658
			continue;
		    }
659 660 661
		    // Only check for FDs that would result in a violation if
		    // unmatched.
		    if (fdit.either_violateable()) {
662 663 664 665 666
			if (fdit.membership() !=
				tb_featuredesire_set_iterator::BOTH) {
			    potential_match = false;
			}

667 668
			// We look for violateable desires on vnodes so that we
			// can report them to the user
669 670 671 672 673 674 675 676 677
			if ((fdit.membership() ==
				tb_featuredesire_set_iterator::FIRST_ONLY ||
			    fdit.membership() ==
				 tb_featuredesire_set_iterator::BOTH)
				&& fdit.first_iterator()->is_violateable()) {
			    if (matched_desires.find(fdit->name()) ==
				    matched_desires.end()) {
				matched_desires[fdit->name()] = 0;
			    }
678 679 680 681
			}
			if (fdit.membership() ==
				tb_featuredesire_set_iterator::BOTH) {
			    matched_desires[fdit->name()]++;
682 683 684
			}
		    }
		}
685
		
686 687 688 689 690 691
		// Check link types - right now, we treat LANs specially, which
                // I am not happy about, but it seems to be necessary.
                // Otherwise, we can get a false negative when there are few
                // ports on a switch available, but we could map by using
                // the trunk links
                if (this_type != "lan") {
692 693 694 695 696 697
                  tb_vnode::link_counts_map::iterator link_it;
                  for (link_it = v->link_counts.begin();
		       link_it != v->link_counts.end();
                       link_it++) {
                    fstring type = link_it->first;
                    int count = link_it->second;
698
                    desired_links[type] = count;
699 700 701 702
                    if (pnode->link_counts.find(type) !=
                          pnode->link_counts.end()) {
                      // Found at least one link of this type
                      matched_links[type] = true;
703 704 705
                      if (pnode->link_counts[type] > max_links[type]) {
                        max_links[type] = pnode->link_counts[type];
                      }
706 707 708 709 710 711 712 713 714 715 716
                      if (pnode->link_counts[type] >= count) {
                        // Great, there are enough, too
                        matched_link_counts[type]++;
                      } else {
                        potential_match = false;
                      }
                    } else {
                      potential_match = false;
                    }
                  }
                }
Mac Newbold's avatar
Mac Newbold committed
717

718 719 720 721 722 723
		if (potential_match) {
		    vec->push_back(*it);
		    vnode_type_table[v->name].first++;
		    (*it)->refcount++;
#ifdef PCLASS_DEBUG
		    cerr << v->name << " can map to " << (*it)->name << endl;
724
#endif
725 726
		}
	    }
727

728
nosuchtype:
729 730
	    if (vclass) { 
		mit++;
731
		if (mit == vclass->get_members().end()) {
732 733 734 735 736 737
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
738
	}
739

740
	if (vnode_type_table[v->name].first == 0) {
741
	    cout << "  *** No possible mapping for " << v->name << endl;
742
	    // Make an attempt to figure out why it didn't match
743 744 745 746 747
	    
	    // Check all of its link types
	    tb_vnode::link_counts_map::iterator lit;
	    for (lit = v->link_counts.begin(); lit != v->link_counts.end();
		lit++) {
748
	      fstring type = lit->first;
749
	      if (!matched_links[type]) {
750 751
		cout << "      No links of type " << type << " found! (" <<
                  desired_links[type] << " requested)" << endl;
752 753
	      } else {
		if (!matched_link_counts[type]) {
754 755 756
		  cout << "      Too many links of type " << type << "! (" <<
                    desired_links[type] << " requested, " << max_links[type] <<
                    " found)" << endl;
757 758
		}
	      }
759
	    }
760

761
	    if (!matched_bw) {
762
		cout << "      Too much bandwidth on emulated links!" << endl;
763
	    }
764

765
	    for (map<fstring,int>::iterator dit = matched_desires.begin();
766 767 768
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
769
		    cout << "      No physical nodes have feature " << dit->first
770 771
			<< "!" << endl;
		}
772
	    }
773
	    ok = false;
774
	}
775 776 777
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
778
#endif
779

780
    }
781

782 783 784
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
785
    } else {
786
	cout << "*** Node mapping precheck failed!" << endl;
787
	return 0;
788 789
    }

790 791 792
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
Robert Ricci's avatar
Robert Ricci committed
793
#endif
794
}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
795

796 797 798 799 800 801 802 803 804 805 806 807 808 809
// Perfrom a pre-cehck to make sure that polices that are checkable at precheck
// time are not violated. Returns 1 if everything is A-OK, 0 otherwise
// TODO - move away from using global variables
int policy_precheck() {
  cout << "Policy precheck:" << endl;
  if (tb_featuredesire::check_desire_policies()) {
    cout << "Policy precheck succeeded" << endl;
    return 1;
  } else {
    cout << "*** Policy precheck failed!" << endl;
    return 0;
  }
}  

810 811 812
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
813
  cout << "*** Killed with signal " << signal << " - exiting!" << endl;
814 815 816 817 818 819 820 821 822
  _exit(EXIT_UNRETRYABLE);
}

// Singal handler - add a way for a user to get some status information
extern double temp;
void status_report(int signal) {
  cout << "I: " << iters << " T: " << temp << " S: " << get_score() << " V: "
    << violated << " (Best S: " << absbest << " V:" << absbestviolated << ")"
    << endl;
823
  cout.flush();
824 825
}

826 827 828 829
// From anneal.cc - the best solution found
extern solution best_solution;

int main(int argc,char **argv) {
830
  int seed = 0;
831
#ifdef GRAPHVIZ_SUPPORT
832
  fstring viz_prefix;
833
#endif
834
  bool scoring_selftest = false;
835
  bool prechecks_only = false;
836 837 838 839 840
  
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
841 842 843 844 845
  
  char* ptopFilename = "";
  char* vtopFilename = "";
  
  while ((ch = getopt(argc,argv,"s:v:l:t:rpPTdH:oguc:nx:X:y:Y:q:w:F")) != -1) {
846 847 848
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
849
		print_help();
850
      }
851
      break;
852
#ifdef GRAPHVIZ_SUPPORT
853 854 855
    case 'v':
      viz_prefix = optarg;
      break;
856
#endif
857 858 859 860 861 862 863 864 865 866 867 868 869
#ifdef TIME_TERMINATE
    case 'l':
      if (sscanf(optarg,"%lf",&timelimit) != 1) {
	print_help();
      }
      break;
#endif
#ifdef TIME_TARGET
    case 't':
      if (sscanf(optarg,"%lf",&timetarget) != 1) {
	print_help();
      }
      break;
870
#endif
871 872 873
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
874
      disable_pclasses = true; break;
Robert Ricci's avatar
Robert Ricci committed
875 876 877 878
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
879 880
    case 'T':
      scoring_selftest = true; break;
881 882
    case 'd':
      dynamic_pclasses = true; break;
883 884 885 886 887
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
888 889
    case 'o':
      allow_overload = true; break;
Robert Ricci's avatar
Robert Ricci committed
890 891
    case 'g':
      greedy_link_assignment = true; break;
Robert Ricci's avatar
Robert Ricci committed
892 893 894 895 896
    case 't':
      if (sscanf(optarg,"%lf",&initial_temperature) != 1) {
	print_help();
      }
      no_melting = true; break;
897 898 899 900 901 902 903
    case 'u':
      print_summary = true; break;
    case 'c':
      if (sscanf(optarg,"%lf",&use_connected_pnode_find) != 1) {
	print_help();
      }
      break;
904 905 906 907
    case 'n':
      prechecks_only = true;
      cout << "Doing only prechecks, exiting early" << endl;
      break;
908
    case 'x':
909 910 911 912 913 914 915
#ifdef WITH_XML
      ptop_xml_input = false;
#endif
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
916
      break;
917 918 919 920 921 922 923 924 925 926 927 928
#ifdef WITH_XML      
    case 'X':
      ptop_xml_input = true;
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
    break;
#endif
    case 'y':
#ifdef WITH_XML
      vtop_xml_input = false;
929
#endif
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  vtopFilename = optarg;
    break;
#ifdef WITH_XML
    case 'Y':
      vtop_xml_input = true;
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  vtopFilename = optarg;
    break;
#endif
#ifdef WITH_XML
	case 'q':
	  ptop_rspec_input = true;
	  if (strcmp(optarg, "") == 0) {
	  	print_help();
	  }
	  ptopFilename = optarg;
    break;

	case 'w':
	  vtop_rspec_input = true;
	  if (strcmp(optarg, "") == 0) {
	  	print_help();
	  }
	  vtopFilename = optarg;
    break;
#endif
        case 'F':
          check_fixed_nodes = true;
    break;

965 966
    default:
      print_help();
967
    }
968
  }
969 970 971
  argc -= optind;
  argv += optind;
  
972 973 974 975 976 977 978 979 980 981 982 983
  if (argc == 2)
  {
	  ptopFilename = argv[0];
	  vtopFilename = argv[1];
  }
  
  if (strcmp(ptopFilename, "") == 0)
	  print_help();
  	
  if (strcmp(vtopFilename, "") == 0)
	  print_help();	
  
984 985 986 987 988 989
  if (seed == 0) {
    if (getenv("ASSIGN_SEED") != NULL) {
      sscanf(getenv("ASSIGN_SEED"),"%d",&seed);
    } else {
      seed = time(NULL)+getpid();
    }
990
  }
991

992
#ifdef GRAPHVIZ_SUPPORT
993 994 995
  if (viz_prefix.size() == 0) {
    if (getenv("ASSIGN_GRAPHVIZ") != NULL) {
      viz_prefix = getenv("ASSIGN_GRAPHVIZ");
996
    }
997
  }
998
#endif
Mac Newbold's avatar
Mac Newbold committed
999

1000 1001 1002
//   if (argc == 0) {
//       print_help();
//   }
1003 1004 1005 1006 1007 1008 1009

  // Set up a signal handler for USR1 that exits with an unretryable error
  struct sigaction action;
  action.sa_handler = exit_unretryable;
  sigemptyset(&action.sa_mask);
  action.sa_flags = 0;
  sigaction(SIGUSR1,&action,NULL);
1010
  sigaction(SIGINT,&action,NULL);
1011

1012 1013 1014 1015 1016
  // Set up a signal handler for control+T
  struct sigaction action2;
  action2.sa_handler = status_report;
  sigemptyset(&action2.sa_mask);
  action2.sa_flags = 0;
1017
#ifdef __FreeBSD__
1018
  sigaction(SIGINFO,&action2,NULL);
1019 1020
#endif 
  
1021
  // Convert options to the common.h parameters.
1022
  //parse_options(argv, options, noptions);
1023
#ifdef SCORE_DEBUG
1024
  //dump_options("Configuration options:", options, noptions);
1025 1026 1027 1028 1029 1030 1031 1032 1033
#endif

#ifdef GNUPLOT_OUTPUT
  scoresout = fopen("scores.out","w");
  tempout = fopen("temp.out","w");
  deltaout = fopen("delta.out","w");
#endif

  cout << "seed = " << seed << endl;
1034
  srandom(seed);
1035

1036
  read_physical_topology(ptopFilename);
1037
  calculate_switch_MST();
1038

1039
  read_virtual_topology(vtopFilename);
1040 1041 1042

  // Time while we make pclasses and do the type prechecks
  timestart = used_time();
1043 1044
  
  cout << "Generating physical equivalence classes:";
1045
  generate_pclasses(PG,disable_pclasses,dynamic_pclasses);
1046
  cout << pclasses.size() << endl;
1047

1048 1049 1050
#ifdef PCLASS_DEBUG
  pclass_debug();
#endif
1051