I've been updating Deadwood

I've been updating Deadwood; right now all of the DNS compression code is written and now I just have to go through and debug the code until it works. This should take a couple of days. Once Deadwood is able to compress DNS packets, I will change the code to store packets internally as uncompressed packets, then release Deadwood 2.4.04 with a different, incompatible format for the DNS cache written to a file (since DNS packets will be uncompressed internally).

After that, Deadwood 2.4.05 with RR rotation and TTL aging.

People can look at Deadwood here.

Back to Firefox 3.0

I just updated the version of Firefox to Firefox 3.5 in one of my virtual machines.

It sucks.

The problem is this: Every time I load a page in a background tab, anytime Firefox needs to process Javascript in that page or whatever, Firefox freezes in the foreground tab; anything I type in (such as replying to an email) isn't typed in and I can't scroll the page or do anything else while Firefox processes the background tab.

Firefox 3.0 doesn't have this problem, so I'm going to use Firefox 3.0 until Firefox stops making security updates for Firefox 3.0; Firefox 3.0.11 can still be downloaded here ("en-US" is US English and "es-AR" is Spanish) and will be updated with security updates for about six more months. After that, well, hopefully the Mozilla foundation will solve their Firefox 3.5 issues or I will switch to another browser.

Firefox's big advantage is that it has a "always use the Verdana font" option, which no other modern browser has; I was able to hack this in to Opera in my Linux virtual machine by having the only available True Type font be Verdana.

Why I will not implement DNS curve

I will not implement DNS curve.

Sorry, guys. It's just, over the years, I have had too much bad blood with DJB and with DJB advocates. Back in 2001, I supported DJB on his "lets flame all of the BIND developers" crusade.

Despite this, he had this childish response to my 2002 Bugtraq announcement of MaraDNS. In addition, I have had a number of unpleasant experiences with DjbDNS zealots over the years.

I understand that DJB has partially addressed the issues I brought up back in 2007 by making DjbDNS public domain instead of its old "useless unless you like patching like crazy" license it used to have.

I find DJB advocates loud-mouthed and unpleasant. DJB's behavior in the early 2000s with BIND developers on mailing lists like Namedroppers was unacceptable, and the fact is that DJB has never apologized for his behavior there.

If DJB wants to have a DNS standard that other DNS implementors will want to implement, he needs to have more respect for the DNS standards process and for other people who have implemented DNS, including the BIND developers.

Another day, another Deadwood snapshot

I've added a new structure (object) type called dns_string that will make it possible to compress uncompressed DNS packets. In addition, this makes it possible to have RR rotation and TTL aging in Deadwood.

The snapshot is here

GbDns : A recursive caching DNS server for Windows

Ok, I just found another DNS implemention out there: GbDns : A recursive caching DNS server for Windows. It looks like it's written in C# and uses the .net framework; I will look at it more later on.

Some blogs on DNSSEC

I found a couple of blogs that mention that DNSSEC is a nightmare to implement.

MaraDNS 2.0 (Deadwood 3.0) will not have DNSSEC. I may make a Deadwood 4.0 with DNSSEC support, but that's a wishlist item right now.

Another day, another Deadwood snapshot

This morning, while walking to work, I realized that a bailiwick check, while useful for making sure DNS data is in bailiwick, isn't useful for compressing DNS data.

The best way to compress DNS data is to make a list of every place a compression pointer might point to, and comparing every part of a label we will add to the compressed string to every one of those parts.

That in mind, I have added a function, dwc_push_offsets(), that adds the offsets of all parts a compression pointer can point to in a DNS name to a stack of 16-bit values.

I've also made functions more flexible, allowing dwc_in_bailiwick() to be used in contexts where it's not compressing a DNS packet more easily (the "q" string can now be NULL without issue).

It is at the usual place.

Deadwood snapshot update

I have now setup a test for the functions that will make up the DNS compression code and fixed a couple of bugs. The new snapshot can be downloaded here.

New deadwood snapshot

OK, I'm going to test the compression code I have in place before finishing up the code. The snapshot is, as always, at maradns.org/deadwood/snap.

I've installed Dillo 2.0

I have compiled and installed Dillo 2.0 in my Linux virtual machine. I have installed this because Netscape 4 is completely dead and it looks to be a reasonable browser for people living in their parents' basement still using a 486 to go online. This, along with IE 6 (20% market share and I will continue to support it until there is confirmed under 2% market share, probably around 2012 or so), are the "lowest common denominator" browsers I test my websites against.

