trp/trp_rtable.c

   1 /*
   2  * Copyright (c) 2016, JANET(UK)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * 3. Neither the name of JANET(UK) nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  31  * OF THE POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  */
  34
  35 #include <stdlib.h>
  36
  37 #include <glib.h>
  38 #include <talloc.h>
  39 #include <time.h>
  40
  41 #include <tr_name_internal.h>
  42 #include <trp_route.h>
  43 #include <trp_internal.h>
  44 #include <trp_rtable.h>
  45 #include <tr_debug.h>
  46 #include <trust_router/trp.h>
  47 #include <trust_router/tid.h>
  48
  49
  50 /* result must be freed with g_free */
  51 static gchar *tr_name_to_g_str(const TR_NAME *n)
  52 {
  53   gchar *s=g_strndup(n->buf, n->len);
  54   if (s==NULL)
  55     tr_debug("tr_name_to_g_str: allocation failure.");
  56   return s;
  57 }
  58
  59 /* hash function for TR_NAME keys */
  60 static guint trp_tr_name_hash(gconstpointer key)
  61 {
  62   const TR_NAME *name=(TR_NAME *)key;
  63   gchar *s=tr_name_to_g_str(name);
  64   guint hash=g_str_hash(s);
  65   g_free(s);
  66   return hash;
  67 }
  68
  69 /* hash equality function for TR_NAME keys */
  70 static gboolean trp_tr_name_equal(gconstpointer key1, gconstpointer key2)
  71 {
  72   const TR_NAME *n1=(TR_NAME *)key1;
  73   const TR_NAME *n2=(TR_NAME *)key2;
  74   gchar *s1=tr_name_to_g_str(n1);
  75   gchar *s2=tr_name_to_g_str(n2);
  76   gboolean equal=g_str_equal(s1, s2);
  77   g_free(s1);
  78   g_free(s2);
  79   return equal;
  80 }
  81
  82 /* free a value to the top level rtable (a hash of all entries in the comm) */
  83 static void trp_rtable_destroy_table(gpointer data)
  84 {
  85   g_hash_table_destroy(data);
  86 }
  87
  88 static void trp_rtable_destroy_rentry(gpointer data)
  89 {
  90   trp_route_free(data);
  91 }
  92
  93 static void trp_rtable_destroy_tr_name(gpointer data)
  94 {
  95   tr_free_name(data);
  96 }
  97
  98 TRP_RTABLE *trp_rtable_new(void)
  99 {
 100   GHashTable *new=g_hash_table_new_full(trp_tr_name_hash,
 101                                         trp_tr_name_equal,
 102                                         trp_rtable_destroy_tr_name,
 103                                         trp_rtable_destroy_table);
 104   return new;
 105 }
 106
 107 void trp_rtable_free(TRP_RTABLE *rtbl)
 108 {
 109   g_hash_table_destroy(rtbl);
 110 }
 111
 112 static GHashTable *trp_rtbl_get_or_add_table(GHashTable *tbl, TR_NAME *key, GDestroyNotify destroy)
 113 {
 114   GHashTable *val_tbl=NULL;
 115
 116   val_tbl=g_hash_table_lookup(tbl, key);
 117   if (val_tbl==NULL) {
 118     val_tbl=g_hash_table_new_full(trp_tr_name_hash,
 119                                   trp_tr_name_equal,
 120                                   trp_rtable_destroy_tr_name,
 121                                   destroy);
 122     g_hash_table_insert(tbl, tr_dup_name(key), val_tbl);
 123   }
 124   return val_tbl;
 125 }
 126
 127 void trp_rtable_add(TRP_RTABLE *rtbl, TRP_ROUTE *entry)
 128 {
 129   GHashTable *comm_tbl=NULL;
 130   GHashTable *realm_tbl=NULL;
 131
 132   comm_tbl=trp_rtbl_get_or_add_table(rtbl, entry->comm, trp_rtable_destroy_table);
 133   realm_tbl=trp_rtbl_get_or_add_table(comm_tbl, entry->realm, trp_rtable_destroy_rentry);
 134   g_hash_table_insert(realm_tbl, tr_dup_name(entry->peer), entry); /* destroys and replaces a duplicate */
 135   /* the route entry should not belong to any context, we will manage it ourselves */
 136   talloc_steal(NULL, entry);
 137 }
 138
 139 /* note: the entry pointer passed in is invalid after calling this because the entry is freed */
 140 void trp_rtable_remove(TRP_RTABLE *rtbl, TRP_ROUTE *entry)
 141 {
 142   GHashTable *comm_tbl=NULL;
 143   GHashTable *realm_tbl=NULL;
 144
 145   comm_tbl=g_hash_table_lookup(rtbl, entry->comm);
 146   if (comm_tbl==NULL)
 147     return;
 148
 149   realm_tbl=g_hash_table_lookup(comm_tbl, entry->realm);
 150   if (realm_tbl==NULL)
 151     return;
 152
 153   /* remove the element */
 154   g_hash_table_remove(realm_tbl, entry->peer);
 155   /* if that was the last entry in the realm, remove the realm table */
 156   if (g_hash_table_size(realm_tbl)==0)
 157     g_hash_table_remove(comm_tbl, entry->realm);
 158   /* if that was the last realm in the comm, remove the comm table */
 159   if (g_hash_table_size(comm_tbl)==0)
 160     g_hash_table_remove(rtbl, entry->comm);
 161 }
 162
 163 void trp_rtable_clear(TRP_RTABLE *rtbl)
 164 {
 165   g_hash_table_remove_all(rtbl); /* destructors should do all the cleanup */
 166 }
 167
 168 /* gets the actual hash table, for internal use only */
 169 static GHashTable *trp_rtable_get_comm_table(TRP_RTABLE *rtbl, TR_NAME *comm)
 170 {
 171   return g_hash_table_lookup(rtbl, comm);
 172 }
 173
 174 /* gets the actual hash table, for internal use only */
 175 static GHashTable *trp_rtable_get_realm_table(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm)
 176 {
 177   GHashTable *comm_tbl=trp_rtable_get_comm_table(rtbl, comm);
 178   if (comm_tbl==NULL)
 179     return NULL;
 180   else
 181     return g_hash_table_lookup(comm_tbl, realm);
 182 }
 183
 184 struct table_size_cookie {
 185   TRP_RTABLE *rtbl;
 186   size_t size;
 187 };
 188 static void trp_rtable_size_helper(gpointer key, gpointer value, gpointer user_data)
 189 {
 190   struct table_size_cookie *data=(struct table_size_cookie *)user_data;
 191   data->size += trp_rtable_comm_size(data->rtbl, (TR_NAME *)key);
 192 };
 193 size_t trp_rtable_size(TRP_RTABLE *rtbl)
 194 {
 195   struct table_size_cookie data={rtbl, 0};
 196   g_hash_table_foreach(rtbl, trp_rtable_size_helper, &data);
 197   return data.size;
 198 }
 199
 200 struct table_comm_size_cookie {
 201   TR_NAME *comm;
 202   TRP_RTABLE *rtbl;
 203   size_t size;
 204 };
 205 static void table_comm_size_helper(gpointer key, gpointer value, gpointer user_data)
 206 {
 207   struct table_comm_size_cookie *data=(struct table_comm_size_cookie *)user_data;
 208   data->size += trp_rtable_realm_size(data->rtbl, data->comm, (TR_NAME *)key);
 209 }
 210 size_t trp_rtable_comm_size(TRP_RTABLE *rtbl, TR_NAME *comm)
 211 {
 212   struct table_comm_size_cookie data={comm, rtbl, 0};
 213   GHashTable *comm_tbl=trp_rtable_get_comm_table(rtbl, comm);
 214   if (comm_tbl==NULL)
 215     return 0;;
 216   g_hash_table_foreach(comm_tbl, table_comm_size_helper, &data);
 217   return data.size;
 218 }
 219
 220 size_t trp_rtable_realm_size(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm)
 221 {
 222   GHashTable *realm_tbl=trp_rtable_get_realm_table(rtbl, comm, realm);
 223   if (realm_tbl==NULL)
 224     return 0;
 225   else
 226     return g_hash_table_size(g_hash_table_lookup(
 227                                g_hash_table_lookup(rtbl, comm),
 228                                realm));
 229 }
 230
 231 /* Returns an array of pointers to TRP_ROUTE, length of array in n_out.
 232  * Caller must free the array (in the mem_ctx context), but must
 233  * not free its contents. */
 234 TRP_ROUTE **trp_rtable_get_entries(TALLOC_CTX *mem_ctx, TRP_RTABLE *rtbl, size_t *n_out)
 235 {
 236   TRP_ROUTE **ret=NULL;
 237   TR_NAME **comm=NULL;
 238   size_t n_comm=0;
 239   TRP_ROUTE **comm_entries=NULL;
 240   size_t n_entries=0;
 241   size_t ii_ret=0;
 242
 243   *n_out=trp_rtable_size(rtbl);
 244   if (*n_out==0)
 245     return NULL;
 246
 247   ret=talloc_array(mem_ctx, TRP_ROUTE *, *n_out);
 248   if (ret==NULL) {
 249     tr_crit("trp_rtable_get_entries: unable to allocate return array.");
 250     *n_out=0;
 251     return NULL;
 252   }
 253
 254   ii_ret=0; /* counts output entries */
 255   comm=trp_rtable_get_comms(rtbl, &n_comm);
 256   while(n_comm--) {
 257     comm_entries=trp_rtable_get_comm_entries(rtbl, comm[n_comm], &n_entries);
 258     while (n_entries--)
 259       ret[ii_ret++]=comm_entries[n_entries];
 260     talloc_free(comm_entries);
 261   }
 262   talloc_free(comm);
 263
 264   if (ii_ret!=*n_out) {
 265     tr_crit("trp_rtable_get_entries: found incorrect number of entries.");
 266     talloc_free(ret);
 267     *n_out=0;
 268     return NULL;
 269   }
 270   return ret;
 271 }
 272
 273 /* Returns an array of pointers to TR_NAME, length of array in n_out.
 274  * Caller must free the array (in the talloc NULL context). */
 275 TR_NAME **trp_rtable_get_comms(TRP_RTABLE *rtbl, size_t *n_out)
 276 {
 277   size_t len=g_hash_table_size(rtbl); /* known comms are keys in top level hash table */
 278   size_t ii=0;
 279   GList *comms=NULL;;
 280   GList *p=NULL;
 281   TR_NAME **ret=NULL;
 282
 283   if (len==0) {
 284     *n_out=0;
 285     return NULL;
 286   }
 287
 288   ret=talloc_array(NULL, TR_NAME *, len);
 289   if (ret==NULL) {
 290     tr_crit("trp_rtable_get_comms: unable to allocate return array.");
 291     *n_out=0;
 292     return NULL;
 293   }
 294   comms=g_hash_table_get_keys(rtbl);
 295   for (ii=0,p=comms; p!=NULL; ii++,p=g_list_next(p))
 296     ret[ii]=(TR_NAME *)p->data;
 297
 298   g_list_free(comms);
 299
 300   *n_out=len;
 301   return ret;
 302 }
 303
 304 /* Returns an array of pointers to TR_NAME, length of array in n_out.
 305  * Caller must free the array (in the talloc NULL context). */
 306 TR_NAME **trp_rtable_get_comm_realms(TRP_RTABLE *rtbl, TR_NAME *comm, size_t *n_out)
 307 {
 308   size_t ii=0;
 309   TRP_RTABLE *comm_tbl=g_hash_table_lookup(rtbl, comm);;
 310   GList *entries=NULL;
 311   GList *p=NULL;
 312   TR_NAME **ret=NULL;
 313
 314   if (comm_tbl==NULL) {
 315     *n_out=0;
 316     return NULL;
 317   }
 318   *n_out=g_hash_table_size(comm_tbl); /* set output length */
 319   ret=talloc_array(NULL, TR_NAME *, *n_out);
 320   entries=g_hash_table_get_keys(comm_tbl);
 321   for (ii=0,p=entries; p!=NULL; ii++,p=g_list_next(p))
 322     ret[ii]=(TR_NAME *)p->data;
 323
 324   g_list_free(entries);
 325   return ret;
 326 }
 327
 328 /* Get all entries in an comm. Returns an array of pointers in NULL talloc context.
 329  * Caller must free this list with talloc_free, but must not free the entries in the
 330  * list.. */
 331 TRP_ROUTE **trp_rtable_get_comm_entries(TRP_RTABLE *rtbl, TR_NAME *comm, size_t *n_out)
 332 {
 333   size_t ii=0, jj=0;
 334   TR_NAME **realm=NULL;
 335   size_t n_realms=0;
 336   TRP_ROUTE **realm_entries=NULL;
 337   size_t n_entries=0;
 338   TRP_ROUTE **ret=NULL;
 339   size_t ii_ret=0;
 340
 341   *n_out=trp_rtable_comm_size(rtbl, comm);
 342   if (*n_out==0)
 343     return NULL;
 344
 345   ret=talloc_array(NULL, TRP_ROUTE *, *n_out);
 346   if (ret==NULL) {
 347     tr_crit("trp_rtable_get_comm_entries: could not allocate return array.");
 348     *n_out=0;
 349     return NULL;
 350   }
 351
 352   ii_ret=0; /* counts entries in the output array */
 353   realm=trp_rtable_get_comm_realms(rtbl, comm, &n_realms);
 354   for (ii=0; ii<n_realms; ii++) {
 355     realm_entries=trp_rtable_get_realm_entries(rtbl, comm, realm[ii], &n_entries);
 356     for (jj=0; jj<n_entries; jj++)
 357       ret[ii_ret++]=realm_entries[jj];
 358     talloc_free(realm_entries);
 359   }
 360   talloc_free(realm);
 361
 362   if (ii_ret!=*n_out) {
 363     tr_crit("trp_rtable_get_comm_entries: found incorrect number of entries.");
 364     talloc_free(ret);
 365     *n_out=0;
 366     return NULL;
 367   }
 368
 369   return ret;
 370 }
 371
 372 /* Get all entries in an comm/realm. Returns an array of pointers in NULL talloc context.
 373  * Caller must free this list with talloc_free, but must not free the entries in the
 374  * list.
 375  *
 376  * If *n_out is 0, then no memory is allocated and NULL is returned. */
 377 TRP_ROUTE **trp_rtable_get_realm_entries(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm, size_t *n_out)
 378 {
 379   size_t ii=0;
 380   TRP_ROUTE **ret=NULL;
 381   TR_NAME **peer=NULL;
 382
 383   tr_debug("trp_rtable_get_realm_entries: entered.");
 384   peer=trp_rtable_get_comm_realm_peers(rtbl, comm, realm, n_out);
 385   if ((peer == NULL) || (*n_out == 0)) {
 386     *n_out = 0; /* May be redundant. That's ok, compilers are smart. */
 387     goto cleanup;
 388   }
 389
 390   ret=talloc_array(NULL, TRP_ROUTE *, *n_out);
 391   if (ret==NULL) {
 392     tr_crit("trp_rtable_get_realm_entries: could not allocate return array.");
 393     n_out=0;
 394     goto cleanup;
 395   }
 396   for (ii=0; ii<*n_out; ii++)
 397     ret[ii]=trp_rtable_get_entry(rtbl, comm, realm, peer[ii]);
 398
 399 cleanup:
 400   if (peer)
 401     talloc_free(peer);
 402   return ret;
 403 }
 404
 405 TR_NAME **trp_rtable_get_comm_realm_peers(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm, size_t *n_out)
 406 {
 407   TR_NAME **ret=NULL;
 408   GHashTable *realm_tbl=NULL;
 409   GList *keys=NULL;
 410   GList *p=NULL;
 411   size_t ii=0;
 412
 413   *n_out=trp_rtable_realm_size(rtbl, comm, realm);
 414   if (*n_out==0)
 415     return NULL;
 416   realm_tbl=trp_rtable_get_realm_table(rtbl, comm, realm);
 417   ret=talloc_array(NULL, TR_NAME *, *n_out);
 418   if (ret==NULL) {
 419     tr_crit("trp_rtable_get_comm_realm_peers: could not allocate return array.");
 420     *n_out=0;
 421     return NULL;
 422   }
 423   keys=g_hash_table_get_keys(realm_tbl);
 424   for (ii=0,p=keys; p!=NULL; ii++,p=g_list_next(p))
 425     ret[ii]=(TR_NAME *)p->data;
 426   g_list_free(keys);
 427   return ret;
 428 }
 429
 430 /* Gets a single entry. Do not free it. */
 431 TRP_ROUTE *trp_rtable_get_entry(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm, TR_NAME *peer)
 432 {
 433   GHashTable *realm_tbl=NULL;
 434
 435   realm_tbl=trp_rtable_get_realm_table(rtbl, comm, realm);
 436   if (realm_tbl==NULL)
 437     return NULL;
 438
 439   return g_hash_table_lookup(realm_tbl, peer); /* does not copy or increment ref count */
 440 }
 441
 442 TRP_ROUTE *trp_rtable_get_selected_entry(TRP_RTABLE *rtbl, TR_NAME *comm, TR_NAME *realm)
 443 {
 444   size_t n=0;
 445   int ii=0;
 446   TRP_ROUTE **entry=trp_rtable_get_realm_entries(rtbl, comm, realm, &n);
 447   TRP_ROUTE *selected=NULL;
 448
 449   if (n==0)
 450     return NULL;
 451
 452   tr_debug("trp_rtable_get_selected_entry: looking through route table entries for realm %.*s.",
 453            realm->len, realm->buf);
 454   for(ii=0; ii<n; ii++) {
 455     if (trp_route_is_selected(entry[ii])) {
 456       selected=entry[ii];
 457       break;
 458     }
 459   }
 460   tr_debug("trp_rtable_get_selected_entry: ii=%d.", ii);
 461
 462   talloc_free(entry);
 463   return selected;
 464 }
 465
 466 void trp_rtable_clear_triggered(TRP_RTABLE *rtbl)
 467 {
 468   size_t n_entries=0;
 469   TRP_ROUTE **entries= trp_rtable_get_entries(NULL, rtbl, &n_entries);
 470   size_t ii=0;
 471
 472   if (entries!=NULL) {
 473     for (ii=0; ii<n_entries; ii++)
 474       trp_route_set_triggered(entries[ii], 0);
 475     talloc_free(entries);
 476   }
 477 }