src/surf/surf_routing_rulebased.c

   1 /* Copyright (c) 2009, 2010, 2011. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6 #include "surf_routing_private.h"
   7 #include <pcre.h>               /* regular expression library */
   8
   9 /* Global vars */
  10 extern routing_global_t global_routing;
  11 extern routing_component_t current_routing;
  12 extern model_type_t current_routing_model;
  13 extern xbt_dynar_t link_list;
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_rulebased, surf, "Routing part of surf");
  16
  17 /* Routing model structure */
  18
  19 typedef struct {
  20   s_routing_component_t generic_routing;
  21   xbt_dict_t dict_processing_units;
  22   xbt_dict_t dict_autonomous_systems;
  23   xbt_dynar_t list_route;
  24   xbt_dynar_t list_ASroute;
  25 } s_routing_component_rulebased_t, *routing_component_rulebased_t;
  26
  27 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
  28 typedef struct s_rule_route_extended s_rule_route_extended_t,
  29     *rule_route_extended_t;
  30
  31 struct s_rule_route {
  32   xbt_dynar_t re_str_link;      // dynar of char*
  33   pcre *re_src;
  34   pcre *re_dst;
  35 };
  36
  37 struct s_rule_route_extended {
  38   s_rule_route_t generic_rule_route;
  39   char *re_src_gateway;
  40   char *re_dst_gateway;
  41 };
  42
  43 static void rule_route_free(void *e)
  44 {
  45   rule_route_t *elem = (rule_route_t *) (e);
  46   if (*elem) {
  47     xbt_dynar_free(&(*elem)->re_str_link);
  48     pcre_free((*elem)->re_src);
  49     pcre_free((*elem)->re_dst);
  50     xbt_free(*elem);
  51   }
  52   *elem = NULL;
  53 }
  54
  55 static void rule_route_extended_free(void *e)
  56 {
  57   rule_route_extended_t *elem = (rule_route_extended_t *) e;
  58   if (*elem) {
  59     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
  60     pcre_free((*elem)->generic_rule_route.re_src);
  61     pcre_free((*elem)->generic_rule_route.re_dst);
  62     xbt_free((*elem)->re_src_gateway);
  63     xbt_free((*elem)->re_dst_gateway);
  64     xbt_free(*elem);
  65   }
  66 }
  67
  68 /* Parse routing model functions */
  69
  70 static void model_rulebased_set_processing_unit(routing_component_t rc,
  71                                                 const char *name)
  72 {
  73   routing_component_rulebased_t routing =
  74       (routing_component_rulebased_t) rc;
  75   xbt_dict_set(routing->dict_processing_units, name, (void *) (-1), NULL);
  76 }
  77
  78 static void model_rulebased_set_autonomous_system(routing_component_t rc,
  79                                                   const char *name)
  80 {
  81   routing_component_rulebased_t routing =
  82       (routing_component_rulebased_t) rc;
  83   xbt_dict_set(routing->dict_autonomous_systems, name, (void *) (-1),
  84                NULL);
  85 }
  86
  87 static void model_rulebased_set_route(routing_component_t rc,
  88                                       const char *src, const char *dst,
  89                                       name_route_extended_t route)
  90 {
  91   routing_component_rulebased_t routing =
  92       (routing_component_rulebased_t) rc;
  93   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
  94   const char *error;
  95   int erroffset;
  96
  97   if(!strcmp(rc->routing->name,"Vivaldi")){
  98           if(xbt_dynar_length(route->generic_route.link_list) != 0)
  99                   xbt_die("You can't have link_ctn with Model Vivaldi.");
 100   }
 101
 102   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
 103   xbt_assert(ruleroute->re_src,
 104               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 105               erroffset, src, error);
 106   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
 107   xbt_assert(ruleroute->re_src,
 108               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 109               erroffset, dst, error);
 110   ruleroute->re_str_link = route->generic_route.link_list;
 111   xbt_dynar_push(routing->list_route, &ruleroute);
 112   xbt_free(route);
 113 }
 114
 115 static void model_rulebased_set_ASroute(routing_component_t rc,
 116                                         const char *src, const char *dst,
 117                                         name_route_extended_t route)
 118 {
 119   routing_component_rulebased_t routing =
 120       (routing_component_rulebased_t) rc;
 121   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
 122   const char *error;
 123   int erroffset;
 124
 125   if(!strcmp(rc->routing->name,"Vivaldi")){
 126           if(xbt_dynar_length(route->generic_route.link_list) != 0)
 127                   xbt_die("You can't have link_ctn with Model Vivaldi.");
 128   }
 129
 130   ruleroute_e->generic_rule_route.re_src =
 131       pcre_compile(src, 0, &error, &erroffset, NULL);
 132   xbt_assert(ruleroute_e->generic_rule_route.re_src,
 133               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 134               erroffset, src, error);
 135   ruleroute_e->generic_rule_route.re_dst =
 136       pcre_compile(dst, 0, &error, &erroffset, NULL);
 137   xbt_assert(ruleroute_e->generic_rule_route.re_src,
 138               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 139               erroffset, dst, error);
 140   ruleroute_e->generic_rule_route.re_str_link =
 141       route->generic_route.link_list;
 142   ruleroute_e->re_src_gateway = route->src_gateway;
 143   ruleroute_e->re_dst_gateway = route->dst_gateway;
 144   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
 145 //  xbt_free(route->src_gateway);
 146 //  xbt_free(route->dst_gateway);
 147   xbt_free(route);
 148 }
 149
 150 static void model_rulebased_set_bypassroute(routing_component_t rc,
 151                                             const char *src,
 152                                             const char *dst,
 153                                             route_extended_t e_route)
 154 {
 155   xbt_die("bypass routing not supported for Route-Based model");
 156 }
 157
 158 #define BUFFER_SIZE 4096        /* result buffer size */
 159 #define OVECCOUNT 30            /* should be a multiple of 3 */
 160
 161 static char *remplace(char *value, const char **src_list, int src_size,
 162                       const char **dst_list, int dst_size)
 163 {
 164   char result[BUFFER_SIZE];
 165   int i_res = 0;
 166   int i = 0;
 167
 168   while (value[i]) {
 169     if (value[i] == '$') {
 170       i++;                      /* skip the '$' */
 171       if (value[i] < '0' || value[i] > '9')
 172         xbt_die("bad string parameter, no number indication, at offset: "
 173                 "%d (\"%s\")", i, value);
 174
 175       /* solve the number */
 176       int number = value[i++] - '0';
 177       while (value[i] >= '0' && value[i] <= '9')
 178         number = 10 * number + (value[i++] - '0');
 179
 180       /* solve the indication */
 181       const char **param_list;
 182       int param_size;
 183       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
 184         param_list = src_list;
 185         param_size = src_size;
 186       } else if (value[i] == 'd' && value[i + 1] == 's'
 187                  && value[i + 2] == 't') {
 188         param_list = dst_list;
 189         param_size = dst_size;
 190       } else {
 191         xbt_die("bad string parameter, support only \"src\" and \"dst\", "
 192                 "at offset: %d (\"%s\")", i, value);
 193       }
 194       i += 3;
 195
 196       xbt_assert(number < param_size,
 197                  "bad string parameter, not enough length param_size, "
 198                  "at offset: %d (\"%s\") %d %d", i, value, param_size, number);
 199
 200       const char *param = param_list[number];
 201       int j = 0;
 202       while (param[j] && i_res < BUFFER_SIZE)
 203         result[i_res++] = param[j++];
 204     } else {
 205       result[i_res++] = value[i++]; /* next char */
 206     }
 207     if (i_res >= BUFFER_SIZE)
 208       xbt_die("solving string \"%s\", small buffer size (%d)",
 209               value, BUFFER_SIZE);
 210   }
 211   result[i_res++] = '\0';
 212   char *res = xbt_malloc(i_res);
 213   return memcpy(res, result, i_res);
 214 }
 215
 216 static route_extended_t rulebased_get_route(routing_component_t rc,
 217                                             const char *src,
 218                                             const char *dst);
 219 static xbt_dynar_t rulebased_get_onelink_routes(routing_component_t rc)
 220 {
 221   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
 222
 223   //We have already bypass cluster routes with network NS3
 224   if(!strcmp(surf_network_model->name,"network NS3"))
 225         return ret;
 226
 227   routing_component_rulebased_t routing = (routing_component_rulebased_t)rc;
 228
 229   xbt_dict_cursor_t c1 = NULL;
 230   char *k1, *d1;
 231
 232   //find router
 233   char *router = NULL;
 234   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
 235     if (rc->get_network_element_type(k1) == SURF_NETWORK_ELEMENT_ROUTER){
 236       router = k1;
 237     }
 238   }
 239
 240   if (!router){
 241     xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
 242   }
 243
 244   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
 245     route_extended_t route = rulebased_get_route (rc, router, k1);
 246
 247     int number_of_links = xbt_dynar_length(route->generic_route.link_list);
 248
 249     if(number_of_links == 1) {
 250                 //loopback
 251     }
 252     else{
 253                 if (number_of_links != 2) {
 254                   xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
 255                 }
 256
 257                 void *link_ptr;
 258                 xbt_dynar_get_cpy (route->generic_route.link_list, 1, &link_ptr);
 259                 onelink_t onelink = xbt_new0 (s_onelink_t, 1);
 260                 onelink->src = xbt_strdup (k1);
 261                 onelink->dst = xbt_strdup (router);
 262                 onelink->link_ptr = link_ptr;
 263                 xbt_dynar_push (ret, &onelink);
 264     }
 265   }
 266   return ret;
 267 }
 268
 269 /* Business methods */
 270 static route_extended_t rulebased_get_route(routing_component_t rc,
 271                                             const char *src,
 272                                             const char *dst)
 273 {
 274   xbt_assert(rc && src
 275               && dst,
 276               "Invalid params for \"get_route\" function at AS \"%s\"",
 277               rc->name);
 278
 279   /* set utils vars */
 280   routing_component_rulebased_t routing =
 281       (routing_component_rulebased_t) rc;
 282
 283   int are_processing_units=0;
 284   xbt_dynar_t rule_list;
 285   if (xbt_dict_get_or_null(routing->dict_processing_units, src)
 286       && xbt_dict_get_or_null(routing->dict_processing_units, dst)) {
 287     are_processing_units = 1;
 288     rule_list = routing->list_route;
 289   } else if (xbt_dict_get_or_null(routing->dict_autonomous_systems, src)
 290              && xbt_dict_get_or_null(routing->dict_autonomous_systems,
 291                                      dst)) {
 292     are_processing_units = 0;
 293     rule_list = routing->list_ASroute;
 294   } else
 295     xbt_die("Ask for route \"from\"(%s)  or \"to\"(%s) no found in "
 296             "the local table", src, dst);
 297
 298   int rc_src = -1;
 299   int rc_dst = -1;
 300   int src_length = (int) strlen(src);
 301   int dst_length = (int) strlen(dst);
 302
 303   xbt_dynar_t links_list =
 304       xbt_dynar_new(global_routing->size_of_link, NULL);
 305
 306   rule_route_t ruleroute;
 307   unsigned int cpt;
 308   int ovector_src[OVECCOUNT];
 309   int ovector_dst[OVECCOUNT];
 310   const char **list_src = NULL;
 311   const char **list_dst = NULL;
 312   int res;
 313   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
 314     rc_src =
 315         pcre_exec(ruleroute->re_src, NULL, src, src_length, 0, 0,
 316                   ovector_src, OVECCOUNT);
 317     if (rc_src >= 0) {
 318       rc_dst =
 319           pcre_exec(ruleroute->re_dst, NULL, dst, dst_length, 0, 0,
 320                     ovector_dst, OVECCOUNT);
 321       if (rc_dst >= 0) {
 322         res = pcre_get_substring_list(src, ovector_src, rc_src, &list_src);
 323         xbt_assert(!res, "error solving substring list for src \"%s\"", src);
 324         res = pcre_get_substring_list(dst, ovector_dst, rc_dst, &list_dst);
 325         xbt_assert(!res, "error solving substring list for src \"%s\"", dst);
 326         char *link_name;
 327         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
 328           char *new_link_name =
 329               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
 330           void *link =
 331                           xbt_lib_get_or_null(link_lib, new_link_name, SURF_LINK_LEVEL);
 332           if (link)
 333             xbt_dynar_push(links_list, &link);
 334           else
 335             THROWF(mismatch_error, 0, "Link %s not found", new_link_name);
 336           xbt_free(new_link_name);
 337         }
 338       }
 339     }
 340     if (rc_src >= 0 && rc_dst >= 0)
 341       break;
 342   }
 343
 344   route_extended_t new_e_route = NULL;
 345   if (rc_src >= 0 && rc_dst >= 0) {
 346     new_e_route = xbt_new0(s_route_extended_t, 1);
 347     new_e_route->generic_route.link_list = links_list;
 348   } else if (!strcmp(src, dst) && are_processing_units) {
 349     new_e_route = xbt_new0(s_route_extended_t, 1);
 350     xbt_dynar_push(links_list, &(global_routing->loopback));
 351     new_e_route->generic_route.link_list = links_list;
 352   } else {
 353     xbt_dynar_free(&link_list);
 354   }
 355
 356   if (!are_processing_units && new_e_route) {
 357     rule_route_extended_t ruleroute_extended =
 358         (rule_route_extended_t) ruleroute;
 359     new_e_route->src_gateway =
 360         remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
 361                  list_dst, rc_dst);
 362     new_e_route->dst_gateway =
 363         remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
 364                  list_dst, rc_dst);
 365   }
 366
 367   if (list_src)
 368     pcre_free_substring_list(list_src);
 369   if (list_dst)
 370     pcre_free_substring_list(list_dst);
 371
 372   return new_e_route;
 373 }
 374
 375 static route_extended_t rulebased_get_bypass_route(routing_component_t rc,
 376                                                    const char *src,
 377                                                    const char *dst)
 378 {
 379   return NULL;
 380 }
 381
 382 static void rulebased_finalize(routing_component_t rc)
 383 {
 384   routing_component_rulebased_t routing =
 385       (routing_component_rulebased_t) rc;
 386   if (routing) {
 387     xbt_dict_free(&routing->dict_processing_units);
 388     xbt_dict_free(&routing->dict_autonomous_systems);
 389     xbt_dynar_free(&routing->list_route);
 390     xbt_dynar_free(&routing->list_ASroute);
 391     /* Delete structure */
 392     xbt_free(routing);
 393   }
 394 }
 395
 396 /* Creation routing model functions */
 397 void *model_rulebased_create(void)
 398 {
 399   routing_component_rulebased_t new_component =
 400       xbt_new0(s_routing_component_rulebased_t, 1);
 401   new_component->generic_routing.set_processing_unit =
 402       model_rulebased_set_processing_unit;
 403   new_component->generic_routing.set_autonomous_system =
 404       model_rulebased_set_autonomous_system;
 405   new_component->generic_routing.set_route = model_rulebased_set_route;
 406   new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
 407   new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
 408   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
 409   new_component->generic_routing.get_route = rulebased_get_route;
 410   new_component->generic_routing.get_latency = generic_get_link_latency;
 411   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
 412   new_component->generic_routing.finalize = rulebased_finalize;
 413   new_component->generic_routing.get_network_element_type = get_network_element_type;
 414   /* initialization of internal structures */
 415   new_component->dict_processing_units = xbt_dict_new();
 416   new_component->dict_autonomous_systems = xbt_dict_new();
 417   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
 418   new_component->list_ASroute =
 419       xbt_dynar_new(sizeof(rule_route_extended_t),
 420                     &rule_route_extended_free);
 421   return new_component;
 422 }
 423
 424 void model_rulebased_load(void)
 425 {
 426   /* use "surfxml_add_callback" to add a parse function call */
 427 }
 428
 429 void model_rulebased_unload(void)
 430 {
 431   /* use "surfxml_del_callback" to remove a parse function call */
 432 }
 433
 434 void model_rulebased_end(void)
 435 {
 436 }