assign.cc 38.4 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1
/*
2
 * Copyright (c) 2000-2017 University of Utah and the Flux Group.
3
 *
4
 * {{{EMULAB-LICENSE
5
 *
6
 * This file is part of the Emulab network testbed software.
7
 *
8 9 10 11
 * 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.
12
 *
13 14 15 16
 * 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.
17
 *
18 19
 * 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/>.
20
 *
21
 * }}}
Robert Ricci's avatar
Robert Ricci committed
22 23
 */

24 25 26 27
#include "port.h"

#include <boost/config.hpp>
#include <boost/utility.hpp>
28
#include BOOST_PMAP_HEADER
29 30 31
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
32
#ifdef GRAPHVIZ_SUPPORT
33
#include <boost/graph/graphviz.hpp>
34
#endif
35

36 37
#include <fstream>
#include <iostream>
38
#include <time.h>
39
#include <stdlib.h>
40
#include <math.h>
41 42
#include <sys/types.h>
#include <sys/time.h>
43
#include <sys/resource.h>
44 45
#include <signal.h>
#include <sys/signal.h>
46
#include <queue>
47
#include <algorithm>
48 49

using namespace boost;
50

51 52
#include <stdio.h>

53
#include "common.h"
54
#include "delay.h"
55
#include "physical.h"
56
#include "virtual.h"
57
#include "vclass.h"
58
#include "pclass.h"
59
#include "score.h"
60 61 62
#include "solution.h"
#include "maps.h"
#include "anneal.h"
63 64
#include "config.h"

65 66
#ifdef WITH_XML
#include "parse_ptop_xml.h"
67 68 69
#include "parse_vtop_xml.h"
#include "parse_advertisement_rspec.h"
#include "parse_request_rspec.h"
70
#endif
71 72 73

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
74
tb_pgraph PG;
75 76 77 78 79 80 81 82 83 84
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.
85
name_count_map vtypes;
86
name_list_map vclasses;
87 88

// A list of all pclasses.
89
pclass_list pclasses;
90

91 92
// Map from a pnode* to the the corresponding pvertex.
pnode_pvertex_map pnode2vertex;
93 94 95

// Map of a type to a tt_entry, a vector of pclasses and the size of
// the vector.
96
pclass_types type_table;
97 98 99
#ifdef PER_VNODE_TT
pclass_types vnode_type_table;
#endif
100

101 102 103 104 105
// 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;
106

107
// Same, but for distances
108
switch_dist_map_map switch_dist;
109

110 111
// Time started, finished, and the time limit
double timestart, timeend, timelimit, timetarget;
112

113 114 115
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

116 117 118 119 120
#ifdef GNUPLOT_OUTPUT
FILE *scoresout, *tempout, *deltaout;
#endif
// Whether or not assign is allowed to generate trivial links
bool allow_trivial_links = true;
121

122
// Whether or not assign should use pclasses
123
bool disable_pclasses = false;
124

125 126 127
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
128 129 130

// Whether or not we should use the experimental support for dynamic pclasses
bool dynamic_pclasses = false;
131 132 133

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

Robert Ricci's avatar
Robert Ricci committed
135 136 137
// Whether or not to allow assign to temporarily over-subscribe pnodes
bool randomize_order = false;

Robert Ricci's avatar
Robert Ricci committed
138 139 140
// 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;
141 142 143 144 145

// Forces assign to skip melting, and, instead, use the temperature given as
// the initial temperature
bool no_melting = false;
double initial_temperature = 0.0f;
146 147 148 149 150 151

// 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;
152

153 154 155
// Whether or not to perform all checks on fixed nodes
bool check_fixed_nodes = false;

156 157 158
// If true, dump a bunch of configrution information
bool dump_config = false;

159 160 161 162 163 164 165 166
// If true, turn on some scoring options that attempt to evenly balance vnodes
// across pnodes
bool strategy_balance = false;

// If true, turn on some scoring options that attempt to pack vnodes as tightly
// as possible onto pnodes
bool strategy_pack = false;

167
// Use XML for file input
168 169 170 171 172 173
// 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;
174
#endif
175

176 177 178 179 180 181 182 183 184 185 186 187 188
/*
 * Score and violations for the best score found so far
 * XXX - shouldn't be in this file
 */
double best_score;
int best_violated;

/*
 * Number of iterations executed so far, and how many it took us to find the
 * best solution
 * XXX - shouldn't be in this file
 */
