tire 做域名白名单

背景

在路由器上，需要做一个域名分流功能：系统配置有两个DNS server，通过配置一个白名单，让白名单内的域名走 DNS server 1, 其余的的dns解析走DNS server 2。

最初想到的方案是，通过dnsmasq配置来完成。dnsmaq实际上是支持一种配置方式就指定某个域名用指定的dns来解析。但，要一条一条的配置，稍显繁琐；而且dnsmaq这种配置方式暗示，很大可能未对大量的这样的配置做优化，很可能是逐条匹配，那么性能估计难达要求（笔者赖，没有去验证这个事实），而且小设备上cpu资源很紧张，所以不太想在dnsmasq上去纠缠。

另一个方案，就是实现一个类似ipset 的 iptables模块，通过内核匹配直接指定目标server：

点击(此处)折叠或打开

1. iptables -t nat -p udp -m udp --dport 53 -m domainset --set-name "srv2" -j DNAT --to-destionation [srvip:53]

至于domainset这个模块，netfilter框架有很好的支持，照猫画虎即可。问题在于这个模块在内核的数据路径上（虽然只包括dns的请求路径），对于性能要求比较高，而且需要兼顾cpu和内存资源。于是并有了本主题的验证：
 
小设备上（cpu 800Mhz，单核或双核，内存64M 或128M）如何快速高效的匹配10000数量级的域名白名单？

通过简单验证，排除了hash， hash 链表等算法，选择了trie。
原因：
1， 该项目中，白名单是事先准备好的，设备运行过程中变动很小，而且基本上只加不删；
2，由于数量不是很大，trie对内存的消耗基本可以接受；
3，trie查询相比hash，对cpu消耗极低，而且查询效率比hash高。

实现和验证

首先定义数据结构：
由于域名中包含的字母 0-9，a-z，A-Z, '.', '-', 由于域名是不区分大小写的，那么把‘a-z’与‘A-Z’合并；即有效字母共26+10+2=38个。
于是不难定义节点结构体为：

点击(此处)折叠或打开

1. struct trie_node {
   
2.         char key；
   
3. 
   
4.          struct trie_node* psub[38];
   
5. }

按该结构体，我用5660个url测试，得出节点数目为38664， 总内存消耗6031584（约6Mb）。这个内存消耗确实有点超出预期。必须优化了。

在上诉结构体中，每个字母的下一级包含了所有可能（这样做是为了高速的查询）；但实际上可以预期，这部分有巨大的浪费。但如果psub不使用静态数组，而使用链表的话，需要遍历，那么查询速度会大打折扣。

一个折中的办法是，psub采用动态数组，记录当前节点实际有效的子节点信息；额为维护一个索引，用于快速索引当前节点。

点击(此处)折叠或打开

1. struct trie_node{
   
2.          char key;
   
3.          unsigned char count;
4.          unsigned char index[39]; // start from 1
   
5.          struct trie_node **psub;
   
6. 
   
7. }

比如域名中字母‘w’，map对应的索引序号是33，那么在节点记录中index[33]就记录了当前节点的子节点‘w’ 在psub数组中的位置。

由于index记录了字母信息，所以成员key可以省去。
另外，由于需求要求域名可以支持顶层域名泛型配置（比如，配置了abc.com为白名单，那么YYY.XXX.abc.com都与其匹配）。为此，我们在存储时，采用倒置存储，moc.cba, 与 moc.cba.*匹配。
但有种情况是，配置了moc.cba， 但搜索moc.cbaXYZ，这二者存在交叠，但又不是域名级数包含关系，实际上二者不能匹配。于是，我们需要在搜索路径上，标明moc.cbaXYZ这个路径上，‘a’到达一次完结点，‘Z’到达一次完结点。因此需要增加一个成员来记录该信息。

点击(此处)折叠或打开

1. struct trie_node {
   
2.         unsigned char count;
   
3.         unsigned char index[39];
   
4.         unsigned char flag;
   
5.         struct trie_node **psub;
   
6. }

最终

点击(此处)折叠或打开

1. struct URL_TRIE_NODE {
   
2.     /*
   
3.     * udata[0], for counter
   
4.     * udata[1-10], for index ??0-9??in @pnodes
   
5.     * udata[11-36], for index 'a-z' in @pnodes
   
6.     * udata[37], for index '.' in @pnodes        
   
7.     * udata[38], for index '-' in @pnodes
   
8.     * udata[39], flags
   
9.     */
   
10.     u8 udata[40];
    
11.     struct URL_TRIE_NODE **pnodes;
    
12. };
    
13. typedef struct URL_TRIE_NODE node_t;

附完整demo代码：

