1 /* Copyright © 2012 Brandon L Black <blblack@gmail.com>
2 *
3 * This file is part of gdnsd.
4 *
5 * gdnsd-plugin-geoip is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * gdnsd-plugin-geoip is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with gdnsd. If not, see <http://www.gnu.org/licenses/>.
17 *
18 */
19
20 #ifndef NTREE_H
21 #define NTREE_H
22
23 #include <gdnsd/compiler.h>
24 #include <gdnsd/plugapi.h>
25
26 #include <inttypes.h>
27
28 /***************************************
29 * ntree_t and related methods
30 **************************************/
31
32 // ipv6 is a uint8_t[16]
33 // bit is 0->127 (MSB -> LSB)
34 F_NONNULL F_UNUSED
SETBIT_v6(uint8_t * ipv6,const unsigned bit)35 static void SETBIT_v6(uint8_t* ipv6, const unsigned bit) {
36 dmn_assert(bit < 128);
37 ipv6[bit >> 3] |= (1UL << (~bit & 7));
38 }
39
40 // Some constant IPv6 address fragments...
41
42 // 96-bit prefix
43 static const uint8_t start_v4compat[16] =
44 { 0x00, 0x00, 0x00, 0x00,
45 0x00, 0x00, 0x00, 0x00,
46 0x00, 0x00, 0x00, 0x00,
47 0x00, 0x00, 0x00, 0x00 };
48
49 // 96-bit prefix
50 static const uint8_t start_v4mapped[16] =
51 { 0x00, 0x00, 0x00, 0x00,
52 0x00, 0x00, 0x00, 0x00,
53 0x00, 0x00, 0xFF, 0xFF,
54 0x00, 0x00, 0x00, 0x00 };
55
56 // 96-bit prefix
57 static const uint8_t start_siit[16] =
58 { 0x00, 0x00, 0x00, 0x00,
59 0x00, 0x00, 0x00, 0x00,
60 0xFF, 0xFF, 0x00, 0x00,
61 0x00, 0x00, 0x00, 0x00 };
62
63 // 96-bit prefix
64 static const uint8_t start_wkp[16] =
65 { 0x00, 0x64, 0xFF, 0x9B,
66 0x00, 0x00, 0x00, 0x00,
67 0x00, 0x00, 0x00, 0x00,
68 0x00, 0x00, 0x00, 0x00 };
69
70 // 16-bit prefix
71 static const uint8_t start_6to4[16] =
72 { 0x20, 0x02, 0x00, 0x00,
73 0x00, 0x00, 0x00, 0x00,
74 0x00, 0x00, 0x00, 0x00,
75 0x00, 0x00, 0x00, 0x00 };
76
77 // 32-bit prefix
78 static const uint8_t start_teredo[16] =
79 { 0x20, 0x01, 0x00, 0x00,
80 0x00, 0x00, 0x00, 0x00,
81 0x00, 0x00, 0x00, 0x00,
82 0x00, 0x00, 0x00, 0x00 };
83
84 // zero-initializer for IPv6
85 static const struct in6_addr ip6_zero = { .s6_addr = { 0 } };
86
87 /*
88 * This is our network/mask database. It becomes fully populated, in that
89 * a lookup of any address *will* find a node. This is because the original
90 * GeoIP database is also fully populated. It maps network/mask -> dclist,
91 * and is constructed by walking the entire input GeoIP database and remapping
92 * it against this maps's vscf config.
93 */
94
95 /*
96 * the legal range of a dclist or a node index is 0 -> INT32_MAX,
97 * and we store it as a uint32_t using the high bit to signal which
98 * For each of the branch fields zero and one:
99 * if the MSB is set, the rest of the uint32_t is a dclist
100 * index (terminal). If the remainder is INT32_MAX (meaning
101 * the whole is UINT32_MAX), it is the special value NN_UNDEF.
102 * if the MSB is not set, the rest of the uint32_t is
103 * a node index for recursion.
104 */
105
106 #define NN_UNDEF UINT32_MAX // special undefined dclist, never
107 // the result of a lookup, used to
108 // to get netmasks correct adjacent
109 // to undefined v4-like spaces...
110 #define NN_IS_DCLIST(x) ((x) & (1U << 31U))
111 #define NN_GET_DCLIST(x) ((x) & ~(1U << 31U)) // strips high bit
112 #define NN_SET_DCLIST(x) ((x) | (1U << 31U)) // sets high bit
113
114 typedef struct {
115 uint32_t zero;
116 uint32_t one;
117 } nnode_t;
118
119 typedef struct {
120 nnode_t* store;
121 unsigned ipv4; // cached ipv4 lookup hint
122 unsigned count; // raw nodes, including interior ones
123 unsigned alloc; // current allocation of store during construction,
124 // set to zero after _finish()
125 } ntree_t;
126
127 F_WUNUSED
128 ntree_t* ntree_new(void);
129
130 F_NONNULL
131 void ntree_destroy(ntree_t* tree);
132
133 // keeps ->count up-to-date and resizes storage
134 // as necc by doubling.
135 F_NONNULL
136 unsigned ntree_add_node(ntree_t* tree);
137
138 // call this after done adding data
139 F_NONNULL
140 void ntree_finish(ntree_t* tree);
141
142 #ifndef NDEBUG
143 F_NONNULL
144 void ntree_debug_dump(const ntree_t* tree);
145 F_NONNULL
146 void ntree_assert_optimal(const ntree_t* tree);
147 #else
148 #define ntree_debug_dump(x)
149 #define ntree_assert_optimal(x)
150 #endif
151
152 F_NONNULL
153 unsigned ntree_lookup(const ntree_t* tree, const client_info_t* client, unsigned* scope_mask);
154
155 #endif // NTREE_H
156