1 /* See the DRL-LICENSE file for this file's software license. */
5 * Mainly a hash table implementation, but other sundry items for
10 #include "raterouter.h"
12 #include "ratetypes.h"
15 static int util_salt = 0;
17 /* stupidity BE:MSB first, LE: MSB last*/
18 static int am_big_endian(void){
20 return !(*((char*)(&one))); /* looking for 1 in the big end */
23 static int compare_key(void *one, void *two, int len){
25 for (i=0;i<len;i++){ /* word-wise bit compare would be faster */
26 if(((char*)one)[i] != ((char*)two)[i]){
33 /* pass in something at least 20 bytes long */
34 void ip_from_bytes(uint32_t addr, char *buf){
36 unsigned char *caddr = (unsigned char*) &addr;
38 i = sprintf(buf,"%d.%d.%d.%d",caddr[0],caddr[1],caddr[2],caddr[3]);
40 i = sprintf(buf,"%d.%d.%d.%d",caddr[3],caddr[2],caddr[1],caddr[0]);
46 void init_hashing(void){
47 util_salt = getpid() ^ time(NULL); // same as ulogd_drl
50 /* some stupid generic hash function things */
51 /* just return a map_handle */
52 map_handle allocate_map(void) {
54 map = (map_handle) malloc(sizeof(struct map));
56 printlog(LOG_WARN, "allocate_map failed.");
60 memset(map,0,sizeof(struct map));
61 map->iterator = map->table[0];
66 /* de-allocates the map, if true, de-allocates crud in map as well */
67 void free_map(map_handle map, int dealloc){
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]);
73 if (dealloc && (nxt_me->value != NULL)){
88 * prior_me points to a pointer for the space holding the next map
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.
96 static struct map_entry* internal_search(map_handle map, void *key, int keylen, struct map_entry*** prior_me){
98 struct map_entry *nxt_me;
100 index = jhash(key,keylen,util_salt) & (GENERIC_HASH_SIZE - 1);
104 for(i=0;i<keylen;i++){
105 printf("[%x]",((char*)key)[i]);
107 printf(" Hashes to index (%d)\n", index);
110 nxt_me = (struct map_entry*) map->table[index];
111 *prior_me = (struct map_entry**) &(map->table[index]);
114 if (compare_key(nxt_me->key,key,keylen)){
117 *prior_me = &(nxt_me->nxt);
118 nxt_me = nxt_me->nxt;
124 void* map_next(map_handle map){
127 if (map->iterator_row == GENERIC_HASH_SIZE){
128 return(NULL); /* empty, call reset */
130 /* iterator points to current one to return */
131 if (map->iterator != NULL){
132 val = map->iterator->value;
133 map->iterator = map->iterator->nxt;
136 /* if null, go to next row */
137 while (map->iterator == NULL){
139 if (map->iterator_row < GENERIC_HASH_SIZE) {
140 map->iterator = map->table[map->iterator_row];
145 val = map->iterator->value;
146 map->iterator = map->iterator->nxt;
150 void map_reset_iterate(map_handle map){
151 map->iterator = map->table[0];
152 map->iterator_row = 0;
155 int map_size(map_handle map){
159 void** map_to_array(map_handle map, int *length){
160 void** array = (void**)malloc(sizeof(void*)*(map->size + 1));
164 map_reset_iterate(map);
165 for(i=0;i<map->size;i++){
166 array[i] = map_next(map);
168 array[i] = NULL; /* just in case */
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);
182 void* map_remove(map_handle map,void *key, int keylen){
183 struct map_entry *me,**pme;
185 me = internal_search(map,key,keylen,&pme);
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;
201 me = internal_search(map,key,keylen,&pme);
203 printlog(LOG_WARN, "util.c: insert failed, key already present.");
206 /* now pme is at the end of the list on that index */
207 me = (struct map_entry*) malloc(sizeof(struct map_entry));
209 printlog(LOG_WARN, "util.c: insert failed, malloc failure");
213 (*pme) = me; /* pointer now points to this new entry */
215 printlog(LOG_WARN, "util.c: insert failed. pme should always be NULL.");
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.
233 char* get_local_ip(){
235 struct ifaddrs *ifa = NULL, *ifp = NULL;
236 struct sockaddr *addr;
240 unsigned char addrbyte;
243 if (getifaddrs(&ifp) < 0) {
244 perror("getifaddrs");
248 if (am_big_endian()){
254 #define STRINGSIZE 200
255 ip = (char *)malloc(STRINGSIZE);
258 for (ifa = ifp; ifa; ifa=ifa->ifa_next){
259 if (ifa->ifa_addr->sa_family == AF_INET){
260 salen = sizeof(struct sockaddr_in);
261 } else if( ifa->ifa_addr->sa_family == AF_INET6){
262 salen = sizeof(struct sockaddr_in6);
268 if (getnameinfo(ifa->ifa_addr,salen, ip, STRINGSIZE, NULL, 0, NI_NUMERICHOST) < 0){
269 perror("getnameinfo");
272 /* return the first public IP match */
274 addr = ifa->ifa_addr; /* a sockaddr */
275 struct in_addr *sin_addr = & (((struct sockaddr_in*)addr)->sin_addr);
276 ho_addr = ntohl((uint32_t)(sin_addr->s_addr));
277 addrbyte = ((char*)&ho_addr)[shift];
278 //printf("get_local_ip found %s and sin_addr 0x%x addrbyte %d\n",ip,ho_addr,(uint32_t)addrbyte);
280 /* is it MSB first? */
282 if ( (addrbyte != 192) && (addrbyte != 172)
283 && (addrbyte != 10) && (addrbyte != 127) ){
284 printlog(LOG_WARN, " Using ip: %s\n",ip);
287 return (ifa->ifa_addr->sin_addr);
289 return(ip); /* for now return the IP address */
298 static FILE *urandfd = NULL;
300 static void myrand_init() {
301 if (urandfd == NULL) {
302 urandfd = fopen("/dev/urandom", "rb");
303 if (urandfd == NULL) {
304 perror("myrand_init: fopen");
306 setvbuf(urandfd, NULL, _IOFBF, 1 << 16);
310 /* returns an unsigned int between 0 and UINT_MAX */
311 unsigned int myrand() {
314 /* my new rand code */
318 successful = fread(&r, sizeof(unsigned int), 1, urandfd);
323 /* returns a random bool */
324 int myrand_boolean() {
330 successful = fread(&r, sizeof(uint8_t), 1, urandfd);
335 /* returns a random double between 0 and 1 */
336 double myrand_double() {
337 return (double) myrand() / (double) UINT_MAX;
340 /* takes the log_2 of x */