inet/ip/ip_listutils.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

#include <sys/types.h>
#include <sys/stream.h>
#include <sys/dlpi.h>
#include <sys/stropts.h>
#include <sys/strlog.h>
#include <sys/systm.h>
#include <sys/ddi.h>
#include <sys/cmn_err.h>

#include <sys/param.h>
#include <sys/tihdr.h>
#include <netinet/in.h>
#include <netinet/ip6.h>

#include <inet/common.h>
#include <inet/mi.h>
#include <inet/ip.h>
#include <inet/ip6.h>
#include <inet/ip_listutils.h>

/*
 * These functions perform set operations on sets of ipv6 addresses.
 * The sets are formatted as slist_t's (defined in <inet/ip.h>):
 *  typedef struct slist_s {
 *      int     sl_nusmrc;
 *      in6_addr_t  sl_addr[MAX_FILTER_SIZE];
 *  } slist_t;
 *
 * The functions were designed specifically for the implementation of
 * IGMPv3 and MLDv2 in ip; they were not meant to be general-purpose.
 */

/*
 * Tells if lists A and B are different or not - true if different;
 * caller guarantees that lists are <= MAX_FILTER_SIZE
 */
boolean_t
lists_are_different(const slist_t *a, const slist_t *b)
{
    int i, j;
    int acnt = SLIST_CNT(a);
    int bcnt = SLIST_CNT(b);
    boolean_t found;

    if (acnt != bcnt)
        return (B_TRUE);

    ASSERT(acnt <= MAX_FILTER_SIZE);
    ASSERT(bcnt <= MAX_FILTER_SIZE);

    for (i = 0; i < acnt; i++) {
        found = B_FALSE;
        for (j = 0; j < bcnt; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &a->sl_addr[i], &b->sl_addr[j])) {
                found = B_TRUE;
                break;
            }
        }
        if (!found)
            return (B_TRUE);
    }
    return (B_FALSE);
}

/*
 * Tells if list a contains address addr - true if it does, false if not;
 * caller guarantees that list is <= MAX_FILTER_SIZE.
 */
boolean_t
list_has_addr(const slist_t *a, const in6_addr_t *addr)
{
    int i;

    if (SLIST_IS_EMPTY(a))
        return (B_FALSE);

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);

    for (i = 0; i < a->sl_numsrc; i++) {
        if (IN6_ARE_ADDR_EQUAL(&a->sl_addr[i], addr))
            return (B_TRUE);
    }
    return (B_FALSE);
}

/*
 * Implements a * b and stores the result in target; caller guarantees
 * that a and b are <= MAX_FILTER_SIZE, and that target is a valid pointer.
 * target must not be the same as a or b; for that case see
 * l_intersection_in_a().
 */
void
l_intersection(const slist_t *a, const slist_t *b, slist_t *target)
{
    int i, j;

    target->sl_numsrc = 0;

    if (SLIST_IS_EMPTY(a) || SLIST_IS_EMPTY(b))
        return;

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
    ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);

    for (i = 0; i < a->sl_numsrc; i++) {
        for (j = 0; j < b->sl_numsrc; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &a->sl_addr[i], &b->sl_addr[j])) {
                target->sl_addr[target->sl_numsrc++] =
                    a->sl_addr[i];
                break;
            }
        }
    }
}

/*
 * Implements a - b and stores the result in target; caller guarantees
 * that a and b are <= MAX_FILTER_SIZE, and that target is a valid pointer.
 * target must not be the same as a or b; for that case see l_difference_in_a().
 */
void
l_difference(const slist_t *a, const slist_t *b, slist_t *target)
{
    int i, j;
    boolean_t found = B_FALSE;

    target->sl_numsrc = 0;

    if (SLIST_IS_EMPTY(a))
        return;

    if (SLIST_IS_EMPTY(b)) {
        l_copy(a, target);
        return;
    }

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
    ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);

    for (i = 0; i < a->sl_numsrc; i++) {
        for (j = 0; j < b->sl_numsrc; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &a->sl_addr[i], &b->sl_addr[j])) {
                found = B_TRUE;
                break;
            }
        }
        if (!found) {
            target->sl_addr[target->sl_numsrc++] = a->sl_addr[i];
        } else {
            found = B_FALSE;
        }
    }
}

/*
 * Removes addr from list a.  Caller guarantees that addr is a valid
 * pointer, and that a <= MAX_FILTER_SIZE.  addr will only be removed
 * once from the list; if it appears in the list multiple times, extra
 * copies may remain.
 */
void
l_remove(slist_t *a, const in6_addr_t *addr)
{
    int i, mvsize;

    if (SLIST_IS_EMPTY(a))
        return;

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);

    for (i = 0; i < a->sl_numsrc; i++) {
        if (IN6_ARE_ADDR_EQUAL(&a->sl_addr[i], addr)) {
            a->sl_numsrc--;
            mvsize = (a->sl_numsrc - i) * sizeof (in6_addr_t);
            (void) memmove(&a->sl_addr[i], &a->sl_addr[i + 1],
                mvsize);
            break;
        }
    }
}