All my websites are attractive in IE6 and readable in Dillo.

If your computer is a Pentium II or better with 64 megs of ram, use Opera 9, which supports modern CSS, passes the Acid 2 test, and is the most lightweight browser usable on today's internet.

Deadwood snapshot update

I'm slowly but surely working on the new DNS compression code, which one can see at maradns.org/deadwood/snap.

Home.netscape.com crashes Netscape 4.79

Netscape 4.79, which was the last release of the closed-sourced pre-Mozilla Netscape browser, had its default home page set to home.netscape.com. Curious, I went over to evolt.org and downloaded and installed Netscape 4.79 in Windows XP to see how this page looks in this ancient browser. Since this was the home page for this ancient browser, I figured some effort would be made to make this page render in that browser, perhaps with a note, only visible in NS4, to update one's browser.

Nope.

The web page redirects to an AOL web page that has some HTML or Javascript that crashes the Netscape browser.

As an aside, both maradns.org and samiam.org (my personal webpage) render fine (albeit without CSS) in Netscape 4.79, but this blog doesn't render. While this blog doesn't crash NS 4, the text here is not visible. The reason is because this blog is a combination of Google's and my own design, and I no longer deal with Netscape 4 compatibility.

My web sites look OK in Netscape because Netscape compatibility was still a (very minor) issue back in 2004 and 2005 when I designed these sites.

If you have some ancient computer that can't run IE6 or Firefox, use Dillo which renders my sites fine, albeit without CSS, last time I tested against it. Or, better yet, get out of your mother's basement and get a new computer; they're only $250 at Dell.

Yeah, Netscape has a lot of memories for me. Back in the 1990s I rooted for Netscape because Internet Explorer was not available for Linux; since Linux never did (and never will) have a significant desktop usage share, this didn't save Netscape as the old Unix workstations died out and were replaced by Windows NT desktops throughout the 1990s. Of course, these days with Opera available for Linux, and Firefox having over 20% browser usage share (Linux kernel developers can learn a lot from Firefox's success on the desktop), this is all a non-issue.

Deadwood snapshot update

Since I have a real AFK (away from keyboard) life this week, Deadwood progress will be slow until I become an über-geek again. In the meantime, I have started work on the DNS compression code. I'm doing a bottom-up approach (with the decomression code, I started with then bottom-up approach, switched to a top-down approach, and finished up the code by meeting in the middle).

I'll probably have DNS compression finished up next week sometime. After that, it's time to work on RR rotation and TTL aging.

There will be no Deadwood updates until early next week

Just letting everyone know that real life has set in and I won't be working on Deadwood again until early next week. Have a wonderful weekend everyone!

Deadwood snapshot update: Code cleanup

One thing I really like about Deadwood being an open-source project is that there is no deadline nor any manager breathing down my neck telling me Deadwood needs to be released yesterday.

So, today, my Deadwood development has consisted of adding no new features; the only changes I have made today involve code cleanup. I have gone through DwCompress.c and made sure no function was no longer than 52 lines long; this involved splitting parts of the code for dwc_decompress() in to two different sub-functions. I also took the function dw_dnsname_convert() in DwStr.c and split off part of it in to a sub-function to make this function be under 52 lines in length.

The snapshot can be seen at the usual place.

New Deadwood snapshot

In today's snapshot, dwc_decompress() now returns RRs in the format I want to return them in (offsets for the beginning of RRs to make RR rotation easier; offsets of the beginning of TYPE in RRs to make TTL aging easier; followed by AN/NS/AR counts and one-byte type). I'm also starting work on getting all functions to be 52 lines or less again to keep the code readable.

Deadwood snapshot update

Deadwood snapshot update: DNS Decompression now works but still needs touch-up.

If I could change one thing about C...

If I could change one thing about C, it would be to add the ability to have functions return lists. In other word, I would have added the ability to do this to C:

(int, int) function(int a) {
    if(a < 0) {
        return (1,a);
    } else {
        return (-1,-a);
    } 
}
main() {
    int a, b;
    (a,b) = function(3); 
    printf("%d %d\n",a,b);
}

