Re: [PATCH] tracing: use hash table to simulate the sparse array

[Frederic Weisbecker]

On Tue, Jun 30, 2009 at 04:47:38PM +0800, Lai Jiangshan wrote:
> Lai Jiangshan wrote:
> > 
> > Subject: [PATCH] tracing: rewrite trace_save_cmdline()
> > 
> > I found the sparse array map_pid_to_cmdline[PID_MAX_DEFAULT+1]
> > wastes too much memory, so I remove it.
> > 
> > The old FIFO algorithm is replaced with a new one:
> > Open address hash table with double hash + tick-LRU.
> > 
> > Signed-off-by: Lai Jiangshan <laijs@xxxxxxxxxxxxxx>
> > ---
> 
> This patch reduces the memory usage.(save 128K memory in kernel)
> But it's too complicated, and it changes the original algorithm.
> 
> This new patch does NOT change the original algorithm,
> but it uses a hash table to simulate the sparse array.
> 
> ---------------
> 
> Subject: [PATCH] tracing: use hash table to simulate the sparse array
> 
> I found the sparse array map_pid_to_cmdline[PID_MAX_DEFAULT+1]
> wastes too much memory, so I remove it.
> 
> A hash table is added to simulate the sparse array. And
> map_pid_to_cmdline and map_cmdline_to_pid become light functions.
> 
> map_pid_to_cmdline[pid] ==> map_pid_to_cmdline(pid)
> map_cmdline_to_pid[idx] ==> map_cmdline_to_pid(idx)
> 
> [Impact: save about 127k memory]
> 
> Signed-off-by: Lai Jiangshan <laijs@xxxxxxxxxxxxxx>
> ---
> diff --git a/kernel/trace/trace.c b/kernel/trace/trace.c
> index 3aa0a0d..3526b9c 100644
> --- a/kernel/trace/trace.c
> +++ b/kernel/trace/trace.c
> @@ -36,6 +36,7 @@
>  #include <linux/poll.h>
>  #include <linux/gfp.h>
>  #include <linux/fs.h>
> +#include <linux/hash.h>
>  
>  #include "trace.h"
>  #include "trace_output.h"
> @@ -648,10 +649,47 @@ void tracing_reset_current_online_cpus(void)
>  	tracing_reset_online_cpus(&global_trace);
>  }
>  
> -#define SAVED_CMDLINES 128
> +#define SAVED_CMDLINES_SHIFT 7
> +#define SAVED_CMDLINES (1 << 7)
>  #define NO_CMDLINE_MAP UINT_MAX
> -static unsigned map_pid_to_cmdline[PID_MAX_DEFAULT+1];
> -static unsigned map_cmdline_to_pid[SAVED_CMDLINES];
> +
> +struct cmdline_index {
> +	struct hlist_node node;
> +	unsigned int pid;
> +};
> +
> +struct hlist_head map_head[SAVED_CMDLINES];
> +struct cmdline_index indexes[SAVED_CMDLINES];
> +
> +static unsigned int map_pid_to_cmdline(unsigned int pid)
> +{
> +	struct cmdline_index *index;
> +	struct hlist_node *n;
> +	unsigned int hash = hash_32(pid, SAVED_CMDLINES_SHIFT);
> +
> +	hlist_for_each_entry(index, n, &map_head[hash], node) {
> +		if (index->pid == pid)
> +			return index - indexes;
> +	}
> +
> +	return NO_CMDLINE_MAP;
> +}
> +
> +static unsigned int map_cmdline_to_pid(unsigned int idx)
> +{
> +	return indexes[idx].pid;
> +}
> +
> +static void do_map_cmdline_index(unsigned int idx, unsigned int pid)
> +{
> +	unsigned int hash = hash_32(pid, SAVED_CMDLINES_SHIFT);
> +
> +	if (map_cmdline_to_pid(idx) != NO_CMDLINE_MAP)
> +		hlist_del(&indexes[idx].node);
> +	indexes[idx].pid = pid;
> +	hlist_add_head(&indexes[idx].node, &map_head[hash]);
> +}



