快速比较 IP 地址的最聪明方法？

Question

我有一个 IP 地址列表，存储方式如下：

char IP_addresses_list[] = {
    "157.55.130", /* 157.55.130.0/24 */
    "157.56.52",  /* 157.56.52.0/24 */
    "157.12.53",  /* 157.12.53.0/24 */
    ...
};

我从嗅探数据包中获取 IP 地址（将其转换为 struct iphdr *iph = (struct iphdr *)(packet + sizeof(struct ether_header)); 我使用 inet_ntop 将其转换为字符串；最后，我将数据包中的 IP 地址与数据包中的 IP 地址进行比较在具有以下代码的列表中：

/* 
* input: IP address to search in the list
* output: 1 if IP address is found in the list, 0 otherwise
*/
int find_IP_addr(char *server) {
    int ret = 0;
    int i, string_size1, string_size2;
    char *copied_server, *copied_const_char;
    char *save_ptr1, *save_ptr2;
    char dot[2] = ".";
    /* Here I store the IP address from the packet */
    char first_IPaddr_pkt[4], second_IPaddr_pkt[4], third_IPaddr_pkt[4];
    /* Here I store the IP address from the list */
    char first_IPaddr_list[4], second_IPaddr_list[4], third_IPaddr_list[4];

    string_size1 = strlen(server)+1;
    copied_server = (char *)malloc(string_size1 * sizeof(char));
    strcpy(copied_server, server);

    /* I store and compare the first three bits of the IP address */
    strcpy(first_IPaddr_pkt, strtok_r(copied_server, dot, &save_ptr1));
    strcpy(second_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1));
    strcpy(third_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1));  
    printf("tokenized %s, %s and %s\n", first_IPaddr_pkt, second_IPaddr_pkt, third_IPaddr_pkt);

    /* Now I scan the list */
    for (i=0; i<LIST_LENGTH; i++) {
        /* I copy an address from the list */
        string_size2 = strlen(IP_addresses_list[i])+1; // +1 for null character
        copied_const_char = (char *)malloc(string_size2 * sizeof(char));
        strcpy(copied_const_char, IP_addresses_list[i]);
        /* Let's split the address from the list */
        strcpy(first_IPaddr_list, strtok_r(copied_const_char, dot, &save_ptr2));
        strcpy(second_IPaddr_list, strtok_r(NULL, dot, &save_ptr2));
        strcpy(third_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
        printf("tokenized %s, %s and %s\n", first_IPaddr_list, second_IPaddr_list, third_IPaddr_list);
        /* I compare the first byte of the address from the packet I got and 
        the first byte of the address from the list:
        if they are different, there's no reason to continue comparing 
        the other bytes of the addresses */
        if (strcmp(first_IPaddr_pkt, first_IPaddr_list) != 0) {
            continue;
        }
        else  {
            if (strcmp(second_IPaddr_pkt, second_IPaddr_list) != 0) {
                continue;
        }
        else {
            if (strcmp(third_IPaddr_pkt, third_IPaddr_list) != 0) {
                continue;
            }
            else
                /* All the bytes are the same! */
                ret = 1;
            }
        }
        free(copied_const_char);
    }
    free(copied_server);
    return ret;
}

我想让它更快，而不使用 strtok、strcmp、malloc 或 free。在 /usr/include/netinet/ip.h 中，我看到地址是

u_int32_t saddr;
u_int32_t daddr;

是否可以在不先使用 inet_ntop 的情况下进行比较，也许只是比较两个地址，而它们仍然是 u_int32_t？

编辑：这是一个解决方案示例，供阅读此问题的人使用。

#include <stdio.h>
#include <sys/types.h>

int main() {

    // In the list I have: 104.40.0.0./13
    int cidr = 13;
    u_int32_t ipaddr_from_pkt = 1747488105;     // pkt coming from 104.40.141.105
    u_int32_t ipaddr_from_list = 1747451904;    // 104.40.0.0
    int mask = (-1) << (32 - cidr);

    if ((ipaddr_from_pkt & mask) == ipaddr_from_list)
        printf("IP address belongs to the given range!!!\n");
    else printf ("failure\n");

    return 0;
}

也感谢 iharob 的 bsearch 提示。

Answer 1

性能问题与strcmp()无关，但malloc()是不必要的。

如果你只使用 IPv4 地址，你只需要 16 个字符来存储它，这样你就可以删除 malloc() 并将临时存储声明为数组。

但是如果列表中有很多 IP 地址，则有一个重要的改进。

首先您需要对IP地址列表进行排序，然后使用bsearch()搜索正确的IP。这样代码将运行在 O(log(2n)) 时间内比 O(N) 快很多，专为大型 N

Answer 2

最快的方法是将地址存储在字典中，请参阅 this link

Answer 3

我的方法是：

只需使用 strncat 和 ".0" 即可构建有效的 IPv4 地址。
使用 getaddrinfo 和套接字类型等的常量值来构建 addrinfo 结构
比较addrinfo的相关字段。

基本上，来自 man getaddrinfo does all this 的示例。

Answer 4

我会避免将二进制数据转换为字符串。如果你把它们保存为二进制，那么比较起来就很容易了：

match = (ip & listed_mask) == listed_ip;

"/24" 是掩码。意味着只有 24 个最高位是相关的。您将其转换为二进制掩码，如下所示：

listed_mask = (-1) << (32 - 24);

快速比较 IP 地址的最聪明方法？

Smartest way to compare IP addresses quickly?

c

linux

ip

networking

libpcap