From owner-freebsd-current@FreeBSD.ORG  Sun Apr 11 15:51:49 2004
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id AA42E16A4CE
	for <current@freebsd.org>; Sun, 11 Apr 2004 15:51:49 -0700 (PDT)
Received: from sccrmhc13.comcast.net (sccrmhc13.comcast.net [204.127.202.64])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 5BB8643D31
	for <current@freebsd.org>; Sun, 11 Apr 2004 15:51:49 -0700 (PDT)
	(envelope-from julian@elischer.org)
Received: from interjet.elischer.org ([24.7.73.28])
          by comcast.net (sccrmhc13) with ESMTP
          id <20040411225148016003gpo9e>; Sun, 11 Apr 2004 22:51:48 +0000
Received: from localhost (localhost.elischer.org [127.0.0.1])
	by InterJet.elischer.org (8.9.1a/8.9.1) with ESMTP id PAA02888
	for <current@freebsd.org>; Sun, 11 Apr 2004 15:51:46 -0700 (PDT)
Date: Sun, 11 Apr 2004 15:51:45 -0700 (PDT)
From: Julian Elischer <julian@elischer.org>
To: FreeBSD current users <current@freebsd.org>
Message-ID: <Pine.BSF.4.21.0404111539430.82054-100000@InterJet.elischer.org>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Subject: JKH project..
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sun, 11 Apr 2004 22:51:49 -0000


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