int iters, iters_to_best;
189

190 191 192
// Map of all physical types in use in the system
tb_ptype_map ptypes;

193 194 195
/*
 * Internal functions
 */
196

197
// Return the CPU time (in seconds) used by this process
198
float used_time() {
199 200 201 202 203 204
  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;
}

205 206 207 208 209 210 211 212 213 214 215 216
// 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);
}

217
// Read in the .ptop file
218
void read_physical_topology(char const * filename) {
219 220
  ifstream ptopfile;
  ptopfile.open(filename);
221
  if (!ptopfile.is_open()) {
222
      cout << "*** Unable to open ptop file " << filename << endl;
223
      exit(EXIT_FATAL);
224
  }
225

226
#ifdef WITH_XML
227
  if (ptop_xml_input) {
228
	cout << "Physical Graph: " << parse_ptop_xml(PG,SG,filename) << endl;
229
  }
230 231
  else if (ptop_rspec_input) {
	cout << "Physical Graph: " << parse_advertisement(PG, SG, filename) << endl;
232 233
	}
	else {
234 235 236
      cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
  }
#else
237
	cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;
238
#endif
239 240 241 242

#ifdef DUMP_GRAPH
  {
    cout << "Physical Graph:" << endl;
243

244 245
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
246

247 248 249 250
    for (;vit != vendit;vit++) {
      tb_pnode *p = get(pvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
251

252 253 254 255 256 257 258 259 260
    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;
    }
  }
261
#endif // DUMP_GRAPH
262 263 264 265

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

267 268 269

    svertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(SG);
270

271 272 273 274
    for (;vit != vendit;vit++) {
      tb_switch *p = get(svertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
275

276 277 278 279 280 281 282 283 284
    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;
    }
  }
285
#endif // GRAPH_DEBUG
286

287 288
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
289 290 291 292 293 294 295 296
  pvertex_iterator pvit,pvendit;
  tie(pvit,pvendit) = vertices(PG);
  for (;pvit != pvendit;pvit++) {
    pnode2vertex[get(pvertex_pmap,*pvit)]=*pvit;
  }

}

297 298
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
299
// XXX: Should soon be replaced by calculate_shortest_routes()
300
void calculate_switch_MST() {
301
  cout << "Calculating shortest paths on switch fabric." << endl;
302 303

  // Set up the weight map for Dijkstra's
304 305 306 307 308 309 310 311 312 313
  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);
  }
314

315
  // Let boost do the Disjktra's for us, from each switch
316 317 318 319 320 321 322 323
  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])));
324 325
  }

326 327 328 329 330 331 332 333 334
#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;
    }
  }
335
#endif // GRAPH_DEBUG
336 337
}

338
// Read in the .top file
339
void read_virtual_topology(char const * filename) {
340 341
  ifstream topfile;
  topfile.open(filename);
342
  if (!topfile.is_open()) {
343
      cout << "*** Unable to open top file " << filename << endl;
344
      exit(EXIT_FATAL);
345
  }
346 347

#ifdef WITH_XML
348 349 350 351
  if (vtop_xml_input) {
	cout << "Virtual Graph: " << parse_vtop_xml(VG,filename) << endl;
  }
  else if (vtop_rspec_input){
352
  	  cout << "Virtual Graph: " << parse_request (VG, filename) << endl;
353 354
  }
  else {
355 356 357
      cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
  }
#else
358
	cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;
359
#endif
360 361 362 363

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

365 366 367

    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
368

369 370 371 372
    for (;vit != vendit;vit++) {
      tb_vnode *p = get(vvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
373

374 375 376 377 378 379 380 381
    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;
    }
382
  }
383 384
#endif
}
385 386 387 388 389 390 391 392 393 394
/*
 * 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) {
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412
            /*
             * 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
413 414 415
                 * we will never use this particular node.
                 * Note: We only have to do this for pclasses that are "real",
                 * not dynamic ones.
416
                 */
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
                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++;
                    }
439 440 441 442
                }
                ptype_iterator++;
            }

443 444 445 446 447 448
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
449

450 451 452 453 454 455 456 457 458 459
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

