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