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 #undef IPN_DEBUG
  36
  37 static struct kmem_cache *ipn_hash_elem_cache;
  38 static void ipn_hash_timer_expired(unsigned long arg);
  39
  40 struct ipn_hash_elem {
  41         struct hlist_node hashnode;
  42         struct list_head lrunode;
  43         u16 key[4];
  44         int port;
  45         u64 expiretime;
  46 };
  47
  48 static inline int po2round(int vx)
  49 {
  50         register int rv=1;
  51         register int x=vx-1;
  52         for (x=vx-1; x;  x>>=1)
  53                 rv<<=1;
  54         return (rv);
  55 }
  56
  57 static inline int hashfun(u16 *key,u16 vlan,int mask)
  58 {
  59         register int x=key[0] * 0x03050000 + key[1] * 0x0709 +
  60                 key[2] * 0x0b0d0000 + vlan *0x1113;
  61         x = (x ^ x >> 12 ^ x >> 8 ^ x >> 4) & mask;
  62         return x;
  63 }
  64
  65 int ipn_hash_new(struct ipn_hash *vdeh,int size,unsigned long timeout)
  66 {
  67         if (size<=0 || timeout <=0)
  68                 return -EINVAL;
  69         vdeh->hashtable=kzalloc(sizeof(struct hlist_head)*size,GFP_KERNEL);
  70         if (!vdeh->hashtable)
  71                 return -ENOMEM;
  72         INIT_LIST_HEAD(&vdeh->lrulist);
  73         vdeh->mask=po2round(size)-1;
  74         vdeh->timeout=timeout * HZ;
  75         spin_lock_init(&vdeh->hashlock);
  76         setup_timer(&vdeh->hashtimer,ipn_hash_timer_expired,
  77                         (unsigned long) vdeh);
  78         return 0;
  79 }
  80
  81 static void _ipn_hash_flush(struct ipn_hash *vdeh)
  82 {
  83         struct list_head *node;
  84         struct list_head *temp;
  85         list_for_each_safe(node,temp,&vdeh->lrulist) {
  86                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
  87 #ifdef IPN_DEBUG
  88                 printk("HASH DELETED FLUSH %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
  89 #endif
  90                 list_del(&elem->lrunode);
  91                 hlist_del(&elem->hashnode);
  92                 kmem_cache_free(ipn_hash_elem_cache,elem);
  93         }
  94 }
  95
  96 void ipn_hash_flush(struct ipn_hash *vdeh)
  97 {
  98         spin_lock(&vdeh->hashlock);
  99         _ipn_hash_flush(vdeh);
 100         spin_unlock(&vdeh->hashlock);
 101 }
 102
 103 void ipn_hash_flush_key(struct ipn_hash *vdeh,u16 *key,u16 *vlan)
 104 {
 105         struct list_head *node;
 106         struct list_head *temp;
 107         spin_lock(&vdeh->hashlock);
 108         list_for_each_safe(node,temp,&vdeh->lrulist) {
 109                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 110                 if ((!key || (elem->key[0]==key[0] &&
 111                                                 elem->key[1]==key[1] &&
 112                                                 elem->key[2]==key[2])) ||
 113                                 (!vlan || elem->key[3]==*vlan)) {
 114 #ifdef IPN_DEBUG
 115                         printk("HASH DELETED FLUSH KEY %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 116 #endif
 117                         list_del(&elem->lrunode);
 118                         hlist_del(&elem->hashnode);
 119                         kmem_cache_free(ipn_hash_elem_cache,elem);
 120                 }
 121         }
 122         spin_unlock(&vdeh->hashlock);
 123 }
 124
 125 void ipn_hash_flush_port(struct ipn_hash *vdeh,int port)
 126 {
 127         struct list_head *node;
 128         struct list_head *temp;
 129         spin_lock(&vdeh->hashlock);
 130         list_for_each_safe(node,temp,&vdeh->lrulist) {
 131                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 132                 if (elem->port==port) {
 133 #ifdef IPN_DEBUG
 134                         printk("HASH DELETED FLUSH PORT %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 135 #endif
 136                         list_del(&elem->lrunode);
 137                         hlist_del(&elem->hashnode);
 138                         kmem_cache_free(ipn_hash_elem_cache,elem);
 139                 }
 140         }
 141         spin_unlock(&vdeh->hashlock);
 142 }
 143
 144 void ipn_hash_free(struct ipn_hash *vdeh)
 145 {
 146         spin_lock(&vdeh->hashlock);
 147         _ipn_hash_flush(vdeh);
 148         del_timer_sync(&vdeh->hashtimer);
 149         kfree(vdeh->hashtable);
 150         spin_unlock(&vdeh->hashlock);
 151 }
 152
 153 static void ipn_hash_timer_expired(unsigned long arg)
 154 {
 155         struct ipn_hash *vdeh=(struct ipn_hash *) arg;
 156         struct list_head *node;
 157         struct list_head *temp;
 158         u64 jiffies64;
 159         spin_lock(&vdeh->hashlock);
 160         jiffies64=get_jiffies_64();
 161 #ifdef IPN_DEBUG
 162         printk("HASH TIMER %lld\n",jiffies64);
 163 #endif
 164         list_for_each_safe(node,temp,&vdeh->lrulist) {
 165                 struct ipn_hash_elem *elem=list_entry(node,struct ipn_hash_elem,lrunode);
 166                 long next=elem->expiretime-jiffies64;
 167                 if (next < 0) {
 168 #ifdef IPN_DEBUG
 169                         printk("HASH DELETED TIMER %x %x %x %x\n", elem->key[0], elem->key[1], elem->key[2], elem->key[3]);
 170 #endif
 171                         list_del(&elem->lrunode);
 172                         hlist_del(&elem->hashnode);
 173                         kmem_cache_free(ipn_hash_elem_cache,elem);
 174                 } else {
 175                         mod_timer(&vdeh->hashtimer,jiffies+(unsigned long)next);
 176                         break;
 177                 }
 178         }
 179         spin_unlock(&vdeh->hashlock);
 180 }
 181
 182 void ipn_hash_add(struct ipn_hash *vdeh,u16 *key,u16 vlan,int port)
 183 {
 184         struct ipn_hash_elem *elem=NULL;
 185         struct hlist_node *node;
 186         int hashvalue=hashfun(key,vlan,vdeh->mask);
 187         int found=0;
 188         spin_lock(&vdeh->hashlock);
 189         hlist_for_each_entry(elem, node,
 190                         &vdeh->hashtable[hashvalue], hashnode) {
 191                 if (elem->key[0]==key[0] && elem->key[1]==key[1] &&
 192                                 elem->key[2]==key[2] && elem->key[3]==vlan) {
 193                         found=1;
 194                         break;
 195                 }
 196         }
 197         if (found) {
 198 #ifdef IPN_DEBUG
 199                 printk("FOUND SENDER %x %x %x %x (%d) <- %d (was %d)\n", key[0], key[1], key[2], vlan,hashvalue,port,elem->port);
 200 #endif
 201                 list_del(&elem->lrunode);
 202                 hlist_del(&elem->hashnode);
 203         } else if (vdeh->timeout>0){ /* vdeh->timeout == 0 means HUB */
 204 #ifdef IPN_DEBUG
 205                 printk("NEW HASH %x %x %x %x (%d) <- %d\n", key[0], key[1], key[2], vlan, hashvalue,port);
 206 #endif
 207                 elem=kmem_cache_alloc(ipn_hash_elem_cache,GFP_KERNEL);
 208                 if (elem) {
 209                         elem->key[0]=key[0]; elem->key[1]=key[1];
 210                         elem->key[2]=key[2]; elem->key[3]=vlan;
 211                 }
 212         }
 213         if (elem) {
 214                 elem->port=port;
 215                 list_add_tail(&elem->lrunode,&vdeh->lrulist);
 216                 hlist_add_head(&elem->hashnode,&vdeh->hashtable[hashvalue]);
 217                 if (!timer_pending(&vdeh->hashtimer))
 218                         mod_timer(&vdeh->hashtimer,jiffies + vdeh->timeout);
 219                 elem->expiretime=get_jiffies_64() + vdeh->timeout;
 220         }
 221         spin_unlock(&vdeh->hashlock);
 222 }
 223
 224 int ipn_hash_find(struct ipn_hash *vdeh,u16 *key,u16 vlan)
 225 {
 226         struct ipn_hash_elem *elem;
 227         struct hlist_node *node;
 228         int rv=-1;
 229         int hashvalue=hashfun(key,vlan,vdeh->mask);
 230
 231         spin_lock(&vdeh->hashlock);
 232 #ifdef IPN_DEBUG
 233         printk("SEARCH HASH %x %x %x %x \n", key[0], key[1], key[2], vlan);
 234 #endif
 235         hlist_for_each_entry(elem, node,
 236                         &vdeh->hashtable[hashvalue], hashnode) {
 237                 if (elem->key[0]==key[0] && elem->key[1]==key[1] &&
 238                                 elem->key[2]==key[2] && elem->key[3]==vlan) {
 239                         rv=elem->port;
 240 #ifdef IPN_DEBUG
 241                         printk("FOUND HASH %x %x %x %x -> %d\n", key[0], key[1], key[2], vlan, rv);
 242 #endif
 243                         break;
 244                 }
 245         }
 246         spin_unlock(&vdeh->hashlock);
 247         return rv;
 248 }
 249
 250 int ipn_hash_init(void)
 251 {
 252         ipn_hash_elem_cache=kmem_cache_create("ipn_hash",sizeof(struct ipn_hash_elem),0,0,NULL);
 253         if (ipn_hash_elem_cache)
 254                 return 0;
 255         else
 256                 return -ENOMEM;
 257 }
 258
 259 void ipn_hash_fini(void)
 260 {
 261         if (ipn_hash_elem_cache)
 262                 kmem_cache_destroy(ipn_hash_elem_cache);
 263 }
 264
 265 EXPORT_SYMBOL_GPL(ipn_hash_new);
 266 EXPORT_SYMBOL_GPL(ipn_hash_flush);
 267 EXPORT_SYMBOL_GPL(ipn_hash_flush_key);
 268 EXPORT_SYMBOL_GPL(ipn_hash_flush_port);
 269 EXPORT_SYMBOL_GPL(ipn_hash_free);
 270 EXPORT_SYMBOL_GPL(ipn_hash_add);
 271 EXPORT_SYMBOL_GPL(ipn_hash_find);
 272
 273 module_init(ipn_hash_init);
 274 module_exit(ipn_hash_fini);
 275