lwpid allocation

[David Laight <david%l8s.co.uk@localhost>]

I happened upon the code on kern_lwp.c that allocates lwp ids.
Basically they are allocated in increasing order (starting from 1).
Should a process allocate a lot of lwp, the id just wraps,
code was added to avoid 0 - but not to avoid duplicate ids.

I also found some code (in ld.elf_so) that will break if the top
bit is set - not sure whether it is allowed to be valid, but 2^31
lwp is rather more than plenty.

The patch below (compile tested only) should allocate unique ids.
The other option would be to use something like the pid allocator
for lwp ids - but that is somewhat OTT since almost no processs
will cycle through anywhere near 2^31 lwps.

        David

Index: kern_lwp.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_lwp.c,v
retrieving revision 1.173
diff -u -p -r1.173 kern_lwp.c
--- kern_lwp.c  27 Sep 2012 20:43:15 -0000      1.173
+++ kern_lwp.c  16 Dec 2012 16:54:06 -0000
@@ -704,6 +704,54 @@ lwp_wait(struct lwp *l, lwpid_t lid, lwp
        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.
+        */
+
+       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;
+               } else {
+                       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 (again) */
+                               try_lid = 2;
+                       }
+               }
+               nxt_lid = scan->l_lid - 1;
+       }
+       p->p_nlwpid = try_lid | LID_SCAN;
+
+       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,
@@ -859,13 +907,23 @@ lwp_create(lwp_t *l1, proc_t *p2, vaddr_
        sigemptyset(&l2->l_sigpend.sp_set);
 
        if (lid == 0) {
-               p2->p_nlwpid++;
-               if (p2->p_nlwpid == 0)
-                       p2->p_nlwpid++;
-               lid = p2->p_nlwpid;
+               /*
+                * 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 (lid & LID_SCAN) {
+                       lid = lwp_find_free_lid(lid & ~LID_SCAN, l2, p2);
+                       /* l2 as been insterted in order */
+                       goto skip_insert;
+               }
+               p2->p_nlwpid = lid;
        }
-       l2->l_lid = lid;
        LIST_INSERT_HEAD(&p2->p_lwps, l2, l_sibling);
+    skip_insert:
+       l2->l_lid = lid;
        p2->p_nlwps++;
        p2->p_nrlwps++;
 
-- 
David Laight: david%l8s.co.uk@localhost