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
ht_hash(int a)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
ht_insert(table_id_t * taid,key_t id,int key)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
ht_search(hash_table table,int key)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
ht_retrieve(table_id_t * taid,int key,ht_match_t * fid_table)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
remove_num_inserted(table_id_t * taid)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
ht_remove(table_id_t * taid,key_t id,int key)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