460
void print_help() {
461
  cout << "assign [options] ptopfile topfile [cparams]" << endl;
462
  cout << "Options: " << endl;
463
#ifdef TIME_TERMINATE
464
  cout << "  -l <time>   - Limit runtime." << endl;
465
#endif
466
  cout << "  -s <seed>   - Set the seed." << endl;
467
#ifdef GRAPHVIZ_SUPPORT
468
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
469
    endl;
470
#endif
471 472 473
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
474
#ifdef PER_VNODE_TT
475
  cout << "  -P          - Prune unusable pclasses." << endl;
476
#endif
477 478 479
  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;
480 481
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
482 483
  cout << "  -u           - Print a summary of the solution." << endl;
  cout << "  -c <float>   - Use the 'connected' pnode finding algorithm ";
484 485
  cout <<                   "<float>*100%" << endl;
  cout << "                 of the time." << endl;
486 487 488 489
  cout << "  -n           - Don't anneal - just do the prechecks." << endl;

  cout << "  -x <file>    - Specify a text ptop file" << endl;
  cout << "  -y <file>    - Specify a text top file" << endl;
490
#ifdef WITH_XML
491
  cout << "  -W <file>    - Specify the output rspec file" << endl;
492 493 494
  cout << "  -f <T>[/<T>] - Specify the ptop/vtop file formats " << endl;
  cout << "                 T should be one of (text|xml|rspec)" << endl;
  cout << "                 Specifying only one T is equivalent to -f T/T"<<endl;
495
#endif
496 497
  cout << "  -F          - Apply additional checking to fixed nodes" << endl;
  cout << "  -D          - Dump configuration options" << endl;
Robert Ricci's avatar
Robert Ricci committed
498
  cout << "  -R          - Randomize order of nodes in pclasses" << endl;
499 500
  cout << "  -S <str>    - Set vnode packing strategy. Currently supported" << endl;
  cout << "                values are 'balance' and 'pack'" << endl;
501 502 503
  cout << "  cparams     - You probably don't want to touch these!" << endl;
  cout << "                If you must, see config.h in the source for a list"
       << endl;
504
  exit(EXIT_FATAL);
505
}
506

507 508 509
// 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
510
int type_precheck(int round) {
511
    cout << "Type precheck:" << endl;
512

513
    bool ok = true;
514

515 516 517 518 519
    /*
     * 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)
     */
520
    char const * round_str;
521 522 523 524 525
    if (round == 1) {
        round_str = "available";
    } else {
        round_str = "suitable";
    }
526
    // First, check the regular types
527 528
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
529

530
	// Check to see if there were any pnodes of the type at all
531
	tb_ptype_map::iterator ptype_it = ptypes.find(vtype_it->first);
532
	if (ptype_it == ptypes.end()) {
533
	    cout << "  *** No " << round_str << " physical nodes of type "
534 535
                << vtype_it->first << " found (" << vtype_it->second
                << " requested)" << endl;
536
	    ok = false;
537
	} else {
538
	    // Okay, there are some - are there enough?
539
	    if (ptype_it->second->pnode_slots() < vtype_it->second) {
540
		cout << "  *** " << vtype_it->second << " nodes of type " <<
541 542 543
                    vtype_it->first << " requested, but only " <<
                    ptype_it->second->pnode_slots() << " " << round_str <<
                    " nodes of type " << vtype_it->first<< " found" << endl;
544 545 546
		ok = false;
	    }
	    // Okay, there are enough - but are we allowed to use them?
547
	    if ((ptype_it->second->maxusers() >= 0) &&
548 549 550 551
		    (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;
552 553
		ok = false;
	    }
554
	}
555
    }
556 557 558 559

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
560
	bool found_match = false;
561
        // Make sure we actually use this vclass
562
        name_vclass_map::iterator dit = vclass_map.find(vclass_it->first);
563 564 565 566 567 568 569 570 571 572 573
        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;
            }
        }

574
	for (vector<fstring>::iterator vtype_it = vclass_it->second.begin();
575
		vtype_it != vclass_it->second.end(); vtype_it++) {
576 577
	    tb_ptype_map::iterator mit = ptypes.find(*vtype_it);
	    if ((mit != ptypes.end()) && (mit->second->pnode_slots() != 0)) {
578 579 580 581 582 583
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
584 585
	    cout << "  *** No " << round_str <<
                " physical nodes can satisfy vclass " << vclass_it->first << endl;
586 587 588 589
	    ok = false;
	}
    }

590
    if (ok) {
591
      cout << "Type precheck succeeded" << endl;
592 593
      return 1;
    } else {
594
      cout << "*** Type precheck failed!" << endl;
595 596 597
      return 0;
    }
}
598

599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614
// 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);
615