This would have been easy to add; it's a simple matter of having more variables on the stack. There are three ways one can do this with C, all of which I find rather ugly:

int function(int a, int *b) {
    if(a < 0) {
        *b = a;
        return 1;
    } else {
        *b = -a;
        return -1;
    } 
}
main() {
    int a, b;
    a = function(3, &b);
    printf("%d %d\n",a,b);
}

Or

typedef struct {
    int a;
    int b; } tuplet;

tuplet function(a) {
    tuplet c;
    if(a < 0) {
        c.a = 1;
        c.b = a;
        return c;
    } else {
        c.a = -1;
        c.b = -a;
        return c;
    } 
}
main() {
    int a, b;
    tuplet c;
    c = function(3);
    a = c.a;
    b = c.b; 
    printf("%d %d\n",a,b);
}

Or

#include <stdint.h>
uint32_t function(int i) {
    int16_t a,b;
    if(a < 0) {
        a = 1;
        b = i;
    } else {
        a = -1;
        b = -i;
    }
    return (a << 16) | b; 
}

main() {
    int16_t a, b;
    uint32_t c;
    c = function(3); 
    a = c >> 16;
    b = c & 0xffff;
    printf("%d %d\n",a,b);
}

Oh well, there's a reason why Deadwood and MaraDNS 2.0 will probably be my last ever non-OOP C project.

Deadwood progress

I've made a lot of progress with the Deadwood decompression code today; see the snapshots or the changelog for details.

One issue I'm having is that a function in DwCompress.c is exceeding the 52-line limit for functions; I will resolve this once DNS decompression is working. Another place where a function exceeds the 52-line limit is in DwStr.c, with the function dw_dnsname_convert() exceeds 52 lines.

In all of the cases, it's an issue where the complexity of DNS makes it so the functions have been spilling over.

I will work on splitting out parts of these functions in to sub-functions once DwCompress.c is doing basic DNS packet decompression.

Deadwood 2.3.04 released: Documentation updated

I have just released Deadwood 2.3.04. This is the stable branch of Deadwood; the only changes to the code are documentation updates and bug fixes. The code is nearly identical to Deadwood's 2.3.03 code, but the documentation has been updated:

• "ifconfig" replaced by "ipconfig" in Windows version of dwood2rc.txt
• I tested and verified Deadwood 2.3 works in Windows 7 last night, so the docs have been updated to mention Windows 7.
• The random hash compression prime has been updated
• Full testing has been done in both 32-bit and 64-bit CentOS 5

It can be downloaded at maradns.org/deadwood

Deadwood snapshot update

OK, I've started work on the DNS packet decompression code. I worked on this code for about an hour today, and have a couple of functions that do certain core operations the full decompressor will eventually do.

It can be seen at maradns.org/deadwood/snap

More on DNS compression

A DNS record looks like this in binary, as per RFC 1035 section 3.2.1:

1. The "name"; this is a variable-length domain label (and is often times compressed)
2. Type, a 16-bit big endian value, which is whether it is a "A" record, a "NS" record, a "MX" record or whatever
3. Class, a 16-bit big-endian value which is no longer used and must be 1 on the modern internet
4. TTL, how long we want to remember this record, which is a 32-bit big-endian number
5. rdlength, which tells us how long the actual DNS record is
6. The actual DNS record

All of the fields are fixed length, except for the annoying variable-length "name" field. So, for each DNS record, we will want, in the decompressed DNS string, two 16-bit big-endian unsigned numbers:

1. How far from the beginning of the string the name part of the given record is
2. How from from the beginning of the string the "type" part of the given record is

Because of how I wrote the string library, these 16-bit values should be after the actual record, just like we put the number of AN, NS, and AR records at the end of the string storing the DNS packet.

OK, design is done. Time to start coding again.

Some more on Deadwood and DNS compression

The way I have designed the "dictionary" (string-index array) in Deadwood is one where we only allow one datatype for the index: A binary string, and one datatype for the value: A binary string.

This is mind, the only data structure I can use for the decompressed DNS packet is a binary string.

So, the real question is: What kind of things do we want to do with a deep packet inspection of the DNS packet. Well, there's:

