| 1 |
The Hostmask and Netmask System |
| 2 |
Copyright(c) 2001 by Andrew Miller(A1kmm)<a1kmm@mware.virtualave.net> |
| 3 |
|
| 4 |
$Id$ |
| 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. |
