4 ms·

I actually have been doing some work with MaraDNS to have the ability to have a pi-hole sized blacklist. The main source of pi-hole’s blacklist is this Git rep

I actually have been doing some work with MaraDNS to have the ability to have a pi-hole sized blacklist. The main source of pi-hole’s blacklist is this Git repo: https://github.com/StevenBlack/hosts https://github.com/StevenBlack/hosts That is about 60,000 hosts, so I added MaraDNS support to have up to 500,000 blacklisted names. Since it’s a speed-optimized (not size-optimized) cache, each element takes about a kilobyte of memory, so a blacklist this size takes about 60 megabytes of memory for MaraDNS to store (on a modern Core i7 7600U processor, it only takes about two seconds to load all 60,000 elements in to memory), but it’s very rapid to use. The script to take that blacklist and convert it in to a MaraDNS compatible format is here: https://github.com/samboy/MaraDNS/blob/master/deadwood-github/tools/make.blacklist.sh https://github.com/samboy/MaraDNS/blob/master/deadwood-githu... There are ways to make the memory footprint of the blacklist smaller, but this was a quick and simple way to implement a medium sized blacklist. Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. My current project is to make a proper Docker container for MaraDNS.

CoolGuySteve 6y ago
What is the optimization gained by having 1KB cache slots when the cacheline size on Intel and ARM is typically 64 bytes?
- strenholme 6y ago
  Each cache entry needs a hash bucket so we can look up the entry in O(1), and we need more hash buckets than entries to minimize cache look up time. The hash bucket needs a copy of the element for each hit (to verify we hit the correct hash bucket), and a possible link to the next hash bucket, just in case we got a hash collision (we still need to store that link in memory as a null pointer regardless). [1] The strings are special structures which allow binary data to be stored in them and to protect against buffer overflow protection, so they take up more room than a normal string. Since the cache is a dynamic LRU cache (blacklist entries are not in the circular LRU, of course, but the cache was designed that way) for temporarily storing correct DNS answers (with overhead because, yes, each entry has among other things a 64-bit expire timestamp), each entry is created or removed with multiple malloc() and free() calls, so there’s some page size overhead there. Like I said, there are ways to make a blacklist have a smaller memory footprint, by using a special data structure which trades speed for size, [2] but for a two-day coding project, it made more sense to just add them to the speed optimized LRU cache the code is built around. [1] As an aside, the hash compression algorithm came out before SIP Hash, but, like SIP Hash, has protection against an attacker finding hash bucket collisions. If I were to write the code today, I would use SIP Hash. [2] Here is how I would do it: I would have two blocks of data. One block is an array of offsets (pointers, but not C memory pointers) to data in the second block, and the second block is a bunch of NULL-terminated strings compactly stored. The array of offsets is a sorted list, where the sort key is the string each element points to. I would then do a binary search every time I wanted to see if an element is blacklisted. Memory overhead is, for 10 million entries with an average length of 15 bytes per string (including the NULL) 30 million bytes for the offsets and 150 million bytes for the strings, so we could store 10 million entries in under 200 megs. Speed is O(log2(N)) instead of O(1) but we save a lot of memory. We would need more memory to sort that list, but we could store this block as a binary file which is made on a host with a lot of memory, but read on our Raspberry Pi or old Netbook. Again, doing this is left as an exercise for the reader, and I’m sure there’s a lot of public domain or otherwise open licensed libraries which have already solved this problem. If I were to go down that path; I would probably use sqlite, but am a bit reluctant to add sqlite to a tiny program which can compile to be under 70k in size.
  - kccqzy 6y ago
    Instead of building hash tables with buckets (and a linked list in case of hash collision), why not use a flat array based hash table and open addressing?
    - strenholme 6y ago
      I actually tried that with MaraDNS in the pre-1.0 days (in case of collision, go forward in hash array N elements until there is no collision). The problem is that it works really great for static data, but doesn’t work for dynamic data as cleanly as using a linked list to handle collisions. The one thing I would do differently is that Deadwood (MaraDNS’s recursive/blacklist DNS server) adds individual elements with malloc() and removes them with free(); doing things that way is OK for relatively small data sets on a desktop class computer, but some embedded systems don’t handle the stress of a lot of malloc() and free()s very well, and doing it that way uses a significant amount of memory per element.
      - GekkePrutser 6y ago
        But the data is fairly static isn't it? You're not constantly updating the blacklists?
        strenholme 6y ago
        We’re using the same hash to both store blacklist data and cache dynamic DNS data. Yes, we could put the blacklist in a separate data structure, but doing it this way made adding blacklist support a one-day instead of a two-month (shorter, if I use something like sqlite) project.
  - gumby 6y ago
    Since you have the complete set of blacklist entries each time distribute it, you could compute a perfect hash (zero collisions, no buckets needed) each time you updated the list.
    - 6y ago
