Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1472 > unrolled thread

Question about inter-thread stack references

Back to article view | Back to comp.compilers

Contents

  Question about inter-thread stack references Ivan Godard <ivan@ootbcomp.com> - 2015-01-15 23:54 -0800
    Re: Question about inter-thread stack references Louis Krupp <lkrupp@nospam.pssw.com.invalid> - 2015-01-16 22:28 -0700
      Re: Question about inter-thread stack references glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-01-17 18:46 +0000
    Re: Question about inter-thread stack references George Neuner <gneuner2@comcast.net> - 2015-01-18 01:58 -0500
      Re: Question about inter-thread stack references glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-01-18 21:47 +0000
        Re: Question about inter-thread stack references glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-01-18 23:24 +0000
    Re: Question about inter-thread stack references Stefan Monnier <monnier@iro.umontreal.ca> - 2015-01-18 08:35 -0500
    Re: Question about inter-thread stack references Kaz Kylheku <kaz@kylheku.com> - 2015-01-18 17:12 +0000
    Re: Question about inter-thread stack references Ivan Godard <ivan@ootbcomp.com> - 2015-01-18 12:49 -0800
    Re: Question about inter-thread stack references jgk@panix.com (Joe keane) - 2015-01-25 09:27 +0000
      Re: Question about inter-thread stack references Kaz Kylheku <kaz@kylheku.com> - 2015-01-25 18:46 +0000
        Re: Question about inter-thread stack references jgk@panix.com (Joe keane) - 2015-01-27 02:53 +0000

#1472 — Question about inter-thread stack references

If a process has two or more threads running in it, what are the rules
regarding one thread referencing memory in a different thread's stack?

In the usual way that paging hardware works both stacks can be made
visible to both threads, but interstack visibility could also be
prevented (assuming that stacks occupied whole pages). However, if a
stack object can be referenced by a concurrent thread running in another
core then it becomes impossible to optimize and move stack objects into
registers because they might be referenced at any time. Even if the
program were required to declare such data volatile there would still be
locking needed.

