1/* dnsmasq is Copyright (c) 2000 Simon Kelley 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License as published by 5 the Free Software Foundation; version 2 dated June, 1991. 6 7 This program is distributed in the hope that it will be useful, 8 but WITHOUT ANY WARRANTY; without even the implied warranty of 9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 GNU General Public License for more details. 11*/ 12 13#include "dnsmasq.h" 14 15 16static struct crec *cache_head, *cache_tail; 17static int cache_inserted, cache_live_freed; 18static union bigname *big_free; 19static int bignames_left, log_queries, cache_size; 20static struct crec *cache_buf; 21 22static void cache_free(struct crec *crecp); 23static void cache_unlink (struct crec *crecp); 24 25void cache_init(int size, int logq) 26{ 27 struct crec *crecp; 28 int i; 29 30 log_queries = logq; 31 cache_head = cache_tail = NULL; 32 cache_size = size; 33 big_free = NULL; 34 bignames_left = size/10; 35 36 cache_inserted = cache_live_freed = 0; 37 38 if (cache_size > 0) 39 { 40 cache_buf = crecp = safe_malloc(size*sizeof(struct crec)); 41 42 for (i=0; i<size; i++, crecp++) 43 { 44 cache_link(crecp); 45 crecp->flags = 0; 46 } 47 } 48} 49 50/* Note that it's OK to free slots with F_DHCP set */ 51/* They just float around unused until the new dhcp.leases load */ 52static void cache_free(struct crec *crecp) 53{ 54 cache_unlink(crecp); 55 crecp->flags &= ~F_FORWARD; 56 crecp->flags &= ~F_REVERSE; 57 cache_tail->next = crecp; 58 crecp->prev = cache_tail; 59 crecp->next = NULL; 60 cache_tail = crecp; 61 /* retrieve big name for further use. */ 62 if (crecp->flags & F_BIGNAME) 63 { 64 crecp->name.bname->next = big_free; 65 big_free = crecp->name.bname; 66 crecp->flags &= ~F_BIGNAME; 67 } 68} 69 70/* insert a new cache entry at the head of the list (youngest entry) */ 71void cache_link(struct crec *crecp) 72{ 73 if (cache_head) /* check needed for init code */ 74 cache_head->prev = crecp; 75 crecp->next = cache_head; 76 crecp->prev = NULL; 77 cache_head = crecp; 78 if (!cache_tail) 79 cache_tail = crecp; 80} 81 82/* remove an arbitrary cache entry for promotion */ 83static void cache_unlink (struct crec *crecp) 84{ 85 if (crecp->prev) 86 crecp->prev->next = crecp->next; 87 else 88 cache_head = crecp->next; 89 90 if (crecp->next) 91 crecp->next->prev = crecp->prev; 92 else 93 cache_tail = crecp->prev; 94} 95 96/* before starting an insertion, mark all existing entries as old, 97 and candidates for replacement */ 98void cache_start_insert(void) 99{ 100 struct crec *crecp; 101 102 for (crecp = cache_head; crecp; crecp = crecp->next) 103 crecp->flags &= ~F_NEW; 104} 105 106/* after end of insertion, if any insertions failed (due to no memory) 107 back out the whole lot */ 108void cache_end_insert(int failed) 109{ 110 struct crec *crecp = cache_head; 111 112 if (failed) 113 while (crecp) 114 { 115 struct crec *tmp = crecp->next; 116 if (crecp->flags & F_NEW) 117 { 118 cache_free(crecp); 119 crecp->flags &= ~F_NEW; 120 } 121 crecp = tmp; 122 } 123} 124 125char *cache_get_name(struct crec *crecp) 126{ 127 return (crecp->flags & F_BIGNAME) ? crecp->name.bname->name : crecp->name.sname; 128} 129 130void cache_insert(char *name, struct all_addr *addr, time_t now, 131 unsigned long ttl, int flags, int *fail) 132{ 133#ifdef HAVE_IPV6 134 int addrlen = (flags & F_IPV6) ? IN6ADDRSZ : INADDRSZ; 135#else 136 int addrlen = INADDRSZ; 137#endif 138 struct crec *new, *crecp = cache_head; 139 union bigname *big_name = NULL; 140 141 log_query(flags | F_UPSTREAM, name, addr); 142 143 /* if previous insertion failed give up now. */ 144 if (*fail || cache_size == 0) 145 return; 146 147 /* first remove old entries for the same name or address and 148 protocol and any expired entries */ 149 /* flags arg is F_FORWARD or F_REVERSE and F_IPV4 or F_IPV6 */ 150 while (crecp) 151 { 152 struct crec *tmp = crecp->next; 153 /* Note that cache entries from /etc/hosts can have both F_FORWARD and 154 F_REVERSE set. Since we don't reap those here, it's no problem. */ 155 if (!(crecp->flags & (F_HOSTS | F_DHCP))) 156 { 157 /* remove expired entries. */ 158 if ((crecp->flags & (F_FORWARD | F_REVERSE)) && 159 (crecp->ttd < now) && !(crecp->flags & F_IMMORTAL)) 160 cache_free(crecp); 161 162 else if (!(crecp->flags & F_NEW) && 163 (crecp->flags & (F_REVERSE | F_FORWARD | F_IPV6 | F_IPV4)) == flags) 164 { 165 if ((flags & F_REVERSE) && 166 memcmp(&crecp->addr, addr, addrlen) == 0) 167 cache_free(crecp); 168 169 else if ((flags & F_FORWARD) && 170 strcmp(cache_get_name(crecp), name) == 0) 171 cache_free(crecp); 172 } 173 } 174 crecp = tmp; 175 } 176 177 /* Now get a cache entry from the end of the LRU list */ 178 do { 179 new = cache_tail; 180 /* if we find a new entry there are not enough freeable entries 181 in the cache so bail out. !new catches completely empty list, 182 new == tmp catches no ordinary entries, just HOSTS and DHCP. */ 183 if (new->flags & F_NEW) 184 { 185 *fail = 1; 186 return; 187 } 188 189 /* just push non-vanila entries back to the top and try again. */ 190 if (new->flags & (F_HOSTS | F_DHCP)) 191 { 192 cache_tail = cache_tail->prev; 193 cache_tail->next = NULL; 194 cache_link(new); 195 new = NULL; 196 } 197 else 198 { 199 /* Check if we need to and can allocate extra memory for a long name. 200 If that fails, give up now. */ 201 if (strlen(name) > SMALLDNAME-1) 202 { 203 if (big_free) 204 { 205 big_name = big_free; 206 big_free = big_free->next; 207 } 208 else if (!bignames_left || 209 !(big_name = (union bigname *)safe_malloc(sizeof(union bigname)))) 210 { 211 *fail = 1; 212 return; 213 } 214 else 215 bignames_left--; 216 217 } 218 /* Got the rest: finally grab entry. */ 219 cache_tail = cache_tail->prev; 220 cache_tail->next = NULL; 221 } 222 } while (!new); 223 224 /* The next bit ensures that if there is more than one entry 225 for a name or address, they all get removed at once */ 226 if (new->flags & (F_FORWARD | F_REVERSE)) 227 { 228 int newflags = new->flags & (F_REVERSE | F_FORWARD | F_IPV6 | F_IPV4); 229#ifdef HAVE_IPV6 230 int newaddrlen = (newflags & F_IPV6) ? IN6ADDRSZ : INADDRSZ; 231#else 232 int newaddrlen = INADDRSZ; 233#endif 234 /* record still-live cache entries we have to blow away */ 235 cache_live_freed++; 236 237 crecp = cache_head; 238 while (crecp) 239 { 240 struct crec *tmp = crecp->next; 241 if (!(crecp->flags & (F_HOSTS | F_DHCP))) 242 { 243 244 if (!(crecp->flags & F_NEW) && 245 (crecp->flags & (F_REVERSE | F_FORWARD | F_IPV6 | F_IPV4)) == newflags) 246 { 247 if ((newflags & F_REVERSE) && 248 memcmp(&crecp->addr, &new->addr, newaddrlen) == 0) 249 cache_free(crecp); 250 251 if ((newflags & F_FORWARD) && 252 strcmp(cache_get_name(crecp), cache_get_name(new)) == 0) 253 cache_free(crecp); 254 } 255 } 256 crecp = tmp; 257 } 258 } 259 260 261 new->flags = F_NEW | flags; 262 if (big_name) 263 { 264 new->name.bname = big_name; 265 new->flags |= F_BIGNAME; 266 } 267 strcpy(cache_get_name(new), name); 268 if (addr) 269 memcpy(&new->addr, addr, addrlen); 270 else 271 new->flags |= F_NEG; 272 new->ttd = ttl + now; 273 cache_link(new); 274 cache_inserted++; 275} 276 277struct crec *cache_find_by_name(struct crec *crecp, char *name, time_t now, int prot) 278{ 279 if (crecp) /* iterating */ 280 { 281 if (crecp->next && 282 (crecp->next->flags & F_FORWARD) && 283 (crecp->next->flags & prot) && 284 strcmp(cache_get_name(crecp->next), name) == 0) 285 return crecp->next; 286 else 287 return NULL; 288 } 289 290 /* first search, look for relevant entries and push to top of list 291 also free anything which has expired */ 292 293 crecp = cache_head; 294 while (crecp) 295 { 296 struct crec *tmp = crecp->next; 297 if ((crecp->flags & F_FORWARD) && 298 (crecp->flags & prot) && 299 (strcmp(cache_get_name(crecp), name) == 0)) 300 { 301 if ((crecp->flags & F_IMMORTAL) || crecp->ttd > now) 302 { 303 cache_unlink(crecp); 304 cache_link(crecp); 305 } 306 else 307 cache_free(crecp); 308 } 309 crecp = tmp; 310 } 311 312 /* if there's anything relevant, it will be at the head of the cache now. */ 313 314 if (cache_head && 315 (cache_head->flags & F_FORWARD) && 316 (cache_head->flags & prot) && 317 (strcmp(cache_get_name(cache_head), name) == 0)) 318 return cache_head; 319 320 return NULL; 321} 322 323struct crec *cache_find_by_addr(struct crec *crecp, struct all_addr *addr, 324 time_t now, int prot) 325{ 326#ifdef HAVE_IPV6 327 int addrlen = (prot == F_IPV6) ? IN6ADDRSZ : INADDRSZ; 328#else 329 int addrlen = INADDRSZ; 330#endif 331 332 if (crecp) /* iterating */ 333 { 334 if (crecp->next && 335 (crecp->next->flags & F_REVERSE) && 336 (crecp->next->flags & prot) && 337 memcmp(&crecp->next->addr, addr, addrlen) == 0) 338 return crecp->next; 339 else 340 return NULL; 341 } 342 343 /* first search, look for relevant entries and push to top of list 344 also free anything which has expired */ 345 346 crecp = cache_head; 347 while (crecp) 348 { 349 struct crec *tmp = crecp->next; 350 if ((crecp->flags & F_REVERSE) && 351 (crecp->flags & prot) && 352 memcmp(&crecp->addr, addr, addrlen) == 0) 353 { 354 if ((crecp->flags & F_IMMORTAL) || crecp->ttd > now) 355 { 356 cache_unlink(crecp); 357 cache_link(crecp); 358 } 359 else 360 cache_free(crecp); 361 } 362 crecp = tmp; 363 } 364 365 /* if there's anything relevant, it will be at the head of the cache now. */ 366 367 if (cache_head && 368 (cache_head->flags & F_REVERSE) && 369 (cache_head->flags & prot) && 370 memcmp(&cache_head->addr, addr, addrlen) == 0) 371 return cache_head; 372 373 return NULL; 374} 375 376void cache_reload(int no_hosts, char *buff) 377{ 378 struct crec *cache, *tmp; 379#ifdef HAVE_FILE_SYSTEM 380 FILE *f; 381 char *line; 382#endif 383 384 for (cache=cache_head; cache; cache=tmp) 385 { 386 tmp = cache->next; 387 if (cache->flags & F_HOSTS) 388 { 389 cache_unlink(cache); 390 safe_free(cache); 391 } 392 else if (!(cache->flags & F_DHCP)) 393 { 394 if (cache->flags & F_BIGNAME) 395 { 396 cache->name.bname->next = big_free; 397 big_free = cache->name.bname; 398 } 399 cache->flags = 0; 400 } 401 } 402 403 if (no_hosts) 404 { 405 if (cache_size > 0) 406 syslog(LOG_INFO, "cleared cache"); 407 return; 408 } 409 410#ifdef HAVE_FILE_SYSTEM 411 f = fopen(HOSTSFILE, "r"); 412 413 if (!f) 414 { 415 syslog(LOG_ERR, "failed to load names from %s: %m", HOSTSFILE); 416 return; 417 } 418 419 syslog(LOG_INFO, "reading %s", HOSTSFILE); 420 421 while ((line = fgets(buff, MAXDNAME, f))) 422 { 423 struct all_addr addr; 424 char *token = strtok(line, " \t\n"); 425 int addrlen, flags; 426 427 if (!token || (*token == '#')) 428 continue; 429 430 if (inet_pton(AF_INET, token, &addr) == 1) 431 { 432 flags = F_HOSTS | F_IMMORTAL | F_FORWARD | F_REVERSE | F_IPV4; 433 addrlen = INADDRSZ; 434 } 435#ifdef HAVE_IPV6 436 else if(inet_pton(AF_INET6, token, &addr) == 1) 437 { 438 flags = F_HOSTS | F_IMMORTAL | F_FORWARD | F_REVERSE | F_IPV6; 439 addrlen = IN6ADDRSZ; 440 } 441#endif 442 else 443 continue; 444 445 while ((token = strtok(NULL, " \t\n")) && (*token != '#')) 446 { 447 canonicalise(token); 448 if ((cache = safe_malloc(sizeof(struct crec) + strlen(token)+1-SMALLDNAME))) 449 { 450 strcpy(cache->name.sname, token); 451 cache->flags = flags; 452 memcpy(&cache->addr, &addr, addrlen); 453 cache_link(cache); 454 /* Only the first name is canonical, and should be 455 returned to reverse queries */ 456 flags &= ~F_REVERSE; 457 } 458 } 459 } 460 461 fclose(f); 462#else 463#endif 464} 465 466 467struct crec *cache_clear_dhcp(void) 468{ 469 struct crec *cache = cache_head, *ret = NULL; 470 471 while (cache) 472 { 473 struct crec *tmp = cache->next; 474 if (cache->flags & F_DHCP) 475 { 476 cache_unlink(cache); 477 cache->next = ret; 478 ret = cache; 479 } 480 cache = tmp; 481 } 482 return ret; 483} 484 485void dump_cache(int debug, int cache_size) 486{ 487 syslog(LOG_INFO, 488 "Cache size %d, %d/%d cache insertions re-used unexpired cache entries.\n", 489 cache_size, cache_live_freed, cache_inserted); 490 491 if (debug) 492 { 493 struct crec *cache ; 494#ifdef HAVE_IPV6 495 char addrbuff[INET6_ADDRSTRLEN]; 496#else 497 char addrbuff[INET_ADDRSTRLEN]; 498#endif 499 syslog(LOG_DEBUG, 500 "Host Address Flags Expires\n"); 501 502 for(cache = cache_head ; cache ; cache = cache->next) 503 if (cache->flags & (F_FORWARD | F_REVERSE)) 504 { 505 if (cache->flags & F_NEG) 506 addrbuff[0] = 0; 507 else if (cache->flags & F_IPV4) 508 inet_ntop(AF_INET, &cache->addr, addrbuff, INET_ADDRSTRLEN); 509#ifdef HAVE_IPV6 510 else if (cache->flags & F_IPV6) 511 inet_ntop(AF_INET6, &cache->addr, addrbuff, INET6_ADDRSTRLEN); 512#endif 513 syslog(LOG_DEBUG, 514 "%-28.28s %-16.16s %s%s%s%s%s%s%s%s %s", 515 cache_get_name(cache), addrbuff, 516 cache->flags & F_IPV4 ? "4" : "", 517 cache->flags & F_IPV6 ? "6" : "", 518 cache->flags & F_FORWARD ? "F" : " ", 519 cache->flags & F_REVERSE ? "R" : " ", 520 cache->flags & F_IMMORTAL ? "I" : " ", 521 cache->flags & F_DHCP ? "D" : " ", 522 cache->flags & F_NEG ? "N" : " ", 523 cache->flags & F_HOSTS ? "H" : " ", 524 cache->flags & F_IMMORTAL ? "\n" : ctime(&(cache->ttd))) ; 525 } 526 } 527} 528 529 530void log_query(int flags, char *name, struct all_addr *addr) 531{ 532 char *source; 533 char *verb = "is"; 534 535#ifdef HAVE_IPV6 536 char addrbuff[INET6_ADDRSTRLEN]; 537#else 538 char addrbuff[INET_ADDRSTRLEN]; 539#endif 540 541 if (!log_queries) 542 return; 543 544 if (flags & F_IPV4) 545 { 546 if (addr) 547 inet_ntop(AF_INET, addr, addrbuff, INET_ADDRSTRLEN); 548 else 549 strcpy(addrbuff, "<unknown>-IPv4"); 550 } 551#ifdef HAVE_IPV6 552 else if (flags & F_IPV6) 553 { 554 if (addr) 555 inet_ntop(AF_INET6, addr, addrbuff, INET6_ADDRSTRLEN); 556 else 557 strcpy(addrbuff, "<unknown>-IPv6"); 558 } 559#endif 560 561 if (flags & F_DHCP) 562 source = "DHCP"; 563#ifdef HAVE_FILE_SYSTEM 564 else if (flags & F_HOSTS) 565 source = HOSTSFILE; 566#endif 567 else if (flags & F_UPSTREAM) 568 source = "reply"; 569 else if (flags & F_SERVER) 570 { 571 source = "forwarded"; 572 verb = "to"; 573 } 574 else 575 source = "cached"; 576 577 if (flags & F_FORWARD) 578 syslog(LOG_INFO, "%s %s %s %s\n", source, name, verb, addrbuff); 579 else if (flags & F_REVERSE) 580 syslog(LOG_INFO, "%s %s is %s\n", source, addrbuff, name); 581} 582 583 584