pid_max hang again...
Quoted 5 lines
As Manfred pointed out, pid allocation and inserting it into task list should be atomic. But going by the range of pids available in 2.5.33 (Linux made it 30-bits), it is unlikely that same pid will be given to two processes, since
last_pidis protected by single lock.
Right now there is quite a lot of code between get_pid and the insertion into the task list: copy mm, files, etc.
And just before the endless loop in get_pid(), there is only one pid left --> probability of getting the same pid again is high. If you fix the hang, you should fix the atomicity, too.
Quoted 5 lines
If
last_pidis withinPID_MAXandmax_pid_crossis set, this pid might have been given to another process. So, goto the corresponding hashlist and check for its existence. If no task with given pid found, thenget_pidis free to return pid as the available pid.
Doesn't work: find_task_by_pid() only checks task->pid. But the result of get_pid mustn't be in use as a session or tgid value either
--
Manfred
Quoted 5 lines · Manfred Spraul
Doesn't work:
find_task_by_pid()only checkstask->pid. But the result ofget_pidmustn't be in use as a session or tgid value either
Thanks to Manfred, to clarfy me further that my patch doesn't work. But I am still in feeling that current pid allocation can be improved. If we assume that the atomicity problem with pid allocation and linking task struct into process list can be ignored (sorry Manfred), does it make any sense to maintain a list of `freed' pids ? For me (some of others too !!), it makes lot of sense to re-use pids of exited processes.
If I am not wrong, an exiting process pid can be re-used (after the task dies) if its pid
1) not used as session ID (i.e p->session != p->pid) (or p->leader == 0)
2) not used as process group ID (p->pgrp != p->pid)
3) not used as thread group-ID (p->tgid != p->pid)
Lets us maintain a list of atmost (PAGE_SIZE /sizeof(pid)) entries for freed pids, protected by a spin_lock (freepid_lock) and let last_pid start from (300 + num_free_pids).
get_pid() looks in freepid_list first to get one free pid. If it finds one, sets its entry to zero and return this pid. If it couldn't find any free pid, then it continues as usual by incrementing last_pid and searching through entire task list. The hang problem might be due to holding the lock forever if pids are not free. Current approach does not re-look at the pids of exiting processes which might be waiting on tasklist_lock to free up its task_struct.
get_pid() {
if(pid = get_free_pid()) return pid;
// usual code of incrementing last_pid
// and comparing next_safe + searching in
// tasklist and exiting (with Paul's fix).
}get_free_pid() searches in freepid_list returns a free pid if it finds one, otherwise 0.
This approach reduces the search time and avoids holding of tasklist_lock for longer times.
A process exiting releases its pid to the freepid_list if its pid matches with about creteria.
Let me know if it is worth implementing this.
~Hanumanthu
Quoted 8 lines
Thanks to Manfred, to clarfy me further that my patch doesn't work. But I am still in feeling that current pid allocation can be improved. If we assume that the atomicity problem with pid allocation and linking task struct into process list can be ignored (sorry Manfred), does it make any sense to maintain a list of `freed' pids ? For me (some of others too !!), it makes lot of sense to re-use pids of exited processes.
Quoted 7 lines
If I am not wrong, an exiting process pid can be re-used (after the task dies) if its pid
1) not used as session ID (i.e
p->session!=p->pid) (orp->leader== 0)
2) not used as process group ID (p->pgrp!=p->pid)
3) not used as thread group-ID (p->tgid!=p->pid)
How do you track this? Can you keep a reference count for each PID and score 1 for each of the above usages (and one for normal use)? Or do you think it's better to just fall back to the current system in the non-trivial case?
Quoted 3 lines
Lets us maintain a list of atmost (
PAGE_SIZE/sizeof(pid)) entries for freed pids, protected by aspin_lock(freepid_lock) and letlast_pidstart from (300 +num_free_pids).
OK, well whilst you're at it, do you want make the free pid list per CPU with no locking, and make it even more efficient? ;-) We now have plenty of free PIDs to play with, and you could refill the list with 100 entries or so if you had to fall back to scanning. Actually, you could do that even if your current proposal doesn't work out ....
Quoted 1 line
Let me know if it is worth implementing this.
Personally, I think it'd be great ... the current scanning doesn't seem like an efficient algorithm at all.
M.
Quoted 32 lines · Martin J. Bligh
Quoted 8 lines
Thanks to Manfred, to clarfy me further that my patch doesn't work. But I am still in feeling that current pid allocation can be improved. If we assume that the atomicity problem with pid allocation and linking task struct into process list can be ignored (sorry Manfred), does it make any sense to maintain a list of `freed' pids ? For me (some of others too !!), it makes lot of sense to re-use pids of exited processes.
Quoted 7 lines
If I am not wrong, an exiting process pid can be re-used (after the task dies) if its pid
1) not used as session ID (i.e
p->session!=p->pid) (orp->leader== 0)
2) not used as process group ID (p->pgrp!=p->pid)
3) not used as thread group-ID (p->tgid!=p->pid)How do you track this? Can you keep a reference count for each PID and score 1 for each of the above usages (and one for normal use)? Or do you think it's better to just fall back to the current system in the non-trivial case?
Quoted 3 lines
Lets us maintain a list of atmost (
PAGE_SIZE/sizeof(pid)) entries for freed pids, protected by aspin_lock(freepid_lock) and letlast_pidstart from (300 +num_free_pids).OK, well whilst you're at it, do you want make the free pid list per CPU with no locking, and make it even more efficient? ;-) We now have plenty of free PIDs to play with, and you could refill the list with 100 entries or so if you had to fall back to scanning. Actually, you could do that even if your current proposal doesn't work out ....
Quoted 4 lines
Quoted 1 line
Let me know if it is worth implementing this.
Personally, I think it'd be great ... the current scanning doesn't seem like an efficient algorithm at all.
I don't like the idea of reusing recent pids at all.
The current repeated scanning is awful. I've been mulling this over in my mind for awhile now and i've had two thoughts.
If we insist on scanning the task list we should at least reap multiple pids. Have an array of free pids managed inside get_pid() that it pulls from until it runs out at which point it would do the scan to refill the array + 1 for immediate use.
Here is my better suggestion.
Dont destroy the task_struct of exited tasks that are session, thread group or process group leaders until last group member exits. Give them a status so that they don't show up in /proc. Heck go ahead and mark them as zombies if you want though i'd rather another status.
Preserved the pid number sort order of the prev_task/next_task list. It looks to me like this is already the case.
get_pid() continues to preserve next_safe.
Also preserve a task_struct *last_safe which would be set to the last pid created. release_task() whould update it to p->prev_task if last_safe == p.
get_pid() would use *last_safe->next_task to walk until it found a gap >= next_safe. (looping if it hits PID_MAX)
So by adding a couple of bits of logic in wait() and keeping around a relatively small number of task_structs for exited processes we can eliminate the scan alltogether.
Defering the release_task() for group leaders eliminates the need for rescanning and opens the possiblity of using find_task_by_pid() instead of scanning as someone recently suggested.
What have i missed? This seems much simpler than the other aproaches i've seen proposed. It should also be much more deterministic in behavior.
Signature · 5 lines
________________________________________________________________ J.W. Schultz Pegasystems Technologies email address: [email protected] Remember Cernan and Schmitt
Quoted 1 line · jw schultz
The current repeated scanning is awful.
I don't know what the problem is. The present scheme is very efficient on the average (since the pid space is very large, much larger than the number of processes, this scan is hardly ever done). All proposed alternatives are clumsy, incorrect, and much less efficient.
Andries
Quoted 9 lines · Andries Brouwer
Quoted 1 line · jw schultz
The current repeated scanning is awful.
I don't know what the problem is. The present scheme is very efficient on the average (since the pid space is very large, much larger than the number of processes, this scan is hardly ever done). All proposed alternatives are clumsy, incorrect, and much less efficient.
The scan itself i don't mind. It is the rescan that bothers me. That is bother as in almost, but not quite, an itch. "Awful" is perhaps an overstatement. I agree the space should be sparse enough to make rescans infrequent and i have trouble imagining what these systems must be like that the rescanning actually loops interminably. Increasing PID_MAX should make the pid space sparse enough to make the problem implausible.
I was just responding to the frequent discussions of "get_pid hang" and when i looked at get_pid said "yuck".
One of the bigger problems i have with the scan is the very idea that there are pids that cannot be used because they are still referenced but don't exist. That sounds lax to me. I can understand the advantage of it. The only place it seems to impact is get_pid. Keeping the task structs around would mean coping with them in several other places. It does occur to me that there could be some advantage to having these terminated session, thread and process group leaders show up in ps.
Well, i've put in my $0.02 plus interest.
Signature · 5 lines
________________________________________________________________ J.W. Schultz Pegasystems Technologies email address: [email protected] Remember Cernan and Schmitt