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

   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
  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
  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
 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
 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
 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
 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 }