1 /*********************************************************************************************************
2 * Software License Agreement (BSD License) *
3 * Author: Sebastien Decugis <sdecugis@freediameter.net> *
4 * *
5 * Copyright (c) 2020, WIDE Project and NICT *
6 * All rights reserved. *
7 * *
8 * Redistribution and use of this software in source and binary forms, with or without modification, are *
9 * permitted provided that the following conditions are met: *
10 * *
11 * * Redistributions of source code must retain the above *
12 * copyright notice, this list of conditions and the *
13 * following disclaimer. *
14 * *
15 * * Redistributions in binary form must reproduce the above *
16 * copyright notice, this list of conditions and the *
17 * following disclaimer in the documentation and/or other *
18 * materials provided with the distribution. *
19 * *
20 * * Neither the name of the WIDE Project or NICT nor the *
21 * names of its contributors may be used to endorse or *
22 * promote products derived from this software without *
23 * specific prior written permission of WIDE Project and *
24 * NICT. *
25 * *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
27 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
28 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
29 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
32 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
33 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
34 *********************************************************************************************************/
35
36 #include "acl_wl.h"
37
38 /* The configuration simply contains the allowed fqdn and/or domains (*.example.net)
39 * It is represented similarly to the DNS tree:
40 * (root)--___
41 * / \ \
42 * tld1 tld2 (tld3...)
43 * / |
44 * label1 label2
45 * / \
46 * lbl21 lbl22
47 * / \
48 * lbl211 *
49 *
50 * This tree would whitelist:
51 * - label1.tld1
52 * - lbl211.lbl21.label2.tld2
53 * - *.lbl22.label2.tld2
54 *
55 * The functions to add and search the tree are in aw_tree.c.
56 *
57 */
58
59 /* Maximum depth of the tree. We set a static size to avoid dynamic allocations. We report an error if this is not sufficient. */
60 #define AW_TREE_MAXDEPTH 10
61
62 /* An element of the tree */
63 struct tree_item {
64 struct fd_list chain; /* Link to elements at the same level. Ordered alphabetically. */
65 struct fd_list children; /* Sentinel for the subtree. */
66 char * str; /* the \0 terminated label, or NULL if it is a generic container ("*") */
67 int flags; /* PI_SEC_* flags */
68 int leaf; /* true if this item can be a leaf of the tree */
69 };
70
71 /* The root of the tree */
72 struct fd_list tree_root = FD_LIST_INITIALIZER(tree_root);
73
74 /* Note: we lock accesses to the tree with acl_wl_lock because of config reload */
75
76
77 /* The parsed name */
78 struct split_name {
79 struct {
80 char * str; /* start of this label */
81 size_t len; /* length of this label. It does not include the final "." or "\0" */
82 } label[AW_TREE_MAXDEPTH];
83 int last_lbl; /* idx of last label defined */
84 };
85
86 /* The following function explodes a name into a split_name structure */
parse_name(char * name,struct split_name * result)87 static int parse_name(char * name, struct split_name * result)
88 {
89 int i, l, prev_offset;
90
91 TRACE_ENTRY("%p %p", name, result);
92
93 /* First, initialize the result array */
94 memset(result, 0, sizeof(struct split_name));
95 result->label[0].str = name;
96 l = 0; prev_offset = 0;
97
98 for (i=0; name[i] != '\0'; i++) {
99 if (name[i]=='.') {
100 l++;
101 CHECK_PARAMS( l < AW_TREE_MAXDEPTH );
102
103 /* The previous label is complete, write its size */
104 result->label[l - 1].len = i - prev_offset;
105 prev_offset = i + 1;
106
107 /* Write the start of the new label */
108 result->label[l].str = name + i + 1;
109 }
110 }
111
112 /* Finally, write the size of the last label */
113 result->label[l].len = i - prev_offset;
114
115 result->last_lbl = l;
116
117 #if 0
118 fd_log_debug("Parsed name %s as:", name);
119 for (i=0; i<=l; i++)
120 fd_log_debug(" str[%d] len: %d, v:%.*s", i, result->label[i].len, result->label[i].len, result->label[i].str);
121 #endif /* 0 */
122 return 0;
123 }
124
125 /* Create a new tree_item structure */
new_ti(char * str,size_t len,int flags,int leaf)126 static struct tree_item * new_ti(char * str, size_t len, int flags, int leaf)
127 {
128 struct tree_item * ti;
129 char * s = NULL;
130
131 TRACE_ENTRY("%p %zd %x", str, len, flags);
132
133 if (str) {
134 CHECK_MALLOC_DO(s = malloc(len + 1), return NULL);
135 memcpy(s, str, len);
136 s[len] = '\0';
137 }
138
139 CHECK_MALLOC_DO( ti = malloc(sizeof(struct tree_item)), {free(s); return NULL; } );
140 memset(ti, 0, sizeof(struct tree_item));
141
142 fd_list_init(&ti->chain, ti);
143 fd_list_init(&ti->children, ti);
144 ti->str = s;
145 ti->flags = flags;
146 ti->leaf = leaf;
147
148 return ti;
149 }
150
151 /* Recursively delete a subtree */
delete_tree(struct fd_list * senti)152 static void delete_tree(struct fd_list * senti)
153 {
154 while (!FD_IS_LIST_EMPTY(senti)) {
155 struct tree_item * ti = (struct tree_item *)(senti->next);
156
157 /* Delete recursively its children first */
158 delete_tree(&ti->children);
159
160 /* Now, unlink from the sentinel list */
161 fd_list_unlink(&ti->chain);
162
163 /* destroy this tree item */
164 free(ti->str);
165 free(ti);
166 }
167 }
168
169 /* Top-level destroy function */
aw_tree_destroy(void)170 void aw_tree_destroy(void)
171 {
172 delete_tree(&tree_root);
173 }
174
175 /* Display the content of a subtree */
tree_dump(struct fd_list * sub,int indent)176 static void tree_dump(struct fd_list * sub, int indent)
177 {
178 struct fd_list * li;
179 for (li = sub->next; li != sub; li = li->next) {
180 struct tree_item * ti = (struct tree_item *)li;
181 char buf[1024];
182 snprintf(buf, sizeof(buf), "%*s%s", indent * 2, "", ti->str?:"*");
183 if (ti->leaf)
184 snprintf(buf+strlen(buf), sizeof(buf)-strlen(buf), " (flag:%x)", ti->flags);
185 fd_log_debug("%s", buf);
186 tree_dump(&ti->children, indent + 1);
187 }
188 }
189
190 /* Top-level function */
aw_tree_dump(void)191 void aw_tree_dump(void)
192 {
193 fd_log_debug("[acl_wl] tree dump:");
194 fd_log_debug("(root)");
195 tree_dump(&tree_root, 1);
196 fd_log_debug("[acl_wl] end of dump");
197 }
198
199 /* Function to add a new entry in the tree */
aw_tree_add(char * name,int flags)200 int aw_tree_add(char * name, int flags)
201 {
202 struct split_name sn;
203 struct tree_item * ti;
204 struct fd_list * li, *senti;
205 int lbl, found;
206
207 TRACE_ENTRY("%p %x", name, flags);
208 CHECK_PARAMS(name && *name);
209
210 CHECK_FCT_DO( parse_name(name, &sn),
211 {
212 fd_log_debug("The name '%s' contains too many labels, try a generic (*) or recompile with bigger AW_TREE_MAXDEPTH value (cur: %d)", name, AW_TREE_MAXDEPTH);
213 return EINVAL;
214 } );
215
216 senti = &tree_root;
217
218 for (lbl = sn.last_lbl; lbl > 0; lbl--) {
219 /* Check if the list is empty, we can directly create the new entry */
220 if (FD_IS_LIST_EMPTY(senti)) {
221 CHECK_MALLOC( ti = new_ti(sn.label[lbl].str, sn.label[lbl].len, 0, 0 /* flags are only set in the terminals */) );
222 /* Insert this label in the sentinel sublist */
223 fd_list_insert_after(senti, &ti->chain);
224 /* Update the sentinel */
225 senti = &ti->children;
226 /* loop to the next label */
227 continue;
228 }
229
230 /* Check if we have a '*' element already that overlapses */
231 ti = (struct tree_item *)(senti->next);
232 if (ti->str == NULL) {
233 fd_log_debug("[acl_wl] Warning: entry '%s' is superseeded by a generic entry at label %d, ignoring.", name, lbl + 1);
234 return 0;
235 }
236
237 /* Search this label in the ordered list */
238 found = 0;
239 for (li = senti->next; li != senti; li=li->next) {
240 int cmp, len;
241 ti = (struct tree_item *)li;
242
243 cmp = strncasecmp(ti->str, sn.label[lbl].str, sn.label[lbl].len);
244 if (cmp > 0)
245 break; /* the new label must be inserted before li */
246 if (cmp < 0)
247 continue;
248
249 /* Check the lengths */
250 len = strlen(ti->str);
251 if (len > sn.label[lbl].len)
252 break; /* the new label must be inserted before li */
253 if (len < sn.label[lbl].len)
254 continue;
255
256 /* We already had this label */
257 found = 1;
258 senti = &ti->children;
259 break;
260 }
261
262 if (found)
263 continue;
264
265 /* Otherwise, we have to create a new ti, and add it before li */
266 CHECK_MALLOC( ti = new_ti(sn.label[lbl].str, sn.label[lbl].len, 0, 0 /* flags are only set in the terminals */) );
267 /* Insert this label in the sentinel sublist */
268 fd_list_insert_before(li, &ti->chain);
269 /* Update the sentinel */
270 senti = &ti->children;
271 }
272
273 ti = NULL;
274 li = senti;
275
276 /* At this point, senti points to the list where we are supposed to insert our last label. */
277 if (sn.label[0].str[0] == '*') {
278 if (!FD_IS_LIST_EMPTY(senti)) {
279 fd_log_debug("[acl_wl] Warning: entry '%s' overwrites previous more detailed entries, these are deleted.", name);
280 delete_tree(senti);
281 }
282
283 /* Create the new entry */
284 CHECK_MALLOC( ti = new_ti(NULL, 0, flags, 1) );
285 } else {
286 if (!FD_IS_LIST_EMPTY(senti)) {
287 /* Check we don't have a '*' entry already */
288 ti = (struct tree_item *)(senti->next);
289 if (ti->str == NULL) {
290 fd_log_debug("[acl_wl] Warning: entry '%s' is superseeded by a generic entry at label 1, ignoring.", name);
291 return 0;
292 }
293
294 /* Search the place for the new label */
295 for (li = senti->next; li != senti; li=li->next) {
296 int cmp, len;
297 ti = (struct tree_item *)li;
298
299 cmp = strncasecmp(ti->str, sn.label[0].str, sn.label[0].len);
300 if (cmp > 0)
301 break; /* the new label must be inserted before li */
302 if (cmp < 0)
303 continue;
304
305 /* Check the lengths */
306 len = strlen(ti->str);
307 if (len > sn.label[0].len)
308 break; /* the new label must be inserted before li */
309 if (len < sn.label[0].len)
310 continue;
311
312 /* We already had this label */
313 if (ti->leaf) {
314 fd_log_debug("[acl_wl] Warning: entry '%s' is duplicated, merging the flags.", name);
315 ti->flags |= flags;
316 return 0;
317 } else {
318 /* Just mark this entry as a valid leaf also */
319 ti->leaf = 1;
320 ti->flags = flags;
321 return 0;
322 }
323 }
324 }
325
326 /* Create the new entry */
327 CHECK_MALLOC( ti = new_ti(sn.label[0].str, sn.label[0].len, flags, 1) );
328 }
329
330 /* The new label is "ti", it is inserted before "li" */
331 fd_list_insert_before(li, &ti->chain);
332
333 /* Done! */
334 return 0;
335 }
336
337 /* Search in the tree. On return, *result = -1: not found; >=0: found with PI_SEC_* flags */
aw_tree_lookup(char * name,int * result)338 int aw_tree_lookup(char * name, int * result)
339 {
340 struct split_name sn;
341 int lbl, found;
342 struct tree_item * ti = NULL;
343 struct fd_list * senti, *li;
344
345 TRACE_ENTRY("%p %p", name, result);
346 CHECK_PARAMS(name && result);
347
348 /* Initialize */
349 *result = -1;
350
351 /* Parse the name into labels */
352 CHECK_FCT_DO( parse_name(name, &sn),
353 {
354 TRACE_DEBUG(INFO, "Too many labels in this name, it cannot be found in the tree, skipping.");
355 return 0;
356 } );
357
358 senti = &tree_root;
359
360 for (lbl = sn.last_lbl; lbl >= 0; lbl--) {
361 /* Check if the list is empty, we can directly return */
362 if (FD_IS_LIST_EMPTY(senti)) {
363 /* The item is not found */
364 return 0;
365 }
366
367 /* Check if we have a '*' element */
368 ti = (struct tree_item *)(senti->next);
369 if (ti->str == NULL) {
370 TRACE_DEBUG(ANNOYING, "[acl_wl] %s matched at label %d with a generic entry.", name, lbl + 1);
371 *result = ti->flags;
372 return 0;
373 }
374
375 /* Search this label in the ordered list */
376 found = 0;
377 for (li = senti->next; li != senti; li=li->next) {
378 int cmp, len;
379 ti = (struct tree_item *)li;
380
381 cmp = strncasecmp(ti->str, sn.label[lbl].str, sn.label[lbl].len);
382 if (cmp > 0)
383 return 0; /* the label was not found */
384 if (cmp < 0)
385 continue;
386
387 /* Check the lengths */
388 len = strlen(ti->str);
389 if (len > sn.label[lbl].len)
390 return 0; /* the label was not found */
391 if (len < sn.label[lbl].len)
392 continue;
393
394 /* We found the label */
395 found = 1;
396 senti = &ti->children;
397 break;
398 }
399
400 if (!found)
401 return 0; /* label not found */
402
403 /* otherwise, continue, sentinel has been updated */
404 }
405
406 /* At the end, ti points to the correct leaf */
407 if (!ti->leaf)
408 return 0;
409
410 TRACE_DEBUG(ANNOYING, "[acl_wl] %s matched exactly.", name);
411 *result = ti->flags;
412 return 0;
413 }
414