JKH project..

Junior kernel hacker project..

the fork syscall has to check the new PID against all exixting pids..

here's the current code.. when teh PID-space starts becoming
"fragmented.."  this starts to take "real time".

retry:
        /*
         * If the process ID prototype has wrapped around,
         * restart somewhat above 0, as the low-numbered procs
         * tend to include daemons that don't exit.
         */
        if (trypid >= PID_MAX) {
                trypid = trypid % PID_MAX;
                if (trypid < 100)
                        trypid += 100;
                pidchecked = 0;
        }
        if (trypid >= pidchecked) {
                int doingzomb = 0;

                pidchecked = PID_MAX;
                /*
                 * Scan the active and zombie procs to check whether
this pid
                 * is in use.  Remember the lowest pid that's greater
                 * than trypid, so we can avoid checking for a while.
                 */
                p2 = LIST_FIRST(&allproc);
again:
                for (; p2 != NULL; p2 = LIST_NEXT(p2, p_list)) {
                        PROC_LOCK(p2);
                        while (p2->p_pid == trypid ||
                            (p2->p_pgrp != NULL &&
                            (p2->p_pgrp->pg_id == trypid ||
                            (p2->p_session != NULL &&
                            p2->p_session->s_sid == trypid)))) {
                                trypid++;
                                if (trypid >= pidchecked) {
                                        PROC_UNLOCK(p2);
                                        goto retry;
                                }
                        }
                        if (p2->p_pid > trypid && pidchecked >
p2->p_pid)
                                pidchecked = p2->p_pid;
                        if (p2->p_pgrp != NULL) {
                                if (p2->p_pgrp->pg_id > trypid &&
                                    pidchecked > p2->p_pgrp->pg_id)
                                        pidchecked = p2->p_pgrp->pg_id;
                                if (p2->p_session != NULL &&
                                    p2->p_session->s_sid > trypid &&
                                    pidchecked > p2->p_session->s_sid)
                                        pidchecked =
p2->p_session->s_sid;
                        }
                        PROC_UNLOCK(p2);
                }
                if (!doingzomb) {
                        doingzomb = 1;
                        p2 = LIST_FIRST(&zombproc);
                        goto again;
                }
        }

with several thousand processes, forking a lot, this starts to take 
a 'noticable' amount of time.

a small amount of time could be spent on trying to work out an
O(1) solution to this.

Possibly a small separate PID object that keeps reference counts
of how many procs refer to it in various ways, and lives in a
hash-table, and is freed when there are no more processes referring to
it.

Suggestions welcome.. :-)

julian