ipn/kvde_switch/ipn_hash.c

   1 /*
   2  * Inter process networking (virtual distributed ethernet) module
   3  * Hash table for Ethernet management
   4  *  (part of the View-OS project: wiki.virtualsquare.org)
   5  *
   6  * Copyright (C) 2007   Renzo Davoli (renzo@cs.unibo.it)
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  Due to this file being licensed under the GPL there is controversy over
  14  *  whether this permits you to write a module that #includes this file
  15  *  without placing your module under the GPL.  Please consult a lawyer for
  16  *  advice before doing this.
  17  *
  18  * WARNING: THIS CODE IS ALREADY EXTREEEEMELY EXPERIMENTAL
  19  *
  20  */
  21
  22 #include <linux/init.h>
  23 #include <linux/module.h>
  24 #include <linux/types.h>
  25 #include <linux/timer.h>
  26 #include <linux/list.h>
  27 #include <linux/jiffies.h>
  28 #include "../af_ipn.h"
  29 #include "ipn_hash.h"
  30
  31 MODULE_LICENSE("GPL");
  32 MODULE_AUTHOR("VIEW-OS TEAM");
  33 MODULE_DESCRIPTION("Ethernet hash table Kernel Module");
  34
  35 #if LINUX_VERSION_CODE < KERNEL_VERSION(3,9,0)
  36 #define IPN_PRE390
  37 #endif
  38
  39 #undef IPN_DEBUG
  40
  41 static struct kmem_cache *ipn_hash_elem_cache;
  42 static void ipn_hash_timer_expired(unsigned long arg);
  43
  44 struct ipn_hash_elem {
  45         struct hlist_node hashnode;
  46         struct list_head lrunode;
  47         u16 key[4];
  48         int port;
  49         u64 expiretime;
  50 };
  51
  52 static inline int po2round(int vx)
  53 {
  54         register int rv=1;
  55         register int x=vx-1;
  56         for (x=vx-1; x;  x>>=1)
  57                 rv<<=1;
  58         return (rv);
  59 }
  60
  61 static inline int hashfun(u16 *key,u16 vlan,int mask)
  62 {
  63         register int x=key[0] * 0x03050000 + key[1] * 0x0709 +
  64                 key[2] * 0x0b0d0000 + vlan *0x1113;
  65         x = (x ^ x >> 12 ^ x >> 8 ^ x >> 4) & mask;
  66         return x;
  67 }
  68
  69 int ipn_hash_new(struct ipn_hash *vdeh,int size,unsigned long timeout)
  70 {
  71         if (size<=0 || timeout <=0)
  72                 return -EINVAL;
  73         vdeh->hashtable=kzalloc(sizeof(struct hlist_head)*size,GFP_KERNEL);
  74         if (!vdeh->hashtable)
  75                 return -ENOMEM;
  76         INIT_LIST_HEAD(&vdeh->lrulist);
  77         vdeh->mask=po2round(size)-1;
  78         vdeh->timeout=timeout * HZ;
  79         spin_lock_init(&vdeh->hashlock);
  80         setup_timer(&vdeh->hashtimer,ipn_hash_timer_expired,
  81                         (unsigned long) vdeh);
  82         return 0;
  83 }
  84
  85 static void _ipn_hash_flush(struct ipn_hash *vdeh)
  86 {
  87         struct list_head *node;
  88         struct list_head *temp;
  89         list_for_each_safe(node,temp,&vdeh->lrulist) {
  90                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
  91 #ifdef IPN_DEBUG
  92                 printk("HASH DELETED FLUSH %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
  93 #endif
  94                 list_del(&elem->lrunode);
  95                 hlist_del(&elem->hashnode);
  96                 kmem_cache_free(ipn_hash_elem_cache,elem);
  97         }
  98 }
  99
 100 void ipn_hash_flush(struct ipn_hash *vdeh)
 101 {
 102         spin_lock(&vdeh->hashlock);
 103         _ipn_hash_flush(vdeh);
 104         spin_unlock(&vdeh->hashlock);
 105 }
 106
 107 void ipn_hash_flush_key(struct ipn_hash *vdeh,u16 *key,u16 *vlan)
 108 {
 109         struct list_head *node;
 110         struct list_head *temp;
 111         spin_lock(&vdeh->hashlock);
 112         list_for_each_safe(node,temp,&vdeh->lrulist) {
 113                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 114                 if ((!key || (elem->key[0]==key[0] &&
 115                                                 elem->key[1]==key[1] &&
 116                                                 elem->key[2]==key[2])) ||
 117                                 (!vlan || elem->key[3]==*vlan)) {
 118 #ifdef IPN_DEBUG
 119                         printk("HASH DELETED FLUSH KEY %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 120 #endif
 121                         list_del(&elem->lrunode);
 122                         hlist_del(&elem->hashnode);
 123                         kmem_cache_free(ipn_hash_elem_cache,elem);
 124                 }
 125         }
 126         spin_unlock(&vdeh->hashlock);
 127 }
 128
 129 void ipn_hash_flush_port(struct ipn_hash *vdeh,int port)
 130 {
 131         struct list_head *node;
 132         struct list_head *temp;
 133         spin_lock(&vdeh->hashlock);
 134         list_for_each_safe(node,temp,&vdeh->lrulist) {
 135                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 136                 if (elem->port==port) {
 137 #ifdef IPN_DEBUG
 138                         printk("HASH DELETED FLUSH PORT %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 139 #endif
 140                         list_del(&elem->lrunode);
 141                         hlist_del(&elem->hashnode);
 142                         kmem_cache_free(ipn_hash_elem_cache,elem);
 143                 }
 144         }
 145         spin_unlock(&vdeh->hashlock);
 146 }
 147
 148 void ipn_hash_free(struct ipn_hash *vdeh)
 149 {
 150         spin_lock(&vdeh->hashlock);
 151         _ipn_hash_flush(vdeh);
 152         del_timer_sync(&vdeh->hashtimer);
 153         kfree(vdeh->hashtable);
 154         spin_unlock(&vdeh->hashlock);
 155 }
 156
 157 static void ipn_hash_timer_expired(unsigned long arg)
 158 {
 159         struct ipn_hash *vdeh=(struct ipn_hash *) arg;
 160         struct list_head *node;
 161         struct list_head *temp;
 162         u64 jiffies64;
 163         spin_lock(&vdeh->hashlock);
 164         jiffies64=get_jiffies_64();
 165 #ifdef IPN_DEBUG
 166         printk("HASH TIMER %lld\n",jiffies64);
 167 #endif
 168         list_for_each_safe(node,temp,&vdeh->lrulist) {
 169                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 170                 long next=elem->expiretime-jiffies64;
 171                 if (next < 0) {
 172 #ifdef IPN_DEBUG
 173                         printk("HASH DELETED TIMER %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 174 #endif
 175                         list_del(&elem->lrunode);
 176                         hlist_del(&elem->hashnode);
 177                         kmem_cache_free(ipn_hash_elem_cache,elem);
 178                 } else {
 179                         mod_timer(&vdeh->hashtimer,jiffies+(unsigned long)next);
 180                         break;
 181                 }
 182         }
 183         spin_unlock(&vdeh->hashlock);
 184 }
 185
 186 void ipn_hash_add(struct ipn_hash *vdeh,u16 *key,u16 vlan,int port)
 187 {
 188         struct ipn_hash_elem *elem=NULL;
 189         int hashvalue=hashfun(key,vlan,vdeh->mask);
 190         int found=0;
 191         spin_lock(&vdeh->hashlock);
 192 #ifdef PRE390
 193         struct hlist_node *node;
 194         hlist_for_each_entry(elem, node,
 195                         &vdeh->hashtable[hashvalue], hashnode)
 196 #else
 197         hlist_for_each_entry(elem,
 198                         &vdeh->hashtable[hashvalue], hashnode)
 199 #endif
 200         {
 201                 if (elem->key[0]==key[0] && elem->key[1]==key[1] &&
 202                                 elem->key[2]==key[2] && elem->key[3]==vlan) {
 203                         found=1;
 204                         break;
 205                 }
 206         }
 207         if (found) {
 208 #ifdef IPN_DEBUG
 209                 printk("FOUND SENDER %x %x %x %x (%d) <- %d (was %d)\n", key[0], key[1], key[2], vlan,hashvalue,port,elem->port);
 210 #endif
 211                 list_del(&elem->lrunode);
 212                 hlist_del(&elem->hashnode);
 213         } else if (vdeh->timeout>0){ /* vdeh->timeout == 0 means HUB */
 214 #ifdef IPN_DEBUG
 215                 printk("NEW HASH %x %x %x %x (%d) <- %d\n", key[0], key[1], key[2], vlan, hashvalue,port);
 216 #endif
 217                 elem=kmem_cache_alloc(ipn_hash_elem_cache,GFP_KERNEL);
 218                 if (elem) {
 219                         elem->key[0]=key[0]; elem->key[1]=key[1];
 220                         elem->key[2]=key[2]; elem->key[3]=vlan;
 221                 }
 222         }
 223         if (elem) {
 224                 elem->port=port;
 225                 list_add_tail(&elem->lrunode,&vdeh->lrulist);
 226                 hlist_add_head(&elem->hashnode,&vdeh->hashtable[hashvalue]);
 227                 if (!timer_pending(&vdeh->hashtimer))
 228                         mod_timer(&vdeh->hashtimer,jiffies + vdeh->timeout);
 229                 elem->expiretime=get_jiffies_64() + vdeh->timeout;
 230         }
 231         spin_unlock(&vdeh->hashlock);
 232 }
 233
 234 int ipn_hash_find(struct ipn_hash *vdeh,u16 *key,u16 vlan)
 235 {
 236         struct ipn_hash_elem *elem;
 237         int rv=-1;
 238         int hashvalue=hashfun(key,vlan,vdeh->mask);
 239
 240         spin_lock(&vdeh->hashlock);
 241 #ifdef IPN_DEBUG
 242         printk("SEARCH HASH %x %x %x %x \n", key[0], key[1], key[2], vlan);
 243 #endif
 244 #ifdef PRE390
 245         struct hlist_node *node;
 246         hlist_for_each_entry(elem, node,
 247                         &vdeh->hashtable[hashvalue], hashnode)
 248 #else
 249         hlist_for_each_entry(elem,
 250                         &vdeh->hashtable[hashvalue], hashnode)
 251 #endif
 252         {
 253                 if (elem->key[0]==key[0] && elem->key[1]==key[1] &&
 254                                 elem->key[2]==key[2] && elem->key[3]==vlan) {
 255                         rv=elem->port;
 256 #ifdef IPN_DEBUG
 257                         printk("FOUND HASH %x %x %x %x -> %d\n", key[0], key[1], key[2], vlan, rv);
 258 #endif
 259                         break;
 260                 }
 261         }
 262         spin_unlock(&vdeh->hashlock);
 263         return rv;
 264 }
 265
 266 int ipn_hash_init(void)
 267 {
 268         ipn_hash_elem_cache=kmem_cache_create("ipn_hash",sizeof(struct ipn_hash_elem),0,0,NULL);
 269         if (ipn_hash_elem_cache)
 270                 return 0;
 271         else
 272                 return -ENOMEM;
 273 }
 274
 275 void ipn_hash_fini(void)
 276 {
 277         if (ipn_hash_elem_cache)
 278                 kmem_cache_destroy(ipn_hash_elem_cache);
 279 }
 280
 281 EXPORT_SYMBOL_GPL(ipn_hash_new);
 282 EXPORT_SYMBOL_GPL(ipn_hash_flush);
 283 EXPORT_SYMBOL_GPL(ipn_hash_flush_key);
 284 EXPORT_SYMBOL_GPL(ipn_hash_flush_port);
 285 EXPORT_SYMBOL_GPL(ipn_hash_free);
 286 EXPORT_SYMBOL_GPL(ipn_hash_add);
 287 EXPORT_SYMBOL_GPL(ipn_hash_find);
 288
 289 module_init(ipn_hash_init);
 290 module_exit(ipn_hash_fini);
 291