x3blah 6y ago
Will you test the efficiency of the block list. For example, given a block list of 60,000 how many hosts on the list did your computer actually try to access. Have you ever read through one of those massive blocklists. I use a whitelist rather than a blocklist. Similar to a firewall, I block everything by default. Then carefully choose what I allow. This way I can see exactly what hosts I actually need to access. Makes it easy to see attempts to access ad servers, trackers, phone home, etc.
- strenholme 6y ago
  MaraDNS (OK, Deadwood) can handle white lists too: upstream_servers = {} upstream_servers["."] = "192.168.253.253" # Never answers upstream_servers["good-domain.example.com."] = "9.9.9.9" upstream_servers["whitelist-entry.foo."] = "9.9.9.9" # And so on The downside is that the code currently only supports 20,000 elements added this way.
  - x3blah 6y ago
    I am a djbdns user. I also use nsd and unbound. I do not use "upstream" third party DNS, such as 9.9.9.9. Surprised to hear that anyone still uses MaraDNS. What I am curious about are these massive blocklists. Does anyone actually read through them. Does it make sense to block 60,000 hosts when only, say 100 or even 1000, ever stand a chance of being accessed by a user's computer -- due to the user's particular usage habits.
    - GekkePrutser 6y ago
      Well, why not? 60.000 isn't a huge amount for a modern computer. If they're known to contain ads/trackers you want to block, then why not include them? It might make sense though to do a periodic run through them to see if they still exist.
      - deleted 6y ago
        [deleted]
    - 6y ago
ignoramous 6y ago
> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is interested (and this may not be what OP had in mind): In trading memory gains with computation, this is how I squeezed ~4M entries in less than 30 MiB: 1. Compress (reversed) individual entries using a dictionary or entropy encoder. I experimented with Shoco [0], Femto [1], and a modified LZ78 [2]. 2. Create a bloom filter for membership checks, [3] or any probabilistic structure for that matter, like the xor-filters [4]. This prevents expensive but unnecessary lookups. 3. Insert the compressed (reversed: google.com -> com.google) entries into a radix-tree [5]. You could use a directed-acyclic graph (DAG), if you don't need to store key-value pairs. 4. Compact [6][7] the radix-tree [8] (compacting a DAG might be super complicated). 5. On every search: 5a. Compress (reversed) incoming query (i.e. domain-name). 5b. Check the bloom filter. 5c. Traverse the radix-tree, if necessary. 5d. Cache an eligible entry in a LFU [9] or possibly, using any other suitable algorithm inspired from Linux's page replacement implementations [10]. 6. Strive for zero-allocation and zero-gc. --- [0] https://news.ycombinator.com/item?id=10060018 https://news.ycombinator.com/item?id=10060018 [1] https://github.com/gtoubassi/femtozip/wiki/How-femtozip-works https://github.com/gtoubassi/femtozip/wiki/How-femtozip-work... [2] https://en.wikipedia.org/wiki/LZ78 https://en.wikipedia.org/wiki/LZ78 [3] https://news.ycombinator.com/item?id=12231623 https://news.ycombinator.com/item?id=12231623 [4] https://news.ycombinator.com/item?id=21840821 https://news.ycombinator.com/item?id=21840821 [5] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin... [6] https://news.ycombinator.com/item?id=22544718 https://news.ycombinator.com/item?id=22544718 [7] https://www.youtube-nocookie.com/embed/3Y2weLDiUWw https://www.youtube-nocookie.com/embed/3Y2weLDiUWw [8] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619 [9] https://github.com/ronomon/hash-table/blob/master/README.md https://github.com/ronomon/hash-table/blob/master/README.md [10] https://en.wikipedia.org/wiki/Page_replacement_algorithm https://en.wikipedia.org/wiki/Page_replacement_algorithm

