drl/util.c

   1 /* See the DRL-LICENSE file for this file's software license. */
   2
   3 /* util.c
   4  *
   5  * Mainly a hash table implementation, but other sundry items for
   6  * ulogd_DRL as well.
   7  * Ken Yocum 2007/08
   8  */
   9
  10 #include "raterouter.h"
  11 #include "util.h"
  12 #include "ratetypes.h"
  13 #include "logging.h"
  14
  15 static int util_salt = 0;
  16
  17 /* stupidity BE:MSB first, LE: MSB last*/
  18 static int am_big_endian(void){
  19     long one = 1;
  20     return !(*((char*)(&one))); /* looking for 1 in the big end */
  21 }
  22
  23 static int compare_key(void *one, void *two, int len){
  24     int i;
  25     for (i=0;i<len;i++){ /* word-wise bit compare would be faster */
  26         if(((char*)one)[i] != ((char*)two)[i]){
  27             return(false);
  28         }
  29     }
  30     return(true);
  31 }
  32
  33 /* pass in something at least 20 bytes long */
  34 void ip_from_bytes(uint32_t addr, char *buf){
  35     int i;
  36     unsigned char *caddr = (unsigned char*) &addr;
  37     if (am_big_endian()){
  38         i = sprintf(buf,"%d.%d.%d.%d",caddr[0],caddr[1],caddr[2],caddr[3]);
  39     } else {
  40         i = sprintf(buf,"%d.%d.%d.%d",caddr[3],caddr[2],caddr[1],caddr[0]);
  41     }
  42     return;
  43 }
  44
  45
  46 void init_hashing(void){
  47     util_salt = getpid() ^ time(NULL); // same as ulogd_drl
  48 }
  49
  50 /* some stupid generic hash function things */
  51 /* just return a map_handle */
  52 map_handle allocate_map(void) {
  53     map_handle map;
  54     map = (map_handle) malloc(sizeof(struct map));
  55     if (map == NULL) {
  56         printlog(LOG_WARN, "allocate_map failed.");
  57         return NULL;
  58     }
  59
  60     memset(map,0,sizeof(struct map));
  61     map->iterator = map->table[0];
  62     map->size = 0;
  63     return(map);
  64 }
  65
  66 /* de-allocates the map, if true, de-allocates crud in map as well */
  67 void free_map(map_handle map, int dealloc){
  68     int i;
  69     struct map_entry *nxt_me,*tmp;
  70     for (i=0;i<GENERIC_HASH_SIZE;i++){
  71         nxt_me = (struct map_entry*) (map->table[i]);
  72         while(nxt_me) {
  73             if (dealloc && (nxt_me->value != NULL)){
  74                 free(nxt_me->value);
  75                 nxt_me->value=NULL;
  76             }
  77             tmp = nxt_me->nxt;
  78             free(nxt_me);
  79             map->size--;
  80             nxt_me= tmp;
  81         }
  82     }
  83     free(map);
  84 }
  85
  86 /* internal_search
  87  *
  88  * prior_me points to a pointer for the space holding the next map
  89  * entry
  90  * If you find the first entry of the linked list, it points to the
  91  * memory in the table holding the pointer to the first map entry.
  92  * Otherwise it points to the memory in the previous map_entry that
  93  * holds the next pointer.
  94  * A triple pointer here, b/c we need to save the value.
  95  */
  96 static struct map_entry* internal_search(map_handle map, void *key, int keylen, struct map_entry*** prior_me){
  97     uint32_t index;
  98     struct map_entry *nxt_me;
  99
 100     index = jhash(key,keylen,util_salt) & (GENERIC_HASH_SIZE - 1);
 101
 102 #if 0
 103     printf("IS: KEY:");
 104     for(i=0;i<keylen;i++){
 105         printf("[%x]",((char*)key)[i]);
 106     }
 107     printf("    Hashes to index (%d)\n", index);
 108 #endif
 109
 110     nxt_me = (struct map_entry*) map->table[index];
 111     *prior_me = (struct map_entry**) &(map->table[index]);
 112
 113     while(nxt_me){
 114         if (compare_key(nxt_me->key,key,keylen)){
 115             return(nxt_me);
 116         }
 117         *prior_me = &(nxt_me->nxt);
 118         nxt_me = nxt_me->nxt;
 119     }
 120     return(NULL);
 121
 122 }
 123
 124 void* map_next(map_handle map){
 125     void *val;
 126
 127     if (map->iterator_row == GENERIC_HASH_SIZE){
 128         return(NULL); /* empty, call reset */
 129     }
 130     /* iterator points to current one to return */
 131     if (map->iterator != NULL){
 132         val = map->iterator->value;
 133         map->iterator = map->iterator->nxt;
 134         return(val);
 135     }
 136     /* if null, go to next row */
 137     while (map->iterator == NULL){
 138         map->iterator_row++;
 139         if (map->iterator_row < GENERIC_HASH_SIZE) {
 140             map->iterator = map->table[map->iterator_row];
 141         } else {
 142             return(NULL);
 143         }
 144     }
 145     val = map->iterator->value;
 146     map->iterator = map->iterator->nxt;
 147     return(val);
 148 }
 149
 150 void map_reset_iterate(map_handle map){
 151     map->iterator = map->table[0];
 152     map->iterator_row = 0;
 153 }
 154
 155 int map_size(map_handle map){
 156     return(map->size);
 157 }
 158
 159 void** map_to_array(map_handle map, int *length){
 160     void** array = (void**)malloc(sizeof(void*)*(map->size + 1));
 161     int i;
 162
 163     *length = map->size;
 164     map_reset_iterate(map);
 165     for(i=0;i<map->size;i++){
 166         array[i] = map_next(map);
 167     }
 168     array[i] = NULL; /* just in case */
 169     return(array);
 170 }
 171
 172 void* map_search(map_handle map,void *key, int keylen){
 173     struct map_entry *me,**pme;
 174     me = internal_search(map,key,keylen,&pme);
 175     if (me!=NULL) {
 176         return(me->value);
 177     } else {
 178         return(NULL);
 179     }
 180 }
 181
 182 void* map_remove(map_handle map,void *key, int keylen){
 183     struct map_entry *me,**pme;
 184     void *rtn_val;
 185     me = internal_search(map,key,keylen,&pme);
 186     if (me!=NULL){
 187         (*pme) = me->nxt;
 188         rtn_val = me->value;
 189         free (me);
 190         map->size--;
 191         return(rtn_val);
 192     } else {
 193         return(NULL);
 194     }
 195 }
 196
 197 /* the key is a void *, but we also need the length */
 198 void map_insert(map_handle map, void *key, int keylen, void *value) {
 199     struct map_entry *me,**pme;
 200
 201     me = internal_search(map,key,keylen,&pme);
 202     if (me != NULL){
 203         printlog(LOG_WARN, "util.c: insert failed, key already present.");
 204         return;
 205     }
 206     /* now pme is at the end of the list on that index */
 207     me = (struct map_entry*) malloc(sizeof(struct map_entry));
 208     if (me == NULL) {
 209         printlog(LOG_WARN, "util.c: insert failed, malloc failure");
 210         return;
 211     }
 212     if ((*pme) == NULL)
 213         (*pme) = me; /* pointer now points to this new entry */
 214     else {
 215         printlog(LOG_WARN, "util.c: insert failed. pme should always be NULL.");
 216         free(me);
 217         return;
 218     }
 219     me->nxt = NULL;
 220     me->key = key;
 221     me->value = value;
 222     map->size++;
 223     return;
 224 }
 225
 226 /* get_local_ip
 227  *
 228  * go through the available interfaces and find the first
 229  * with a routable IP (not 10.*, 192.*, or 172.*)
 230  * Ignore inet6 addrs for now.
 231  * return the string.
 232  */
 233 char* get_local_ip(){
 234     char *ip, *localip;
 235     struct ifaddrs *ifa = NULL, *ifp = NULL;
 236     struct sockaddr *addr;
 237     uint32_t ho_addr;
 238     socklen_t salen;
 239     int shift;
 240     unsigned char addrbyte;
 241
 242
 243     if (getifaddrs(&ifp) < 0) {
 244         perror("getifaddrs");
 245         return 0;
 246     }
 247
 248     if (am_big_endian()){
 249         shift = 0;
 250     } else {
 251         shift = 3;
 252     }
 253
 254 #define STRINGSIZE 200
 255     ip = (char *)malloc(STRINGSIZE);
 256     localip = NULL;
 257
 258
 259     for (ifa = ifp; ifa; ifa=ifa->ifa_next){
 260         if (ifa->ifa_addr->sa_family == AF_INET){
 261             salen = sizeof(struct sockaddr_in);
 262         } else if( ifa->ifa_addr->sa_family == AF_INET6){
 263             salen = sizeof(struct sockaddr_in6);
 264         } else {
 265             continue;
 266         }
 267
 268
 269         if (getnameinfo(ifa->ifa_addr,salen, ip, STRINGSIZE, NULL, 0, NI_NUMERICHOST) < 0){
 270             perror("getnameinfo");
 271             continue;
 272         }
 273         /* return the first public IP match */
 274
 275         addr = ifa->ifa_addr;  /* a sockaddr */
 276         struct in_addr *sin_addr = & (((struct sockaddr_in*)addr)->sin_addr);
 277         ho_addr = ntohl((uint32_t)(sin_addr->s_addr));
 278         addrbyte = ((char*)&ho_addr)[shift];
 279         //printf("get_local_ip found %s and sin_addr 0x%x addrbyte %d\n",ip,ho_addr,(uint32_t)addrbyte);
 280
 281         /* is it MSB first? */
 282
 283         /* We don't want to choose the loopback. */
 284         if (addrbyte == 127)
 285             continue;
 286
 287         /* If there's a non-local address, use that. */
 288         if ((addrbyte != 192) && (addrbyte != 172) && (addrbyte != 10)){
 289             printlog(LOG_WARN, "     Using ip: %s\n",ip);
 290             freeifaddrs(ifp);
 291             if (localip != NULL) {
 292                 free(localip);
 293             }
 294             return(ip); /* for now return the IP address */
 295         } else {
 296             if (localip == NULL) {
 297                 localip = malloc(STRINGSIZE);
 298             }
 299             strncpy(localip, ip, STRINGSIZE);
 300         }
 301     }
 302     freeifaddrs(ifp);
 303     free(ip);
 304
 305     if (localip != NULL)
 306         return localip;
 307     else
 308         return(NULL);
 309 }
 310
 311 static FILE *urandfd = NULL;
 312
 313 static void myrand_init() {
 314     if (urandfd == NULL) {
 315         urandfd = fopen("/dev/urandom", "rb");
 316         if (urandfd == NULL) {
 317             perror("myrand_init: fopen");
 318         }
 319         setvbuf(urandfd, NULL, _IOFBF, 1 << 16);
 320     }
 321 }
 322
 323 /* returns an unsigned int between 0 and UINT_MAX */
 324 unsigned int myrand() {
 325     int successful;
 326
 327     /* my new rand code */
 328     myrand_init();
 329
 330     unsigned int r;
 331     successful = fread(&r, sizeof(unsigned int), 1, urandfd);
 332
 333     return r;
 334 }
 335
 336 /* returns a random bool */
 337 int myrand_boolean() {
 338     int successful;
 339
 340     myrand_init();
 341
 342     uint8_t r;
 343     successful = fread(&r, sizeof(uint8_t), 1, urandfd);
 344
 345     return (r%2);
 346 }
 347
 348 /* returns a random double between 0 and 1 */
 349 double myrand_double() {
 350     return (double) myrand() / (double) UINT_MAX;
 351 }
 352
 353 /* takes the log_2 of x */
 354 int my_lg(int x) {
 355     int c = 0;
 356     while (x > 0) {
 357         c++;
 358         x = x >> 1;
 359     }
 360
 361     return c;
 362 }