tire 做域名白名单-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心

苦海澜石

凯发app官方网站首页　| 　博文目录　| 　关于我

khls27

  • 博客访问： 752876
  • 博文数量： 144
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1150
  • 用 户 组： 普通用户
  • 注册时间： 2014-03-17 14:32
个人简介

小公司研发总监，既当司令也当兵！

文章分类

全部博文（144）

推荐博文
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
tire 做域名白名单

分类： linux

2018-10-02 00:00:47

背景

在路由器上，需要做一个域名分流功能：系统配置有两个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；

  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;

  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>

  7. #define debug 1

  9. #undef u8
  10. typedef unsigned char u8;

  12. #define idx_val_dot 37
  13. #define idx_val_hypline 38
  14. #define idx_val_flags 39

  16. #define domain_tail_mask 0x01

  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;

  32. #define is_domain_tail(flag) ((flag) & domain_tail_mask)

  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;

  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;

  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.         }

  63.         if (ndidx)
  64.         {
  65.             pnd = pnd->pnodes[ndidx - 1];

  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. }

  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;

  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.             }

  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. }

  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. }

  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.         }

  195.         url[len - 1 - cursor] = ch;
  196.         cursor;
  197.     }
  198.     url[len] = 0;
  199.     return 0;
  200. }

  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);

  224.         trie_url_add(trie, (const u8*)idx,len);
  225.     }    
  226. }

  228. trie_t* urltrie_new()
  229. {
  230.     trie_t *trie;

  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. }

  241. int urltrie_find(trie_t *trie, u8 *url)
  242. {
  243.     u8 idx[128]= {0};
  244.     int len = 0;

  246.     if (null == trie || null == url)
  247.         return 0;

  249.     len = url2idx(url, idx);
  250.     if (len <= 0)
  251.         return 0;
  252.     return trie_urlidx_find(trie, idx, len);
  253. }

  255. int urltrie_add(trie_t *trie, u8 *url)
  256. {
  257.     u8 idx[128]= {0};
  258.     int len = 0;

  260.     if (null == trie || null == url)
  261.         return 0;

  263.     len = url2idx(url, idx);
  264.     if (len <= 0)
  265.         return -1;

  267.     return trie_url_add(trie, idx, len);
  268. }


  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.     }

  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;

  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. }

  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");

  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);

  352.     printf("load time: %ld(us)\n", tv2.tv_usec - tv1.tv_usec);
  353.     debug_print_trie(trie);

  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. }

  361. #endif


  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中数据可以节省0左右）；
2， 上面的代码可以避免完全重复的域名添加，但是没有检出域名级数包含。当然简化处理是外部先处理原数据，剔除重复包含关系的数据。

阅读(6188) | 评论(0) | 转发(0) |
0

上一篇：lua 元祖方法之：__index

下一篇：dns报文解析

给主人留下些什么吧！~~
| | | | |

凯发app官方网站 copyright 2001-2010 chinaunix.net all rights reserved 北京皓辰网域网络信息技术有限公司. 凯发k8官网下载客户端中心的版权所有

感谢所有关心和支持过chinaunix的朋友们
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图