"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.16.7/lib/dns/badcache.c" (4 Sep 2020, 13056 Bytes) of package /linux/misc/dns/bind9/9.16.7/bind-9.16.7.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "badcache.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 9.17.3_vs_9.17.4.

    1 /*
    2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
    3  *
    4  * This Source Code Form is subject to the terms of the Mozilla Public
    5  * License, v. 2.0. If a copy of the MPL was not distributed with this
    6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
    7  *
    8  * See the COPYRIGHT file distributed with this work for additional
    9  * information regarding copyright ownership.
   10  */
   11 
   12 /*! \file */
   13 
   14 #include <inttypes.h>
   15 #include <stdbool.h>
   16 
   17 #include <isc/buffer.h>
   18 #include <isc/hash.h>
   19 #include <isc/log.h>
   20 #include <isc/mem.h>
   21 #include <isc/mutex.h>
   22 #include <isc/platform.h>
   23 #include <isc/print.h>
   24 #include <isc/rwlock.h>
   25 #include <isc/string.h>
   26 #include <isc/time.h>
   27 #include <isc/util.h>
   28 
   29 #include <dns/badcache.h>
   30 #include <dns/name.h>
   31 #include <dns/rdatatype.h>
   32 #include <dns/types.h>
   33 
   34 typedef struct dns_bcentry dns_bcentry_t;
   35 
   36 struct dns_badcache {
   37     unsigned int magic;
   38     isc_rwlock_t lock;
   39     isc_mem_t *mctx;
   40 
   41     isc_mutex_t *tlocks;
   42     dns_bcentry_t **table;
   43 
   44     atomic_uint_fast32_t count;
   45     atomic_uint_fast32_t sweep;
   46 
   47     unsigned int minsize;
   48     unsigned int size;
   49 };
   50 
   51 #define BADCACHE_MAGIC    ISC_MAGIC('B', 'd', 'C', 'a')
   52 #define VALID_BADCACHE(m) ISC_MAGIC_VALID(m, BADCACHE_MAGIC)
   53 
   54 struct dns_bcentry {
   55     dns_bcentry_t *next;
   56     dns_rdatatype_t type;
   57     isc_time_t expire;
   58     uint32_t flags;
   59     unsigned int hashval;
   60     dns_name_t name;
   61 };
   62 
   63 static void
   64 badcache_resize(dns_badcache_t *bc, isc_time_t *now);
   65 
   66 isc_result_t
   67 dns_badcache_init(isc_mem_t *mctx, unsigned int size, dns_badcache_t **bcp) {
   68     dns_badcache_t *bc = NULL;
   69     unsigned int i;
   70 
   71     REQUIRE(bcp != NULL && *bcp == NULL);
   72     REQUIRE(mctx != NULL);
   73 
   74     bc = isc_mem_get(mctx, sizeof(dns_badcache_t));
   75     memset(bc, 0, sizeof(dns_badcache_t));
   76 
   77     isc_mem_attach(mctx, &bc->mctx);
   78     isc_rwlock_init(&bc->lock, 0, 0);
   79 
   80     bc->table = isc_mem_get(bc->mctx, sizeof(*bc->table) * size);
   81     bc->tlocks = isc_mem_get(bc->mctx, sizeof(isc_mutex_t) * size);
   82     for (i = 0; i < size; i++) {
   83         isc_mutex_init(&bc->tlocks[i]);
   84     }
   85     bc->size = bc->minsize = size;
   86     memset(bc->table, 0, bc->size * sizeof(dns_bcentry_t *));
   87 
   88     atomic_init(&bc->count, 0);
   89     atomic_init(&bc->sweep, 0);
   90     bc->magic = BADCACHE_MAGIC;
   91 
   92     *bcp = bc;
   93     return (ISC_R_SUCCESS);
   94 }
   95 
   96 void
   97 dns_badcache_destroy(dns_badcache_t **bcp) {
   98     dns_badcache_t *bc;
   99     unsigned int i;
  100 
  101     REQUIRE(bcp != NULL && *bcp != NULL);
  102     bc = *bcp;
  103     *bcp = NULL;
  104 
  105     dns_badcache_flush(bc);
  106 
  107     bc->magic = 0;
  108     isc_rwlock_destroy(&bc->lock);
  109     for (i = 0; i < bc->size; i++) {
  110         isc_mutex_destroy(&bc->tlocks[i]);
  111     }
  112     isc_mem_put(bc->mctx, bc->table, sizeof(dns_bcentry_t *) * bc->size);
  113     isc_mem_put(bc->mctx, bc->tlocks, sizeof(isc_mutex_t) * bc->size);
  114     isc_mem_putanddetach(&bc->mctx, bc, sizeof(dns_badcache_t));
  115 }
  116 
  117 static void
  118 badcache_resize(dns_badcache_t *bc, isc_time_t *now) {
  119     dns_bcentry_t **newtable, *bad, *next;
  120     isc_mutex_t *newlocks;
  121     unsigned int newsize, i;
  122     bool grow;
  123 
  124     RWLOCK(&bc->lock, isc_rwlocktype_write);
  125 
  126     /*
  127      * XXXWPK we will have a thundering herd problem here,
  128      * as all threads will wait on the RWLOCK when there's
  129      * a need to resize badcache.
  130      * However, it happens so rarely it should not be a
  131      * performance issue. This is because we double the
  132      * size every time we grow it, and we don't shrink
  133      * unless the number of entries really shrunk. In a
  134      * high load situation, the number of badcache entries
  135      * will eventually stabilize.
  136      */
  137     if (atomic_load_relaxed(&bc->count) > bc->size * 8) {
  138         grow = true;
  139     } else if (atomic_load_relaxed(&bc->count) < bc->size * 2 &&
  140            bc->size > bc->minsize)
  141     {
  142         grow = false;
  143     } else {
  144         /* Someone resized it already, bail. */
  145         RWUNLOCK(&bc->lock, isc_rwlocktype_write);
  146         return;
  147     }
  148 
  149     if (grow) {
  150         newsize = bc->size * 2 + 1;
  151     } else {
  152         newsize = (bc->size - 1) / 2;
  153 #ifdef __clang_analyzer__
  154         /*
  155          * XXXWPK there's a bug in clang static analyzer -
  156          * `value % newsize` is considered undefined even though
  157          * we check if newsize is larger than 0. This helps.
  158          */
  159         newsize += 1;
  160 #endif
  161     }
  162     RUNTIME_CHECK(newsize > 0);
  163 
  164     newtable = isc_mem_get(bc->mctx, sizeof(dns_bcentry_t *) * newsize);
  165     memset(newtable, 0, sizeof(dns_bcentry_t *) * newsize);
  166 
  167     newlocks = isc_mem_get(bc->mctx, sizeof(isc_mutex_t) * newsize);
  168 
  169     /* Copy existing mutexes */
  170     for (i = 0; i < newsize && i < bc->size; i++) {
  171         newlocks[i] = bc->tlocks[i];
  172     }
  173     /* Initialize additional mutexes if we're growing */
  174     for (i = bc->size; i < newsize; i++) {
  175         isc_mutex_init(&newlocks[i]);
  176     }
  177     /* Destroy extra mutexes if we're shrinking */
  178     for (i = newsize; i < bc->size; i++) {
  179         isc_mutex_destroy(&bc->tlocks[i]);
  180     }
  181 
  182     for (i = 0; atomic_load_relaxed(&bc->count) > 0 && i < bc->size; i++) {
  183         for (bad = bc->table[i]; bad != NULL; bad = next) {
  184             next = bad->next;
  185             if (isc_time_compare(&bad->expire, now) < 0) {
  186                 isc_mem_put(bc->mctx, bad,
  187                         sizeof(*bad) + bad->name.length);
  188                 atomic_fetch_sub_relaxed(&bc->count, 1);
  189             } else {
  190                 bad->next = newtable[bad->hashval % newsize];
  191                 newtable[bad->hashval % newsize] = bad;
  192             }
  193         }
  194         bc->table[i] = NULL;
  195     }
  196 
  197     isc_mem_put(bc->mctx, bc->tlocks, sizeof(isc_mutex_t) * bc->size);
  198     bc->tlocks = newlocks;
  199 
  200     isc_mem_put(bc->mctx, bc->table, sizeof(*bc->table) * bc->size);
  201     bc->size = newsize;
  202     bc->table = newtable;
  203 
  204     RWUNLOCK(&bc->lock, isc_rwlocktype_write);
  205 }
  206 
  207 void
  208 dns_badcache_add(dns_badcache_t *bc, const dns_name_t *name,
  209          dns_rdatatype_t type, bool update, uint32_t flags,
  210          isc_time_t *expire) {
  211     isc_result_t result;
  212     unsigned int hashval, hash;
  213     dns_bcentry_t *bad, *prev, *next;
  214     isc_time_t now;
  215     bool resize = false;
  216 
  217     REQUIRE(VALID_BADCACHE(bc));
  218     REQUIRE(name != NULL);
  219     REQUIRE(expire != NULL);
  220 
  221     RWLOCK(&bc->lock, isc_rwlocktype_read);
  222 
  223     result = isc_time_now(&now);
  224     if (result != ISC_R_SUCCESS) {
  225         isc_time_settoepoch(&now);
  226     }
  227 
  228     hashval = dns_name_hash(name, false);
  229     hash = hashval % bc->size;
  230     LOCK(&bc->tlocks[hash]);
  231     prev = NULL;
  232     for (bad = bc->table[hash]; bad != NULL; bad = next) {
  233         next = bad->next;
  234         if (bad->type == type && dns_name_equal(name, &bad->name)) {
  235             if (update) {
  236                 bad->expire = *expire;
  237                 bad->flags = flags;
  238             }
  239             break;
  240         }
  241         if (isc_time_compare(&bad->expire, &now) < 0) {
  242             if (prev == NULL) {
  243                 bc->table[hash] = bad->next;
  244             } else {
  245                 prev->next = bad->next;
  246             }
  247             isc_mem_put(bc->mctx, bad,
  248                     sizeof(*bad) + bad->name.length);
  249             atomic_fetch_sub_relaxed(&bc->count, 1);
  250         } else {
  251             prev = bad;
  252         }
  253     }
  254 
  255     if (bad == NULL) {
  256         isc_buffer_t buffer;
  257         bad = isc_mem_get(bc->mctx, sizeof(*bad) + name->length);
  258         bad->type = type;
  259         bad->hashval = hashval;
  260         bad->expire = *expire;
  261         bad->flags = flags;
  262         isc_buffer_init(&buffer, bad + 1, name->length);
  263         dns_name_init(&bad->name, NULL);
  264         dns_name_copy(name, &bad->name, &buffer);
  265         bad->next = bc->table[hash];
  266         bc->table[hash] = bad;
  267         unsigned count = atomic_fetch_add_relaxed(&bc->count, 1);
  268         if ((count > bc->size * 8) ||
  269             (count < bc->size * 2 && bc->size > bc->minsize)) {
  270             resize = true;
  271         }
  272     } else {
  273         bad->expire = *expire;
  274     }
  275 
  276     UNLOCK(&bc->tlocks[hash]);
  277     RWUNLOCK(&bc->lock, isc_rwlocktype_read);
  278     if (resize) {
  279         badcache_resize(bc, &now);
  280     }
  281 }
  282 
  283 bool
  284 dns_badcache_find(dns_badcache_t *bc, const dns_name_t *name,
  285           dns_rdatatype_t type, uint32_t *flagp, isc_time_t *now) {
  286     dns_bcentry_t *bad, *prev, *next;
  287     bool answer = false;
  288     unsigned int i;
  289     unsigned int hash;
  290 
  291     REQUIRE(VALID_BADCACHE(bc));
  292     REQUIRE(name != NULL);
  293     REQUIRE(now != NULL);
  294 
  295     RWLOCK(&bc->lock, isc_rwlocktype_read);
  296 
  297     /*
  298      * XXXMUKS: dns_name_equal() is expensive as it does a
  299      * octet-by-octet comparison, and it can be made better in two
  300      * ways here. First, lowercase the names (use
  301      * dns_name_downcase() instead of dns_name_copy() in
  302      * dns_badcache_add()) so that dns_name_caseequal() can be used
  303      * which the compiler will emit as SIMD instructions. Second,
  304      * don't put multiple copies of the same name in the chain (or
  305      * multiple names will have to be matched for equality), but use
  306      * name->link to store the type specific part.
  307      */
  308 
  309     if (atomic_load_relaxed(&bc->count) == 0) {
  310         goto skip;
  311     }
  312 
  313     hash = dns_name_hash(name, false) % bc->size;
  314     prev = NULL;
  315     LOCK(&bc->tlocks[hash]);
  316     for (bad = bc->table[hash]; bad != NULL; bad = next) {
  317         next = bad->next;
  318         /*
  319          * Search the hash list. Clean out expired records as we go.
  320          */
  321         if (isc_time_compare(&bad->expire, now) < 0) {
  322             if (prev != NULL) {
  323                 prev->next = bad->next;
  324             } else {
  325                 bc->table[hash] = bad->next;
  326             }
  327 
  328             isc_mem_put(bc->mctx, bad,
  329                     sizeof(*bad) + bad->name.length);
  330             atomic_fetch_sub(&bc->count, 1);
  331             continue;
  332         }
  333         if (bad->type == type && dns_name_equal(name, &bad->name)) {
  334             if (flagp != NULL) {
  335                 *flagp = bad->flags;
  336             }
  337             answer = true;
  338             break;
  339         }
  340         prev = bad;
  341     }
  342     UNLOCK(&bc->tlocks[hash]);
  343 skip:
  344 
  345     /*
  346      * Slow sweep to clean out stale records.
  347      */
  348     i = atomic_fetch_add(&bc->sweep, 1) % bc->size;
  349     if (isc_mutex_trylock(&bc->tlocks[i]) == ISC_R_SUCCESS) {
  350         bad = bc->table[i];
  351         if (bad != NULL && isc_time_compare(&bad->expire, now) < 0) {
  352             bc->table[i] = bad->next;
  353             isc_mem_put(bc->mctx, bad,
  354                     sizeof(*bad) + bad->name.length);
  355             atomic_fetch_sub_relaxed(&bc->count, 1);
  356         }
  357         UNLOCK(&bc->tlocks[i]);
  358     }
  359 
  360     RWUNLOCK(&bc->lock, isc_rwlocktype_read);
  361     return (answer);
  362 }
  363 
  364 void
  365 dns_badcache_flush(dns_badcache_t *bc) {
  366     dns_bcentry_t *entry, *next;
  367     unsigned int i;
  368 
  369     RWLOCK(&bc->lock, isc_rwlocktype_write);
  370     REQUIRE(VALID_BADCACHE(bc));
  371 
  372     for (i = 0; atomic_load_relaxed(&bc->count) > 0 && i < bc->size; i++) {
  373         for (entry = bc->table[i]; entry != NULL; entry = next) {
  374             next = entry->next;
  375             isc_mem_put(bc->mctx, entry,
  376                     sizeof(*entry) + entry->name.length);
  377             atomic_fetch_sub_relaxed(&bc->count, 1);
  378         }
  379         bc->table[i] = NULL;
  380     }
  381     RWUNLOCK(&bc->lock, isc_rwlocktype_write);
  382 }
  383 
  384 void
  385 dns_badcache_flushname(dns_badcache_t *bc, const dns_name_t *name) {
  386     dns_bcentry_t *bad, *prev, *next;
  387     isc_result_t result;
  388     isc_time_t now;
  389     unsigned int hash;
  390 
  391     REQUIRE(VALID_BADCACHE(bc));
  392     REQUIRE(name != NULL);
  393 
  394     RWLOCK(&bc->lock, isc_rwlocktype_read);
  395 
  396     result = isc_time_now(&now);
  397     if (result != ISC_R_SUCCESS) {
  398         isc_time_settoepoch(&now);
  399     }
  400     hash = dns_name_hash(name, false) % bc->size;
  401     LOCK(&bc->tlocks[hash]);
  402     prev = NULL;
  403     for (bad = bc->table[hash]; bad != NULL; bad = next) {
  404         int n;
  405         next = bad->next;
  406         n = isc_time_compare(&bad->expire, &now);
  407         if (n < 0 || dns_name_equal(name, &bad->name)) {
  408             if (prev == NULL) {
  409                 bc->table[hash] = bad->next;
  410             } else {
  411                 prev->next = bad->next;
  412             }
  413 
  414             isc_mem_put(bc->mctx, bad,
  415                     sizeof(*bad) + bad->name.length);
  416             atomic_fetch_sub_relaxed(&bc->count, 1);
  417         } else {
  418             prev = bad;
  419         }
  420     }
  421     UNLOCK(&bc->tlocks[hash]);
  422 
  423     RWUNLOCK(&bc->lock, isc_rwlocktype_read);
  424 }
  425 
  426 void
  427 dns_badcache_flushtree(dns_badcache_t *bc, const dns_name_t *name) {
  428     dns_bcentry_t *bad, *prev, *next;
  429     unsigned int i;
  430     int n;
  431     isc_time_t now;
  432     isc_result_t result;
  433 
  434     REQUIRE(VALID_BADCACHE(bc));
  435     REQUIRE(name != NULL);
  436 
  437     /*
  438      * We write lock the tree to avoid relocking every node
  439      * individually.
  440      */
  441     RWLOCK(&bc->lock, isc_rwlocktype_write);
  442 
  443     result = isc_time_now(&now);
  444     if (result != ISC_R_SUCCESS) {
  445         isc_time_settoepoch(&now);
  446     }
  447 
  448     for (i = 0; atomic_load_relaxed(&bc->count) > 0 && i < bc->size; i++) {
  449         prev = NULL;
  450         for (bad = bc->table[i]; bad != NULL; bad = next) {
  451             next = bad->next;
  452             n = isc_time_compare(&bad->expire, &now);
  453             if (n < 0 || dns_name_issubdomain(&bad->name, name)) {
  454                 if (prev == NULL) {
  455                     bc->table[i] = bad->next;
  456                 } else {
  457                     prev->next = bad->next;
  458                 }
  459 
  460                 isc_mem_put(bc->mctx, bad,
  461                         sizeof(*bad) + bad->name.length);
  462                 atomic_fetch_sub_relaxed(&bc->count, 1);
  463             } else {
  464                 prev = bad;
  465             }
  466         }
  467     }
  468 
  469     RWUNLOCK(&bc->lock, isc_rwlocktype_write);
  470 }
  471 
  472 void
  473 dns_badcache_print(dns_badcache_t *bc, const char *cachename, FILE *fp) {
  474     char namebuf[DNS_NAME_FORMATSIZE];
  475     char typebuf[DNS_RDATATYPE_FORMATSIZE];
  476     dns_bcentry_t *bad, *next, *prev;
  477     isc_time_t now;
  478     unsigned int i;
  479     uint64_t t;
  480 
  481     REQUIRE(VALID_BADCACHE(bc));
  482     REQUIRE(cachename != NULL);
  483     REQUIRE(fp != NULL);
  484 
  485     /*
  486      * We write lock the tree to avoid relocking every node
  487      * individually.
  488      */
  489     RWLOCK(&bc->lock, isc_rwlocktype_write);
  490     fprintf(fp, ";\n; %s\n;\n", cachename);
  491 
  492     TIME_NOW(&now);
  493     for (i = 0; atomic_load_relaxed(&bc->count) > 0 && i < bc->size; i++) {
  494         prev = NULL;
  495         for (bad = bc->table[i]; bad != NULL; bad = next) {
  496             next = bad->next;
  497             if (isc_time_compare(&bad->expire, &now) < 0) {
  498                 if (prev != NULL) {
  499                     prev->next = bad->next;
  500                 } else {
  501                     bc->table[i] = bad->next;
  502                 }
  503 
  504                 isc_mem_put(bc->mctx, bad,
  505                         sizeof(*bad) + bad->name.length);
  506                 atomic_fetch_sub_relaxed(&bc->count, 1);
  507                 continue;
  508             }
  509             prev = bad;
  510             dns_name_format(&bad->name, namebuf, sizeof(namebuf));
  511             dns_rdatatype_format(bad->type, typebuf,
  512                          sizeof(typebuf));
  513             t = isc_time_microdiff(&bad->expire, &now);
  514             t /= 1000;
  515             fprintf(fp,
  516                 "; %s/%s [ttl "
  517                 "%" PRIu64 "]\n",
  518                 namebuf, typebuf, t);
  519         }
  520     }
  521     RWUNLOCK(&bc->lock, isc_rwlocktype_write);
  522 }