pclass.cc 15 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1
/*
Robert Ricci's avatar
Robert Ricci committed
2
 * Copyright (c) 2000-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/>.
 * 
 * }}}
Robert Ricci's avatar
Robert Ricci committed
22 23
 */

24
static const char rcsid[] = "$Id: pclass.cc,v 1.31 2009-06-15 19:42:26 ricci Exp $";
25

26 27
#include "port.h"

28
#include <stdlib.h>
29 30

#include <queue>
31
#include <list>
32 33 34 35
#include <algorithm>

#include <boost/config.hpp>
#include <boost/utility.hpp>
36
#include BOOST_PMAP_HEADER
37 38 39 40
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;
41 42

#include "common.h"
43
#include "delay.h"
44 45 46 47
#include "physical.h"
#include "virtual.h"
#include "pclass.h"

48 49 50 51 52 53 54 55 56 57

// The purpose of the code in s this file is to generate the physical
// equivalence classes and then maintain them during the simulated
// annealing process.  A function generate_pclasses is provided to
// fill out the pclass structure.  Then two routines pclass_set, and
// pclass_unset are used to maintaing the structure during annealing.

extern pnode_pvertex_map pnode2vertex;

// pclasses - A list of all pclasses.
58
extern pclass_list pclasses;
59

60
// type_table - Maps a type (fstring) to a tt_entry.  A tt_entry
61 62
// consists of an array of pclasses that satisfy that type, and the
// length of the array.
63
extern pclass_types type_table;
64 65 66 67

// returns 1 if a and b are equivalent.  They are equivalent if the
// type and features information match and if there is a one-to-one
// mapping between links that preserves bw, and destination.
68
int pclass_equiv(tb_pgraph &pg, tb_pnode *a,tb_pnode *b)
69
{
70 71 72
#ifdef PCLASS_DEBUG_MORE
  cerr << "pclass_equiv: a=" << a->name << " b=" << b->name << endl;
#endif
73 74 75
  // The unique flag is used to signify that there is some reason that assign
  // is not aware of that the node is unique, and shouldn't be put into a
  // pclass. The usual reason for doing this is for scoring purposes - ie.
76
  // don't prefer one just because it's the same pclass over another that, in
77 78
  // reality, is very different.
  if (a->unique || b->unique) {
79 80 81
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, unique" << endl;
#endif
82 83
      return 0;
  }
84
  
85
  // check type information
86 87
  for (tb_pnode::types_map::iterator it=a->types.begin();
       it!=a->types.end();++it) {
88
    const fstring &a_type = (*it).first;
89
    tb_pnode::type_record *a_type_record = (*it).second;
90 91
    
    tb_pnode::types_map::iterator bit = b->types.find(a_type);
92 93 94 95
    if ((bit == b->types.end()) || ! ( *(*bit).second == *a_type_record) ) {
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, a has type " << a_type << endl;
#endif
96
      return 0;
97
    }
98
  }
99 100 101 102
  // We have to check in both directions, or b might have a type that a does
  // not
  for (tb_pnode::types_map::iterator it=b->types.begin();
       it!=b->types.end();++it) {
103
    const fstring &b_type = (*it).first;
104 105 106
    tb_pnode::type_record *b_type_record = (*it).second;
    
    tb_pnode::types_map::iterator bit = a->types.find(b_type);
107 108 109 110
    if ((bit == a->types.end()) || ! ( *(*bit).second == *b_type_record) ) {
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, b has type " << b_type << endl;
#endif
111
      return 0;
112
    }
113
  }
114

115 116
  // check subnode information
  if (a->subnode_of != b->subnode_of) {
117 118 119
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, parent nodes difer" << endl;
#endif
120 121 122
      return 0;
  }
  if (a->has_subnode || b->has_subnode) {
123 124 125
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, subnodes nodes difer" << endl;
#endif
126 127 128
      return 0;
  }

129
  // check features
130 131 132 133 134 135 136 137
  tb_featuredesire_set_iterator fdit(a->features.begin(),a->features.end(),
	  b->features.begin(),b->features.end());

  while (!fdit.done()) {
      if (fdit.membership() == tb_featuredesire_set_iterator::BOTH) {
	  // Great, we've got a feature that's in both, just make sure that
	  // the two are equivalent (score, etc.)
	  if (!fdit.both_equiv()) {
138 139 140
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, different weights for feature " << fdit->name() << endl;
#endif
141 142 143 144
	      return 0;
	  }
      } else {
	  // Got a feature that's in one but not the other
145 146 147
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, only one has " << fdit->name() << endl;
#endif
148 149 150 151
	  return 0;
      }

      fdit++;
152 153
  }

154
  // Check links
155 156
  pvertex an = pnode2vertex[a];
  pvertex bn = pnode2vertex[b];
157

158 159 160
  // Make a list of all links for node b
  typedef list<pedge> link_list;
  link_list b_links;
161 162

  poedge_iterator eit,eendit;
163
  tie(eit,eendit) = out_edges(bn,pg);
164
  for (;eit != eendit;++eit) {
165
    b_links.push_back(*eit);
166
  }
167 168 169
  
  // Go through all of a's links, trying to find matches on node b. If we find
  // a match, we remove it from the list
170
  tie(eit,eendit) = out_edges(an,pg);
171
  for (;eit != eendit;++eit) {
172
    tb_plink *plink_a = get(pedge_pmap,*eit);
173
    pvertex dest_pv_a = target(*eit,pg);
174
    if (dest_pv_a == a)
175
      dest_pv_a = source(*eit,pg);
176 177 178 179

    link_list::iterator bit;
    for (bit = b_links.begin(); bit != b_links.end(); bit++) {
      tb_plink *plink_b = get(pedge_pmap,*bit);
180
      pvertex dest_pv_b = target(*bit,pg);
181
      if (dest_pv_b == b)
182
	dest_pv_b = source(*bit,pg);
183 184 185 186

      // If links are equivalent, remove this link in b from further
      // consideration, and go to the next link in a
      if ((dest_pv_a == dest_pv_b) && plink_a->is_equiv(*plink_b)) {
187 188 189
#ifdef PCLASS_DEBUG_TONS
        cerr << "    mached link " << plink_a->name << endl;
#endif
190 191 192 193 194 195
	b_links.erase(bit);
	break;
      }
    }
    // If we never found a match, these nodes aren't equivalent
    if (bit == b_links.end()) {
196 197 198
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, a has unmached link " << plink_a->name << endl;
#endif
199 200
      return 0;
    }
201
  }
202 203

  // Make sure node b has no extra links
204 205 206 207 208 209 210 211 212
  if (b_links.size() != 0) {
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, b has unmached link " << endl;
#endif
      return 0;
  }
#ifdef PCLASS_DEBUG_MORE
              cerr << "    yes" << endl;
#endif
213 214 215
  return 1;
}