点击(此处)折叠或打开

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <sys/time.h>
   
5. #include <unistd.h>
   
6. 
   
7. #define DEBUG 1
   
8. 
   
9. #undef u8
   
10. typedef unsigned char u8;
    
11. 
    
12. #define IDX_VAL_DOT 37
    
13. #define IDX_VAL_HYPLINE 38
    
14. #define IDX_VAL_FLAGS 39
    
15. 
    
16. #define DOMAIN_TAIL_MASK 0x01
    
17. 
    
18. struct URL_TRIE_NODE {
    
19.     /*
    
20.     * udata[0], for counter
    
21.     * udata[1-10], for index ??0-9??in @pnodes
    
22.     * udata[11-36], for index 'a-z' in @pnodes
    
23.     * udata[37], for index '.' in @pnodes        
    
24.     * udata[38], for index '-' in @pnodes
    
25.     * udata[39], flags
    
26.     */
    
27.     u8 udata[40];
    
28.     struct URL_TRIE_NODE **pnodes;
    
29. };
    
30. typedef struct URL_TRIE_NODE node_t;
    
31. 
    
32. #define IS_DOMAIN_TAIL(flag) ((flag) & DOMAIN_TAIL_MASK)
    
33. 
    
34. struct URL_TRIE {
    
35.     unsigned int ndnum;
    
36.     unsigned int urlnum;
    
37.     unsigned int size;
    
38.     node_t root;
    
39. };
    
40. typedef struct URL_TRIE trie_t;
    
41. 
    
42. static int trie_urlidx_find(trie_t *trie, const u8 *urlidx, int len)
    
43. {
    
44.     node_t *pnd = &trie->root;
    
45.     int cursor = 0;
    
46. 
    
47.     while (pnd && (cursor < len))
    
48.     {
    
49.         int ndidx = pnd->udata[urlidx[cursor]];
    
50.         
    
51.         if (IS_DOMAIN_TAIL(pnd->udata[IDX_VAL_FLAGS]))
    
52.         {
    
53.             /*
    
54.             * domain top level overlap
    
55.             * recorder: abc.com match rul<XXX.abc.com>
    
56.             */
    
57.             if (urlidx[cursor] == IDX_VAL_DOT)
    
58.             {
    
59.                 return 1;
    
60.             }
    
61.         }
    
62. 
    
63.         if (ndidx)
    
64.         {
    
65.             pnd = pnd->pnodes[ndidx - 1];
    
66. 
    
67.             // common mathed
    
68.             if (cursor == len - 1 && IS_DOMAIN_TAIL(pnd->udata[IDX_VAL_FLAGS]))
    
69.             {
    
70.                 return 1;
    
71.             }
    
72.             cursor ++;
    
73.         }
    
74.         else
    
75.         {
    
76.             break;
    
77.         }
    
78.     
    
79.     }
    
80.     return 0;
    
81. }
    
82. 
    
83. static int trie_url_add(trie_t *trie, const u8 *urlidx, int len)
    
84. {
    
85.     node_t* pnd = &trie->root;
    
86.     int cursor = 0;
    
87. 
    
88.     while (cursor < len)
    
89.     {
    
90.         int ndidx = pnd->udata[urlidx[cursor]]; // start from 1
    
91.         if (ndidx)
    
92.         {
    
93.             pnd = pnd->pnodes[ndidx - 1];
    
94.             cursor++;
    
95.         }
    
96.         else
    
97.         {
    
98.             node_t **old = pnd->pnodes;
    
99.             node_t **pnnd;
    
100.             node_t *nd = NULL;
     
101.             
     
102.             pnnd = (node_t**)malloc(sizeof(node_t *) * (pnd->udata[0] + 1));
     
103.             if (!pnnd)
     
104.             {
     
105.                 printf("malloc for new nodes for(%p) error\n", pnd);
     
106.                 return -1;
     
107.             }
     
108.             nd = (node_t*)malloc(sizeof(node_t));
     
109.             if (!nd)
     
110.             {
     
111.                 printf("malloc new node fail\n");
     
112.                 free(pnnd);
     
113.                 return -1;
     
114.             }
     
115.             memset(nd, 0, sizeof(node_t));
     
116.             if (pnd->udata[0])
     
117.             {
     
118.                 memcpy(pnnd, old, sizeof(node_t*) * pnd->udata[0]);
     
119.                 free(old);
     
120.             }
     
121. 
     
122.             pnd->pnodes= pnnd;
     
123.             pnd->pnodes[pnd->udata[0]++] = nd;
     
124.             pnd->udata[urlidx[cursor]] = pnd->udata[0];
     
125.             trie->ndnum++;
     
126.             trie->size += sizeof(node_t) + sizeof(node_t*);
     
127.             pnd = nd;
     
128.             cursor++;
     
129.         }
     
130.     }
     
131.     pnd->udata[IDX_VAL_FLAGS] |= DOMAIN_TAIL_MASK; // add end flag
     
132.     trie->urlnum++;
     
133.     return 0;
     
134. }
     