If I understand well, you won't ever have more than one
entry per map_head[x]

So why are you using a hashlist that supports more than one
entry (the use of hlist_head op).

You could use a simple hashlist with only one entry on each
index to map the pid.

But the background idea of your patch looks good indeed.

Thanks.


> +
>  static char saved_cmdlines[SAVED_CMDLINES][TASK_COMM_LEN];
>  static int cmdline_idx;
>  static raw_spinlock_t trace_cmdline_lock = __RAW_SPIN_LOCK_UNLOCKED;
> @@ -661,8 +699,7 @@ static atomic_t trace_record_cmdline_disabled __read_mostly;
>  
>  static void trace_init_cmdlines(void)
>  {
> -	memset(&map_pid_to_cmdline, NO_CMDLINE_MAP, sizeof(map_pid_to_cmdline));
> -	memset(&map_cmdline_to_pid, NO_CMDLINE_MAP, sizeof(map_cmdline_to_pid));
> +	memset(&indexes, NO_CMDLINE_MAP, sizeof(indexes));
>  	cmdline_idx = 0;
>  }
>  
> @@ -754,9 +791,9 @@ void trace_stop_cmdline_recording(void);
>  
>  static void trace_save_cmdline(struct task_struct *tsk)
>  {
> -	unsigned pid, idx;
> +	unsigned int idx;
>  
> -	if (!tsk->pid || unlikely(tsk->pid > PID_MAX_DEFAULT))
> +	if (!tsk->pid)
>  		return;
>  
>  	/*
> @@ -768,22 +805,11 @@ static void trace_save_cmdline(struct task_struct *tsk)
>  	if (!__raw_spin_trylock(&trace_cmdline_lock))
>  		return;
>  
> -	idx = map_pid_to_cmdline[tsk->pid];
> +	idx = map_pid_to_cmdline(tsk->pid);
>  	if (idx == NO_CMDLINE_MAP) {
>  		idx = (cmdline_idx + 1) % SAVED_CMDLINES;
>  
> -		/*
> -		 * Check whether the cmdline buffer at idx has a pid
> -		 * mapped. We are going to overwrite that entry so we
> -		 * need to clear the map_pid_to_cmdline. Otherwise we
> -		 * would read the new comm for the old pid.
> -		 */
> -		pid = map_cmdline_to_pid[idx];
> -		if (pid != NO_CMDLINE_MAP)
> -			map_pid_to_cmdline[pid] = NO_CMDLINE_MAP;
> -
> -		map_cmdline_to_pid[idx] = tsk->pid;
> -		map_pid_to_cmdline[tsk->pid] = idx;
> +		do_map_cmdline_index(idx, tsk->pid);
>  
>  		cmdline_idx = idx;
>  	}
> @@ -802,14 +828,9 @@ void trace_find_cmdline(int pid, char comm[])
>  		return;
>  	}
>  
> -	if (pid > PID_MAX_DEFAULT) {
> -		strcpy(comm, "<...>");
> -		return;
> -	}
> -
>  	preempt_disable();
>  	__raw_spin_lock(&trace_cmdline_lock);
> -	map = map_pid_to_cmdline[pid];
> +	map = map_pid_to_cmdline(pid);
>  	if (map != NO_CMDLINE_MAP)
>  		strcpy(comm, saved_cmdlines[map]);
>  	else
> @@ -2458,7 +2479,7 @@ tracing_saved_cmdlines_read(struct file *file, char __user *ubuf,
>  	for (i = 0; i < SAVED_CMDLINES; i++) {
>  		int r;
>  
> -		pid = map_cmdline_to_pid[i];
> +		pid = map_cmdline_to_pid(i);
>  		if (pid == -1 || pid == NO_CMDLINE_MAP)
>  			continue;
>  
> 
> 
> 
> 
> 
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/