CoolGuySteve 6y ago

What is the optimization gained by having 1KB cache slots when the cacheline size on Intel and ARM is typically 64 bytes?

strenholme 6y ago
Each cache entry needs a hash bucket so we can look up the entry in O(1), and we need more hash buckets than entries to minimize cache look up time. The hash bucket needs a copy of the element for each hit (to verify we hit the correct hash bucket), and a possible link to the next hash bucket, just in case we got a hash collision (we still need to store that link in memory as a null pointer regardless). [1] The strings are special structures which allow binary data to be stored in them and to protect against buffer overflow protection, so they take up more room than a normal string. Since the cache is a dynamic LRU cache (blacklist entries are not in the circular LRU, of course, but the cache was designed that way) for temporarily storing correct DNS answers (with overhead because, yes, each entry has among other things a 64-bit expire timestamp), each entry is created or removed with multiple malloc() and free() calls, so there’s some page size overhead there. Like I said, there are ways to make a blacklist have a smaller memory footprint, by using a special data structure which trades speed for size, [2] but for a two-day coding project, it made more sense to just add them to the speed optimized LRU cache the code is built around. [1] As an aside, the hash compression algorithm came out before SIP Hash, but, like SIP Hash, has protection against an attacker finding hash bucket collisions. If I were to write the code today, I would use SIP Hash. [2] Here is how I would do it: I would have two blocks of data. One block is an array of offsets (pointers, but not C memory pointers) to data in the second block, and the second block is a bunch of NULL-terminated strings compactly stored. The array of offsets is a sorted list, where the sort key is the string each element points to. I would then do a binary search every time I wanted to see if an element is blacklisted. Memory overhead is, for 10 million entries with an average length of 15 bytes per string (including the NULL) 30 million bytes for the offsets and 150 million bytes for the strings, so we could store 10 million entries in under 200 megs. Speed is O(log2(N)) instead of O(1) but we save a lot of memory. We would need more memory to sort that list, but we could store this block as a binary file which is made on a host with a lot of memory, but read on our Raspberry Pi or old Netbook. Again, doing this is left as an exercise for the reader, and I’m sure there’s a lot of public domain or otherwise open licensed libraries which have already solved this problem. If I were to go down that path; I would probably use sqlite, but am a bit reluctant to add sqlite to a tiny program which can compile to be under 70k in size.
- kccqzy 6y ago
  Instead of building hash tables with buckets (and a linked list in case of hash collision), why not use a flat array based hash table and open addressing?
  - strenholme 6y ago
    I actually tried that with MaraDNS in the pre-1.0 days (in case of collision, go forward in hash array N elements until there is no collision). The problem is that it works really great for static data, but doesn’t work for dynamic data as cleanly as using a linked list to handle collisions. The one thing I would do differently is that Deadwood (MaraDNS’s recursive/blacklist DNS server) adds individual elements with malloc() and removes them with free(); doing things that way is OK for relatively small data sets on a desktop class computer, but some embedded systems don’t handle the stress of a lot of malloc() and free()s very well, and doing it that way uses a significant amount of memory per element.
    - GekkePrutser 6y ago
      But the data is fairly static isn't it? You're not constantly updating the blacklists?
      - strenholme 6y ago
        We’re using the same hash to both store blacklist data and cache dynamic DNS data. Yes, we could put the blacklist in a separate data structure, but doing it this way made adding blacklist support a one-day instead of a two-month (shorter, if I use something like sqlite) project.