135. 
     
136. static int url2idx(const u8 *url, u8* index)
     
137. {
     
138.     int len = strlen(url);
     
139.     int cursor = 0;
     
140.     
     
141.     while( cursor < len)
     
142.     {
     
143.         int idx = 0;
     
144.         if (url[cursor] == '.')
     
145.         {
     
146.             idx = IDX_VAL_DOT;
     
147.         }
     
148.         else if (url[cursor] == '-')
     
149.         {
     
150.             idx = IDX_VAL_HYPLINE;
     
151.         }
     
152.         else if (url[cursor] >= '0' && url[cursor] <= '9')
     
153.         {
     
154.             idx = 1 + (url[cursor] - '0');
     
155.         }
     
156.         else if (url[cursor] >= 'a' & url[cursor] <= 'z')
     
157.         {
     
158.             idx = 11 + (url[cursor] - 'a');
     
159.         }
     
160.         else if (url[cursor] >= 'A' & url[cursor] <= 'Z')
     
161.         {
     
162.             idx = 11 + (url[cursor] - 'A');
     
163.         }
     
164.         else
     
165.         {
     
166.             printf("bad url:%s, bad key:%c\n", url, url[cursor]);
     
167.             return 0;
     
168.         }
     
169.         index[len -1 -cursor] = idx;
     
170.         cursor++;
     
171.     }
     
172.     return len;
     
173. }
     
174. 
     
175. static int idx2url(u8 *index, int len, u8 *url)
     
176. {
     
177.     int cursor = 0;
     
178.     while (cursor < len)
     
179.     {
     
180.         u8 ch = 0;
     
181.         if (index[cursor] == IDX_VAL_DOT )
     
182.             ch = '.';
     
183.         else if (index[cursor] == IDX_VAL_HYPLINE )
     
184.             ch = '-';
     
185.         else if (index[cursor] >= 1 && index[cursor] <= 10)
     
186.             ch = '0' + (index[cursor] -1);
     
187.         else if (index[cursor] >= 11 && index[cursor] <= 36)
     
188.             ch = 'a' + (index[cursor]- 11);
     
189.         else
     
190.         {
     
191.             printf("fail to map %d\n", index[cursor]);
     
192.             return -1;
     
193.         }
     
194. 
     
195.         url[len - 1 - cursor] = ch;
     
196.         cursor++;
     
197.     }
     
198.     url[len] = 0;
     
199.     return 0;
     
200. }
     
201. 
     
202. int URLTRIE_loadfile(trie_t *trie, char *path)
     
203. {
     
204.     char buf[130] = {0};
     
205.     FILE *pFile;
     
206.     char data[100] = {0};
     
207.     
     
208.     pFile =fopen(path, "r");
     
209.     if (NULL == pFile )
     
210.     {
     
211.         printf("can't open %s\n", path);
     
212.         return -1;
     
213.     }
     
214.     while (( fgets(data, 128, pFile) != NULL))
     
215.     {
     
216.         int len = strlen(data);
     
217.         u8 idx[128] = {0};
     
218.         if (data[len -1] == '\n')
     
219.         {
     
220.             data[len - 1] = 0;
     
221.         }
     
222.         len = url2idx(data, idx);
     
223. 
     
224.         trie_url_add(trie, (const u8*)idx,len);
     
225.     }    
     
226. }
     
227. 
     
228. trie_t* URLTRIE_new()
     
229. {
     
230.     trie_t *trie;
     
231. 
     
232.     trie = (trie_t *)malloc(sizeof(trie_t));
     
233.     if (trie)
     
234.     {
     
235.         memset(trie, 0, sizeof(trie_t));
     
236.         return trie;
     
237.     }
     
238.     return NULL;
     
239. }
     
240. 
     
241. int URLTRIE_find(trie_t *trie, u8 *url)
     
242. {
     
243.     u8 idx[128]= {0};
     
244.     int len = 0;
     
245. 
     
246.     if (NULL == trie || NULL == url)
     
247.         return 0;
     
248. 
     
249.     len = url2idx(url, idx);
     
250.     if (len <= 0)
     
251.         return 0;
     
252.     return trie_urlidx_find(trie, idx, len);
     
253. }
     
254. 
     
