Main Page | Directories | File List | Globals

hash_st.c File Reference

#include <agnix/agnix.h>
#include <agnix/init.h>
#include <agnix/memory.h>
#include <agnix/list.h>
#include <agnix/errno.h>
#include <agnix/spinlock.h>
#include <agnix/console.h>

Include dependency graph for hash_st.c:

Go to the source code of this file.

Defines

#define HASH_ENTRIES   ((PAGE_SIZE - sizeof(struct hash_table_s)) >> 3)
#define MAX_HASH_TABLES   16
#define MAX_HASH_ORDER   16
#define PSEUDO_KEY_FREE   0
#define PSEUDO_KEY_DELETED   1
#define PSEUDO_KEY_BUSY   2
#define find_hash_table(hashd)   (&hash_tables[hashd])
#define HASH_DEBUG   0
#define MOD_NAME   "HASH: "

Functions

u32 hash_fn_default (u32 key)
u32 hash_math_pseudo (struct hash_table_s *hash_table_ptr, u32 hash_key)
void hash_count_entries (int hashd)
int hash_entry_add (int hashd, u32 hash_key, u32 hash_addr)
int hash_entry_del (int hashd, u32 hash_key)
u32 hash_entry_find (int hashd, u32 hash_key)
int register_hash_table (char *name, u32 rows, u32(*hash_fn)(u32 key))
int unregister_hash_table (int hashd)
int hash_static_init (void)

Variables

hash_table_s hash_tables [MAX_HASH_TABLES]


Define Documentation

#define find_hash_table hashd   )     (&hash_tables[hashd])
 

Definition at line 30 of file hash_st.c.

Referenced by hash_count_entries(), hash_entry_add(), hash_entry_del(), hash_entry_find(), and unregister_hash_table().

#define HASH_DEBUG   0
 

Definition at line 32 of file hash_st.c.

#define HASH_ENTRIES   ((PAGE_SIZE - sizeof(struct hash_table_s)) >> 3)
 

Definition at line 22 of file hash_st.c.

#define MAX_HASH_ORDER   16
 

Definition at line 24 of file hash_st.c.

Referenced by register_hash_table().

#define MAX_HASH_TABLES   16
 

Definition at line 23 of file hash_st.c.

#define MOD_NAME   "HASH: "
 

Definition at line 33 of file hash_st.c.

#define PSEUDO_KEY_BUSY   2
 

Definition at line 28 of file hash_st.c.

Referenced by hash_entry_add(), hash_entry_del(), and hash_entry_find().

#define PSEUDO_KEY_DELETED   1
 

Definition at line 27 of file hash_st.c.

Referenced by hash_entry_del().

#define PSEUDO_KEY_FREE   0
 

Definition at line 26 of file hash_st.c.

Referenced by hash_entry_del(), hash_entry_find(), and register_hash_table().


Function Documentation

void hash_count_entries int  hashd  ) 
 

Definition at line 68 of file hash_st.c.

References find_hash_table, and printk().

00069 {
00070     struct hash_table_s *hash_table_ptr;    
00071 
00072     hash_table_ptr = find_hash_table(hashd);
00073     printk("hash_ptr %x\n", hash_table_ptr);
00074     printk("hash_max_entries %x\n", hash_table_ptr->max_entries);
00075     printk("hash_cur_entries %x\n", hash_table_ptr->cur_entries);
00076 }

Here is the call graph for this function:

int hash_entry_add int  hashd,
u32  hash_key,
u32  hash_addr
 

Definition at line 78 of file hash_st.c.

References find_hash_table, flags, hash_math_pseudo(), and PSEUDO_KEY_BUSY.

Referenced by arp_add_neigh_lock(), and fork_add_hash_entry().