616 617 618 619
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
620

621 622
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
623

624 625 626
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

627 628 629 630
	// Remember if there are no nodes of the requested type in the physical
	// topology. Without this diagnostic, our "guess what's wrong with
	// the vnode" code concludes that there was not enough bandwidth.
	bool matched_node_type = true;
631 632 633 634 635
	// 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
636
	map<fstring,int> matched_desires;
637

638 639 640
	// 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;
641 642
        hash_map<fstring,int> max_links;
        hash_map<fstring,int> desired_links;
643
	map<fstring,bool> matched_links;
644

645
	tb_vclass *vclass = v->vclass;
646
	tb_vclass::members_map::const_iterator mit;
647
	if (vclass) {
648
	    mit = vclass->get_members().begin();
649
	}
650 651 652
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
653
	    fstring this_type;
654 655 656 657 658
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
659

660 661 662
            // Check to make sure there are actually nodes of this type in the
            // physical topology
            if (type_table.find(this_type) == type_table.end()) {
663
                matched_node_type = false;
664 665 666 667 668
                // Yes, I know, goto is evil. But I'm not gonna indent the next
                // 100 lines of code for this error case
                goto nosuchtype;
            }

669 670
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
671

672 673
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
674
	 	tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
675 676 677

		// Check to see if any of the link that this pnode has are of
		// the correct type for the virtual node
678

679 680 681 682
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
683
			potential_match = false;
684
		}
685

686 687
		// Check to see if if the pnode has enough slots of the
		// appropriate type available
688 689 690
		tb_pnode::types_map::iterator type_iterator =
		    pnode->types.find(v->type);
		if (type_iterator == pnode->types.end()) {
691 692
		    // Must have been a vtype to get here - ignore it
		} else {
693
		    if (v->typecount > type_iterator->second->get_max_load()) {
694 695 696 697 698
			// Nope, this vnode is too demanding
			potential_match = false;
		    }
		}

