am 2d94ee29: Merge "Revert "Revert "Hide _tolower_tab_ and _toupper_tab_ on LP64."""
[android-sdk/platform-bionic.git] / libc / dns / resolv / res_cache.c
1 /*
2  * Copyright (C) 2008 The Android Open Source Project
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *  * Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *  * Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in
12  *    the documentation and/or other materials provided with the
13  *    distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26  * SUCH DAMAGE.
27  */
29 #include "resolv_cache.h"
30 #include <resolv.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <time.h>
34 #include "pthread.h"
36 #include <errno.h>
37 #include <arpa/nameser.h>
38 #include <sys/system_properties.h>
39 #include <net/if.h>
40 #include <netdb.h>
41 #include <linux/if.h>
43 #include <arpa/inet.h>
44 #include "resolv_private.h"
45 #include "resolv_netid.h"
46 #include "res_private.h"
48 /* This code implements a small and *simple* DNS resolver cache.
49  *
50  * It is only used to cache DNS answers for a time defined by the smallest TTL
51  * among the answer records in order to reduce DNS traffic. It is not supposed
52  * to be a full DNS cache, since we plan to implement that in the future in a
53  * dedicated process running on the system.
54  *
55  * Note that its design is kept simple very intentionally, i.e.:
56  *
57  *  - it takes raw DNS query packet data as input, and returns raw DNS
58  *    answer packet data as output
59  *
60  *    (this means that two similar queries that encode the DNS name
61  *     differently will be treated distinctly).
62  *
63  *    the smallest TTL value among the answer records are used as the time
64  *    to keep an answer in the cache.
65  *
66  *    this is bad, but we absolutely want to avoid parsing the answer packets
67  *    (and should be solved by the later full DNS cache process).
68  *
69  *  - the implementation is just a (query-data) => (answer-data) hash table
70  *    with a trivial least-recently-used expiration policy.
71  *
72  * Doing this keeps the code simple and avoids to deal with a lot of things
73  * that a full DNS cache is expected to do.
74  *
75  * The API is also very simple:
76  *
77  *   - the client calls _resolv_cache_get() to obtain a handle to the cache.
78  *     this will initialize the cache on first usage. the result can be NULL
79  *     if the cache is disabled.
80  *
81  *   - the client calls _resolv_cache_lookup() before performing a query
82  *
83  *     if the function returns RESOLV_CACHE_FOUND, a copy of the answer data
84  *     has been copied into the client-provided answer buffer.
85  *
86  *     if the function returns RESOLV_CACHE_NOTFOUND, the client should perform
87  *     a request normally, *then* call _resolv_cache_add() to add the received
88  *     answer to the cache.
89  *
90  *     if the function returns RESOLV_CACHE_UNSUPPORTED, the client should
91  *     perform a request normally, and *not* call _resolv_cache_add()
92  *
93  *     note that RESOLV_CACHE_UNSUPPORTED is also returned if the answer buffer
94  *     is too short to accomodate the cached result.
95  */
97 /* the name of an environment variable that will be checked the first time
98  * this code is called if its value is "0", then the resolver cache is
99  * disabled.
100  */
101 #define  CONFIG_ENV  "BIONIC_DNSCACHE"
103 /* entries older than CONFIG_SECONDS seconds are always discarded.
104  */
105 #define  CONFIG_SECONDS    (60*10)    /* 10 minutes */
107 /* default number of entries kept in the cache. This value has been
108  * determined by browsing through various sites and counting the number
109  * of corresponding requests. Keep in mind that our framework is currently
110  * performing two requests per name lookup (one for IPv4, the other for IPv6)
111  *
112  *    www.google.com      4
113  *    www.ysearch.com     6
114  *    www.amazon.com      8
115  *    www.nytimes.com     22
116  *    www.espn.com        28
117  *    www.msn.com         28
118  *    www.lemonde.fr      35
119  *
120  * (determined in 2009-2-17 from Paris, France, results may vary depending
121  *  on location)
122  *
123  * most high-level websites use lots of media/ad servers with different names
124  * but these are generally reused when browsing through the site.
125  *
126  * As such, a value of 64 should be relatively comfortable at the moment.
127  *
128  * ******************************************
129  * * NOTE - this has changed.
130  * * 1) we've added IPv6 support so each dns query results in 2 responses
131  * * 2) we've made this a system-wide cache, so the cost is less (it's not
132  * *    duplicated in each process) and the need is greater (more processes
133  * *    making different requests).
134  * * Upping by 2x for IPv6
135  * * Upping by another 5x for the centralized nature
136  * *****************************************
137  */
138 #define  CONFIG_MAX_ENTRIES    64 * 2 * 5
139 /* name of the system property that can be used to set the cache size */
141 /****************************************************************************/
142 /****************************************************************************/
143 /*****                                                                  *****/
144 /*****                                                                  *****/
145 /*****                                                                  *****/
146 /****************************************************************************/
147 /****************************************************************************/
149 /* set to 1 to debug cache operations */
150 #define  DEBUG       0
152 /* set to 1 to debug query data */
153 #define  DEBUG_DATA  0
155 #undef XLOG
156 #if DEBUG
157 #  include "private/libc_logging.h"
158 #  define XLOG(...)  __libc_format_log(ANDROID_LOG_DEBUG,"libc",__VA_ARGS__)
160 #include <stdio.h>
161 #include <stdarg.h>
163 /** BOUNDED BUFFER FORMATTING
164  **/
166 /* technical note:
167  *
168  *   the following debugging routines are used to append data to a bounded
169  *   buffer they take two parameters that are:
170  *
171  *   - p : a pointer to the current cursor position in the buffer
172  *         this value is initially set to the buffer's address.
173  *
174  *   - end : the address of the buffer's limit, i.e. of the first byte
175  *           after the buffer. this address should never be touched.
176  *
177  *           IMPORTANT: it is assumed that end > buffer_address, i.e.
178  *                      that the buffer is at least one byte.
179  *
180  *   the _bprint_() functions return the new value of 'p' after the data
181  *   has been appended, and also ensure the following:
182  *
183  *   - the returned value will never be strictly greater than 'end'
184  *
185  *   - a return value equal to 'end' means that truncation occured
186  *     (in which case, end[-1] will be set to 0)
187  *
188  *   - after returning from a _bprint_() function, the content of the buffer
189  *     is always 0-terminated, even in the event of truncation.
190  *
191  *  these conventions allow you to call _bprint_ functions multiple times and
192  *  only check for truncation at the end of the sequence, as in:
193  *
194  *     char  buff[1000], *p = buff, *end = p + sizeof(buff);
195  *
196  *     p = _bprint_c(p, end, '"');
197  *     p = _bprint_s(p, end, my_string);
198  *     p = _bprint_c(p, end, '"');
199  *
200  *     if (p >= end) {
201  *        // buffer was too small
202  *     }
203  *
204  *     printf( "%s", buff );
205  */
207 /* add a char to a bounded buffer */
208 static char*
209 _bprint_c( char*  p, char*  end, int  c )
211     if (p < end) {
212         if (p+1 == end)
213             *p++ = 0;
214         else {
215             *p++ = (char) c;
216             *p   = 0;
217         }
218     }
219     return p;
222 /* add a sequence of bytes to a bounded buffer */
223 static char*
224 _bprint_b( char*  p, char*  end, const char*  buf, int  len )
226     int  avail = end - p;
228     if (avail <= 0 || len <= 0)
229         return p;
231     if (avail > len)
232         avail = len;
234     memcpy( p, buf, avail );
235     p += avail;
237     if (p < end)
238         p[0] = 0;
239     else
240         end[-1] = 0;
242     return p;
245 /* add a string to a bounded buffer */
246 static char*
247 _bprint_s( char*  p, char*  end, const char*  str )
249     return _bprint_b(p, end, str, strlen(str));
252 /* add a formatted string to a bounded buffer */
253 static char*
254 _bprint( char*  p, char*  end, const char*  format, ... )
256     int      avail, n;
257     va_list  args;
259     avail = end - p;
261     if (avail <= 0)
262         return p;
264     va_start(args, format);
265     n = vsnprintf( p, avail, format, args);
266     va_end(args);
268     /* certain C libraries return -1 in case of truncation */
269     if (n < 0 || n > avail)
270         n = avail;
272     p += n;
273     /* certain C libraries do not zero-terminate in case of truncation */
274     if (p == end)
275         p[-1] = 0;
277     return p;
280 /* add a hex value to a bounded buffer, up to 8 digits */
281 static char*
282 _bprint_hex( char*  p, char*  end, unsigned  value, int  numDigits )
284     char   text[sizeof(unsigned)*2];
285     int    nn = 0;
287     while (numDigits-- > 0) {
288         text[nn++] = "0123456789abcdef"[(value >> (numDigits*4)) & 15];
289     }
290     return _bprint_b(p, end, text, nn);
293 /* add the hexadecimal dump of some memory area to a bounded buffer */
294 static char*
295 _bprint_hexdump( char*  p, char*  end, const uint8_t*  data, int  datalen )
297     int   lineSize = 16;
299     while (datalen > 0) {
300         int  avail = datalen;
301         int  nn;
303         if (avail > lineSize)
304             avail = lineSize;
306         for (nn = 0; nn < avail; nn++) {
307             if (nn > 0)
308                 p = _bprint_c(p, end, ' ');
309             p = _bprint_hex(p, end, data[nn], 2);
310         }
311         for ( ; nn < lineSize; nn++ ) {
312             p = _bprint_s(p, end, "   ");
313         }
314         p = _bprint_s(p, end, "  ");
316         for (nn = 0; nn < avail; nn++) {
317             int  c = data[nn];
319             if (c < 32 || c > 127)
320                 c = '.';
322             p = _bprint_c(p, end, c);
323         }
324         p = _bprint_c(p, end, '\n');
326         data    += avail;
327         datalen -= avail;
328     }
329     return p;
332 /* dump the content of a query of packet to the log */
333 static void
334 XLOG_BYTES( const void*  base, int  len )
336     char  buff[1024];
337     char*  p = buff, *end = p + sizeof(buff);
339     p = _bprint_hexdump(p, end, base, len);
340     XLOG("%s",buff);
343 #else /* !DEBUG */
344 #  define  XLOG(...)        ((void)0)
345 #  define  XLOG_BYTES(a,b)  ((void)0)
346 #endif
348 static time_t
349 _time_now( void )
351     struct timeval  tv;
353     gettimeofday( &tv, NULL );
354     return tv.tv_sec;
357 /* reminder: the general format of a DNS packet is the following:
358  *
359  *    HEADER  (12 bytes)
360  *    QUESTION  (variable)
361  *    ANSWER (variable)
362  *    AUTHORITY (variable)
363  *    ADDITIONNAL (variable)
364  *
365  * the HEADER is made of:
366  *
367  *   ID     : 16 : 16-bit unique query identification field
368  *
369  *   QR     :  1 : set to 0 for queries, and 1 for responses
370  *   Opcode :  4 : set to 0 for queries
371  *   AA     :  1 : set to 0 for queries
372  *   TC     :  1 : truncation flag, will be set to 0 in queries
373  *   RD     :  1 : recursion desired
374  *
375  *   RA     :  1 : recursion available (0 in queries)
376  *   Z      :  3 : three reserved zero bits
377  *   RCODE  :  4 : response code (always 0=NOERROR in queries)
378  *
379  *   QDCount: 16 : question count
380  *   ANCount: 16 : Answer count (0 in queries)
381  *   NSCount: 16: Authority Record count (0 in queries)
382  *   ARCount: 16: Additionnal Record count (0 in queries)
383  *
384  * the QUESTION is made of QDCount Question Record (QRs)
385  * the ANSWER is made of ANCount RRs
386  * the AUTHORITY is made of NSCount RRs
387  * the ADDITIONNAL is made of ARCount RRs
388  *
389  * Each Question Record (QR) is made of:
390  *
391  *   QNAME   : variable : Query DNS NAME
392  *   TYPE    : 16       : type of query (A=1, PTR=12, MX=15, AAAA=28, ALL=255)
393  *   CLASS   : 16       : class of query (IN=1)
394  *
395  * Each Resource Record (RR) is made of:
396  *
397  *   NAME    : variable : DNS NAME
398  *   TYPE    : 16       : type of query (A=1, PTR=12, MX=15, AAAA=28, ALL=255)
399  *   CLASS   : 16       : class of query (IN=1)
400  *   TTL     : 32       : seconds to cache this RR (0=none)
401  *   RDLENGTH: 16       : size of RDDATA in bytes
402  *   RDDATA  : variable : RR data (depends on TYPE)
403  *
404  * Each QNAME contains a domain name encoded as a sequence of 'labels'
405  * terminated by a zero. Each label has the following format:
406  *
407  *    LEN  : 8     : lenght of label (MUST be < 64)
408  *    NAME : 8*LEN : label length (must exclude dots)
409  *
410  * A value of 0 in the encoding is interpreted as the 'root' domain and
411  * terminates the encoding. So 'www.android.com' will be encoded as:
412  *
413  *   <3>www<7>android<3>com<0>
414  *
415  * Where <n> represents the byte with value 'n'
416  *
417  * Each NAME reflects the QNAME of the question, but has a slightly more
418  * complex encoding in order to provide message compression. This is achieved
419  * by using a 2-byte pointer, with format:
420  *
421  *    TYPE   : 2  : 0b11 to indicate a pointer, 0b01 and 0b10 are reserved
422  *    OFFSET : 14 : offset to another part of the DNS packet
423  *
424  * The offset is relative to the start of the DNS packet and must point
425  * A pointer terminates the encoding.
426  *
427  * The NAME can be encoded in one of the following formats:
428  *
429  *   - a sequence of simple labels terminated by 0 (like QNAMEs)
430  *   - a single pointer
431  *   - a sequence of simple labels terminated by a pointer
432  *
433  * A pointer shall always point to either a pointer of a sequence of
434  * labels (which can themselves be terminated by either a 0 or a pointer)
435  *
436  * The expanded length of a given domain name should not exceed 255 bytes.
437  *
438  * NOTE: we don't parse the answer packets, so don't need to deal with NAME
439  *       records, only QNAMEs.
440  */
442 #define  DNS_HEADER_SIZE  12
444 #define  DNS_TYPE_A   "\00\01"   /* big-endian decimal 1 */
445 #define  DNS_TYPE_PTR "\00\014"  /* big-endian decimal 12 */
446 #define  DNS_TYPE_MX  "\00\017"  /* big-endian decimal 15 */
447 #define  DNS_TYPE_AAAA "\00\034" /* big-endian decimal 28 */
448 #define  DNS_TYPE_ALL "\00\0377" /* big-endian decimal 255 */
450 #define  DNS_CLASS_IN "\00\01"   /* big-endian decimal 1 */
452 typedef struct {
453     const uint8_t*  base;
454     const uint8_t*  end;
455     const uint8_t*  cursor;
456 } DnsPacket;
458 static void
459 _dnsPacket_init( DnsPacket*  packet, const uint8_t*  buff, int  bufflen )
461     packet->base   = buff;
462     packet->end    = buff + bufflen;
463     packet->cursor = buff;
466 static void
467 _dnsPacket_rewind( DnsPacket*  packet )
469     packet->cursor = packet->base;
472 static void
473 _dnsPacket_skip( DnsPacket*  packet, int  count )
475     const uint8_t*  p = packet->cursor + count;
477     if (p > packet->end)
478         p = packet->end;
480     packet->cursor = p;
483 static int
484 _dnsPacket_readInt16( DnsPacket*  packet )
486     const uint8_t*  p = packet->cursor;
488     if (p+2 > packet->end)
489         return -1;
491     packet->cursor = p+2;
492     return (p[0]<< 8) | p[1];
495 /** QUERY CHECKING
496  **/
498 /* check bytes in a dns packet. returns 1 on success, 0 on failure.
499  * the cursor is only advanced in the case of success
500  */
501 static int
502 _dnsPacket_checkBytes( DnsPacket*  packet, int  numBytes, const void*  bytes )
504     const uint8_t*  p = packet->cursor;
506     if (p + numBytes > packet->end)
507         return 0;
509     if (memcmp(p, bytes, numBytes) != 0)
510         return 0;
512     packet->cursor = p + numBytes;
513     return 1;
516 /* parse and skip a given QNAME stored in a query packet,
517  * from the current cursor position. returns 1 on success,
518  * or 0 for malformed data.
519  */
520 static int
521 _dnsPacket_checkQName( DnsPacket*  packet )
523     const uint8_t*  p   = packet->cursor;
524     const uint8_t*  end = packet->end;
526     for (;;) {
527         int  c;
529         if (p >= end)
530             break;
532         c = *p++;
534         if (c == 0) {
535             packet->cursor = p;
536             return 1;
537         }
539         /* we don't expect label compression in QNAMEs */
540         if (c >= 64)
541             break;
543         p += c;
544         /* we rely on the bound check at the start
545          * of the loop here */
546     }
547     /* malformed data */
548     XLOG("malformed QNAME");
549     return 0;
552 /* parse and skip a given QR stored in a packet.
553  * returns 1 on success, and 0 on failure
554  */
555 static int
556 _dnsPacket_checkQR( DnsPacket*  packet )
558     if (!_dnsPacket_checkQName(packet))
559         return 0;
561     /* TYPE must be one of the things we support */
562     if (!_dnsPacket_checkBytes(packet, 2, DNS_TYPE_A) &&
563         !_dnsPacket_checkBytes(packet, 2, DNS_TYPE_PTR) &&
564         !_dnsPacket_checkBytes(packet, 2, DNS_TYPE_MX) &&
565         !_dnsPacket_checkBytes(packet, 2, DNS_TYPE_AAAA) &&
566         !_dnsPacket_checkBytes(packet, 2, DNS_TYPE_ALL))
567     {
568         XLOG("unsupported TYPE");
569         return 0;
570     }
571     /* CLASS must be IN */
572     if (!_dnsPacket_checkBytes(packet, 2, DNS_CLASS_IN)) {
573         XLOG("unsupported CLASS");
574         return 0;
575     }
577     return 1;
580 /* check the header of a DNS Query packet, return 1 if it is one
581  * type of query we can cache, or 0 otherwise
582  */
583 static int
584 _dnsPacket_checkQuery( DnsPacket*  packet )
586     const uint8_t*  p = packet->base;
587     int             qdCount, anCount, dnCount, arCount;
589     if (p + DNS_HEADER_SIZE > packet->end) {
590         XLOG("query packet too small");
591         return 0;
592     }
594     /* QR must be set to 0, opcode must be 0 and AA must be 0 */
595     /* RA, Z, and RCODE must be 0 */
596     if ((p[2] & 0xFC) != 0 || p[3] != 0) {
597         XLOG("query packet flags unsupported");
598         return 0;
599     }
601     /* Note that we ignore the TC and RD bits here for the
602      * following reasons:
603      *
604      * - there is no point for a query packet sent to a server
605      *   to have the TC bit set, but the implementation might
606      *   set the bit in the query buffer for its own needs
607      *   between a _resolv_cache_lookup and a
608      *   _resolv_cache_add. We should not freak out if this
609      *   is the case.
610      *
611      * - we consider that the result from a RD=0 or a RD=1
612      *   query might be different, hence that the RD bit
613      *   should be used to differentiate cached result.
614      *
615      *   this implies that RD is checked when hashing or
616      *   comparing query packets, but not TC
617      */
619     /* ANCOUNT, DNCOUNT and ARCOUNT must be 0 */
620     qdCount = (p[4] << 8) | p[5];
621     anCount = (p[6] << 8) | p[7];
622     dnCount = (p[8] << 8) | p[9];
623     arCount = (p[10]<< 8) | p[11];
625     if (anCount != 0 || dnCount != 0 || arCount != 0) {
626         XLOG("query packet contains non-query records");
627         return 0;
628     }
630     if (qdCount == 0) {
631         XLOG("query packet doesn't contain query record");
632         return 0;
633     }
635     /* Check QDCOUNT QRs */
636     packet->cursor = p + DNS_HEADER_SIZE;
638     for (;qdCount > 0; qdCount--)
639         if (!_dnsPacket_checkQR(packet))
640             return 0;
642     return 1;
645 /** QUERY DEBUGGING
646  **/
647 #if DEBUG
648 static char*
649 _dnsPacket_bprintQName(DnsPacket*  packet, char*  bp, char*  bend)
651     const uint8_t*  p   = packet->cursor;
652     const uint8_t*  end = packet->end;
653     int             first = 1;
655     for (;;) {
656         int  c;
658         if (p >= end)
659             break;
661         c = *p++;
663         if (c == 0) {
664             packet->cursor = p;
665             return bp;
666         }
668         /* we don't expect label compression in QNAMEs */
669         if (c >= 64)
670             break;
672         if (first)
673             first = 0;
674         else
675             bp = _bprint_c(bp, bend, '.');
677         bp = _bprint_b(bp, bend, (const char*)p, c);
679         p += c;
680         /* we rely on the bound check at the start
681          * of the loop here */
682     }
683     /* malformed data */
684     bp = _bprint_s(bp, bend, "<MALFORMED>");
685     return bp;
688 static char*
689 _dnsPacket_bprintQR(DnsPacket*  packet, char*  p, char*  end)
691 #define  QQ(x)   { DNS_TYPE_##x, #x }
692     static const struct {
693         const char*  typeBytes;
694         const char*  typeString;
695     } qTypes[] =
696     {
697         QQ(A), QQ(PTR), QQ(MX), QQ(AAAA), QQ(ALL),
698         { NULL, NULL }
699     };
700     int          nn;
701     const char*  typeString = NULL;
703     /* dump QNAME */
704     p = _dnsPacket_bprintQName(packet, p, end);
706     /* dump TYPE */
707     p = _bprint_s(p, end, " (");
709     for (nn = 0; qTypes[nn].typeBytes != NULL; nn++) {
710         if (_dnsPacket_checkBytes(packet, 2, qTypes[nn].typeBytes)) {
711             typeString = qTypes[nn].typeString;
712             break;
713         }
714     }
716     if (typeString != NULL)
717         p = _bprint_s(p, end, typeString);
718     else {
719         int  typeCode = _dnsPacket_readInt16(packet);
720         p = _bprint(p, end, "UNKNOWN-%d", typeCode);
721     }
723     p = _bprint_c(p, end, ')');
725     /* skip CLASS */
726     _dnsPacket_skip(packet, 2);
727     return p;
730 /* this function assumes the packet has already been checked */
731 static char*
732 _dnsPacket_bprintQuery( DnsPacket*  packet, char*  p, char*  end )
734     int   qdCount;
736     if (packet->base[2] & 0x1) {
737         p = _bprint_s(p, end, "RECURSIVE ");
738     }
740     _dnsPacket_skip(packet, 4);
741     qdCount = _dnsPacket_readInt16(packet);
742     _dnsPacket_skip(packet, 6);
744     for ( ; qdCount > 0; qdCount-- ) {
745         p = _dnsPacket_bprintQR(packet, p, end);
746     }
747     return p;
749 #endif
752 /** QUERY HASHING SUPPORT
753  **
754  ** THE FOLLOWING CODE ASSUMES THAT THE INPUT PACKET HAS ALREADY
755  ** BEEN SUCCESFULLY CHECKED.
756  **/
758 /* use 32-bit FNV hash function */
759 #define  FNV_MULT   16777619U
760 #define  FNV_BASIS  2166136261U
762 static unsigned
763 _dnsPacket_hashBytes( DnsPacket*  packet, int  numBytes, unsigned  hash )
765     const uint8_t*  p   = packet->cursor;
766     const uint8_t*  end = packet->end;
768     while (numBytes > 0 && p < end) {
769         hash = hash*FNV_MULT ^ *p++;
770     }
771     packet->cursor = p;
772     return hash;
776 static unsigned
777 _dnsPacket_hashQName( DnsPacket*  packet, unsigned  hash )
779     const uint8_t*  p   = packet->cursor;
780     const uint8_t*  end = packet->end;
782     for (;;) {
783         int  c;
785         if (p >= end) {  /* should not happen */
786             XLOG("%s: INTERNAL_ERROR: read-overflow !!\n", __FUNCTION__);
787             break;
788         }
790         c = *p++;
792         if (c == 0)
793             break;
795         if (c >= 64) {
796             XLOG("%s: INTERNAL_ERROR: malformed domain !!\n", __FUNCTION__);
797             break;
798         }
799         if (p + c >= end) {
800             XLOG("%s: INTERNAL_ERROR: simple label read-overflow !!\n",
801                     __FUNCTION__);
802             break;
803         }
804         while (c > 0) {
805             hash = hash*FNV_MULT ^ *p++;
806             c   -= 1;
807         }
808     }
809     packet->cursor = p;
810     return hash;
813 static unsigned
814 _dnsPacket_hashQR( DnsPacket*  packet, unsigned  hash )
816     hash = _dnsPacket_hashQName(packet, hash);
817     hash = _dnsPacket_hashBytes(packet, 4, hash); /* TYPE and CLASS */
818     return hash;
821 static unsigned
822 _dnsPacket_hashQuery( DnsPacket*  packet )
824     unsigned  hash = FNV_BASIS;
825     int       count;
826     _dnsPacket_rewind(packet);
828     /* we ignore the TC bit for reasons explained in
829      * _dnsPacket_checkQuery().
830      *
831      * however we hash the RD bit to differentiate
832      * between answers for recursive and non-recursive
833      * queries.
834      */
835     hash = hash*FNV_MULT ^ (packet->base[2] & 1);
837     /* assume: other flags are 0 */
838     _dnsPacket_skip(packet, 4);
840     /* read QDCOUNT */
841     count = _dnsPacket_readInt16(packet);
843     /* assume: ANcount, NScount, ARcount are 0 */
844     _dnsPacket_skip(packet, 6);
846     /* hash QDCOUNT QRs */
847     for ( ; count > 0; count-- )
848         hash = _dnsPacket_hashQR(packet, hash);
850     return hash;
854 /** QUERY COMPARISON
855  **
856  ** THE FOLLOWING CODE ASSUMES THAT THE INPUT PACKETS HAVE ALREADY
857  ** BEEN SUCCESFULLY CHECKED.
858  **/
860 static int
861 _dnsPacket_isEqualDomainName( DnsPacket*  pack1, DnsPacket*  pack2 )
863     const uint8_t*  p1   = pack1->cursor;
864     const uint8_t*  end1 = pack1->end;
865     const uint8_t*  p2   = pack2->cursor;
866     const uint8_t*  end2 = pack2->end;
868     for (;;) {
869         int  c1, c2;
871         if (p1 >= end1 || p2 >= end2) {
872             XLOG("%s: INTERNAL_ERROR: read-overflow !!\n", __FUNCTION__);
873             break;
874         }
875         c1 = *p1++;
876         c2 = *p2++;
877         if (c1 != c2)
878             break;
880         if (c1 == 0) {
881             pack1->cursor = p1;
882             pack2->cursor = p2;
883             return 1;
884         }
885         if (c1 >= 64) {
886             XLOG("%s: INTERNAL_ERROR: malformed domain !!\n", __FUNCTION__);
887             break;
888         }
889         if ((p1+c1 > end1) || (p2+c1 > end2)) {
890             XLOG("%s: INTERNAL_ERROR: simple label read-overflow !!\n",
891                     __FUNCTION__);
892             break;
893         }
894         if (memcmp(p1, p2, c1) != 0)
895             break;
896         p1 += c1;
897         p2 += c1;
898         /* we rely on the bound checks at the start of the loop */
899     }
900     /* not the same, or one is malformed */
901     XLOG("different DN");
902     return 0;
905 static int
906 _dnsPacket_isEqualBytes( DnsPacket*  pack1, DnsPacket*  pack2, int  numBytes )
908     const uint8_t*  p1 = pack1->cursor;
909     const uint8_t*  p2 = pack2->cursor;
911     if ( p1 + numBytes > pack1->end || p2 + numBytes > pack2->end )
912         return 0;
914     if ( memcmp(p1, p2, numBytes) != 0 )
915         return 0;
917     pack1->cursor += numBytes;
918     pack2->cursor += numBytes;
919     return 1;
922 static int
923 _dnsPacket_isEqualQR( DnsPacket*  pack1, DnsPacket*  pack2 )
925     /* compare domain name encoding + TYPE + CLASS */
926     if ( !_dnsPacket_isEqualDomainName(pack1, pack2) ||
927          !_dnsPacket_isEqualBytes(pack1, pack2, 2+2) )
928         return 0;
930     return 1;
933 static int
934 _dnsPacket_isEqualQuery( DnsPacket*  pack1, DnsPacket*  pack2 )
936     int  count1, count2;
938     /* compare the headers, ignore most fields */
939     _dnsPacket_rewind(pack1);
940     _dnsPacket_rewind(pack2);
942     /* compare RD, ignore TC, see comment in _dnsPacket_checkQuery */
943     if ((pack1->base[2] & 1) != (pack2->base[2] & 1)) {
944         XLOG("different RD");
945         return 0;
946     }
948     /* assume: other flags are all 0 */
949     _dnsPacket_skip(pack1, 4);
950     _dnsPacket_skip(pack2, 4);
952     /* compare QDCOUNT */
953     count1 = _dnsPacket_readInt16(pack1);
954     count2 = _dnsPacket_readInt16(pack2);
955     if (count1 != count2 || count1 < 0) {
956         XLOG("different QDCOUNT");
957         return 0;
958     }
960     /* assume: ANcount, NScount and ARcount are all 0 */
961     _dnsPacket_skip(pack1, 6);
962     _dnsPacket_skip(pack2, 6);
964     /* compare the QDCOUNT QRs */
965     for ( ; count1 > 0; count1-- ) {
966         if (!_dnsPacket_isEqualQR(pack1, pack2)) {
967             XLOG("different QR");
968             return 0;
969         }
970     }
971     return 1;
974 /****************************************************************************/
975 /****************************************************************************/
976 /*****                                                                  *****/
977 /*****                                                                  *****/
978 /*****                                                                  *****/
979 /****************************************************************************/
980 /****************************************************************************/
982 /* cache entry. for simplicity, 'hash' and 'hlink' are inlined in this
983  * structure though they are conceptually part of the hash table.
984  *
985  * similarly, mru_next and mru_prev are part of the global MRU list
986  */
987 typedef struct Entry {
988     unsigned int     hash;   /* hash value */
989     struct Entry*    hlink;  /* next in collision chain */
990     struct Entry*    mru_prev;
991     struct Entry*    mru_next;
993     const uint8_t*   query;
994     int              querylen;
995     const uint8_t*   answer;
996     int              answerlen;
997     time_t           expires;   /* time_t when the entry isn't valid any more */
998     int              id;        /* for debugging purpose */
999 } Entry;
1001 /**
1002  * Find the TTL for a negative DNS result.  This is defined as the minimum
1003  * of the SOA records TTL and the MINIMUM-TTL field (RFC-2308).
1004  *
1005  * Return 0 if not found.
1006  */
1007 static u_long
1008 answer_getNegativeTTL(ns_msg handle) {
1009     int n, nscount;
1010     u_long result = 0;
1011     ns_rr rr;
1013     nscount = ns_msg_count(handle, ns_s_ns);
1014     for (n = 0; n < nscount; n++) {
1015         if ((ns_parserr(&handle, ns_s_ns, n, &rr) == 0) && (ns_rr_type(rr) == ns_t_soa)) {
1016             const u_char *rdata = ns_rr_rdata(rr); // find the data
1017             const u_char *edata = rdata + ns_rr_rdlen(rr); // add the len to find the end
1018             int len;
1019             u_long ttl, rec_result = ns_rr_ttl(rr);
1021             // find the MINIMUM-TTL field from the blob of binary data for this record
1022             // skip the server name
1023             len = dn_skipname(rdata, edata);
1024             if (len == -1) continue; // error skipping
1025             rdata += len;
1027             // skip the admin name
1028             len = dn_skipname(rdata, edata);
1029             if (len == -1) continue; // error skipping
1030             rdata += len;
1032             if (edata - rdata != 5*NS_INT32SZ) continue;
1033             // skip: serial number + refresh interval + retry interval + expiry
1034             rdata += NS_INT32SZ * 4;
1035             // finally read the MINIMUM TTL
1036             ttl = ns_get32(rdata);
1037             if (ttl < rec_result) {
1038                 rec_result = ttl;
1039             }
1040             // Now that the record is read successfully, apply the new min TTL
1041             if (n == 0 || rec_result < result) {
1042                 result = rec_result;
1043             }
1044         }
1045     }
1046     return result;
1049 /**
1050  * Parse the answer records and find the appropriate
1051  * smallest TTL among the records.  This might be from
1052  * the answer records if found or from the SOA record
1053  * if it's a negative result.
1054  *
1055  * The returned TTL is the number of seconds to
1056  * keep the answer in the cache.
1057  *
1058  * In case of parse error zero (0) is returned which
1059  * indicates that the answer shall not be cached.
1060  */
1061 static u_long
1062 answer_getTTL(const void* answer, int answerlen)
1064     ns_msg handle;
1065     int ancount, n;
1066     u_long result, ttl;
1067     ns_rr rr;
1069     result = 0;
1070     if (ns_initparse(answer, answerlen, &handle) >= 0) {
1071         // get number of answer records
1072         ancount = ns_msg_count(handle, ns_s_an);
1074         if (ancount == 0) {
1075             // a response with no answers?  Cache this negative result.
1076             result = answer_getNegativeTTL(handle);
1077         } else {
1078             for (n = 0; n < ancount; n++) {
1079                 if (ns_parserr(&handle, ns_s_an, n, &rr) == 0) {
1080                     ttl = ns_rr_ttl(rr);
1081                     if (n == 0 || ttl < result) {
1082                         result = ttl;
1083                     }
1084                 } else {
1085                     XLOG("ns_parserr failed ancount no = %d. errno = %s\n", n, strerror(errno));
1086                 }
1087             }
1088         }
1089     } else {
1090         XLOG("ns_parserr failed. %s\n", strerror(errno));
1091     }
1093     XLOG("TTL = %d\n", result);
1095     return result;
1098 static void
1099 entry_free( Entry*  e )
1101     /* everything is allocated in a single memory block */
1102     if (e) {
1103         free(e);
1104     }
1107 static __inline__ void
1108 entry_mru_remove( Entry*  e )
1110     e->mru_prev->mru_next = e->mru_next;
1111     e->mru_next->mru_prev = e->mru_prev;
1114 static __inline__ void
1115 entry_mru_add( Entry*  e, Entry*  list )
1117     Entry*  first = list->mru_next;
1119     e->mru_next = first;
1120     e->mru_prev = list;
1122     list->mru_next  = e;
1123     first->mru_prev = e;
1126 /* compute the hash of a given entry, this is a hash of most
1127  * data in the query (key) */
1128 static unsigned
1129 entry_hash( const Entry*  e )
1131     DnsPacket  pack[1];
1133     _dnsPacket_init(pack, e->query, e->querylen);
1134     return _dnsPacket_hashQuery(pack);
1137 /* initialize an Entry as a search key, this also checks the input query packet
1138  * returns 1 on success, or 0 in case of unsupported/malformed data */
1139 static int
1140 entry_init_key( Entry*  e, const void*  query, int  querylen )
1142     DnsPacket  pack[1];
1144     memset(e, 0, sizeof(*e));
1146     e->query    = query;
1147     e->querylen = querylen;
1148     e->hash     = entry_hash(e);
1150     _dnsPacket_init(pack, query, querylen);
1152     return _dnsPacket_checkQuery(pack);
1155 /* allocate a new entry as a cache node */
1156 static Entry*
1157 entry_alloc( const Entry*  init, const void*  answer, int  answerlen )
1159     Entry*  e;
1160     int     size;
1162     size = sizeof(*e) + init->querylen + answerlen;
1163     e    = calloc(size, 1);
1164     if (e == NULL)
1165         return e;
1167     e->hash     = init->hash;
1168     e->query    = (const uint8_t*)(e+1);
1169     e->querylen = init->querylen;
1171     memcpy( (char*)e->query, init->query, e->querylen );
1173     e->answer    = e->query + e->querylen;
1174     e->answerlen = answerlen;
1176     memcpy( (char*)e->answer, answer, e->answerlen );
1178     return e;
1181 static int
1182 entry_equals( const Entry*  e1, const Entry*  e2 )
1184     DnsPacket  pack1[1], pack2[1];
1186     if (e1->querylen != e2->querylen) {
1187         return 0;
1188     }
1189     _dnsPacket_init(pack1, e1->query, e1->querylen);
1190     _dnsPacket_init(pack2, e2->query, e2->querylen);
1192     return _dnsPacket_isEqualQuery(pack1, pack2);
1195 /****************************************************************************/
1196 /****************************************************************************/
1197 /*****                                                                  *****/
1198 /*****                                                                  *****/
1199 /*****                                                                  *****/
1200 /****************************************************************************/
1201 /****************************************************************************/
1203 /* We use a simple hash table with external collision lists
1204  * for simplicity, the hash-table fields 'hash' and 'hlink' are
1205  * inlined in the Entry structure.
1206  */
1208 /* Maximum time for a thread to wait for an pending request */
1209 #define PENDING_REQUEST_TIMEOUT 20;
1211 typedef struct pending_req_info {
1212     unsigned int                hash;
1213     pthread_cond_t              cond;
1214     struct pending_req_info*    next;
1215 } PendingReqInfo;
1217 typedef struct resolv_cache {
1218     int              max_entries;
1219     int              num_entries;
1220     Entry            mru_list;
1221     pthread_mutex_t  lock;
1222     int              last_id;
1223     Entry*           entries;
1224     PendingReqInfo   pending_requests;
1225 } Cache;
1227 struct resolv_cache_info {
1228     unsigned                    netid;
1229     Cache*                      cache;
1230     struct resolv_cache_info*   next;
1231     char*                       nameservers[MAXNS +1];
1232     struct addrinfo*            nsaddrinfo[MAXNS + 1];
1233     char                        defdname[256];
1234     int                         dnsrch_offset[MAXDNSRCH+1];  // offsets into defdname
1235 };
1237 #define  HTABLE_VALID(x)  ((x) != NULL && (x) != HTABLE_DELETED)
1239 static void
1240 _cache_flush_pending_requests_locked( struct resolv_cache* cache )
1242     struct pending_req_info *ri, *tmp;
1243     if (cache) {
1244         ri = cache->pending_requests.next;
1246         while (ri) {
1247             tmp = ri;
1248             ri = ri->next;
1249             pthread_cond_broadcast(&tmp->cond);
1251             pthread_cond_destroy(&tmp->cond);
1252             free(tmp);
1253         }
1255         cache->pending_requests.next = NULL;
1256     }
1259 /* return 0 if no pending request is found matching the key
1260  * if a matching request is found the calling thread will wait
1261  * and return 1 when released */
1262 static int
1263 _cache_check_pending_request_locked( struct resolv_cache* cache, Entry* key )
1265     struct pending_req_info *ri, *prev;
1266     int exist = 0;
1268     if (cache && key) {
1269         ri = cache->pending_requests.next;
1270         prev = &cache->pending_requests;
1271         while (ri) {
1272             if (ri->hash == key->hash) {
1273                 exist = 1;
1274                 break;
1275             }
1276             prev = ri;
1277             ri = ri->next;
1278         }
1280         if (!exist) {
1281             ri = calloc(1, sizeof(struct pending_req_info));
1282             if (ri) {
1283                 ri->hash = key->hash;
1284                 pthread_cond_init(&ri->cond, NULL);
1285                 prev->next = ri;
1286             }
1287         } else {
1288             struct timespec ts = {0,0};
1289             XLOG("Waiting for previous request");
1290             ts.tv_sec = _time_now() + PENDING_REQUEST_TIMEOUT;
1291             pthread_cond_timedwait(&ri->cond, &cache->lock, &ts);
1292         }
1293     }
1295     return exist;
1298 /* notify any waiting thread that waiting on a request
1299  * matching the key has been added to the cache */
1300 static void
1301 _cache_notify_waiting_tid_locked( struct resolv_cache* cache, Entry* key )
1303     struct pending_req_info *ri, *prev;
1305     if (cache && key) {
1306         ri = cache->pending_requests.next;
1307         prev = &cache->pending_requests;
1308         while (ri) {
1309             if (ri->hash == key->hash) {
1310                 pthread_cond_broadcast(&ri->cond);
1311                 break;
1312             }
1313             prev = ri;
1314             ri = ri->next;
1315         }
1317         // remove item from list and destroy
1318         if (ri) {
1319             prev->next = ri->next;
1320             pthread_cond_destroy(&ri->cond);
1321             free(ri);
1322         }
1323     }
1326 /* notify the cache that the query failed */
1327 void
1328 _resolv_cache_query_failed( struct resolv_cache* cache,
1329                    const void* query,
1330                    int         querylen)
1332     Entry    key[1];
1334     if (cache && entry_init_key(key, query, querylen)) {
1335         pthread_mutex_lock(&cache->lock);
1336         _cache_notify_waiting_tid_locked(cache, key);
1337         pthread_mutex_unlock(&cache->lock);
1338     }
1341 static void
1342 _cache_flush_locked( Cache*  cache )
1344     int     nn;
1346     for (nn = 0; nn < cache->max_entries; nn++)
1347     {
1348         Entry**  pnode = (Entry**) &cache->entries[nn];
1350         while (*pnode != NULL) {
1351             Entry*  node = *pnode;
1352             *pnode = node->hlink;
1353             entry_free(node);
1354         }
1355     }
1357     // flush pending request
1358     _cache_flush_pending_requests_locked(cache);
1360     cache->mru_list.mru_next = cache->mru_list.mru_prev = &cache->mru_list;
1361     cache->num_entries       = 0;
1362     cache->last_id           = 0;
1364     XLOG("*************************\n"
1365          "*** DNS CACHE FLUSHED ***\n"
1366          "*************************");
1369 static int
1370 _res_cache_get_max_entries( void )
1372     int cache_size = CONFIG_MAX_ENTRIES;
1374     const char* cache_mode = getenv("ANDROID_DNS_MODE");
1375     if (cache_mode == NULL || strcmp(cache_mode, "local") != 0) {
1376         // Don't use the cache in local mode. This is used by the proxy itself.
1377         cache_size = 0;
1378     }
1380     XLOG("cache size: %d", cache_size);
1381     return cache_size;
1384 static struct resolv_cache*
1385 _resolv_cache_create( void )
1387     struct resolv_cache*  cache;
1389     cache = calloc(sizeof(*cache), 1);
1390     if (cache) {
1391         cache->max_entries = _res_cache_get_max_entries();
1392         cache->entries = calloc(sizeof(*cache->entries), cache->max_entries);
1393         if (cache->entries) {
1394             pthread_mutex_init( &cache->lock, NULL );
1395             cache->mru_list.mru_prev = cache->mru_list.mru_next = &cache->mru_list;
1396             XLOG("%s: cache created\n", __FUNCTION__);
1397         } else {
1398             free(cache);
1399             cache = NULL;
1400         }
1401     }
1402     return cache;
1406 #if DEBUG
1407 static void
1408 _dump_query( const uint8_t*  query, int  querylen )
1410     char       temp[256], *p=temp, *end=p+sizeof(temp);
1411     DnsPacket  pack[1];
1413     _dnsPacket_init(pack, query, querylen);
1414     p = _dnsPacket_bprintQuery(pack, p, end);
1415     XLOG("QUERY: %s", temp);
1418 static void
1419 _cache_dump_mru( Cache*  cache )
1421     char    temp[512], *p=temp, *end=p+sizeof(temp);
1422     Entry*  e;
1424     p = _bprint(temp, end, "MRU LIST (%2d): ", cache->num_entries);
1425     for (e = cache->mru_list.mru_next; e != &cache->mru_list; e = e->mru_next)
1426         p = _bprint(p, end, " %d", e->id);
1428     XLOG("%s", temp);
1431 static void
1432 _dump_answer(const void* answer, int answerlen)
1434     res_state statep;
1435     FILE* fp;
1436     char* buf;
1437     int fileLen;
1439     fp = fopen("/data/reslog.txt", "w+");
1440     if (fp != NULL) {
1441         statep = __res_get_state();
1443         res_pquery(statep, answer, answerlen, fp);
1445         //Get file length
1446         fseek(fp, 0, SEEK_END);
1447         fileLen=ftell(fp);
1448         fseek(fp, 0, SEEK_SET);
1449         buf = (char *)malloc(fileLen+1);
1450         if (buf != NULL) {
1451             //Read file contents into buffer
1452             fread(buf, fileLen, 1, fp);
1453             XLOG("%s\n", buf);
1454             free(buf);
1455         }
1456         fclose(fp);
1457         remove("/data/reslog.txt");
1458     }
1459     else {
1460         errno = 0; // else debug is introducing error signals
1461         XLOG("%s: can't open file\n", __FUNCTION__);
1462     }
1464 #endif
1466 #if DEBUG
1467 #  define  XLOG_QUERY(q,len)   _dump_query((q), (len))
1468 #  define  XLOG_ANSWER(a, len) _dump_answer((a), (len))
1469 #else
1470 #  define  XLOG_QUERY(q,len)   ((void)0)
1471 #  define  XLOG_ANSWER(a,len)  ((void)0)
1472 #endif
1474 /* This function tries to find a key within the hash table
1475  * In case of success, it will return a *pointer* to the hashed key.
1476  * In case of failure, it will return a *pointer* to NULL
1477  *
1478  * So, the caller must check '*result' to check for success/failure.
1479  *
1480  * The main idea is that the result can later be used directly in
1481  * calls to _resolv_cache_add or _resolv_cache_remove as the 'lookup'
1482  * parameter. This makes the code simpler and avoids re-searching
1483  * for the key position in the htable.
1484  *
1485  * The result of a lookup_p is only valid until you alter the hash
1486  * table.
1487  */
1488 static Entry**
1489 _cache_lookup_p( Cache*   cache,
1490                  Entry*   key )
1492     int      index = key->hash % cache->max_entries;
1493     Entry**  pnode = (Entry**) &cache->entries[ index ];
1495     while (*pnode != NULL) {
1496         Entry*  node = *pnode;
1498         if (node == NULL)
1499             break;
1501         if (node->hash == key->hash && entry_equals(node, key))
1502             break;
1504         pnode = &node->hlink;
1505     }
1506     return pnode;
1509 /* Add a new entry to the hash table. 'lookup' must be the
1510  * result of an immediate previous failed _lookup_p() call
1511  * (i.e. with *lookup == NULL), and 'e' is the pointer to the
1512  * newly created entry
1513  */
1514 static void
1515 _cache_add_p( Cache*   cache,
1516               Entry**  lookup,
1517               Entry*   e )
1519     *lookup = e;
1520     e->id = ++cache->last_id;
1521     entry_mru_add(e, &cache->mru_list);
1522     cache->num_entries += 1;
1524     XLOG("%s: entry %d added (count=%d)", __FUNCTION__,
1525          e->id, cache->num_entries);
1528 /* Remove an existing entry from the hash table,
1529  * 'lookup' must be the result of an immediate previous
1530  * and succesful _lookup_p() call.
1531  */
1532 static void
1533 _cache_remove_p( Cache*   cache,
1534                  Entry**  lookup )
1536     Entry*  e  = *lookup;
1538     XLOG("%s: entry %d removed (count=%d)", __FUNCTION__,
1539          e->id, cache->num_entries-1);
1541     entry_mru_remove(e);
1542     *lookup = e->hlink;
1543     entry_free(e);
1544     cache->num_entries -= 1;
1547 /* Remove the oldest entry from the hash table.
1548  */
1549 static void
1550 _cache_remove_oldest( Cache*  cache )
1552     Entry*   oldest = cache->mru_list.mru_prev;
1553     Entry**  lookup = _cache_lookup_p(cache, oldest);
1555     if (*lookup == NULL) { /* should not happen */
1556         XLOG("%s: OLDEST NOT IN HTABLE ?", __FUNCTION__);
1557         return;
1558     }
1559     if (DEBUG) {
1560         XLOG("Cache full - removing oldest");
1561         XLOG_QUERY(oldest->query, oldest->querylen);
1562     }
1563     _cache_remove_p(cache, lookup);
1566 /* Remove all expired entries from the hash table.
1567  */
1568 static void _cache_remove_expired(Cache* cache) {
1569     Entry* e;
1570     time_t now = _time_now();
1572     for (e = cache->mru_list.mru_next; e != &cache->mru_list;) {
1573         // Entry is old, remove
1574         if (now >= e->expires) {
1575             Entry** lookup = _cache_lookup_p(cache, e);
1576             if (*lookup == NULL) { /* should not happen */
1577                 XLOG("%s: ENTRY NOT IN HTABLE ?", __FUNCTION__);
1578                 return;
1579             }
1580             e = e->mru_next;
1581             _cache_remove_p(cache, lookup);
1582         } else {
1583             e = e->mru_next;
1584         }
1585     }
1588 ResolvCacheStatus
1589 _resolv_cache_lookup( struct resolv_cache*  cache,
1590                       const void*           query,
1591                       int                   querylen,
1592                       void*                 answer,
1593                       int                   answersize,
1594                       int                  *answerlen )
1596     Entry      key[1];
1597     Entry**    lookup;
1598     Entry*     e;
1599     time_t     now;
1601     ResolvCacheStatus  result = RESOLV_CACHE_NOTFOUND;
1603     XLOG("%s: lookup", __FUNCTION__);
1604     XLOG_QUERY(query, querylen);
1606     /* we don't cache malformed queries */
1607     if (!entry_init_key(key, query, querylen)) {
1608         XLOG("%s: unsupported query", __FUNCTION__);
1609         return RESOLV_CACHE_UNSUPPORTED;
1610     }
1611     /* lookup cache */
1612     pthread_mutex_lock( &cache->lock );
1614     /* see the description of _lookup_p to understand this.
1615      * the function always return a non-NULL pointer.
1616      */
1617     lookup = _cache_lookup_p(cache, key);
1618     e      = *lookup;
1620     if (e == NULL) {
1621         XLOG( "NOT IN CACHE");
1622         // calling thread will wait if an outstanding request is found
1623         // that matching this query
1624         if (!_cache_check_pending_request_locked(cache, key)) {
1625             goto Exit;
1626         } else {
1627             lookup = _cache_lookup_p(cache, key);
1628             e = *lookup;
1629             if (e == NULL) {
1630                 goto Exit;
1631             }
1632         }
1633     }
1635     now = _time_now();
1637     /* remove stale entries here */
1638     if (now >= e->expires) {
1639         XLOG( " NOT IN CACHE (STALE ENTRY %p DISCARDED)", *lookup );
1640         XLOG_QUERY(e->query, e->querylen);
1641         _cache_remove_p(cache, lookup);
1642         goto Exit;
1643     }
1645     *answerlen = e->answerlen;
1646     if (e->answerlen > answersize) {
1647         /* NOTE: we return UNSUPPORTED if the answer buffer is too short */
1648         result = RESOLV_CACHE_UNSUPPORTED;
1649         XLOG(" ANSWER TOO LONG");
1650         goto Exit;
1651     }
1653     memcpy( answer, e->answer, e->answerlen );
1655     /* bump up this entry to the top of the MRU list */
1656     if (e != cache->mru_list.mru_next) {
1657         entry_mru_remove( e );
1658         entry_mru_add( e, &cache->mru_list );
1659     }
1661     XLOG( "FOUND IN CACHE entry=%p", e );
1662     result = RESOLV_CACHE_FOUND;
1664 Exit:
1665     pthread_mutex_unlock( &cache->lock );
1666     return result;
1670 void
1671 _resolv_cache_add( struct resolv_cache*  cache,
1672                    const void*           query,
1673                    int                   querylen,
1674                    const void*           answer,
1675                    int                   answerlen )
1677     Entry    key[1];
1678     Entry*   e;
1679     Entry**  lookup;
1680     u_long   ttl;
1682     /* don't assume that the query has already been cached
1683      */
1684     if (!entry_init_key( key, query, querylen )) {
1685         XLOG( "%s: passed invalid query ?", __FUNCTION__);
1686         return;
1687     }
1689     pthread_mutex_lock( &cache->lock );
1691     XLOG( "%s: query:", __FUNCTION__ );
1692     XLOG_QUERY(query,querylen);
1693     XLOG_ANSWER(answer, answerlen);
1694 #if DEBUG_DATA
1695     XLOG( "answer:");
1696     XLOG_BYTES(answer,answerlen);
1697 #endif
1699     lookup = _cache_lookup_p(cache, key);
1700     e      = *lookup;
1702     if (e != NULL) { /* should not happen */
1703         XLOG("%s: ALREADY IN CACHE (%p) ? IGNORING ADD",
1704              __FUNCTION__, e);
1705         goto Exit;
1706     }
1708     if (cache->num_entries >= cache->max_entries) {
1709         _cache_remove_expired(cache);
1710         if (cache->num_entries >= cache->max_entries) {
1711             _cache_remove_oldest(cache);
1712         }
1713         /* need to lookup again */
1714         lookup = _cache_lookup_p(cache, key);
1715         e      = *lookup;
1716         if (e != NULL) {
1717             XLOG("%s: ALREADY IN CACHE (%p) ? IGNORING ADD",
1718                 __FUNCTION__, e);
1719             goto Exit;
1720         }
1721     }
1723     ttl = answer_getTTL(answer, answerlen);
1724     if (ttl > 0) {
1725         e = entry_alloc(key, answer, answerlen);
1726         if (e != NULL) {
1727             e->expires = ttl + _time_now();
1728             _cache_add_p(cache, lookup, e);
1729         }
1730     }
1731 #if DEBUG
1732     _cache_dump_mru(cache);
1733 #endif
1734 Exit:
1735     _cache_notify_waiting_tid_locked(cache, key);
1736     pthread_mutex_unlock( &cache->lock );
1739 /****************************************************************************/
1740 /****************************************************************************/
1741 /*****                                                                  *****/
1742 /*****                                                                  *****/
1743 /*****                                                                  *****/
1744 /****************************************************************************/
1745 /****************************************************************************/
1747 static pthread_once_t        _res_cache_once = PTHREAD_ONCE_INIT;
1749 // Head of the list of caches.  Protected by _res_cache_list_lock.
1750 static struct resolv_cache_info _res_cache_list;
1752 // lock protecting everything in the _resolve_cache_info structs (next ptr, etc)
1753 static pthread_mutex_t _res_cache_list_lock;
1755 /* insert resolv_cache_info into the list of resolv_cache_infos */
1756 static void _insert_cache_info_locked(struct resolv_cache_info* cache_info);
1757 /* creates a resolv_cache_info */
1758 static struct resolv_cache_info* _create_cache_info( void );
1759 /* gets cache associated with a network, or NULL if none exists */
1760 static struct resolv_cache* _find_named_cache_locked(unsigned netid);
1761 /* gets a resolv_cache_info associated with a network, or NULL if not found */
1762 static struct resolv_cache_info* _find_cache_info_locked(unsigned netid);
1763 /* look up the named cache, and creates one if needed */
1764 static struct resolv_cache* _get_res_cache_for_net_locked(unsigned netid);
1765 /* empty the named cache */
1766 static void _flush_cache_for_net_locked(unsigned netid);
1767 /* empty the nameservers set for the named cache */
1768 static void _free_nameservers_locked(struct resolv_cache_info* cache_info);
1769 /* return 1 if the provided list of name servers differs from the list of name servers
1770  * currently attached to the provided cache_info */
1771 static int _resolv_is_nameservers_equal_locked(struct resolv_cache_info* cache_info,
1772         const char** servers, int numservers);
1774 static void
1775 _res_cache_init(void)
1777     const char*  env = getenv(CONFIG_ENV);
1779     if (env && atoi(env) == 0) {
1780         /* the cache is disabled */
1781         return;
1782     }
1784     memset(&_res_cache_list, 0, sizeof(_res_cache_list));
1785     pthread_mutex_init(&_res_cache_list_lock, NULL);
1788 struct resolv_cache*
1789 __get_res_cache(unsigned netid)
1791     struct resolv_cache *cache;
1793     pthread_once(&_res_cache_once, _res_cache_init);
1794     pthread_mutex_lock(&_res_cache_list_lock);
1796     /* Does NOT create a cache if it does not exist. */
1797     cache = _find_named_cache_locked(netid);
1799     pthread_mutex_unlock(&_res_cache_list_lock);
1800     XLOG("%s: netid=%u, cache=%p\n", __FUNCTION__, netid, cache);
1801     return cache;
1804 static struct resolv_cache*
1805 _get_res_cache_for_net_locked(unsigned netid)
1807     struct resolv_cache* cache = _find_named_cache_locked(netid);
1808     if (!cache) {
1809         struct resolv_cache_info* cache_info = _create_cache_info();
1810         if (cache_info) {
1811             cache = _resolv_cache_create();
1812             if (cache) {
1813                 cache_info->cache = cache;
1814                 cache_info->netid = netid;
1815                 _insert_cache_info_locked(cache_info);
1816             } else {
1817                 free(cache_info);
1818             }
1819         }
1820     }
1821     return cache;
1824 void
1825 _resolv_flush_cache_for_net(unsigned netid)
1827     pthread_once(&_res_cache_once, _res_cache_init);
1828     pthread_mutex_lock(&_res_cache_list_lock);
1830     _flush_cache_for_net_locked(netid);
1832     pthread_mutex_unlock(&_res_cache_list_lock);
1835 static void
1836 _flush_cache_for_net_locked(unsigned netid)
1838     struct resolv_cache* cache = _find_named_cache_locked(netid);
1839     if (cache) {
1840         pthread_mutex_lock(&cache->lock);
1841         _cache_flush_locked(cache);
1842         pthread_mutex_unlock(&cache->lock);
1843     }
1846 static struct resolv_cache_info*
1847 _create_cache_info(void)
1849     struct resolv_cache_info* cache_info;
1851     cache_info = calloc(sizeof(*cache_info), 1);
1852     return cache_info;
1855 static void
1856 _insert_cache_info_locked(struct resolv_cache_info* cache_info)
1858     struct resolv_cache_info* last;
1860     for (last = &_res_cache_list; last->next; last = last->next);
1862     last->next = cache_info;
1866 static struct resolv_cache*
1867 _find_named_cache_locked(unsigned netid) {
1869     struct resolv_cache_info* info = _find_cache_info_locked(netid);
1871     if (info != NULL) return info->cache;
1873     return NULL;
1876 static struct resolv_cache_info*
1877 _find_cache_info_locked(unsigned netid)
1879     struct resolv_cache_info* cache_info = _res_cache_list.next;
1881     while (cache_info) {
1882         if (cache_info->netid == netid) {
1883             break;
1884         }
1886         cache_info = cache_info->next;
1887     }
1888     return cache_info;
1891 void
1892 _resolv_set_nameservers_for_net(unsigned netid, const char** servers, int numservers,
1893         const char *domains)
1895     int i, rt, index;
1896     struct addrinfo hints;
1897     char sbuf[NI_MAXSERV];
1898     register char *cp;
1899     int *offset;
1901     pthread_once(&_res_cache_once, _res_cache_init);
1902     pthread_mutex_lock(&_res_cache_list_lock);
1904     // creates the cache if not created
1905     _get_res_cache_for_net_locked(netid);
1907     struct resolv_cache_info* cache_info = _find_cache_info_locked(netid);
1909     if (cache_info != NULL &&
1910             !_resolv_is_nameservers_equal_locked(cache_info, servers, numservers)) {
1911         // free current before adding new
1912         _free_nameservers_locked(cache_info);
1914         memset(&hints, 0, sizeof(hints));
1915         hints.ai_family = PF_UNSPEC;
1916         hints.ai_socktype = SOCK_DGRAM; /*dummy*/
1917         hints.ai_flags = AI_NUMERICHOST;
1918         sprintf(sbuf, "%u", NAMESERVER_PORT);
1920         index = 0;
1921         for (i = 0; i < numservers && i < MAXNS; i++) {
1922             rt = getaddrinfo(servers[i], sbuf, &hints, &cache_info->nsaddrinfo[index]);
1923             if (rt == 0) {
1924                 cache_info->nameservers[index] = strdup(servers[i]);
1925                 index++;
1926                 XLOG("%s: netid = %u, addr = %s\n", __FUNCTION__, netid, servers[i]);
1927             } else {
1928                 cache_info->nsaddrinfo[index] = NULL;
1929             }
1930         }
1932         // code moved from res_init.c, load_domain_search_list
1933         strlcpy(cache_info->defdname, domains, sizeof(cache_info->defdname));
1934         if ((cp = strchr(cache_info->defdname, '\n')) != NULL)
1935             *cp = '\0';
1936         cp = cache_info->defdname;
1937         offset = cache_info->dnsrch_offset;
1938         while (offset < cache_info->dnsrch_offset + MAXDNSRCH) {
1939             while (*cp == ' ' || *cp == '\t') /* skip leading white space */
1940                 cp++;
1941             if (*cp == '\0') /* stop if nothing more to do */
1942                 break;
1943             *offset++ = cp - cache_info->defdname; /* record this search domain */
1944             while (*cp) { /* zero-terminate it */
1945                 if (*cp == ' '|| *cp == '\t') {
1946                     *cp++ = '\0';
1947                     break;
1948                 }
1949                 cp++;
1950             }
1951         }
1952         *offset = -1; /* cache_info->dnsrch_offset has MAXDNSRCH+1 items */
1954         // flush cache since new settings
1955         _flush_cache_for_net_locked(netid);
1957     }
1959     pthread_mutex_unlock(&_res_cache_list_lock);
1962 static int
1963 _resolv_is_nameservers_equal_locked(struct resolv_cache_info* cache_info,
1964         const char** servers, int numservers)
1966     int i;
1967     char** ns;
1968     int equal = 1;
1970     // compare each name server against current name servers
1971     if (numservers > MAXNS) numservers = MAXNS;
1972     for (i = 0; i < numservers && equal; i++) {
1973         ns = cache_info->nameservers;
1974         equal = 0;
1975         while(*ns) {
1976             if (strcmp(*ns, servers[i]) == 0) {
1977                 equal = 1;
1978                 break;
1979             }
1980             ns++;
1981         }
1982     }
1984     return equal;
1987 static void
1988 _free_nameservers_locked(struct resolv_cache_info* cache_info)
1990     int i;
1991     for (i = 0; i <= MAXNS; i++) {
1992         free(cache_info->nameservers[i]);
1993         cache_info->nameservers[i] = NULL;
1994         if (cache_info->nsaddrinfo[i] != NULL) {
1995             freeaddrinfo(cache_info->nsaddrinfo[i]);
1996             cache_info->nsaddrinfo[i] = NULL;
1997         }
1998     }
2001 void
2002 _resolv_populate_res_for_net(res_state statp)
2004     if (statp == NULL) {
2005         return;
2006     }
2008     pthread_once(&_res_cache_once, _res_cache_init);
2009     pthread_mutex_lock(&_res_cache_list_lock);
2011     struct resolv_cache_info* info = _find_cache_info_locked(statp->netid);
2012     if (info != NULL) {
2013         int nserv;
2014         struct addrinfo* ai;
2015         XLOG("%s: %u\n", __FUNCTION__, statp->netid);
2016         for (nserv = 0; nserv < MAXNS; nserv++) {
2017             ai = info->nsaddrinfo[nserv];
2018             if (ai == NULL) {
2019                 break;
2020             }
2022             if ((size_t) ai->ai_addrlen <= sizeof(statp->_u._ext.ext->nsaddrs[0])) {
2023                 if (statp->_u._ext.ext != NULL) {
2024                     memcpy(&statp->_u._ext.ext->nsaddrs[nserv], ai->ai_addr, ai->ai_addrlen);
2025                     statp->nsaddr_list[nserv].sin_family = AF_UNSPEC;
2026                 } else {
2027                     if ((size_t) ai->ai_addrlen
2028                             <= sizeof(statp->nsaddr_list[0])) {
2029                         memcpy(&statp->nsaddr_list[nserv], ai->ai_addr,
2030                                 ai->ai_addrlen);
2031                     } else {
2032                         statp->nsaddr_list[nserv].sin_family = AF_UNSPEC;
2033                     }
2034                 }
2035             } else {
2036                 XLOG("%s: found too long addrlen", __FUNCTION__);
2037             }
2038         }
2039         statp->nscount = nserv;
2040         // now do search domains.  Note that we cache the offsets as this code runs alot
2041         // but the setting/offset-computer only runs when set/changed
2042         strlcpy(statp->defdname, info->defdname, sizeof(statp->defdname));
2043         register char **pp = statp->dnsrch;
2044         register int *p = info->dnsrch_offset;
2045         while (pp < statp->dnsrch + MAXDNSRCH && *p != -1) {
2046             *pp++ = &statp->defdname[0] + *p++;
2047         }
2048     }
2049     pthread_mutex_unlock(&_res_cache_list_lock);