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

#ifndef __FEATUREDESIRE_H
#define __FEATUREDESIRE_H

#include "common.h"

29 30 31 32 33
#include "port.h"
#include "fstring.h"

#include <iostream>
using namespace std;
34

35 36 37 38 39 40 41 42 43 44 45 46 47 48

namespace featuredesire {
    // The weight at which a feature or desire triggers a violations if
    // unstatisfied or unused
    const float FD_VIOLATION_WEIGHT = 1.0;
    
    enum fd_type {
	FD_TYPE_NORMAL,
	FD_TYPE_LOCAL_ADDITIVE,
	FD_TYPE_GLOBAL_ONE_IS_OKAY,
	FD_TYPE_GLOBAL_MORE_THAN_ONE
    };
};

49
/*
50 51 52 53 54 55 56 57
 * This small class is used to describe policies in force regarding features
 * and desires. The idea behind putting this it its own class is that you want
 * to be able to apply baiscally the same policies to features and desires, but
 * treat them seperateley.
 */
class tb_featuredesire_policy {
public:
    tb_featuredesire_policy(): allowable(true), limited_use(false),
58
    max_use(0.0f), min_use(0.0f)  { ; };
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
    /*
     * Functions for maintaining FD policy state. Inline, since they're
     * so simple.
     */
    void allow()                   { allowable = true; };
    void disallow()                { allowable = false; }
    bool is_allowable()            { return this->allowable; };
    void limit_use(double howmuch) { limited_use = true; max_use = howmuch; };
    void unlimit_use()             { limited_use = false; max_use = 0.0f; }
    bool is_limited()              { return limited_use; }
    double get_limit()             { return max_use; }
    
    friend ostream &operator<<(ostream &o, const tb_featuredesire_policy &fdp);
    
private:
    // Indicates whether or not we are allowed to use this feature or
    // desire, and if so, how much of it we are allowed to use. Note that
    // while these limits are global, this is different from using a global
    // FD - it is a policy knob that can be applied in the ptop file
    bool allowable;
    bool limited_use;
    double max_use;
    // Note: min_use not implemented, as it's not clear what the point
    // would be
    double min_use;
};

/*
 * Base class for features and desires.
88 89 90 91 92 93 94 95 96 97 98
 */
class tb_featuredesire {
    public:

	/*
	 * Note: Constructor is below - use get_featuredesire_obj instead
	 */

	~tb_featuredesire() { ; }

	/*
99 100
	 * Get the object for a particular feature/desire - returns NULL if
	 * the feature/desire does not exist.
101
	 */
102
	static tb_featuredesire *get_featuredesire_by_name(const fstring name);
103

104 105 106 107 108 109 110 111 112 113 114 115 116
	/*
	 * Get the object for a particular feature/desire if it already exists,
	 * or creates a new one if it does not. DEPRECATED, use the next version
	 * below.
	 */
	static tb_featuredesire *get_or_create_featuredesire(const fstring name);
        
       /*
	* Get the object for a particular feature/desire if it already exists,
	* or creates a new one if it does not.
        */
        static tb_featuredesire *get_or_create_featuredesire(const fstring name,
					    featuredesire::fd_type type);
117 118 119 120 121 122 123 124 125
	/*
	 * Silly accessor functions
	 */
	inline bool  is_global()        const { return global;          }
	inline bool  is_local()         const { return local;           }
	inline bool  is_l_additive()	const { return l_additive;	}
	inline bool  is_g_one()		const { return g_one_is_okay;	}
	inline bool  is_g_more()	const { return g_more_than_one; }
	inline int   global_use_count() const { return in_use_globally; }
126
	inline fstring name()           const { return my_name;         }
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

	/*
	 * Operators, primarily for use with the STL
	 */
	inline bool operator==(const tb_featuredesire &o) const {
	    return (id == o.id);
	}

	inline bool operator<(const tb_featuredesire &o) const {
	    return (id < o.id);
	}

	friend ostream &operator<<(ostream &o, const tb_featuredesire &fd);

	/*
	 * Functions for maintaining state for global FDs
	 */
	void add_global_user(int howmany = 1);
	void remove_global_user(int howmany = 1);
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
    
	/*
	 * Simple bookkeeping
	 */
	void add_desire_user(double weight);
	int get_desire_users();
	double get_desire_total_weight();
    
	/*
	 * Functions for manipulating the policies for features or desires with
	 * this name.
	 * NOTE: Only desire policies implement for now
	 */
	void disallow_desire();
	void allow_desire();
	void limit_desire(double limit);
	void unlimit_desire();
    
	/*
	 * Check to see if any desires violate policies - this is checkable at
	 * any time (after all desires and policies have been set up), because
	 * it is not dependant on the current mapping. Returns true if
	 * everything is okay, false if not.
	 * Feature policy violations, which are not yet implemented, will be
	 * much harder because of thise.
	 */
	static bool check_desire_policies();
    
174 175 176 177 178 179
    private:
	/*
	 * This is private, so that we can force callers to go through the
	 * static get_featuredesire_obj function which uses the existing desire
	 * if there is one
	 */
180
	explicit tb_featuredesire(fstring _my_name);
181 182 183 184 185 186 187
    
        /*
	 * This version of the constructor takes the type of the FD explicitly,
	 * no mucking around with trying to find "flags" in the name.
	 */
	explicit tb_featuredesire(fstring _my_name,
				  featuredesire::fd_type _fd_type);
188 189 190 191 192

	// Globally unique identifier
	int id;

	// String name of this FD, used for debugging purposes only
193
	fstring my_name;
194 195 196 197 198 199 200 201 202 203

