usr/src/uts/common/ipp/ipgpc/filters.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <sys/atomic.h>
#include <sys/types.h>
#include <sys/systm.h>
#include <netinet/in.h>
#include <netinet/ip6.h>
#include <inet/common.h>
#include <inet/ip.h>
#include <inet/ip6.h>
#include <ipp/ipp_config.h>
#include <ipp/ipgpc/filters.h>
#include <ipp/ipgpc/trie.h>
#include <ipp/ipgpc/table.h>
#include <ipp/ipgpc/ba_table.h>
#include <ipp/ipgpc/classifier.h>

/* Implementation for filter management and configuration support of ipgpc */

#define	BITLENGTH(x) (sizeof (x) * NBBY)

/* Globals */
kmutex_t ipgpc_table_list_lock; /* table list lock */
kmutex_t ipgpc_fid_list_lock;	/* filter id list lock */
kmutex_t ipgpc_cid_list_lock;	/* class id list lock */
trie_id_t ipgpc_trie_list[NUM_TRIES]; /* list of all trie structures ids */
table_id_t ipgpc_table_list[NUM_TABLES]; /* list of all table ids */
ba_table_id_t ipgpc_ds_table_id;	/* DiffServ field table id */
fid_t *ipgpc_fid_list = NULL;		/* filter id list */
cid_t *ipgpc_cid_list = NULL;		/* class id list */
kmem_cache_t *ht_node_cache = NULL;	/* hashtable cache */
kmem_cache_t *ht_match_cache = NULL;	/* ht_match cache */
kmem_cache_t *trie_node_cache = NULL;	/* trie node cache */
kmem_cache_t *element_node_cache = NULL; /* element node cache */
boolean_t ipgpc_gather_stats;	/* should stats be performed for ipgpc */
uint64_t ipgpc_npackets;	/* number of packets stat */
uint64_t ipgpc_nbytes;		/* number of bytes stat */
uint64_t ipgpc_epackets;	/* number of packets in error */
int ipgpc_def_class_id = -1;	/* class id of default class */
size_t ipgpc_num_fltrs;		/* number of loaded filter */
size_t ipgpc_num_cls;		/* number of loaded classes */
/* max number of allowable filters */
size_t ipgpc_max_num_filters = IPGPC_DEFAULT_MAX_FILTERS;
/* max number of allowable classes */
size_t ipgpc_max_num_classes = IPGPC_DEFAULT_MAX_CLASSES;
size_t ipgpc_max_filters = 0;	/* set in /etc/system */
size_t ipgpc_max_classes = 0;	/* set in /etc/system */
ipp_stat_t *ipgpc_global_stats = NULL; /* global stats structure */

/* Statics */
static trie saddr_trie;		/* IPv4 source address trie */
static trie daddr_trie;		/* IPv4 destination address trie */
static trie sport_trie;		/* source port trie */
static trie dport_trie;		/* destination port trie */
static trie saddr6_trie;	/* IPv6 source address trie */
static trie daddr6_trie;	/* IPv6 destination address trie */
static ht_node_t proto_table[TABLE_SIZE]; /* protocol table */
static ht_node_t uid_table[TABLE_SIZE]; /* IPGPC_UID table */
static ht_node_t projid_table[TABLE_SIZE]; /* IPGPC_PROJID table */
static ht_node_t if_table[TABLE_SIZE]; /* Interface ID table */
static ht_node_t dir_table[TABLE_SIZE]; /* packet direction table */
static ipp_action_id_t ipgpc_aid; /* the action id for ipgpc */

static int global_statinit(void);
static void insert_ipgpc_trie_list_info(int, size_t, trie, uint16_t);
static int initialize_tries(void);
static void insert_ipgpc_table_list_info(int, hash_table, int, uint16_t);
static void initialize_tables(void);
static void initialize_ba_tables(void);
static void element_node_ref(element_node_t *);
static void element_node_unref(element_node_t *);
static int element_node_cache_constructor(void *, void *, int);
static int filter_name2id(unsigned *, char[], int32_t, int);
static int class_name2id(unsigned *, char[], int);
static boolean_t iscontinuousmask(uint32_t, uint8_t);
static void insertfid(int, ipgpc_filter_t *, uint_t);
static void common_addfilter(fid_t *, int);
static void v4_addfilter(fid_t *, int);
static void v6_addfilter(fid_t *, int);
static void reset_dontcare_stats(void);
static int class_statinit(ipgpc_class_t *, int);
static int insertcid(ipgpc_class_t *, int *);
static void common_removefilter(int, fid_t *);
static void v4_removefilter(int, fid_t *);
static void v6_removefilter(int, fid_t *);
static void removecid(int);
static void remove_from_cid_filter_list(int, int);
static void removeclasses(ipp_flags_t);
static void freetriev6nodes(node_t **);
static int ht_match_insert(ht_match_t *, int, uint16_t);
static int update_class_stats(ipp_stat_t *, void *, int);
static int update_global_stats(ipp_stat_t *, void *, int);
static int build_class_nvlist(nvlist_t **, ipgpc_class_t *, boolean_t);
static int build_filter_nvlist(nvlist_t **, ipgpc_filter_t *, char *);


/*
 * Module initialization code
 */

/*
 * global_statinit()
 *
 * initializes global stats for ipgpc action module.
 * global include:
 * - number of filters loaded
 * - number of classes loaded
 * - number of packets that have passed through ipgpc since action create
 * - number of bytes that have passed through ipgpc since action create
 * if ipp_stat_create fails, an error code is returned
 * if ipp_stat_named_init fails, an error code is returned
 * 0 is returned on success
 */
static int
global_statinit(void)
{
	int rc;
	globalstats_t *gblsnames = NULL;

	/* create stat structure */
	if ((rc = ipp_stat_create(ipgpc_aid, "ipgpc_global_stats", 5,
	    update_global_stats, NULL, &ipgpc_global_stats)) != 0) {
		ipgpc0dbg(("global_statinit: error creating ipp_stat entry"));
		return (rc);
	}

	ASSERT(ipgpc_global_stats != NULL);
	gblsnames = (globalstats_t *)ipgpc_global_stats->ipps_data;
	ASSERT(gblsnames != NULL);

	/* add stat name entries */
	if ((rc = ipp_stat_named_init(ipgpc_global_stats, "nfilters",
	    IPP_STAT_UINT32, &gblsnames->nfilters)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipgpc_global_stats, "nclasses",
	    IPP_STAT_UINT32, &gblsnames->nclasses)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipgpc_global_stats, "nbytes",
	    IPP_STAT_UINT64, &gblsnames->nbytes)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipgpc_global_stats, "npackets",
	    IPP_STAT_UINT64, &gblsnames->npackets)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipgpc_global_stats, "epackets",
	    IPP_STAT_UINT64, &gblsnames->epackets)) != 0) {
		return (rc);
	}
	ipp_stat_install(ipgpc_global_stats);
	return (0);
}

static void
insert_ipgpc_trie_list_info(int trie_id, size_t key_len, trie in_trie,
    uint16_t mask)
{
	ipgpc_trie_list[trie_id].trie = in_trie;
	rw_init(&ipgpc_trie_list[trie_id].rw_lock, NULL, RW_DEFAULT, NULL);
	ipgpc_trie_list[trie_id].key_len = key_len;
	ipgpc_trie_list[trie_id].info.mask = mask;
	ipgpc_trie_list[trie_id].info.dontcareonly = B_TRUE;
}

