rt/subnet.c

   1 /*
   2     subnet.c -- subnet handling
   3
   4     Copyright (C) 2003-2004 Guus Sliepen <guus@tinc-vpn.org>,
   5                   2003-2004 Ivo Timmermans <ivo@tinc-vpn.org>
   6
   7     This program is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     This program is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program; if not, write to the Free Software
  19     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20
  21     $Id$
  22 */
  23
  24 #include "system.h"
  25
  26 #include "cfg/cfg.h"
  27 #include "logger/logger.h"
  28 #include "rt/node.h"
  29 #include "rt/subnet.h"
  30 #include "support/avl.h"
  31 #include "support/xalloc.h"
  32
  33 avl_tree_t *subnets;
  34 /* Subnet mask handling */
  35
  36 static int maskcmp(const void *va, const void *vb, int masklen, int len) {
  37         int i, m, result;
  38         const char *a = va;
  39         const char *b = vb;
  40
  41         for(m = masklen, i = 0; m >= 8; m -= 8, i++) {
  42                 result = a[i] - b[i];
  43                 if(result)
  44                         return result;
  45         }
  46
  47         return m ? (a[i] & (0x100 - (1 << (8 - m)))) - (b[i] & (0x100 - (1 << (8 - m)))) : 0;
  48 }
  49
  50 static void mask(void *va, int masklen, int len) {
  51         int i;
  52         char *a = va;
  53
  54         i = masklen / 8;
  55         masklen %= 8;
  56
  57         if(masklen)
  58                 a[i++] &= (0x100 - (1 << masklen));
  59
  60         for(; i < len; i++)
  61                 a[i] = 0;
  62 }
  63
  64 static void maskcpy(void *va, const void *vb, int masklen, int len) {
  65         int i, m;
  66         char *a = va;
  67         const char *b = vb;
  68
  69         for(m = masklen, i = 0; m >= 8; m -= 8, i++)
  70                 a[i] = b[i];
  71
  72         if(m) {
  73                 a[i] = b[i] & (0x100 - (1 << m));
  74                 i++;
  75         }
  76
  77         for(; i < len; i++)
  78                 a[i] = 0;
  79 }
  80
  81 static bool maskcheck(const void *va, int masklen, int len) {
  82         int i;
  83         const char *a = va;
  84
  85         i = masklen / 8;
  86         masklen %= 8;
  87
  88         if(masklen && a[i++] & (0xff >> masklen))
  89                 return false;
  90
  91         for(; i < len; i++)
  92                 if(a[i] != 0)
  93                         return false;
  94
  95         return true;
  96 }
  97
  98 /* Cache handling */
  99
 100 struct {
 101         subnet_t key;
 102         subnet_t *subnet;
 103 } *cache;
 104
 105 int cache_bits;
 106 int cache_size;
 107 uint32_t cache_mask;
 108
 109 static void cache_flush(void) {
 110         memset(cache, 0, sizeof *cache * cache_size);
 111 }
 112
 113 static void cache_init(void) {
 114         cache_bits = 8;
 115         cache_size = 1 << 8;
 116         cache_mask = cache_size - 1;
 117
 118         dim(cache, cache_size);
 119
 120         cache_flush();
 121 }
 122
 123 static void cache_exit(void) {
 124         free(cache);
 125 }
 126
 127 static uint32_t subnet_hash(const subnet_t *subnet) {
 128         uint32_t hash;
 129         int i;
 130
 131         hash = subnet->type;
 132
 133         for(i = 0; i < sizeof subnet->net / sizeof(uint32_t); i++)
 134                 hash ^= ((uint32_t *)&subnet->net)[i];
 135
 136         hash ^= hash >> 16;
 137         hash ^= hash >> 8;
 138
 139         return hash & cache_mask;
 140 }
 141
 142 static subnet_t *cache_get(subnet_t *subnet) {
 143         uint32_t hash = subnet_hash(subnet);
 144
 145         if(cache[hash].subnet && memcmp(&cache[hash].key, subnet, sizeof *subnet))
 146                 return cache[hash].subnet;
 147         else
 148                 return NULL;
 149 }
 150
 151 static void cache_add(subnet_t *key, subnet_t *subnet) {
 152         uint32_t hash = subnet_hash(subnet);
 153
 154         cache[hash].key = *key;
 155         cache[hash].subnet = subnet;
 156 }
 157
 158 /* Subnet tree handling */
 159
 160 static int subnet_compare_mac(const subnet_t *a, const subnet_t *b) {
 161         return memcmp(&a->net.mac.address, &b->net.mac.address, sizeof(mac_t))
 162                 ?: (a->owner && b->owner) ? strcmp(a->owner->name, b->owner->name) : 0;
 163 }
 164
 165 static int subnet_compare_ipv4(const subnet_t *a, const subnet_t *b) {
 166         return memcmp(&a->net.ipv4.address, &b->net.ipv4.address, sizeof(ipv4_t))
 167                 ?: (a->net.ipv4.prefixlength - b->net.ipv4.prefixlength)
 168                 ?: (a->owner && b->owner) ? strcmp(a->owner->name, b->owner->name) : 0;
 169 }
 170
 171 static int subnet_compare_ipv6(const subnet_t *a, const subnet_t *b) {
 172         return memcmp(&a->net.ipv6.address, &b->net.ipv6.address, sizeof(ipv6_t))
 173                 ?: (a->net.ipv6.prefixlength - b->net.ipv6.prefixlength)
 174                 ?: (a->owner && b->owner) ? strcmp(a->owner->name, b->owner->name) : 0;
 175 }
 176
 177 static int subnet_compare(const subnet_t *a, const subnet_t *b) {
 178         int result;
 179
 180         result = a->type - b->type;
 181
 182         if(result)
 183                 return result;
 184
 185         switch (a->type) {
 186                 case SUBNET_TYPE_MAC:
 187                         return subnet_compare_mac(a, b);
 188                 case SUBNET_TYPE_IPV4:
 189                         return subnet_compare_ipv4(a, b);
 190                 case SUBNET_TYPE_IPV6:
 191                         return subnet_compare_ipv6(a, b);
 192                 default:
 193                         logger(LOG_ERR, _("rt: subnet_compare() was called with unknown subnet type %d, exitting!"), a->type);
 194                         exit(1);
 195         }
 196 }
 197
 198 avl_tree_t *subnet_tree_new(void) {
 199         return avl_tree_new((avl_compare_t)subnet_compare, NULL);
 200 }
 201
 202 void subnet_tree_free(avl_tree_t *subnets) {
 203         avl_tree_free(subnets);
 204 }
 205
 206 subnet_t *subnet_new(void) {
 207         subnet_t *subnet;
 208
 209         return clear(new(subnet));
 210 }
 211
 212 void subnet_free(subnet_t *subnet) {
 213         free(subnet);
 214 }
 215
 216 void subnet_add(subnet_t *subnet) {
 217         avl_add(subnets, subnet);
 218         avl_add(subnet->owner->subnets, subnet);
 219         cache_flush();
 220 }
 221
 222 void subnet_del(subnet_t *subnet) {
 223         avl_del(subnet->owner->subnets, subnet);
 224         avl_del(subnets, subnet);
 225         cache_flush();
 226 }
 227
 228 bool subnet_init(void) {
 229         cache_init();
 230         subnets = avl_tree_new((avl_compare_t)subnet_compare, (avl_action_t)subnet_free);
 231
 232         return true;
 233 }
 234
 235 bool subnet_exit(void) {
 236         avl_tree_del(subnets);
 237         cache_exit();
 238
 239         return true;
 240 }
 241
 242 subnet_t *str2net(const char *subnetstr) {
 243         int i, l;
 244         subnet_t subnet = {0};
 245         uint16_t x[8];
 246
 247         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu/%d",
 248                           &x[0], &x[1], &x[2], &x[3], &l) == 5) {
 249                 subnet.type = SUBNET_TYPE_IPV4;
 250                 subnet.net.ipv4.prefixlength = l;
 251
 252                 for(i = 0; i < 4; i++)
 253                         subnet.net.ipv4.address.x[i] = x[i];
 254
 255                 return copy(&subnet);
 256         }
 257
 258         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d",
 259                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7],
 260                           &l) == 9) {
 261                 subnet.type = SUBNET_TYPE_IPV6;
 262                 subnet.net.ipv6.prefixlength = l;
 263
 264                 for(i = 0; i < 8; i++)
 265                         subnet.net.ipv6.address.x[i] = htons(x[i]);
 266
 267                 return copy(&subnet);
 268         }
 269
 270         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu", &x[0], &x[1], &x[2], &x[3]) == 4) {
 271                 subnet.type = SUBNET_TYPE_IPV4;
 272                 subnet.net.ipv4.prefixlength = 32;
 273
 274                 for(i = 0; i < 4; i++)
 275                         subnet.net.ipv4.address.x[i] = x[i];
 276
 277                 return copy(&subnet);
 278         }
 279
 280         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx",
 281                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7]) == 8) {
 282                 subnet.type = SUBNET_TYPE_IPV6;
 283                 subnet.net.ipv6.prefixlength = 128;
 284
 285                 for(i = 0; i < 8; i++)
 286                         subnet.net.ipv6.address.x[i] = htons(x[i]);
 287
 288                 return copy(&subnet);
 289         }
 290
 291         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx",
 292                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5]) == 6) {
 293                 subnet.type = SUBNET_TYPE_MAC;
 294
 295                 for(i = 0; i < 6; i++)
 296                         subnet.net.mac.address.x[i] = x[i];
 297
 298                 return copy(&subnet);
 299         }
 300
 301         return NULL;
 302 }
 303
 304 char *net2str(const subnet_t *subnet) {
 305         char *netstr;
 306
 307         switch (subnet->type) {
 308                 case SUBNET_TYPE_MAC:
 309                         asprintf(&netstr, "%hx:%hx:%hx:%hx:%hx:%hx",
 310                                          subnet->net.mac.address.x[0],
 311                                          subnet->net.mac.address.x[1],
 312                                          subnet->net.mac.address.x[2],
 313                                          subnet->net.mac.address.x[3],
 314                                          subnet->net.mac.address.x[4],
 315                                          subnet->net.mac.address.x[5]);
 316                         break;
 317
 318                 case SUBNET_TYPE_IPV4:
 319                         asprintf(&netstr, "%hu.%hu.%hu.%hu/%d",
 320                                          subnet->net.ipv4.address.x[0],
 321                                          subnet->net.ipv4.address.x[1],
 322                                          subnet->net.ipv4.address.x[2],
 323                                          subnet->net.ipv4.address.x[3],
 324                                          subnet->net.ipv4.prefixlength);
 325                         break;
 326
 327                 case SUBNET_TYPE_IPV6:
 328                         asprintf(&netstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d",
 329                                          ntohs(subnet->net.ipv6.address.x[0]),
 330                                          ntohs(subnet->net.ipv6.address.x[1]),
 331                                          ntohs(subnet->net.ipv6.address.x[2]),
 332                                          ntohs(subnet->net.ipv6.address.x[3]),
 333                                          ntohs(subnet->net.ipv6.address.x[4]),
 334                                          ntohs(subnet->net.ipv6.address.x[5]),
 335                                          ntohs(subnet->net.ipv6.address.x[6]),
 336                                          ntohs(subnet->net.ipv6.address.x[7]),
 337                                          subnet->net.ipv6.prefixlength);
 338                         break;
 339
 340                 default:
 341                         logger(LOG_ERR, _("net2str() was called with unknown subnet type %d, exiting!"), subnet->type);
 342                         exit(0);
 343         }
 344
 345         return netstr;
 346 }
 347
 348 bool cfg_subnet(cfg_t *cfg, subnet_t **result) {
 349         subnet_t *subnet;
 350
 351         subnet = str2net(cfg->value);
 352
 353         if(!subnet) {
 354                 logger(LOG_ERR, _("rt: invalid subnet for configuration variable %s in %s line %d"),
 355                    cfg->variable, cfg->file, cfg->line);
 356                 return false;
 357         }
 358
 359         *result = subnet;
 360
 361         return true;
 362 }
 363
 364 subnet_t *subnet_get(const subnet_t *subnet) {
 365         return subnet->owner ? avl_get(subnet->owner->subnets, subnet) : avl_get(subnets, subnet);
 366 }
 367
 368 subnet_t *subnet_get_mac(const mac_t *address) {
 369         subnet_t *subnet, search = {0};
 370
 371         search.type = SUBNET_TYPE_MAC;
 372         search.net.mac.address = *address;
 373
 374         subnet = cache_get(&search);
 375
 376         if(subnet)
 377                 return subnet;
 378
 379         subnet = avl_get(subnets, &search);
 380
 381         if(subnet)
 382                 cache_add(&search, subnet);
 383
 384         return subnet;
 385 }
 386
 387 subnet_t *subnet_get_ipv4(const ipv4_t *address) {
 388         subnet_t *subnet, search = {0};
 389
 390         search.type = SUBNET_TYPE_IPV4;
 391         search.net.ipv4.address = *address;
 392         search.net.ipv4.prefixlength = 32;
 393
 394         subnet = cache_get(&search);
 395
 396         if(subnet)
 397                 return subnet;
 398
 399         while(subnet = avl_get_closest_smaller(subnets, &search)) {
 400                 if(subnet->type != SUBNET_TYPE_IPV4)
 401                         return NULL;
 402
 403                 if(!maskcmp(address, &subnet->net.ipv4.address, subnet->net.ipv4.prefixlength, sizeof(ipv4_t))) {
 404                         cache_add(&search, subnet);
 405                         return subnet;
 406                 }
 407
 408                 search.net.ipv4.prefixlength = subnet->net.ipv4.prefixlength - 1;
 409                 maskcpy(&search.net.ipv4.address, &subnet->net.ipv4.address, search.net.ipv4.prefixlength, sizeof(ipv4_t));
 410         }
 411
 412         return NULL;
 413 }
 414
 415 subnet_t *subnet_get_ipv6(const ipv6_t *address) {
 416         subnet_t *subnet, search = {0};
 417
 418         search.type = SUBNET_TYPE_IPV6;
 419         search.net.ipv6.address = *address;
 420         search.net.ipv6.prefixlength = 128;
 421
 422         subnet = cache_get(&search);
 423
 424         if(subnet)
 425                 return subnet;
 426
 427         while(subnet = avl_get_closest_smaller(subnets, &search)) {
 428                 if(subnet->type != SUBNET_TYPE_IPV6)
 429                         return NULL;
 430
 431                 if(!maskcmp(address, &subnet->net.ipv6.address, subnet->net.ipv6.prefixlength, sizeof(ipv6_t))) {
 432                         cache_add(&search, subnet);
 433                         return subnet;
 434                 }
 435
 436                 search.net.ipv6.prefixlength = subnet->net.ipv6.prefixlength - 1;
 437                 maskcpy(&search.net.ipv6.address, &subnet->net.ipv6.address, search.net.ipv6.prefixlength, sizeof(ipv6_t));
 438         }
 439
 440         return NULL;
 441 }