[9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Giacomo Tesio]

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

2011-05-20 3:30 GMT+02:00 erik quanstrom <quanstro@quanstro.net>:

> one note is that while i'm aware of privalloc(2), i didn't use it.  the
> implementation doesn't appear correct for shared-memory procs.
> i think there are two issues
> - locking is unnecessary.  the only preemptable unit of execution is
> a process and each process is guarenteed to have its own instance
> of _privates and _nprivates.
> - for shared-memory procs, we will run out of privates because
> the static privinit will be falsely shared.  privinit should be replaced
> by using a private entry.
>

In a set of processes that share memory, I need a single per-process
location to store the address of structure (which is in turn allocated in
the global memory space).

Privalloc(2) seemed what I need, but seem that I can't use it properly.

In the parent process I do:

1) initialialize a global variable p = (MyStruct **)privalloc();
2) allocate a MyStruct for every process I'm going to spawn
3) spawn processes with rfork(RFMEM|RFPROC)

The spawn() function that call rfork takes a MyStruct* as argument and
assign it to *p in the new process.
For extra safety I added an assert(*p == nil) just after rfork, and after a
few (apparently?) successful spawns, the assert fails.

What I need is a sort of thread-local storage for the MyStruct*, so that
each child process can find it's own dedicated MyStruct.
I know that could get this with an hashtable based on the pid, but I'd
prefer to avoid the book keeping if possible.


Giacomo

[-- Attachment #2: Type: text/html, Size: 2039 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Giacomo Tesio]

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

... and given getpid(2) implementation, a pid based table could be quite
expensive, since MyStruct is accessed very very often.

2015-09-05 16:03 GMT+02:00 Giacomo Tesio <giacomo@tesio.it>:

> 2011-05-20 3:30 GMT+02:00 erik quanstrom <quanstro@quanstro.net>:
>
>> one note is that while i'm aware of privalloc(2), i didn't use it.  the
>> implementation doesn't appear correct for shared-memory procs.
>> i think there are two issues
>> - locking is unnecessary.  the only preemptable unit of execution is
>> a process and each process is guarenteed to have its own instance
>> of _privates and _nprivates.
>> - for shared-memory procs, we will run out of privates because
>> the static privinit will be falsely shared.  privinit should be replaced
>> by using a private entry.
>>
>
> In a set of processes that share memory, I need a single per-process
> location to store the address of structure (which is in turn allocated in
> the global memory space).
>
> Privalloc(2) seemed what I need, but seem that I can't use it properly.
>
> In the parent process I do:
>
> 1) initialialize a global variable p = (MyStruct **)privalloc();
> 2) allocate a MyStruct for every process I'm going to spawn
> 3) spawn processes with rfork(RFMEM|RFPROC)
>
> The spawn() function that call rfork takes a MyStruct* as argument and
> assign it to *p in the new process.
> For extra safety I added an assert(*p == nil) just after rfork, and after
> a few (apparently?) successful spawns, the assert fails.
>
> What I need is a sort of thread-local storage for the MyStruct*, so that
> each child process can find it's own dedicated MyStruct.
> I know that could get this with an hashtable based on the pid, but I'd
> prefer to avoid the book keeping if possible.
>
>
> Giacomo
>

[-- Attachment #2: Type: text/html, Size: 2639 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

On Sat Sep  5 07:06:44 PDT 2015, giacomo@tesio.it wrote:

> 2011-05-20 3:30 GMT+02:00 erik quanstrom <quanstro@quanstro.net>:

uh, wow.  i hope this wasn't my mailer dragging the past up.

> > one note is that while i'm aware of privalloc(2), i didn't use it.  the
> > implementation doesn't appear correct for shared-memory procs.
> > i think there are two issues
> > - locking is unnecessary.  the only preemptable unit of execution is
> > a process and each process is guarenteed to have its own instance
> > of _privates and _nprivates.
> > - for shared-memory procs, we will run out of privates because
> > the static privinit will be falsely shared.  privinit should be replaced
> > by using a private entry.
> >
>
> In a set of processes that share memory, I need a single per-process
> location to store the address of structure (which is in turn allocated in
> the global memory space).
>
> Privalloc(2) seemed what I need, but seem that I can't use it properly.
>
> In the parent process I do:
>
> 1) initialialize a global variable p = (MyStruct **)privalloc();
> 2) allocate a MyStruct for every process I'm going to spawn
> 3) spawn processes with rfork(RFMEM|RFPROC)
>
> The spawn() function that call rfork takes a MyStruct* as argument and
> assign it to *p in the new process.
> For extra safety I added an assert(*p == nil) just after rfork, and after a
> few (apparently?) successful spawns, the assert fails.

hmm.  in /sys/src/libc/amd64/arv0.s _privates and _nprivates are in the bss.

GLOBL	_privates(SB), $8
GLOBL	_nprivates(SB), $4

so they can be set in the parent process.  in /sys/src/libc/amd64/main9.s

