← Back to branch summary

~ubuntu-branches/ubuntu/wily/maradns/wily-proposed

« back to all changes in this revision

Viewing changes to deadwood-3.2.07/doc/internals/CACHE.DESIGN

  • Committer: Package Import Robot
  • Author(s): Dariusz Dwornikowski, Tomasz Buchert, Dariusz Dwornikowski
  • Date: 2015-03-27 18:34:08 UTC
  • mfrom: (1.2.12)
  • Revision ID: package-import@ubuntu.com-20150327183408-wnfachdkdjt96yu6
Tags: 2.0.11-1
http://bugs.debian.org/785536
http://bugs.debian.org/785535
[ Tomasz Buchert ]
* Imported Upstream version 2.0.11

[ Dariusz Dwornikowski ]
* d/patches: 
  - refreshed all patches for new deadwood version
  - removed generating of random prime on build (Closes: #785536) 
* d/rules: date taken from changelog (Closes: #785535)

Show diffs side-by-side

added added

removed removed

Lines of Context:
deadwood-3.2.07/doc/internals/CACHE.DESIGN
 
1
[Note: This data is terribly out of date, based on the peliminary design for
 
2
 Deadwood 2 back in 2007.  In 2010, in order to implement full recursion,
 
3
 I added a whole bunch of types, such as CNAME referrals, NS referrals,
 
4
 and a couple of types for truncated replies.  I also have two different
 
5
 types for "not found" packets; one for NXDOMAIN, and another for 
 
6
 non-NXDOMAIN "not found" replies.  See DwRecurse.h and DwRecurse.c for
 
7
 an overview; there are extensive comments that explain the datatypes
 
8
 stored here.
 
9
 
 
10
 I should also point out the simple answers have offsets to RRs in the
 
11
 answers, and are no longer stored in compressed form.  The following data
 
12
 types are only used in the "tiny" 2.3 branch of Deadwood]
 
13
 
 
14
Cache data: Cached data will use the hash (see HASH.DESIGN) 
 
15
            and be stored like this:
 
16
 
 
17
       <raw DNS answer><ANCOUNT><NSCOUNT><ARCOUNT><type>
 
18
 
 
19
       The raw DNS answer is the packet, as-is sent from the server (complete
 
20
       with compression pointers, etc), starting after the end of the 
 
21
       question.  Basically, we reject DNS replies that don't have a QDCOUNT
 
22
       of 1, that don't have the expected DNS question, or that don't have
 
23
       the expected query ID.  We then shave off the DNS header (noting
 
24
       ANCOUNT, NSCOUNT, and ARCOUNT), the question, and put the rest of
 
25
       the reply in the cache, adding (AN/NS/AR)COUNT at the end of the
 
26
       cached packet.
 
27
 
 
28
       The cache is an assosciative array; the "key" is the DNS question;
 
29
       the value is the answer as described above.
 
30
 
 
31
       When getting an answer from the cache, we sew the key, value, and 
 
32
       current query to give the client an answer.  Basically, in the
 
33
       header:
 
34
 
 
35
       ID: As sent by the client
 
36
       QR: 1, since it is a reply
 
37
       OPCODE: 0
 
38
       AA: 0 (since we're a cache)
 
39
       TC: 0 (if we get a TC of 1 from the remote server, we do not
 
40
              cache the reply, but pass on a reply to the client with
 
41
              the TC bit on.  This way, they can use DwTcp to get
 
42
              a non-cached answer.  Yes, the real solution is to use
 
43
              TCP and UDP in the same daemon, but we'll deal with that 
 
44
              later)
 
45
       RD: 1 (We reject queries where this is 0)
 
46
       RA: 1 (Some DNS stub resolvers actually check this bit)
 
47
       Z: 0
 
48
       RCODE: 0 or 3 if "type" in cache is 1 (would be 2 if we have a 
 
49
              server failure)
 
50
       QDCOUNT: 1
 
51
       (AN/NS/AR)COUNT: As per the last 6 bytes of the value in the cache
 
52
       Question: As per the key + (0x0001) (CLASS 1)
 
53
       Answer: The rest of the value after shaving off (AN/NS/AR)COUNT
 
54
 
 
55
type: Type is an 8-bit value placed at the end of the string for each
 
56
      cache entry.  Type currently has two values:
 
57
 
 
58
        0: This indicates that the rest of the string is stored as described
 
59
           here, with an RCODE of 0
 
60
 
 
61
        1: This indicates that the rest of the string is stored as described
 
62
           here, with an RCODE of 1
 
63
 
 
64
== The cache on disk ==
 
65
 
 
66
The cache file on disk is pretty simple; it just has a 4-byte header, 
 
67
followed by the maximum number of elements the cache can have (not really
 
68
used in Deadwood 2.4), followed by each hash element.
 
69
 
 
70
Each hash element has three values: A 4-byte big endian number storing the
 
71
number of bytes in the key, followed by the actual key.  The same string
 
72
format for the value in the hash.  This is followed by an 8-byte timestamp
 
73
that uses a Deadwood-specific format for the time when the entry expires.
 
74
 
 
75
The expires are stored with the least important entries being first in
 
76
the file, followed by more and more important entires.
 
77
 
 
78
OK, in more detail, there are three data types in the cache:
 
79
 
 
80
1) 4-byte big endian binary numbers
 
81
 
 
82
2) Strings (this is a black box, as far as the code that writes to disk is
 
83
   concerned)
 
84
 
 
85
3) 8-byte binary timestamps.
 
86
 
 
87
The cache starts with a 4-byte header '\0'DX2 (An ASCII null, followed by 
 
88
"DX2" in ASCII).  It then has a 4-byte number with the maximum allowed number 
 
89
of entries in the cache.
 
90
 
 
91
This is followed by each hash element.
 
92
 
 
93
4-byte: Length of key
 
94
String: Key
 
95
4-byte: Length of value
 
96
String: Value
 
97
Timestamp: Expire time for record
 
98
 
 
99
The records closer to the end of the file are considered more important
 
100
than records at the beginning of the file; this means they are less likely
 
101
to be axed when the hash is full and needs to remove elements.
 
102
 
 
103
 
 
104