255. int URLTRIE_add(trie_t *trie, u8 *url)
     
256. {
     
257.     u8 idx[128]= {0};
     
258.     int len = 0;
     
259. 
     
260.     if (NULL == trie || NULL == url)
     
261.         return 0;
     
262. 
     
263.     len = url2idx(url, idx);
     
264.     if (len <= 0)
     
265.         return -1;
     
266. 
     
267.     return trie_url_add(trie, idx, len);
     
268. }
     
269. 
     
270. 
     
271. #if DEBUG
     
272. static void debug_print_trie_url(u8* index, int len)
     
273. {
     
274.     u8 curl[128] = {0};
     
275.     idx2url(index, len, curl);
     
276.     printf("%s\n", curl);
     
277.     
     
278. }
     
279. static void debug_print_trie_path(node_t *pnd, u8* stack, int *head)
     
280. {
     
281.     int i;
     
282.     if (pnd->udata[39] & 0x01)
     
283.     {
     
284.         debug_print_trie_url(stack, *head);
     
285.     }
     
286. 
     
287.     for (i = 1; i <= 38; i++)
     
288.     {
     
289.         if (pnd->udata[i])
     
290.         {
     
291.             stack[(*head)++] = i;
     
292.             debug_print_trie_path(pnd->pnodes[pnd->udata[i] -1], stack, head);
     
293.             stack[(*head)--] = 0;
     
294.         }
     
295.     }
     
296. }
     
297. static void debug_print_trie(trie_t *trie)
     
298. {
     
299.     u8 stack[128] = {0};
     
300.     int head= 0;
     
301.     node_t *pnd = &trie->root;
     
302. 
     
303.     printf("trie:%p, rul number: %u, node number:%u, size:%u\n", trie, trie->urlnum, trie->ndnum, trie->size);
     
304.     //debug_print_trie_path(pnd, stack, &head);
     
305. }
     
306. 
     
307. static void debug_search_file(trie_t *trie, u8 *path)
     
308. {
     
309.     char buf[130] = {0};
     
310.     FILE *pFile;
     
311.     char data[100] = {0};
     
312.     
     
313.     unsigned int total = 0;
     
314.     unsigned int matched = 0;
     
315.     
     
316.     pFile =fopen(path, "r");
     
317. 
     
318.     if (NULL == pFile )
     
319.     {
     
320.         printf("can't open %s\n", path);
     
321.         return ;
     
322.     }
     
323.     while (( fgets(data, 128, pFile) != NULL))
     
324.     {
     
325.         int len = strlen(data);
     
326.         u8 idx[128] = {0};
     
327.         if (data[len -1] == '\n')
     
328.         {
     
329.             data[len - 1] = 0;
     
330.         }
     
331.         total++;
     
332.         if (URLTRIE_find(trie, data))
     
333.             matched++;
     
334.     }
     
335.     printf("search %s, total :%u, matched:%u\n", path, total, matched);
     
336. }
     
337. static void debug_test()
     
338. {
     
339.     trie_t *trie = URLTRIE_new();
     
340.     struct timeval tv1;
     
341.     struct timeval tv2;
     
342.     
     
343.     if (NULL == trie)
     
344.     {
     
345.         printf("new trie fail\n");
     
346.         return;
     
347.     }
     
348.     gettimeofday(&tv1, NULL);
     
349.     URLTRIE_loadfile(trie, "domain.dat");
     
350.     gettimeofday(&tv2, NULL);
     
351. 
     
352.     printf("load time: %ld(us)\n", tv2.tv_usec - tv1.tv_usec);
     
353.     debug_print_trie(trie);
     
354. 
     
355.     gettimeofday(&tv1, NULL);
     
356.     debug_search_file(trie, "domain.dat");
     
357.     gettimeofday(&tv2, NULL);
     
358.     printf("search time: %ld(us)\n", tv2.tv_usec - tv1.tv_usec);
     
359. }
     
360. 
     
361. #endif
     
362. 
     
363. 
     
364. int main(int argc, char **argv)
     
365. {
     
366.     #if DEBUG
     
367.         debug_test();
     
368.     #endif
     
369.     return 0;
     
370. }

最终测试结果：
load time: 26534(us)
trie:0x2101010, rul number: 5660, node number:38664, size:1855872
search domain.dat, total :5660, matched:5660
search time: 7816(us)

测试域名资源文件
domain.txt

后续优化：
1， 域名中www开头的很多，如果把www压缩后可以省不少空间（domain.txt中数据可以节省%30左右）；
2， 上面的代码可以避免完全重复的域名添加，但是没有检出域名级数包含。当然简化处理是外部先处理原数据，剔除重复包含关系的数据。