216
/* This function takes a physical graph and generates the set of
217 218 219 220
   equivalence classes of physical nodes.  The globals pclasses (a
   list of all equivalence classes) and type_table (and table of
   physical type to list of classes that can satisfy that type) are
   set by this routine. */
221
int generate_pclasses(tb_pgraph &pg, bool pclass_for_each_pnode,
Robert Ricci's avatar
Robert Ricci committed
222
    bool dynamic_pclasses, bool randomize_order) {
223
  typedef hash_map<tb_pclass*,tb_pnode*,hashptr<tb_pclass*> > pclass_pnode_map;
224
  typedef hash_map<fstring,pclass_list*> name_pclass_list_map;
225 226 227 228 229

  pvertex cur;
  pclass_pnode_map canonical_members;

  pvertex_iterator vit,vendit;
230
  tie(vit,vendit) = vertices(pg);
Robert Ricci's avatar
Robert Ricci committed
231 232 233 234 235 236 237 238

  /*
   * Create a vector that we'll use for iterating through the nodes - it's
   * a seperate structure so that we can randomize the order if desired.
   * Argh, can't use STL copy since pg is not an STL structure
   */
  typedef vector<pvertex> pvertex_vector;
  pvertex_vector pvertexes;
239
  for (;vit != vendit;++vit) {
Robert Ricci's avatar
Robert Ricci committed
240 241 242 243 244 245 246 247 248 249
      pvertexes.push_back(*vit);
  }

  if (randomize_order) {
      random_shuffle(pvertexes.begin(), pvertexes.end());
  }

  pvertex_vector::iterator pvit;
  for (pvit = pvertexes.begin();pvit != pvertexes.end();++pvit) {
    cur = *pvit;
250
    bool found_class = 0;
251
    tb_pnode *curP = get(pvertex_pmap,cur);
252 253 254 255 256 257 258 259 260
    tb_pclass *curclass;

    // If we're putting each pnode in its own pclass, don't bother to find
    // existing pclasses that it matches
    if (!pclass_for_each_pnode) {
      pclass_pnode_map::iterator dit;
      for (dit=canonical_members.begin();dit!=canonical_members.end();
	  ++dit) {
	curclass=(*dit).first;
261
	if (pclass_equiv(pg,curP,(*dit).second)) {
262 263
	  // found the right class
	  found_class=1;
264
	  curclass->add_member(curP,false);
265 266 267
	  break;
	} 
      }
268
    }
269

270 271 272 273
    if (found_class == 0) {
      // new class
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
274
      canonical_members[n]=curP;
275
      n->name = curP->name;
276
      n->add_member(curP,false);
277 278 279
    }
  }

280 281 282
  if (dynamic_pclasses) {
    // Make a pclass for each node, which starts out disabled. It will get
    // enabled later when something is assigned to the pnode
283 284 285 286
    pvertex_iterator pvit, pvendit;
    tie(pvit,pvendit) = vertices(pg);
    for (;pvit != pvendit;++pvit) {
      tb_pnode *pnode = get(pvertex_pmap,*pvit);
287 288 289 290 291 292 293 294
      // No point in doing this if the pnode is either: already in a pclass of
      // size one, or can only have a single vnode mapped to it anyway
      if (pnode->my_class->size == 1) {
	  continue;
      }
      bool multiplexed = false;
      tb_pnode::types_map::iterator it = pnode->types.begin();
      for (; it != pnode->types.end(); it++) {
295
	  if ((*it).second->get_max_load() > 1) {
296 297 298 299 300 301 302 303 304 305
	      multiplexed = true;
	      break;
	  }
      }
      if (!multiplexed) {
	  continue;
      }
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
      n->name = pnode->name + "-own";
306
      n->add_member(pnode,true);
307
      n->disabled = true;
308
      n->is_dynamic = true;
309 310 311
    }
  }

312 313
  name_pclass_list_map pre_type_table;

314 315 316
  pclass_list::iterator pit;
  for (pit=pclasses.begin();pit!=pclasses.end();++pit) {
    tb_pclass *pclass = *pit;
317
    tb_pclass::pclass_members_map::iterator dit;
318
    for (dit=pclass->members.begin();dit!=pclass->members.end();
319 320 321
	 ++dit) {
      if (pre_type_table.find((*dit).first) == pre_type_table.end()) {
	pre_type_table[(*dit).first]=new pclass_list;
322
      }
323
      pre_type_table[(*dit).first]->push_back(pclass);
324 325 326 327 328
    }
  }

  // now we convert the lists in pre_type_table into arrays for
  // faster access.
329 330 331 332 333
  name_pclass_list_map::iterator dit;
  for (dit=pre_type_table.begin();dit!=pre_type_table.end();
       ++dit) {
    pclass_list *L = (*dit).second;
    pclass_vector *A = new pclass_vector(L->size());
334 335
    int i=0;
    
336 337 338 339 340
    type_table[(*dit).first]=tt_entry(L->size(),A);

    pclass_list::iterator it;
    for (it=L->begin();it!=L->end();++it) {
      (*A)[i++] = *it;
341
    }
342
    delete L;
343 344 345 346
  }
  return 0;
}