I vaguely (so vague that I can't find citations) remember that on some,
possibly legacy, hardware it was physically impossible to do
inter-thread stack accesses; stacks were strictly per-thread and
private. I also vaguely recall that some languages (or thread packages)
banned the practice even if it were physically possible.

Is anyone aware of language/thread package/hardware rules about required
semantics for such usage? Is it explicitly permitted, explicitly banned,
stated to be implementation defined, stated to be undefined, or simply
not mentioned?

Thanks for your help.

Ivan

[toc] | [next] | [standalone]

#1481

On Thu, 15 Jan 2015 23:54:57 -0800, Ivan Godard <ivan@ootbcomp.com>
wrote:

>If a process has two or more threads running in it, what are the rules
>regarding one thread referencing memory in a different thread's stack?
> ...

>Is anyone aware of language/thread package/hardware rules about required
>semantics for such usage? Is it explicitly permitted, explicitly banned,
>stated to be implementation defined, stated to be undefined, or simply
>not mentioned?

This sounds a bit like what was once known as Burroughs Large Systems
(then Unisys A-Series and now Clearpath or something) architecture. It
had processes, not threads, but processes can be related and can share
data.  Every process has a stack, one stack can have a reference into
another stack, and unfortunately, that's about all I can remember at
the moment.

There are architecture reference manuals out there.  The data
reference I'm thinking of is called a Stuffed Indirect Reference Word,
which might give you some idea of what you're getting into.

Louis

[toc] | [prev] | [next] | [standalone]

#1483

Louis Krupp <lkrupp@nospam.pssw.com.invalid> wrote:
> On Thu, 15 Jan 2015 23:54:57 -0800, Ivan Godard <ivan@ootbcomp.com>
(snip)
>>Is anyone aware of language/thread package/hardware rules about required
>>semantics for such usage? Is it explicitly permitted, explicitly banned,
>>stated to be implementation defined, stated to be undefined, or simply
>>not mentioned?

> This sounds a bit like what was once known as Burroughs Large Systems
> (then Unisys A-Series and now Clearpath or something) architecture. It
> had processes, not threads, but processes can be related and can share
> data.  Every process has a stack, one stack can have a reference into
> another stack, and unfortunately, that's about all I can remember at
> the moment.

Is this the one that depends on the compiler for its security?
That is, there is no memory protection, but the compiler will only
compile programs that can't access things that they are not supposed to.
Only programs supplied by the system, or compiled by compilers supplied
by the system, are allowed to run. (No downloading apps!)

-- glen
[Downloading? This was the 1960s.  The security issue was about making
sure that backups kept the security info intact, and you couldn't
install a bad program by loading it from a fake backup tape. -John]

[toc] | [prev] | [next] | [standalone]

#1484

Hi Ivan,

On Thu, 15 Jan 2015 23:54:57 -0800, Ivan Godard <ivan@ootbcomp.com>
wrote:

>If a process has two or more threads running in it, what are the rules
>regarding one thread referencing memory in a different thread's stack?

No rules per se, but it isn't even feasible unless the lifetimes of
the references obey strict stack discipline wrt to the lifetime of the
target.  You can find that sort of structure with coroutines and with
map-reduce style parent-child thread relationships - but not in
general.

However, I don't see any compelling reason to permit it.  The stack is
nothing more than a compiler managed mark-release heap: it's only real
benefit to the programmer is no-brainer deallocation.  Anything that
might usefully be done using stack sharing can be done almost as
easily - and much more safely - using an explicit mark-release heap or
stacked heaps (regions, per Tofte and others).

>Ivan
George

[toc] | [prev] | [next] | [standalone]

#1490

George Neuner <gneuner2@comcast.net> wrote:

> On Thu, 15 Jan 2015 23:54:57 -0800, Ivan Godard <ivan@ootbcomp.com>
> wrote:

>>If a process has two or more threads running in it, what are the rules
>>regarding one thread referencing memory in a different thread's stack?

> No rules per se, but it isn't even feasible unless the lifetimes of
> the references obey strict stack discipline
(snip)

> However, I don't see any compelling reason to permit it.  The stack is
> nothing more than a compiler managed mark-release heap:

Yes. OS/360 and successors use a doubly-linked list for linkage and
register saving, and for reentrant routines usually local variables,
too.

> it's only real benefit to the programmer is no-brainer deallocation.

Non-reentrant OS/360 programs traditionally use static storage for
the save areas, which is also pretty much no-brainer. Reentrant ones
have to dynamically allocate them.

I believe that OS/360 MVT subtasks run in the same protection key
as the parent. With MVS, ordinary user tasks all run with the same
protection key, with segment and page tables updated as needed.

> Anything that might usefully be done using stack sharing can be
> done almost as easily - and much more safely - using an explicit
> mark-release heap or stacked heaps (regions, per Tofte and others).

PL/I allows for multitasking, and, as well as it can, communication
between tasks. EVENT varibles are used to synchronize, as are ECBs
(Event Control Blocks) for the OS system calls.

-- glen
[Yes, OS subtasks started with ATTACH all run in the same address
space. -John]

[toc] | [prev] | [next] | [standalone]

#1491

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

(snip, I wrote)
> Yes. OS/360 and successors use a doubly-linked list for linkage and
> register saving, and for reentrant routines usually local variables,
> too.

(snip)

> I believe that OS/360 MVT subtasks run in the same protection key
> as the parent. With MVS, ordinary user tasks all run with the same
> protection key, with segment and page tables updated as needed.

(snip)

> [Yes, OS subtasks started with ATTACH all run in the same address
> space. -John]

Well, all of OS/360, OS/VS1 and OS/VS2 runs in one address space.
For OS/360 all real addresses, for OS/VS1 and OS/VS2 a single 16MB
virtual address space.  (MVS is where they started using separate
address spaces.)

Much of the OS is key zero, and readable by everyone.

But I think you are agreeing that subtasks run with the same key
as the parent.

-- glen
[Yes.  Now back to compilers. -John]

[toc] | [prev] | [next] | [standalone]

#1485

> If a process has two or more threads running in it, what are the rules
> regarding one thread referencing memory in a different thread's stack?

IIUC you're question is not "which weird architecture doesn't allow
them?" (since I guess you know the answer to this one, and you're
mostly interested in the Mill), but rather "which languages support
such references?".

AFAIK the rules are that inter-thread stack references are either
strictly disallowed or at best "undefined".

But even if they can be allowed, I'm pretty sure the Mill can handle
it by handling those rare cases specially (i.e. adding an indirection:
allocating them i the heap and only keeping a reference to them in the
stack).

        Stefan

[toc] | [prev] | [next] | [standalone]

#1487

On 2015-01-16, Ivan Godard <ivan@ootbcomp.com> wrote:
> If a process has two or more threads running in it, what are the rules
> regarding one thread referencing memory in a different thread's stack?

