24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
| 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
34 */
35
36/**
37 * \file
38 *
39 * This file contains structures combining types and functions to
40 * manipulate those structures that help building DNS lookup trees.
41 */
42#include "config.h"
43#include "util/storage/dnstree.h"
44#include "util/data/dname.h"
45#include "util/net_help.h"
46
47int name_tree_compare(const void* k1, const void* k2)
48{
49 struct name_tree_node* x = (struct name_tree_node*)k1;
50 struct name_tree_node* y = (struct name_tree_node*)k2;
51 int m;
52 if(x->dclass != y->dclass) {
53 if(x->dclass < y->dclass)
54 return -1;
55 return 1;
56 }
57 return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
58}
59
60int addr_tree_compare(const void* k1, const void* k2)
61{
62 struct addr_tree_node* n1 = (struct addr_tree_node*)k1;
63 struct addr_tree_node* n2 = (struct addr_tree_node*)k2;
64 int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr,
65 n2->addrlen);
66 if(r != 0) return r;
67 if(n1->net < n2->net)
68 return -1;
69 if(n1->net > n2->net)
70 return 1;
71 return 0;
72}
73
74void name_tree_init(rbtree_t* tree)
75{
76 rbtree_init(tree, &name_tree_compare);
77}
78
79void addr_tree_init(rbtree_t* tree)
80{
81 rbtree_init(tree, &addr_tree_compare);
82}
83
84int name_tree_insert(rbtree_t* tree, struct name_tree_node* node,
85 uint8_t* name, size_t len, int labs, uint16_t dclass)
86{
87 node->node.key = node;
88 node->name = name;
89 node->len = len;
90 node->labs = labs;
91 node->dclass = dclass;
92 node->parent = NULL;
93 return rbtree_insert(tree, &node->node) != NULL;
94}
95
96int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
97 struct sockaddr_storage* addr, socklen_t addrlen, int net)
98{
99 node->node.key = node;
100 memcpy(&node->addr, addr, addrlen);
101 node->addrlen = addrlen;
102 node->net = net;
103 node->parent = NULL;
104 return rbtree_insert(tree, &node->node) != NULL;
105}
106
107void addr_tree_init_parents(rbtree_t* tree)
108{
109 struct addr_tree_node* node, *prev = NULL, *p;
110 int m;
111 RBTREE_FOR(node, struct addr_tree_node*, tree) {
112 node->parent = NULL;
113 if(!prev || prev->addrlen != node->addrlen) {
114 prev = node;
115 continue;
116 }
117 m = addr_in_common(&prev->addr, prev->net, &node->addr,
118 node->net, node->addrlen);
119 /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */
120 /* find the previous, or parent-parent-parent */
121 for(p = prev; p; p = p->parent)
122 if(p->net <= m) {
123 /* ==: since prev matched m, this is closest*/
124 /* <: prev matches more, but is not a parent,
125 * this one is a (grand)parent */
126 node->parent = p;
127 break;
128 }
129 prev = node;
130 }
131}
132
133void name_tree_init_parents(rbtree_t* tree)
134{
135 struct name_tree_node* node, *prev = NULL, *p;
136 int m;
137 RBTREE_FOR(node, struct name_tree_node*, tree) {
138 node->parent = NULL;
139 if(!prev || prev->dclass != node->dclass) {
140 prev = node;
141 continue;
142 }
143 (void)dname_lab_cmp(prev->name, prev->labs, node->name,
144 node->labs, &m); /* we know prev is smaller */
145 /* sort order like: . com. bla.com. zwb.com. net. */
146 /* find the previous, or parent-parent-parent */
147 for(p = prev; p; p = p->parent)
148 if(p->labs <= m) {
149 /* ==: since prev matched m, this is closest*/
150 /* <: prev matches more, but is not a parent,
151 * this one is a (grand)parent */
152 node->parent = p;
153 break;
154 }
155 prev = node;
156 }
157}
158
159struct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name,
160 size_t len, int labs, uint16_t dclass)
161{
162 struct name_tree_node key;
163 key.node.key = &key;
164 key.name = name;
165 key.len = len;
166 key.labs = labs;
167 key.dclass = dclass;
168 return (struct name_tree_node*)rbtree_search(tree, &key);
169}
170
171struct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name,
172 size_t len, int labs, uint16_t dclass)
173{
174 rbnode_t* res = NULL;
175 struct name_tree_node *result;
176 struct name_tree_node key;
177 key.node.key = &key;
178 key.name = name;
179 key.len = len;
180 key.labs = labs;
181 key.dclass = dclass;
182 if(rbtree_find_less_equal(tree, &key, &res)) {
183 /* exact */
184 result = (struct name_tree_node*)res;
185 } else {
186 /* smaller element (or no element) */
187 int m;
188 result = (struct name_tree_node*)res;
189 if(!result || result->dclass != dclass)
190 return NULL;
191 /* count number of labels matched */
192 (void)dname_lab_cmp(result->name, result->labs, key.name,
193 key.labs, &m);
194 while(result) { /* go up until qname is subdomain of stub */
195 if(result->labs <= m)
196 break;
197 result = result->parent;
198 }
199 }
200 return result;
201}
202
203struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
204 struct sockaddr_storage* addr, socklen_t addrlen)
205{
206 rbnode_t* res = NULL;
207 struct addr_tree_node* result;
208 struct addr_tree_node key;
209 key.node.key = &key;
210 memcpy(&key.addr, addr, addrlen);
211 key.addrlen = addrlen;
212 key.net = (addr_is_ip6(addr, addrlen)?128:32);
213 if(rbtree_find_less_equal(tree, &key, &res)) {
214 /* exact */
215 return (struct addr_tree_node*)res;
216 } else {
217 /* smaller element (or no element) */
218 int m;
219 result = (struct addr_tree_node*)res;
220 if(!result || result->addrlen != addrlen)
221 return 0;
222 /* count number of bits matched */
223 m = addr_in_common(&result->addr, result->net, addr,
224 key.net, addrlen);
225 while(result) { /* go up until addr is inside netblock */
226 if(result->net <= m)
227 break;
228 result = result->parent;
229 }
230 }
231 return result;
232}
233
234int
235name_tree_next_root(rbtree_t* tree, uint16_t* dclass)
236{
237 struct name_tree_node key;
238 rbnode_t* n;
239 struct name_tree_node* p;
240 if(*dclass == 0) {
241 /* first root item is first item in tree */
242 n = rbtree_first(tree);
243 if(n == RBTREE_NULL)
244 return 0;
245 p = (struct name_tree_node*)n;
246 if(dname_is_root(p->name)) {
247 *dclass = p->dclass;
248 return 1;
249 }
250 /* root not first item? search for higher items */
251 *dclass = p->dclass + 1;
252 return name_tree_next_root(tree, dclass);
253 }
254 /* find class n in tree, we may get a direct hit, or if we don't
255 * this is the last item of the previous class so rbtree_next() takes
256 * us to the next root (if any) */
257 key.node.key = &key;
258 key.name = (uint8_t*)"\000";
259 key.len = 1;
260 key.labs = 0;
261 key.dclass = *dclass;
262 n = NULL;
263 if(rbtree_find_less_equal(tree, &key, &n)) {
264 /* exact */
265 return 1;
266 } else {
267 /* smaller element */
268 if(!n || n == RBTREE_NULL)
269 return 0; /* nothing found */
270 n = rbtree_next(n);
271 if(n == RBTREE_NULL)
272 return 0; /* no higher */
273 p = (struct name_tree_node*)n;
274 if(dname_is_root(p->name)) {
275 *dclass = p->dclass;
276 return 1;
277 }
278 /* not a root node, return next higher item */
279 *dclass = p->dclass+1;
280 return name_tree_next_root(tree, dclass);
281 }
282}
| 34 */
35
36/**
37 * \file
38 *
39 * This file contains structures combining types and functions to
40 * manipulate those structures that help building DNS lookup trees.
41 */
42#include "config.h"
43#include "util/storage/dnstree.h"
44#include "util/data/dname.h"
45#include "util/net_help.h"
46
47int name_tree_compare(const void* k1, const void* k2)
48{
49 struct name_tree_node* x = (struct name_tree_node*)k1;
50 struct name_tree_node* y = (struct name_tree_node*)k2;
51 int m;
52 if(x->dclass != y->dclass) {
53 if(x->dclass < y->dclass)
54 return -1;
55 return 1;
56 }
57 return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
58}
59
60int addr_tree_compare(const void* k1, const void* k2)
61{
62 struct addr_tree_node* n1 = (struct addr_tree_node*)k1;
63 struct addr_tree_node* n2 = (struct addr_tree_node*)k2;
64 int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr,
65 n2->addrlen);
66 if(r != 0) return r;
67 if(n1->net < n2->net)
68 return -1;
69 if(n1->net > n2->net)
70 return 1;
71 return 0;
72}
73
74void name_tree_init(rbtree_t* tree)
75{
76 rbtree_init(tree, &name_tree_compare);
77}
78
79void addr_tree_init(rbtree_t* tree)
80{
81 rbtree_init(tree, &addr_tree_compare);
82}
83
84int name_tree_insert(rbtree_t* tree, struct name_tree_node* node,
85 uint8_t* name, size_t len, int labs, uint16_t dclass)
86{
87 node->node.key = node;
88 node->name = name;
89 node->len = len;
90 node->labs = labs;
91 node->dclass = dclass;
92 node->parent = NULL;
93 return rbtree_insert(tree, &node->node) != NULL;
94}
95
96int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
97 struct sockaddr_storage* addr, socklen_t addrlen, int net)
98{
99 node->node.key = node;
100 memcpy(&node->addr, addr, addrlen);
101 node->addrlen = addrlen;
102 node->net = net;
103 node->parent = NULL;
104 return rbtree_insert(tree, &node->node) != NULL;
105}
106
107void addr_tree_init_parents(rbtree_t* tree)
108{
109 struct addr_tree_node* node, *prev = NULL, *p;
110 int m;
111 RBTREE_FOR(node, struct addr_tree_node*, tree) {
112 node->parent = NULL;
113 if(!prev || prev->addrlen != node->addrlen) {
114 prev = node;
115 continue;
116 }
117 m = addr_in_common(&prev->addr, prev->net, &node->addr,
118 node->net, node->addrlen);
119 /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */
120 /* find the previous, or parent-parent-parent */
121 for(p = prev; p; p = p->parent)
122 if(p->net <= m) {
123 /* ==: since prev matched m, this is closest*/
124 /* <: prev matches more, but is not a parent,
125 * this one is a (grand)parent */
126 node->parent = p;
127 break;
128 }
129 prev = node;
130 }
131}
132
133void name_tree_init_parents(rbtree_t* tree)
134{
135 struct name_tree_node* node, *prev = NULL, *p;
136 int m;
137 RBTREE_FOR(node, struct name_tree_node*, tree) {
138 node->parent = NULL;
139 if(!prev || prev->dclass != node->dclass) {
140 prev = node;
141 continue;
142 }
143 (void)dname_lab_cmp(prev->name, prev->labs, node->name,
144 node->labs, &m); /* we know prev is smaller */
145 /* sort order like: . com. bla.com. zwb.com. net. */
146 /* find the previous, or parent-parent-parent */
147 for(p = prev; p; p = p->parent)
148 if(p->labs <= m) {
149 /* ==: since prev matched m, this is closest*/
150 /* <: prev matches more, but is not a parent,
151 * this one is a (grand)parent */
152 node->parent = p;
153 break;
154 }
155 prev = node;
156 }
157}
158
159struct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name,
160 size_t len, int labs, uint16_t dclass)
161{
162 struct name_tree_node key;
163 key.node.key = &key;
164 key.name = name;
165 key.len = len;
166 key.labs = labs;
167 key.dclass = dclass;
168 return (struct name_tree_node*)rbtree_search(tree, &key);
169}
170
171struct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name,
172 size_t len, int labs, uint16_t dclass)
173{
174 rbnode_t* res = NULL;
175 struct name_tree_node *result;
176 struct name_tree_node key;
177 key.node.key = &key;
178 key.name = name;
179 key.len = len;
180 key.labs = labs;
181 key.dclass = dclass;
182 if(rbtree_find_less_equal(tree, &key, &res)) {
183 /* exact */
184 result = (struct name_tree_node*)res;
185 } else {
186 /* smaller element (or no element) */
187 int m;
188 result = (struct name_tree_node*)res;
189 if(!result || result->dclass != dclass)
190 return NULL;
191 /* count number of labels matched */
192 (void)dname_lab_cmp(result->name, result->labs, key.name,
193 key.labs, &m);
194 while(result) { /* go up until qname is subdomain of stub */
195 if(result->labs <= m)
196 break;
197 result = result->parent;
198 }
199 }
200 return result;
201}
202
203struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
204 struct sockaddr_storage* addr, socklen_t addrlen)
205{
206 rbnode_t* res = NULL;
207 struct addr_tree_node* result;
208 struct addr_tree_node key;
209 key.node.key = &key;
210 memcpy(&key.addr, addr, addrlen);
211 key.addrlen = addrlen;
212 key.net = (addr_is_ip6(addr, addrlen)?128:32);
213 if(rbtree_find_less_equal(tree, &key, &res)) {
214 /* exact */
215 return (struct addr_tree_node*)res;
216 } else {
217 /* smaller element (or no element) */
218 int m;
219 result = (struct addr_tree_node*)res;
220 if(!result || result->addrlen != addrlen)
221 return 0;
222 /* count number of bits matched */
223 m = addr_in_common(&result->addr, result->net, addr,
224 key.net, addrlen);
225 while(result) { /* go up until addr is inside netblock */
226 if(result->net <= m)
227 break;
228 result = result->parent;
229 }
230 }
231 return result;
232}
233
234int
235name_tree_next_root(rbtree_t* tree, uint16_t* dclass)
236{
237 struct name_tree_node key;
238 rbnode_t* n;
239 struct name_tree_node* p;
240 if(*dclass == 0) {
241 /* first root item is first item in tree */
242 n = rbtree_first(tree);
243 if(n == RBTREE_NULL)
244 return 0;
245 p = (struct name_tree_node*)n;
246 if(dname_is_root(p->name)) {
247 *dclass = p->dclass;
248 return 1;
249 }
250 /* root not first item? search for higher items */
251 *dclass = p->dclass + 1;
252 return name_tree_next_root(tree, dclass);
253 }
254 /* find class n in tree, we may get a direct hit, or if we don't
255 * this is the last item of the previous class so rbtree_next() takes
256 * us to the next root (if any) */
257 key.node.key = &key;
258 key.name = (uint8_t*)"\000";
259 key.len = 1;
260 key.labs = 0;
261 key.dclass = *dclass;
262 n = NULL;
263 if(rbtree_find_less_equal(tree, &key, &n)) {
264 /* exact */
265 return 1;
266 } else {
267 /* smaller element */
268 if(!n || n == RBTREE_NULL)
269 return 0; /* nothing found */
270 n = rbtree_next(n);
271 if(n == RBTREE_NULL)
272 return 0; /* no higher */
273 p = (struct name_tree_node*)n;
274 if(dname_is_root(p->name)) {
275 *dclass = p->dclass;
276 return 1;
277 }
278 /* not a root node, return next higher item */
279 *dclass = p->dclass+1;
280 return name_tree_next_root(tree, dclass);
281 }
282}
|