netdev - Re: [PATCH] [IPV4] fib_trie: size and statistics

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <478C58FD.9030407@cosmosbay.com>
Date:	Tue, 15 Jan 2008 07:55:57 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Stephen Hemminger <shemminger@...ux-foundation.org>
CC:	David Miller <davem@...emloft.net>, robert.olsson@....uu.se,
	netdev@...r.kernel.org, stephen.hemminger@...tta.com
Subject: Re: [PATCH] [IPV4] fib_trie: size and statistics

Stephen Hemminger a écrit :
> Show number of entries in trie, the size field was being set but never used,
> but it only counted leaves, not all entries. Refactor the two cases in
> fib_triestat_seq_show into a single routine.
> 
> Note: the stat structure was being malloc'd but the stack usage isn't so
> high (288 bytes) that it is worth the additional complexity.
> 
> Signed-off-by: Stephen Hemminger <stephen.hemminger@...tta.com>
> ---
> Patch against current net-2.6.25
> 
> --- a/net/ipv4/fib_trie.c	2008-01-14 10:16:06.000000000 -0800
> +++ b/net/ipv4/fib_trie.c	2008-01-14 10:30:11.000000000 -0800
> @@ -148,10 +148,10 @@ struct trie_stat {
>  
>  struct trie {
>  	struct node *trie;
> +	unsigned int size;
>  #ifdef CONFIG_IP_FIB_TRIE_STATS
>  	struct trie_use_stats stats;
>  #endif
> -	int size;
>  };
>  
>  static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
> @@ -1045,7 +1045,6 @@ static struct list_head *fib_insert_node
>  		insert_leaf_info(&l->list, li);
>  		goto done;
>  	}
> -	t->size++;
>  	l = leaf_new();
>  
>  	if (!l)
> @@ -1258,6 +1257,8 @@ static int fn_trie_insert(struct fib_tab
>  	list_add_tail_rcu(&new_fa->fa_list,
>  			  (fa ? &fa->fa_list : fa_head));
>  
> +	t->size++;
> +
>  	rt_cache_flush(-1);
>  	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
>  		  &cfg->fc_nlinfo, 0);
> @@ -2128,50 +2129,34 @@ static void trie_show_usage(struct seq_f
>  }
>  #endif /*  CONFIG_IP_FIB_TRIE_STATS */
>  
> +static void fib_trie_show(struct seq_file *seq, const char *name, struct trie *trie)
> +{
> +	struct trie_stat stat;
> +
> +	seq_printf(seq, "%s: %d\n", name, trie->size);
> +	trie_collect_stats(trie, &stat);
> +	trie_show_stats(seq, &stat);
> +#ifdef CONFIG_IP_FIB_TRIE_STATS
> +	trie_show_usage(seq, &trie->stats);
> +#endif
> +}
>  
>  static int fib_triestat_seq_show(struct seq_file *seq, void *v)
>  {
>  	struct net *net = (struct net *)seq->private;
> -	struct trie *trie_local, *trie_main;
> -	struct trie_stat *stat;
>  	struct fib_table *tb;
>  
> -	trie_local = NULL;
> +	seq_printf(seq,
> +		   "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
> +		   sizeof(struct leaf), sizeof(struct tnode));
> +
>  	tb = fib_get_table(net, RT_TABLE_LOCAL);
>  	if (tb)
> -		trie_local = (struct trie *) tb->tb_data;
> -
> -	trie_main = NULL;
> +		fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
> +
>  	tb = fib_get_table(net, RT_TABLE_MAIN);
>  	if (tb)
> -		trie_main = (struct trie *) tb->tb_data;
> -
> -
> -	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
> -	if (!stat)
> -		return -ENOMEM;
> -
> -	seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
> -		   sizeof(struct leaf), sizeof(struct tnode));
> -
> -	if (trie_local) {
> -		seq_printf(seq, "Local:\n");
> -		trie_collect_stats(trie_local, stat);
> -		trie_show_stats(seq, stat);
> -#ifdef CONFIG_IP_FIB_TRIE_STATS
> -		trie_show_usage(seq, &trie_local->stats);
> -#endif
> -	}
> -
> -	if (trie_main) {
> -		seq_printf(seq, "Main:\n");
> -		trie_collect_stats(trie_main, stat);
> -		trie_show_stats(seq, stat);
> -#ifdef CONFIG_IP_FIB_TRIE_STATS
> -		trie_show_usage(seq, &trie_main->stats);
> -#endif
> -	}
> -	kfree(stat);
> +		fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
>  
>  	return 0;
>  }

Keeping a 'size' counter is not necessary, since trie_collect_stats() must go
through all the tree and get this information for free.

This 'size' field only slows down inserts/deletes and dirty a cacheline that 
readers will hit.


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html