In what system?

In all the systems I'm familiar with, threads run in one address
space, and accessing all valid objects is fair game regardless of
their storage class or thread affiliation.

If we are talking in C terms, then if in some thread, the following
block is executing:

  { some_type_t x; ... }

then while that block continues to execute, the object x is valid.

Anything in the address space which has a pointer to the object can
use that object.

When the block terminates, then the pointer becomes indeterminate.

Secondly, if this x is accessed by multiple threads, then the usual concurrency
considerations apply. Unless x is some atomically accessed type, you need some
kind of mutex, and so forth.

Consider that this sort of stack access is absolutely essential in
various kinds of core multithreading API's. For instance, send a message
to another thread and wait for a reply:

   message_type_t request, reply;

   request_fill(&request, ...);

   if (send_message(other_thread, &request, &reply) == SEND_OKAY) {
     /* process reply */
   }

How this fictitious API works is that the request and reply objects
(local to the thread, on its stack) are registered into some global
message-queuing data structure. The thread which calls send_message is
then blocked. Because it is blocked, those objects remain valid: the
suspension prevents it from terminating the statement block.  While
the sender is blocked, the other thread can access the request, and
fill in the reply. Then when the sender is unblocked, everything is
cool: it finds the repy.  The suspend and resume discipline also
ensures proper synchronization. The send_message thread does not
access the reply prior to the reply being produced, and the receiver
of course won't access the request before that is enqueued and the
sender thread is being put to sleep.

> In the usual way that paging hardware works both stacks can be made
> visible to both threads, but interstack visibility could also be
> prevented (assuming that stacks occupied whole pages).

How paging hardware works is that preventing inter-stack visibility
using paging would be so expensive, that it would be making a mockery
of the concept of threading.  The processor would have to swap page
tables and flush translation caches when switching thread contexts.

Some special support for protecting stacks could make it possible.
For instance stacks could be segments, and segments could have some
security word in their descriptor which is cheaply checked against the
current security descriptor of the current thread.

> I vaguely (so vague that I can't find citations) remember that on some,
> possibly legacy, hardware it was physically impossible to do
> inter-thread stack accesses; stacks were strictly per-thread and
> private. I also vaguely recall that some languages (or thread packages)
> banned the practice even if it were physically possible.

Could be, but that's a pretty dumb approach which is why those systems
ended up as legacy. Well, it's not a dumb approach, but it's just not
threading, really.

One way to emulate that scenario is simply to use multiple processes
(e.g. with fork() on Unix), and use explicit memory sharing (mmap,
SysV) to have a global area which is common, and mapped to exactly the
same address in every process, too. Then you have private stacks.

[toc] | [prev] | [next] | [standalone]

#1489

Interestingly, the answers I have gotten here (thank you all) have been
all over the lot, from required to forbidden and all points between.

Some explanation:

As Stefan guessed, my question does in fact arise from architectural
issues on the Mill. The Mill design goes to considerably greater
lengths in support of program reliability than most, and in particular
the Mill attempts to do as much sanity-checking of the executing
program that it can, consistent with hardware and execution cost. It
is tighter on issues that impact security, but also tends to nanny on
issues that are not obvious vulnerabilities but are nevertheless
semantically invalid.  The concern is in part philosophical and in
part because we feel reliability is something that can be marketed
when we have product.  Crassly commercial I know, but there it is :-)

One way the reliability concern surfaces is in checking for invalid
references to memory. Mill memory checking is to the byte, not to the
page; it is possible to grant access to a one byte object to some
process without allowing access to adjacent bytes. This might be used
to give a device driver access to a single register in MMIO space
without also giving it the ability to trample over the rest, as is so
often the root cause of OS crashes.

To support limited access, the hardware contains special facilities to
track the current size of the running stack as that changes with call
and return operations. As a result, and unique to the Mill as far as I
know, a function that returns a pointer to an activation-local object
will cause a segv when the caller dereferences that pointer. The stack
rubble of prior activations is not in the address space of the
executing thread. The check is in hardware, transparent, and cheap,
and so is consistent with the Mill design philosophy, as described.

However, the hardware check can only track one stack. If there are two
threads, each running in their own core, then each will be checked
w/r/t their own accesses, but we would like to check the accesses from
each to the others' stack too. Unfortunately, despite a lot of head
scratching, we have found no way to do inter-thread checks that is not
intrusive and/or expensive.

