From: Robert Olsson <Robert.Olsson@xxxxxxxxxxx>
Date: Wed, 11 Jun 2003 19:40:47 +0200
vma samples %-age symbol name
c023c038 107340 33.143 fn_hash_lookup
Ok, let's optimize our datastructures for how we actually
use them :-) Also, fn_zone shrunk by 8 bytes.
Try this:
--- ./include/net/ip_fib.h.~1~ Thu Jun 12 22:18:33 2003
+++ ./include/net/ip_fib.h Thu Jun 12 22:19:57 2003
@@ -89,13 +89,12 @@ struct fib_info
struct fib_rule;
#endif
-struct fib_result
-{
- unsigned char prefixlen;
- unsigned char nh_sel;
+struct fib_result {
+ struct fib_info *fi;
unsigned char type;
unsigned char scope;
- struct fib_info *fi;
+ unsigned char prefixlen;
+ unsigned char nh_sel;
#ifdef CONFIG_IP_MULTIPLE_TABLES
struct fib_rule *r;
#endif
--- ./net/ipv4/fib_hash.c.~1~ Thu Jun 12 21:47:11 2003
+++ ./net/ipv4/fib_hash.c Thu Jun 12 22:08:27 2003
@@ -65,16 +65,15 @@ typedef struct {
u32 datum;
} fn_hash_idx_t;
-struct fib_node
-{
- struct fib_node *fn_next;
- struct fib_info *fn_info;
-#define FIB_INFO(f) ((f)->fn_info)
+struct fib_node {
fn_key_t fn_key;
u8 fn_tos;
- u8 fn_type;
- u8 fn_scope;
u8 fn_state;
+ u8 fn_scope;
+ u8 fn_type;
+ struct fib_node *fn_next;
+ struct fib_info *fn_info;
+#define FIB_INFO(f) ((f)->fn_info)
};
#define FN_S_ZOMBIE 1
@@ -82,29 +81,19 @@ struct fib_node
static int fib_hash_zombies;
-struct fn_zone
-{
- struct fn_zone *fz_next; /* Next not empty zone */
- struct fib_node **fz_hash; /* Hash table pointer */
- int fz_nent; /* Number of entries */
-
+struct fn_zone {
int fz_divisor; /* Hash divisor */
- u32 fz_hashmask; /* (fz_divisor - 1) */
-#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)
-
+#define FZ_HASHMASK(fz) ((fz)->fz_divisor - 1)
int fz_order; /* Zone order */
- u32 fz_mask;
-#define FZ_MASK(fz) ((fz)->fz_mask)
+#define FZ_MASK(fz) (inet_make_mask((fz)->fz_order))
+ struct fib_node **fz_hash; /* Hash table pointer */
+ struct fn_zone *fz_next; /* Next not empty zone */
+ int fz_nent; /* Number of entries */
};
-/* NOTE. On fast computers evaluation of fz_hashmask and fz_mask
- can be cheaper than memory lookup, so that FZ_* macros are used.
- */
-
-struct fn_hash
-{
- struct fn_zone *fn_zones[33];
+struct fn_hash {
struct fn_zone *fn_zone_list;
+ struct fn_zone *fn_zones[33];
};
static __inline__ fn_hash_idx_t fn_hash(fn_key_t key, struct fn_zone *fz)
@@ -197,7 +186,6 @@ static void fn_rehash_zone(struct fn_zon
{
struct fib_node **ht, **old_ht;
int old_divisor, new_divisor;
- u32 new_hashmask;
old_divisor = fz->fz_divisor;
@@ -217,8 +205,6 @@ static void fn_rehash_zone(struct fn_zon
break;
}
- new_hashmask = (new_divisor - 1);
-
#if RT_CACHE_DEBUG >= 2
printk("fn_rehash_zone: hash for zone %d grows from %d\n",
fz->fz_order, old_divisor);
#endif
@@ -231,7 +217,6 @@ static void fn_rehash_zone(struct fn_zon
write_lock_bh(&fib_hash_lock);
old_ht = fz->fz_hash;
fz->fz_hash = ht;
- fz->fz_hashmask = new_hashmask;
fz->fz_divisor = new_divisor;
fn_rebuild_zone(fz, old_ht, old_divisor);
write_unlock_bh(&fib_hash_lock);
@@ -261,7 +246,6 @@ fn_new_zone(struct fn_hash *table, int z
} else {
fz->fz_divisor = 1;
}
- fz->fz_hashmask = (fz->fz_divisor - 1);
fz->fz_hash = fz_hash_alloc(fz->fz_divisor);
if (!fz->fz_hash) {
kfree(fz);
@@ -269,7 +253,6 @@ fn_new_zone(struct fn_hash *table, int z
}
memset(fz->fz_hash, 0, fz->fz_divisor*sizeof(struct fib_node*));
fz->fz_order = z;
- fz->fz_mask = inet_make_mask(z);
/* Find the first not empty zone with more specific mask */
for (i=z+1; i<=32; i++)
@@ -312,10 +295,15 @@ fn_hash_lookup(struct fib_table *tb, con
if (f->fn_tos && f->fn_tos != flp->fl4_tos)
continue;
#endif
- f->fn_state |= FN_S_ACCESSED;
+ {
+ u8 state = f->fn_state;
- if (f->fn_state&FN_S_ZOMBIE)
- continue;
+ if (!(state & FN_S_ACCESSED))
+ f->fn_state = state | FN_S_ACCESSED;
+
+ if (state & FN_S_ZOMBIE)
+ continue;
+ }
if (f->fn_scope < flp->fl4_scope)
continue;
|