MaraDNS 1.3.10 and 1.3.07.07 released

Today I have released two versions of MaraDNS: MaraDNS 1.3.07.07, and MaraDNS 1.3.10. Full details on what has been updated can be seen in the changelog. Downloads are here (scroll down).

- Sam

Adding support for reading and writing the cache to disk

This week, I have been working on adding the ability to write the Deadwood-2 cache to a file, and read the Deadwood-2 cache from a file. Support for writing the file is complete. The file is very simple, and has the following format: For each element in the cache, write the key string to the file, followed by the value string object, followed by a 64-bit timestamp of when this record expires. Put less important (more likely to be deleted) elements at the beginning of the file and more commonly accessed cache elements at the end of the file (The reason for this is, when adding elements to the cache, more recently added elements are considered more important).

The string object has a very simple format in the file: A 32-bit big-endian length value, which must be a positive signed number (negative signed numbers mean the string has a length of 0), followed by the binary string. The timestamp is a representation of the 64-bit timestamp used by Deadwood, whose epoch is when the episode "Gambit" of the Blake's 7 television programme was first broadcast. Each second has 256 "ticks".

I have also fixed a bug in the hash used by the cache (it took me a couple of hours of fiddling around with Deadwood to find and get rid of it).

---

I'm also playing around with Doom Builder, an open-source Windows-only (Why doesn't Linux have a decent Pascal compiler?) program for editing maps. It's very easy to learn and use; I'm using it to make changes to a 9-map megawad generated by Oblige (for Heretic) in to one suitable for single player, deathmatch, and coop play.

I'm having a lot of fun with it; I just wish I had some buddies down here in Mexico to deathmatch with.

- Sam

Deadwood-2 hash core finished; ObHack update

I have finished the core hash that will be the Deadwood-2 cache this weekend. This is a data structure that is optimized for making a DNS cache. It's like the cache MaraDNS currently uses, but a much simpler, clener codebase with some features MaraDNS' current cache does not have. This code can now be expanded to make a caching forwarding DNS server.

The one feature I want to add to the core hash first, however, is the ability to write the cache to a file, and read the cache from a file.

The updated snapshot can be downloaded here

---

I also have an update to ObHack, fixing some critical bugs, and adding one "feature":

• Critical fix: Door statues are now less likely to make it impossible to finish a level w/o the "noclip" (OK, "kitty") cheat code.
• Critical fix: Being unable to find a door fab no longer causes ObHack to crash and burn (we just try with a different level)
• Critical fix: Now there's a high recursion depth limit when retrying to plan a level; this way, the program does not freeze in an infinite loop if it's impossible to find a plan that meets the requirements.
• Critical fix: An assert when making small deathmatch maps sometimes failed. Fixed; assert removed.
• Feature added: Heretic "full game" megawads now make E6M1-3, with E6M3 not having an exit (neither in single player nor deathmatch)

ObHack can be downloaded here

MaraDNS, ObHack, and font updates

I have updates for not one, not two, but three different projects of mine today.

---

My MaraDNS update has one change to the mainline code: l.root-servers.net IP has been updated. I am also working on the hash-generation code again for the "Deadwood-2" code, which will become a simple non-recursive caching DNS server. This is available here.

---

ObHack, my hacks to the excellent OBLIGE Doom random map generator, has a very minor update: Single player maps now have deathmatch starts. I added this feature since the small levels are small enough to be playable as 1-on-1 deathmatch maps with Heretic, and as 3-way or 4-way Doom/Doom2 deathmatch maps (all of those Doom fabs give players more little hidey holes). Also, Heretic (but only Heretic, alas) single player maps now have a couple of coop starts. In addition, I now have a Linux tarball, in addition to the Windows zipfile and a source tarball.

