1. 21 Jul, 2020 1 commit
    • Ondřej Surý's avatar
      Fix the rbt hashtable and grow it when setting max-cache-size · e24bc324
      Ondřej Surý authored
      There were several problems with rbt hashtable implementation:
      
      1. Our internal hashing function returns uint64_t value, but it was
         silently truncated to unsigned int in dns_name_hash() and
         dns_name_fullhash() functions.  As the SipHash 2-4 higher bits are
         more random, we need to use the upper half of the return value.
      
      2. The hashtable implementation in rbt.c was using modulo to pick the
         slot number for the hash table.  This has several problems because
         modulo is: a) slow, b) oblivious to patterns in the input data.  This
         could lead to very uneven distribution of the hashed data in the
         hashtable.  Combined with the single-linked lists we use, it could
         really hog-down the lookup and removal of the nodes from the rbt
         tree[a].  The Fibonacci Hashing is much better fit for the hashtable
         function here.  For longer description, read "Fibonacci Hashing: The
         Optimization that the World Forgot"[b] or just look at the Linux
         kernel.  Also this will make Diego very happy :).
      
      3. The hashtable would rehash every time the number of nodes in the rbt
         tree would exceed 3 * (hashtable size).  The overcommit will make the
         uneven distribution in the hashtable even worse, but the main problem
         lies in the rehashing - every time the database grows beyond the
         limit, each subsequent rehashing will be much slower.  The mitigation
         here is letting the rbt know how big the cache can grown and
         pre-allocate the hashtable to be big enough to actually never need to
         rehash.  This will consume more memory at the start, but since the
         size of the hashtable is capped to `1 << 32` (e.g. 4 mio entries), it
         will only consume maximum of 32GB of memory for hashtable in the
         worst case (and max-cache-size would need to be set to more than
         4TB).  Calling the dns_db_adjusthashsize() will also cap the maximum
         size of the hashtable to the pre-computed number of bits, so it won't
         try to consume more gigabytes of memory than available for the
         database.
      
         FIXME: What is the average size of the rbt node that gets hashed?  I
         chose the pagesize (4k) as initial value to precompute the size of
         the hashtable, but the value is based on feeling and not any real
         data.
      
      For future work, there are more places where we use result of the hash
      value modulo some small number and that would benefit from Fibonacci
      Hashing to get better distribution.
      
      Notes:
      a. A doubly linked list should be used here to speedup the removal of
         the entries from the hashtable.
      b. https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
      e24bc324
  2. 25 May, 2020 1 commit
  3. 19 May, 2020 1 commit
  4. 15 Apr, 2020 1 commit
    • Ondřej Surý's avatar
      Workaround MSVC warning C4477 · 60c632ab
      Ondřej Surý authored
      Due to a way the stdatomic.h shim is implemented on Windows, the MSVC
      always things that the outside type is the largest - atomic_(u)int_fast64_t.
      This can lead to false positives as this one:
      
        lib\dns\adb.c(3678): warning C4477: 'fprintf' : format string '%u' requires an argument of type 'unsigned int', but variadic argument 2 has type 'unsigned __int64'
      
      We workaround the issue by loading the value in a scoped local variable
      with correct type first.
      60c632ab
  5. 14 Feb, 2020 1 commit
  6. 13 Feb, 2020 3 commits
    • Evan Hunt's avatar
      apply the modified style · e851ed0b
      Evan Hunt authored
      e851ed0b
    • Ondřej Surý's avatar
      Use clang-tidy to add curly braces around one-line statements · 056e133c
      Ondřej Surý authored
      The command used to reformat the files in this commit was:
      
      ./util/run-clang-tidy \
      	-clang-tidy-binary clang-tidy-11
      	-clang-apply-replacements-binary clang-apply-replacements-11 \
      	-checks=-*,readability-braces-around-statements \
      	-j 9 \
      	-fix \
      	-format \
      	-style=file \
      	-quiet
      clang-format -i --style=format $(git ls-files '*.c' '*.h')
      uncrustify -c .uncrustify.cfg --replace --no-backup $(git ls-files '*.c' '*.h')
      clang-format -i --style=format $(git ls-files '*.c' '*.h')
      056e133c
    • Ondřej Surý's avatar
      Use coccinelle to add braces to nested single line statement · 36c6105e
      Ondřej Surý authored
      Both clang-tidy and uncrustify chokes on statement like this:
      
      for (...)
      	if (...)
      		break;
      
      This commit uses a very simple semantic patch (below) to add braces around such
      statements.
      
      Semantic patch used:
      
      @@
      statement S;
      expression E;
      @@
      
      while (...)
      - if (E) S
      + { if (E) { S } }
      
      @@
      statement S;
      expression E;
      @@
      
      for (...;...;...)
      - if (E) S
      + { if (E) { S } }
      
      @@
      statement S;
      expression E;
      @@
      
      if (...)
      - if (E) S
      + { if (E) { S } }
      36c6105e
  7. 12 Feb, 2020 1 commit
  8. 10 Feb, 2020 1 commit
  9. 03 Feb, 2020 1 commit
  10. 29 Nov, 2019 1 commit
  11. 26 Nov, 2019 2 commits
  12. 18 Nov, 2019 1 commit
  13. 05 Nov, 2019 1 commit
  14. 01 Oct, 2019 2 commits
  15. 23 Jul, 2019 1 commit
  16. 08 Mar, 2019 1 commit
  17. 06 Dec, 2018 1 commit
  18. 22 Nov, 2018 2 commits
  19. 08 Nov, 2018 1 commit
  20. 23 Oct, 2018 4 commits
  21. 08 Aug, 2018 2 commits
  22. 12 Jun, 2018 3 commits
  23. 29 May, 2018 1 commit
    • Ondřej Surý's avatar
      Change isc_random() to be just PRNG, and add isc_nonce_buf() that uses CSPRNG · 99ba29bc
      Ondřej Surý authored
      This commit reverts the previous change to use system provided
      entropy, as (SYS_)getrandom is very slow on Linux because it is
      a syscall.
      
      The change introduced in this commit adds a new call isc_nonce_buf
      that uses CSPRNG from cryptographic library provider to generate
      secure data that can be and must be used for generating nonces.
      Example usage would be DNS cookies.
      
      The isc_random() API has been changed to use fast PRNG that is not
      cryptographically secure, but runs entirely in user space.  Two
      contestants have been considered xoroshiro family of the functions
      by Villa&Blackman and PCG by O'Neill.  After a consideration the
      xoshiro128starstar function has been used as uint32_t random number
      provider because it is very fast and has good enough properties
      for our usage pattern.
      
      The other change introduced in the commit is the more extensive usage
      of isc_random_uniform in places where the usage pattern was
      isc_random() % n to prevent modulo bias.  For usage patterns where
      only 16 or 8 bits are needed (DNS Message ID), the isc_random()
      functions has been renamed to isc_random32(), and isc_random16() and
      isc_random8() functions have been introduced by &-ing the
      isc_random32() output with 0xffff and 0xff.  Please note that the
      functions that uses stripped down bit count doesn't pass our
      NIST SP 800-22 based random test.
      99ba29bc
  24. 16 May, 2018 1 commit
    • Ondřej Surý's avatar
      Replace all random functions with isc_random, isc_random_buf and isc_random_uniform API. · 3a4f820d
      Ondřej Surý authored
      The three functions has been modeled after the arc4random family of
      functions, and they will always return random bytes.
      
      The isc_random family of functions internally use these CSPRNG (if available):
      
      1. getrandom() libc call (might be available on Linux and Solaris)
      2. SYS_getrandom syscall (might be available on Linux, detected at runtime)
      3. arc4random(), arc4random_buf() and arc4random_uniform() (available on BSDs and Mac OS X)
      4. crypto library function:
      4a. RAND_bytes in case OpenSSL
      4b. pkcs_C_GenerateRandom() in case PKCS#11 library
      3a4f820d
  25. 09 Apr, 2018 1 commit
    • Michał Kępień's avatar
      Use dns_fixedname_initname() where possible · 4df4a8e7
      Michał Kępień authored
      Replace dns_fixedname_init() calls followed by dns_fixedname_name()
      calls with calls to dns_fixedname_initname() where it is possible
      without affecting current behavior and/or performance.
      
      This patch was mostly prepared using Coccinelle and the following
      semantic patch:
      
          @@
          expression fixedname, name;
          @@
          -	dns_fixedname_init(&fixedname);
          	...
          -	name = dns_fixedname_name(&fixedname);
          +	name = dns_fixedname_initname(&fixedname);
      
      The resulting set of changes was then manually reviewed to exclude false
      positives and apply minor tweaks.
      
      It is likely that more occurrences of this pattern can be refactored in
      an identical way.  This commit only takes care of the low-hanging fruit.
      4df4a8e7
  26. 06 Apr, 2018 3 commits
  27. 23 Feb, 2018 1 commit