rrl.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012-2014  Internet Systems Consortium, Inc. ("ISC")
00003  *
00004  * Permission to use, copy, modify, and/or distribute this software for any
00005  * purpose with or without fee is hereby granted, provided that the above
00006  * copyright notice and this permission notice appear in all copies.
00007  *
00008  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
00009  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
00010  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
00011  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
00012  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
00013  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
00014  * PERFORMANCE OF THIS SOFTWARE.
00015  */
00016 
00017 /*! \file */
00018 
00019 /*
00020  * Rate limit DNS responses.
00021  */
00022 
00023 /* #define ISC_LIST_CHECKINIT */
00024 
00025 #include <config.h>
00026 #include <isc/mem.h>
00027 #include <isc/net.h>
00028 #include <isc/netaddr.h>
00029 #include <isc/print.h>
00030 
00031 #include <dns/result.h>
00032 #include <dns/rcode.h>
00033 #include <dns/rdatatype.h>
00034 #include <dns/rdataclass.h>
00035 #include <dns/log.h>
00036 #include <dns/rrl.h>
00037 #include <dns/view.h>
00038 
00039 static void
00040 log_end(dns_rrl_t *rrl, dns_rrl_entry_t *e, isc_boolean_t early,
00041         char *log_buf, unsigned int log_buf_len);
00042 
00043 /*
00044  * Get a modulus for a hash function that is tolerably likely to be
00045  * relatively prime to most inputs.  Of course, we get a prime for for initial
00046  * values not larger than the square of the last prime.  We often get a prime
00047  * after that.
00048  * This works well in practice for hash tables up to at least 100
00049  * times the square of the last prime and better than a multiplicative hash.
00050  */
00051 static int
00052 hash_divisor(unsigned int initial) {
00053         static isc_uint16_t primes[] = {
00054                   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,
00055                  43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,
00056 #if 0
00057                 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
00058                 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
00059                 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
00060                 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367,
00061                 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
00062                 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
00063                 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
00064                 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
00065                 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751,
00066                 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
00067                 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
00068                 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,1009,
00069 #endif
00070         };
00071         int divisions, tries;
00072         unsigned int result;
00073         isc_uint16_t *pp, p;
00074 
00075         result = initial;
00076 
00077         if (primes[sizeof(primes)/sizeof(primes[0])-1] >= result) {
00078                 pp = primes;
00079                 while (*pp < result)
00080                         ++pp;
00081                 return (*pp);
00082         }
00083 
00084         if ((result & 1) == 0)
00085                 ++result;
00086 
00087         divisions = 0;
00088         tries = 1;
00089         pp = primes;
00090         do {
00091                 p = *pp++;
00092                 ++divisions;
00093                 if ((result % p) == 0) {
00094                         ++tries;
00095                         result += 2;
00096                         pp = primes;
00097                 }
00098         } while (pp < &primes[sizeof(primes) / sizeof(primes[0])]);
00099 
00100         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
00101                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00102                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG3,
00103                               "%d hash_divisor() divisions in %d tries"
00104                               " to get %d from %d",
00105                               divisions, tries, result, initial);
00106 
00107         return (result);
00108 }
00109 
00110 /*
00111  * Convert a timestamp to a number of seconds in the past.
00112  */
00113 static inline int
00114 delta_rrl_time(isc_stdtime_t ts, isc_stdtime_t now) {
00115         int delta;
00116 
00117         delta = now - ts;
00118         if (delta >= 0)
00119                 return (delta);
00120 
00121         /*
00122          * The timestamp is in the future.  That future might result from
00123          * re-ordered requests, because we use timestamps on requests
00124          * instead of consulting a clock.  Timestamps in the distant future are
00125          * assumed to result from clock changes.  When the clock changes to
00126          * the past, make existing timestamps appear to be in the past.
00127          */
00128         if (delta < -DNS_RRL_MAX_TIME_TRAVEL)
00129                 return (DNS_RRL_FOREVER);
00130         return (0);
00131 }
00132 
00133 static inline int
00134 get_age(const dns_rrl_t *rrl, const dns_rrl_entry_t *e, isc_stdtime_t now) {
00135         if (!e->ts_valid)
00136                 return (DNS_RRL_FOREVER);
00137         return (delta_rrl_time(e->ts + rrl->ts_bases[e->ts_gen], now));
00138 }
00139 
00140 static inline void
00141 set_age(dns_rrl_t *rrl, dns_rrl_entry_t *e, isc_stdtime_t now) {
00142         dns_rrl_entry_t *e_old;
00143         unsigned int ts_gen;
00144         int i, ts;
00145 
00146         ts_gen = rrl->ts_gen;
00147         ts = now - rrl->ts_bases[ts_gen];
00148         if (ts < 0) {
00149                 if (ts < -DNS_RRL_MAX_TIME_TRAVEL)
00150                         ts = DNS_RRL_FOREVER;
00151                 else
00152                         ts = 0;
00153         }
00154 
00155         /*
00156          * Make a new timestamp base if the current base is too old.
00157          * All entries older than DNS_RRL_MAX_WINDOW seconds are ancient,
00158          * useless history.  Their timestamps can be treated as if they are
00159          * all the same.
00160          * We only do arithmetic on more recent timestamps, so bases for
00161          * older timestamps can be recycled provided the old timestamps are
00162          * marked as ancient history.
00163          * This loop is almost always very short because most entries are
00164          * recycled after one second and any entries that need to be marked
00165          * are older than (DNS_RRL_TS_BASES)*DNS_RRL_MAX_TS seconds.
00166          */
00167         if (ts >= DNS_RRL_MAX_TS) {
00168                 ts_gen = (ts_gen + 1) % DNS_RRL_TS_BASES;
00169                 for (e_old = ISC_LIST_TAIL(rrl->lru), i = 0;
00170                      e_old != NULL && (e_old->ts_gen == ts_gen ||
00171                                        !ISC_LINK_LINKED(e_old, hlink));
00172                      e_old = ISC_LIST_PREV(e_old, lru), ++i)
00173                 {
00174                         e_old->ts_valid = ISC_FALSE;
00175                 }
00176                 if (i != 0)
00177                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00178                                       DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG1,
00179                                       "rrl new time base scanned %d entries"
00180                                       " at %d for %d %d %d %d",
00181                                       i, now, rrl->ts_bases[ts_gen],
00182                                       rrl->ts_bases[(ts_gen + 1) %
00183                                         DNS_RRL_TS_BASES],
00184                                       rrl->ts_bases[(ts_gen + 2) %
00185                                         DNS_RRL_TS_BASES],
00186                                       rrl->ts_bases[(ts_gen + 3) %
00187                                         DNS_RRL_TS_BASES]);
00188                 rrl->ts_gen = ts_gen;
00189                 rrl->ts_bases[ts_gen] = now;
00190                 ts = 0;
00191         }
00192 
00193         e->ts_gen = ts_gen;
00194         e->ts = ts;
00195         e->ts_valid = ISC_TRUE;
00196 }
00197 
00198 static isc_result_t
00199 expand_entries(dns_rrl_t *rrl, int new) {
00200         unsigned int bsize;
00201         dns_rrl_block_t *b;
00202         dns_rrl_entry_t *e;
00203         double rate;
00204         int i;
00205 
00206         if (rrl->num_entries + new >= rrl->max_entries &&
00207             rrl->max_entries != 0)
00208         {
00209                 new = rrl->max_entries - rrl->num_entries;
00210                 if (new <= 0)
00211                         return (ISC_R_SUCCESS);
00212         }
00213 
00214         /*
00215          * Log expansions so that the user can tune max-table-size
00216          * and min-table-size.
00217          */
00218         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP) &&
00219             rrl->hash != NULL) {
00220                 rate = rrl->probes;
00221                 if (rrl->searches != 0)
00222                         rate /= rrl->searches;
00223                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00224                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
00225                               "increase from %d to %d RRL entries with"
00226                               " %d bins; average search length %.1f",
00227                               rrl->num_entries, rrl->num_entries+new,
00228                               rrl->hash->length, rate);
00229         }
00230 
00231         bsize = sizeof(dns_rrl_block_t) + (new-1)*sizeof(dns_rrl_entry_t);
00232         b = isc_mem_get(rrl->mctx, bsize);
00233         if (b == NULL) {
00234                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00235                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_FAIL,
00236                               "isc_mem_get(%d) failed for RRL entries",
00237                               bsize);
00238                 return (ISC_R_NOMEMORY);
00239         }
00240         memset(b, 0, bsize);
00241         b->size = bsize;
00242 
00243         e = b->entries;
00244         for (i = 0; i < new; ++i, ++e) {
00245                 ISC_LINK_INIT(e, hlink);
00246                 ISC_LIST_INITANDAPPEND(rrl->lru, e, lru);
00247         }
00248         rrl->num_entries += new;
00249         ISC_LIST_INITANDAPPEND(rrl->blocks, b, link);
00250 
00251         return (ISC_R_SUCCESS);
00252 }
00253 
00254 static inline dns_rrl_bin_t *
00255 get_bin(dns_rrl_hash_t *hash, unsigned int hval) {
00256         INSIST(hash != NULL);
00257         return (&hash->bins[hval % hash->length]);
00258 }
00259 
00260 static void
00261 free_old_hash(dns_rrl_t *rrl) {
00262         dns_rrl_hash_t *old_hash;
00263         dns_rrl_bin_t *old_bin;
00264         dns_rrl_entry_t *e, *e_next;
00265 
00266         old_hash = rrl->old_hash;
00267         for (old_bin = &old_hash->bins[0];
00268              old_bin < &old_hash->bins[old_hash->length];
00269              ++old_bin)
00270         {
00271                 for (e = ISC_LIST_HEAD(*old_bin); e != NULL; e = e_next) {
00272                         e_next = ISC_LIST_NEXT(e, hlink);
00273                         ISC_LINK_INIT(e, hlink);
00274                 }
00275         }
00276 
00277         isc_mem_put(rrl->mctx, old_hash,
00278                     sizeof(*old_hash)
00279                       + (old_hash->length - 1) * sizeof(old_hash->bins[0]));
00280         rrl->old_hash = NULL;
00281 }
00282 
00283 static isc_result_t
00284 expand_rrl_hash(dns_rrl_t *rrl, isc_stdtime_t now) {
00285         dns_rrl_hash_t *hash;
00286         int old_bins, new_bins, hsize;
00287         double rate;
00288 
00289         if (rrl->old_hash != NULL)
00290                 free_old_hash(rrl);
00291 
00292         /*
00293          * Most searches fail and so go to the end of the chain.
00294          * Use a small hash table load factor.
00295          */
00296         old_bins = (rrl->hash == NULL) ? 0 : rrl->hash->length;
00297         new_bins = old_bins/8 + old_bins;
00298         if (new_bins < rrl->num_entries)
00299                 new_bins = rrl->num_entries;
00300         new_bins = hash_divisor(new_bins);
00301 
00302         hsize = sizeof(dns_rrl_hash_t) + (new_bins-1)*sizeof(hash->bins[0]);
00303         hash = isc_mem_get(rrl->mctx, hsize);
00304         if (hash == NULL) {
00305                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00306                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_FAIL,
00307                               "isc_mem_get(%d) failed for"
00308                               " RRL hash table",
00309                               hsize);
00310                 return (ISC_R_NOMEMORY);
00311         }
00312         memset(hash, 0, hsize);
00313         hash->length = new_bins;
00314         rrl->hash_gen ^= 1;
00315         hash->gen = rrl->hash_gen;
00316 
00317         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP) && old_bins != 0) {
00318                 rate = rrl->probes;
00319                 if (rrl->searches != 0)
00320                         rate /= rrl->searches;
00321                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00322                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
00323                               "increase from %d to %d RRL bins for"
00324                               " %d entries; average search length %.1f",
00325                               old_bins, new_bins, rrl->num_entries, rate);
00326         }
00327 
00328         rrl->old_hash = rrl->hash;
00329         if (rrl->old_hash != NULL)
00330                 rrl->old_hash->check_time = now;
00331         rrl->hash = hash;
00332 
00333         return (ISC_R_SUCCESS);
00334 }
00335 
00336 static void
00337 ref_entry(dns_rrl_t *rrl, dns_rrl_entry_t *e, int probes, isc_stdtime_t now) {
00338         /*
00339          * Make the entry most recently used.
00340          */
00341         if (ISC_LIST_HEAD(rrl->lru) != e) {
00342                 if (e == rrl->last_logged)
00343                         rrl->last_logged = ISC_LIST_PREV(e, lru);
00344                 ISC_LIST_UNLINK(rrl->lru, e, lru);
00345                 ISC_LIST_PREPEND(rrl->lru, e, lru);
00346         }
00347 
00348         /*
00349          * Expand the hash table if it is time and necessary.
00350          * This will leave the newly referenced entry in a chain in the
00351          * old hash table.  It will migrate to the new hash table the next
00352          * time it is used or be cut loose when the old hash table is destroyed.
00353          */
00354         rrl->probes += probes;
00355         ++rrl->searches;
00356         if (rrl->searches > 100 &&
00357             delta_rrl_time(rrl->hash->check_time, now) > 1) {
00358                 if (rrl->probes/rrl->searches > 2)
00359                         expand_rrl_hash(rrl, now);
00360                 rrl->hash->check_time = now;
00361                 rrl->probes = 0;
00362                 rrl->searches = 0;
00363         }
00364 }
00365 
00366 static inline isc_boolean_t
00367 key_cmp(const dns_rrl_key_t *a, const dns_rrl_key_t *b) {
00368         if (memcmp(a, b, sizeof(dns_rrl_key_t)) == 0)
00369                 return (ISC_TRUE);
00370         return (ISC_FALSE);
00371 }
00372 
00373 static inline isc_uint32_t
00374 hash_key(const dns_rrl_key_t *key) {
00375         isc_uint32_t hval;
00376         int i;
00377 
00378         hval = key->w[0];
00379         for (i = sizeof(*key) / sizeof(key->w[0]) - 1; i >= 0; --i) {
00380                 hval = key->w[i] + (hval<<1);
00381         }
00382         return (hval);
00383 }
00384 
00385 /*
00386  * Construct the hash table key.
00387  * Use a hash of the DNS query name to save space in the database.
00388  * Collisions result in legitimate rate limiting responses for one
00389  * query name also limiting responses for other names to the
00390  * same client.  This is rare and benign enough given the large
00391  * space costs compared to keeping the entire name in the database
00392  * entry or the time costs of dynamic allocation.
00393  */
00394 static void
00395 make_key(const dns_rrl_t *rrl, dns_rrl_key_t *key,
00396          const isc_sockaddr_t *client_addr,
00397          dns_rdatatype_t qtype, dns_name_t *qname, dns_rdataclass_t qclass,
00398          dns_rrl_rtype_t rtype)
00399 {
00400         dns_name_t base;
00401         dns_offsets_t base_offsets;
00402         int labels, i;
00403 
00404         memset(key, 0, sizeof(*key));
00405 
00406         key->s.rtype = rtype;
00407         if (rtype == DNS_RRL_RTYPE_QUERY) {
00408                 key->s.qtype = qtype;
00409                 key->s.qclass = qclass & 0xff;
00410         } else if (rtype == DNS_RRL_RTYPE_REFERRAL ||
00411                    rtype == DNS_RRL_RTYPE_NODATA) {
00412                 /*
00413                  * Because there is no qtype in the empty answer sections of
00414                  * referral and NODATA responses, count them as the same.
00415                  */
00416                 key->s.qclass = qclass & 0xff;
00417         }
00418 
00419         if (qname != NULL && qname->labels != 0) {
00420                 /*
00421                  * Ignore the first label of wildcards.
00422                  */
00423                 if ((qname->attributes & DNS_NAMEATTR_WILDCARD) != 0 &&
00424                     (labels = dns_name_countlabels(qname)) > 1)
00425                 {
00426                         dns_name_init(&base, base_offsets);
00427                         dns_name_getlabelsequence(qname, 1, labels-1, &base);
00428                         key->s.qname_hash = dns_name_hashbylabel(&base,
00429                                                         ISC_FALSE);
00430                 } else {
00431                         key->s.qname_hash = dns_name_hashbylabel(qname,
00432                                                         ISC_FALSE);
00433                 }
00434         }
00435 
00436         switch (client_addr->type.sa.sa_family) {
00437         case AF_INET:
00438                 key->s.ip[0] = (client_addr->type.sin.sin_addr.s_addr &
00439                               rrl->ipv4_mask);
00440                 break;
00441         case AF_INET6:
00442                 key->s.ipv6 = ISC_TRUE;
00443                 memmove(key->s.ip, &client_addr->type.sin6.sin6_addr,
00444                         sizeof(key->s.ip));
00445                 for (i = 0; i < DNS_RRL_MAX_PREFIX/32; ++i)
00446                         key->s.ip[i] &= rrl->ipv6_mask[i];
00447                 break;
00448         }
00449 }
00450 
00451 static inline dns_rrl_rate_t *
00452 get_rate(dns_rrl_t *rrl, dns_rrl_rtype_t rtype) {
00453         switch (rtype) {
00454         case DNS_RRL_RTYPE_QUERY:
00455                 return (&rrl->responses_per_second);
00456         case DNS_RRL_RTYPE_REFERRAL:
00457                 return (&rrl->referrals_per_second);
00458         case DNS_RRL_RTYPE_NODATA:
00459                 return (&rrl->nodata_per_second);
00460         case DNS_RRL_RTYPE_NXDOMAIN:
00461                 return (&rrl->nxdomains_per_second);
00462         case DNS_RRL_RTYPE_ERROR:
00463                 return (&rrl->errors_per_second);
00464         case DNS_RRL_RTYPE_ALL:
00465                 return (&rrl->all_per_second);
00466         default:
00467                 INSIST(0);
00468         }
00469         return (NULL);
00470 }
00471 
00472 static int
00473 response_balance(dns_rrl_t *rrl, const dns_rrl_entry_t *e, int age) {
00474         dns_rrl_rate_t *ratep;
00475         int balance, rate;
00476 
00477         if (e->key.s.rtype == DNS_RRL_RTYPE_TCP) {
00478                 rate = 1;
00479         } else {
00480                 ratep = get_rate(rrl, e->key.s.rtype);
00481                 rate = ratep->scaled;
00482         }
00483 
00484         balance = e->responses + age * rate;
00485         if (balance > rate)
00486                 balance = rate;
00487         return (balance);
00488 }
00489 
00490 /*
00491  * Search for an entry for a response and optionally create it.
00492  */
00493 static dns_rrl_entry_t *
00494 get_entry(dns_rrl_t *rrl, const isc_sockaddr_t *client_addr,
00495           dns_rdataclass_t qclass, dns_rdatatype_t qtype, dns_name_t *qname,
00496           dns_rrl_rtype_t rtype, isc_stdtime_t now, isc_boolean_t create,
00497           char *log_buf, unsigned int log_buf_len)
00498 {
00499         dns_rrl_key_t key;
00500         isc_uint32_t hval;
00501         dns_rrl_entry_t *e;
00502         dns_rrl_hash_t *hash;
00503         dns_rrl_bin_t *new_bin, *old_bin;
00504         int probes, age;
00505 
00506         make_key(rrl, &key, client_addr, qtype, qname, qclass, rtype);
00507         hval = hash_key(&key);
00508 
00509         /*
00510          * Look for the entry in the current hash table.
00511          */
00512         new_bin = get_bin(rrl->hash, hval);
00513         probes = 1;
00514         e = ISC_LIST_HEAD(*new_bin);
00515         while (e != NULL) {
00516                 if (key_cmp(&e->key, &key)) {
00517                         ref_entry(rrl, e, probes, now);
00518                         return (e);
00519                 }
00520                 ++probes;
00521                 e = ISC_LIST_NEXT(e, hlink);
00522         }
00523 
00524         /*
00525          * Look in the old hash table.
00526          */
00527         if (rrl->old_hash != NULL) {
00528                 old_bin = get_bin(rrl->old_hash, hval);
00529                 e = ISC_LIST_HEAD(*old_bin);
00530                 while (e != NULL) {
00531                         if (key_cmp(&e->key, &key)) {
00532                                 ISC_LIST_UNLINK(*old_bin, e, hlink);
00533                                 ISC_LIST_PREPEND(*new_bin, e, hlink);
00534                                 e->hash_gen = rrl->hash_gen;
00535                                 ref_entry(rrl, e, probes, now);
00536                                 return (e);
00537                         }
00538                         e = ISC_LIST_NEXT(e, hlink);
00539                 }
00540 
00541                 /*
00542                  * Discard prevous hash table when all of its entries are old.
00543                  */
00544                 age = delta_rrl_time(rrl->old_hash->check_time, now);
00545                 if (age > rrl->window)
00546                         free_old_hash(rrl);
00547         }
00548 
00549         if (!create)
00550                 return (NULL);
00551 
00552         /*
00553          * The entry does not exist, so create it by finding a free entry.
00554          * Keep currently penalized and logged entries.
00555          * Try to make more entries if none are idle.
00556          * Steal the oldest entry if we cannot create more.
00557          */
00558         for (e = ISC_LIST_TAIL(rrl->lru);
00559              e != NULL;
00560              e = ISC_LIST_PREV(e, lru))
00561         {
00562                 if (!ISC_LINK_LINKED(e, hlink))
00563                         break;
00564                 age = get_age(rrl, e, now);
00565                 if (age <= 1) {
00566                         e = NULL;
00567                         break;
00568                 }
00569                 if (!e->logged && response_balance(rrl, e, age) > 0)
00570                         break;
00571         }
00572         if (e == NULL) {
00573                 expand_entries(rrl, ISC_MIN((rrl->num_entries+1)/2, 1000));
00574                 e = ISC_LIST_TAIL(rrl->lru);
00575         }
00576         if (e->logged)
00577                 log_end(rrl, e, ISC_TRUE, log_buf, log_buf_len);
00578         if (ISC_LINK_LINKED(e, hlink)) {
00579                 if (e->hash_gen == rrl->hash_gen)
00580                         hash = rrl->hash;
00581                 else
00582                         hash = rrl->old_hash;
00583                 old_bin = get_bin(hash, hash_key(&e->key));
00584                 ISC_LIST_UNLINK(*old_bin, e, hlink);
00585         }
00586         ISC_LIST_PREPEND(*new_bin, e, hlink);
00587         e->hash_gen = rrl->hash_gen;
00588         e->key = key;
00589         e->ts_valid = ISC_FALSE;
00590         ref_entry(rrl, e, probes, now);
00591         return (e);
00592 }
00593 
00594 static void
00595 debit_log(const dns_rrl_entry_t *e, int age, const char *action) {
00596         char buf[sizeof("age=12345678")];
00597         const char *age_str;
00598 
00599         if (age == DNS_RRL_FOREVER) {
00600                 age_str = "";
00601         } else {
00602                 snprintf(buf, sizeof(buf), "age=%d", age);
00603                 age_str = buf;
00604         }
00605         isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00606                       DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG3,
00607                       "rrl %08x %6s  responses=%-3d %s",
00608                       hash_key(&e->key), age_str, e->responses, action);
00609 }
00610 
00611 static inline dns_rrl_result_t
00612 debit_rrl_entry(dns_rrl_t *rrl, dns_rrl_entry_t *e, double qps, double scale,
00613                 const isc_sockaddr_t *client_addr, isc_stdtime_t now,
00614                 char *log_buf, unsigned int log_buf_len)
00615 {
00616         int rate, new_rate, slip, new_slip, age, log_secs, min;
00617         dns_rrl_rate_t *ratep;
00618         dns_rrl_entry_t const *credit_e;
00619 
00620         /*
00621          * Pick the rate counter.
00622          * Optionally adjust the rate by the estimated query/second rate.
00623          */
00624         ratep = get_rate(rrl, e->key.s.rtype);
00625         rate = ratep->r;
00626         if (rate == 0)
00627                 return (DNS_RRL_RESULT_OK);
00628 
00629         if (scale < 1.0) {
00630                 /*
00631                  * The limit for clients that have used TCP is not scaled.
00632                  */
00633                 credit_e = get_entry(rrl, client_addr,
00634                                      0, dns_rdatatype_none, NULL,
00635                                      DNS_RRL_RTYPE_TCP, now, ISC_FALSE,
00636                                      log_buf, log_buf_len);
00637                 if (credit_e != NULL) {
00638                         age = get_age(rrl, e, now);
00639                         if (age < rrl->window)
00640                                 scale = 1.0;
00641                 }
00642         }
00643         if (scale < 1.0) {
00644                 new_rate = (int) (rate * scale);
00645                 if (new_rate < 1)
00646                         new_rate = 1;
00647                 if (ratep->scaled != new_rate) {
00648                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00649                                       DNS_LOGMODULE_REQUEST,
00650                                       DNS_RRL_LOG_DEBUG1,
00651                                       "%d qps scaled %s by %.2f"
00652                                       " from %d to %d",
00653                                       (int)qps, ratep->str, scale,
00654                                       rate, new_rate);
00655                         rate = new_rate;
00656                         ratep->scaled = rate;
00657                 }
00658         }
00659 
00660         min = -rrl->window * rate;
00661 
00662         /*
00663          * Treat time jumps into the recent past as no time.
00664          * Treat entries older than the window as if they were just created
00665          * Credit other entries.
00666          */
00667         age = get_age(rrl, e, now);
00668         if (age > 0) {
00669                 /*
00670                  * Credit tokens earned during elapsed time.
00671                  */
00672                 if (age > rrl->window) {
00673                         e->responses = rate;
00674                         e->slip_cnt = 0;
00675                 } else {
00676                         e->responses += rate*age;
00677                         if (e->responses > rate) {
00678                                 e->responses = rate;
00679                                 e->slip_cnt = 0;
00680                         }
00681                 }
00682                 /*
00683                  * Find the seconds since last log message without overflowing
00684                  * small counter.  This counter is reset when an entry is
00685                  * created.  It is not necessarily reset when some requests
00686                  * are answered provided other requests continue to be dropped
00687                  * or slipped.  This can happen when the request rate is just
00688                  * at the limit.
00689                  */
00690                 if (e->logged) {
00691                         log_secs = e->log_secs;
00692                         log_secs += age;
00693                         if (log_secs > DNS_RRL_MAX_LOG_SECS || log_secs < 0)
00694                                 log_secs = DNS_RRL_MAX_LOG_SECS;
00695                         e->log_secs = log_secs;
00696                 }
00697         }
00698         set_age(rrl, e, now);
00699 
00700         /*
00701          * Debit the entry for this response.
00702          */
00703         if (--e->responses >= 0) {
00704                 if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
00705                         debit_log(e, age, "");
00706                 return (DNS_RRL_RESULT_OK);
00707         }
00708 
00709         if (e->responses < min)
00710                 e->responses = min;
00711 
00712         /*
00713          * Drop this response unless it should slip or leak.
00714          */
00715         slip = rrl->slip.r;
00716         if (slip > 2 && scale < 1.0) {
00717                 new_slip = (int) (slip * scale);
00718                 if (new_slip < 2)
00719                         new_slip = 2;
00720                 if (rrl->slip.scaled != new_slip) {
00721                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00722                                       DNS_LOGMODULE_REQUEST,
00723                                       DNS_RRL_LOG_DEBUG1,
00724                                       "%d qps scaled slip"
00725                                       " by %.2f from %d to %d",
00726                                       (int)qps, scale,
00727                                       slip, new_slip);
00728                         slip = new_slip;
00729                         rrl->slip.scaled = slip;
00730                 }
00731         }
00732         if (slip != 0 && e->key.s.rtype != DNS_RRL_RTYPE_ALL) {
00733                 if (e->slip_cnt++ == 0) {
00734                         if ((int) e->slip_cnt >= slip)
00735                                 e->slip_cnt = 0;
00736                         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
00737                                 debit_log(e, age, "slip");
00738                         return (DNS_RRL_RESULT_SLIP);
00739                 } else if ((int) e->slip_cnt >= slip) {
00740                         e->slip_cnt = 0;
00741                 }
00742         }
00743 
00744         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
00745                 debit_log(e, age, "drop");
00746         return (DNS_RRL_RESULT_DROP);
00747 }
00748 
00749 static inline dns_rrl_qname_buf_t *
00750 get_qname(dns_rrl_t *rrl, const dns_rrl_entry_t *e) {
00751         dns_rrl_qname_buf_t *qbuf;
00752 
00753         qbuf = rrl->qnames[e->log_qname];
00754         if (qbuf == NULL || qbuf->e != e)
00755                 return (NULL);
00756         return (qbuf);
00757 }
00758 
00759 static inline void
00760 free_qname(dns_rrl_t *rrl, dns_rrl_entry_t *e) {
00761         dns_rrl_qname_buf_t *qbuf;
00762 
00763         qbuf = get_qname(rrl, e);
00764         if (qbuf != NULL) {
00765                 qbuf->e = NULL;
00766                 ISC_LIST_APPEND(rrl->qname_free, qbuf, link);
00767         }
00768 }
00769 
00770 static void
00771 add_log_str(isc_buffer_t *lb, const char *str, unsigned int str_len) {
00772         isc_region_t region;
00773 
00774         isc_buffer_availableregion(lb, &region);
00775         if (str_len >= region.length) {
00776                 if (region.length <= 0)
00777                         return;
00778                 str_len = region.length;
00779         }
00780         memmove(region.base, str, str_len);
00781         isc_buffer_add(lb, str_len);
00782 }
00783 
00784 #define ADD_LOG_CSTR(eb, s) add_log_str(eb, s, sizeof(s)-1)
00785 
00786 /*
00787  * Build strings for the logs
00788  */
00789 static void
00790 make_log_buf(dns_rrl_t *rrl, dns_rrl_entry_t *e,
00791              const char *str1, const char *str2, isc_boolean_t plural,
00792              dns_name_t *qname, isc_boolean_t save_qname,
00793              dns_rrl_result_t rrl_result, isc_result_t resp_result,
00794              char *log_buf, unsigned int log_buf_len)
00795 {
00796         isc_buffer_t lb;
00797         dns_rrl_qname_buf_t *qbuf;
00798         isc_netaddr_t cidr;
00799         char strbuf[ISC_MAX(sizeof("/123"), sizeof("  (12345678)"))];
00800         const char *rstr;
00801         isc_result_t msg_result;
00802 
00803         if (log_buf_len <= 1) {
00804                 if (log_buf_len == 1)
00805                         log_buf[0] = '\0';
00806                 return;
00807         }
00808         isc_buffer_init(&lb, log_buf, log_buf_len-1);
00809 
00810         if (str1 != NULL)
00811                 add_log_str(&lb, str1, strlen(str1));
00812         if (str2 != NULL)
00813                 add_log_str(&lb, str2, strlen(str2));
00814 
00815         switch (rrl_result) {
00816         case DNS_RRL_RESULT_OK:
00817                 break;
00818         case DNS_RRL_RESULT_DROP:
00819                 ADD_LOG_CSTR(&lb, "drop ");
00820                 break;
00821         case DNS_RRL_RESULT_SLIP:
00822                 ADD_LOG_CSTR(&lb, "slip ");
00823                 break;
00824         default:
00825                 INSIST(0);
00826                 break;
00827         }
00828 
00829         switch (e->key.s.rtype) {
00830         case DNS_RRL_RTYPE_QUERY:
00831                 break;
00832         case DNS_RRL_RTYPE_REFERRAL:
00833                 ADD_LOG_CSTR(&lb, "referral ");
00834                 break;
00835         case DNS_RRL_RTYPE_NODATA:
00836                 ADD_LOG_CSTR(&lb, "NODATA ");
00837                 break;
00838         case DNS_RRL_RTYPE_NXDOMAIN:
00839                 ADD_LOG_CSTR(&lb, "NXDOMAIN ");
00840                 break;
00841         case DNS_RRL_RTYPE_ERROR:
00842                 if (resp_result == ISC_R_SUCCESS) {
00843                         ADD_LOG_CSTR(&lb, "error ");
00844                 } else {
00845                         rstr = isc_result_totext(resp_result);
00846                         add_log_str(&lb, rstr, strlen(rstr));
00847                         ADD_LOG_CSTR(&lb, " error ");
00848                 }
00849                 break;
00850         case DNS_RRL_RTYPE_ALL:
00851                 ADD_LOG_CSTR(&lb, "all ");
00852                 break;
00853         default:
00854                 INSIST(0);
00855         }
00856 
00857         if (plural)
00858                 ADD_LOG_CSTR(&lb, "responses to ");
00859         else
00860                 ADD_LOG_CSTR(&lb, "response to ");
00861 
00862         memset(&cidr, 0, sizeof(cidr));
00863         if (e->key.s.ipv6) {
00864                 snprintf(strbuf, sizeof(strbuf), "/%d", rrl->ipv6_prefixlen);
00865                 cidr.family = AF_INET6;
00866                 memset(&cidr.type.in6, 0,  sizeof(cidr.type.in6));
00867                 memmove(&cidr.type.in6, e->key.s.ip, sizeof(e->key.s.ip));
00868         } else {
00869                 snprintf(strbuf, sizeof(strbuf), "/%d", rrl->ipv4_prefixlen);
00870                 cidr.family = AF_INET;
00871                 cidr.type.in.s_addr = e->key.s.ip[0];
00872         }
00873         msg_result = isc_netaddr_totext(&cidr, &lb);
00874         if (msg_result != ISC_R_SUCCESS)
00875                 ADD_LOG_CSTR(&lb, "?");
00876         add_log_str(&lb, strbuf, strlen(strbuf));
00877 
00878         if (e->key.s.rtype == DNS_RRL_RTYPE_QUERY ||
00879             e->key.s.rtype == DNS_RRL_RTYPE_REFERRAL ||
00880             e->key.s.rtype == DNS_RRL_RTYPE_NODATA ||
00881             e->key.s.rtype == DNS_RRL_RTYPE_NXDOMAIN) {
00882                 qbuf = get_qname(rrl, e);
00883                 if (save_qname && qbuf == NULL &&
00884                     qname != NULL && dns_name_isabsolute(qname)) {
00885                         /*
00886                          * Capture the qname for the "stop limiting" message.
00887                          */
00888                         qbuf = ISC_LIST_TAIL(rrl->qname_free);
00889                         if (qbuf != NULL) {
00890                                 ISC_LIST_UNLINK(rrl->qname_free, qbuf, link);
00891                         } else if (rrl->num_qnames < DNS_RRL_QNAMES) {
00892                                 qbuf = isc_mem_get(rrl->mctx, sizeof(*qbuf));
00893                                 if (qbuf != NULL) {
00894                                         memset(qbuf, 0, sizeof(*qbuf));
00895                                         ISC_LINK_INIT(qbuf, link);
00896                                         qbuf->index = rrl->num_qnames;
00897                                         rrl->qnames[rrl->num_qnames++] = qbuf;
00898                                 } else {
00899                                         isc_log_write(dns_lctx,
00900                                                       DNS_LOGCATEGORY_RRL,
00901                                                       DNS_LOGMODULE_REQUEST,
00902                                                       DNS_RRL_LOG_FAIL,
00903                                                       "isc_mem_get(%d)"
00904                                                       " failed for RRL qname",
00905                                                       (int)sizeof(*qbuf));
00906                                 }
00907                         }
00908                         if (qbuf != NULL) {
00909                                 e->log_qname = qbuf->index;
00910                                 qbuf->e = e;
00911                                 dns_fixedname_init(&qbuf->qname);
00912                                 dns_name_copy(qname,
00913                                               dns_fixedname_name(&qbuf->qname),
00914                                               NULL);
00915                         }
00916                 }
00917                 if (qbuf != NULL)
00918                         qname = dns_fixedname_name(&qbuf->qname);
00919                 if (qname != NULL) {
00920                         ADD_LOG_CSTR(&lb, " for ");
00921                         (void)dns_name_totext(qname, ISC_TRUE, &lb);
00922                 } else {
00923                         ADD_LOG_CSTR(&lb, " for (?)");
00924                 }
00925                 if (e->key.s.rtype != DNS_RRL_RTYPE_NXDOMAIN) {
00926                         ADD_LOG_CSTR(&lb, " ");
00927                         (void)dns_rdataclass_totext(e->key.s.qclass, &lb);
00928                         if (e->key.s.rtype == DNS_RRL_RTYPE_QUERY) {
00929                                 ADD_LOG_CSTR(&lb, " ");
00930                                 (void)dns_rdatatype_totext(e->key.s.qtype, &lb);
00931                         }
00932                 }
00933                 snprintf(strbuf, sizeof(strbuf), "  (%08x)",
00934                          e->key.s.qname_hash);
00935                 add_log_str(&lb, strbuf, strlen(strbuf));
00936         }
00937 
00938         /*
00939          * We saved room for '\0'.
00940          */
00941         log_buf[isc_buffer_usedlength(&lb)] = '\0';
00942 }
00943 
00944 static void
00945 log_end(dns_rrl_t *rrl, dns_rrl_entry_t *e, isc_boolean_t early,
00946         char *log_buf, unsigned int log_buf_len)
00947 {
00948         if (e->logged) {
00949                 make_log_buf(rrl, e,
00950                              early ? "*" : NULL,
00951                              rrl->log_only ? "would stop limiting "
00952                                            : "stop limiting ",
00953                              ISC_TRUE, NULL, ISC_FALSE,
00954                              DNS_RRL_RESULT_OK, ISC_R_SUCCESS,
00955                              log_buf, log_buf_len);
00956                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
00957                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
00958                               "%s", log_buf);
00959                 free_qname(rrl, e);
00960                 e->logged = ISC_FALSE;
00961                 --rrl->num_logged;
00962         }
00963 }
00964 
00965 /*
00966  * Log messages for streams that have stopped being rate limited.
00967  */
00968 static void
00969 log_stops(dns_rrl_t *rrl, isc_stdtime_t now, int limit,
00970           char *log_buf, unsigned int log_buf_len)
00971 {
00972         dns_rrl_entry_t *e;
00973         int age;
00974 
00975         for (e = rrl->last_logged; e != NULL; e = ISC_LIST_PREV(e, lru)) {
00976                 if (!e->logged)
00977                         continue;
00978                 if (now != 0) {
00979                         age = get_age(rrl, e, now);
00980                         if (age < DNS_RRL_STOP_LOG_SECS ||
00981                             response_balance(rrl, e, age) < 0)
00982                                 break;
00983                 }
00984 
00985                 log_end(rrl, e, now == 0, log_buf, log_buf_len);
00986                 if (rrl->num_logged <= 0)
00987                         break;
00988 
00989                 /*
00990                  * Too many messages could stall real work.
00991                  */
00992                 if (--limit < 0) {
00993                         rrl->last_logged = ISC_LIST_PREV(e, lru);
00994                         return;
00995                 }
00996         }
00997         if (e == NULL) {
00998                 INSIST(rrl->num_logged == 0);
00999                 rrl->log_stops_time = now;
01000         }
01001         rrl->last_logged = e;
01002 }
01003 
01004 /*
01005  * Main rate limit interface.
01006  */
01007 dns_rrl_result_t
01008 dns_rrl(dns_view_t *view,
01009         const isc_sockaddr_t *client_addr, isc_boolean_t is_tcp,
01010         dns_rdataclass_t qclass, dns_rdatatype_t qtype,
01011         dns_name_t *qname, isc_result_t resp_result, isc_stdtime_t now,
01012         isc_boolean_t wouldlog, char *log_buf, unsigned int log_buf_len)
01013 {
01014         dns_rrl_t *rrl;
01015         dns_rrl_rtype_t rtype;
01016         dns_rrl_entry_t *e;
01017         isc_netaddr_t netclient;
01018         int secs;
01019         double qps, scale;
01020         int exempt_match;
01021         isc_result_t result;
01022         dns_rrl_result_t rrl_result;
01023 
01024         INSIST(log_buf != NULL && log_buf_len > 0);
01025 
01026         rrl = view->rrl;
01027         if (rrl->exempt != NULL) {
01028                 isc_netaddr_fromsockaddr(&netclient, client_addr);
01029                 result = dns_acl_match(&netclient, NULL, rrl->exempt,
01030                                        &view->aclenv, &exempt_match, NULL);
01031                 if (result == ISC_R_SUCCESS && exempt_match > 0)
01032                         return (DNS_RRL_RESULT_OK);
01033         }
01034 
01035         LOCK(&rrl->lock);
01036 
01037         /*
01038          * Estimate total query per second rate when scaling by qps.
01039          */
01040         if (rrl->qps_scale == 0) {
01041                 qps = 0.0;
01042                 scale = 1.0;
01043         } else {
01044                 ++rrl->qps_responses;
01045                 secs = delta_rrl_time(rrl->qps_time, now);
01046                 if (secs <= 0) {
01047                         qps = rrl->qps;
01048                 } else {
01049                         qps = (1.0*rrl->qps_responses) / secs;
01050                         if (secs >= rrl->window) {
01051                                 if (isc_log_wouldlog(dns_lctx,
01052                                                      DNS_RRL_LOG_DEBUG3))
01053                                         isc_log_write(dns_lctx,
01054                                                       DNS_LOGCATEGORY_RRL,
01055                                                       DNS_LOGMODULE_REQUEST,
01056                                                       DNS_RRL_LOG_DEBUG3,
01057                                                       "%d responses/%d seconds"
01058                                                       " = %d qps",
01059                                                       rrl->qps_responses, secs,
01060                                                       (int)qps);
01061                                 rrl->qps = qps;
01062                                 rrl->qps_responses = 0;
01063                                 rrl->qps_time = now;
01064                         } else if (qps < rrl->qps) {
01065                                 qps = rrl->qps;
01066                         }
01067                 }
01068                 scale = rrl->qps_scale / qps;
01069         }
01070 
01071         /*
01072          * Do maintenance once per second.
01073          */
01074         if (rrl->num_logged > 0 && rrl->log_stops_time != now)
01075                 log_stops(rrl, now, 8, log_buf, log_buf_len);
01076 
01077         /*
01078          * Notice TCP responses when scaling limits by qps.
01079          * Do not try to rate limit TCP responses.
01080          */
01081         if (is_tcp) {
01082                 if (scale < 1.0) {
01083                         e = get_entry(rrl, client_addr,
01084                                       0, dns_rdatatype_none, NULL,
01085                                       DNS_RRL_RTYPE_TCP, now, ISC_TRUE,
01086                                       log_buf, log_buf_len);
01087                         if (e != NULL) {
01088                                 e->responses = -(rrl->window+1);
01089                                 set_age(rrl, e, now);
01090                         }
01091                 }
01092                 UNLOCK(&rrl->lock);
01093                 return (ISC_R_SUCCESS);
01094         }
01095 
01096         /*
01097          * Find the right kind of entry, creating it if necessary.
01098          * If that is impossible, then nothing more can be done
01099          */
01100         switch (resp_result) {
01101         case ISC_R_SUCCESS:
01102                 rtype = DNS_RRL_RTYPE_QUERY;
01103                 break;
01104         case DNS_R_DELEGATION:
01105                 rtype = DNS_RRL_RTYPE_REFERRAL;
01106                 break;
01107         case DNS_R_NXRRSET:
01108                 rtype = DNS_RRL_RTYPE_NODATA;
01109                 break;
01110         case DNS_R_NXDOMAIN:
01111                 rtype = DNS_RRL_RTYPE_NXDOMAIN;
01112                 break;
01113         default:
01114                 rtype = DNS_RRL_RTYPE_ERROR;
01115                 break;
01116         }
01117         e = get_entry(rrl, client_addr, qclass, qtype, qname, rtype,
01118                       now, ISC_TRUE, log_buf, log_buf_len);
01119         if (e == NULL) {
01120                 UNLOCK(&rrl->lock);
01121                 return (DNS_RRL_RESULT_OK);
01122         }
01123 
01124         if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG1)) {
01125                 /*
01126                  * Do not worry about speed or releasing the lock.
01127                  * This message appears before messages from debit_rrl_entry().
01128                  */
01129                 make_log_buf(rrl, e, "consider limiting ", NULL, ISC_FALSE,
01130                              qname, ISC_FALSE, DNS_RRL_RESULT_OK, resp_result,
01131                              log_buf, log_buf_len);
01132                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
01133                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG1,
01134                               "%s", log_buf);
01135         }
01136 
01137         rrl_result = debit_rrl_entry(rrl, e, qps, scale, client_addr, now,
01138                                      log_buf, log_buf_len);
01139 
01140         if (rrl->all_per_second.r != 0) {
01141                 /*
01142                  * We must debit the all-per-second token bucket if we have
01143                  * an all-per-second limit for the IP address.
01144                  * The all-per-second limit determines the log message
01145                  * when both limits are hit.
01146                  * The response limiting must continue if the
01147                  * all-per-second limiting lapses.
01148                  */
01149                 dns_rrl_entry_t *e_all;
01150                 dns_rrl_result_t rrl_all_result;
01151 
01152                 e_all = get_entry(rrl, client_addr,
01153                                   0, dns_rdatatype_none, NULL,
01154                                   DNS_RRL_RTYPE_ALL, now, ISC_TRUE,
01155                                   log_buf, log_buf_len);
01156                 if (e_all == NULL) {
01157                         UNLOCK(&rrl->lock);
01158                         return (DNS_RRL_RESULT_OK);
01159                 }
01160                 rrl_all_result = debit_rrl_entry(rrl, e_all, qps, scale,
01161                                                  client_addr, now,
01162                                                  log_buf, log_buf_len);
01163                 if (rrl_all_result != DNS_RRL_RESULT_OK) {
01164                         int level;
01165 
01166                         e = e_all;
01167                         rrl_result = rrl_all_result;
01168                         if (rrl_result == DNS_RRL_RESULT_OK)
01169                                 level = DNS_RRL_LOG_DEBUG2;
01170                         else
01171                                 level = DNS_RRL_LOG_DEBUG1;
01172                         if (isc_log_wouldlog(dns_lctx, level)) {
01173                                 make_log_buf(rrl, e,
01174                                              "prefer all-per-second limiting ",
01175                                              NULL, ISC_TRUE, qname, ISC_FALSE,
01176                                              DNS_RRL_RESULT_OK, resp_result,
01177                                              log_buf, log_buf_len);
01178                                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
01179                                               DNS_LOGMODULE_REQUEST, level,
01180                                               "%s", log_buf);
01181                         }
01182                 }
01183         }
01184 
01185         if (rrl_result == DNS_RRL_RESULT_OK) {
01186                 UNLOCK(&rrl->lock);
01187                 return (DNS_RRL_RESULT_OK);
01188         }
01189 
01190         /*
01191          * Log occassionally in the rate-limit category.
01192          */
01193         if ((!e->logged || e->log_secs >= DNS_RRL_MAX_LOG_SECS) &&
01194             isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP)) {
01195                 make_log_buf(rrl, e, rrl->log_only ? "would " : NULL,
01196                              e->logged ? "continue limiting " : "limit ",
01197                              ISC_TRUE, qname, ISC_TRUE,
01198                              DNS_RRL_RESULT_OK, resp_result,
01199                              log_buf, log_buf_len);
01200                 if (!e->logged) {
01201                         e->logged = ISC_TRUE;
01202                         if (++rrl->num_logged <= 1)
01203                                 rrl->last_logged = e;
01204                 }
01205                 e->log_secs = 0;
01206 
01207                 /*
01208                  * Avoid holding the lock.
01209                  */
01210                 if (!wouldlog) {
01211                         UNLOCK(&rrl->lock);
01212                         e = NULL;
01213                 }
01214                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
01215                               DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
01216                               "%s", log_buf);
01217         }
01218 
01219         /*
01220          * Make a log message for the caller.
01221          */
01222         if (wouldlog)
01223                 make_log_buf(rrl, e,
01224                              rrl->log_only ? "would rate limit " : "rate limit ",
01225                              NULL, ISC_FALSE, qname, ISC_FALSE,
01226                              rrl_result, resp_result, log_buf, log_buf_len);
01227 
01228         if (e != NULL) {
01229                 /*
01230                  * Do not save the qname unless we might need it for
01231                  * the ending log message.
01232                  */
01233                 if (!e->logged)
01234                         free_qname(rrl, e);
01235                 UNLOCK(&rrl->lock);
01236         }
01237 
01238         return (rrl_result);
01239 }
01240 
01241 void
01242 dns_rrl_view_destroy(dns_view_t *view) {
01243         dns_rrl_t *rrl;
01244         dns_rrl_block_t *b;
01245         dns_rrl_hash_t *h;
01246         char log_buf[DNS_RRL_LOG_BUF_LEN];
01247         int i;
01248 
01249         rrl = view->rrl;
01250         if (rrl == NULL)
01251                 return;
01252         view->rrl = NULL;
01253 
01254         /*
01255          * Assume the caller takes care of locking the view and anything else.
01256          */
01257 
01258         if (rrl->num_logged > 0)
01259                 log_stops(rrl, 0, ISC_INT32_MAX, log_buf, sizeof(log_buf));
01260 
01261         for (i = 0; i < DNS_RRL_QNAMES; ++i) {
01262                 if (rrl->qnames[i] == NULL)
01263                         break;
01264                 isc_mem_put(rrl->mctx, rrl->qnames[i], sizeof(*rrl->qnames[i]));
01265         }
01266 
01267         if (rrl->exempt != NULL)
01268                 dns_acl_detach(&rrl->exempt);
01269 
01270         DESTROYLOCK(&rrl->lock);
01271 
01272         while (!ISC_LIST_EMPTY(rrl->blocks)) {
01273                 b = ISC_LIST_HEAD(rrl->blocks);
01274                 ISC_LIST_UNLINK(rrl->blocks, b, link);
01275                 isc_mem_put(rrl->mctx, b, b->size);
01276         }
01277 
01278         h = rrl->hash;
01279         if (h != NULL)
01280                 isc_mem_put(rrl->mctx, h,
01281                             sizeof(*h) + (h->length - 1) * sizeof(h->bins[0]));
01282 
01283         h = rrl->old_hash;
01284         if (h != NULL)
01285                 isc_mem_put(rrl->mctx, h,
01286                             sizeof(*h) + (h->length - 1) * sizeof(h->bins[0]));
01287 
01288         isc_mem_putanddetach(&rrl->mctx, rrl, sizeof(*rrl));
01289 }
01290 
01291 isc_result_t
01292 dns_rrl_init(dns_rrl_t **rrlp, dns_view_t *view, int min_entries) {
01293         dns_rrl_t *rrl;
01294         isc_result_t result;
01295 
01296         *rrlp = NULL;
01297 
01298         rrl = isc_mem_get(view->mctx, sizeof(*rrl));
01299         if (rrl == NULL)
01300                 return (ISC_R_NOMEMORY);
01301         memset(rrl, 0, sizeof(*rrl));
01302         isc_mem_attach(view->mctx, &rrl->mctx);
01303         result = isc_mutex_init(&rrl->lock);
01304         if (result != ISC_R_SUCCESS) {
01305                 isc_mem_putanddetach(&rrl->mctx, rrl, sizeof(*rrl));
01306                 return (result);
01307         }
01308         isc_stdtime_get(&rrl->ts_bases[0]);
01309 
01310         view->rrl = rrl;
01311 
01312         result = expand_entries(rrl, min_entries);
01313         if (result != ISC_R_SUCCESS) {
01314                 dns_rrl_view_destroy(view);
01315                 return (result);
01316         }
01317         result = expand_rrl_hash(rrl, 0);
01318         if (result != ISC_R_SUCCESS) {
01319                 dns_rrl_view_destroy(view);
01320                 return (result);
01321         }
01322 
01323         *rrlp = rrl;
01324         return (ISC_R_SUCCESS);
01325 }

Generated on Tue Apr 28 17:41:01 2015 by Doxygen 1.5.4 for BIND9 Internals 9.11.0pre-alpha