fix PID hash sizing

PATCH In review Nick Piggin 5 participants 10 messages Aug 22, 2004 – Sep 6, 2004

Subsystems (2)

Memory management Page allocator

lore

Share & tools

lore

Nick Piggin

author

2004-08-22 04:48 UTC #0 lore raw

PATCH 1/2 fix PID hash sizing

I see PID hash sizing problems on an Opteron.
I thought this got fixed a while ago? Hm.

Export nr_kernel_pages, nr_all_pages. Use nr_kernel_pages when sizing the PID hash. This fixes a sizing problem I'm seeing with the x86-64 kernel on an Opteron.

---

 linux-2.6-npiggin/include/linux/bootmem.h |    3 +++
 linux-2.6-npiggin/kernel/pid.c            |    2 +-
 linux-2.6-npiggin/mm/page_alloc.c         |    4 ++--
 3 files changed, 6 insertions(+), 3 deletions(-)

kernel/pid.c renamed from kernel/pid.c~pid-hash-alloc +1 -1

diff -puN kernel/pid.c~pid-hash-alloc kernel/pid.c
@@ -276,7 +276,7 @@ int kgdb_pid_init_done; /* so we don't c
 void __init pidhash_init(void)
 {
 	int i, j, pidhash_size;
-	unsigned long megabytes = max_pfn >> (20 - PAGE_SHIFT);
+	unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);
 
 	pidhash_shift = max(4, fls(megabytes * 4));
 	pidhash_shift = min(12, pidhash_shift);

include/linux/bootmem.h renamed from include/linux/bootmem.h~pid-hash-alloc +3 -0

diff -puN include/linux/bootmem.h~pid-hash-alloc include/linux/bootmem.h
@@ -67,6 +67,9 @@ extern void * __init __alloc_bootmem_nod
 	__alloc_bootmem_node((pgdat), (x), PAGE_SIZE, 0)
 #endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
 
+extern unsigned long __initdata nr_kernel_pages;
+extern unsigned long __initdata nr_all_pages;
+
 extern void *__init alloc_large_system_hash(const char *tablename,
 					    unsigned long bucketsize,
 					    unsigned long numentries,

mm/page_alloc.c renamed from mm/page_alloc.c~pid-hash-alloc +2 -2

diff -puN mm/page_alloc.c~pid-hash-alloc mm/page_alloc.c
@@ -55,8 +55,8 @@ EXPORT_SYMBOL(zone_table);
 static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" };
 int min_free_kbytes = 1024;
 
-static unsigned long __initdata nr_kernel_pages;
-static unsigned long __initdata nr_all_pages;
+unsigned long __initdata nr_kernel_pages;
+unsigned long __initdata nr_all_pages;
 
 /*
  * Temporary debugging check for pages not lying within a given zone.

Nick Piggin

author

2004-08-22 04:49 UTC #1 lore raw

PATCH 2/2 use hlist for pid hash

Any reason why this shouldn't be done? Anyone know of a decent test that stresses the pid hash?

Use hlists for the PID hashes. This halves the memory footprint of these hashes. No benchmarks, but I think this is a worthy improvement because the hashes are something that would be likely to have significant portions loaded into the cache of every CPU on some workloads.

This comes at the "expense" of
1. reintroducing the memory prefetch into the hash traversal loop;
2. adding new pids to the head of the list instead of the tail. I suspect that if this was a big problem then the hash isn't sized well or could benefit from moving hot entries to the head.

Also, account for all the pid hashes when reporting hash memory usage.

---

 linux-2.6-npiggin/include/linux/pid.h |    2 +-
 linux-2.6-npiggin/kernel/pid.c        |   19 ++++++++++---------
 2 files changed, 11 insertions(+), 10 deletions(-)

kernel/pid.c renamed from kernel/pid.c~pid-use-hlist +10 -9

diff -puN kernel/pid.c~pid-use-hlist kernel/pid.c
@@ -27,7 +27,7 @@
 #include <linux/hash.h>
 
 #define pid_hashfn(nr) hash_long((unsigned long)nr, pidhash_shift)
-static struct list_head *pid_hash[PIDTYPE_MAX];
+static struct hlist_head *pid_hash[PIDTYPE_MAX];
 static int pidhash_shift;
 
 int pid_max = PID_MAX_DEFAULT;

@@ -150,11 +150,11 @@ failure:
 
 fastcall struct pid *find_pid(enum pid_type type, int nr)
 {
-	struct list_head *elem, *bucket = &pid_hash[type][pid_hashfn(nr)];
+	struct hlist_node *elem;
 	struct pid *pid;
 
-	__list_for_each(elem, bucket) {
-		pid = list_entry(elem, struct pid, hash_chain);
+	hlist_for_each_entry(pid, elem,
+			&pid_hash[type][pid_hashfn(nr)], hash_chain) {
 		if (pid->nr == nr)
 			return pid;
 	}

@@ -181,7 +181,8 @@ int fastcall attach_pid(task_t *task, en
 		INIT_LIST_HEAD(&pid->task_list);
 		pid->task = task;
 		get_task_struct(task);
-		list_add(&pid->hash_chain, &pid_hash[type][pid_hashfn(nr)]);
+		hlist_add_head(&pid->hash_chain,
+				&pid_hash[type][pid_hashfn(nr)]);
 	}
 	list_add_tail(&task->pids[type].pid_chain, &pid->task_list);
 	task->pids[type].pidptr = pid;

@@ -200,7 +201,7 @@ static inline int __detach_pid(task_t *t
 		return 0;
 
 	nr = pid->nr;
-	list_del(&pid->hash_chain);
+	hlist_del(&pid->hash_chain);
 	put_task_struct(pid->task);
 
 	return nr;

@@ -282,9 +283,9 @@ void __init pidhash_init(void)
 	pidhash_shift = min(12, pidhash_shift);
 	pidhash_size = 1 << pidhash_shift;
 
-	printk("PID hash table entries: %d (order %d: %Zd bytes)\n",
+	printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
 		pidhash_size, pidhash_shift,
-		pidhash_size * sizeof(struct list_head));
+		PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head));
 
 	for (i = 0; i < PIDTYPE_MAX; i++) {
 		pid_hash[i] = alloc_bootmem(pidhash_size *

@@ -292,7 +293,7 @@ void __init pidhash_init(void)
 		if (!pid_hash[i])
 			panic("Could not alloc pidhash!\n");
 		for (j = 0; j < pidhash_size; j++)
-			INIT_LIST_HEAD(&pid_hash[i][j]);
+			INIT_HLIST_HEAD(&pid_hash[i][j]);
 	}
 #ifdef CONFIG_KGDB
 	kgdb_pid_init_done++;

include/linux/pid.h renamed from include/linux/pid.h~pid-use-hlist +1 -1

diff -puN include/linux/pid.h~pid-use-hlist include/linux/pid.h
@@ -16,7 +16,7 @@ struct pid
 	atomic_t count;
 	struct task_struct *task;
 	struct list_head task_list;
-	struct list_head hash_chain;
+	struct hlist_node hash_chain;
 };
 
 struct pid_link

David S. Miller

2004-08-22 05:01 UTC #2 lore raw

Re: [PATCH 2/2] use hlist for pid hash

Quoted 2 lines · On Sun, 22 Aug 2004 14:46:38 +1000 Nick Piggin <[email protected]> wrote:

Any reason why this shouldn't be done? Anyone know of a decent test that stresses the pid hash?

I can't think of any way in which this could decrease performance. I highly recommend this patch :-)

Nick Piggin

author

2004-08-22 05:34 UTC #3 lore raw

Re: [PATCH 2/2] use hlist for pid hash

Quoted 11 lines · David S. Miller

Quoted 2 lines · On Sun, 22 Aug 2004 14:46:38 +1000 Nick Piggin <[email protected]> wrote:
Any reason why this shouldn't be done? Anyone know of a decent test that stresses the pid hash?
I can't think of any way in which this could decrease performance. I highly recommend this patch :-)

Oh good :)

The only thing that could hurt is that the hash list traversal in find_pid now does prefetch.

This would be trivial to remove by introducing another list.h entity similar to __list_for_each for hlists, however I would have thought that if anything, the prefetch might help a tiny bit on the odd workloads where the number of tasks is much greater than the number of hash entries. Ingo? WLI?

I expect you could get a good bit of overlap on the prefetch if the next hash pointer isn't in the same cacheline as ->nr... although, on a 64-bit architecture with a 32byte cacheline size, this is guaranteed to be the case. Why not put them together?

---

 linux-2.6-npiggin/include/linux/pid.h |    3 ++-
 1 files changed, 2 insertions(+), 1 deletion(-)

include/linux/pid.h renamed from include/linux/pid.h~pid-search-cacheline +2 -1

diff -puN include/linux/pid.h~pid-search-cacheline include/linux/pid.h
@@ -12,11 +12,12 @@ enum pid_type
 
 struct pid
 {
+	/* Try to keep hash_chain in the same cacheline as nr for find_pid */
+	struct hlist_node hash_chain;
 	int nr;
 	atomic_t count;
 	struct task_struct *task;
 	struct list_head task_list;
