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