- gumby 6y ago
  Since you have the complete set of blacklist entries each time distribute it, you could compute a perfect hash (zero collisions, no buckets needed) each time you updated the list.
  - 6y ago

x3blah 6y ago

Will you test the efficiency of the block list. For example, given a block list of 60,000 how many hosts on the list did your computer actually try to access. Have you ever read through one of those massive blocklists. I use a whitelist rather than a blocklist. Similar to a firewall, I block everything by default. Then carefully choose what I allow. This way I can see exactly what hosts I actually need to access. Makes it easy to see attempts to access ad servers, trackers, phone home, etc.

strenholme 6y ago
MaraDNS (OK, Deadwood) can handle white lists too: upstream_servers = {} upstream_servers["."] = "192.168.253.253" # Never answers upstream_servers["good-domain.example.com."] = "9.9.9.9" upstream_servers["whitelist-entry.foo."] = "9.9.9.9" # And so on The downside is that the code currently only supports 20,000 elements added this way.
- x3blah 6y ago
  I am a djbdns user. I also use nsd and unbound. I do not use "upstream" third party DNS, such as 9.9.9.9. Surprised to hear that anyone still uses MaraDNS. What I am curious about are these massive blocklists. Does anyone actually read through them. Does it make sense to block 60,000 hosts when only, say 100 or even 1000, ever stand a chance of being accessed by a user's computer -- due to the user's particular usage habits.
  - GekkePrutser 6y ago
    Well, why not? 60.000 isn't a huge amount for a modern computer. If they're known to contain ads/trackers you want to block, then why not include them? It might make sense though to do a periodic run through them to see if they still exist.
    - deleted 6y ago
      [deleted]
  - 6y ago

ignoramous 6y ago

> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is interested (and this may not be what OP had in mind): In trading memory gains with computation, this is how I squeezed ~4M entries in less than 30 MiB: 1. Compress (reversed) individual entries using a dictionary or entropy encoder. I experimented with Shoco [0], Femto [1], and a modified LZ78 [2]. 2. Create a bloom filter for membership checks, [3] or any probabilistic structure for that matter, like the xor-filters [4]. This prevents expensive but unnecessary lookups. 3. Insert the compressed (reversed: google.com -> com.google) entries into a radix-tree [5]. You could use a directed-acyclic graph (DAG), if you don't need to store key-value pairs. 4. Compact [6][7] the radix-tree [8] (compacting a DAG might be super complicated). 5. On every search: 5a. Compress (reversed) incoming query (i.e. domain-name). 5b. Check the bloom filter. 5c. Traverse the radix-tree, if necessary. 5d. Cache an eligible entry in a LFU [9] or possibly, using any other suitable algorithm inspired from Linux's page replacement implementations [10]. 6. Strive for zero-allocation and zero-gc. --- [0] https://news.ycombinator.com/item?id=10060018 https://news.ycombinator.com/item?id=10060018 [1] https://github.com/gtoubassi/femtozip/wiki/How-femtozip-works https://github.com/gtoubassi/femtozip/wiki/How-femtozip-work... [2] https://en.wikipedia.org/wiki/LZ78 https://en.wikipedia.org/wiki/LZ78 [3] https://news.ycombinator.com/item?id=12231623 https://news.ycombinator.com/item?id=12231623 [4] https://news.ycombinator.com/item?id=21840821 https://news.ycombinator.com/item?id=21840821 [5] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin... [6] https://news.ycombinator.com/item?id=22544718 https://news.ycombinator.com/item?id=22544718 [7] https://www.youtube-nocookie.com/embed/3Y2weLDiUWw https://www.youtube-nocookie.com/embed/3Y2weLDiUWw [8] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619 [9] https://github.com/ronomon/hash-table/blob/master/README.md https://github.com/ronomon/hash-table/blob/master/README.md [10] https://en.wikipedia.org/wiki/Page_replacement_algorithm https://en.wikipedia.org/wiki/Page_replacement_algorithm