347
int tb_pclass::add_member(tb_pnode *p, bool own_class)
348
{
349 350
  tb_pnode::types_map::iterator it;
  for (it=p->types.begin();it!=p->types.end();++it) {
351
    fstring type = (*it).first;
352 353
    if (members.find(type) == members.end()) {
      members[type]=new tb_pnodelist;
354
    }
355
    members[type]->push_back(p);
356 357
  }
  size++;
358
  if (own_class) {
359 360 361 362
      p->my_own_class=this;
  } else {
      p->my_class=this;
  }
363 364 365
  return 0;
}

366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
// Debugging function to check the invariant that a node is either in its
// dynamic pclass, a 'normal' pclass, but not both
void assert_own_class_invariant(tb_pnode *p) {
  cerr << "class_invariant: " << p->name << endl;
  bool own_class = false;
  bool other_class = false;
  pclass_list::iterator pit = pclasses.begin();
  for (;pit != pclasses.end(); pit++) {
    tb_pclass::pclass_members_map::iterator mit = (*pit)->members.begin();
    for (;mit != (*pit)->members.end(); mit++) {
      if (mit->second->exists(p)) {
	if (*pit == p->my_own_class) {
	  cerr << "In own pclass (" << (*pit)->name << "," << (*pit)->disabled
	    << ")" << endl;
	  if (!(*pit)->disabled) {
	    own_class = true;
	  }
	} else {
	  cerr << "In pclass " << (*pit)->name << " type " << mit->first <<
	    " size " << mit->second->size() << endl;
	  other_class = true;
	}
      }
    }
  }
  if (own_class && other_class) {
    cerr << "Uh oh, in own and other class!" << endl;
    pclass_debug();
    abort();
  }
396 397 398 399 400
  if (!own_class && !other_class) {
    cerr << "In neither class!" << endl;
    pclass_debug();
    abort();
  }
401 402
}

