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
  12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_rulebased, surf, "Routing part of surf");
  13
  14 /* Routing model structure */
  15
  16 typedef struct {
  17   s_as_t generic_routing;
  18   int nb_processing_units;
  19   int nb_autonomous_systems;
  20   xbt_dynar_t list_route;
  21   xbt_dynar_t list_ASroute;
  22 } s_AS_rulebased_t, *AS_rulebased_t;
  23
  24 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
  25 typedef struct s_rule_route_extended s_rule_route_extended_t,
  26     *rule_route_extended_t;
  27
  28 struct s_rule_route {
  29   xbt_dynar_t re_str_link;      // dynar of char*
  30   pcre *re_src;
  31   pcre *re_dst;
  32 };
  33
  34 struct s_rule_route_extended {
  35   s_rule_route_t generic_rule_route;
  36   char *re_src_gateway;
  37   char *re_dst_gateway;
  38 };
  39
  40 static void rule_route_free(void *e)
  41 {
  42   rule_route_t *elem = (rule_route_t *) (e);
  43   if (*elem) {
  44     xbt_dynar_free(&(*elem)->re_str_link);
  45     pcre_free((*elem)->re_src);
  46     pcre_free((*elem)->re_dst);
  47     xbt_free(*elem);
  48   }
  49   *elem = NULL;
  50 }
  51
  52 static void rule_route_extended_free(void *e)
  53 {
  54   rule_route_extended_t *elem = (rule_route_extended_t *) e;
  55   if (*elem) {
  56     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
  57     pcre_free((*elem)->generic_rule_route.re_src);
  58     pcre_free((*elem)->generic_rule_route.re_dst);
  59     xbt_free((*elem)->re_src_gateway);
  60     xbt_free((*elem)->re_dst_gateway);
  61     xbt_free(*elem);
  62   }
  63 }
  64
  65 /* Parse routing model functions */
  66
  67 static int model_rulebased_parse_PU(AS_t rc, const char *name)
  68 {
  69   AS_rulebased_t routing = (AS_rulebased_t) rc;
  70   routing->nb_processing_units++;
  71   return -1;
  72 }
  73
  74 static int model_rulebased_parse_AS(AS_t rc, const char *name)
  75 {
  76   AS_rulebased_t routing = (AS_rulebased_t) rc;
  77   routing->nb_autonomous_systems++;
  78   return -1;
  79 }
  80
  81 static void model_rulebased_parse_route(AS_t rc,
  82                                       const char *src, const char *dst,
  83                                       route_t route)
  84 {
  85   AS_rulebased_t routing = (AS_rulebased_t) rc;
  86   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
  87   const char *error;
  88   int erroffset;
  89
  90   if(!strcmp(rc->model_desc->name,"Vivaldi")){
  91           if(!xbt_dynar_is_empty(route->link_list))
  92                   xbt_die("You can't have link_ctn with Model Vivaldi.");
  93   }
  94
  95   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
  96   xbt_assert(ruleroute->re_src,
  97               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
  98               erroffset, src, error);
  99   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
 100   xbt_assert(ruleroute->re_src,
 101               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 102               erroffset, dst, error);
 103
 104   ruleroute->re_str_link = route->link_list;
 105   route->link_list = NULL; // Don't free it twice in each container
 106
 107   xbt_dynar_push(routing->list_route, &ruleroute);
 108 }
 109
 110 static void model_rulebased_parse_ASroute(AS_t rc,
 111                                         const char *src, const char *dst,
 112                                         route_t route)
 113 {
 114   AS_rulebased_t routing = (AS_rulebased_t) rc;
 115   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
 116   const char *error;
 117   int erroffset;
 118
 119   if(!strcmp(rc->model_desc->name,"Vivaldi")){
 120           if(!xbt_dynar_is_empty(route->link_list))
 121                   xbt_die("You can't have link_ctn with Model Vivaldi.");
 122   }
 123
 124   ruleroute_e->generic_rule_route.re_src =
 125       pcre_compile(src, 0, &error, &erroffset, NULL);
 126   xbt_assert(ruleroute_e->generic_rule_route.re_src,
 127               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 128               erroffset, src, error);
 129   ruleroute_e->generic_rule_route.re_dst =
 130       pcre_compile(dst, 0, &error, &erroffset, NULL);
 131   xbt_assert(ruleroute_e->generic_rule_route.re_src,
 132               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
 133               erroffset, dst, error);
 134   ruleroute_e->generic_rule_route.re_str_link =
 135       route->link_list;
 136   ruleroute_e->re_src_gateway = xbt_strdup((char *)route->src_gateway); // DIRTY HACK possible only
 137   ruleroute_e->re_dst_gateway = xbt_strdup((char *)route->dst_gateway); // because of what is in routing_parse_E_ASroute
 138   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
 139
 140   /* make sure that they don't get freed */
 141   route->link_list = NULL;
 142   route->src_gateway = route->dst_gateway = NULL;
 143 }
 144
 145 static void model_rulebased_parse_bypassroute(AS_t rc,
 146                                             const char *src,
 147                                             const char *dst,
 148                                             route_t e_route)
 149 {
 150   xbt_die("bypass routing not supported for Route-Based model");
 151 }
 152
 153 #define BUFFER_SIZE 4096        /* result buffer size */
 154 #define OVECCOUNT 30            /* should be a multiple of 3 */
 155
 156 static char *remplace(char *value, const char **src_list, int src_size,
 157                       const char **dst_list, int dst_size)
 158 {
 159   char result[BUFFER_SIZE];
 160   int i_res = 0;
 161   int i = 0;
 162
 163   while (value[i]) {
 164     if (value[i] == '$') {
 165       i++;                      /* skip the '$' */
 166       if (value[i] < '0' || value[i] > '9')
 167         xbt_die("bad string parameter, no number indication, at offset: "
 168                 "%d (\"%s\")", i, value);
 169
 170       /* solve the number */
 171       int number = value[i++] - '0';
 172       while (value[i] >= '0' && value[i] <= '9')
 173         number = 10 * number + (value[i++] - '0');
 174
 175       /* solve the indication */
 176       const char **param_list;
 177       _XBT_GNUC_UNUSED int param_size;
 178       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
 179         param_list = src_list;
 180         param_size = src_size;
 181       } else if (value[i] == 'd' && value[i + 1] == 's'
 182                  && value[i + 2] == 't') {
 183         param_list = dst_list;
 184         param_size = dst_size;
 185       } else {
 186         xbt_die("bad string parameter, support only \"src\" and \"dst\", "
 187                 "at offset: %d (\"%s\")", i, value);
 188       }
 189       i += 3;
 190
 191       xbt_assert(number < param_size,
 192                  "bad string parameter, not enough length param_size, "
 193                  "at offset: %d (\"%s\") %d %d", i, value, param_size, number);
 194
 195       const char *param = param_list[number];
 196       int j = 0;
 197       while (param[j] && i_res < BUFFER_SIZE)
 198         result[i_res++] = param[j++];
 199     } else {
 200       result[i_res++] = value[i++]; /* next char */
 201     }
 202     if (i_res >= BUFFER_SIZE)
 203       xbt_die("solving string \"%s\", small buffer size (%d)",
 204               value, BUFFER_SIZE);
 205   }
 206   result[i_res++] = '\0';
 207   char *res = xbt_malloc(i_res);
 208   return memcpy(res, result, i_res);
 209 }
 210
 211 static void rulebased_get_route_and_latency(AS_t rc,
 212     network_element_t src, network_element_t dst,
 213                                 route_t res,double*lat);
 214 static xbt_dynar_t rulebased_get_onelink_routes(AS_t rc)
 215 {
 216   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
 217   THROW_UNIMPLEMENTED;
 218 //  //We have already bypass cluster routes with network NS3
 219 //  if(!strcmp(surf_network_model->name,"network NS3"))
 220 //      return ret;
 221 //
 222 //  AS_rulebased_t routing = (AS_rulebased_t)rc;
 223 //
 224 //  xbt_dict_cursor_t c1 = NULL;
 225 //  char *k1, *d1;
 226 //
 227 //  //find router
 228 //  char *router = NULL;
 229 //  xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
 230 //    if (routing_get_network_element_type(k1) == SURF_NETWORK_ELEMENT_ROUTER){
 231 //      router = k1;
 232 //      break;
 233 //    }
 234 //  }
 235 //
 236 //  if (!router)
 237 //    xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
 238 //
 239 //  xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
 240 //    route_t route = xbt_new0(s_route_t,1);
 241 //    route->link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 242 //    rulebased_get_route_and_latency (rc, router, k1, route,NULL);
 243 //
 244 //    int number_of_links = xbt_dynar_length(route->link_list);
 245 //
 246 //    if(number_of_links == 1) {
 247 //              //loopback
 248 //    }
 249 //    else{
 250 //              if (number_of_links != 2) {
 251 //                xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
 252 //              }
 253 //
 254 //              void *link_ptr;
 255 //              xbt_dynar_get_cpy (route->link_list, 1, &link_ptr);
 256 //              onelink_t onelink = xbt_new0 (s_onelink_t, 1);
 257 //              onelink->src = xbt_strdup (k1);
 258 //              onelink->dst = xbt_strdup (router);
 259 //              onelink->link_ptr = link_ptr;
 260 //              xbt_dynar_push (ret, &onelink);
 261 //    }
 262 //  }
 263   return ret;
 264 }
 265
 266 /* Business methods */
 267 static void rulebased_get_route_and_latency(AS_t rc,
 268     network_element_t src, network_element_t dst,
 269                                 route_t route, double *lat)
 270 {
 271   XBT_DEBUG("rulebased_get_route_and_latency from '%s' to '%s'",src->name,dst->name);
 272   xbt_assert(rc && src
 273               && dst,
 274               "Invalid params for \"get_route\" function at AS \"%s\"",
 275               rc->name);
 276
 277   /* set utils vars */
 278   AS_rulebased_t routing = (AS_rulebased_t) rc;
 279
 280   char* src_name = src->name;
 281   char* dst_name = dst->name;
 282
 283   int are_processing_units=0;
 284   xbt_dynar_t rule_list;
 285   if ((src->rc_type == SURF_NETWORK_ELEMENT_HOST || src->rc_type == SURF_NETWORK_ELEMENT_ROUTER)&&
 286       (dst->rc_type == SURF_NETWORK_ELEMENT_HOST || dst->rc_type == SURF_NETWORK_ELEMENT_ROUTER)){
 287     are_processing_units = 1;
 288     rule_list = routing->list_route;
 289   } else if (src->rc_type == SURF_NETWORK_ELEMENT_AS && dst->rc_type == SURF_NETWORK_ELEMENT_AS) {
 290     are_processing_units = 0;
 291     rule_list = routing->list_ASroute;
 292   } else
 293     THROWF(arg_error,0,"No route from '%s' to '%s'",src_name,dst_name);
 294
 295   int rc_src = -1;
 296   int rc_dst = -1;
 297   int src_length = (int) strlen(src_name);
 298   int dst_length = (int) strlen(dst_name);
 299
 300   rule_route_t ruleroute;
 301   unsigned int cpt;
 302   int ovector_src[OVECCOUNT];
 303   int ovector_dst[OVECCOUNT];
 304   const char **list_src = NULL;
 305   const char **list_dst = NULL;
 306   _XBT_GNUC_UNUSED int res;
 307   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
 308     rc_src =
 309         pcre_exec(ruleroute->re_src, NULL, src_name, src_length, 0, 0,
 310                   ovector_src, OVECCOUNT);
 311     if (rc_src >= 0) {
 312       rc_dst =
 313           pcre_exec(ruleroute->re_dst, NULL, dst_name, dst_length, 0, 0,
 314                     ovector_dst, OVECCOUNT);
 315       if (rc_dst >= 0) {
 316         res = pcre_get_substring_list(src_name, ovector_src, rc_src, &list_src);
 317         xbt_assert(!res, "error solving substring list for src \"%s\"", src_name);
 318         res = pcre_get_substring_list(dst_name, ovector_dst, rc_dst, &list_dst);
 319         xbt_assert(!res, "error solving substring list for dst \"%s\"", dst_name);
 320         char *link_name;
 321         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
 322           char *new_link_name =
 323               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
 324           void *link =
 325                           xbt_lib_get_or_null(link_lib, new_link_name, SURF_LINK_LEVEL);
 326           if (link) {
 327             xbt_dynar_push(route->link_list, &link);
 328             if (lat)
 329               *lat += surf_network_model->extension.network.get_link_latency(link);
 330           } else
 331             THROWF(mismatch_error, 0, "Link %s not found", new_link_name);
 332           xbt_free(new_link_name);
 333         }
 334       }
 335     }
 336     if (rc_src >= 0 && rc_dst >= 0)
 337       break;
 338   }
 339
 340   if (rc_src >= 0 && rc_dst >= 0) {
 341     /* matched src and dest, nothing more to do (?) */
 342   } else if (!strcmp(src_name, dst_name) && are_processing_units) {
 343     xbt_dynar_push(route->link_list, &(global_routing->loopback));
 344     if (lat)
 345       *lat += surf_network_model->extension.network.get_link_latency(global_routing->loopback);
 346   } else {
 347     THROWF(arg_error,0,"No route from '%s' to '%s'??",src_name,dst_name);
 348     //xbt_dynar_reset(route->link_list);
 349   }
 350
 351   if (!are_processing_units && !xbt_dynar_is_empty(route->link_list)) {
 352     rule_route_extended_t ruleroute_extended =
 353         (rule_route_extended_t) ruleroute;
 354     char *gw_src_name = remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
 355         list_dst, rc_dst);
 356     route->src_gateway = (network_element_t)xbt_lib_get_or_null(host_lib, gw_src_name, ROUTING_HOST_LEVEL);
 357     route->src_gateway = (network_element_t)xbt_lib_get_or_null(host_lib, gw_src_name, ROUTING_HOST_LEVEL);
 358     if(!route->src_gateway)
 359       route->src_gateway = (network_element_t)xbt_lib_get_or_null(as_router_lib, gw_src_name, ROUTING_ASR_LEVEL);
 360     if(!route->src_gateway)
 361       route->src_gateway = (network_element_t)xbt_lib_get_or_null(as_router_lib, gw_src_name, ROUTING_ASR_LEVEL);
 362
 363     char *gw_dst_name = remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
 364         list_dst, rc_dst);
 365     route->dst_gateway = (network_element_t)xbt_lib_get_or_null(host_lib, gw_dst_name, ROUTING_HOST_LEVEL);
 366     route->dst_gateway = (network_element_t)xbt_lib_get_or_null(host_lib, gw_dst_name, ROUTING_HOST_LEVEL);
 367     if(!route->dst_gateway)
 368       route->dst_gateway = (network_element_t)xbt_lib_get_or_null(as_router_lib, gw_dst_name, ROUTING_ASR_LEVEL);
 369     if(!route->dst_gateway)
 370       route->dst_gateway = (network_element_t)xbt_lib_get_or_null(as_router_lib, gw_dst_name, ROUTING_ASR_LEVEL);
 371   }
 372
 373   if (list_src)
 374     pcre_free_substring_list(list_src);
 375   if (list_dst)
 376     pcre_free_substring_list(list_dst);
 377 }
 378
 379 static route_t rulebased_get_bypass_route(AS_t rc, network_element_t src, network_element_t dst) {
 380   return NULL;
 381 }
 382
 383 static void rulebased_finalize(AS_t rc)
 384 {
 385   AS_rulebased_t routing =
 386       (AS_rulebased_t) rc;
 387   if (routing) {
 388     xbt_dynar_free(&routing->list_route);
 389     xbt_dynar_free(&routing->list_ASroute);
 390     model_generic_finalize(rc);
 391   }
 392 }
 393
 394 /* Creation routing model functions */
 395 AS_t model_rulebased_create(void) {
 396
 397   AS_rulebased_t new_component = (AS_rulebased_t)
 398       model_generic_create_sized(sizeof(s_AS_rulebased_t));
 399
 400   new_component->generic_routing.parse_PU = model_rulebased_parse_PU;
 401   new_component->generic_routing.parse_AS = model_rulebased_parse_AS;
 402   new_component->generic_routing.parse_route = model_rulebased_parse_route;
 403   new_component->generic_routing.parse_ASroute = model_rulebased_parse_ASroute;
 404   new_component->generic_routing.parse_bypassroute = model_rulebased_parse_bypassroute;
 405   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
 406   new_component->generic_routing.get_route_and_latency = rulebased_get_route_and_latency;
 407   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
 408   new_component->generic_routing.finalize = rulebased_finalize;
 409   /* initialization of internal structures */
 410   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
 411   new_component->list_ASroute =
 412       xbt_dynar_new(sizeof(rule_route_extended_t),
 413                     &rule_route_extended_free);
 414
 415   return (AS_t) new_component;
 416 }