• TTL aging
• RR rotation
• Converting a NS referral packet in to one where we say "The NS servers for names ending in whatever consist of the following IPs, the following IPv6 IPs, and the following names which we still need to look up"
• Converting an incomplete CNAME referral packet in to one where we say "This is a dangling CNAME answer that points to this name"
• If the A record points to a given IP, we may want to make this a "not there" packet (working around ISPs with NXDOMAIN redirects)
• If we get a "not found", we may want to make this an A or AAAA answer (so we can be an ISP with a NXDOMAIN redirect)
• Finding the TTL of the packet (already done)

I should probably talk about TTL aging a little more. To keep things simple, if the user wishes TTL aging for their DNS records, we have a single 8-byte (64-bit) expire timestamp in the record, and convert all TTLs in the record to (expire time - current time). Actually, we already keep track of when records expire, so TTL aging is just a matter of converting the TTLs to (expire time - current time).

OK, so the next thought for the next blog entry: What kind of metadeta do we put in the DNS record as we're decompressing it?

The next step: DNS decompression

The next step for Deadwood is to implement DNS compression.

In order to implement DNS compression, it is necessary to perform a "deep packet inspection" of the DNS packets. So far, I have been able to keep Deadwood's code as simple as possible by treating DNS packets as a mostly "black box". We only parse parts of the DNS header, the DNS question, and the TTL of the answer from the DNS record.

This keeps the code simple and it's one of the reasons we have have, in under 32k, a complete DNS-over-UDP non-recursive cache. The only TTL we care about in the answer is the TTL of the first answer we get. In order to resolve what I called the "Google Problem" (DNS packets where the first CNAME record has a high TTL and the actual A records the CNAME points to have a low TTL), I have code that go through the answer section of a DNS packet, looking at the TTL of CNAME answers until we get a non-CNAME answer, and using the lowest TTL we find.

OK, let me try to say that in English. DNS is an unnecessarily complex protocol. There's a reason Dr. Bernstein muttered very darkly about DNS' format. A DNS record has multiple records. Each and every DNS record has a "TTL": Time to live. This tells the DNS resolver how long the DNS packet should be stored locally.

Deadwood, however, doesn't store each record individually. Deadwood stores the entire DNS data packet as a single "black box" packet and only does the most cursory inspection of the DNS packet to figure out how long the TTL should be. In more detail, Deadwood usually just looks at the TTL of the first record to determine how long to cache the packet. Since, in the case of some records, we have what is called a CNAME record ("This host really has this name"), we sometimes have a packet that looks like this (this is a real resolution of www.google.com I just performed):

• www.google.com actually is an alias for the name www.l.google.com; remember this for 604800 seconds (one week)
• www.l.google.com has the IP 74.125.159.106; remember this for 300 seconds (five minutes)
• www.l.google.com also has the IP 74.125.159.147; remember this for five minutes
• www.l.google.com has the IP 74.125.159.103; again remember this for five minutes

Now, the problem is that Deadwood used to remember both the fact that Google's portal really has the name www.l.google.com for a week, in addition to all of the IPs for www.l.google.com.

A few months ago, I finally fixed things so, when the first answer is this CNAME (no, we really have a different name) answer, we will look past the CNAME record to see if the name the CNAME points to has a lower TTL (how long we want to remember the record).

This is the only time we do any real inspection of the DNS packet. Once we implement DNS decompression, this will change.

Right now, I'm trying to decide what is a reasonable way to store the DNS packet internally after inspecting and decompressing the packet. There are various possibilities, which I will discuss in my next blog entry.

A pet peeve of mine

One pet peeve of mine is when people send MaraDNS support requests or bug reports via private mail. When someone does this, I get irritated and angry to the point that smoke starts coming out of my ears. The thing is that I'm working on rewriting the Deadwood resolver and after spending hours on a given day working on the code, I'm pretty burnt out and just don't have the time to deal with support email.

So, I've made it pretty clear that I don't do free private email MaraDNS support.

Despite this, I got two requests for MaraDNS support via private email last week.

AAAAAAAARRRRRRRRGGGGGGGGGGGHHHHHHHHH!

When I explained my "pay me to support policy" to one of these people, they explained that they didn't know how to file non-security bug reports for MaraDNS. So, I've now clarified that the MaraDNS mailing list is the place to file your bug reports and that I don't have the time to maintain a bug tracker for MaraDNS.

In addition, so that these kinds of emails can be more easily handled, I have just hacked together a Perl script (taking my spam filter Perl script and making the appropriate changes) to make it trivial for me to send a "Show me the money or, if you're a cheapskate, here's how to take this concern to the list" form reply to people who ask for MaraDNS support via private email.

