Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Richard C Bilson]

> From 9fans-bounces+rcbilson=plg.uwaterloo.ca@cse.psu.edu Fri Jun  4 11:19:57 2004
> 
> I would associate each stack segment to an 'address space' structure
> shared by each shared-memory process.
> When the reference counter of this structure goes to zero, I would
> free all the segment 'associated' to this structure (and free the structure 
> :) ).

Yes, but what thread does the free?  You can't free your own stack, and
how does any other thread know to do it for you?  This is a pain, and a
pain that I have felt myself.

Of course, it's easy if there is some kind of termination
synchronization, and the thread that waits is responsible for cleaning
up after the thread that finishes.  But I assume that Russ is trying to
solve the problem in the general case.

As far as I know, the new pthreads library on Linux uses a technique
very similar to the one that Russ describes, with the additional
optimization of re-using stacks if possible.  In fact, I'm not sure if
they ever free stacks -- just keep them around in case a new thread
needs one.

The old linuxthreads library used a "manager thread" to do the reaping
(among other things), which isn't particularly nice or efficient.

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Russ Cox]

> As far as I know, the new pthreads library on Linux uses a technique
> very similar to the one that Russ describes, with the additional
> optimization of re-using stacks if possible.  In fact, I'm not sure if
> they ever free stacks -- just keep them around in case a new thread
> needs one.

That's exactly what I'm doing.  What a crock.

Russ

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[boyd, rounin]

> >... just keep them around in case a new thread needs one.

smacks of 'all the world is a VAX' -- [kernel] malloc is fast now.

> That's exactly what I'm doing.  What a crock.

possibly.

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Philippe Anel]

>Yes, but what thread does the free?  You can't free your own stack, and
>how does any other thread know to do it for you?  This is a pain, and a
>pain that I have felt myself.
>
>Of course, it's easy if there is some kind of termination
>synchronization, and the thread that waits is responsible for cleaning
>up after the thread that finishes.  But I assume that Russ is trying to
>solve the problem in the general case.
>
>As far as I know, the new pthreads library on Linux uses a technique
>very similar to the one that Russ describes, with the additional
>optimization of re-using stacks if possible.  In fact, I'm not sure if
>they ever free stacks -- just keep them around in case a new thread
>needs one.
>
>The old linuxthreads library used a "manager thread" to do the reaping
>(among other things), which isn't particularly nice or efficient.

Ok. What do you think then about the following pseudo-code:

------------------------------------------------------------------------------
struct segment {
         struct segment * next;
         struct segment * prev;
         void * addr;
         int len;
         int threadid;
};

struct addr_space {
         Lock;
         int refcount;
         struct segment * inuse;
         struct segment * tofree;
} addrspace;

void
exit_thread()
  {
         struct segment * s;

         lock(&addrspace);
         for (s = addrspace.tofree; s; s = s->next)
                 free(s->addr);
         if (--refcount) {
                 s = find_segment_from_id(get_my_thread_id());
                 list_remove(s);
                 list_add(tofree, s);
                 unlock(&addrspace);
         }
}

------------------------------------------------------------------------------

It would free the stack of the previous exited thread.

         Philippe,

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Philippe Anel]

>void
>exit_thread()
>  {
>         struct segment * s;
>
>         lock(&addrspace);
>         for (s = addrspace.tofree; s; s = s->next)
>                 free(s->addr);
>         if (--refcount) {
>                 s = find_segment_from_id(get_my_thread_id());
>                 list_remove(s);
>                 list_add(tofree, s);

move the unlock call out of the block of course.

>                 unlock(&addrspace);
>         }
>}

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Russ Cox]

> void
> exit_thread()
>   {
>          struct segment * s;
> 
>          lock(&addrspace);
>          for (s = addrspace.tofree; s; s = s->next)
>                  free(s->addr);
>          if (--refcount) {
>                  s = find_segment_from_id(get_my_thread_id());
>                  list_remove(s);
>                  list_add(tofree, s);
>                  unlock(&addrspace);
>          }
> }

this isn't safe because you keep using the stack
after you unlock &addrspace, so someone else
might come along and free it out from under you
before you manage to exit.  the inferno version
posted by charles fixes this.

unfortunately, i'm trying not to assume that all the threads
will exit with my exit function, so this approach isn't
really an option.

russ

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Charles Forsyth]