However, it would be trivial to simply ban inter-thread references
outright using the existing checking logic. Were we to do so, we could
define the ABI so as to require the compiler to detect references to
stack-allocated objects that leak from the stack and either issue a
diagnostic or automatically place them on the heap, as is often done
now for all alloca() calls on some systems. Unfortunately, C and
pointer analysis do not make good bed-fellows, and we doubt that
compilation-based techniques will be universally effective. As a
result, we fear that an inter-thread reference ban will break existing
programs, and forcing rewrite is very much not something we want to
do.

So I asked here what the experience was with inter-thread stack
references, in hopes that the issues (which clearly impact how garbage
collection can be implemented for example, where stacks must be
searched for roots) might have been previously addressed by others in
the field and possibly might even have been baked into languages or
prior architectures. Apparently not, at least as far as the expertise
here reports.

Can any of you suggest some other board or venue where I could repeat my
question usefully?

Thank you again for your help.

[I'd look at the programming models people use for threads, notably
POSIX pthreads and MIT/Intel Cilk.  You'll generally find that threads
are managed in a tree, with a routine which may itself be a thread
starting up subthreads and then waiting for them and cleaning up.  So
it is common for a thread to access data in the threads above it in
the tree, passed as arguments, but considerably less common to have
cross-tree or downward accesses. You might ask in places where people
who do high performance numeric computing hang out, since that's all
heavily parallel and usually threaded these days.  -John]

[toc] | [prev] | [next] | [standalone]

#1499

In article <15-01-015@comp.compilers>, Ivan Godard  <ivan@ootbcomp.com> wrote:
>If a process has two or more threads running in it, what are the rules
>regarding one thread referencing memory in a different thread's stack?

It should be illegal, if you ask me.

[Even if they have some way to lock and synchronize?  Imagine that one
thread is acting as a server for others that put requests into a queue,
and the queue entries point to structures in the requesting thread's
stack. -John]

[toc] | [prev] | [next] | [standalone]

#1500

On 2015-01-25, Joe keane <jgk@panix.com> wrote:
>
> In article <15-01-015@comp.compilers>, Ivan Godard  <ivan@ootbcomp.com> wrote:
>>If a process has two or more threads running in it, what are the rules
>>regarding one thread referencing memory in a different thread's stack?
>
> It should be illegal, if you ask me.
>
> [Even if they have some way to lock and synchronize?  Imagine that one
> thread is acting as a server for others that put requests into a queue,
> and the queue entries point to structures in the requesting thread's
> stack. -John]

Concretely:

  message_t request, reply;

  init_request(&request, ... args);

  if (send_request(other_thread, &request, &reply) == SEND_OK) {
    /* reply object contains reply */
  }

This scenario benefits from inter-thread stack access. While our thread is
blocked in send_request, pointers to the request and reply objects can be
directly enqueued somewhere, and the other thread can read from the request and
update the reply directly.

The inter-thread stack access could be avoided, but only if the API provides
alternative buffers and performs copying back and forth.

Anyway, it's done in the direct, efficient way in real life, whether anyone
likes it or not. Unix-like kernels do it, POSIX threads programs do it, Windows
threads programs do it, ...
[yes, and educated fleas do it.

This is a long way from compilers, unless someone's has a suggestion about how
one might handle these things directly in source code. -John]

[toc] | [prev] | [next] | [standalone]

#1501

Kaz Kylheku  <kaz@kylheku.com> wrote:
>  message_t request, reply;
>
>  init_request(&request, ... args);
>
>  if (send_request(other_thread, &request, &reply) == SEND_OK) {
>    /* reply object contains reply */
>  }

It is more like:

    struct my_request request;
    struct my_reply reply;

    /* request is dead, reply is dead */

    put_stuff_into_request(&request, args);

    /* request is live, reply is dead */

    do_some_bullshit_with_request(&request, args);

    /* request is live, reply is dead */

    err = enqueue_request_and_reply(queue, args, &request, &reply);

    /* request is live, reply is live */

    do_some_bullshit();

    /* request is live, reply is live */

    err = dequeue_request_and_reply(queue, args, &request, &reply);

    /* request is dead, reply is live */

    do_some_bullshit_with_reply(&reply, args);

    /* request is dead, reply is live */

    get_stuff_out_of_reply(&reply, args);

    /* request is dead, reply is dead */

It is OK if both threads are in one function, but it is easy to make a
benign change that breaks things, or worse, usually works.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web