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