00079 {
00080     struct hash_table_s *hash_table_ptr;
00081     struct hash_entry_s *hash_entry;
00082     u32 pseudo_key = 0;
00083     int loops;
00084     u32 flags;
00085 
00086     spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);
00087 
00088     hash_table_ptr = find_hash_table(hashd);
00089 
00090     if (!hash_table_ptr->max_entries)
00091         return -1;
00092 
00093     hash_entry = hash_table_ptr->hash_entry;
00094     pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;
00095 
00096     loops = 0;
00097     do {
00098         if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_BUSY) {
00099             pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
00100         } else {
00101             hash_entry[pseudo_key].hash_key    = hash_key;
00102             hash_entry[pseudo_key].hash_addr   = hash_addr;
00103             hash_entry[pseudo_key].hash_status = PSEUDO_KEY_BUSY;
00104             hash_table_ptr->cur_entries++;
00105             spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00106             return 0;
00107         }
00108         
00109         loops++;
00110         
00111     } while(loops < hash_table_ptr->max_entries);
00112         
00113     spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00114     
00115     return -1;   
00116 }

Here is the call graph for this function:

int hash_entry_del int  hashd,
u32  hash_key
 

Definition at line 118 of file hash_st.c.

References find_hash_table, flags, hash_math_pseudo(), PSEUDO_KEY_BUSY, PSEUDO_KEY_DELETED, and PSEUDO_KEY_FREE.

Referenced by arp_del_entry_lock().

00119 {
00120     struct hash_table_s *hash_table_ptr;
00121     struct hash_entry_s *hash_entry;
00122     u32 pseudo_key = 0;
00123     int loops;
00124     u32 flags;
00125 
00126     spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);
00127 
00128     hash_table_ptr = find_hash_table(hashd);
00129     if (!hash_table_ptr->max_entries)
00130         return -1;
00131 
00132     hash_entry = hash_table_ptr->hash_entry;
00133     pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;
00134 
00135     loops = 0;
00136     do {
00137         
00138         if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_FREE) {
00139             break;
00140         }
00141     
00142         if ((hash_entry[pseudo_key].hash_status != PSEUDO_KEY_BUSY) || 
00143             ((u32)hash_entry[pseudo_key].hash_key != (u32)hash_key)) {
00144             pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
00145         }
00146         else {   
00147             hash_entry[pseudo_key].hash_status = PSEUDO_KEY_DELETED;    
00148             spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00149             return 0;
00150         }
00151         
00152         loops++;
00153         
00154     } while(loops < hash_table_ptr->max_entries);
00155     
00156     spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00157     return -1;   
00158 }

Here is the call graph for this function:

u32 hash_entry_find int  hashd,
u32  hash_key
 

Definition at line 160 of file hash_st.c.

References find_hash_table, flags, hash_math_pseudo(), PSEUDO_KEY_BUSY, and PSEUDO_KEY_FREE.

Referenced by arp_get_entry_lock(), and fork_find_hash_entry().

00161 {
00162     struct hash_table_s *hash_table_ptr;
00163     struct hash_entry_s *hash_entry;
00164     u32 pseudo_key = 0;
00165     int loops;
00166     u32 flags;
00167     
00168     spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);
00169     
00170     hash_table_ptr = find_hash_table(hashd);
00171     if (!hash_table_ptr->max_entries)
00172         return 0;
00173 
00174     hash_entry = hash_table_ptr->hash_entry;
00175     pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;
00176 
00177     loops = 0;    
00178     do {
00179         if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_FREE)
00180             break;
00181             
00182         if ((hash_entry[pseudo_key].hash_status != PSEUDO_KEY_BUSY) || 
00183             ((u32)hash_entry[pseudo_key].hash_key != (u32)hash_key)) {
00184             pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
00185         }
00186         else {   
00187 
00188             spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00189             return hash_entry[pseudo_key].hash_addr;
00190         }
00191         
00192         loops++;
00193         
00194     } while(loops < hash_table_ptr->max_entries);
00195     
00196     spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
00197     
00198     return 0;
00199 }

Here is the call graph for this function:

u32 hash_fn_default u32  key  ) 
 

Definition at line 55 of file hash_st.c.

Referenced by register_hash_table().

00056 {
00057     return key;
00058 }

