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 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 #include <ipp/ipgpc/filters.h>
30
31 /* table structure used for exact-match classification of selectors */
32
33 /* Statics */
34 static int ht_hash(int);
35 static linked_list ht_search(hash_table, int);
36 static void remove_num_inserted(table_id_t *);
37
38 /*
39 * ht_hash(a)
40 *
41 * hash function for keys (a) of type int
42 */
43 static int
ht_hash(int a)44 ht_hash(int a)
45 {
46 return (a % TABLE_SIZE);
47 }
48
49 /*
50 * ht_insert(taid, id, key)
51 *
52 * inserts id into table with filter_id as the value
53 * if key == taid->wildcard, the key is inserted as a wildcard
54 * statistics are updated after insert is successful
55 * returns DONTCARE_VALUE if key == wildcard, NORMAL_VALUE otherwise
56 */
57 int
ht_insert(table_id_t * taid,key_t id,int key)58 ht_insert(table_id_t *taid, key_t id, int key)
59 {
60 int x;
61 ht_node_t *p;
62 hash_table table = taid->table;
63
64 /* check if dontcare */
65 if (key == taid->wildcard) {
66 /* don't cares/wildcards are not inserted */
67 ++taid->stats.num_dontcare;
68 return (DONTCARE_VALUE);
69 }
70
71 x = ht_hash(key);
72 /*
73 * insert if key matches and entry is being used or if entry is empty
74 */
75 if (((table[x].key == key) && (table[x].info == 1)) ||
76 (table[x].info == 0)) {
77 table[x].key = key;
78 table[x].info = 1;
79 (void) ipgpc_list_insert(&table[x].elements, id);
80 } else if (table[x].next == NULL) {
81 table[x].next = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
82 table[x].next->elements = NULL;
83 table[x].next->next = NULL;
84 table[x].next->key = key;
85 table[x].next->info = 1;
86 (void) ipgpc_list_insert(&table[x].next->elements, id);
87 } else {
88 p = table[x].next;
89 while (p != NULL) {
90 if (((p->key == key) && (p->info == 1)) ||
91 (p->info == 0)) {
92 p->key = key;
93 p->info = 1;
94 (void) ipgpc_list_insert(&p->elements, id);
95 if (taid->info.dontcareonly == B_TRUE) {
96 taid->info.dontcareonly = B_FALSE;
97 }
98 return (NORMAL_VALUE);
99 }
100 p = p->next;
101 }
102 p = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
103 p->elements = NULL;
104 p->next = NULL;
105 p->key = key;
106 p->info = 1;
107 (void) ipgpc_list_insert(&p->elements, id);
108 p->next = table[x].next;
109 table[x].next = p->next;
110 }
111 /* update stats */
112 ++taid->stats.num_inserted;
113 if (taid->info.dontcareonly == B_TRUE) {
114 taid->info.dontcareonly = B_FALSE;
115 }
116 return (NORMAL_VALUE);
117 }
118
119 /*
120 * ht_search(table, key)
121 *
122 * searches for key and returns the linked list value associated with key if
123 * found in table. NULL is returned if key not found
124 */
125 static linked_list
ht_search(hash_table table,int key)126 ht_search(hash_table table, int key)
127 {
128 int x;
129 ht_node_t *p = NULL;
130
131 x = ht_hash(key);
132 if ((table[x].key == key) && (table[x].info == 1)) {
133 return (table[x].elements);
134 } else {
135 p = table[x].next;
136 while (p != NULL) {
137 if ((p->key == key) && (p->info == 1)) {
138 return (p->elements);
139 }
140 p = p->next;
141 }
142 return (NULL);
143 }
144 }
145
146 /*
147 * ht_retrieve(taid, key, fid_table)
148 *
149 * All exact matches and wildcard matches are collected and inserted
150 * into the fid_table
151 * the number of found filters that match the input key are returned
152 * returns (-1) if memory error
153 */
154 int
ht_retrieve(table_id_t * taid,int key,ht_match_t * fid_table)155 ht_retrieve(table_id_t *taid, int key, ht_match_t *fid_table)
156 {
157 int num_found = 0;
158 linked_list alist = NULL;
159 hash_table table = taid->table;
160
161 /* dontcare/wildcards are not inserted */
162 if (key == taid->wildcard) {
163 return (0);
164 } else {
165 alist = ht_search(table, key);
166 if (alist != NULL) {
167 if ((num_found = ipgpc_mark_found(taid->info.mask,
168 alist, fid_table)) == -1) {
169 return (-1); /* signifies memory error */
170 }
171 }
172 }
173 return (num_found);
174 }
175
176 /*
177 * remove_num_inserted(taid)
178 *
179 * updates the num_inserted statistics along with reseting the dontcareonly
180 * flag when applicable and decrementing the total inserted
181 */
182 static void
remove_num_inserted(table_id_t * taid)183 remove_num_inserted(table_id_t *taid)
184 {
185 --taid->stats.num_inserted;
186 if (taid->stats.num_inserted <= 0) {
187 taid->info.dontcareonly = B_TRUE;
188 }
189 }
190
191 /*
192 * ht_remove(taid, id, key)
193 *
194 * removes a single filter id item from the linked_list associated with id in
195 * table
196 */
197 void
ht_remove(table_id_t * taid,key_t id,int key)198 ht_remove(table_id_t *taid, key_t id, int key)
199 {
200 hash_table table = taid->table;
201 int x;
202 ht_node_t *p;
203 ht_node_t *t;
204
205 /* check if dontcare */
206 if (key == taid->wildcard) {
207 /* don't cares/wildcards are not inserted */
208 --taid->stats.num_dontcare;
209 return;
210 }
211 x = ht_hash(key);
212 /* remove entry if key matches and entry is being used */
213 if ((table[x].key == key) && (table[x].info == 1)) {
214 if (table[x].elements != NULL) {
215 if (ipgpc_list_remove(&table[x].elements, id)) {
216 /* update stats */
217 remove_num_inserted(taid);
218 }
219 }
220 if (table[x].elements == NULL) {
221 /* reclaim memory if possible */
222 if (table[x].next != NULL) {
223 table[x].elements = table[x].next->elements;
224 table[x].info = table[x].next->info;
225 table[x].key = table[x].next->key;
226 p = table[x].next; /* use p as temp */
227 table[x].next = table[x].next->next;
228 kmem_cache_free(ht_node_cache, p);
229 } else {
230 table[x].info = 0; /* mark entry as empty */
231 table[x].key = 0;
232 }
233 }
234 } else {
235 p = &table[x];
236 while (p->next != NULL) {
237 if ((p->next->key == key) && (p->next->info == 1)) {
238 if (ipgpc_list_remove(&p->next->elements, id)) {
239 /* update stats */
240 remove_num_inserted(taid);
241 }
242 if (p->next->elements == NULL) {
243 /* reclaim memory if possible */
244 if (p->next->next == NULL) {
245 kmem_cache_free(ht_node_cache,
246 p->next);
247 p->next = NULL;
248 } else {
249 t = p->next;
250 p->next = p->next->next;
251 kmem_cache_free(ht_node_cache,
252 t);
253 }
254 }
255 return;
256 }
257 p = p->next;
258 }
259 }
260 }
261