From owner-freebsd-bugs@freebsd.org Wed Sep 27 10:07:12 2017 Return-Path: Delivered-To: freebsd-bugs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 6056EE3027D for ; Wed, 27 Sep 2017 10:07:12 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2001:1900:2254:206a::16:76]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 33FC36C2C1 for ; Wed, 27 Sep 2017 10:07:12 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from bugs.freebsd.org ([127.0.1.118]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id v8RA7CxV024088 for ; Wed, 27 Sep 2017 10:07:12 GMT (envelope-from bugzilla-noreply@freebsd.org) From: bugzilla-noreply@freebsd.org To: freebsd-bugs@FreeBSD.org Subject: [Bug 222639] fork: Time it takes to allocate random PID approach infinity as num_processes approach PID_MAX (related to: sysctl kern.randompid) Date: Wed, 27 Sep 2017 10:07:12 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: kern X-Bugzilla-Version: CURRENT X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Only Me X-Bugzilla-Who: marieheleneka@gmail.com X-Bugzilla-Status: New X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: freebsd-bugs@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 27 Sep 2017 10:07:12 -0000 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D222639 Bug ID: 222639 Summary: fork: Time it takes to allocate random PID approach infinity as num_processes approach PID_MAX (related to: sysctl kern.randompid) Product: Base System Version: CURRENT Hardware: Any OS: Any Status: New Severity: Affects Only Me Priority: --- Component: kern Assignee: freebsd-bugs@FreeBSD.org Reporter: marieheleneka@gmail.com The current implementation of random PID generation is a bit opportunistic. It currently generates a random value which is lastpid + (random_number cap= ped to a max value of kern.randompid), but always at least 1 more than lastpid. It then checks if this PID is available, and if not, tries again. Therefore, as number of processes approach PID_MAX (i.e. number of available PIDs approach 0), the time to allocate a randomly generated PID approaches infinity. Proposed solution: Prequisite: Change how PIDs are tracked and allocated. Implement a bitmap of PIDs (I'm currently working on this) which is updated whenever anything in = the PID namespace changes (a new PID/session ID/etc is created, or a PID/session ID/etc is considered available again).=20 The bitmap should be an array of 4096 uint32_t where each bit represents a = PID. A set (on) bit indicates an available PID. New random PID generation algorithm: Create an index of the bitmap consisting of 128 uint32_t. Each bit represen= ts a single uint32_t in the bitmap, declaring whether it has any available PIDs. When creating a random PID: - Iterate the index and find all uint32_t which have at least one bit set. - Select one of thee aforementioned at random. - Select a random set bit from the selected, to decide which uint32_t in the bitmap to use for further selection. - Select a random bit in the aforementioned to determine which PID to alloc= ate. Restrict allocation to lastpid < newpid < PID_MAX I'm working on this, but describing it here so it's not lost. For feedback = or just in case the "Bus Test" actually happens. ;) --=20 You are receiving this mail because: You are the assignee for the bug.=