I'm really sorry guys. I'm devoting all of my time I spend developing MaraDNS on getting Deadwood out the door. I just don't have time to adequately handle MaraDNS support or non-security bug reports via private email. Please pay me for my time to take it to the list.

Deadwood 2.4.03 released

I have just released Deadwood 2.4.03. Like all 2.4 releases of Deadwood, this is a testing release; while reasonable effort has been made to keep the code bug-free, the emphasis is on adding new features and not on fixing bugs.

This release is, from the user's point of view, identical to Deadwood 2.4.02. The changes are all under-the-hood changes.

I have changed the code that handles dictionary variables to use the already-in-place code in DwHash.c instead of trying to implement yet another string-indexed array in Deadwood. The changes I made were fairly minor, but needed a lot of testing with Valgrind to make sure I wasn't leaking any memory or doing any double-freeing of elements.

I also made the Valgrind test more fussy; for Deadwood to pass its regression, it now needs to generate no errors when Deadwood is compiled with -DVALGRIND_NOERRORS (Valgrind doesn't like how Deadwood reads uninitialized memory to get more entropy for the random number generator).

I also had to revise the hash_magic_number test a little since the DwDict.c code is now mostly a wrapper for the relevant functions in DwHash.c.

Next: Implement real compression and decompression for DNS RRs, and implement resource record rotation.

It can be downloaded at maradns.org/deadwood/testing.

To keep things clean, I have removed all snapshot releases.

New Deadwood snapshot

I'm done some testing with DwHash to make sure we can do a lot of hash operations and generate no errors that Valgrind can see (all allocated memory is freed, no errors that Valgrind reports).

Now, I will make sure I can have a version of Deadwood that doesn't generate any Valgrind errors when compiled with -DVALGRIND_NOERRORS (Valgrind doesn't like how Deadwood reads uninitialized memory to get more entropy for the random number generator).

Then, I will convert DwDict to use DwHash routines instead of its current simple hash. After that, I will release Deadwood 2.4.03.

Note that DwDict's hash wastes a little memory. In more detail, the hash as a whole has a single unused pointer (fila) and an unused 32-bit value (max); this wastes 8 bytes on a 32-bit system and 12 (or 16 depending on how the structure is padded [1]) on a 64-bit system. Each element has a single unused pointer (fila) and unused 64-bit value (expire). This wastes 12 bytes per element on a 32-bit system and 16 bytes per element on a 64-bit system (or more depending on how the structure is padded).

I'm doing things this way so I only have one codebase to maintain (the DwHash codebase) and because changing things to not have this waste is more bother than it's worth in C. Can you say not an object oriented language?

The snapshot can be seen at maradns.org/deadwood/snap

[1] Is there a "don't pad structures" GCC option? There really should be.

Deadwood snapshot update

dwh_hash_autogrow() function created and test framework (Makefile.hsck) added to test this function.

It can be seen at maradns.org/deadwood/snap

I found a bug in ObHack 006b

I found a bug in ObHack 006b. Occasionally, the "You found a secret area!" message pops up when I stand outside a secret door, which spoils a secret.

In more detail, with the seed "OB-Doom1-200906" (no quotes in the actual seed), using the game "Doom 1", the length "Full Game", the mode "Single player", and with the following adjustments: Level Size "Small", Monsters "Plenty", Puzzles "Heaps", Outdoors "More", Switches "Keys only", Steepness "Some", Health "Enough", Ammo "Enough", and Start weapon "Basic", in E1M3, the secret area leading to the secret level gives me the "Your found a secret area" message when I stand outside the secret door.

I hope to find time to fix this bug this week sometime and released ObHack 006c with this one bug fixed.

Deadwood snapshot; MaraDNS keeping old colors

I have released a new Deadwood snapshot today. After looking at various hacks to give Object-oriented capabilities to C, I decided to not go that route and just add a "use_fila" flag to the relevant functions in DwHash.c. This is how I'm going to expand the hash routines in DwHash.c to work with DwDict.c.

Now I just need to add an autogrow function.

I had my girlfriend look at the new design I proposed for MaraDNS.org and told me she prefers the older design; the colors are sharper.

The snapshot is at maradns.org/deadwood/snap