1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
2007/03/30 - Header storage in trees
This documentation describes how to store headers in radix trees, providing
fast access to any known position, while retaining the ability to grow/reduce
any arbitrary header without having to recompute all positions.
Principle :
We have a radix tree represented in an integer array, which represents the
total number of bytes used by all headers whose position is below it. This
ensures that we can compute any header's position in O(log(N)) where N is
the number of headers.
Example with N=16 :
+-----------------------+
| |
+-----------+ +-----------+
| | | |
+-----+ +-----+ +-----+ +-----+
| | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 A B C D E F
To reach header 6, we have to compute hdr[0]+hdr[4]+hdr[6]
With this method, it becomes easy to grow any header and update the array.
To achieve this, we have to replace one after the other all bits on the
right with one 1 followed by zeroes, and update the position if it's higher
than current position, and stop when it's above number of stored headers.
For instance, if we want to grow hdr[6], we proceed like this :
6 = 0110 (BIN)
Let's consider the values to update :
(bit 0) : (0110 & ~0001) | 0001 = 0111 = 7 > 6 => update
(bit 1) : (0110 & ~0011) | 0010 = 0110 = 6 <= 6 => leave it
(bit 2) : (0110 & ~0111) | 0100 = 0100 = 4 <= 6 => leave it
(bit 4) : (0110 & ~1111) | 1000 = 1000 = 8 > 6 => update
(bit 5) : larger than array size, stop.
It's easy to walk through the tree too. We only have one iteration per bit
changing from X to the ancestor, and one per bit from the ancestor to Y.
The ancestor is found while walking. To go from X to Y :
pos = pos(X)
while (Y != X) {
if (Y > X) {
// walk from Y to ancestor
pos += hdr[Y]
Y &= (Y - 1)
} else {
// walk from X to ancestor
pos -= hdr[X]
X &= (X - 1)
}
}
However, it is not trivial anymore to linearly walk the tree. We have to move
from a known place to another known place, but a jump to next entry costs the
same as a jump to a random place.
Other caveats :
- it is not possible to remove a header, it is only possible to empty it.
- it is not possible to insert a header, as that would imply a renumbering.
=> this means that a "defrag" function is required. Headers should preferably
be added, then should be stuffed on top of destroyed ones, then only
inserted if absolutely required.
When we have this, we can then focus on a 32-bit header descriptor which would
look like this :
{
unsigned line_len :13; /* total line length, including CRLF */
unsigned name_len :6; /* header name length, max 63 chars */
unsigned sp1 :5; /* max spaces before value : 31 */
unsigned sp2 :8; /* max spaces after value : 255 */
}
Example :
Connection: close \r\n
<---------+-----+-----+-------------> line_len
<-------->| | | name_len
<-----> | sp1
<-------------> sp2
Rem:
- if there are more than 31 spaces before the value, the buffer will have to
be moved before being registered
- if there are more than 255 spaces after the value, the buffer will have to
be moved before being registered
- we can use the empty header name as an indicator for a deleted header
- it would be wise to format a new request before sending lots of random
spaces to the servers.
- normal clients do not send such crap, so those operations *may* reasonably
be more expensive than the rest provided that other ones are very fast.
It would be handy to have the following macros :
hdr_eon(hdr) => end of name
hdr_sov(hdr) => start of value
hdr_eof(hdr) => end of value
hdr_vlen(hdr) => length of value
hdr_hlen(hdr) => total header length
A 48-bit encoding would look like this :
Connection: close \r\n
<---------+------+---+--------------> eoh = 16 bits
<-------->| | | eon = 8 bits
<--------------->| | sov = 8 bits
<---> vlen = 16 bits
|
