src_frescan/frescan_bwres_analysis.c

   1 /*!
   2  * @file frescan_bwres_analysis.c
   3  *
   4  * @brief FRESCAN bandwith reservation layer: sched analysis
   5  *
   6  * This module contains the scheduling analysis data and functions for the
   7  * admission tests and spare capacity distribution of the negotiation layer.
   8  * It provides an easy API easy to understand and in the implementation part
   9  * it makes call to the general sched analysis module of FRSH which is shared
  10  * with the CPU contracts layer in FRSH.
  11  *
  12  * EXAMPLE of utilization:
  13  *
  14  * INITIALIZATION
  15  * --------------
  16  * params.min_prio = 0;
  17  * params.max_prio = 16;
  18  * params.overhead = ...;
  19  * frescan_sa_init(&scenario, &params);
  20  *
  21  * NEGOTIATE
  22  * ---------
  23  * fadt_freelist_alloc(&freelist_contracts, &id);
  24  * frescan_sa_add_contract(&scenario, &contracts[id], id);
  25  * frescan_sa_sched_test(&scenario, &success);
  26  *
  27  * if (!success) {
  28  *      frescan_sa_remove_contract(&scenario, id);
  29  * } else {
  30  *      frescan_sa_spare_capacity(&scenario);
  31  *      vres_id = to_vres(resource_type, resource_id, id);
  32  *      create vres runtime structures;
  33  *
  34  *      for vres_id in active_vres_id {
  35  *                frescan_sa_get_final_values(&scenario,
  36  *                                            to_index(vres_id),
  37  *                                            &final_values);
  38  *                update vres runtime structures if necessary;
  39  *      }
  40  * }
  41  *
  42  * RENEGOTIATE
  43  * -----------
  44  * copy old_contract
  45  * frescan_sa_update_contract(&scenario, to_index(vres_id), &contract);
  46  * frescan_sa_sched_test(&scenario, &success);
  47  *
  48  * if (!success) {
  49  *         frescan_sa_update_contract(&sa_data,
  50  *                                    to_index(vres_id),
  51  *                                    &old_contract);
  52  * } else {
  53  *      frescan_sa_spare_capacity(&scenario);
  54  *      for vres_id in active_vres_id {
  55  *              frescan_sa_get_final_values(&scenario,
  56  *                                          to_index(vres_id),
  57  *                                          &final_values);
  58  *              update vres runtime structures if necessary;
  59  *      }
  60  * }
  61  *
  62  * CANCEL
  63  * ------
  64  * frescan_sa_remove_contract(&scenario, to_index(vres_id));
  65  * frescan_sa_spare_capacity(&scenario);
  66  *
  67  * @version 0.01
  68  *
  69  * @date 15-Apr-2008
  70  *
  71  * @author Daniel Sangorrin <daniel.sangorrin@unican.es>
  72  *
  73  * @license
  74  *
  75  * -----------------------------------------------------------------------
  76  *  Copyright (C) 2006 - 2008 FRESCOR consortium partners:
  77  *
  78  *    Universidad de Cantabria,              SPAIN
  79  *    University of York,                    UK
  80  *    Scuola Superiore Sant'Anna,            ITALY
  81  *    Kaiserslautern University,             GERMANY
  82  *    Univ. Politécnica  Valencia,           SPAIN
  83  *    Czech Technical University in Prague,  CZECH REPUBLIC
  84  *    ENEA                                   SWEDEN
  85  *    Thales Communication S.A.              FRANCE
  86  *    Visual Tools S.A.                      SPAIN
  87  *    Rapita Systems Ltd                     UK
  88  *    Evidence                               ITALY
  89  *
  90  *    See http://www.frescor.org for a link to partners' websites
  91  *
  92  *           FRESCOR project (FP6/2005/IST/5-034026) is funded
  93  *        in part by the European Union Sixth Framework Programme
  94  *        The European Union is not liable of any use that may be
  95  *        made of this code.
  96  *
  97  *  This file is part of FRESCAN
  98  *
  99  *  FRESCAN is free software; you can  redistribute it and/or  modify
 100  *  it under the terms of  the GNU General Public License as published by
 101  *  the Free Software Foundation;  either  version 2, or (at  your option)
 102  *  any later version.
 103  *
 104  *  FRESCAN  is distributed  in  the hope  that  it  will  be useful,  but
 105  *  WITHOUT  ANY  WARRANTY;     without  even the   implied   warranty  of
 106  *  MERCHANTABILITY  or  FITNESS FOR  A  PARTICULAR PURPOSE. See  the  GNU
 107  *  General Public License for more details.
 108  *
 109  *  You should have  received a  copy of  the  GNU  General Public License
 110  *  distributed  with  FRESCAN;  see file COPYING.   If not,  write to the
 111  *  Free Software  Foundation,  59 Temple Place  -  Suite 330,  Boston, MA
 112  *  02111-1307, USA.
 113  *
 114  * As a special exception, including FRESCAN header files in a file,
 115  * instantiating FRESCAN generics or templates, or linking other files
 116  * with FRESCAN objects to produce an executable application, does not
 117  * by itself cause the resulting executable application to be covered
 118  * by the GNU General Public License. This exception does not
 119  * however invalidate any other reasons why the executable file might be
 120  * covered by the GNU Public License.
 121  * -----------------------------------------------------------------------
 122  *
 123  */
 124
 125 #include <math.h>
 126 #include <misc/timespec_operations.h>
 127 #include "frescan_bwres_analysis.h"
 128 #undef ERROR
 129 #include "frescan_debug.h"
 130
 131 /**
 132  * frescan_sa_init() - init the scenario
 133  *
 134  * @scenario: the scenario (in out)
 135  * @params: init params (in)
 136  */
 137
 138 int frescan_sa_init(frescan_sa_scenario_t *scenario,
 139                     const frescan_sa_init_params_t *params)
 140 {
 141 //         int ret;
 142 //
 143 //         ret = frsh_sa_scenario_init(scenario, params);
 144 //         return ret;
 145
 146         INIT_LIST_HEAD(&scenario->contracts_head.list);
 147         scenario->init_params = *params;
 148         return 0;
 149 }
 150
 151 /**
 152  * frescan_sa_add_contract() - add a contract to the scenario
 153  *
 154  * @scenario: the scenario (in out)
 155  * @contract: the new contract (in)
 156  * @ss: the preallocated ss identificator (in)
 157  * @node: the node this contract belongs to (in)
 158  */
 159
 160 int frescan_sa_add_contract(frescan_sa_scenario_t    *scenario,
 161                             const frescan_contract_t *contract,
 162                             frescan_ss_t             ss,
 163                             frescan_node_t           node)
 164 {
 165 //         int ret;
 166 //
 167 //         ret = frsh_sa_scenario_add_vres(scenario, contract, id);
 168 //         return ret;
 169         frescan_sa_contract_t *sa_contract;
 170
 171         sa_contract = &scenario->contracts[node][ss];
 172
 173         sa_contract->contract = *contract;
 174         sa_contract->node     = node;
 175         sa_contract->ss       = ss;
 176
 177         list_add_tail(&sa_contract->list,
 178                       &scenario->contracts_head.list);
 179
 180         return 0;
 181 }
 182
 183 /**
 184  * frescan_sa_update_contract() - update a contract in the scenario
 185  *
 186  * @scenario: the scenario (in out)
 187  * @ss: the ss identificator (in)
 188  * @node: the node this contract belongs to (in)
 189  * @contract: the values to update the contract (in)
 190  * @old_contract: the values of the previous contract. Can be NULL (out)
 191  */
 192
 193 int frescan_sa_update_contract(frescan_sa_scenario_t   *scenario,
 194                                frescan_ss_t             ss,
 195                                frescan_node_t           node,
 196                                const frescan_contract_t *contract,
 197                                frescan_contract_t       *old_contract)
 198 {
 199 //         int ret;
 200 //
 201 //         ret = frsh_sa_scenario_modify_vres(scenario, id, *contract);
 202 //         return ret;
 203         frescan_sa_contract_t *sa_contract;
 204
 205         sa_contract = &scenario->contracts[node][ss];
 206
 207         if (old_contract != NULL) {
 208                 *old_contract = sa_contract->contract;
 209         }
 210
 211         sa_contract->contract = *contract;
 212
 213         return 0;
 214 }
 215
 216 /**
 217  * frescan_sa_remove_contract() - remove a contract from the scenario
 218  *
 219  * @scenario: the scenario (in out)
 220  * @ss: the ss to remove (in)
 221  * @node: the node this contract belongs to (in)
 222  */
 223
 224 int frescan_sa_remove_contract(frescan_sa_scenario_t *scenario,
 225                                frescan_ss_t          ss,
 226                                frescan_node_t        node)
 227 {
 228 //         int ret;
 229 //
 230 //         ret = frsh_sa_scenario_del_vres(scenario, id);
 231 //         return ret;
 232         frescan_sa_contract_t *sa_contract;
 233
 234         sa_contract = &scenario->contracts[node][ss];
 235         list_del(&sa_contract->list);
 236
 237         return 0;
 238 }
 239
 240 /**
 241  * frescan_sa_sched_test() - perform a scheduling test on the scenario
 242  *
 243  * @scenario: the scenario (in out)
 244  * @success: if the scenario is schedulable or not (out)
 245  */
 246
 247 int frescan_sa_sched_test(frescan_sa_scenario_t *scenario,
 248                           bool *success)
 249 {
 250 //         int ret;
 251 //
 252 //         ret = frsh_sa_scenario_reset_to_min(scenario, NULL, NULL);
 253 //         if (ret != 0) goto error;
 254 //
 255 //         ret = frsh_sa_assign_priorities(scenario, NULL, NULL, NULL, NULL);
 256 //         if (ret != 0) goto error;
 257 //
 258 //         ret = frsh_sa_ceilings_ok(scenario);
 259 //         if (ret != 0) goto error;
 260 //
 261 //         ret = frsh_sa_calculate_blockings(scenario);
 262 //         if (ret != 0) goto error;
 263 //
 264 //         ret = frsh_sa_sched_test(scenario, success);
 265 //         if (ret != 0) goto error;
 266 //
 267 //         return 0;
 268 //
 269 // error:
 270 //         *success = false;
 271 //         return ret;
 272
 273         struct list_head *pos;
 274         frescan_sa_contract_t *sa_contract;
 275         int num_contracts;
 276         double utilization, max_utilization, budget, period;
 277
 278         // WARNING("simplified ub test (no blocks, prio ordered)\n");
 279
 280         utilization = 0.0;
 281         num_contracts = 0;
 282
 283         list_for_each(pos, &scenario->contracts_head.list) {
 284                 sa_contract = list_entry(pos, frescan_sa_contract_t, list);
 285                 sa_contract->final_values.server_prio = sa_contract->contract.prio;
 286
 287                 budget = (double)sa_contract->contract.min_values.budget *
 288                          (double)FRESCAN_FRAME_TX_TIME_US;
 289
 290                 period = timespec_to_double
 291                                 (&sa_contract->contract.min_values.period);
 292
 293                 utilization = utilization + (budget / period);
 294
 295                 num_contracts++;
 296
 297                 DEBUG(FRESCAN_SA_ENABLE_DEBUG,
 298                       "sa_contract, node:%d ss:%d, c:%d t:(%d,%d) p:%d\n",
 299                       sa_contract->node, sa_contract->ss,
 300                       sa_contract->contract.min_values.budget,
 301                       sa_contract->contract.min_values.period.tv_sec,
 302                       sa_contract->contract.min_values.period.tv_nsec,
 303                       sa_contract->contract.prio);
 304         }
 305
 306         max_utilization = num_contracts *
 307                           (pow(2.0, 1.0/(double)num_contracts) - 1);
 308
 309         DEBUG(FRESCAN_SA_ENABLE_DEBUG, "u:%f n:%d u_max:%f %s\n",
 310               utilization, num_contracts, max_utilization,
 311               (utilization < max_utilization) ? "accepted" : "not accepted");
 312
 313         if (utilization < max_utilization) {
 314                 *success = true;
 315         } else {
 316                 *success = false;
 317         }
 318
 319         return 0;
 320 }
 321
 322 /**
 323  * frescan_sa_spare_capacity() - distribute the remaining spare capacity
 324  *
 325  * @scenario: the scenario (in out)
 326  */
 327
 328 int frescan_sa_spare_capacity(frescan_sa_scenario_t *scenario)
 329 {
 330 //         int ret;
 331 //
 332 //         ret = frsh_sa_distribute_spare(scenario,
 333 //                                        NULL, NULL, NULL, NULL, NULL, NULL);
 334 //         return ret;
 335         WARNING("not implemented, returning 0\n");
 336         return 0;
 337 }
 338
 339 /**
 340  * frescan_sa_get_final_values() - get the final values
 341  *
 342  * @scenario: the scenario (in)
 343  * @ss: the ss from which we want the final values (in)
 344  * @node: the node this contract belongs to (in)
 345  * @final_values: the final values (out)
 346  */
 347
 348
 349 int frescan_sa_get_final_values(const frescan_sa_scenario_t *scenario,
 350                                 frescan_ss_t              ss,
 351                                 frescan_node_t            node,
 352                                 frescan_sa_final_values_t *final_values)
 353 {
 354 //         final_values->budget   = scenario->sa_vres_alloc[id].c;
 355 //         final_values->period   = scenario->sa_vres_alloc[id].t;
 356 //         final_values->deadline = scenario->sa_vres_alloc[id].d;
 357 //         final_values->priority = scenario->sa_vres_alloc[id].p;
 358 //         return 0;
 359
 360         *final_values = scenario->contracts[node][ss].final_values;
 361
 362         return 0;
 363 }