The hash table for task structures
As all the data structures representing processes (task_struct) are on a doubly linked list, any one can be found by searching the list linearly. This method can be time-consuming, particularly if there are a large number of processes. So, to speed things up, all the structures are also kept on hash lists, hashed on the pid of the process, and linked through the pidhash_next and pidhash_pprev fields of the task_struct. This section examines the hash structure itself, the hash function used, and how this whole mechanism is used to search for the task_struct representing a particular process.
3.2.1 The process hash table
An overview of the two sets of links holding the task_struct structures together, including the pidhash[] table, is shown in Figure 3.9. For simplicity, only the forward links are shown. The pidhash[ ] table is declared in kernel/fork.c as
*pidhash[]
|
task_struct | ||||
|
1 |
r |
k | ||
|
task_struct | ||||
|
1 |
k | |||
|
task_struct |
----n | |||
|
1 |
r |
k | ||
|
task_struct | ||||
|
1 |
r |
k | ||
|
task_struct | ||||
|
1 |
i |
k | ||
|
task_struct |
4----------------------- | |||
Figure 3.9 The process hash table
struct task_struct *pidhash[PIDHASH_SZ];
The constant PIDHASH_SZ is defined in < linux/sched.h > as:
so this table has 1024 entries. The hash table is initialised to NULL values by the function sched_init() (see Section 1.3.2).
3.2.2 The hash function
A simple hash function is used to spread entries evenly over this table. It is defined in < linux/sched.h > as:
525 #definepid_hashfn(x) ((((x) >> 8) A (x)) & (PIDHASH_SZ - 1))
The first part of the function tries to avoid clustering. The parameter x, the pid, is of type pid_t, which is architecture-specific, but is generally defined as an int, or 32 bits. However, the pid allocator uses only the low-order 16 bits of this int. The structure of a pid is shown in the top row of Figure 3.10.
|
zero |
high byte |
low byte |
|
zero |
high byte | |
|
zero |
high byte |
random |
Figure 3.10 Hashing a pid
Figure 3.10 Hashing a pid
The result after shifting this right 8 bits is shown in the middle of Figure 3.10. The result of the XOR between the two of them is shown at the bottom of Figure 3.10. Performing an XOR between the low byte and the high byte produces a fairly random least-significant 8 bits.
The bitwise AND (&) in the hash function guarantees that the result will not be greater than the number of slots in the hash table, as it effectively strips off all but the 10 low-order bits. PIDHASH_SZ - 1 is 1023, or 1111111111.
Because pids are given out more or less consecutively, the high byte will tend to be the same over a range of processes. The bitwise AND ignores the six most significant bits of this; these are the six most likely to be different. Despite all this, it would seem that in most cases just taking the 10 least- significant bits of the pid would give an adequate spread over the pidhash[] table.
3.2.3 Insert a task_struct into the hash table
Figure 3.11 from <linux/sched.h> shows the function hash_pid(), which inserts a given task_struct at the appropriate place in this hash table.
526 static inline void hash_pid(struct task_struct *p)
527 {
528 struct task_struct **htable =
529 &pidhash[pid_hashfn(p->pid)];
if((p->pidhash_next =*htable) ! = (*htable)->pidhash_pprev = < *htable = p;
p->pidhash_pprev = htable;
NULL)
p->pidhash_next;
Figure 3.11 Function to insert a task_struct into the hash table
528-529 working from right to left, this hashes the pid to an index into the array (using the function from Section 0), and the variable htable is initialised to point to that entry in the hash table. At this stage htable points to a pointer to the first entry in the appropriate chain (see the top of Figure 3.12).
- Lines 530-531
- . NULL
Line 532
- Figure 3.12 Inserting a task_struct
530-531 the new task_struct is always inserted at the head of the chain. Remember that *htable is the pointer in the hash table, pointing to the first entry in the chain. The value from that entry in the hash table (the head of the chain) is copied into the pidhash_next field of the new task_struct. Then, if it is a valid pointer, implying that there is at least one entry in that chain beforehand, the pprev pointer of the old first entry is set to point to the pidhash_next field of the new entry (remember that pprev is declared as an indirect pointer); see the middle of Figure 3.12.
532 whether there is a previous entry on the chain or not, this sets the header entry to point to the new task_struct; see the bottom of Figure 3.12.
533 finally, the pprev entry in the new task_struct is set to point to whatever htable is pointing to - the head of the chain.
3.2.4 Remove a task_struct from the hash table
Figure 3.13, from <linux/sched.h>, shows the function that unlinks a task_struct from the hash table. It is only ever called from unhash_process() (see Section 9.4.2.3).
536 static inline voidunhash_pid(struct task_struct *p)
537 {
538 if(p->pidhash_next)
539 p->pidhash_next->pidhash_pprev = p->pidhash_pprev;
540 *p->pidhash_pprev = p->pidhash_next;
541 }
Figure 3.13 Remove a task_struct from the hash table 536 the parameter is a pointer to the task_struct to be removed from the table.
538-539 if the parameter is not the last entry on its chain, the back pointer of its successor is set to point to its predecessor.
540 the forward pointer of the predecessor of the parameter is always set to point to its successor. If it is the only entry on its chain, this will in fact be equal to the header entry in the hash table entry, now pointing to NULL.
Note that pidhash_pprev is declared as an indirect pointer in Section 2.3. It does not point to the beginning of the previous entry, but to the link field in that entry, which is itself a pointer field (see Figure 3.14).
Figure 3.14 Adjusting pointers in a hash chain p
Figure 3.14 Adjusting pointers in a hash chain
Continue reading here: Setting up the idle thread
Was this article helpful?