699 700 701 702 703 704 705
		/*
		 * 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++) {
706
		    // Skip 'local' and 'global' features
707
		    if (fdit->is_global() || fdit->is_local()) {
708 709
			continue;
		    }
710 711 712
		    // Only check for FDs that would result in a violation if
		    // unmatched.
		    if (fdit.either_violateable()) {
713 714 715 716 717
			if (fdit.membership() !=
				tb_featuredesire_set_iterator::BOTH) {
			    potential_match = false;
			}

718 719
			// We look for violateable desires on vnodes so that we
			// can report them to the user
720 721 722 723 724 725 726 727 728
			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;
			    }
729 730 731 732
			}
			if (fdit.membership() ==
				tb_featuredesire_set_iterator::BOTH) {
			    matched_desires[fdit->name()]++;
733 734 735
			}
		    }
		}
736

737 738 739 740 741 742
		// 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") {
743 744 745 746 747 748
                  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;
749
                    desired_links[type] = count;
750 751 752 753
                    if (pnode->link_counts.find(type) !=
                          pnode->link_counts.end()) {
                      // Found at least one link of this type
                      matched_links[type] = true;
754 755 756
                      if (pnode->link_counts[type] > max_links[type]) {
                        max_links[type] = pnode->link_counts[type];
                      }
757 758 759 760 761 762 763 764 765 766 767
                      if (pnode->link_counts[type] >= count) {
                        // Great, there are enough, too
                        matched_link_counts[type]++;
                      } else {
                        potential_match = false;
                      }
                    } else {
                      potential_match = false;
                    }
                  }
                }
768

769 770 771 772 773 774
		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;
775
#endif
776 777
		}
	    }
778

779
nosuchtype:
780
	    if (vclass) {
781
		mit++;
782
		if (mit == vclass->get_members().end()) {
783 784 785 786 787 788
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
789
	}
790

791
	if (vnode_type_table[v->name].first == 0) {
792
	    cout << "  *** No possible mapping for " << v->name << endl;
793
	    // Make an attempt to figure out why it didn't match
794

795 796 797 798
	    // 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++) {
799
	      fstring type = lit->first;
800
	      if (!matched_links[type]) {
801 802
		cout << "      No links of type " << type << " found! (" <<
                  desired_links[type] << " requested)" << endl;
803 804
	      } else {
		if (!matched_link_counts[type]) {
805 806 807
		  cout << "      Too many links of type " << type << "! (" <<
                    desired_links[type] << " requested, " << max_links[type] <<
                    " found)" << endl;
808 809
		}
	      }
810
	    }
811

812 813 814 815
	    if (!matched_node_type) {
		cout << "      No physical nodes of requested type '"
		     << v->type << "'!\n";
	    } else if (!matched_bw) {
816
		cout << "      Too much bandwidth on emulated links!" << endl;
817
	    }
818

819
	    for (map<fstring,int>::iterator dit = matched_desires.begin();
820 821 822
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
823
		    cout << "      No physical nodes have feature " << dit->first
824 825
			<< "!" << endl;
		}
826
	    }
827
	    ok = false;
828
	}
829 830 831
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
832
#endif
833

834
    }
835

836 837 838
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
839
    } else {
840
	cout << "*** Node mapping precheck failed!" << endl;
841
	return 0;
842 843
    }

844 845 846
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
847
#endif
848
}
849

850 851 852 853 854 855 856 857 858 859 860 861
// 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;
  }
862
}
863

864 865 866
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
867
  cout << "*** Killed with signal " << signal << " - exiting!" << endl;
868 869 870 871 872 873 874
  _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: "
875
    << violated << " (Best S: " << best_score << " V:" << best_violated << ")"
876
    << endl;
877
  cout.flush();
878 879
}

880 881 882 883
// From anneal.cc - the best solution found
extern solution best_solution;

int main(int argc,char **argv) {
884
  int seed = 0;
885
#ifdef GRAPHVIZ_SUPPORT
886
  fstring viz_prefix;
887
#endif
888
  bool scoring_selftest = false;
889
  bool prechecks_only = false;
890

891 892 893 894
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
895

896 897
  char const * ptopFilename = "";
  char const * vtopFilename = "";
898 899
  char* vtopOutputFilename = 0;

900 901 902
#ifdef WITH_XML
	char* ptopFileFormat;
	char* vtopFileFormat;
903 904
	char const * delims = "/";
	char const * flags = "s:v:l:t:rpPTdH:oguc:nx:y:W:FDf:RS:";
905
#else
906
	char const * flags = "s:v:l:t:rpPTdH:oguc:nx:y:FDRS:";
907 908
#endif

909
  while ((ch = getopt(argc,argv,flags)) != -1) {
910 911 912
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
913
		print_help();
914
      }
915
      break;
916
#ifdef GRAPHVIZ_SUPPORT
917 918 919
    case 'v':
      viz_prefix = optarg;
      break;
920
#endif
921 922 923 924 925 926 927 928 929 930 931 932 933
#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;
934
#endif
935 936 937
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
938
      disable_pclasses = true; break;
939 940 941 942
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
943 944
    case 'T':
      scoring_selftest = true; break;
945 946
    case 'd':
      dynamic_pclasses = true; break;
947 948 949 950 951
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
952 953
    case 'o':
      allow_overload = true; break;
Robert Ricci's avatar
Robert Ricci committed
954 955
    case 'g':
      greedy_link_assignment = true; break;
956 957 958 959 960
    case 't':
      if (sscanf(optarg,"%lf",&initial_temperature) != 1) {
	print_help();
      }
      no_melting = true; break;
961 962 963 964 965 966 967
    case 'u':
      print_summary = true; break;
    case 'c':
      if (sscanf(optarg,"%lf",&use_connected_pnode_find) != 1) {
	print_help();
      }
      break;
968 969 970 971
    case 'n':
      prechecks_only = true;
      cout << "Doing only prechecks, exiting early" << endl;
      break;
972 973 974
    case 'D':
      dump_config = true;
      break;
975
    case 'x':
976 977 978 979 980 981 982
#ifdef WITH_XML
      ptop_xml_input = false;
#endif
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  ptopFilename = optarg;
983
      break;
984

985
		case 'y':
986 987
#ifdef WITH_XML
      vtop_xml_input = false;
988
#endif
989 990 991 992 993
      if (strcmp(optarg, "") == 0) {
      	print_help();
	  }
	  vtopFilename = optarg;
    break;
994
	  case 'F':
995 996 997 998 999
          check_fixed_nodes = true;
    break;

#ifdef WITH_XML

1000 1001 1002 1003 1004
    case 'W':
    if (strcmp(optarg, "") == 0) {
      print_help();
    }
    vtopOutputFilename = optarg;
1005
    break;
1006

1007 1008 1009 1010
	case 'f':
		if (strcmp(optarg, "") == 0) {
			print_help();
		}
1011

1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
		ptopFileFormat = strtok(optarg, delims);
		vtopFileFormat = strtok(NULL, delims);
		if (strcmp(ptopFileFormat, "text") == 0) {
			ptop_xml_input = false;
		}
		else if (strstr(ptopFileFormat, "rspec") != NULL) {
			ptop_rspec_input = true;
		}
		else if (strstr(ptopFileFormat, "xml") != NULL){
			ptop_xml_input = true;
		}
		else {
			print_help();
		}
1026

1027 1028 1029 1030 1031
		if (vtopFileFormat == NULL)
		{
			vtop_xml_input = ptop_xml_input;
			vtop_rspec_input = ptop_rspec_input;
		}
1032
		else
1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
		{
			if (strcmp(vtopFileFormat, "text") == 0) {
				vtop_xml_input = false;
			}
			else if (strstr(vtopFileFormat, "rspec") != NULL) {
				vtop_rspec_input = true;
			}
			else if (strstr(vtopFileFormat, "xml") != NULL){
				vtop_xml_input = true;
			}
			else {
				print_help();
			}
		}
1047

1048
		break;
1049
#endif
Robert Ricci's avatar
Robert Ricci committed
1050 1051 1052
	case 'R':
	  randomize_order = true;
	  break;
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062

        case 'S':
          if (strcmp(optarg,"balance") == 0) {
              strategy_balance = true;
          } else if (strcmp(optarg,"pack") == 0) {
              strategy_pack = true;
          } else {
              print_help();
          }
          break;
1063

1064
	default:
1065
      print_help();
1066
    }
1067
  }
1068 1069 1070 1071

  // Save argv and argc, and advance past the initial options
  char **oldargv = argv;
  int oldargc = argc;
1072 1073
  argc -= optind;
  argv += optind;
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085

  if (strcmp(ptopFilename, "") == 0 && argc >= 1) {
      ptopFilename = argv[0];
      argc -= 1;
      argv += 1;
  }

  if (strcmp(vtopFilename, "") == 0 && argc >= 1) {
      vtopFilename = argv[0];
      argc -= 1;
      argv += 1;
  }
1086

1087
  if (argc > 0)
1088
  {
1089 1090 1091
      // If there are still more options, they must be from the common.h
      // parameters.
      parse_options(argv, options, noptions);
1092
  }
1093

1094 1095
  if (strcmp(ptopFilename, "") == 0)
	  print_help();
1096

1097
  if (strcmp(vtopFilename, "") == 0)
1098 1099
	  print_help();

1100 1101 1102 1103 1104 1105
  if (seed == 0) {
    if (getenv("ASSIGN_SEED") != NULL) {
      sscanf(getenv("ASSIGN_SEED"),"%d",&seed);
    } else {
      seed = time(NULL)+getpid();
    }
1106
  }
1107

1108
#ifdef GRAPHVIZ_SUPPORT
1109 1110 1111
  if (viz_prefix.size() == 0) {
    if (getenv("ASSIGN_GRAPHVIZ") != NULL) {
      viz_prefix = getenv("ASSIGN_GRAPHVIZ");
1112
    }
1113
  }
1114
#endif
1115

1116 1117 1118
//   if (argc == 0) {
//       print_help();
//   }
1119 1120 1121 1122 1123 1124 1125

  // 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);
1126
  sigaction(SIGINT,&action,NULL);
1127

1128 1129 1130 1131 1132
  // Set up a signal handler for control+T
  struct sigaction action2;
  action2.sa_handler = status_report;
  sigemptyset(&action2.sa_mask);
  action2.sa_flags = 0;
1133
#ifdef __FreeBSD__
1134
  sigaction(SIGINFO,&action2,NULL);
1135 1136
#endif

1137 1138 1139 1140 1141 1142 1143
#ifdef GNUPLOT_OUTPUT
  scoresout = fopen("scores.out","w");
  tempout = fopen("temp.out","w");
  deltaout = fopen("delta.out","w");
#endif

  cout << "seed = " << seed << endl;
1144
  srandom(seed);
1145

1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
  // Print out information about how we were called
  if (dump_config) {
      cout << "Command line:";
      for (int i = 0; i < oldargc; i++) {
          cout << " " << oldargv[i];
      }
      cout << endl;
      dump_options("Config parameters", options, noptions);
  }

1156
  read_physical_topology(ptopFilename);
1157
  calculate_switch_MST();
1158

1159
  read_virtual_topology(vtopFilename);
1160 1161 1162

  // Time while we make pclasses and do the type prechecks
  timestart = used_time();
1163

1164
  cout << "Generating physical equivalence classes:";
Robert Ricci's avatar
Robert Ricci committed
1165
  generate_pclasses(PG,disable_pclasses,dynamic_pclasses,randomize_order);
1166
  cout << pclasses.size() << endl;
1167

1168 1169 1170
#ifdef PCLASS_DEBUG
  pclass_debug();
#endif
1171

1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193
#ifdef NODE_DUMP_DEBUG
  cerr << "========== Physical nodes" << endl;
  pvertex_iterator vit,vendit;
  tie(vit,vendit) = vertices(PG);
  for (;vit != vendit;++vit) {
      pvertex cur = *vit;
      tb_pnode *curP = get(pvertex_pmap,cur);
      cerr << *curP;
  }
  cerr << "========== End physical nodes" << endl;

  cerr << "========== Virtual nodes" << endl;
  vvertex_iterator vvit,vvendit;
  tie(vvit,vvendit) = vertices(VG);
  for (;vvit != vvendit;++vvit) {
      vvertex cur = *vvit;
      tb_vnode *curV = get(vvertex_pmap,cur);
      cerr << *curV;
  }
  cerr << "========== End virtual nodes" << endl;
#endif

1194 1195 1196 1197 1198
  /*
   * There is a reason for the ordering of the prechecks. The mapping precheck
   * basically assumes that the type precheck has already run, so it doesn't
   * have to worry about nodes which cannot map due to type.
   */
