Blame apache2/msc_tree.c

Packit Service 384592
/*
Packit Service 384592
 * ModSecurity for Apache 2.x, http://www.modsecurity.org/
Packit Service 384592
 * Copyright (c) 2004-2013 Trustwave Holdings, Inc. (http://www.trustwave.com/)
Packit Service 384592
 *
Packit Service 384592
 * You may not use this file except in compliance with
Packit Service 384592
 * the License.  You may obtain a copy of the License at
Packit Service 384592
 *
Packit Service 384592
 *     http://www.apache.org/licenses/LICENSE-2.0
Packit Service 384592
 *
Packit Service 384592
 * If any of the files related to licensing are missing or if you have any
Packit Service 384592
 * other questions related to licensing please contact Trustwave Holdings, Inc.
Packit Service 384592
 * directly using the email address security@modsecurity.org.
Packit Service 384592
 */
Packit Service 384592
Packit Service 384592
#include <stdio.h>
Packit Service 384592
#include <stdlib.h>
Packit Service 384592
#if APR_HAVE_STDINT_H
Packit Service 384592
#include <stdint.h>
Packit Service 384592
#endif
Packit Service 384592
#include <string.h>
Packit Service 384592
#if APR_HAVE_NETINET_IN_H
Packit Service 384592
#include <netinet/in.h>
Packit Service 384592
#endif
Packit Service 384592
#if APR_HAVE_ARPA_INET_H
Packit Service 384592
#include <arpa/inet.h>
Packit Service 384592
#endif
Packit Service 384592
#include "apr_lib.h"
Packit Service 384592
#include "msc_util.h"
Packit Service 384592
#include "msc_tree.h"
Packit Service 384592
Packit Service 384592
CPTTree *CPTCreateRadixTree(apr_pool_t *pool)   {
Packit Service 384592
    CPTTree *tree = NULL;
Packit Service 384592
Packit Service 384592
    tree = apr_palloc(pool, sizeof(CPTTree));
Packit Service 384592
Packit Service 384592
    if(tree == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    memset(tree, 0, sizeof(CPTTree));
Packit Service 384592
    tree->pool = pool;
Packit Service 384592
Packit Service 384592
    return tree;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
void ConvertIPNetmask(unsigned char *buffer, unsigned char netmask, unsigned int ip_bitmask) {
Packit Service 384592
    int aux = 0, bytes = 0;
Packit Service 384592
    int mask = 0, mask_bit = 0;
Packit Service 384592
Packit Service 384592
    bytes = ip_bitmask/8;
Packit Service 384592
Packit Service 384592
    while(aux < bytes)    {
Packit Service 384592
        mask_bit  = ((1+aux) * 8);
Packit Service 384592
Packit Service 384592
        if (mask_bit > netmask) {
Packit Service 384592
            mask = 0;
Packit Service 384592
            if ((mask_bit - netmask) < 8)   mask = SHIFT_LEFT_MASK(mask_bit - netmask);
Packit Service 384592
        }   else    {
Packit Service 384592
            mask = -1;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        buffer[aux] &= mask;
Packit Service 384592
        aux++;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTCreateNode(apr_pool_t *pool)   {
Packit Service 384592
    TreeNode *node = NULL;
Packit Service 384592
Packit Service 384592
    node = apr_palloc(pool, sizeof(TreeNode));
Packit Service 384592
Packit Service 384592
    if(node == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    memset(node, 0, sizeof(TreeNode));
Packit Service 384592
    return node;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
CPTData *CPTCreateCPTData(unsigned char netmask, apr_pool_t *pool) {
Packit Service 384592
Packit Service 384592
    CPTData *prefix_data = apr_palloc(pool, sizeof(CPTData));
Packit Service 384592
Packit Service 384592
    if (prefix_data == NULL) {
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    memset(prefix_data, 0, sizeof(CPTData));
Packit Service 384592
Packit Service 384592
    prefix_data->netmask = netmask;
Packit Service 384592
Packit Service 384592
    return prefix_data;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreePrefix *InsertDataPrefix(TreePrefix *prefix, unsigned char *ipdata, unsigned int ip_bitmask,
Packit Service 384592
        unsigned char netmask, apr_pool_t *pool)  {
Packit Service 384592
Packit Service 384592
    if(prefix == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    memcpy(prefix->buffer, ipdata, ip_bitmask/8);
Packit Service 384592
    prefix->bitlen = ip_bitmask;
Packit Service 384592
Packit Service 384592
    prefix->prefix_data = CPTCreateCPTData(netmask, pool);
Packit Service 384592
Packit Service 384592
    if(prefix->prefix_data == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    return prefix;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreePrefix *CPTCreatePrefix(unsigned char *ipdata, unsigned int ip_bitmask,
Packit Service 384592
        unsigned char netmask, apr_pool_t *pool)  {
Packit Service 384592
Packit Service 384592
    TreePrefix *prefix = NULL;
Packit Service 384592
    int bytes = ip_bitmask/8;
Packit Service 384592
Packit Service 384592
    if ((ip_bitmask % 8 != 0) || (ipdata == NULL)) {
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    prefix = apr_palloc(pool, sizeof(TreePrefix));
Packit Service 384592
    if (prefix == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    memset(prefix, 0, sizeof(TreePrefix));
Packit Service 384592
Packit Service 384592
    prefix->buffer = apr_palloc(pool, bytes);
Packit Service 384592
Packit Service 384592
    if(prefix->buffer == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    memset(prefix->buffer, 0, bytes);
Packit Service 384592
Packit Service 384592
    return InsertDataPrefix(prefix, ipdata, ip_bitmask, netmask, pool);
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
void CPTAppendToCPTDataList(CPTData *new, CPTData **list)  {
Packit Service 384592
    CPTData *temp = NULL, *prev = NULL;
Packit Service 384592
Packit Service 384592
    if (new == NULL) {
Packit Service 384592
        return;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (list == NULL) {
Packit Service 384592
        return;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    prev = *list;
Packit Service 384592
    temp = *list;
Packit Service 384592
Packit Service 384592
    while (temp != NULL) {
Packit Service 384592
        if (new->netmask > temp->netmask)
Packit Service 384592
            break;
Packit Service 384592
        prev = temp;
Packit Service 384592
        temp = temp->next;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (temp == *list) {
Packit Service 384592
        new->next = *list;
Packit Service 384592
        *list = new;
Packit Service 384592
    } else {
Packit Service 384592
        new->next = prev->next;
Packit Service 384592
        prev->next = new;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
int TreePrefixContainNetmask(TreePrefix *prefix, unsigned char netmask)   {
Packit Service 384592
    CPTData *prefix_data = NULL;
Packit Service 384592
Packit Service 384592
    if (prefix == NULL) {
Packit Service 384592
        return 0;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    prefix_data = prefix->prefix_data;
Packit Service 384592
Packit Service 384592
    while (prefix_data != NULL) {
Packit Service 384592
        if (prefix_data->netmask == netmask)
Packit Service 384592
            return 1;
Packit Service 384592
        prefix_data = prefix_data->next;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return 0;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
int CheckBitmask(unsigned char netmask, unsigned int ip_bitmask)   {
Packit Service 384592
Packit Service 384592
    switch(netmask) {
Packit Service 384592
Packit Service 384592
        case 0xff:
Packit Service 384592
            return 1;
Packit Service 384592
        case 0x20:
Packit Service 384592
            if(ip_bitmask == 0x20)
Packit Service 384592
                return 1;
Packit Service 384592
            break;
Packit Service 384592
        case 0x80:
Packit Service 384592
            if(ip_bitmask == 0x80)
Packit Service 384592
                return 1;
Packit Service 384592
            break;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return 0;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTCreateHead(TreePrefix *prefix, TreeNode *node, CPTTree *tree, unsigned char netmask, unsigned int ip_bitmask)    {
Packit Service 384592
Packit Service 384592
    if(tree == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    if(prefix == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    if (node != NULL)   {
Packit Service 384592
Packit Service 384592
        node->prefix = prefix;
Packit Service 384592
        node->bit = prefix->bitlen;
Packit Service 384592
        tree->head = node;
Packit Service 384592
Packit Service 384592
        if(CheckBitmask(netmask, ip_bitmask))
Packit Service 384592
            return node;
Packit Service 384592
Packit Service 384592
        node->count++;
Packit Service 384592
        node->netmasks = apr_palloc(tree->pool, (node->count *  sizeof(unsigned char)));
Packit Service 384592
Packit Service 384592
        if(node->netmasks)
Packit Service 384592
            node->netmasks[0] = netmask;
Packit Service 384592
Packit Service 384592
        return node;
Packit Service 384592
Packit Service 384592
    } else {
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return NULL;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *SetParentNode(TreeNode *node, TreeNode *new_node, CPTTree *tree)  {
Packit Service 384592
Packit Service 384592
    if (node->parent == NULL)
Packit Service 384592
        tree->head = new_node;
Packit Service 384592
    else if (node->parent->right == node)
Packit Service 384592
        node->parent->right = new_node;
Packit Service 384592
    else
Packit Service 384592
        node->parent->left = new_node;
Packit Service 384592
Packit Service 384592
    return new_node;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
int InsertNetmask(TreeNode *node, TreeNode *parent, TreeNode *new_node,
Packit Service 384592
        CPTTree *tree, unsigned char netmask, unsigned char bitlen) {
Packit Service 384592
    int i;
Packit Service 384592
Packit Service 384592
    if (netmask != NETMASK_256-1 && netmask != NETMASK_128) {
Packit Service 384592
        if ((netmask != NETMASK_32 || (netmask == NETMASK_32 && bitlen != NETMASK_32))) {
Packit Service 384592
Packit Service 384592
            node = new_node;
Packit Service 384592
            parent = new_node->parent;
Packit Service 384592
Packit Service 384592
            while (parent != NULL && netmask < (parent->bit + 1)) {
Packit Service 384592
                node = parent;
Packit Service 384592
                parent = parent->parent;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            node->count++;
Packit Service 384592
            node->netmasks = apr_palloc(tree->pool, (node->count * sizeof(unsigned char)));
Packit Service 384592
Packit Service 384592
            if(node->netmasks == NULL)
Packit Service 384592
                return 0;
Packit Service 384592
            if ((node->count-1) == 0) {
Packit Service 384592
                node->netmasks[0] = netmask;
Packit Service 384592
                return 1;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            node->netmasks[node->count - 1] = netmask;
Packit Service 384592
Packit Service 384592
            i = node->count - 2;
Packit Service 384592
            while (i >= 0) {
Packit Service 384592
                if (netmask < node->netmasks[i]) {
Packit Service 384592
                    node->netmasks[i + 1] = netmask;
Packit Service 384592
                    break;
Packit Service 384592
                }
Packit Service 384592
Packit Service 384592
                node->netmasks[i + 1] = node->netmasks[i];
Packit Service 384592
                node->netmasks[i] = netmask;
Packit Service 384592
                i--;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return 0;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTAddElement(unsigned char *ipdata, unsigned int ip_bitmask, CPTTree *tree, unsigned char netmask)   {
Packit Service 384592
    unsigned char *buffer = NULL;
Packit Service 384592
    unsigned char bitlen = 0;
Packit Service 384592
    int bit_validation = 0, test_bit = 0;
Packit Service 384592
    int i = 0, j = 0, temp = 0;
Packit Service 384592
    unsigned int x, y;
Packit Service 384592
    TreeNode *node = NULL, *new_node = NULL;
Packit Service 384592
    TreeNode *parent = NULL, *i_node = NULL;
Packit Service 384592
    TreeNode *bottom_node = NULL;
Packit Service 384592
    TreePrefix *prefix = NULL;
Packit Service 384592
Packit Service 384592
    if (tree == NULL) {
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    ConvertIPNetmask(ipdata, netmask, ip_bitmask);
Packit Service 384592
Packit Service 384592
    prefix = CPTCreatePrefix(ipdata, ip_bitmask, netmask, tree->pool);
Packit Service 384592
Packit Service 384592
    if (prefix == NULL) {
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (tree->head == NULL) {
Packit Service 384592
        node = CPTCreateNode(tree->pool);
Packit Service 384592
        return CPTCreateHead(prefix, node, tree, netmask, ip_bitmask);
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    node = tree->head;
Packit Service 384592
    buffer = prefix->buffer;
Packit Service 384592
    bitlen = prefix->bitlen;
Packit Service 384592
Packit Service 384592
    while (node->bit < bitlen || node->prefix == NULL) {
Packit Service 384592
Packit Service 384592
        if (bitlen < node->bit) {
Packit Service 384592
            if (node->right == NULL)
Packit Service 384592
                break;
Packit Service 384592
            else
Packit Service 384592
                node = node->right;
Packit Service 384592
        } else {
Packit Service 384592
            x = SHIFT_RIGHT_MASK(node->bit, 3); y = SHIFT_RIGHT_MASK(NETMASK_128, (node->bit % 8));
Packit Service 384592
Packit Service 384592
            if (TREE_CHECK(buffer[x],y)) {
Packit Service 384592
                if (node->right == NULL)
Packit Service 384592
                    break;
Packit Service 384592
                node = node->right;
Packit Service 384592
            } else {
Packit Service 384592
                if (node->left == NULL)
Packit Service 384592
                    break;
Packit Service 384592
                else
Packit Service 384592
                    node = node->left;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    bottom_node = node;
Packit Service 384592
Packit Service 384592
    if(node->bit < bitlen)
Packit Service 384592
        bit_validation = node->bit;
Packit Service 384592
    else
Packit Service 384592
        bit_validation = bitlen;
Packit Service 384592
Packit Service 384592
    for (i = 0; (i * NETMASK_8) < bit_validation; i++) {
Packit Service 384592
        int net = 0, div = 0;
Packit Service 384592
        int cnt = 0;
Packit Service 384592
Packit Service 384592
        if ((temp = (buffer[i] ^ bottom_node->prefix->buffer[i])) == 0) {
Packit Service 384592
            test_bit = (i + 1) * NETMASK_8;
Packit Service 384592
            continue;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        temp += temp;
Packit Service 384592
Packit Service 384592
        for(cnt = 0, net = NETMASK_256, div = 2; net >= NETMASK_2; net = NETMASK_256/div,
Packit Service 384592
                div += div, cnt++)      {
Packit Service 384592
            if(temp >= net)   {
Packit Service 384592
                test_bit = (i * NETMASK_8) + cnt;
Packit Service 384592
                break;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
        break;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (bit_validation < test_bit)
Packit Service 384592
        test_bit = bit_validation;
Packit Service 384592
Packit Service 384592
    parent = node->parent;
Packit Service 384592
Packit Service 384592
    while (parent && test_bit <= parent->bit) {
Packit Service 384592
        node = parent;
Packit Service 384592
        parent = node->parent;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (test_bit == bitlen && node->bit == bitlen) {
Packit Service 384592
        if (node->prefix != NULL) {
Packit Service 384592
            int found = 0;
Packit Service 384592
            CPTData *prefix_data = NULL;
Packit Service 384592
Packit Service 384592
            prefix_data = node->prefix->prefix_data;
Packit Service 384592
Packit Service 384592
            while(prefix_data != NULL)  {
Packit Service 384592
                if (prefix_data->netmask == netmask)
Packit Service 384592
                    ++found;
Packit Service 384592
                prefix_data = prefix_data->next;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if (found != 0) {
Packit Service 384592
Packit Service 384592
                CPTData *prefix_data = CPTCreateCPTData(netmask, tree->pool);
Packit Service 384592
                CPTAppendToCPTDataList(prefix_data, &prefix->prefix_data);
Packit Service 384592
Packit Service 384592
                if(CheckBitmask(netmask, ip_bitmask))
Packit Service 384592
                    return node;
Packit Service 384592
Packit Service 384592
                parent = node->parent;
Packit Service 384592
                while (parent != NULL && netmask < (parent->bit + 1)) {
Packit Service 384592
                    node = parent;
Packit Service 384592
                    parent = parent->parent;
Packit Service 384592
                }
Packit Service 384592
Packit Service 384592
                node->count++;
Packit Service 384592
                new_node = node;
Packit Service 384592
                node->netmasks = apr_palloc(tree->pool, (node->count *  sizeof(unsigned char)));
Packit Service 384592
Packit Service 384592
                if ((node->count -1) == 0) {
Packit Service 384592
                    node->netmasks[0] = netmask;
Packit Service 384592
                    return new_node;
Packit Service 384592
                }
Packit Service 384592
Packit Service 384592
                node->netmasks[node->count - 1] = netmask;
Packit Service 384592
Packit Service 384592
                i = node->count - 2;
Packit Service 384592
                while (i >= 0) {
Packit Service 384592
                    if (netmask < node->netmasks[i]) {
Packit Service 384592
                        node->netmasks[i + 1] = netmask;
Packit Service 384592
                        break;
Packit Service 384592
                    }
Packit Service 384592
Packit Service 384592
                    node->netmasks[i + 1] = node->netmasks[i];
Packit Service 384592
                    node->netmasks[i] = netmask;
Packit Service 384592
                    i--;
Packit Service 384592
                }
Packit Service 384592
            }
Packit Service 384592
        } else {
Packit Service 384592
            node->prefix = CPTCreatePrefix(prefix->buffer, prefix->bitlen,
Packit Service 384592
                    NETMASK_256-1, tree->pool);
Packit Service 384592
        }
Packit Service 384592
        return node;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    new_node = CPTCreateNode(tree->pool);
Packit Service 384592
Packit Service 384592
    if(new_node == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    new_node->prefix = prefix;
Packit Service 384592
    new_node->bit = prefix->bitlen;
Packit Service 384592
Packit Service 384592
    if (test_bit == bitlen) {
Packit Service 384592
Packit Service 384592
        x = SHIFT_RIGHT_MASK(test_bit, 3); y = SHIFT_RIGHT_MASK(NETMASK_128, (test_bit % 8));
Packit Service 384592
Packit Service 384592
        if (TREE_CHECK(bottom_node->prefix->buffer[x],y)) {
Packit Service 384592
            new_node->right = node;
Packit Service 384592
        } else {
Packit Service 384592
            new_node->left = node;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        new_node->parent = node->parent;
Packit Service 384592
        node->parent = SetParentNode(node, new_node, tree);
Packit Service 384592
Packit Service 384592
    } else {
Packit Service 384592
        i_node = CPTCreateNode(tree->pool);
Packit Service 384592
Packit Service 384592
        if(i_node == NULL)
Packit Service 384592
            return NULL;
Packit Service 384592
Packit Service 384592
        //i_node->prefix = NULL;
Packit Service 384592
        i_node->bit = test_bit;
Packit Service 384592
        i_node->parent = node->parent;
Packit Service 384592
Packit Service 384592
        if (node->netmasks != NULL) {
Packit Service 384592
            i = 0;
Packit Service 384592
            while(i < node->count) {
Packit Service 384592
                if (node->netmasks[i] < test_bit + 1)
Packit Service 384592
                    break;
Packit Service 384592
                i++;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            i_node->netmasks = apr_palloc(tree->pool, (node->count - i) * sizeof(unsigned char));
Packit Service 384592
Packit Service 384592
            if(i_node->netmasks == NULL) {
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            j = 0;
Packit Service 384592
            while (j < (node->count - i))   {
Packit Service 384592
                i_node->netmasks[j] = node->netmasks[i + j];
Packit Service 384592
                j++;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            i_node->count = (node->count - i);
Packit Service 384592
            node->count = i;
Packit Service 384592
Packit Service 384592
            if (node->count == 0) {
Packit Service 384592
                node->netmasks = NULL;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        x = SHIFT_RIGHT_MASK(test_bit, 3); y = SHIFT_RIGHT_MASK(NETMASK_128, (test_bit % 8));
Packit Service 384592
Packit Service 384592
        if (TREE_CHECK(buffer[x],y)) {
Packit Service 384592
            i_node->left = node;
Packit Service 384592
            i_node->right = new_node;
Packit Service 384592
        } else {
Packit Service 384592
            i_node->left = new_node;
Packit Service 384592
            i_node->right = node;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        new_node->parent = i_node;
Packit Service 384592
        node->parent = SetParentNode(node, i_node, tree);
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (InsertNetmask(node, parent, new_node, tree, netmask, bitlen))
Packit Service 384592
        return new_node;
Packit Service 384592
Packit Service 384592
    return new_node;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
int TreeCheckData(TreePrefix *prefix, CPTData *prefix_data, unsigned int netmask)   {
Packit Service 384592
Packit Service 384592
    while(prefix_data != NULL)  {
Packit Service 384592
        if (prefix_data->netmask == netmask) {
Packit Service 384592
            return 1;
Packit Service 384592
        }
Packit Service 384592
        prefix_data = prefix_data->next;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return 0;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
int TreePrefixNetmask(modsec_rec *msr, TreePrefix *prefix, unsigned int netmask, int flag)   {
Packit Service 384592
    CPTData *prefix_data = NULL;
Packit Service 384592
    int ret = 0;
Packit Service 384592
Packit Service 384592
    if (prefix == NULL) {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "TreePrefixNetmask: prefix is NULL.");
Packit Service 384592
        }
Packit Service 384592
        return 0;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    prefix_data = prefix->prefix_data;
Packit Service 384592
Packit Service 384592
    if (flag == 1) {
Packit Service 384592
Packit Service 384592
        if(prefix_data == NULL) return 0;
Packit Service 384592
Packit Service 384592
        if (prefix_data->netmask != netmask) {
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "TreePrefixNetmask: Cannot find a prefix with correct netmask.");
Packit Service 384592
            }
Packit Service 384592
            return 0;
Packit Service 384592
        } else {
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "TreePrefixNetmask: Found a prefix with correct netmask.");
Packit Service 384592
            }
Packit Service 384592
            return 1;
Packit Service 384592
        }
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
        msr_log(msr, 9, "TreePrefixNetmask: Check if a prefix has a the correct netmask");
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    ret = TreeCheckData(prefix, prefix_data, netmask);
Packit Service 384592
Packit Service 384592
    return ret;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTRetriveNode(modsec_rec *msr, unsigned char *buffer, unsigned int ip_bitmask, TreeNode *node)  {
Packit Service 384592
    unsigned int x, y;
Packit Service 384592
Packit Service 384592
    if(node == NULL)    {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTRetriveNode: Node tree is NULL.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if(buffer == NULL)  {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTRetriveNode: Empty ip address. Nothing to search for.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    while (node->bit < ip_bitmask) {
Packit Service 384592
Packit Service 384592
        x = SHIFT_RIGHT_MASK(node->bit, 3); y = SHIFT_RIGHT_MASK(NETMASK_128, (node->bit % 8));
Packit Service 384592
Packit Service 384592
        if (TREE_CHECK(buffer[x], y)) {
Packit Service 384592
            node = node->right;
Packit Service 384592
            if (node == NULL)   return NULL;
Packit Service 384592
        } else {
Packit Service 384592
            node = node->left;
Packit Service 384592
            if (node == NULL)   return NULL;
Packit Service 384592
        }
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
        msr_log(msr, 9, "CPTRetriveNode: Found the node for provided ip address.");
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
Packit Service 384592
    return node;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTRetriveParentNode(TreeNode *node)  {
Packit Service 384592
Packit Service 384592
    while (node != NULL && node->netmasks == NULL)
Packit Service 384592
        node = node->parent;
Packit Service 384592
Packit Service 384592
    return node;
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTFindElementIPNetblock(modsec_rec *msr, unsigned char *ipdata, unsigned char ip_bitmask, TreeNode *node) {
Packit Service 384592
    TreeNode *netmask_node = NULL;
Packit Service 384592
    int mask = 0,  bytes = 0;
Packit Service 384592
    int i = 0, j = 0;
Packit Service 384592
    int mask_bits = 0;
Packit Service 384592
Packit Service 384592
    node = CPTRetriveParentNode(node);
Packit Service 384592
Packit Service 384592
    if (node == NULL)   {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElementIPNetblock: Node tree is NULL.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    netmask_node = node;
Packit Service 384592
Packit Service 384592
    while(j < netmask_node->count)    {
Packit Service 384592
        bytes = ip_bitmask / 8;
Packit Service 384592
Packit Service 384592
        while( i < bytes )  {
Packit Service 384592
Packit Service 384592
            mask = -1;
Packit Service 384592
            mask_bits = ((i + 1) * 8);
Packit Service 384592
Packit Service 384592
            if (mask_bits > netmask_node->netmasks[j]) {
Packit Service 384592
                if ((mask_bits - netmask_node->netmasks[j]) < 8)
Packit Service 384592
                    mask = SHIFT_LEFT_MASK(mask_bits - netmask_node->netmasks[j]);
Packit Service 384592
                else
Packit Service 384592
                    mask = 0;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            ipdata[i] &= mask;
Packit Service 384592
            i++;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        node = CPTRetriveNode(msr, ipdata, ip_bitmask, node);
Packit Service 384592
Packit Service 384592
        if (node && node->bit != ip_bitmask)    {
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "CPTFindElementIPNetblock: Found a tree node but netmask is different.");
Packit Service 384592
            }
Packit Service 384592
            return NULL;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        if (node && node->prefix == NULL)   {
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "CPTFindElementIPNetblock: Found a tree node but prefix is NULL.");
Packit Service 384592
            }
Packit Service 384592
            return NULL;
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        if (memcmp(node->prefix->buffer, ipdata, bytes) == 0) {
Packit Service 384592
            mask = SHIFT_LEFT_MASK(8 - ip_bitmask % 8);
Packit Service 384592
Packit Service 384592
            if ((ip_bitmask % 8) == 0) {
Packit Service 384592
                if (TreePrefixNetmask(msr, node->prefix, netmask_node->netmasks[j], FALSE)) {
Packit Service 384592
                    if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                        msr_log(msr, 9, "CPTFindElementIPNetblock: Node found for provided ip address");
Packit Service 384592
                    }
Packit Service 384592
                    return node;
Packit Service 384592
                }
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if ((node->prefix->buffer[bytes] & mask) == (ipdata[bytes] & mask)) {
Packit Service 384592
                if (TreePrefixNetmask(msr, node->prefix, netmask_node->netmasks[j], FALSE)) {
Packit Service 384592
                    if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                        msr_log(msr, 9, "CPTFindElementIPNetblock: Node found for provided ip address");
Packit Service 384592
                    }
Packit Service 384592
                    return node;
Packit Service 384592
                }
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        j++;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return CPTFindElementIPNetblock(msr, ipdata, ip_bitmask, netmask_node->parent);
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTFindElement(modsec_rec *msr, unsigned char *ipdata, unsigned int ip_bitmask, CPTTree *tree)   {
Packit Service 384592
    TreeNode *node = NULL;
Packit Service 384592
    int mask = 0, bytes = 0;
Packit Service 384592
    unsigned char temp_data[NETMASK_256-1];
Packit Service 384592
Packit Service 384592
    if (tree == NULL)   {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Tree is NULL. Cannot proceed searching the ip.");
Packit Service 384592
        }
Packit Service 384592
        return node;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (tree->head == NULL) {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Tree head is NULL. Cannot proceed searching the ip.");
Packit Service 384592
        }
Packit Service 384592
        return node;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    node = tree->head;
Packit Service 384592
Packit Service 384592
    if (ip_bitmask > (NETMASK_256-1))   {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Netmask cannot be greater than 255");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    bytes = ip_bitmask/8;
Packit Service 384592
Packit Service 384592
    memset(temp_data, 0, NETMASK_256-1);
Packit Service 384592
    memcpy(temp_data, ipdata, bytes);
Packit Service 384592
Packit Service 384592
    node = CPTRetriveNode(msr, temp_data, ip_bitmask, node);
Packit Service 384592
Packit Service 384592
    if (node && (node->bit != ip_bitmask)) {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Found a tree node but netmask is different.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if(node == NULL)    {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Node tree is NULL.");
Packit Service 384592
        }
Packit Service 384592
        return node;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if(node->prefix == NULL)    {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTFindElement: Found a tree node but prefix is NULL.");
Packit Service 384592
        }
Packit Service 384592
        return node;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if (memcmp(node->prefix->buffer, temp_data, bytes) == 0) {
Packit Service 384592
        mask = SHIFT_LEFT_MASK(8 - ip_bitmask % 8);
Packit Service 384592
Packit Service 384592
        if ((ip_bitmask % 8) == 0) {
Packit Service 384592
            if (TreePrefixNetmask(msr, node->prefix, ip_bitmask, TRUE)) {
Packit Service 384592
                if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                    msr_log(msr, 9, "CPTFindElement: Node found for provided ip address");
Packit Service 384592
                }
Packit Service 384592
                return node;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
Packit Service 384592
        if ((node->prefix->buffer[bytes] & mask) == (temp_data[bytes] & mask)) {
Packit Service 384592
            if (TreePrefixNetmask(msr, node->prefix, ip_bitmask, TRUE)) {
Packit Service 384592
                if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                    msr_log(msr, 9, "CPTFindElement: Node found for provided ip address");
Packit Service 384592
                }
Packit Service 384592
                return node;
Packit Service 384592
            }
Packit Service 384592
        }
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return CPTFindElementIPNetblock(msr, temp_data, ip_bitmask, node);
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *CPTIpMatch(modsec_rec *msr, unsigned char *ipdata, CPTTree *tree, int type)   {
Packit Service 384592
Packit Service 384592
    if(tree == NULL)  {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTIpMatch: Tree is NULL. Cannot proceed searching the ip.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    if(ipdata == NULL)  {
Packit Service 384592
        if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
            msr_log(msr, 9, "CPTIpMatch: Empty ip address. Nothing to search for.");
Packit Service 384592
        }
Packit Service 384592
        return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    switch(type)    {
Packit Service 384592
        case IPV4_TREE:
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "CPTIpMatch: Searching ip type 0x%x", type);
Packit Service 384592
            }
Packit Service 384592
            return CPTFindElement(msr, ipdata, NETMASK_32, tree);
Packit Service 384592
        case IPV6_TREE:
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "CPTIpMatch: Searching ip type 0x%x", type);
Packit Service 384592
            }
Packit Service 384592
            return CPTFindElement(msr, ipdata, NETMASK_128, tree);
Packit Service 384592
        default:
Packit Service 384592
            if (msr && msr->txcfg->debuglog_level >= 9) {
Packit Service 384592
                msr_log(msr, 9, "CPTIpMatch: Unknown ip type 0x%x", type);
Packit Service 384592
            }
Packit Service 384592
            return NULL;
Packit Service 384592
    }
Packit Service 384592
}
Packit Service 384592
Packit Service 384592
TreeNode *TreeAddIP(const char *buffer, CPTTree *tree, int type) {
Packit Service 384592
    unsigned long ip, ret;
Packit Service 384592
    unsigned char netmask_v4 = NETMASK_32, netmask_v6 = NETMASK_128;
Packit Service 384592
    char ip_strv4[NETMASK_32], ip_strv6[NETMASK_128];
Packit Service 384592
    struct in_addr addr4;
Packit Service 384592
    struct in6_addr addr6;
Packit Service 384592
    int pos = 0;
Packit Service 384592
    char *ptr = NULL;
Packit Service 384592
Packit Service 384592
    if(tree == NULL)
Packit Service 384592
        return NULL;
Packit Service 384592
Packit Service 384592
    pos = strchr(buffer, '/') - buffer;
Packit Service 384592
Packit Service 384592
    switch(type)    {
Packit Service 384592
Packit Service 384592
        case IPV4_TREE:
Packit Service 384592
            memset(&addr4, 0, sizeof(addr4));
Packit Service 384592
            memset(ip_strv4, 0x0, NETMASK_32);
Packit Service 384592
Packit Service 384592
            strncpy(ip_strv4, buffer, sizeof(ip_strv4));
Packit Service 384592
            *(ip_strv4 + (sizeof(ip_strv4) - 1)) = '\0';
Packit Service 384592
Packit Service 384592
            ptr = strdup(ip_strv4);
Packit Service 384592
            netmask_v4 = is_netmask_v4(ptr);
Packit Service 384592
Packit Service 384592
            if (netmask_v4 > NETMASK_32) {
Packit Service 384592
                free(ptr);
Packit Service 384592
                ptr = NULL;
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if(ptr != NULL) {
Packit Service 384592
                free(ptr);
Packit Service 384592
                ptr = NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if(netmask_v4 == 0) {
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
            else if (netmask_v4 != NETMASK_32 && pos < strlen(ip_strv4)) {
Packit Service 384592
                ip_strv4[pos] = '\0';
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            ret = inet_pton(AF_INET, ip_strv4, &addr4);
Packit Service 384592
Packit Service 384592
            if (ret <= 0) {
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            ip = addr4.s_addr;
Packit Service 384592
Packit Service 384592
            tree->count++;
Packit Service 384592
Packit Service 384592
            return CPTAddElement((unsigned char *)&ip, NETMASK_32, tree, netmask_v4);
Packit Service 384592
Packit Service 384592
        case IPV6_TREE:
Packit Service 384592
            memset(&addr6, 0, sizeof(addr6));
Packit Service 384592
            memset(ip_strv6, 0x0, NETMASK_128);
Packit Service 384592
Packit Service 384592
            strncpy(ip_strv6, buffer, sizeof(ip_strv6));
Packit Service 384592
            *(ip_strv6 + sizeof(ip_strv6) - 1) = '\0';
Packit Service 384592
Packit Service 384592
            ptr = strdup(ip_strv6);
Packit Service 384592
            netmask_v6 = is_netmask_v6(ptr);
Packit Service 384592
Packit Service 384592
            if (netmask_v6 > NETMASK_128) {
Packit Service 384592
                free(ptr);
Packit Service 384592
                ptr = NULL;
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if(ptr != NULL) {
Packit Service 384592
                free(ptr);
Packit Service 384592
                ptr = NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            if(netmask_v6 == 0) {
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
            else if (netmask_v6 != NETMASK_128 && pos < strlen(ip_strv6)) {
Packit Service 384592
                ip_strv6[pos] = '\0';
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            ret = inet_pton(AF_INET6, ip_strv6, &addr6);
Packit Service 384592
Packit Service 384592
            if (ret <= 0)
Packit Service 384592
            {
Packit Service 384592
                return NULL;
Packit Service 384592
            }
Packit Service 384592
Packit Service 384592
            tree->count++;
Packit Service 384592
Packit Service 384592
            return CPTAddElement((unsigned char *)&addr6.s6_addr, NETMASK_128, tree, netmask_v6);
Packit Service 384592
        default:
Packit Service 384592
            return NULL;
Packit Service 384592
    }
Packit Service 384592
Packit Service 384592
    return NULL;
Packit Service 384592
}