-	struct hlist_node hash_chain;
 };
 
 struct pid_link

Ryan Cumming

2004-08-22 05:26 UTC #4 lore raw

Re: [PATCH 2/2] use hlist for pid hash

In reply to Nick Piggin

Quoted 5 lines · you

This comes at the "expense" of
1. reintroducing the memory prefetch into the hash traversal loop;
2. adding new pids to the head of the list instead of the tail. I suspect that if this was a big problem then the hash isn't sized well or could benefit from moving hot entries to the head.

It looks like the current code is already adding PIDs to the head: list_add() adds to the head of a list and list_add_tail() adds to the tail.

-Ryan

Nick Piggin

author

2004-08-22 05:29 UTC #5 lore raw

Re: [PATCH 2/2] use hlist for pid hash

Quoted 11 lines · Ryan Cumming

Quoted 5 lines · you
This comes at the "expense" of
1. reintroducing the memory prefetch into the hash traversal loop;
2. adding new pids to the head of the list instead of the tail. I suspect that if this was a big problem then the hash isn't sized well or could benefit from moving hot entries to the head.
It looks like the current code is already adding PIDs to the head: list_add() adds to the head of a list and list_add_tail() adds to the tail.

Hmm, so it is. I must have been looking at the task_list list when I was thinking that. Well, all the better.