1199

1200
  // Run the type precheck
1201
  if (!type_precheck(1)) {
1202
      exit(EXIT_UNRETRYABLE);
1203
  }
1204

1205 1206
  // Run the mapping precheck
  if (!mapping_precheck()) {
1207
      exit(EXIT_UNRETRYABLE);
1208
  }
1209

1210
#ifdef PER_VNODE_TT
1211 1212
  if (prune_pclasses) {
      prune_unusable_pclasses();
1213 1214 1215 1216 1217 1218
      /*
       * Run the type precheck again, this time without the pclasses we just
       * pruned. Yes, it's a bit redundant, but for the reasons stated above,
       * we mave to run the type precheck before the mapping precheck. And,
       * the type precheck is very fast.
       */
1219
      if (!type_precheck(2)) {
1220 1221
          exit(EXIT_UNRETRYABLE);
      }
1222
  }
1223
#endif
1224

1225 1226 1227 1228 1229
  // Run the policy precheck - the idea behind running this last is that some
  // policy violations might become more clear after doing pruning
    if (!policy_precheck()) {
	exit(EXIT_UNRETRYABLE);
    }
1230

1231 1232 1233 1234 1235
  // Bomb out early if we're only doing the prechecks
  if (prechecks_only) {
      exit(EXIT_SUCCESS);
  }