#define NPRIVATES	16

TEXT	_main(SB), 1, $(2*8+NPRIVATES*8)
	MOVQ	AX, _tos(SB)
	LEAQ	16(SP), AX
	MOVQ	AX, _privates(SB)
	MOVL	$NPRIVATES, _nprivates(SB)


we see that the privates and nprivates are on the stack just below _tos.

the only ways i can see your pointer not being nil is
(a) kernel bug -- the stack is not cleared
(b) the the parent has written to the privalloc'd element before forking,
and the stack was copied faithfully.

i think you can tell which case you have by assert(*p == nil) in the parent.

i'm sure there could be other bugs as well.

as to getpid() being "slow", you can always use _tos->pid

- erik

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

by the way, the following program runs without asserting for me
with or without the waits.

- erik

---

#include <u.h>
#include <libc.h>

void
task(void **p)
{
	assert(*p == nil);
	*p = (void*)(uintptr)getpid();
}

void
spawn(void (*t)(void**), void **p)
{
	int pid;

	switch(pid = rfork(RFMEM|RFPROC)){
	case -1:
		sysfatal("spawn: rfork: %r");
	case 0:
		t(p);
		exits("");
	default:
		USED(pid);
		return;
	}
}

void
main(void)
{
	int i, k;
	void **p;
	Waitmsg *w;

	p = privalloc();
	k = 0;
	for(i = 0; i < 1024; i++){
		spawn(task, p);
		for(k++; k > 16; k--){
			if((w = wait()) == nil)
				break;
			free(w);
		}
	}
	exits("");
}

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Giacomo Tesio]

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

Nice example thanks.

May be my problem is that p is global in my case?

Giacomo
Il 05/Set/2015 18:50, "erik quanstrom" <quanstro@quanstro.net> ha scritto:

> by the way, the following program runs without asserting for me
> with or without the waits.
>
> - erik
>
> ---
>
> #include <u.h>
> #include <libc.h>
>
> void
> task(void **p)
> {
>         assert(*p == nil);
>         *p = (void*)(uintptr)getpid();
> }
>
> void
> spawn(void (*t)(void**), void **p)
> {
>         int pid;
>
>         switch(pid = rfork(RFMEM|RFPROC)){
>         case -1:
>                 sysfatal("spawn: rfork: %r");
>         case 0:
>                 t(p);
>                 exits("");
>         default:
>                 USED(pid);
>                 return;
>         }
> }
>
> void
> main(void)
> {
>         int i, k;
>         void **p;
>         Waitmsg *w;
>
>         p = privalloc();
>         k = 0;
>         for(i = 0; i < 1024; i++){
>                 spawn(task, p);
>                 for(k++; k > 16; k--){
>                         if((w = wait()) == nil)
>                                 break;
>                         free(w);
>                 }
>         }
>         exits("");
> }
>
>

