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