1236
  // Output graphviz if necessary
1237
#ifdef GRAPHVIZ_SUPPORT
1238
  if (viz_prefix.size() != 0) {
1239 1240 1241
    fstring vviz = viz_prefix + "_virtual.viz";
    fstring pviz = viz_prefix + "_physical.viz";
    fstring sviz = viz_prefix + "_switch.viz";
1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252
    ofstream vfile,pfile,sfile;
    vfile.open(vviz.c_str());
    write_graphviz(vfile,VG,vvertex_writer(),vedge_writer(),graph_writer());
    vfile.close();
    pfile.open(pviz.c_str());
    write_graphviz(pfile,PG,pvertex_writer(),pedge_writer(),graph_writer());
    pfile.close();
    sfile.open(sviz.c_str());
    write_graphviz(sfile,SG,svertex_writer(),sedge_writer(),graph_writer());
    sfile.close();
  }
1253
#endif
1254 1255 1256 1257 1258 1259 1260 1261 1262

  // Handle the initial temperature, if one was given - a NULL initial temp.
  // means that we should start with the normal melting procedure
  double *initial_temperature_pointer;
  if (no_melting) {
    initial_temperature_pointer = &initial_temperature;
  } else {
    initial_temperature_pointer = NULL;
  }
1263

1264
  // Note, time is started earlier now, up by where we make pclasses
1265 1266
  anneal(scoring_selftest, check_fixed_nodes, scale_neighborhood,
          initial_temperature_pointer, use_connected_pnode_find);