[-- Attachment #2: Type: text/html, Size: 1860 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

> May be my problem is that p is global in my case?

global variables are in the bss, and thus shared. p will have
the same value in each thread, but *p should point into the
stack, and thus the same virtual address will be mapped to
different physical pages of memory.

however, if *p is assigned to a non-zero value before the process
is created, the new page allocated for the new process' stack will
have a copy of the old value, and thus not be 0.

- erik

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[cinap_lenrek]

it doesnt matter. p is a pointer to a pointer. the whole
idea of privalloc() is to give you a memory locaiton that
when *dereferenced* can yield different *values* under different
processes, tho the *address* is the same, so it can be passed
arround.

--
cinap

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

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

On 5 September 2015 at 15:03, Giacomo Tesio <giacomo@tesio.it> wrote:

> For extra safety I added an assert(*p == nil) just after rfork, and after
> a few (apparently?) successful spawns, the assert fails.


The stack is a logical copy of the parent process's stack at rfork, even
with RFMEM, since the stack's not shared,
so if you've previously assigned it in the parent, its child will see the
non-nil value after the fork. It doesn't get a completely fresh stack.

[-- Attachment #2: Type: text/html, Size: 799 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Giacomo Tesio]

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

2015-09-05 20:47 GMT+02:00 erik quanstrom <quanstro@quanstro.net>:

> > May be my problem is that p is global in my case?
>
> global variables are in the bss, and thus shared. p will have
> the same value in each thread, but *p should point into the
> stack, and thus the same virtual address will be mapped to
> different physical pages of memory.
>
> however, if *p is assigned to a non-zero value before the process
> is created, the new page allocated for the new process' stack will
> have a copy of the old value, and thus not be 0.
>
> - erik
>
>
That's exactly what happened.
I misread privalloc(2), and assumed that privalloc()ed addresses were
somehow reset on rfork.
This is probably something to explicitly state the man page.

Thanks you all!


Giacomo

[-- Attachment #2: Type: text/html, Size: 1354 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[cinap_lenrek]

hey charles!

is privfree() broken? it appears it chains the slots together,
but only the calling process will get a correct chain. the chain
head (privs) is shared (in bss) and seen by all process so the
others will get corrupted chains (chain link is private) no?

i wonder what the intended use for privfree() was. theres no
code using it.

--
cinap

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

On Sat Sep  5 23:33:50 PDT 2015, cinap_lenrek@felloff.net wrote:
> hey charles!
>
> is privfree() broken? it appears it chains the slots together,
> but only the calling process will get a correct chain. the chain
> head (privs) is shared (in bss) and seen by all process so the
> others will get corrupted chains (chain link is private) no?
>
> i wonder what the intended use for privfree() was. theres no
> code using it.

i think the logic in tprivalloc is what was intended.

- erik

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

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

On 6 September 2015 at 00:38, <cinap_lenrek@felloff.net> wrote:

> is privfree() broken? it appears it chains the slots together,
> but only the calling process will get a correct chain.
>

The only way it works is to have a main process allocate and free slots for
use by
all participants, which is a workable scheme in many cases, and indeed
preferable
to a strictly-local allocation for certain types of data. For instance, to
tag a process
with (say) an application-defined Proc structure, that structure must be at
the same slot in
every process to allow it to be found.

With that scheme, there isn't any need for the lock, because only one
process can call it. If the cells were instead allocated using a strictly
local free list or bitmap,
which would be possible, there still wouldn't be any need for the lock,
so the original thinking is still obscure.

i think the logic in tprivalloc is what was intended.
>

probably, since a shared bitmap would need a lock and allow
any process to allocate a slot, which could then either be broadcast
to allow per-process tagging (as above), or allocation of a slot of only
local interest. even so, tprivfree is incomplete.

[-- Attachment #2: Type: text/html, Size: 2706 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

> probably, since a shared bitmap would need a lock and allow
> any process to allocate a slot, which could then either be broadcast
> to allow per-process tagging (as above), or allocation of a slot of only
> local interest. even so, tprivfree is incomplete.

a slot of local interest?  doesn't malloc serve that purpose well enough?

- erik

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[cinap_lenrek]

instead of trying to explain these semantics of privfree() in the
manpage, might just get rid of privfree() itself. globally allocate
the slots one after another.

--
cinap

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

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

On 6 September 2015 at 16:02, erik quanstrom <quanstro@quanstro.net> wrote:

> a slot of local interest?  doesn't malloc serve that purpose well enough?


It doesn't create a name for a per-process global.

[-- Attachment #2: Type: text/html, Size: 507 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

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

On 6 September 2015 at 19:21, <cinap_lenrek@felloff.net> wrote:

> manpage, might just get rid of privfree() itself. globally allocate
> the slots one after another.
>

it's useful to be able to reset some or all of the state in a supervisory
process after a failure and restart.
the tprivalloc/tprivfree [+bug fix] approach to allocation/deallocation
through a global bitmap
(but returning a void**)  is probably best for the time being, and keeps
the same interface and reasonable
semantics.

[-- Attachment #2: Type: text/html, Size: 948 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[erik quanstrom]

[-- Attachment #1: Type: text/html, Size: 1017 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

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

On 7 September 2015 at 01:30, erik quanstrom <quanstro@quanstro.net> wrote:

> unless by name an entry in a table shared by the set of memory sharing
> processes is what is meant


the table isn't shared. the address of the table is the same, but the
underlying memory is private,
and indeed can't be shared (there isn't a system call to map the pages
elsewhere in the shared address space).

[-- Attachment #2: Type: text/html, Size: 724 bytes --]

Re: [9fans] Privalloc(2) and rfork(RFPROC|RFMEM) (was: a pair nec bugs)

[Charles Forsyth]

[-- Attachment #1.1: Type: text/plain, Size: 107 bytes --]

In any case, an implementation along the lines of tprivalloc seems ok,
and passes my naive test program.

[-- Attachment #1.2: Type: text/html, Size: 188 bytes --]

[-- Attachment #2: privalloc.c --]
[-- Type: text/x-csrc, Size: 629 bytes --]

#include <u.h>
#include <libc.h>

static Lock	privlock;
static int	privinit;
static u32int privmap;

extern void	**_privates;
extern int	_nprivates;

void **
privalloc(void)
{
	void **p;
	int i;

	lock(&privlock);
	for(i = 0; i < 32 && i < _nprivates; i++){
		if((privmap & (1<<i)) == 0){
			privmap |= 1<<i;
			unlock(&privlock);
			p = &_privates[i];
			*p = nil;
			return p;
		}
	}
	unlock(&privlock);
	return nil;
}

void
privfree(void **p)
{
	int i;

	if(p != nil){
		i = p - _privates;
		if(i < 0 || i > _nprivates || (privmap & (1<<i)) == 0)
			abort();
		lock(&privlock);
		privmap &= ~(1<<i);
		unlock(&privlock);
	}
}