	// Flags
	bool global;          // Whether this FD has global scope
	bool g_one_is_okay;   // If global, we can have one without penalty
	bool g_more_than_one; // If global, more than one doesn't incur
			      // additional penalty
	bool local;           // Whether this FD has local scope
	bool l_additive;      // If a local FD, is additive

	// Counts how many instances of this feature are in use across all
204
	// nodes - for use with global features
205 206
	int in_use_globally;

207
	typedef map<fstring,tb_featuredesire*> name_featuredesire_map;
208
	static name_featuredesire_map featuredesires_by_name;
209 210 211 212 213 214 215 216 217 218 219 220 221 222
    
	/*
	 * Policies for using features and desires with the name. NOTE: Only
	 * feature policies implemented yet, as they are easier to check for.
	 */
	tb_featuredesire_policy feature_policy;
	tb_featuredesire_policy desire_policy;
    
	/*
	 * Some simple bookkeeping stuff, currently only used to enforce
	 * policies.
	 */
	int desire_users;
	double desire_total_weight;
223 224 225 226 227
    
        /*
	 * Used to assign unque IDs to each feature/desire
	 */
        static int highest_id;
228 229 230 231 232 233 234 235
};

/*
 * This class stores information about a particular feature or desire for a
 * particular node, rather than global information about the feature or desire.
 */
class tb_node_featuredesire {
    public:
236 237 238 239
        /*
	 * This version of the constructor takes "legacy" names, with the
	 * special flags at the beginning, and parses them
	 */
240
	tb_node_featuredesire(fstring _name, double _weight);
241

242 243 244 245 246 247 248
	/*
	 * This version of the constructor passes all type information
	 * explicitly, and leaves the name alone
	 */
	tb_node_featuredesire(fstring _name, double _weight,
			      bool _violatable, featuredesire::fd_type _type);
    
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
	~tb_node_featuredesire() { ; }

	/*
	 * Operators, mostly for use with the STL
	 */
	const bool operator==(const tb_node_featuredesire &o) const {
	    // Note: Compares that two FDs are have the same name/ID, but NOT
	    // that they have the same weight - see equivalent() below for that
	    return(*featuredesire_obj == *(o.featuredesire_obj));
	}

	const bool operator<(const tb_node_featuredesire &o) const {
	    return(*featuredesire_obj < *(o.featuredesire_obj));
	}

	// Since we have to use == to compare names, for the STL's sake, this
	// function checks to make sure that the node-specific parts are
	// equivalent too
	const bool equivalent(const tb_node_featuredesire &o) const {
	    return ((*this == o) && (weight == o.weight) &&
		    (violateable == o.violateable));
	}

	/*
	 * Silly accesors
	 */
	inline const bool   is_violateable() const { return violateable; }
	inline const double cost()           const { return weight;      }
	inline const double used()	     const { return used_local_capacity; }

	/*
	 * Proxy functions for the stuff in tb_featuredesire
	 */
282
	const fstring name()      const { return featuredesire_obj->name();      }
283 284 285 286 287
	const bool  is_local()  const { return featuredesire_obj->is_local();  }
	const bool  is_global() const { return featuredesire_obj->is_global(); }
	const bool  is_l_additive() const {
	    return featuredesire_obj->is_l_additive();
	}
288 289 290
	void add_desire_user(double weight) const { 
	    featuredesire_obj->add_desire_user(weight); 
	}
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 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 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375

	score_and_violations add_global_user() const;
	score_and_violations remove_global_user() const;

	/*
	 * Functions for tracking local features/desires
	 */
	score_and_violations add_local(double amount);
	score_and_violations subtract_local(double amount);

    protected:

	double weight;
	bool violateable;
	tb_featuredesire *featuredesire_obj;
	double used_local_capacity;
};

/*
 * Types to hold virtual nodes' sets of desires and physical nodes' sets of
 * features
 */
typedef slist<tb_node_featuredesire> node_feature_set;
typedef slist<tb_node_featuredesire> node_desire_set;
typedef slist<tb_node_featuredesire> node_fd_set;

/*
 * Kind of like an iterator, but not quite - used for going through a virtual
 * node's desires and a physical node's features, and deterimining which are
 * only in one set, and which are in both
 */
class tb_featuredesire_set_iterator {
    public:
	/*
	 * Constructors
	 */
	tb_featuredesire_set_iterator(node_fd_set::iterator _begin1,
		node_fd_set::iterator _end1,
		node_fd_set::iterator _begin2,
		node_fd_set::iterator _end2);

	// Enum for indicating which set(s) an element belongs to
	typedef enum { FIRST_ONLY, SECOND_ONLY, BOTH } set_membership;

	// Return whether or not we've iterated to the end of both sets
	bool done() const;

	// If we have a membership() of BOTH, do they pass the equivalence
	// test?
	bool both_equiv() const;

	// Is either of the two elements violateable?
	bool either_violateable() const;

	// Iterate to the next element of the set
	void operator++(int);

	// Return the member of the set we're currently iterating to
	const tb_node_featuredesire &operator*() const {
	    return *current;
	}
	
	// Return the member of the set we're currently iterating to
	const tb_node_featuredesire *operator->() const {
	    return &*current;
	}

	// Return the set membership of the current element
	const set_membership membership() const {
	    return current_membership;
	}

	// Give out the iterators to the two elements, so that they can be
	// operated upon
	node_fd_set::iterator &first_iterator()  { return it1; }
	node_fd_set::iterator &second_iterator() { return it2; }
	
    private:
	node_fd_set::iterator it1, end1;
	node_fd_set::iterator it2, end2;
	node_fd_set::iterator current;
	set_membership current_membership;
};

#endif