u32 hash_math_pseudo struct hash_table_s *  hash_table_ptr,
u32  hash_key
 

Definition at line 60 of file hash_st.c.

Referenced by hash_entry_add(), hash_entry_del(), and hash_entry_find().

00061 {
00062     if (hash_table_ptr->hash_fn)
00063         return hash_table_ptr->hash_fn(hash_key);
00064     else
00065         return hash_key;
00066 }

int hash_static_init void   ) 
 

Definition at line 297 of file hash_st.c.

References memset().

Referenced by data_structures_init().

00298 {
00299     int i;
00300 
00301     for (i = 0; i < MAX_HASH_TABLES; i++) {
00302         memset((void *)&hash_tables[i], 0, sizeof(struct hash_table_s));
00303     }
00304 
00305     return 0;
00306 }

Here is the call graph for this function:

int register_hash_table char *  name,
u32  rows,
u32(*)(u32 key)  hash_fn
 

Definition at line 229 of file hash_st.c.

References get_free_pages(), hash_fn_default(), MAX_HASH_ORDER, MOD_NAME, printk(), and PSEUDO_KEY_FREE.

Referenced by fork_init(), and net_layer_2_arp_init().

00230 {
00231     struct hash_table_s *hash_table;
00232     struct hash_entry_s *hash_entry;
00233     int page_order = 0;  
00234     int hashd;  
00235     int i;
00236 
00237     hashd = get_empty_hash_table();
00238     if (hashd == -1)
00239         return -EAGAIN;
00240 
00241     for (i = 0; i < MAX_HASH_ORDER; i++) {
00242         if (rows < (((1 << i) * PAGE_SIZE) / sizeof(struct hash_entry_s))) {
00243             page_order = i;
00244             break;
00245         }
00246     }
00247 
00248     if (i == MAX_HASH_ORDER)
00249         return -EINVAL;
00250 
00251     hash_table = &hash_tables[hashd];
00252     hash_entry = (struct hash_entry_s *)get_free_pages(page_order);
00253     
00254     if (!hash_table) {
00255         put_empty_hash_table(hashd);
00256         return -ENOMEM;
00257     }
00258 
00259     if (hash_fn)
00260         hash_table->hash_fn = hash_fn;
00261     else
00262         hash_table->hash_fn = hash_fn_default;
00263 
00264     hash_table->hash_name   = name;
00265     hash_table->max_entries = ((1 << page_order) * PAGE_SIZE) / sizeof(struct hash_entry_s);
00266     hash_table->cur_entries = 0;
00267     hash_table->page_order  = page_order;
00268     hash_table->hashd       = hashd;        
00269     hash_table->hash_entry  = hash_entry;
00270     
00271     for (i = 0; i < hash_table->max_entries; i++)
00272         hash_table->hash_entry[i].hash_status = PSEUDO_KEY_FREE;
00273     
00274 #if HASH_DEBUG
00275     printk(MOD_NAME "registering %s hashing table (%d rows/%d pages)\n", name, hash_table->max_entries, page_order);
00276 #endif
00277 
00278     spin_lock_init(&hash_table->hash_lock);
00279     
00280     return hashd;
00281 }

Here is the call graph for this function:

int unregister_hash_table int  hashd  ) 
 

Definition at line 283 of file hash_st.c.

References find_hash_table, and put_free_pages().

00284 {
00285     struct hash_table_s *hash_table_ptr;    
00286 
00287     hash_table_ptr = find_hash_table(hashd);
00288 
00289     if (hash_table_ptr) {
00290         put_free_pages((u32)hash_table_ptr->hash_entry, (u8)(hash_table_ptr->page_order));
00291         put_free_pages((u32)hash_table_ptr, 0);
00292     }
00293 
00294     return 0;
00295 }

Here is the call graph for this function:


Variable Documentation

struct hash_table_s hash_tables[MAX_HASH_TABLES]
 

Definition at line 53 of file hash_st.c.

Dokumentacje wygenerowano programem Doxygen 1.4.2 dla projektu Agnix