xref: /illumos-gate/usr/src/uts/common/ipp/ipgpc/table.c (revision 7a6d80f1660abd4755c68cbd094d4a914681d26e)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2002-2003 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #include <ipp/ipgpc/filters.h>
28 
29 /* table structure used for exact-match classification of selectors */
30 
31 /* Statics */
32 static int ht_hash(int);
33 static linked_list ht_search(hash_table, int);
34 static void remove_num_inserted(table_id_t *);
35 
36 /*
37  * ht_hash(a)
38  *
39  * hash function for keys (a) of type int
40  */
41 static int
42 ht_hash(int a)
43 {
44 	return (a % TABLE_SIZE);
45 }
46 
47 /*
48  * ht_insert(taid, id, key)
49  *
50  * inserts id into table with filter_id as the value
51  * if key == taid->wildcard, the key is inserted as a wildcard
52  * statistics are updated after insert is successful
53  * returns DONTCARE_VALUE if key == wildcard, NORMAL_VALUE otherwise
54  */
55 int
56 ht_insert(table_id_t *taid, key_t id, int key)
57 {
58 	int x;
59 	ht_node_t *p;
60 	hash_table table = taid->table;
61 
62 	/* check if dontcare */
63 	if (key == taid->wildcard) {
64 		/* don't cares/wildcards are not inserted */
65 		++taid->stats.num_dontcare;
66 		return (DONTCARE_VALUE);
67 	}
68 
69 	x = ht_hash(key);
70 	/*
71 	 * insert if key matches and entry is being used or if entry is empty
72 	 */
73 	if (((table[x].key == key) && (table[x].info == 1)) ||
74 	    (table[x].info == 0)) {
75 		table[x].key = key;
76 		table[x].info = 1;
77 		(void) ipgpc_list_insert(&table[x].elements, id);
78 	} else if (table[x].next == NULL) {
79 		table[x].next = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
80 		table[x].next->elements = NULL;
81 		table[x].next->next = NULL;
82 		table[x].next->key = key;
83 		table[x].next->info = 1;
84 		(void) ipgpc_list_insert(&table[x].next->elements, id);
85 	} else {
86 		p = table[x].next;
87 		while (p != NULL) {
88 			if (((p->key == key) && (p->info == 1)) ||
89 			    (p->info == 0)) {
90 				p->key = key;
91 				p->info = 1;
92 				(void) ipgpc_list_insert(&p->elements, id);
93 				if (taid->info.dontcareonly == B_TRUE) {
94 					taid->info.dontcareonly = B_FALSE;
95 				}
96 				return (NORMAL_VALUE);
97 			}
98 			p = p->next;
99 		}
100 		p = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
101 		p->elements = NULL;
102 		p->next = NULL;
103 		p->key = key;
104 		p->info = 1;
105 		(void) ipgpc_list_insert(&p->elements, id);
106 		p->next = table[x].next;
107 		table[x].next = p->next;
108 	}
109 	/* update stats */
110 	++taid->stats.num_inserted;
111 	if (taid->info.dontcareonly == B_TRUE) {
112 		taid->info.dontcareonly = B_FALSE;
113 	}
114 	return (NORMAL_VALUE);
115 }
116 
117 /*
118  * ht_search(table, key)
119  *
120  * searches for key and returns the linked list value associated with key if
121  * found in table. NULL is returned if key not found
122  */
123 static linked_list
124 ht_search(hash_table table, int key)
125 {
126 	int x;
127 	ht_node_t *p = NULL;
128 
129 	x = ht_hash(key);
130 	if ((table[x].key == key) && (table[x].info == 1)) {
131 		return (table[x].elements);
132 	} else {
133 		p = table[x].next;
134 		while (p != NULL) {
135 			if ((p->key == key) && (p->info == 1)) {
136 				return (p->elements);
137 			}
138 			p = p->next;
139 		}
140 		return (NULL);
141 	}
142 }
143 
144 /*
145  * ht_retrieve(taid, key, fid_table)
146  *
147  * All exact matches and wildcard matches are collected and inserted
148  * into the fid_table
149  * the number of found filters that match the input key are returned
150  * returns (-1) if memory error
151  */
152 int
153 ht_retrieve(table_id_t *taid, int key, ht_match_t *fid_table)
154 {
155 	int num_found = 0;
156 	linked_list alist = NULL;
157 	hash_table table = taid->table;
158 
159 	/* dontcare/wildcards are not inserted */
160 	if (key == taid->wildcard) {
161 		return (0);
162 	} else {
163 		alist = ht_search(table, key);
164 		if (alist != NULL) {
165 			if ((num_found = ipgpc_mark_found(taid->info.mask,
166 			    alist, fid_table)) == -1) {
167 				return (-1); /* signifies memory error */
168 			}
169 		}
170 	}
171 	return (num_found);
172 }
173 
174 /*
175  * remove_num_inserted(taid)
176  *
177  * updates the num_inserted statistics along with reseting the dontcareonly
178  * flag when applicable and decrementing the total inserted
179  */
180 static void
181 remove_num_inserted(table_id_t *taid)
182 {
183 	--taid->stats.num_inserted;
184 	if (taid->stats.num_inserted <= 0) {
185 		taid->info.dontcareonly = B_TRUE;
186 	}
187 }
188 
189 /*
190  * ht_remove(taid, id, key)
191  *
192  * removes a single filter id item from the linked_list associated with id in
193  * table
194  */
195 void
196 ht_remove(table_id_t *taid, key_t id, int key)
197 {
198 	hash_table table = taid->table;
199 	int x;
200 	ht_node_t *p;
201 	ht_node_t *t;
202 
203 	/* check if dontcare */
204 	if (key == taid->wildcard) {
205 		/* don't cares/wildcards are not inserted */
206 		--taid->stats.num_dontcare;
207 		return;
208 	}
209 	x = ht_hash(key);
210 	/* remove entry if key matches and entry is being used */
211 	if ((table[x].key == key) && (table[x].info == 1)) {
212 		if (table[x].elements != NULL) {
213 			if (ipgpc_list_remove(&table[x].elements, id)) {
214 				/* update stats */
215 				remove_num_inserted(taid);
216 			}
217 		}
218 		if (table[x].elements == NULL) {
219 			/* reclaim memory if possible */
220 			if (table[x].next != NULL) {
221 				table[x].elements = table[x].next->elements;
222 				table[x].info = table[x].next->info;
223 				table[x].key = table[x].next->key;
224 				p = table[x].next; /* use p as temp */
225 				table[x].next = table[x].next->next;
226 				kmem_cache_free(ht_node_cache, p);
227 			} else {
228 				table[x].info = 0; /* mark entry as empty */
229 				table[x].key = 0;
230 			}
231 		}
232 	} else {
233 		p = &table[x];
234 		while (p->next != NULL) {
235 			if ((p->next->key == key) && (p->next->info == 1)) {
236 				if (ipgpc_list_remove(&p->next->elements, id)) {
237 					/* update stats */
238 					remove_num_inserted(taid);
239 				}
240 				if (p->next->elements == NULL) {
241 					/* reclaim memory if possible */
242 					if (p->next->next == NULL) {
243 						kmem_cache_free(ht_node_cache,
244 						    p->next);
245 						p->next = NULL;
246 					} else {
247 						t = p->next;
248 						p->next = p->next->next;
249 						kmem_cache_free(ht_node_cache,
250 						    t);
251 					}
252 				}
253 				return;
254 			}
255 			p = p->next;
256 		}
257 	}
258 }
259