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