[-- Attachment #1: Type: text/plain, Size: 699 bytes --]

>>the inferno version posted by charles fixes this.

actually i sent that privately, but it's fairly obvious (once you know
the dangers).  the mess in that one is that it needs assembly language in order
to have precise control over access to the stack and to allow
an INT $SYS_exit or whatever to be made without using the (user) stack,
so that you need to do the raw INT yourself, not call _exit,
after unlocking the global stack allocation Lock.  void unlockandexit(Lock*).
ugh.  it also can't simply free() the stack, but can only recycle it,
though you could fix that one by queueing the stack for freeing
by the next stackalloc once it's past the global lock.

now, go hug a TLB!

[-- Attachment #2: Type: message/rfc822, Size: 3308 bytes --]

From: Russ Cox <russcox@gmail.com>
To: Fans of the OS Plan 9 from Bell Labs <9fans@cse.psu.edu>
Subject: Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.
Date: Fri, 4 Jun 2004 12:38:56 -0400
Message-ID: <ee9e417a040604093860e7fcf5@mail.gmail.com>

> void
> exit_thread()
>   {
>          struct segment * s;
> 
>          lock(&addrspace);
>          for (s = addrspace.tofree; s; s = s->next)
>                  free(s->addr);
>          if (--refcount) {
>                  s = find_segment_from_id(get_my_thread_id());
>                  list_remove(s);
>                  list_add(tofree, s);
>                  unlock(&addrspace);
>          }
> }

this isn't safe because you keep using the stack
after you unlock &addrspace, so someone else
might come along and free it out from under you
before you manage to exit.  the inferno version
posted by charles fixes this.

unfortunately, i'm trying not to assume that all the threads
will exit with my exit function, so this approach isn't
really an option.

russ

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[boyd, rounin]

> Ok. What do you think then about the following pseudo-code:

roll on lunix ...

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[boyd, rounin]

> Yes, but what thread does the free?  You can't free your own stack, and
> how does any other thread know to do it for you?  This is a pain, and a
> pain that I have felt myself.

mark it as BUGGERED and get the memory mangement system to clean it up.

i'd reference count it too, if they are shared in some way.

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Richard C Bilson]

> From: Philippe Anel <xigh@free.fr> Fri Jun  4 12:23:49 2004
> 
> void
> exit_thread()
>   {
>          struct segment * s;
> 
>          lock(&addrspace);
>          for (s = addrspace.tofree; s; s = s->next)
>                  free(s->addr);
>          if (--refcount) {
>                  s = find_segment_from_id(get_my_thread_id());
>                  list_remove(s);
>                  list_add(tofree, s);
>          }
>          unlock(&addrspace);
> }
> 
> ------------------------------------------------------------------------------
> 
> It would free the stack of the previous exited thread.

This isn't actually so different from what Russ describes -- you're just
keeping a separate free list, rather than setting a per-thread flag in
some global list of all threads.

Note that you have to be very careful about race conditions -- your
stack could disappear immediately after the call to unlock, which means
that you'd better be done all you need to do at that point, except for
calling _exit (and even that is problematic).

[9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Russ Cox]

Anyone have any idea how one is supposed to arrange
to free the stack on which a shared-memory proc is 
running?

In my current implementation, I have a routine called
stackalloc() that keeps a list of all stacks ever allocated
along with the pids they were allocated for, and every Nth
time it gets called, it scans the list freeing the stacks that
correspond to processes that no longer exist.

Damn TLB-friendly operating systems.

Russ

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Philippe Anel]

At 04:39 PM 6/4/2004, you wrote:
>Anyone have any idea how one is supposed to arrange
>to free the stack on which a shared-memory proc is
>running?
>
>In my current implementation, I have a routine called
>stackalloc() that keeps a list of all stacks ever allocated
>along with the pids they were allocated for, and every Nth
>time it gets called, it scans the list freeing the stacks that
>correspond to processes that no longer exist.
>
>Damn TLB-friendly operating systems.
>
>Russ

Hello,

I would associate each stack segment to an 'address space' structure
shared by each shared-memory process.
When the reference counter of this structure goes to zero, I would
free all the segment 'associated' to this structure (and free the structure 
:) ).

I thought plan9 doesn't share process stack segment, am i wrong ?
If it doesn't share these segments you only have to free the stack when the
process is ending.

         Philippe,

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Philippe Anel]

>
>I thought plan9 doesn't share process stack segment, am i wrong ?

I've just re-read the subject ... oopppss. sorry.

         Philippe,

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[boyd, rounin]

> Anyone have any idea how one is supposed to arrange
> to free the stack on which a shared-memory proc is 
> running?

is this a shared memory multiprocessor?

or is it it full blown process migration?

Re: [9fans] stack reclamation on Unix using clone, rfork_thread, etc.

[Russ Cox]

> is this a shared memory multiprocessor?
> 
> or is it it full blown process migration?

a solution for a uniprocessor would suffice.