/[svn]/ircd-hybrid/doc/technical/hostmask.txt
ViewVC logotype

Contents of /ircd-hybrid/doc/technical/hostmask.txt

Parent Directory Parent Directory | Revision Log Revision Log


Revision 30 - (show annotations)
Sun Oct 2 20:03:27 2005 UTC (14 years, 2 months ago) by adx
File MIME type: text/plain
File size: 5053 byte(s)
- imported sources
- can be moved later according to the directory/branching scheme,
  but we need the svn up

1 The Hostmask and Netmask System
2 Copyright(c) 2001 by Andrew Miller(A1kmm)<a1kmm@mware.virtualave.net>
3
4 $Id: hostmask.txt,v 1.4 2005/08/20 15:00:55 knight Exp $
5 ------------------------------------------------------------------------
6
7 Contents ::
8 ============
9 * Section 1: Motivation
10 * Section 2: Underlying Mechanism
11 - 2.1: General Overview
12 - 2.2: IPv4 Netmasks
13 - 2.3: IPv6 Netmasks
14 - 2.4: Hostmasks
15 * Section 3: Exposed Abstraction Layer
16 - 3.1: Parsing Masks
17 - 3.2: Adding Configuration Items
18 - 3.3: Initialising or Rehashing
19 - 3.4: Finding IP/Hostname Confs
20 - 3.5: Deleting Entries
21 - 3.6: Reporting Entries
22
23 Section 1: Motivation
24 =====================
25
26 Looking up configuration hostnames and IP addresses (such as for I-Lines
27 and K-Lines) needs to be implemented efficiently. It turns out a hash
28 based algorithm like that employed here performs very will on the average
29 case, which is what we should be the most concerned about. A profiling
30 comparison with the mtre code using data from a real network confirmed
31 that this algorithm performs much better.
32
33
34 Section 2: Underlying Mechanism
35 ===============================
36
37 2.1: General Overview
38 ---------------------
39
40 In short, a hash-table with linked lists for buckets is used to locate
41 the correct hostname/netmask entries. In order to support CIDR IPs and
42 wildcard masks, the entire key cannot be hashed, and there is a need to
43 rehash. The means for deciding how much to hash differs between the
44 hostmasks and IPv4/6 netmasks.
45
46 2.2: IPv4 Netmasks
47 ------------------
48
49 In order to hash IPv4 netmasks for addition to the hash, the mask is first
50 processed into a 32-bit address and a number of bits is used. All unused
51 bits are set to 0. The mask could be in these forms:
52
53 1.2.3.4 => 1.2.3.4 : 32
54 1.2.3.* => 1.2.3.0 : 24
55 1.2.*.* => 1.2.0.0 : 16
56 1.2.3.64/26 => 1.2.3.64 : 26
57
58 The number of whole bytes is then calculated, and only those bytes are
59 hashed (e.g. 1.2.3.64/26 and 1.2.3.0/24 hash the same). When a complete
60 IPv4 address is given so that an IPv4 match can be found the entire IP
61 address is first hashed, and then looked up in the table. Then the most
62 significant three bytes are hashed, followed by the most significant two,
63 the most significant one, and finally the "identity hash" bucket is
64 searched (to match masks like 192/7).
65
66 2.3: IPv6 Netmasks
67 ------------------
68
69 As per the IPv4 netmasks, except that instead of rehashing with one byte
70 granularity, a 16-bit (two byte) granularity is used, as 16 rehashes is
71 considered too great a fixed offset to be justified for a (possible)
72 slight reduction in hash collisions.
73
74 2.4: Hostmasks
75 --------------
76
77 On adding a hostmask to the hash, all of the hostmask right of the next
78 dot after the last wildcard character in the string is hashed, or in the
79 case that there are no wildcards in the hostmask, the entire string is
80 hashed.
81
82 On searching for a hostmask match, the entire hostname is hashed, followed
83 by the entire hostmask after the first dot, followed by the entire hostmask
84 after the second dot, and so on. Finally the "identity hash" bucket is checked
85 to catch hostnames like *test*.
86
87 Section 3: Exposed Abstraction Layer
88 ====================================
89
90 Section 3.1: Parsing Masks
91 --------------------------
92
93 Call "parse_netmask()" with the netmask and a pointer to an irc_inaddr
94 structure to be filled in, as well as a pointer to an integer where the
95 number of bits will be placed.
96
97 Always check the return value, if it returns HM_MOST, it means that the
98 mask is probably a hostmask. If it returns HM_IPV4, it means it was an
99 IPv4 address. If it returns HM_IPV6, it means it was an IPv6 address.
100 If parse_netmask() returns HM_MOST however, no change is made to the
101 irc_inaddr structure or the number of bits.
102
103 Section 3.2: Adding Configuration Items
104 ---------------------------------------
105
106 Call "add_conf_by_address()" with the hostname or IP mask, the username,
107 and the ConfItem* to associate with this mask.
108
109 Section 3.3: Initialising and Rehashing
110 ---------------------------------------
111
112 To initialise, call "init_host_hash()". This only needs to be done once
113 on start-up. On rehash, to wipe out the old unwanted configuration, and
114 free them if there are no references to them, call
115 "clear_out_address_conf()".
116
117 Section 3.4: Finding IP/Hostname Confs
118 ---------------------------------------
119
120 Call "find_address_conf()" with the hostname, the username, the address,
121 the address family and the client-supplied password. To find a D-Line,
122 call "find_dline()" with the address and address family.
123
124 Section 3.5: Deleted Entries
125 ----------------------------
126
127 Call "delete_one_address_conf()" with the hostname and the ConfItem*.
128
129 Section 3.6: Reporting Entries
130 ------------------------------
131
132 Call "report_dlines()", "report_exemptlines()", "report_Klines()", or
133 "report_Ilines()" with the client pointer to report to. Note these walk
134 the hash, which is inefficient, but these are not called often enough
135 to justify the memory and maintenance clockcycles to for more efficient
136 data structuring.

Properties

Name Value
svn:eol-style native
svn:keywords "Id Revision"

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.26