ObHack 002a (I'm not giving this a new number since the maps are identical to 002 maps, with only deathmatch and coop starts added) is available as a Windows zipfile here, as a Linux binary tarball here, and as a source code tarball here. An example megawad for Heretic is available here

---

I have made a minor update to my "Sandals" font, an attempt to make a readable screen font. This font can be downloaded here. I also have a version of this font that includes the bitmap version of a famous font made by a major software company here (I'm using an American server owned by an American since, while American law clearly states you can't copyright the bitmap version of a font, European laws are not clear on this matter).

- Sam

ObHack update

I have just uploaded a minor update to ObHack, my hack of Oblige. This is a bugfix only release; the bugs fixed are:

• There was a bug that would sometimes stop megawads of small episodes being created. Fixed.
• It was possible to have only one exit (either the secret exit or an exit going to the non-secret level) on a small map. Fixed; any map that should has a secret exit will now always have both a normal and secret exit
• In Heretic, at "Smite-Meister" (Heretic's name for "Ultra-Violence") diffculty, it is sometimes nay to impossible to get through the legion of golems and gargoyles to get at the cross bow. Workaround: There is now, at this difficulty level, always the gauntlets and the Chaos device at the beginning of the level; this makes it easier for the player to rush to the crossbow without unbalancing things too much
• Random numbers generated tweaked to make completely different maps than yesterday's ObHack release

The Windows binary is here and the source code here

My hacks to Oblige (a new Doom random map generator)

For a while now, I have been working on some FreeDoom-specific hacks to SLIGE called SLUMP. Indeed, I released an update to this program in late October.

Just this Monday, I disocovered a new (for 2007) Doom random map generator called OBLIGE (alternate link). I feel this map generator is a good deal more advanced than SLIGE and SLUMP. Unlike SLIGE/SLUMP, it supports:

• Real outdoor areas
• Balconies
• More detailed rooms
• No "null" quests: If you go somewhere and fight monsters, you will get some prize for your bother (such as a good weapon or a power-up)
• Heretic and Hexen support, in addition to real FreeDoom and Plutonia/Evilution support
• Real deathmatch and coop support
• A GUI interface

SLIGE only has a couple of features not supported by OBLIGE, such as variable-sized rooms, boss arenas (which I broke in SLUMP), and teleporters.

Unlike SLIGE, which codes everything in C, OBLIGE uses a scripting language called Lua for the map building core. The code is larger than SLIGE--my Windows zipfile of SLUMP, complete with node-builder is only 100k in size; OBLIGE is about six times larger. It's also slower; I can make a 32-level small megawad in SLUMP/SLIGE (complete with the nodes being built with BSP) in about a second; a megawad with the same size takes between 30 seconds and a minute to make in OBLIGE.

The nice thing about the Lua core is that it is far easier to customize the map generator. Indeed, I have done exactly that, and have made the following updates to OBLIGE:

• Smaller levels, especially when making deathmatch maps and when selecting a "small" level size.
• Allowing smaller levels caused some bugs to pop up, which I have addressed.
• It is now possible to finish an episode in Doom 1 or Heretic; E#M8 is now a normal level with a normal exit (no boss arenas though)
• Heretic fixes: No more doors that you can't open; you can now go to the secret level
• Build fix: If a level is unable to place a staircase, instead of crashing and burning, the generator will discard the level and try again.

I call my hacked version of OBLIGE "ObHack" (an expression used in a now-dead once great Usenet newsgroup called alt.hackers); the Windows binary can be downloaded here; the source code (nothing that compiled has been changed, however; only the Lua scripts) is here.

---

Some MaraDNS support issues: An automatically generated Debian bug saying it's hard to automate getting a new version of MaraDNS; one of the root servers has changed. Now that I've had fun making my ObHack fork of OBLIGE, I will work on these this afternoon.

MaraDNS snapshot update: Another bug fixed

I didn't have any time to work on Deadwood this weekend because:

1. Jan Hrdonka reported another bug which I had to find and fix (details below)
2. I was working on a new version of my tiny live CD distribution of Linux (Firefox had to be updated, etc.)
3. I spent some time with my girlfriend this weekend

The bug fixed in MaraDNS is that the CSV2 parser could not handle "blank" zone files--zone files with only SOA and NS records. I have fixed this bug in MaraDNS 1.3, complete with adding a regression to make sure the bug stays fixed, and have added a FAQ entry describing the bug and a workaround.

The reason for the bug is this: The CSV2 parser doesn't actually add the SOA record to memory until after all of the NS records, since the SOA record needs the NS records. The code adds the SOA records before adding the first non-NS entry. I forgot to add the SOA record after reading all of the zone in the case of having a zone with no records except SOA and NS records. I have added code to do this.

Since this is not a critical fix (there's a workaround for 1.2 users), this bug will not be fixed in MaraDNS 1.2

Deadwood and 64-bit systems; a highly scalable load balancer

People looking at the source code of Deadwood will observe some of the code is 32-bit specific; There are a lot of int32_t and uint32_t variables and functions in the code. The reason for this is to make porting to 64-bit easier; while not as efficient as using 64-bit ints everywhere, it's pretty much guaranteed that the code will run the same on a 32-bit and 64-bit CPU/operating system (my development machine has a 64-bit CPU, but is currently using a 32-bit operating system). However, one thing I have been thinking about is how to scale the code up to use 64-bit ints.

Most of the code can be pretty easily scaled up; use a 64-bit int instead of a 32-bit int for various constants. The random number generator, Radio Gatun, has both a 64-bit and 32-bit version.

The one bit of code that can't easily scale up quickly is the code that generates the 31-bit primes. I use a simple trial division that doesn't scale up. This code will have to be rewritten to use something fancier; Chris Caldwell has a lot of really good pages about how to quickly find a big prime. Using this method, along with this should be able to find a number that is almost certainly a 63-bit (18-digit) prime without being too much slower than finding a 31-bit prime.

---

It is possible to make a DNS load balancer that can handle far more than 3,500 queries a second. The bottleneck with Deadwood-1 is how I use TCP/IP (or, should I say, UDP/IP). The trick is to have both the load balancer and the upstream DNS servers have public and private IPs. The load balancer would get its query on a public IP, and send it over a private IP to the upstream DNS server. There will be a firewall in front of the load balancer that rejects all packets with private IPs coming in from outside.

For each upstream load balancer, there can be about 64000 connections at the same time. Given 10 upstream load balancers, thats 640000 connections a second. That's, with a seven second timeout, over 90000 DNS queries a second.

However, I'm not going to develop this code. Instead, I'm going to work on the caching DNS server. My plate is already full.

- Sam

Deadwood-1 updated; MaraDNS snapshot update

I have updated Deadwood-1 today to handle a higher load. This is done by having the port range used for binding to a secure local port be user settable, and by having the code that binds to a local port retry up to 10 times should it be unable to bind to a port the first time. I estimate that the Deadwood-1 load balancer can handle up to 24,500 simultaneous pending connections, or 3,500 connections a second at the default timeout of seven seconds (more if the upstream DNS server answers more quickly then seven seconds).

These changes are documented in a HANDLING.HIGH.LOAD document.

I have also made some revisions to the design of the hash in Deadwood-2, and have started writing code to store and retrieve entries from an array based on the hash value of dw_str objects.

- Sam

Deadwood-1 bugfix

I have just uploaded a new snapshot of MaraDNS today. In this snapshot, I have fleshed out the design of the hash for Deadwood-2 a little more, and have fixed a minor bug in Deadwood-1: When Deadwood-1 was overloaded, the "SERVER FAIL" packets did not have the correct length; I have fixed this and now the packets have the correct length.

I have also made a package with just Deadwood-1 called "Deadwood-1.00"; this package will be updated when (and if) I find and correct other bugs in Deadwood-1.

Both can be downloaded here

- Sam

Deadwood-2 started ; Qmail may soon become public domain

Today I am releasing the groundbreaking release of Deadwood-2. Deadwood-2 will be a simple DNS cache that caches requests made to a fully recursive DNS server. Last night, I wrote the code to implement the hash compression algorithm, making what I feel to be a reasonable balance between security and speed.

The has compression algorithm is a simple XOR with the data to hash, followed by a 32-bit multiply and a circular rotate (since mod 2^32 multiplies have problems with repeating patterns in the lower bits); the last data we XOR against is the length of the message. To make things reasonably secure, I am making the 32-bit number one multiplies by be a relatively secret 31-bit prime number; I have written a small program that finds a random 31-bit prime number, and makes a header file that determines Deadwood's default multiplication constant for making a hash out of a string. The script that creates the MaraDNS tarball automatically runs this program to change the random number.

In addition, the code will allow the user to reset this number to some other number, and the documentation will encourage the user to do so (telling them how to use RandomPrime to see a random 31-bit prime number).

The file can be downloaded here

---

I have some very good news: It looks like DJB is going to make Qmail public domain. I hope DJB soon does the same thing for DjbDNS; my main issue with DjbDNS, besides the hyperbolic claims like "DjbDNS has no security holes" (it does), is its license. I will retract my rant against DjbDNS when and if the DjbDNS code becomes public domain.

Thanks a lot for the birthday present, DJB! :)

- Sam

MaraDNS snapshot update

I just uploaded a snapshot with three minor errors in Deadwood-1 pointed out by Jean-Jacques Sarton corrected:

• I did not close the socket for binding to a local IP if bind() or accept() failed
• I did not close the dwood1rc file handle after parsing the dwood1rc file
• I did not close the random seed file after getting entropy from this file

It can be downloaded here

Note that none of these problems caused a leak; in all three cases, it was simply a case of a resource (a file or socket) being opened once and then never closed.

I will update the coding style to make sure these kinds of problems don't pop up again.

- Sam

Deadwood-1 is now finsihed

In today's snapshot of MaraDNS, all of the features that deadwood-1 is going to have are already implemented. Deadwood-1 is now frozen, and it is time to look at the roadmap for Deadwood again:

Deadwood-1: An IPv6-capable cross-platform TCP and UDP DNS load balancer.

The target for this was the end of October, and it was finished around the beginning of November.

Deadwood-2: A DNS forwarding cache. Target date: Before the end of 2007.

Deadwood-3: A full DNS recursive resolver. Target date: Mid-2008

And, in more detail, my plans for Deadwood-2:

Deadwood-2 will be a forwarding cache. This means that deadwood-2 will look for an answer in the cache, and, if there isn't an answer in the cache, it will contact a recursive DNS server and cache the reply it gets. The cache will have the following features:

• A custodian that deletes an unused cache entry if the cache is full. (MaraDNS' current cache has this)
• The ability to get an expired record from the cache if it is not possible to contact any upstream recursive servers.
• The ability to write the cache to disk, and read the cache from disk.

Deadwood now works in Windows

I spent about four hours this morning making a one-line fix in the Deadwood code so it would run in Windows. First, I installed and configured BIND in Windows; a non-trivial task since the BIND developers seem to be on a crusade to make BIND as difficult to configure and run as possible. Once I did that, I found out, the hard way, that services on localhost can only bind to the IP 127.0.0.1, and that binding to other localhost addresses doesn't work.

At this point, I had a working testing setup. I finally was able to debug the code, and found out that the reason TCP wasn't working in Windows is because you have to send() instead of write() on a TCP socket.

Once I fixed the code, I updated the documentation and coding style document to document the macros I use to make the same socket code work both in Windows and *NIX, so other people writing socket code will also write cross-platform socket code.

Anyway, the updated Deadwood source code that works in Windows can be downloaded here.

- Sam