pidhash: Refactor the pid hash table.
Subsystems (3)
PATCH 1/1 pidhash: Refactor the pid hash table.
This splits the current struct pid into two structures, struct pid and struct pid_link, and reduces our number of hash tables from PIDTYPE_MAX to just one. struct pid_link is the per process linkage into the hash tables and lives in struct task_struct. struct pid is given an indepedent lifetime, and holds pointers to each of the pid types.
The independent life of struct pid simplifies attach_pid, and detach_pid, because we are always manipulating the list of pids and not the hash table. In addition in giving struct pid an indpendent life it makes the concept much more powerful.
Kernel data structurs can now embed a struct pid * instead of a pid_t and not suffer from pid wrap around problems or from keeping unnecessarily large amounts of memory allocated.
---
Andrew this patch is largely indepedent of previous work but it does have a couple of dependencies.
Oleg's pids-kill-pidtype_tgid, pidhash-dont-count-idle-threads My make-setsid-more-robust, and kill-switch_exec_pids
This patch conflicts with and obsoletes:
tref-fix-task_ref-reference-counting-ensure-the-references-is-always-on-the-first-task tref-fix-task_ref-reference-counting-fix tref-fix-task_ref-reference-counting tref-implement-task-references-kill-init_tref tref-implement-task-references
Sorry to for sending you a patch that falls in the middle of a stack like this but it seems the only sane way to implement this.
include/linux/pid.h | 90 +++++++++++++++++---- include/linux/sched.h | 4 - kernel/fork.c | 16 ++-- kernel/pid.c | 213 ++++++++++++++++++++++++++++++++++--------------- 4 files changed, 233 insertions(+), 90 deletions(-)
f841047af05e375118496679f34cb5942a91a53e
include/linux/pid.h +76 -14
@@ -1,6 +1,8 @@#ifndef _LINUX_PID_H#define _LINUX_PID_H +#include <linux/rcupdate.h> +enum pid_type { PIDTYPE_PID,
@@ -9,18 +11,61 @@ enum pid_typePIDTYPE_MAX }; +/* What is struct pid? +* +* A struct pid is the kernels internal notion of a process identier. +* It refers to individual tasks, process groups, and sessions. While +* there are processes attached to it the struct pid lives in a hash +* table, so it and then the processes that it refers to it can be found +* quickly from the numeric pid value. The attached processes may be +* quickly access by following pointers from struct pid. +* +* Storing pid_t values in the kernel and refering to them later has a +* problem. The process originally with that pid may have exited the +* pid allocator wrapped, and another process could have come along +* and been assigned that pid. +* +* Refering to user space process by holding a reference to struct +* task_struct has a problem. When the user space process exit +* the now useless task_struct still kept. A task_struct plus a +* stack consumes around 10K of low kernel memory. More precisely +* this is THREAD_SIZE + sizeof(struct task_struct). By comparison +* a struct pid is about 64 bytes. +* +* Holding a reference to struct pid solves both of these problems. +* It is small so holding a reference does not consume a lot of +* resources, and since a new struct pid is allocated when the numeric +* pid value is reused when don't mistakenly refer to new process. +*/ +struct pid { +atomic_t count;/* Try to keep pid_chain in the same cacheline as nr for find_pid */ int nr;struct hlist_node pid_chain; -/* list of pids with the same nr, only one of them is in the hash */ -struct list_head pid_list; +/* lists of tasks that use this pid */ +struct hlist_head tasks[PIDTYPE_MAX ]; +struct rcu_head rcu; }; -#define pid_task (elem, type) \ - list_entry(elem, struct task_struct, pids[type].pid_list) +struct pid_link +{ +struct hlist_node node; +struct pid *pid; +}; +static inline struct pid *get_pid (struct pid *pid) +{ +if (pid) +atomic_inc (&pid->count); +return pid; +} + +extern void FASTCALL (put_pid (struct pid *pid)); +extern struct task_struct *FASTCALL (pid_task (struct pid *pid,enum pid_type )); +extern struct task_struct *FASTCALL (get_pid_task (struct pid *pid,enum pid_type )); +/* * attach_pid() and detach_pid() must be called with the tasklist_lock * write-held.
@@ -31,23 +76,40 @@ extern void FASTCALL(detach_pid(struct t/* * look up a PID in the hash table. Must be called with the tasklist_lock -* held. +* or rcu_read_lock() held. */ -extern struct pid *FASTCALL (find_pid (enum pid_type ,int )); +extern struct pid *FASTCALL (find_pid (int nr)); -extern int alloc_pidmap (void ); -extern void FASTCALL (free_pidmap (int )); +/* +* Lookup a PID in the hash table, and return with it's count elevated. +*/ +extern struct pid *find_get_pid (int nr); + +extern struct pid *alloc_pid (void ); +extern void FASTCALL (free_pid (struct pid *pid)); + +#define pid_next (task, type) \ + ((task)->pids[(type)].node.next) +#define pid_next_task (task, type) \ + hlist_entry(pid_next(task, type), struct task_struct, pids[(type)].node) + + +/* We could use hlist_for_each_entry_rcu here but it takes more arguments +* than the do_each_task_pid/while_each_task_pid. So we roll our own +* to preserve the existing interface. +*/ #define do_each_task_pid (who, type, task) \ if ((task = find_task_by_pid_type(type, who))) { \ - prefetch((task)->pids[type].pid_list.next); \ + prefetch(pid_next(task, type)); \ do {#define while_each_task_pid (who, type, task) \ - } while (task = pid_task((task)->pids[type].pid_list.next,\ - type), \ - prefetch((task)->pids[type].pid_list.next), \ - hlist_unhashed(&(task)->pids[type].pid_chain)); \ - } \ + } while (pid_next(task, type) && ({ \ + task = pid_next_task(task, type); \ + rcu_dereference(task); \ + prefetch(pid_next(task, type)); \ + 1; }) ); \ + }#endif /* _LINUX_PID_H */
include/linux/sched.h +2 -2
@@ -764,7 +764,7 @@ struct task_struct {struct task_struct *group_leader;/* threadgroup leader */ /* PID/PID hash table linkage. */ -struct pid pids[PIDTYPE_MAX ]; +struct pid_link pids[PIDTYPE_MAX ];struct list_head thread_group;struct completion *vfork_done;/* for vfork() */
@@ -902,7 +902,7 @@ static inline pid_t process_group(struct*/ static inline int pid_alive (struct task_struct *p) { -return p->pids[PIDTYPE_PID ].nr !=0 ; +return p->pids[PIDTYPE_PID ].pid !=NULL ; }extern void free_task (struct task_struct *tsk);
kernel/fork.c +9 -7
@@ -1304,17 +1304,19 @@ long do_fork(unsigned long clone_flags, {struct task_struct *p;int trace =0 ; -long pid =alloc_pidmap (); +struct pid *pid =alloc_pid (); +long nr; -if (pid <0 ) +if (!pid)return -EAGAIN ; + nr = pid->nr;if (unlikely (current->ptrace)) { trace =fork_traceflag (clone_flags);if (trace) clone_flags |=CLONE_PTRACE ; } - p =copy_process (clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr, pid); + p =copy_process (clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr, nr);/* * Do this prior waking up the new thread - the thread pointer * might get invalid after that point, if the thread exits quickly.
@@ -1341,7 +1343,7 @@ long do_fork(unsigned long clone_flags, p->state =TASK_STOPPED ;if (unlikely (trace)) { - current->ptrace_message = pid; + current->ptrace_message = nr;ptrace_notify ((trace <<8 ) |SIGTRAP ); }
@@ -1351,10 +1353,10 @@ long do_fork(unsigned long clone_flags,ptrace_notify ((PTRACE_EVENT_VFORK_DONE <<8 ) |SIGTRAP ); } }else { -free_pidmap (pid); - pid =PTR_ERR (p); +free_pid (pid); + nr =PTR_ERR (p); } -return pid; +return nr; }#ifndef ARCH_MIN_MMSTRUCT_ALIGN
kernel/pid.c +146 -67
299 lines not on this page · raw message
Signature · 1 line
1.2.2.g709a-dirty
kernel/pid.c int alloc_pidmap(void) · line 154
Quoted 9 lines · [email protected] (Eric W. Biederman) wrote:
kernel/pid.c +8
-0+fastcall void put_pid(struct pid *pid) +{ +if (!pid) +return ; +if ((atomic_read (&pid->count) ==1 ) || +atomic_dec_and_test (&pid->count)) +kmem_cache_free (pid_cachep, pid); +}
This looks odd. It's an RCU callback so it's asynchronous. It doesn't take any locks, so if anyone else can have a ref on this thing then the refcount can change at any time.
And both sides of the || are basically equivalent. Perhaps you meant &&. But I'm more worried by the apparent raciness?
Quoted 15 lines · Andrew Morton
kernel/pid.c int alloc_pidmap(void) · line 154
Quoted 9 lines · [email protected] (Eric W. Biederman) wrote:
kernel/pid.c +8
-0+fastcall void put_pid(struct pid *pid) +{ +if (!pid) +return ; +if ((atomic_read (&pid->count) ==1 ) || +atomic_dec_and_test (&pid->count)) +kmem_cache_free (pid_cachep, pid); +}This looks odd. It's an RCU callback so it's asynchronous. It doesn't take any locks, so if anyone else can have a ref on this thing then the refcount can change at any time.
Quoted 2 lines
And both sides of the || are basically equivalent. Perhaps you meant &&. But I'm more worried by the apparent raciness?
The || was deliberate.
I expect the count to usually be 1. So the atomic_read optimizes out the atomic operation in the common case. skb_put and kref_put do it for the same reason.
As for the raciness, that is an interesting case.
Because the decrement is in the rcu callback the count of the structure is guaranteed to be at least one the entire time the structure is reachable in an rcu safe manner. So during that interval the count can go up or down, safely and atomically, and it won't reach zero.
After the structure stops being reachable in an rcu protected manner through the hash table it devolves into a simple reference counted structure. Now unless something like /proc captured this pid it will have a count of exactly one, and I expect this to be relatively common.
So if pid->count == 1 it means I own the only reference, and can do what I please with this structure.
If pid->count > 1 then I don't own the only reference and someone may be racing with me. In that case I do need to do the full atomic_dec_and_test to see if I have the very last reference to this structure.
I wasn't certain which part of this you were confused about so I tried to cover all of my bases. Hopefully I have cleared up your confusion.
Eric