Anton Blanchard

2004-09-06 11:38 UTC #6 lore raw

PATCH 1/1 Allocate correct amount of memory for pid hash

In reply to Nick Piggin

Hi Nick,

Quoted 5 lines

Use hlists for the PID hashes. This halves the memory footprint of these hashes. No benchmarks, but I think this is a worthy improvement because the hashes are something that would be likely to have significant portions loaded into the cache of every CPU on some workloads.

Quoted 7 lines

This comes at the "expense" of
1. reintroducing the memory prefetch into the hash traversal loop;
2. adding new pids to the head of the list instead of the tail. I suspect that if this was a big problem then the hash isn't sized well or could benefit from moving hot entries to the head.
Also, account for all the pid hashes when reporting hash memory usage.

It looks like we are now allocating twice as much memory as required. How does this look?

Signed-off-by Anton Blanchard <[email protected]>

kernel/pid.c renamed from kernel/pid.c~fix_freemem_reporting +1 -1

diff -puN kernel/pid.c~fix_freemem_reporting kernel/pid.c
@@ -278,7 +278,7 @@ void __init pidhash_init(void)
 
 	for (i = 0; i < PIDTYPE_MAX; i++) {
 		pid_hash[i] = alloc_bootmem(pidhash_size *
-					sizeof(struct list_head));
+					sizeof(struct hlist_head));
 		if (!pid_hash[i])
 			panic("Could not alloc pidhash!\n");
 		for (j = 0; j < pidhash_size; j++)

Nick Piggin

author

2004-09-06 11:41 UTC #7 lore raw

Re: [PATCH] Allocate correct amount of memory for pid hash

Quoted 6 lines · Anton Blanchard

Quoted 1 line
Also, account for all the pid hashes when reporting hash memory usage.
It looks like we are now allocating twice as much memory as required. How does this look?

Fine. Good catch thanks Anton.

William Lee Irwin III

2004-08-22 12:32 UTC #8 lore raw

In reply to Nick Piggin

Quoted 5 lines · Nick Piggin

I see PID hash sizing problems on an Opteron.
I thought this got fixed a while ago? Hm.
Export nr_kernel_pages, nr_all_pages. Use nr_kernel_pages when sizing the PID hash. This fixes a sizing problem I'm seeing with the x86-64 kernel on an Opteron.

Please describe the the pid hash sizing problem.

-- wli

Nick Piggin

author

2004-08-23 00:16 UTC #9 lore raw

Quoted 13 lines · William Lee Irwin III

Quoted 6 lines · Nick Piggin
I see PID hash sizing problems on an Opteron.
I thought this got fixed a while ago? Hm.
Export nr_kernel_pages, nr_all_pages. Use nr_kernel_pages when sizing the PID hash. This fixes a sizing problem I'm seeing with the x86-64 kernel on an Opteron.
Please describe the the pid hash sizing problem.

max_pfn isn't set up at that time yet, I'm guessing. I didn't look into it further than that.