static int
initialize_tries(void)
{
	/* IPv4 Source Address field structure */
	if ((saddr_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	saddr_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_SADDRID, IP_ABITS, saddr_trie,
	    SADDR_MASK);
	/* IPv4 Destination Address field structure */
	if ((daddr_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	daddr_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_DADDRID, IP_ABITS, daddr_trie,
	    DADDR_MASK);
	/* TCP Source Port field structure */
	if ((sport_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	sport_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_SPORTID, BITLENGTH(uint16_t),
	    sport_trie, SPORT_MASK);
	/* TCP Destination Port field structure */
	if ((dport_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	dport_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_DPORTID, BITLENGTH(uint16_t),
	    dport_trie, DPORT_MASK);
	/* IPv6 Source Address field structure */
	if ((saddr6_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	saddr6_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_SADDRID6, IPV6_ABITS,
	    saddr6_trie, SADDR6_MASK);
	/* IPv6 Destination Address field structure */
	if ((daddr6_trie = create_node(KM_NOSLEEP)) == NULL) {
		return (ENOMEM);
	}
	daddr6_trie->isroot = 1;
	insert_ipgpc_trie_list_info(IPGPC_TRIE_DADDRID6, IPV6_ABITS,
	    daddr6_trie, DADDR6_MASK);
	return (0);
}

static void
insert_ipgpc_table_list_info(int table_id, hash_table table, int wildcard,
    uint16_t mask)
{
	ipgpc_table_list[table_id].table = table;
	ipgpc_table_list[table_id].wildcard = wildcard;
	ipgpc_table_list[table_id].info.mask = mask;
	ipgpc_table_list[table_id].info.dontcareonly = B_TRUE;
}
static void
initialize_tables(void)
{
	/* Protocol selector structure */
	insert_ipgpc_table_list_info(PROTOID_IDX, proto_table,
	    IPGPC_UNSPECIFIED, PROTO_MASK);
	/* UID selector structure */
	insert_ipgpc_table_list_info(UID_IDX, uid_table, IPGPC_WILDCARD,
	    UID_MASK);
	/* PROJID selector structure */
	insert_ipgpc_table_list_info(PROJID_IDX, projid_table, IPGPC_WILDCARD,
	    PROJID_MASK);
	/* IF_INDEX selector structure */
	insert_ipgpc_table_list_info(IF_IDX, if_table, IPGPC_UNSPECIFIED,
	    IF_MASK);
	/* DIR selector structure */
	insert_ipgpc_table_list_info(DIR_IDX, dir_table, IPGPC_UNSPECIFIED,
	    DIR_MASK);
}

static void
initialize_ba_tables(void)
{
	/* DS (ToS/Traffic Class) field structure */
	ipgpc_ds_table_id.info.mask = DS_MASK;
	ipgpc_ds_table_id.info.dontcareonly = B_TRUE;
}

static void
element_node_ref(element_node_t *element)
{
	atomic_add_32(&element->element_refcnt, 1);
	ASSERT(element->element_refcnt > 1);
}

static void
element_node_unref(element_node_t *element)
{
	ASSERT(element->element_refcnt > 0);
	if (atomic_add_32_nv(&element->element_refcnt, -1) == 0) {
		kmem_cache_free(element_node_cache, element);
	}
}

/* ARGSUSED1 */
static int
element_node_cache_constructor(void *buf, void *cdrarg, int kmflags)
{
	element_node_t *node = buf;

	node->element_ref = element_node_ref;
	node->element_unref = element_node_unref;
	return (0);
}

/* prime values to be used for hashing of filter and class tables */
#define	IPGPC_PRIMES()	{0, 0, 0, 5, 11, 23, 47, 89, 191, 383, 503, 761, \
			1009, 1531, 2003, 2503, 3067, 3511, 4001, 5003, 6143, \
			10007, 12281, 15013, 20011, 24571, 49139, 98299, \
			100003, 196597, 393209, 786431, 1000003, 1251409, \
			1572853, 3145721, 0}

/*
 * ipgpc_initialize(in_aid)
 *
 * initializes locks, data structures, configuration variables used and
 * sets globals.  Will fail on memory or initialization error.
 */
int
ipgpc_initialize(ipp_action_id_t in_aid)
{
	ipgpc_class_t def_class;
	int i;
	int rc;
	int sizes[] = IPGPC_PRIMES();

	/* initialize globals */
	ipgpc_aid = in_aid;	/* store away action id for ipgpc */
	ipgpc_num_fltrs = 0;
	ipgpc_num_cls = 0;
	ipgpc_npackets = 0;
	ipgpc_nbytes = 0;
	ipgpc_epackets = 0;

	/* check for user tunable maximums (set in /etc/system) */
	if (ipgpc_max_filters > 0) {
		/* start with a reasonably small value to find closest prime */
		for (i = 3; i < sizeof (sizes) / sizeof (*sizes) - 1; ++i) {
			if (sizes[i] >= ipgpc_max_filters) {
				break;
			}
		}
		if (sizes[i] == 0) {
			ipgpc0dbg(("ipgpc_initialize: ipgpc_max_filters " \
			    "out of range"));
			/* use the largest allowable value */
			ipgpc_max_num_filters = sizes[(i - 1)];
		} else {
			ipgpc_max_num_filters = sizes[i];
		}
	}
	if (ipgpc_max_classes > 0) {
		/* start with a reasonably small value to find closest prime */
		for (i = 3; i < sizeof (sizes) / sizeof (*sizes) - 1; ++i) {
			if (sizes[i] >= ipgpc_max_classes) {
				break;
			}
		}
		if (sizes[i] == 0) {
			ipgpc0dbg(("ipgpc_initialize: ipgpc_max_classes " \
			    "out of range"));
			/* use the largest allowable value */
			ipgpc_max_num_classes = sizes[(i - 1)];
		} else {
			ipgpc_max_num_classes = sizes[i];
		}
	}

	/* create filter id list */
	ipgpc_fid_list =
	    kmem_zalloc(sizeof (fid_t) * ipgpc_max_num_filters, KM_NOSLEEP);
	if (ipgpc_fid_list == NULL) {
		ipgpc0dbg(("ipgpc_initialize: failed to create fid list"));
		return (ENOMEM);
	}

	/* create class id list */
	ipgpc_cid_list = kmem_zalloc(sizeof (cid_t) * ipgpc_max_num_classes,
	    KM_NOSLEEP);
	if (ipgpc_cid_list == NULL) {
		ipgpc0dbg(("ipgpc_initialize: failed to create cid list"));
		return (ENOMEM);
	}

	/* create object caches */
	element_node_cache = kmem_cache_create("element_node_cache",
	    sizeof (element_node_t), 0, element_node_cache_constructor,
	    NULL, NULL, NULL, NULL, 0);
	trie_node_cache = kmem_cache_create("trie_node_cache",
	    sizeof (node_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
	ht_node_cache = kmem_cache_create("ht_node_cache",
	    sizeof (ht_node_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
	ht_match_cache = kmem_cache_create("ht_match_cache",
	    sizeof (ht_match_t), 0, NULL, NULL, NULL, NULL, NULL, 0);

	/* initialize tries, catch memory errors */
	if ((rc = initialize_tries()) != 0) {
		return (rc);
	}

	initialize_tables();	/* no memory is allocated here */
	initialize_ba_tables();	/* no memory is allocated here */

	if ((rc = global_statinit()) != 0) { /* init global stats */
		ipgpc0dbg(("ipgpc_initialize: global_statinit error " \
		    "%d", rc));
		return (rc);
	}

	/* create default class */
	bzero(&def_class, sizeof (ipgpc_class_t));
	def_class.next_action = IPP_ACTION_CONT;
	def_class.gather_stats = B_FALSE; /* don't gather stats by default */
	(void) strcpy(def_class.class_name, "default");
	def_class.originator = IPP_CONFIG_PERMANENT; /* label as permanent */

	/* add default class and record default class id */
	if ((rc = insertcid(&def_class, &ipgpc_def_class_id)) != ENOENT) {
		ipgpc0dbg(("ipgpc_initialize: insert of default class failed" \
		    " with error %d", rc));
		return (rc);
	}
	return (0);
}

/*
 * Module modify code
 */

/*
 * name_hash(name, M)
 *
 * hash function for a string (name) of lenght M
 */
unsigned
name_hash(char *name, size_t M)
{
	unsigned h;

	for (h = 0; *name != '\0'; name++) {
		h = ((64 * h) + *name);
	}
	return ((h % M));
}


/*
 * ipgpc_filter_destructor(filter)
 *
 * frees any allocated memory pointed to in the filter structure
 * this function should be run before freeing an ipgpc_filter_t
 */
void
ipgpc_filter_destructor(ipgpc_filter_t *filter)
{
	if (filter->filter_comment != NULL) {
		kmem_free(filter->filter_comment,
		    (strlen(filter->filter_comment) + 1));
	}
	if (filter->saddr_hostname != NULL) {
		kmem_free(filter->saddr_hostname,
		    (strlen(filter->saddr_hostname) + 1));
	}
	if (filter->daddr_hostname != NULL) {
		kmem_free(filter->daddr_hostname,
		    (strlen(filter->daddr_hostname) + 1));
	}
}

/*
 * filter_name2id(*out_id, name, filter_instance, in_num_filters)
 *
 * looks up name and instance in filter id table
 * checks in_num_filters against max filter boundary
 * if found, returns EEXIST and places the id in out_id
 * if not found, returns ENOENT and places the new id in out_id
 * if no additional filter ids are available, ENOMEM is returned
 */
static int
filter_name2id(unsigned *out_id, char name[], int32_t filter_instance,
    int in_num_filters)
{
	unsigned h;
	int dirty = -1;		/* set dirty to not found */

	if (in_num_filters >= ipgpc_max_num_filters) {
		return (ENOSPC); /* will exceed maximum number of filters */
	}

	/*
	 * search until fid w/ matching name is found or clean space is found
	 * if clean space is found, return first dirty space found or if
	 * none werer found, return clean space
	 */
	h = name_hash(name, ipgpc_max_num_filters);
	while ((ipgpc_fid_list[h].info != 0) &&
	    ((ipgpc_fid_list[h].filter.filter_instance != filter_instance) ||
	    (strcmp(name, ipgpc_fid_list[h].filter.filter_name) != 0))) {
		if (dirty == -1) { /* this is the first dirty space */
			if (ipgpc_fid_list[h].info == -1) { /* dirty */
				dirty = h;
			}
		}
		h = (h + 1) % ipgpc_max_num_filters;
	}
	/*
	 * check to see if searching stopped because a clean spot was found
	 * and a dirty space was seen before
	 */
	if ((dirty != -1) && (ipgpc_fid_list[h].info == 0)) {
		*out_id = dirty;
		return (ENOENT); /* name does not exist in table */
	} else if (ipgpc_fid_list[h].info == 0) {
		*out_id = h;
		return (ENOENT); /* name does not exist in table */
	} else {
		*out_id = h;
		if (ipgpc_fid_list[h].info == -1) {
			return (ENOENT);
		} else {
			return (EEXIST); /* name exists in table */
		}
	}
}

/*
 * class_name2id(*out_id, name, in_num_classes)
 *
 * looks up name in class id table
 * checks in_num_classes against max class boundry
 * if found, returns EEXIST and places the id in out_id
 * if not found, returns ENOENT and places the new id in out_id
 * if no additional class ids are available, ENOSPC is returned
 */
static int
class_name2id(unsigned *out_id, char name[], int in_num_classes)
{
	unsigned h;
	int dirty = -1;		/* set dirty to not found */

	if (in_num_classes >= ipgpc_max_num_classes) {
		return (ENOSPC); /* will exceed maximum number of classes */
	}

	/*
	 * search until cid w/ matching name is found or clean space is found
	 * if clean space is found, return first dirty space found or if
	 * none were found, return clean space
	 */
	h = name_hash(name, ipgpc_max_num_classes);
	while ((ipgpc_cid_list[h].info != 0) &&
	    (strcmp(name, ipgpc_cid_list[h].aclass.class_name) != 0)) {
		if (dirty == -1) { /* this is the first dirty space */
			if (ipgpc_cid_list[h].info == -1) { /* dirty */
				dirty = h;
			}
		}
		h = (h + 1) % ipgpc_max_num_classes;
	}
	/*
	 * check to see if searching stopped because a clean spot was found
	 * and a dirty space was seen before
	 */
	if ((dirty != -1) && (ipgpc_cid_list[h].info == 0)) {
		*out_id = dirty;
		return (ENOENT); /* name does not exist in table */
	} else if (ipgpc_cid_list[h].info == 0) {
		*out_id = h;
		return (ENOENT); /* name does not exist in table */
	} else {
		*out_id = h;
		if (ipgpc_cid_list[h].info == -1) { /* name did exist */
			return (ENOENT); /* name does not exist in table */
		} else {
			return (EEXIST); /* name exists in table */
		}
	}
}

/*
 * ipgpc_parse_filter(filter, nvlp)
 *
 * given a name value pair list, a filter structure is parsed.  A valid
 * filter must have a filter_name and originator id.  Any value that is not
 * present, will be given the default wildcard value for that selector
 */
int
ipgpc_parse_filter(ipgpc_filter_t *filter, nvlist_t *nvlp)
{
	uint_t nelem = 4;	/* an IPv6 address is an uint32_t array[4] */
	uint32_t *mask;
	uint32_t *addr;
	char *s;
	int i;
	in6_addr_t zeroaddr = IN6ADDR_ANY_INIT;

	/* parse filter name */
	if (nvlist_lookup_string(nvlp, CLASSIFIER_FILTER_NAME, &s) != 0) {
		return (EINVAL); /* filter name is missing, error */
	}

	/* parse originator */
	if (nvlist_lookup_uint32(nvlp, IPP_CONFIG_ORIGINATOR,
	    &filter->originator) != 0) {
		ipgpc0dbg(("ipgpc_parse_filter: originator missing"));
		return (EINVAL);
	}

	/* check for max name length */
	if ((strlen(s) + 1) > MAXNAMELEN) {
		ipgpc0dbg(("ipgpc_parse_filter: filter name length > " \
		    "MAXNAMELEN"));
		return (EINVAL);
	}

	bcopy(s, filter->filter_name, (strlen(s) + 1));

	/* parse uid */
	if (nvlist_lookup_uint32(nvlp, IPGPC_UID, &filter->uid) != 0) {
		filter->uid = (uid_t)IPGPC_WILDCARD;
	}

	/* parse projid */
	if (nvlist_lookup_int32(nvlp, IPGPC_PROJID, &filter->projid) != 0) {
		filter->projid = IPGPC_WILDCARD;
	}

	/* parse if_index */
	if (nvlist_lookup_uint32(nvlp, IPGPC_IF_INDEX, &filter->if_index)
	    != 0) {
		filter->if_index = 0;
	}

	/* parse direction */
	if (nvlist_lookup_uint32(nvlp, IPGPC_DIR, &filter->direction) != 0) {
		filter->direction = 0;
	}

	/* parse proto */
	if (nvlist_lookup_byte(nvlp, IPGPC_PROTO, &filter->proto) != 0) {
		filter->proto = 0;
	}

	/*
	 * parse dsfield mask, if mask is present and dsfield value is not,
	 * then this is an invalid filter configuration
	 */
	if (nvlist_lookup_byte(nvlp, IPGPC_DSFIELD_MASK, &filter->dsfield_mask)
	    == 0) {
		/* parse dsfield */
		if (nvlist_lookup_byte(nvlp, IPGPC_DSFIELD, &filter->dsfield)
		    != 0) {
			ipgpc0dbg(("ipgpc_parse_filter: dsfield missing" \
			    " when dsfield_mask 0x%x is present",
			    filter->dsfield_mask));
			return (EINVAL);
		}
	} else {
		filter->dsfield_mask = 0;
		/* check to see if user added dsfield, but not dsfield_mask */
		if (nvlist_lookup_byte(nvlp, IPGPC_DSFIELD, &filter->dsfield)
		    == 0) {
			ipgpc0dbg(("ipgpc_parse_filter: dsfield_mask missing" \
			    " when dsfield 0x%x is present",
			    filter->dsfield));
			return (EINVAL);
		}
		filter->dsfield = 0;
	}

	/* parse source port */
	if (nvlist_lookup_uint16(nvlp, IPGPC_SPORT, &filter->sport) != 0) {
		filter->sport = 0;
	}

	/*
	 * parse source port mask, mask and value must be present, or neither
	 */
	if (nvlist_lookup_uint16(nvlp, IPGPC_SPORT_MASK, &filter->sport_mask)
	    != 0) {
		if (filter->sport != 0) {
			ipgpc0dbg(("ipgpc_parse_filter: sport_mask missing " \
			    "to mask sport %u", filter->sport));
			return (EINVAL);
		}
		filter->sport_mask = 0;
	} else {		/* sport mask is present */
		if (filter->sport == 0) {
			ipgpc0dbg(("ipgpc_parse_filter: sport missing " \
			    "when sport_mask %u is present",
			    filter->sport_mask));
			return (EINVAL);
		}
	}

	/* check for non-continuous mask */
	if (!iscontinuousmask(filter->sport_mask, BITLENGTH(uint16_t))) {
		ipgpc0dbg(("ipgpc_parse_filter: sport_mask is " \
		    "non-continuous"));
		return (EINVAL);
	}

	/* parse destination port */
	if (nvlist_lookup_uint16(nvlp, IPGPC_DPORT, &filter->dport) != 0) {
		filter->dport = 0;
	}

	/*
	 * parse destination port mask, mask and value must be present,
	 * or neither
	 */
	if (nvlist_lookup_uint16(nvlp, IPGPC_DPORT_MASK, &filter->dport_mask)
	    != 0) {
		if (filter->dport != 0) {
			ipgpc0dbg(("ipgpc_parse_filter: dport_mask missing " \
			    "to mask dport %u", filter->dport));
			return (EINVAL);
		}
		filter->dport_mask = 0;
	} else {		/* dport mask is present */
		if (filter->dport == 0) {
			ipgpc0dbg(("ipgpc_parse_filter: dport missing " \
			    "when dport_mask %u is present",
			    filter->dport_mask));
			return (EINVAL);
		}
	}

	/* check for non-continuous mask */
	if (!iscontinuousmask(filter->dport_mask, BITLENGTH(uint16_t))) {
		ipgpc0dbg(("ipgpc_parse_filter: dport_mask is " \
		    "non-continuous"));
		return (EINVAL);
	}

	/* parse precedence */
	if (nvlist_lookup_uint32(nvlp, IPGPC_PRECEDENCE, &filter->precedence)
	    != 0) {
		filter->precedence = UINT_MAX; /* worst precedence */
	}

	/* parse priority */
	if (nvlist_lookup_uint32(nvlp, IPGPC_PRIORITY, &filter->priority)
	    != 0) {
		filter->priority = 0; /* worst priority */
	}

	/* parse filter type */
	if (nvlist_lookup_byte(nvlp, IPGPC_FILTER_TYPE, &filter->filter_type)
	    != 0) {
		filter->filter_type = IPGPC_GENERIC_FLTR;
	}

	/* parse filter instance */
	if (nvlist_lookup_int32(nvlp, IPGPC_FILTER_INSTANCE,
	    &filter->filter_instance) != 0) {
		filter->filter_instance = -1;
	}

	/* parse filter private field */
	if (nvlist_lookup_string(nvlp, IPGPC_FILTER_PRIVATE, &s) != 0) {
		filter->filter_comment = NULL;
	} else {
		filter->filter_comment = kmem_alloc((strlen(s) + 1), KM_SLEEP);
		(void) strcpy(filter->filter_comment, s);
	}

	/*
	 * parse source address mask, if address is present, mask must be
	 * present
	 */
	if (nvlist_lookup_uint32_array(nvlp, IPGPC_SADDR_MASK, &mask, &nelem)
	    != 0) {
		/* check if source address is present */
		if (nvlist_lookup_uint32_array(nvlp, IPGPC_SADDR, &addr,
		    &nelem) == 0) {
			ipgpc0dbg(("ipgpc_parse_filter: source address mask " \
			    "missing"));
			return (EINVAL);
		} else {	/* both saddr and saddr_mask absent */
			bcopy(zeroaddr.s6_addr32, filter->saddr.s6_addr32,
			    sizeof (filter->saddr.s6_addr32));
		}
		bcopy(zeroaddr.s6_addr32, filter->saddr_mask.s6_addr32,
		    sizeof (filter->saddr_mask.s6_addr32));
	} else {		/* saddr_mask present */
		/* parse source address */
		if (nvlist_lookup_uint32_array(nvlp, IPGPC_SADDR, &addr,
		    &nelem) != 0) {
			ipgpc0dbg(("ipgpc_parse_filter: source address " \
			    "missing"));
			return (EINVAL);
		} else {	/* saddr present */
			bcopy(addr, filter->saddr.s6_addr32,
			    sizeof (filter->saddr.s6_addr32));
		}
		bcopy(mask, filter->saddr_mask.s6_addr32,
		    sizeof (filter->saddr_mask.s6_addr32));
	}

	/* check for non-continuous mask */
	if ((filter->filter_type == IPGPC_V6_FLTR) ||
	    (filter->filter_type == IPGPC_GENERIC_FLTR)) {
		boolean_t zero_found = B_FALSE;
		for (i = 0; i < 4; ++i) {
			if (filter->saddr_mask.s6_addr32[i] == 0) {
				zero_found = B_TRUE;
			} else {
				if (zero_found) {
					ipgpc0dbg(("ipgpc_parse_filter: "
					    "saddr_mask is non-continuous"));
					return (EINVAL);
				}
			}
			if (!iscontinuousmask(filter->saddr_mask.s6_addr32[i],
			    IP_ABITS)) {
				ipgpc0dbg(("ipgpc_parse_filter: saddr_mask " \
				    "is non-continuous"));
				return (EINVAL);
			}
		}
	} else {		/* IPGPC_V4_FLTR */
		if (!iscontinuousmask((V4_PART_OF_V6(filter->saddr_mask)),
		    IP_ABITS)) {
			ipgpc0dbg(("ipgpc_parse_filter: saddr_mask is " \
			    "non-continuous"));
			return (EINVAL);
		}
	}

	/* parse source address hostname */
	if (nvlist_lookup_string(nvlp, IPGPC_SADDR_HOSTNAME, &s) != 0) {
		filter->saddr_hostname = NULL;
	} else {
		filter->saddr_hostname = kmem_alloc((strlen(s) + 1), KM_SLEEP);
		(void) strcpy(filter->saddr_hostname, s);
	}

	/*
	 * parse destination address mask, if address is present, mask must be
	 * present
	 */
	if (nvlist_lookup_uint32_array(nvlp, IPGPC_DADDR_MASK, &mask, &nelem)
	    != 0) {
		/* check if destination address is present */
		if (nvlist_lookup_uint32_array(nvlp, IPGPC_DADDR, &addr,
		    &nelem) == 0) {
			ipgpc0dbg(("ipgpc_parse_filter: destination address " \
			    "mask missing"));
			return (EINVAL);
		} else {	/* both daddr and daddr_mask absent */
			bcopy(zeroaddr.s6_addr32, filter->daddr.s6_addr32,
			    sizeof (filter->daddr.s6_addr32));
		}
		bcopy(zeroaddr.s6_addr32, filter->daddr_mask.s6_addr32,
		    sizeof (filter->daddr_mask.s6_addr32));
	} else {		/* daddr_mask present */
		/* parse destination address */
		if (nvlist_lookup_uint32_array(nvlp, IPGPC_DADDR, &addr,
		    &nelem) != 0) {
			ipgpc0dbg(("ipgpc_parse_filter: destination address " \
			    "missing"));
			return (EINVAL);
		} else {	/* daddr present */
			bcopy(addr, filter->daddr.s6_addr32,
			    sizeof (filter->daddr.s6_addr32));
		}
		bcopy(mask, filter->daddr_mask.s6_addr32,
		    sizeof (filter->daddr_mask.s6_addr32));
	}

	/* check for non-continuous mask */
	if ((filter->filter_type == IPGPC_V6_FLTR) ||
	    (filter->filter_type == IPGPC_GENERIC_FLTR)) {
		boolean_t zero_found = B_FALSE;
		for (i = 0; i < 4; ++i) {
			if (filter->daddr_mask.s6_addr32[i] == 0) {
				zero_found = B_TRUE;
			} else {
				if (zero_found) {
					ipgpc0dbg(("ipgpc_parse_filter: "
					    "daddr_mask is non-continuous"));
					return (EINVAL);
				}
			}
			if (!iscontinuousmask(filter->daddr_mask.s6_addr32[i],
			    IP_ABITS)) {
				ipgpc0dbg(("ipgpc_parse_filter: daddr_mask " \
				    "is non-continuous"));
				return (EINVAL);
			}
		}
	} else {		/* IPGPC_V4_FLTR */
		if (!iscontinuousmask((V4_PART_OF_V6(filter->daddr_mask)),
		    IP_ABITS)) {
			ipgpc0dbg(("ipgpc_parse_filter: daddr_mask is " \
			    "non-continuous"));
			return (EINVAL);
		}
	}

	/* parse destination address hostname */
	if (nvlist_lookup_string(nvlp, IPGPC_DADDR_HOSTNAME, &s) != 0) {
		filter->daddr_hostname = NULL;
	} else {
		filter->daddr_hostname = kmem_alloc((strlen(s) + 1), KM_SLEEP);
		(void) strcpy(filter->daddr_hostname, s);
	}

	return (0);
}

/*
 * iscontinuousmask(mask, len)
 *
 * Searches a given mask of length len from MSB to LSB looking for a zero
 * bit followed by one bit.  A continuous mask must be a string of zero or
 * more ones followed by a string of zero or more zeros, which would return
 * B_TRUE.  Otherwise, it is not continuous and this function returns B_FALSE.
 */
static boolean_t
iscontinuousmask(uint32_t mask, uint8_t len)
{
	uint8_t pos;
	boolean_t zero_found = B_FALSE;

	for (pos = len; pos > 0; --pos) {
		if (EXTRACTBIT(mask, (pos - 1), len) == 0) {
			zero_found = B_TRUE;
		} else {
			if (zero_found) {
				return (B_FALSE);
			}
		}
	}
	return (B_TRUE);
}


/*
 * insertfid(filter_id, filter, class_id)
 *
 * creates a filter id (fid) structure for filter with filter_id.
 * filter is associated with the input class id
 * it is assumed that a fid will not be inserted for a filter that already
 * exists by the same name.
 */
static void
insertfid(int filter_id, ipgpc_filter_t *filter, uint_t class_id)
{
	ipgpc_fid_list[filter_id].info = 1;
	ipgpc3dbg(("insert_fid: adding filter %s to class %s",
	    filter->filter_name,
	    ipgpc_cid_list[class_id].aclass.class_name));
	ipgpc_fid_list[filter_id].class_id = class_id;
	ipgpc_fid_list[filter_id].filter = *filter;
	ipgpc_fid_list[filter_id].insert_map = 0;
}


static void
common_addfilter(fid_t *fid, int filter_id)
{
	/* start trie inserts */
	/* add source port selector */
	if (t_insert(&ipgpc_trie_list[IPGPC_TRIE_SPORTID], filter_id,
	    fid->filter.sport, fid->filter.sport_mask) == NORMAL_VALUE) {
		fid->insert_map |= SPORT_MASK;
	}
	/* add destination port selector */
	if (t_insert(&ipgpc_trie_list[IPGPC_TRIE_DPORTID], filter_id,
	    fid->filter.dport, fid->filter.dport_mask) == NORMAL_VALUE) {
		fid->insert_map |= DPORT_MASK;
	}
	/* end trie inserts */

	/* add diffserv field selector */
	mutex_enter(&ipgpc_ds_table_id.lock);
	if (ba_insert(&ipgpc_ds_table_id, filter_id, fid->filter.dsfield,
	    fid->filter.dsfield_mask) == NORMAL_VALUE) {
		fid->insert_map |= DS_MASK;
	}
	mutex_exit(&ipgpc_ds_table_id.lock);

	/* start table inserts */
	mutex_enter(&ipgpc_table_list_lock);
	/* add protocol selector */
	if (ht_insert(&ipgpc_table_list[PROTOID_IDX], filter_id,
	    fid->filter.proto) == NORMAL_VALUE) {
		fid->insert_map |= PROTO_MASK;
	}

	/* add UID selector */
	if (ht_insert(&ipgpc_table_list[UID_IDX], filter_id, fid->filter.uid)
	    == NORMAL_VALUE) {
		fid->insert_map |= UID_MASK;
	}

	/* add PROJID selector */
	if (ht_insert(&ipgpc_table_list[PROJID_IDX], filter_id,
	    fid->filter.projid) == NORMAL_VALUE) {
		fid->insert_map |= PROJID_MASK;
	}

	/* add interface index selector */
	if (ht_insert(&ipgpc_table_list[IF_IDX], filter_id,
	    fid->filter.if_index) == NORMAL_VALUE) {
		fid->insert_map |= IF_MASK;
	}

	/* add direction selector */
	if (ht_insert(&ipgpc_table_list[DIR_IDX], filter_id,
	    fid->filter.direction) == NORMAL_VALUE) {
		fid->insert_map |= DIR_MASK;
	}
	mutex_exit(&ipgpc_table_list_lock);
	/* end table inserts */
}

static void
v4_addfilter(fid_t *fid, int filter_id)
{
	/* add IPv4 source address selector */
	if (t_insert(&ipgpc_trie_list[IPGPC_TRIE_SADDRID], filter_id,
	    V4_PART_OF_V6(fid->filter.saddr),
	    V4_PART_OF_V6(fid->filter.saddr_mask)) == NORMAL_VALUE) {
		fid->insert_map |= SADDR_MASK;
	}

	/* add IPv4 destination address selector */
	if (t_insert(&ipgpc_trie_list[IPGPC_TRIE_DADDRID], filter_id,
	    V4_PART_OF_V6(fid->filter.daddr),
	    V4_PART_OF_V6(fid->filter.daddr_mask)) == NORMAL_VALUE) {
		fid->insert_map |= DADDR_MASK;
	}
}

static void
v6_addfilter(fid_t *fid, int filter_id)
{
	/* add IPv6 source address selector */
	if (t_insert6(&ipgpc_trie_list[IPGPC_TRIE_SADDRID6], filter_id,
	    fid->filter.saddr, fid->filter.saddr_mask) == NORMAL_VALUE) {
		fid->insert_map |= SADDR6_MASK;
	}

	/* add IPv6 destination address selector */
	if (t_insert6(&ipgpc_trie_list[IPGPC_TRIE_DADDRID6], filter_id,
	    fid->filter.daddr, fid->filter.daddr_mask) == NORMAL_VALUE) {
		fid->insert_map |= DADDR6_MASK;
	}
}

/*
 * ipgpc_addfilter(filter, class_name, flags)
 *
 * add the specified filter and associate it with the specified class
 * name
 * - add filter id to filter list
 * - add filter keys to selector structures
 * - ENOENT is returned if class does not exist
 * - EEXIST is returned if add failed because filter name exists
 * - ENOMEM is returned if no memory is available to add a new filter
 * - EINVAL if filter.filter_type is invalid
 * - 0 is returned on success
 * flags is unused currently
 */
/* ARGSUSED1 */
int
ipgpc_addfilter(ipgpc_filter_t *filter, char *class_name, ipp_flags_t flags)
{
	unsigned filter_id;
	int err = 0;
	fid_t *fid;
	unsigned class_id;

	err = class_name2id(&class_id, class_name, ipgpc_num_cls);
	if (err != EEXIST) {
		ipgpc0dbg(("ipgpc_addfilter: class lookup error %d", err));
		return (err);
	}
	mutex_enter(&ipgpc_fid_list_lock);
	/* make sure filter does not already exist */
	if ((err = filter_name2id(&filter_id, filter->filter_name,
	    filter->filter_instance, ipgpc_num_fltrs + 1)) == EEXIST) {
		ipgpc0dbg(("ipgpc_addfilter: filter name %s already exists",
		    filter->filter_name));
		mutex_exit(&ipgpc_fid_list_lock);
		return (err);
	} else if (err == ENOSPC) {
		ipgpc0dbg(("ipgpc_addfilter: can not add filter %s, " \
		    "ipgpc_max_num_filteres has been reached",
		    filter->filter_name));
		mutex_exit(&ipgpc_fid_list_lock);
		return (err);
	}
	insertfid(filter_id, filter, class_id);

	fid = &ipgpc_fid_list[filter_id];
	/* add filter id to selector structures */
	switch (fid->filter.filter_type) {
	case IPGPC_GENERIC_FLTR:
		/* add filter id to all selectors */
		common_addfilter(fid, filter_id);
		v4_addfilter(fid, filter_id);
		v6_addfilter(fid, filter_id);
		break;
	case IPGPC_V4_FLTR:
		/* add filter to common and V4 selectors */
		common_addfilter(fid, filter_id);
		v4_addfilter(fid, filter_id);
		break;
	case IPGPC_V6_FLTR:
		/* add filter to common and V6 selectors */
		common_addfilter(fid, filter_id);
		v6_addfilter(fid, filter_id);
		break;
	default:
		ipgpc0dbg(("ipgpc_addfilter(): invalid filter type %d",
		    fid->filter.filter_type));
		mutex_exit(&ipgpc_fid_list_lock);
		return (EINVAL);
	}
	/* check to see if this is a catch all filter, which we reject */
	if (fid->insert_map == 0) {
		ipgpc0dbg(("ipgpc_addfilter(): filter %s rejected because " \
		    "catch all filters are not supported\n",
		    filter->filter_name));
		/* cleanup what we allocated */
		/* remove filter from filter list */
		ipgpc_fid_list[filter_id].info = -1;
		ipgpc_fid_list[filter_id].filter.filter_name[0] = '\0';
		reset_dontcare_stats();	/* need to fixup stats */
		mutex_exit(&ipgpc_fid_list_lock);
		return (EINVAL);
	} else {		/* associate filter with class */
		mutex_enter(&ipgpc_cid_list_lock);
		(void) ipgpc_list_insert(&ipgpc_cid_list[class_id].filter_list,
		    filter_id);
		mutex_exit(&ipgpc_cid_list_lock);
	}
	mutex_exit(&ipgpc_fid_list_lock);
	atomic_add_long(&ipgpc_num_fltrs, 1);
	ipgpc3dbg(("ipgpc_addfilter: adding filter %s", filter->filter_name));
	return (0);
}

/*
 * reset_dontcare_stats()
 *
 * when an insertion fails because zero selectors are specified in a filter
 * the number of dontcare's recorded for each selector structure needs to be
 * decremented
 */
static void
reset_dontcare_stats(void)
{
	int i;

	for (i = 0; i < NUM_TRIES; ++i) {
		atomic_add_32(&ipgpc_trie_list[i].stats.num_dontcare, -1);
	}
	for (i = 0; i < NUM_TABLES; ++i) {
		atomic_add_32(&ipgpc_table_list[i].stats.num_dontcare, -1);
	}
	atomic_add_32(&ipgpc_ds_table_id.stats.num_dontcare, -1);
}

/*
 * ipgpc_parse_class(out_class, nvlp)
 *
 * Given a name value pair list, a class structure will be parsed.
 * To be a valid class, the class name, originator id and next action name
 * must be present. gather_stats is optional, if absent default value is used
 */
int
ipgpc_parse_class(ipgpc_class_t *out_class, nvlist_t *nvlp)
{
	char *name;
	size_t name_len;
	uint32_t gather_stats;

	/* parse class name */
	if (nvlist_lookup_string(nvlp, CLASSIFIER_CLASS_NAME, &name) != 0) {
		return (EINVAL); /* class name missing, error */
	}

	name_len = strlen(name);
	/* check for max name length */
	if ((name_len + 1) > MAXNAMELEN) {
		ipgpc0dbg(("ipgpc_parse_class: class name length > " \
		    "MAXNAMELEN"));
		return (EINVAL);
	}

	bcopy(name, out_class->class_name, (name_len + 1));

	/* parse originator */
	if (nvlist_lookup_uint32(nvlp, IPP_CONFIG_ORIGINATOR,
	    &out_class->originator) != 0) {
		ipgpc0dbg(("ipgpc_parse_class: originator missing"));
		return (EINVAL);
	}

	/* parse action name */
	if (nvlist_lookup_string(nvlp, CLASSIFIER_NEXT_ACTION, &name) != 0) {
		return (EINVAL); /* action name missing, error */
	}
	if ((out_class->next_action = ipp_action_lookup(name))
	    == IPP_ACTION_INVAL) {
		ipgpc0dbg(("ipgpc_parse_class: invalid action name %s", name));
		return (EINVAL);
	}

	/* parse gather stats boolean */
	if (nvlist_lookup_uint32(nvlp, CLASSIFIER_CLASS_STATS_ENABLE,
	    &gather_stats) != 0) {
		/* stats turned off by default */
		out_class->gather_stats = B_FALSE;
	} else {
		out_class->gather_stats = (boolean_t)gather_stats;
	}
	return (0);
}


/*
 * ipgpc_addclass(in_class, flags)
 *
 * adds the given class to the class id list.
 * - EEXIST is returned if class of same name already exists
 * - ENOSPC if there is no more available memory to add class
 * - 0 for success
 * flags is currently unused
 */
/* ARGSUSED */
int
ipgpc_addclass(ipgpc_class_t *in_class, ipp_flags_t flags) {
	int class_id;
	int err;

	if ((err = insertcid(in_class, &class_id)) == EEXIST) {
		ipgpc0dbg(("ipgpc_addclass: class name %s already exists",
		    in_class->class_name));
		return (err);
	} else if (err == ENOSPC) {
		ipgpc0dbg(("ipgpc_addclass: can not add class %s, " \
		    "ipgpc_max_num_classes has been reached",
		    in_class->class_name));
		return (err);
	}
	/* add reference to next action */
	if ((err = ipp_action_ref(ipgpc_aid, in_class->next_action, 0)) != 0) {
		/*
		 * the action id we want to reference must have been
		 * destroyed before we could reference it. remove class
		 * and fail.
		 */
		removecid(class_id);
		return (err);
	}
	return (0);
}



/*
 * class_statinit(in_class, in_class_id)
 *
 * for the given class, create stats entries to record
 * - next action id
 * - number of bytes that matched this class
 * - number of packets that matched this class
 * - time in hrtime of last match for this class
 * any failures are returned, zero on success
 */
static int
class_statinit(ipgpc_class_t *in_class, int in_class_id)
{
	int rc;
	ipp_stat_t *ipp_cl_stats;
	classstats_t *clsnames = NULL;

	/* create stat structure */
	if ((rc = ipp_stat_create(ipgpc_aid, in_class->class_name, 3,
	    update_class_stats, &ipgpc_cid_list[in_class_id].stats,
	    &ipp_cl_stats)) != 0) {
		ipgpc0dbg(("class_statinit: error creating ipp_stat entry"));
		return (rc);
	}

	ASSERT(ipp_cl_stats != NULL);
	clsnames = (classstats_t *)ipp_cl_stats->ipps_data;
	ASSERT(clsnames != NULL);

	/* create stats entry */
	bzero(&ipgpc_cid_list[in_class_id].stats,
	    sizeof (ipgpc_class_stats_t));

	/* set next action id */
	ipgpc_cid_list[in_class_id].stats.next_action =
	    ipgpc_cid_list[in_class_id].aclass.next_action;

	if ((rc = ipp_stat_named_init(ipp_cl_stats, "nbytes",
	    IPP_STAT_UINT64, &clsnames->nbytes)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipp_cl_stats, "npackets",
	    IPP_STAT_UINT64, &clsnames->npackets)) != 0) {
		return (rc);
	}
	if ((rc = ipp_stat_named_init(ipp_cl_stats, "last_match",
	    IPP_STAT_INT64, &clsnames->last_match)) != 0) {
		return (rc);
	}

	/* make reference to kstat structure, for removal */
	ipgpc_cid_list[in_class_id].cl_stats = ipp_cl_stats;
	ipp_stat_install(ipp_cl_stats);
	return (0);
}

/*
 * insertcid(in_class, out_class_id)
 *
 * creates a class id (cid) structure for in_class, if in_class name
 * does not exist already.  id is associated with in_class. the internal
 * id of the cid associated with in_class is returned in out_class_id
 * - ENOENT is returned if in_class->class_name does not already exist
 * - EEXIST is returned if in_class->class_name does already exist
 * - ENOSPC is returned if by adding this class, the ipgpc_max_num_classes
 *   will be exceeded.
 */
static int
insertcid(ipgpc_class_t *in_class, int *out_class_id)
{
	int err, rc;
	unsigned class_id;

	mutex_enter(&ipgpc_cid_list_lock);
	/* see if entry already exists for class */
	if ((err = class_name2id(&class_id, in_class->class_name,
	    ipgpc_num_cls + 1)) == ENOENT) {
		/* create new filter list for new class */
		ipgpc_cid_list[class_id].info = 1;
		ipgpc_cid_list[class_id].aclass = *in_class;
		if (in_class->gather_stats == B_TRUE) {
			/* init kstat entry */
			if ((rc = class_statinit(in_class, class_id)) != 0) {
				ipgpc_cid_list[class_id].info = -1;
				ipgpc0dbg(("insertcid: "
				    "class_statinit failed with error %d", rc));
				mutex_exit(&ipgpc_cid_list_lock);
				return (rc);
			}
		} else {
			ipgpc_cid_list[class_id].cl_stats = NULL;
		}
		ipgpc3dbg(("insertcid: adding class %s",
		    in_class->class_name));
		bcopy(in_class->class_name,
		    ipgpc_cid_list[class_id].aclass.class_name, MAXNAMELEN);
		ipgpc_cid_list[class_id].filter_list = NULL;
		atomic_add_long(&ipgpc_num_cls, 1);
	} else {
		ipgpc0dbg(("insertcid: class name lookup error %d", err));
		mutex_exit(&ipgpc_cid_list_lock);
		return (err);
	}
	mutex_exit(&ipgpc_cid_list_lock);
	*out_class_id = class_id;
	return (err);
}

/*
 * common_removefilter(in_filter_id, fid)
 *
 * removes in_filter_id from each of the common selector structures
 */
static void
common_removefilter(int in_filter_id, fid_t *fid)
{
	/* start trie removes */
	t_remove(&ipgpc_trie_list[IPGPC_TRIE_SPORTID], in_filter_id,
	    fid->filter.sport, fid->filter.sport_mask);
	/* remove id from destination port trie */
	t_remove(&ipgpc_trie_list[IPGPC_TRIE_DPORTID], in_filter_id,
	    fid->filter.dport, fid->filter.dport_mask);
	/* end trie revmoves */

	/* remove id from DiffServ field ba table */
	mutex_enter(&ipgpc_ds_table_id.lock);
	ba_remove(&ipgpc_ds_table_id, in_filter_id, fid->filter.dsfield,
	    fid->filter.dsfield_mask);
	mutex_exit(&ipgpc_ds_table_id.lock);

	/* start table removes */
	mutex_enter(&ipgpc_table_list_lock);
	/* remove id from protocol table */
	ht_remove(&ipgpc_table_list[PROTOID_IDX], in_filter_id,
	    fid->filter.proto);
	/* remove id from UID table */
	ht_remove(&ipgpc_table_list[UID_IDX], in_filter_id, fid->filter.uid);
	/* remove id from PROJID table */
	ht_remove(&ipgpc_table_list[PROJID_IDX], in_filter_id,
	    fid->filter.projid);
	/* remove id from interface id table */
	ht_remove(&ipgpc_table_list[IF_IDX], in_filter_id,
	    fid->filter.if_index);
	/* remove id from direction table */
	ht_remove(&ipgpc_table_list[DIR_IDX], in_filter_id,
	    fid->filter.direction);
	mutex_exit(&ipgpc_table_list_lock);
	/* end table removes */
}

/*
 * v4_removefilter(in_filter_id, fid)
 *
 * removes id from IPV4 specific structures
 */
static void
v4_removefilter(int in_filter_id, fid_t *fid)
{
	/* remove id from source address trie */
	t_remove(&ipgpc_trie_list[IPGPC_TRIE_SADDRID], in_filter_id,
	    V4_PART_OF_V6(fid->filter.saddr),
	    V4_PART_OF_V6(fid->filter.saddr_mask));
	/* remove id from destination address trie */
	t_remove(&ipgpc_trie_list[IPGPC_TRIE_DADDRID], in_filter_id,
	    V4_PART_OF_V6(fid->filter.daddr),
	    V4_PART_OF_V6(fid->filter.daddr_mask));
}

/*
 * v6_removefilter(in_filter_id, fid)
 *
 * removes id from IPV6 specific structures
 */
static void
v6_removefilter(int in_filter_id, fid_t *fid)
{
	/* remove id from source address trie */
	t_remove6(&ipgpc_trie_list[IPGPC_TRIE_SADDRID6], in_filter_id,
	    fid->filter.saddr, fid->filter.saddr_mask);
	/* remove id from destination address trie */
	t_remove6(&ipgpc_trie_list[IPGPC_TRIE_DADDRID6], in_filter_id,
	    fid->filter.daddr, fid->filter.daddr_mask);
}

/*
 * ipgpc_removefilter(filter_name, filter_instance, flags)
 *
 * remove the filter associated with the specified name and instance
 * - remove filter keys from all search tries
 * - remove from filter id list
 * - ENOENT is returned if filter name does not exist
 * - returns 0 on success
 */
/* ARGSUSED */
int
ipgpc_removefilter(char *filter_name, int32_t filter_instance,
    ipp_flags_t flags)
{
	unsigned filter_id;
	fid_t *fid;
	int rc;

	/* check to see if any filters are loaded */
	if (ipgpc_num_fltrs == 0) {
		return (ENOENT);
	}

	mutex_enter(&ipgpc_fid_list_lock);
	/* lookup filter name, only existing filters can be removed */
	if ((rc = filter_name2id(&filter_id, filter_name, filter_instance,
	    ipgpc_num_fltrs)) != EEXIST) {
		mutex_exit(&ipgpc_fid_list_lock);
		return (rc);
	}
	fid = &ipgpc_fid_list[filter_id];
	switch (fid->filter.filter_type) {
	case IPGPC_GENERIC_FLTR:
		common_removefilter(filter_id, fid);
		v4_removefilter(filter_id, fid);
		v6_removefilter(filter_id, fid);
		break;
	case IPGPC_V4_FLTR:
		common_removefilter(filter_id, fid);
		v4_removefilter(filter_id, fid);
		break;
	case IPGPC_V6_FLTR:
		common_removefilter(filter_id, fid);
		v6_removefilter(filter_id, fid);
		break;
	default:
		ipgpc0dbg(("ipgpc_removefilter(): invalid filter type %d",
		    fid->filter.filter_type));
		mutex_exit(&ipgpc_fid_list_lock);
		return (EINVAL);
	}
	/* remove filter from filter list */
	ipgpc_fid_list[filter_id].info = -1;
	ipgpc_fid_list[filter_id].insert_map = 0;
	ipgpc_fid_list[filter_id].filter.filter_name[0] = '\0';
	ipgpc_filter_destructor(&ipgpc_fid_list[filter_id].filter);
	mutex_exit(&ipgpc_fid_list_lock);
	/* remove filter id from class' list of filters */
	remove_from_cid_filter_list(ipgpc_fid_list[filter_id].class_id,
	    filter_id);
	atomic_add_long(&ipgpc_num_fltrs, -1);
	return (0);
}

/*
 * removecid(in_class_id)
 *
 * removes the cid entry from the cid list and frees allocated structures
 */
static void
removecid(int in_class_id)
{
	ipgpc_cid_list[in_class_id].info = -1;
	ipgpc_cid_list[in_class_id].aclass.class_name[0] = '\0';
	ipgpc_cid_list[in_class_id].aclass.next_action = -1;
	/* delete kstat entry */
	if (ipgpc_cid_list[in_class_id].cl_stats != NULL) {
		ipp_stat_destroy(ipgpc_cid_list[in_class_id].cl_stats);
		ipgpc_cid_list[in_class_id].cl_stats = NULL;
	}
	/* decrement total number of classes loaded */
	atomic_add_long(&ipgpc_num_cls, -1);
}

/*
 * remove_from_cid_filter_list(in_class_id, in_filter_id)
 *
 * removes the input filter_id from the filter_list of the class associated
 * with the input class_id
 */
static void
remove_from_cid_filter_list(int in_class_id, int in_filter_id)
{
	cid_t *cid = &ipgpc_cid_list[in_class_id];

	if (cid->filter_list != NULL) {
		(void) ipgpc_list_remove(&cid->filter_list, in_filter_id);
	}
}

/*
 * ipgpc_removeclass(class_name)
 *
 * removes a class and all the filters that point to it (ouch!)
 * - returns 0 on success
 * - ENOENT if class name does not exist
 * - ENOTSUP if class name equals 'default'
 */
int
ipgpc_removeclass(char *class_name, ipp_flags_t flags)
{
	unsigned class_id;
	element_node_t *anode = NULL;
	element_node_t *tnode = NULL;
	fid_t *fid = NULL;
	ipp_action_id_t old_next_action;
	int rc;

	/* check to see if any classes are loaded */
	if (ipgpc_num_cls == 0) {
		return (ENOENT);
	}

	mutex_enter(&ipgpc_cid_list_lock); /* set lock */
	/* lookup class name, only classes that exist can be removed */
	if ((rc = class_name2id(&class_id, class_name, (ipgpc_num_cls - 1)))
	    != EEXIST) {
		mutex_exit(&ipgpc_cid_list_lock); /* release lock */
		return (rc);
	}
	if (class_id == ipgpc_def_class_id) {
		ipgpc0dbg(("ipgpc_removeclass(): default class may not be " \
		    "removed"));
		mutex_exit(&ipgpc_cid_list_lock); /* release lock */
		return (ENOTSUP);
	}

	old_next_action = ipgpc_cid_list[class_id].aclass.next_action;
	anode = ipgpc_cid_list[class_id].filter_list;
	while (anode != NULL) {
		fid = &ipgpc_fid_list[anode->id];
		if (ipgpc_fid_list[anode->id].info > 0) {
			anode = anode->next;
			(void) ipgpc_removefilter(fid->filter.filter_name,
			    fid->filter.filter_instance, flags);
		} else {
			tnode = anode;
			anode = anode->next;
			/* free this node */
			kmem_cache_free(element_node_cache, tnode);
		}
	}
	/* remove cid from ipgpc_cid_list and decrement ipgpc_num_cls */
	ipgpc3dbg(("ipgpc_removeclass: class %s has been removed",
	    class_name));
	removecid(class_id);
	mutex_exit(&ipgpc_cid_list_lock); /* release lock */
	rc = ipp_action_unref(ipgpc_aid, old_next_action, flags);
	ASSERT(rc == 0);
	return (0);
}

/*
 * ipgpc_modifyfilter(nvlist, flags)
 *
 * modifies the input filter
 * - if in_class != NULL, filter is associated with that class
 * - EINVAL is returned if filter name does not exist in nvlist
 * - if filter->filter_name does not exist ENOENT is returned
 * - if a class name to associate with is not present in nvlist, then the
 *   previous class association is used
 */
int
ipgpc_modifyfilter(nvlist_t **nvlpp, ipp_flags_t flags)
{
	unsigned filter_id;
	int ret = 0;
	int rc;
	ipgpc_filter_t *filter;
	ipgpc_filter_t old_filter;
	char *name;
	char *s;
	uint_t class_id;

	filter = kmem_zalloc(sizeof (ipgpc_filter_t), KM_SLEEP);
	if ((ret = ipgpc_parse_filter(filter, *nvlpp)) != 0) {
		ipgpc0dbg(("ipgpc_modifyfilter: error %d parsing filter",
		    ret));
		ipgpc_filter_destructor(filter);
		kmem_free(filter, sizeof (ipgpc_filter_t));
		return (ret);
	}

	/* parse class name */
	if (nvlist_lookup_string(*nvlpp, CLASSIFIER_CLASS_NAME, &name)
	    != 0) {
		name = NULL;	/* no class specified */
	}

	/* modify filter entry */
	if ((rc = filter_name2id(&filter_id, filter->filter_name,
	    filter->filter_instance, ipgpc_num_fltrs)) == EEXIST) {
		if (name == NULL) {
			/* set class_name to previous class_name association */
			class_id = ipgpc_fid_list[filter_id].class_id;
			name = ipgpc_cid_list[class_id].aclass.class_name;
		} else {
			if ((ret = class_name2id(&class_id, name,
			    ipgpc_num_cls)) != EEXIST) {
				ipgpc0dbg(("ipgpc_modifyfilter: class does " \
				    "not exist"));
				ipgpc_filter_destructor(filter);
				kmem_free(filter, sizeof (ipgpc_filter_t));
				return (ret);
			}
		}
		/* copy out old filter just in case we need to revert */
		old_filter = ipgpc_fid_list[filter_id].filter;

		/* make copy of filter_comment */
		if (ipgpc_fid_list[filter_id].filter.filter_comment != NULL) {
			s = ipgpc_fid_list[filter_id].filter.filter_comment;
			old_filter.filter_comment =
			    kmem_alloc((strlen(s) + 1), KM_SLEEP);
			(void) strcpy(old_filter.filter_comment, s);
		} else {
			old_filter.filter_comment = NULL;
		}

		/* make copy of saddr_hostname */
		if (ipgpc_fid_list[filter_id].filter.saddr_hostname != NULL) {
			s = ipgpc_fid_list[filter_id].filter.saddr_hostname;
			old_filter.saddr_hostname =
			    kmem_alloc((strlen(s) + 1), KM_SLEEP);
			(void) strcpy(old_filter.saddr_hostname, s);
		} else {
			old_filter.saddr_hostname = NULL;
		}

		/* make copy of daddr_hostname */
		if (ipgpc_fid_list[filter_id].filter.daddr_hostname != NULL) {
			s = ipgpc_fid_list[filter_id].filter.daddr_hostname;
			old_filter.daddr_hostname =
			    kmem_alloc((strlen(s) + 1), KM_SLEEP);
			(void) strcpy(old_filter.daddr_hostname, s);
		} else {
			old_filter.daddr_hostname = NULL;
		}

		/* remove old filter entry */
		ret = ipgpc_removefilter(filter->filter_name,
		    filter->filter_instance, flags);
		if (ret == 0) {	/* no error, add filter */
			ret = ipgpc_addfilter(filter, name, flags);
			if (ret != 0) {
				/* error occurred, free filter fields */
				ipgpc0dbg(("ipgpc_modifyfilter: invalid " \
				    "filter given, unable to modify " \
				    "existing filter %s",
				    filter->filter_name));
				ipgpc_filter_destructor(filter);
				kmem_free(filter, sizeof (ipgpc_filter_t));
				/* revert back to old filter */
				(void) ipgpc_addfilter(&old_filter, name,
				    flags);
				return (ret);
			}
			ipgpc_filter_destructor(&old_filter);
		} else {
			ipgpc0dbg(("ipgpc_modifyfilter: error %d occurred " \
			    "when modifying filter", ret));
			ipgpc_filter_destructor(&old_filter);
			ipgpc_filter_destructor(filter);
			kmem_free(filter, sizeof (ipgpc_filter_t));
			return (ret);
		}
	} else {
		ipgpc0dbg(("ipgpc_modifyfilter: filter lookup error %d", rc));
		return (rc); /* filter name does not exist */
	}
	kmem_free(filter, sizeof (ipgpc_filter_t));
	return (0);
}

/*
 * ipgpc_modifyclass(in_class)
 *
 * if the input class exists, then the action list is modified
 * if the input class does not exist, ENOENT is returned
 */
/* ARGSUSED */
int
ipgpc_modifyclass(nvlist_t **nvlpp, ipp_flags_t flags)
{
	unsigned class_id;
	ipgpc_class_t in_class;
	char *name;
	int rc;
	uint32_t gather_stats;
	boolean_t ref_action = B_FALSE;
	ipp_action_id_t old_next_action;
	size_t name_len;

	/* parse class name */
	if (nvlist_lookup_string(*nvlpp, CLASSIFIER_CLASS_NAME, &name) != 0) {
		return (EINVAL); /* class name missing, error */
	}
	name_len = strlen(name);
	/* check for max name length */
	if ((name_len + 1) > MAXNAMELEN) {
		ipgpc0dbg(("ipgpc_modifyclass: class name length > " \
		    "MAXNAMELEN"));
		return (EINVAL);
	}
	bcopy(name, in_class.class_name, (name_len + 1));

	mutex_enter(&ipgpc_cid_list_lock);
	/* look up class name, only existing classes can be modified */
	if ((rc = class_name2id(&class_id, in_class.class_name,
	    ipgpc_num_cls)) == EEXIST) {
		/* preserve previous config if values are absent */
		/* parse action name */
		old_next_action = ipgpc_cid_list[class_id].aclass.next_action;
		if (nvlist_lookup_string(*nvlpp, CLASSIFIER_NEXT_ACTION, &name)
		    != 0) {
			/* use previous config */
			in_class.next_action = old_next_action;
		} else {	/* next action name present */
			if ((in_class.next_action = ipp_action_lookup(name))
			    == IPP_ACTION_INVAL) {
				ipgpc0dbg(("ipgpc_modifyclass: invalid " \
				    "action name %s", name));
				mutex_exit(&ipgpc_cid_list_lock);
				return (EINVAL); /* this is an error */
			}
			ref_action = B_TRUE;
		}
		/* parse gather stats byte */
		if (nvlist_lookup_uint32(*nvlpp, CLASSIFIER_CLASS_STATS_ENABLE,
		    &gather_stats) != 0) {
			/* use previous config */
			in_class.gather_stats =
			    ipgpc_cid_list[class_id].aclass.gather_stats;
		} else {
			in_class.gather_stats = (boolean_t)gather_stats;
		}
		/* check to see if gather_stats booleans differ */
		if ((ipgpc_cid_list[class_id].aclass.gather_stats !=
		    in_class.gather_stats)) {
			if (ipgpc_cid_list[class_id].aclass.gather_stats) {
				/* delete kstat entry */
				if (ipgpc_cid_list[class_id].cl_stats != NULL) {
					ipp_stat_destroy(
					    ipgpc_cid_list[class_id].cl_stats);
					ipgpc_cid_list[class_id].cl_stats =
					    NULL;
				}
			} else { /* gather_stats == B_FALSE */
				if ((rc = class_statinit(&in_class, class_id))
				    != 0) {
					ipgpc0dbg(("ipgpc_modifyclass: " \
					    "class_statinit failed with " \
					    "error %d", rc));
					mutex_exit(&ipgpc_cid_list_lock);
					return (rc);
				}
			}
		}
		mutex_exit(&ipgpc_cid_list_lock);
		/* check if next_action was modified */
		if (ref_action == B_TRUE) {
			if ((rc = ipp_action_ref(ipgpc_aid,
			    in_class.next_action, 0)) != 0) {
				ipgpc0dbg(("ipgpc_modifyclass: error " \
				    "occurred while adding a reference to " \
				    "the new next_action %d",
				    in_class.next_action));
				mutex_exit(&ipgpc_cid_list_lock);
				return (rc);
			}
			/* fix up references */
			rc = ipp_action_unref(ipgpc_aid, old_next_action,
			    flags);
			ASSERT(rc == 0);
		}
		/* preserve originator id */
		in_class.originator =
		    ipgpc_cid_list[class_id].aclass.originator;
		ipgpc_cid_list[class_id].aclass = in_class;
		ipgpc_cid_list[class_id].stats.next_action =
		    in_class.next_action;
	} else {
		ipgpc0dbg(("ipgpc_modifyclass: class name lookup error %d",
		    rc));
		mutex_exit(&ipgpc_cid_list_lock);
		return (rc);
	}
	return (0);
}


/*
 * ipgpc_list_insert(listpp, id)
 *
 * inserts an item, id, into the list, if item exists EEXIST is returned
 */
int
ipgpc_list_insert(linked_list *listpp, key_t id)
{
	element_node_t *p;

	if (*listpp == NULL) {
		*listpp = kmem_cache_alloc(element_node_cache, KM_SLEEP);
		(*listpp)->element_refcnt = 1;
		(*listpp)->next = NULL;
		(*listpp)->id = id;
	} else {
		for (p = *listpp; p->next != NULL; p = p->next) {
			if (p->id == id) {
				(*p->element_ref)(p);
				return (EEXIST);
			}
		}
		if (p->id == id) {
			(*p->element_ref)(p);
			return (EEXIST);
		} else {
			p->next =
			    kmem_cache_alloc(element_node_cache, KM_SLEEP);
			p->next->element_refcnt = 1;
			p->next->next = NULL;
			p = p->next;
			p->id = id;
		}
	}
	return (0);
}

/*
 * ipgpc_list_remove(listpp, id)
 *
 * removes an item, id, from the list if it exists and returns TRUE or FALSE
 * if not removed
 */
boolean_t
ipgpc_list_remove(element_node_t **listpp, key_t id)
{
	element_node_t *p = NULL;
	element_node_t *t = NULL;

	if (*listpp == NULL) {
		return (B_FALSE);
	}
	if ((*listpp)->id == id) {
		p = *listpp;
		if ((*listpp)->element_refcnt == 1) {
			*listpp = (*listpp)->next;
		}
		(*p->element_unref)(p);
		return (B_TRUE);
	} else if ((*listpp)->next != NULL) {
		/* linear search for matching id */
		for (p = *listpp; p->next != NULL; p = p->next) {
			if (p->next->id == id) {
				t = p->next;
				if (p->next->element_refcnt == 1) {
					p->next = p->next->next;
				}
				(*t->element_unref)(t);
				return (B_TRUE);
			}
		}
	}
	return (B_FALSE);
}

/*
 * Module destroy code
 */

static void
removeclasses(ipp_flags_t flags)
{
	int i;

	for (i = 0; i < ipgpc_max_num_classes; ++i) {
		if (ipgpc_cid_list[i].info > 0) {
			(void) ipgpc_removeclass(
			    ipgpc_cid_list[i].aclass.class_name, flags);
		}
	}
}

static void
freetriev6nodes(node_t **inNode)
{
	node_t *anode = *inNode;
	node_t *tnode;
	node_t *s[130];		/* stack of previous nodes */
	int prev_link[130];	/* stack of what the previous link was */
	int sp = 0;
	node_t *root = *inNode;	/* pointer to root node */

	s[sp] = NULL;
	prev_link[sp] = -1;
	/* loop until only the root node remains */
	while (!((root->zero == NULL) && (root->one == NULL))) {
		if (anode->zero != NULL) { /* check zero node */
			tnode = anode;
			anode = anode->zero;
			s[++sp] = tnode; /* put node on stack */
			prev_link[sp] = 0;
		} else if (anode->one != NULL) { /* check one node */
			tnode = anode;
			anode = anode->one;
			s[++sp] = tnode; /* put node on stack */
			prev_link[sp] = 1;
		} else {	/* leaf node reached */
			/* free leaf node and pop the stack */
			kmem_cache_free(trie_node_cache, anode);
			anode = s[sp];
			if (prev_link[sp--] == 0) {
				anode->zero = NULL;
			} else {
				anode->one = NULL;
			}
			if (anode == NULL) {
				return;
			}
		}
	}
}


void
ipgpc_destroy(ipp_flags_t flags)
{
	int i;
	int rc;
	element_node_t *anode = NULL;
	element_node_t *tnode = NULL;
	fid_t *fid = NULL;

	/* check to see if default class id was set */
	if (ipgpc_def_class_id != -1) {
		ipp_action_id_t next_action =
		    ipgpc_cid_list[ipgpc_def_class_id].aclass.next_action;

		/* unreference default_class->next_action */
		rc = ipp_action_unref(ipgpc_aid, next_action, flags);
		ASSERT(rc == 0);
		/* removing filter associated with the default class */
		anode = ipgpc_cid_list[ipgpc_def_class_id].filter_list;
		while (anode != NULL) {
			fid = &ipgpc_fid_list[anode->id];
			if (ipgpc_fid_list[anode->id].info > 0) {
				anode = anode->next;
				(void) ipgpc_removefilter(
				    fid->filter.filter_name,
				    fid->filter.filter_instance, flags);
			} else {
				tnode = anode;
				anode = anode->next;
				/* free this node */
				kmem_cache_free(element_node_cache, tnode);
			}
		}
		ASSERT(ipgpc_cid_list[ipgpc_def_class_id].filter_list == NULL);
		removecid(ipgpc_def_class_id);
		ASSERT(ipgpc_cid_list[ipgpc_def_class_id].info == -1);
		ipgpc_def_class_id = -1;
	}
	/* remove stats entries */
	if (ipgpc_global_stats != NULL) {
		/* destroy global stats */
		ipp_stat_destroy(ipgpc_global_stats);
		ipgpc_global_stats = NULL;
	}

	/*
	 * remove all classes, which will remove all filters, stats and
	 * selectors
	 */
	if (ipgpc_cid_list != NULL) {
		removeclasses(flags);
		kmem_free(ipgpc_cid_list,
		    sizeof (cid_t) * ipgpc_max_num_classes);
		ipgpc_cid_list = NULL;
	}
	/* all filters and classes should have been removed at this point */
	ASSERT((ipgpc_num_cls == 0) && (ipgpc_num_fltrs == 0));

	/* free filter id list structure */
	if (ipgpc_fid_list != NULL) {
		kmem_free(ipgpc_fid_list,
		    sizeof (fid_t) * ipgpc_max_num_filters);
		ipgpc_fid_list = NULL;
	}

	/*
	 * IPv6 address tries don't implement path compression or node
	 * deletions, like v4/port tries.  All allocated nodes must be freed
	 * before trie root node is destroyed
	 */
	if (ipgpc_trie_list[IPGPC_TRIE_SADDRID6].trie != NULL) {
		freetriev6nodes(&ipgpc_trie_list[IPGPC_TRIE_SADDRID6].trie);
		/* free trie root */
		kmem_cache_free(trie_node_cache,
		    ipgpc_trie_list[IPGPC_TRIE_SADDRID6].trie);
		/* destroy lock */
		rw_destroy(&ipgpc_trie_list[IPGPC_TRIE_SADDRID6].rw_lock);
		ipgpc_trie_list[IPGPC_TRIE_SADDRID6].trie = NULL;
	}
	if (ipgpc_trie_list[IPGPC_TRIE_DADDRID6].trie != NULL) {
		freetriev6nodes(&ipgpc_trie_list[IPGPC_TRIE_DADDRID6].trie);
		/* free trie root */
		kmem_cache_free(trie_node_cache,
		    ipgpc_trie_list[IPGPC_TRIE_DADDRID6].trie);
		/* destroy lock */
		rw_destroy(&ipgpc_trie_list[IPGPC_TRIE_DADDRID6].rw_lock);
		ipgpc_trie_list[IPGPC_TRIE_DADDRID6].trie = NULL;
	}

	/* free remaining tries structures */
	for (i = 0; i < (NUM_TRIES - 2); ++i) {
		if (ipgpc_trie_list[i].trie != NULL) {
			/* free trie root */
			kmem_cache_free(trie_node_cache,
			    ipgpc_trie_list[i].trie);
			/* destroy lock */
			rw_destroy(&ipgpc_trie_list[i].rw_lock);
			ipgpc_trie_list[i].trie = NULL;
		}
	}

	/* destroy caches */
	if (ht_node_cache != NULL) {
		kmem_cache_destroy(ht_node_cache);
		ht_node_cache = NULL;
	}
	if (trie_node_cache != NULL) {
		kmem_cache_destroy(trie_node_cache);
		trie_node_cache = NULL;
	}
	if (element_node_cache != NULL) {
		kmem_cache_destroy(element_node_cache);
		element_node_cache = NULL;
	}
	if (ht_match_cache != NULL) {
		kmem_cache_destroy(ht_match_cache);
		ht_match_cache = NULL;
	}
}

/*
 * Module info code
 */

/*
 * ipgpc_params_info(fn, arg)
 *
 * allocates, builds and passes an nvlist to fn with arg
 */
int
ipgpc_params_info(int (*fn)(nvlist_t *, void *), void *arg)
{
	nvlist_t *nvlp;
	int rc;

	/* allocate nvlist to be passed back */
	if ((rc = nvlist_alloc(&nvlp, NV_UNIQUE_NAME, KM_NOSLEEP)) != 0) {
		return (rc);
	}

	/* add config type */
	if ((rc = nvlist_add_byte(nvlp, IPP_CONFIG_TYPE, IPP_SET)) != 0) {
		nvlist_free(nvlp);
		return (rc);
	}

	/* add gather stats boolean */
	if ((rc = nvlist_add_uint32(nvlp, IPP_ACTION_STATS_ENABLE,
	    (uint32_t)ipgpc_gather_stats)) != 0) {
		nvlist_free(nvlp);
		return (rc);
	}

	/* call back with nvlist */
	rc = fn(nvlp, arg);

	nvlist_free(nvlp);

	return (rc);
}

/*
 * build_class_nvlist(nvlpp, in_class)
 *
 * build an nvlist based on in_class
 * if isdefault, add apporiate configuration type to nvlpp
 */
static int
build_class_nvlist(nvlist_t **nvlpp, ipgpc_class_t *in_class,
    boolean_t isdefault)
{
	nvlist_t *nvlp = *nvlpp;
	char *next_action;
	int rc;

	/*
	 * add configuration type
	 * if class is the default class, config type should be
	 * CLASSIFIER_MODIFY_CLASS
	 * otherwise it should be CLASSIFIER_ADD_CLASS
	 */
	/* add config type */
	if ((rc = nvlist_add_byte(nvlp, IPP_CONFIG_TYPE,
	    ((isdefault) ? CLASSIFIER_MODIFY_CLASS : CLASSIFIER_ADD_CLASS)))
	    != 0) {
		return (rc);
	}

	/* add class name */
	if ((rc = nvlist_add_string(nvlp, CLASSIFIER_CLASS_NAME,
	    in_class->class_name)) != 0) {
		return (rc);
	}

	/* add originator */
	if ((rc = nvlist_add_uint32(nvlp, IPP_CONFIG_ORIGINATOR,
	    in_class->originator)) != 0) {
		return (rc);
	}

	/* look up next action name with next action id */
	if ((rc = ipp_action_name(in_class->next_action, &next_action)) != 0) {
		return (rc);
	}

	/* add next action name */
	if ((rc = nvlist_add_string(nvlp, CLASSIFIER_NEXT_ACTION,
	    next_action)) != 0) {
		kmem_free(next_action, (strlen(next_action) + 1));
		return (rc);
	}

	kmem_free(next_action, (strlen(next_action) + 1));

	/* add gather stats boolean */
	if ((rc = nvlist_add_uint32(nvlp, CLASSIFIER_CLASS_STATS_ENABLE,
	    (uint32_t)in_class->gather_stats)) != 0) {
		return (rc);
	}

	return (0);
}


/*
 * ipgpc_classes_info(fn, arg)
 *
 * foreach class, allocate, build and pass an nvlist to fn with arg
 */
int
ipgpc_classes_info(int (*fn)(nvlist_t *, void *), void *arg)
{
	int i;
	int rc;
	nvlist_t *nvlp;

	for (i = 0; i < ipgpc_max_num_classes; ++i) {
		if (ipgpc_cid_list[i].info <= 0) {
			/* cid not allocated for this entry */
			continue;
		}
		/* allocate an nvlist */
		if ((rc = nvlist_alloc(&nvlp, NV_UNIQUE_NAME, KM_NOSLEEP))
		    != 0) {
			return (rc);
		}
		/* build an nvlist for this particular class */
		if ((rc = (build_class_nvlist(&nvlp,
		    &ipgpc_cid_list[i].aclass,
		    ((i == ipgpc_def_class_id) ? B_TRUE : B_FALSE)))) != 0) {
			nvlist_free(nvlp);
			return (rc);
		}
		/* call back with nvlist */
		if ((rc = fn(nvlp, arg)) != 0) {
			nvlist_free(nvlp);
			return (rc);
		}

		nvlist_free(nvlp); /* free nvlist and continue */
	}

	return (0);
}

/*
 * build_filter_nvlist(nvlpp, in_filter, class_name)
 *
 * build an nvlist based on in_filter and class_name.
 * Only non-wildcard/dontcare selectors are added to the nvlist.
 */
static int
build_filter_nvlist(nvlist_t **nvlpp, ipgpc_filter_t *in_filter,
    char *class_name)
{
	nvlist_t *nvlp = *nvlpp;
	int rc;
	in6_addr_t zero_addr = IN6ADDR_ANY_INIT;

	/* add filter name */
	if ((rc = nvlist_add_string(nvlp, CLASSIFIER_FILTER_NAME,
	    in_filter->filter_name)) != 0) {
		return (rc);
	}

	/* add class name */
	if ((rc = nvlist_add_string(nvlp, CLASSIFIER_CLASS_NAME, class_name))
	    != 0) {
		return (rc);
	}

	/* add originator */
	if ((rc = nvlist_add_uint32(nvlp, IPP_CONFIG_ORIGINATOR,
	    in_filter->originator)) != 0) {
		return (rc);
	}

	/* add configuration type of CLASSIFIER_ADD_FILTER */
	if ((rc = nvlist_add_byte(nvlp, IPP_CONFIG_TYPE,
	    CLASSIFIER_ADD_FILTER)) != 0) {
		return (rc);
	}

	/* add uid */
	if (in_filter->uid != IPGPC_WILDCARD) {
		if ((rc = nvlist_add_uint32(nvlp, IPGPC_UID, in_filter->uid))
		    != 0) {
			return (rc);
		}
	}

	/* add projid */
	if (in_filter->projid != IPGPC_WILDCARD) {
		if ((rc = nvlist_add_int32(nvlp, IPGPC_PROJID,
		    in_filter->projid)) != 0) {
			return (rc);
		}
	}

	/* add interface index */
	if (in_filter->if_index != IPGPC_UNSPECIFIED) {
		if ((rc = nvlist_add_uint32(nvlp, IPGPC_IF_INDEX,
		    in_filter->if_index)) != 0) {
			return (rc);
		}
	}

	/* add direction */
	if (in_filter->direction != IPGPC_UNSPECIFIED) {
		if ((rc = nvlist_add_uint32(nvlp, IPGPC_DIR,
		    in_filter->direction)) != 0) {
			return (rc);
		}
	}

	/* add protocol */
	if (in_filter->proto != IPGPC_UNSPECIFIED) {
		if ((rc = nvlist_add_byte(nvlp, IPGPC_PROTO, in_filter->proto))
		    != 0) {
			return (rc);
		}
	}

	/* add dsfield and mask */
	if (in_filter->dsfield_mask != 0) {
		if ((rc = nvlist_add_byte(nvlp, IPGPC_DSFIELD,
		    in_filter->dsfield)) != 0) {
			return (rc);
		}
		if ((rc = nvlist_add_byte(nvlp, IPGPC_DSFIELD_MASK,
		    in_filter->dsfield_mask)) != 0) {
			return (rc);
		}
	}

	/* add source address, mask and hostname */
	if (!(IN6_ARE_ADDR_EQUAL(&in_filter->saddr_mask, &zero_addr))) {
		if ((rc = nvlist_add_uint32_array(nvlp, IPGPC_SADDR,
		    in_filter->saddr.s6_addr32, 4)) != 0) {
			return (rc);
		}

		if ((rc = nvlist_add_uint32_array(nvlp, IPGPC_SADDR_MASK,
		    in_filter->saddr_mask.s6_addr32, 4)) != 0) {
			return (rc);
		}

		if (in_filter->saddr_hostname != NULL) {
			if ((rc = nvlist_add_string(nvlp, IPGPC_SADDR_HOSTNAME,
			    in_filter->saddr_hostname)) != 0) {
				return (rc);
			}
		}
	}

	/* add destination address, mask and hostname */
	if (!(IN6_ARE_ADDR_EQUAL(&in_filter->daddr_mask, &zero_addr))) {
		if ((rc = nvlist_add_uint32_array(nvlp, IPGPC_DADDR,
		    in_filter->daddr.s6_addr32, 4)) != 0) {
			return (rc);
		}
		if ((rc = nvlist_add_uint32_array(nvlp, IPGPC_DADDR_MASK,
		    in_filter->daddr_mask.s6_addr32, 4)) != 0) {
			return (rc);
		}
		if (in_filter->daddr_hostname != NULL) {
			if ((rc = nvlist_add_string(nvlp, IPGPC_DADDR_HOSTNAME,
			    in_filter->daddr_hostname)) != 0) {
				return (rc);
			}
		}
	}

	/* add source port and mask */
	if (in_filter->sport_mask != 0) {
		if ((rc = nvlist_add_uint16(nvlp, IPGPC_SPORT,
		    in_filter->sport)) != 0) {
			return (rc);
		}
		if ((rc = nvlist_add_uint16(nvlp, IPGPC_SPORT_MASK,
		    in_filter->sport_mask)) != 0) {
			return (rc);
		}
	}

	/* add destination port and mask */
	if (in_filter->dport_mask != 0) {
		if ((rc = nvlist_add_uint16(nvlp, IPGPC_DPORT,
		    in_filter->dport)) != 0) {
			return (rc);
		}
		if ((rc = nvlist_add_uint16(nvlp, IPGPC_DPORT_MASK,
		    in_filter->dport_mask)) != 0) {
			return (rc);
		}
	}

	/* add precedence */
	if (in_filter->precedence != UINT_MAX) {
		if ((rc = nvlist_add_uint32(nvlp, IPGPC_PRECEDENCE,
		    in_filter->precedence)) != 0) {
			return (rc);
		}
	}

	/* add priority */
	if (in_filter->priority != 0) {
		if ((rc = nvlist_add_uint32(nvlp, IPGPC_PRIORITY,
		    in_filter->priority)) != 0) {
			return (rc);
		}
	}

	/* add filter type */
	if (in_filter->filter_type != IPGPC_GENERIC_FLTR) {
		if ((rc = nvlist_add_byte(nvlp, IPGPC_FILTER_TYPE,
		    in_filter->filter_type)) != 0) {
			return (rc);
		}
	}

	/* add filter instance */
	if (in_filter->filter_instance != -1) {
		if ((rc = nvlist_add_int32(nvlp, IPGPC_FILTER_INSTANCE,
		    in_filter->filter_instance)) != 0) {
			return (rc);
		}
	}

	/* add filter private field */
	if (in_filter->filter_comment != NULL) {
		if ((rc = nvlist_add_string(nvlp, IPGPC_FILTER_PRIVATE,
		    in_filter->filter_comment)) != 0) {
			return (rc);
		}
	}

	return (0);
}

/*
 * ipgpc_filters_info(fn, arg)
 *
 * for each filter, allocate, build and pass an nvlist to fn with arg
 */
int
ipgpc_filters_info(int (*fn)(nvlist_t *, void *), void *arg)
{
	int i;
	int rc;
	nvlist_t *nvlp;
	int class_id;

	for (i = 0; i < ipgpc_max_num_filters; ++i) {
		if (ipgpc_fid_list[i].info <= 0) {
			/* fid not allocated for this entry */
			continue;
		}
		/* allocate an nvlist */
		if ((rc = nvlist_alloc(&nvlp, NV_UNIQUE_NAME, KM_NOSLEEP))
		    != 0) {
			return (rc);
		}
		class_id = ipgpc_fid_list[i].class_id;
		/* build an nvlist for this particular filter */
		if ((rc = (build_filter_nvlist(&nvlp,
		    &ipgpc_fid_list[i].filter,
		    ipgpc_cid_list[class_id].aclass.class_name))) != 0) {
			nvlist_free(nvlp);
			return (rc);
		}
		/* call back with nvlist */
		if ((rc = fn(nvlp, arg)) != 0) {
			nvlist_free(nvlp);
			return (rc);
		}

		nvlist_free(nvlp); /* free nvlist and continue */
	}
	return (0);
}

/*
 * Module invoke code
 */

/*
 * ipgpc_findfilters(in_id, key, fid_table)
 *
 * returns a list of matching filters for searching the given structure
 * associated with the input id with the input key
 * - returns DONTCARE_ONLY_MATCH if the selector structure described by
 *   in_id contains only dontcares
 * - returns NO_MATCHES if no filters were found and no dontcares exist
 *   for a given selector
 * - ENOMEM is returned if memory error occurs
 * - NORMAL_MATCH on success
 */
int
ipgpc_findfilters(int in_id, int key, ht_match_t *fid_table)
{
	int num_found = 0;

	if (in_id == IPGPC_BA_DSID) {	/* special search for DSFIELD */
		if (ipgpc_ds_table_id.info.dontcareonly == B_TRUE) {
			/* trie is loaded with only DONTCARE(*) keys */
			return (DONTCARE_ONLY_MATCH);
		}
		num_found = ba_retrieve(&ipgpc_ds_table_id, (uint8_t)key,
		    fid_table);
		/* check to see if no matches were made */
		if ((num_found == 0) &&
		    (ipgpc_ds_table_id.stats.num_dontcare == 0)) {
			return (NO_MATCHES);
		}
	} else if (in_id >= TABLE_ID_OFFSET) {	/* table to search */
		table_id_t *taid = &ipgpc_table_list[in_id - TABLE_ID_OFFSET];

		if (taid->info.dontcareonly == B_TRUE) {
			/* trie is loaded with only DONTCARE(*) keys */
			return (DONTCARE_ONLY_MATCH);
		}
		num_found = ht_retrieve(taid, key, fid_table);
		/* check to see if no matches were made */
		if ((num_found == 0) && (taid->stats.num_dontcare == 0)) {
			return (NO_MATCHES);
		}
	} else {		/* trie to search */
		trie_id_t *tid = &ipgpc_trie_list[in_id];

		if (tid->info.dontcareonly == B_TRUE) {
			/* trie is loaded with only DONTCARE(*) keys */
			return (DONTCARE_ONLY_MATCH);
		}
		/* search the trie for matches */
		num_found = t_retrieve(tid, key, fid_table);
		/* check to see if no matches were made */
		if ((num_found == 0) && (tid->stats.num_dontcare == 0)) {
			return (NO_MATCHES);
		}
	}
	if (num_found == -1) {	/* num_found == -1 if memory error */
		return (ENOMEM);
	} else {
		return (NORMAL_MATCH);
	}
}

/*
 * ipgpc_findfilters6(in_id, key, fid_table)
 *
 * findfilters specific to IPv6 traffic
 */
int
ipgpc_findfilters6(int in_id, in6_addr_t key, ht_match_t *fid_table)
{
	trie_id_t *tid = &ipgpc_trie_list[in_id];
	int num_found = 0;

	if (tid->info.dontcareonly == B_TRUE) {
		/* trie is loaded with only DONTCARE(*) keys */
		return (DONTCARE_ONLY_MATCH);
	}
	/* search the trie for matches */
	num_found = t_retrieve6(tid, key, fid_table);
	/* check to see if no matches were made */
	if ((num_found == 0) && (tid->stats.num_dontcare == 0)) {
		return (NO_MATCHES);
	} else if (num_found == -1) { /* num_found == -1 if memory error */
		return (ENOMEM);
	} else {
		return (NORMAL_MATCH);
	}
}

/*
 * ht_match_insert(a, id, mask)
 *
 * inserts id into table and applies mask to match_map
 * returns ENOMEM if can't allocate ht_match_t node, 0 otherwise
 */
static int
ht_match_insert(ht_match_t *a, int id, uint16_t mask)
{
	int x = (id % HASH_SIZE); /* has for index */
	ht_match_t *p = NULL;

	if ((a[x].key == id) || (a[x].key == 0)) {
		a[x].key = id;
		a[x].match_map |= mask;
	} else if (a[x].next == NULL) {
		a[x].next = kmem_cache_alloc(ht_match_cache, KM_NOSLEEP);
		if (a[x].next == NULL) {
			ipgpc0dbg(("ht_match_insert(): kmem_cache_alloc " \
			    "error"));
			return (ENOMEM);
		}
		a[x].next->next = NULL;
		a[x].next->key = id;
		a[x].next->match_map = mask;
	} else {

		p = a[x].next;
		while (p != NULL) {
			if (p->key == id) {
				p->match_map |= mask;
				return (0);
			}
			p = p->next;
		}
		p = kmem_cache_alloc(ht_match_cache, KM_NOSLEEP);
		if (p == NULL) {
			ipgpc0dbg(("ht_match_insert(): kmem_cache_alloc " \
			    "error"));
			return (ENOMEM);
		}
		p->key = id;
		p->match_map = mask;
		p->next = a[x].next;
		a[x].next = p;
	}
	return (0);
}

/*
 * ipgpc_mark_found(mask, list, fid_table)
 *
 * given a list of filter ids and a mask for the selector that is being marked,
 * the ids are inserted (or updated) in the fid_table to being marked as
 * matched for the given selector
 * return -1 if memory error
 */
int
ipgpc_mark_found(uint16_t mask, linked_list list, ht_match_t *fid_table)
{
	linked_list tnode = NULL;
	int num_found = 0;

	for (tnode = list; tnode != NULL; tnode = tnode->next) {
		/* apply the trie mask to the match map for this element */
		if (ipgpc_fid_list[tnode->id].info > 0) {
			if (ht_match_insert(fid_table, tnode->id, mask)
			    == ENOMEM) {
				return (-1);
			}
			++num_found;
		}
	}
	return (num_found);
}

/* updates global stats for ipgpc */
/* ARGSUSED */
static int
update_global_stats(ipp_stat_t *sp, void *arg, int rw)
{
	globalstats_t *gbl_stats = (globalstats_t *)sp->ipps_data;
	uint32_t num_filters = (uint32_t)ipgpc_num_fltrs;
	uint32_t num_classes = (uint32_t)ipgpc_num_cls;

	ASSERT(gbl_stats != NULL);
	(void) ipp_stat_named_op(&gbl_stats->nfilters, &num_filters, rw);
	(void) ipp_stat_named_op(&gbl_stats->nclasses, &num_classes, rw);
	(void) ipp_stat_named_op(&gbl_stats->nbytes, &ipgpc_nbytes, rw);
	(void) ipp_stat_named_op(&gbl_stats->npackets, &ipgpc_npackets, rw);
	(void) ipp_stat_named_op(&gbl_stats->epackets, &ipgpc_epackets, rw);
	return (0);
}


/* updates class stats for a specific class */
static int
update_class_stats(ipp_stat_t *sp, void *arg, int rw)
{
	ipgpc_class_stats_t *stats = (ipgpc_class_stats_t *)arg;
	classstats_t *cl_stats = (classstats_t *)sp->ipps_data;

	ASSERT(stats != NULL);
	ASSERT(cl_stats != NULL);
	(void) ipp_stat_named_op(&cl_stats->nbytes, &stats->nbytes, rw);
	(void) ipp_stat_named_op(&cl_stats->npackets, &stats->npackets, rw);
	(void) ipp_stat_named_op(&cl_stats->last_match, &stats->last_match, rw);
	return (0);
}