[src/trunk]: src/sys/kern The lwp_id in a process are supposed to be non-zero...

[dsl <dsl%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/d28e6bf22472
branches:  trunk
changeset: 783365:d28e6bf22472
user:      dsl <dsl%NetBSD.org@localhost>
date:      Sun Dec 16 22:21:03 2012 +0000

description:
The lwp_id in a process are supposed to be non-zero and unique.
This stops being true once a process has allocated (and freed) 2^32 lwps.
(I've not timed it!)
There is also some code lurking (eg ld.elf_so) that doesn't expect the
  high be be set.
Once the lwp_id wraps, scan the list to find the first free id higher
  than the last one allocated.
Maintain the sort order to make the possible.
Note that if some lwp (but not all) are allocated numbers from the pid
  space it will go horribly wrong.
Tested by setting the limit to 128 and getting firefox to create threads.

diffstat:

 sys/kern/kern_lwp.c |  83 +++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 75 insertions(+), 8 deletions(-)

diffs (113 lines):

diff -r 24acbe3bbf60 -r d28e6bf22472 sys/kern/kern_lwp.c
--- a/sys/kern/kern_lwp.c       Sun Dec 16 20:44:16 2012 +0000
+++ b/sys/kern/kern_lwp.c       Sun Dec 16 22:21:03 2012 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: kern_lwp.c,v 1.173 2012/09/27 20:43:15 rmind Exp $     */
+/*     $NetBSD: kern_lwp.c,v 1.174 2012/12/16 22:21:03 dsl Exp $       */
 
 /*-
  * Copyright (c) 2001, 2006, 2007, 2008, 2009 The NetBSD Foundation, Inc.
@@ -211,7 +211,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_lwp.c,v 1.173 2012/09/27 20:43:15 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_lwp.c,v 1.174 2012/12/16 22:21:03 dsl Exp $");
 
 #include "opt_ddb.h"
 #include "opt_lockdebug.h"
@@ -704,6 +704,62 @@
        return error;
 }
 
+static lwpid_t
+lwp_find_free_lid(lwpid_t try_lid, lwp_t * new_lwp, proc_t *p)
+{
+       #define LID_SCAN (1u << 31)
+       lwp_t *scan, *free_before;
+       lwpid_t nxt_lid;
+
+       /*
+        * We want the first unused lid greater than or equal to
+        * try_lid (modulo 2^31).
+        * (If nothing else ld.elf_so doesn't want lwpid with the top bit set.)
+        * We must not return 0, and avoiding 'LID_SCAN - 1' makes
+        * the outer test easier.
+        * This would be much easier if the list were sorted in
+        * increasing order.
+        * The list is kept sorted in decreasing order.
+        * This code is only used after a process has generated 2^31 lwp.
+        *
+        * Code assumes it can always find an id.
+        */
+
+       try_lid &= LID_SCAN - 1;
+       if (try_lid <= 1)
+               try_lid = 2;
+
+       free_before = NULL;
+       nxt_lid = LID_SCAN - 1;
+       LIST_FOREACH(scan, &p->p_lwps, l_sibling) {
+               if (scan->l_lid != nxt_lid) {
+                       /* There are available lid before this entry */
+                       free_before = scan;
+                       if (try_lid > scan->l_lid)
+                               break;
+               } 
+               if (try_lid == scan->l_lid) {
+                       /* The ideal lid is busy, take a higher one */
+                       if (free_before != NULL) {
+                               try_lid = free_before->l_lid + 1;
+                               break;
+                       }
+                       /* No higher ones, reuse low numbers */
+                       try_lid = 2;
+               }
+
+               nxt_lid = scan->l_lid - 1;
+               if (LIST_NEXT(scan, l_sibling) == NULL) {
+                   /* The value we have is lower than any existing lwp */
+                   LIST_INSERT_AFTER(scan, new_lwp, l_sibling);
+                   return try_lid;
+               }
+       }
+
+       LIST_INSERT_BEFORE(free_before, new_lwp, l_sibling);
+       return try_lid;
+}
+
 /*
  * Create a new LWP within process 'p2', using LWP 'l1' as a template.
  * The new LWP is created in state LSIDL and must be set running,
@@ -858,14 +914,25 @@
        CIRCLEQ_INIT(&l2->l_sigpend.sp_info);
        sigemptyset(&l2->l_sigpend.sp_set);
 
-       if (lid == 0) {
-               p2->p_nlwpid++;
-               if (p2->p_nlwpid == 0)
-                       p2->p_nlwpid++;
-               lid = p2->p_nlwpid;
+       if (__predict_true(lid == 0)) {
+               /*
+                * XXX: l_lid are expected to be unique (for a process)
+                * if LWP_PIDLID is sometimes set this won't be true.
+                * Once 2^31 threads have been allocated we have to
+                * scan to ensure we allocate a unique value.
+                */
+               lid = ++p2->p_nlwpid;
+               if (__predict_false(lid & LID_SCAN)) {
+                       lid = lwp_find_free_lid(lid, l2, p2);
+                       p2->p_nlwpid = lid | LID_SCAN;
+                       /* l2 as been inserted into p_lwps in order */
+                       goto skip_insert;
+               }
+               p2->p_nlwpid = lid;
        }
+       LIST_INSERT_HEAD(&p2->p_lwps, l2, l_sibling);
+    skip_insert:
        l2->l_lid = lid;
-       LIST_INSERT_HEAD(&p2->p_lwps, l2, l_sibling);
        p2->p_nlwps++;
        p2->p_nrlwps++;