/*
 * Make a copy of list a by allocating a new slist_t and copying only
 * a->sl_numsrc addrs.  Caller guarantees that a <= MAX_FILTER_SIZE.
 * Return a pointer to the newly alloc'd list, or NULL if a is empty
 * (no memory is alloc'd in this case).
 */
slist_t *
l_alloc_copy(const slist_t *a)
{
    slist_t *b;

    if (SLIST_IS_EMPTY(a))
        return (NULL);

    if ((b = l_alloc()) == NULL)
        return (NULL);

    l_copy(a, b);

    return (b);
}

/*
 * Copy the address list from slist a into slist b, overwriting anything
 * that might already be in slist b.  Assumes that a <= MAX_FILTER_SIZE
 * and that b points to a properly allocated slist.
 */
void
l_copy(const slist_t *a, slist_t *b)
{
    if (SLIST_IS_EMPTY(a)) {
        b->sl_numsrc = 0;
        return;
    }

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);

    b->sl_numsrc = a->sl_numsrc;
    (void) memcpy(b->sl_addr, a->sl_addr,
        a->sl_numsrc * sizeof (in6_addr_t));
}

/*
 * Append to a any addrs in b that are not already in a (i.e. perform
 * a + b and store the result in a).  If b is empty, the function returns
 * without taking any action.
 *
 * Caller guarantees that a and b are <= MAX_FILTER_SIZE, and that a
 * and overflow are valid pointers.
 *
 * If an overflow occurs (a + b > MAX_FILTER_SIZE), a will contain the
 * first MAX_FILTER_SIZE addresses of the union, and *overflow will be
 * set to true.  Otherwise, *overflow will be set to false.
 */
void
l_union_in_a(slist_t *a, const slist_t *b, boolean_t *overflow)
{
    int i, j;
    boolean_t found;

    *overflow = B_FALSE;

    if (SLIST_IS_EMPTY(b))
        return;

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
    ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);

    for (i = 0; i < b->sl_numsrc; i++) {
        found = B_FALSE;
        for (j = 0; j < a->sl_numsrc; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &b->sl_addr[i], &a->sl_addr[j])) {
                found = B_TRUE;
                break;
            }
        }
        if (!found) {
            if (a->sl_numsrc == MAX_FILTER_SIZE) {
                *overflow = B_TRUE;
                break;
            } else {
                a->sl_addr[a->sl_numsrc++] = b->sl_addr[i];
            }
        }
    }
}

/*
 * Remove from list a any addresses that are not also in list b
 * (i.e. perform a * b and store the result in a).
 *
 * Caller guarantees that a and b are <= MAX_FILTER_SIZE, and that
 * a is a valid pointer.
 */
void
l_intersection_in_a(slist_t *a, const slist_t *b)
{
    int i, j, shift;
    boolean_t found;

    if (SLIST_IS_EMPTY(b)) {
        a->sl_numsrc = 0;
        return;
    }

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
    ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);

    shift = 0;
    for (i = 0; i < a->sl_numsrc; i++) {
        found = B_FALSE;
        for (j = 0; j < b->sl_numsrc; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &a->sl_addr[i], &b->sl_addr[j])) {
                found = B_TRUE;
                break;
            }
        }
        if (!found)
            shift++;
        else if (shift > 0)
            a->sl_addr[i - shift] = a->sl_addr[i];
    }
    a->sl_numsrc -= shift;
}

/*
 * Remove from list a any addresses that are in list b (i.e. perform
 * a - b and store the result in a).
 *
 * Caller guarantees that a and b are <= MAX_FILTER_SIZE.  If either
 * list is empty (or a null pointer), the function returns without
 * taking any action.
 */
void
l_difference_in_a(slist_t *a, const slist_t *b)
{
    int i, j, shift;
    boolean_t found;

    if (SLIST_IS_EMPTY(a) || SLIST_IS_EMPTY(b))
        return;

    ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
    ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);

    shift = 0;
    for (i = 0; i < a->sl_numsrc; i++) {
        found = B_FALSE;
        for (j = 0; j < b->sl_numsrc; j++) {
            if (IN6_ARE_ADDR_EQUAL(
                &a->sl_addr[i], &b->sl_addr[j])) {
                found = B_TRUE;
                break;
            }
        }
        if (found)
            shift++;
        else if (shift > 0)
            a->sl_addr[i - shift] = a->sl_addr[i];
    }
    a->sl_numsrc -= shift;
}

/*
 * Wrapper function to alloc an slist_t.
 */
slist_t *
l_alloc()
{
    slist_t *p;

    p = (slist_t *)mi_alloc(sizeof (slist_t), BPRI_MED);
    if (p != NULL)
        p->sl_numsrc = 0;
    return (p);
}

/*
 * Frees an slist_t structure.  Provided for symmetry with l_alloc().
 */
void
l_free(slist_t *a)
{
    mi_free(a);
}