403
// should be called after add_node
404
int pclass_set(tb_vnode *v,tb_pnode *p)
405
{
406
  tb_pclass *c = p->my_class;
407 408
  
  // remove p node from correct lists in equivalence class.
409 410 411
  tb_pclass::pclass_members_map::iterator dit;
  for (dit=c->members.begin();dit!=c->members.end();dit++) {
    if ((*dit).first == p->current_type) {
412
      // same class - only remove if node is full
413 414
      if ((p->current_type_record->get_current_load() ==
	      p->current_type_record->get_max_load()) ||
415
	      p->my_own_class) {
416
	(*dit).second->remove(p);
417 418 419
	if (p->my_own_class) {
	  p->my_own_class->disabled = false;
	}
420 421
      }
    } else {
422
      // XXX - should be made faster
423
      if (!p->types[dit->first]->is_static()) {
424 425 426
	  // If it's not in the list then this fails quietly.
	  (*dit).second->remove(p);
      }
427 428
    }
  }
429

430
  c->used_members++;
431
  
432
  //assert_own_class_invariant(p);
433 434 435
  return 0;
}

436
int pclass_unset(tb_pnode *p)
437
{
438 439 440
  // add pnode back to the list in the equivalence class that corresponds with
  // the current type of the vnode - may be used whether or not the pnode is
  // empty.
441 442 443 444 445
  tb_pclass *c = p->my_class;

  tb_pclass::pclass_members_map::iterator dit;
  for (dit=c->members.begin();dit!=c->members.end();++dit) {
    if ((*dit).first == p->current_type) {
446
      // If it's not in the list then we need to add it to the back if it's
447 448 449
      // empty (so that it will be picked last) and the front if it's not (so 
      // hat it will be picked first). Since unset is called before remove_node
      // is finished decremeting the counts, empty means only one user.
450
      if (! (*dit).second->exists(p)) {
451
	assert(p->current_type_record->get_current_load() > 0);
452
	if (p->current_type_record->get_current_load() == 1) {
453
	  (*dit).second->push_back(p);
454
	} else {
455
	  (*dit).second->push_front(p);
456 457 458 459 460
	}
      }
    }
  }

461
  if (p->my_own_class && (p->total_load == 1)) {
462 463
    p->my_own_class->disabled = true;
  }
464

465
  c->used_members--;
466
  
467
  //assert_own_class_invariant(p);
468 469 470
  return 0;
}

471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486
int pclass_reset_maps(tb_pnode *p)
{
  // add pnode to *all* lists in equivalence class - should only be called if
  // the pnode is empty
  tb_pclass *c = p->my_class;

  tb_pclass::pclass_members_map::iterator dit;
  for (dit=c->members.begin();dit!=c->members.end();++dit) {
    if (! (*dit).second->exists(p)) {
      (*dit).second->push_front(p);
    }
  }

  return 0;
}

487 488 489
void pclass_debug()
{
  cout << "PClasses:\n";
490 491 492
  pclass_list::iterator it;
  for (it=pclasses.begin();it != pclasses.end();++it) {
    cout << *(*it);
493 494 495 496
  }

  cout << "\n";
  cout << "Type Table:\n";
497
  pclass_types::iterator dit;
498 499
  extern pclass_types vnode_type_table; // from assign.cc
  for (dit=vnode_type_table.begin();dit!=vnode_type_table.end();++dit) {
500 501 502
    cout << (*dit).first << ":";
    int n = (*dit).second.first;
    pclass_vector &A = *((*dit).second.second);
503
    for (int i = 0; i < n ; ++i) {
504
      cout << " " << A[i]->name;
505 506 507 508 509
    }
    cout << "\n";
  }
}

510 511 512 513 514 515 516 517 518 519 520 521 522
/* Count how many enabled, non-empty, pclasses there currently are. */
int count_enabled_pclasses()
{
  pclass_list::iterator it;
  int count = 0;
  for (it=pclasses.begin();it != pclasses.end();++it) {
      if ((*it)->disabled) { continue; }
      // XXX - skip empty pclasses
      count++;
  }

  return count;
}