RE: PROT_SEM + FUTEX

RE: PROT_SEM + FUTEX

[Perez-Gonzalez, Inaky]

> frequently. I would find any application that needed to actively wait
> on 4000 futex objects to be either incorrectly designed, or under
> enough load that I think an investment in a few more CPU's would be
> worthwhile... :-)

Not really; well, yeah really, but on other side; the case 
I am talking about is threaded applications with thousands of threads 
[no  kidding], where for example, 2K are producers and 4K are consumers;
there you have a rough 50% rate of contention for each lock [assume
each producer has a lock that the two consumers need to acquire]; the
contention might not be very bad, but as an average you might have
around 1000 futexes locked, that would add up to, in worst case, 1000
pages locked ...

However, if you do some thousand threads, you better have more memory
so that 1000 pages locked does not really mind :]

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my
fault]

Re: PROT_SEM + FUTEX

[Mark Mielke]

On Mon, Nov 11, 2002 at 02:31:28PM -0800, Perez-Gonzalez, Inaky wrote:
> > As long as the person attempting to manipulate the FUTEX word succeeds
> > (i.e. 0 -> 1, or 0 -> -1, or whatever), futex_wait() need not 
> > be issued. futex_wake() only pins the page for a brief period of time.
> Define brief - remember that if the futex is locked, the page is already
> pinned, futex_wake() is just making sure it is there while it uses it - and
> again, as you said before, this is completely application specific; the
> kernel cannot count on any specific behaviour on the user side.

I am defining "brief" as the length of time that futex_wake() takes to
pin and unpin the page, which I hope is quite short as the internal
futex locks are also held during this time.

I might be doing something wrong -- but it seems to me that using inc,
dec, xchg or cmpxchg (depending on the object being implemented) is
all that is necessary for IA-32. futex_wait() should only be executed
by threads which decides that they need to wait, which on an
application with a well designed thread architecture, should not occur
frequently. I would find any application that needed to actively wait
on 4000 futex objects to be either incorrectly designed, or under
enough load that I think an investment in a few more CPU's would be
worthwhile... :-)

> > same cache line. Also, if the memory word is used to synchronize
> > access to a smaller data structure (<128 bytes), it is actually
> > optimal to include the memory word used to synchronize access to the
> > data, and the data itself, in the same cache line.
> Sure, this makes full sense; if you are using the futexes straight off from
> the kernel for synchronization; however, when used by something like NGPT's
> mutex system, the story changes, because you cannot assume anything, you
> have to be generic - and there is my bias. 
> Lucky you that don't need to worry about that :)

In this case it isn't luck -- although I am certain that NGPT, and the
other recent projects to improve the speed of threads and thread
synchronization on Linux are doing very well, I have been dabbing with
purposefully avoiding 'pthreads-like' libraries for synchronization
primitives. Originally my goal was to reduce the overhead of a
MUTEX-like object and a RWLOCK-like object to be a single word. The
increased efficiency, and reduced storage requirement for these
storage primitives would allow me to use them at more granular levels,
which reduces the potential for contention.

At some point, the need to be absolutely general and portable gets in
the way of being efficient. You seem to be trying to accomplish all
three goals (NGPT), a task that I can appreciate, but one that I
cannot envy... :-)

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

RE: PROT_SEM + FUTEX

[Perez-Gonzalez, Inaky]

> hoping that
> > > PROT_SEM is not required, as I intend to scatter the 
> words throughout
> > > memory, and it would be a real pain to mprotect(PROT_SEM) 
> each page
> > > that contains a FUTEX word.
> >
> > Still you want to group them as much as possible - each 
> time you lock
> > a futex you are pinning the containing page into physical 
> memory, that
> > would cause that if you have, for example, 4000 futexes 
> locked in 4000 
> > different pages, there is going to be 4 MB of memory locked 
> in ... it
> > helps to have an allocator that ties them together.
> 
> This is not necessarily correct for a high-capacity, low-latency
> application (i.e. a poorly designed thread architecture might suffer
> from this problem -- but a poorly designed thread architecture suffers
> from more problems than pinned pages).

Too much thinking about the general case - you are absolutely right, but
only as long as you are sure that the contention rate across the many
futexes you have is going to be _really_ low; that, or if your applications
are always mlocked in memory, then you are ok.

I keep thinking about multi-thousand threads and their locks, so spare me, I
forget about the well-designed cases.

> As far as I understand - PROT_SEM has no effect on the behaviour of
> FUTEX operations. I think it should be removed.

Rusty (Russel) declared that Linus declared that platforms that don't
implement a sane cache architecture can not implement futexes ... so I guess
this means we can forget about PROT_SEM for futexes.

> As long as the person attempting to manipulate the FUTEX word succeeds
> (i.e. 0 -> 1, or 0 -> -1, or whatever), futex_wait() need not 
> be issued.
> futex_wake() only pins the page for a brief period of time.

Define brief - remember that if the futex is locked, the page is already
pinned, futex_wake() is just making sure it is there while it uses it - and
again, as you said before, this is completely application specific; the
kernel cannot count on any specific behaviour on the user side.

> same cache line. Also, if the memory word is used to synchronize
> access to a smaller data structure (<128 bytes), it is actually
> optimal to include the memory word used to synchronize access to the
> data, and the data itself, in the same cache line.

Sure, this makes full sense; if you are using the futexes straight off from
the kernel for synchronization; however, when used by something like NGPT's
mutex system, the story changes, because you cannot assume anything, you
have to be generic - and there is my bias. 

Lucky you that don't need to worry about that :)

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my
fault]

Re: PROT_SEM + FUTEX

[Mark Mielke]

On Mon, Nov 11, 2002 at 12:28:32PM -0800, Perez-Gonzalez, Inaky wrote:
> > I am beginning to play with the FUTEX system call. I am hoping that
> > PROT_SEM is not required, as I intend to scatter the words throughout
> > memory, and it would be a real pain to mprotect(PROT_SEM) each page
> > that contains a FUTEX word.
> Still you want to group them as much as possible - each time you lock
> a futex you are pinning the containing page into physical memory, that
> would cause that if you have, for example, 4000 futexes locked in 4000 
> different pages, there is going to be 4 MB of memory locked in ... it
> helps to have an allocator that ties them together.

This is not necessarily correct for a high-capacity, low-latency
application (i.e. a poorly designed thread architecture might suffer
from this problem -- but a poorly designed thread architecture suffers
from more problems than pinned pages).

As long as the person attempting to manipulate the FUTEX word succeeds
(i.e. 0 -> 1, or 0 -> -1, or whatever), futex_wait() need not be issued.
futex_wake() only pins the page for a brief period of time.

On IA-32, especially for PIII + P4, my understanding is that memory
words used for the purpose of thread synchronization, on an SMP
machine, should not allow two independent memory words to occupy the
same cache line. Also, if the memory word is used to synchronize
access to a smaller data structure (<128 bytes), it is actually
optimal to include the memory word used to synchronize access to the
data, and the data itself, in the same cache line.

Since the synchronization memory + data for a data structure may be
128 bytes or more (to at least put the synchronization memory words on
separate cache lines), 4000 such data structures would use up 100+
pages whether or not the memory was scattered. The real benefit of the
FUTEX concept is that spinlocks are 'cheap' and can be used with such
a granularity that the possibility of contention is extremely low.

As far as I understand - PROT_SEM has no effect on the behaviour of
FUTEX operations. I think it should be removed.

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

RE: PROT_SEM + FUTEX

[Perez-Gonzalez, Inaky]

> I am beginning to play with the FUTEX system call. I am hoping that
> PROT_SEM is not required, as I intend to scatter the words throughout
> memory, and it would be a real pain to mprotect(PROT_SEM) each page
> that contains a FUTEX word.

Still you want to group them as much as possible - each time you lock
a futex you are pinning the containing page into physical memory, that
would cause that if you have, for example, 4000 futexes locked in 4000 
different pages, there is going to be 4 MB of memory locked in ... it
helps to have an allocator that ties them together.

Cheers,

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my
fault]

PROT_SEM + FUTEX

[Mark Mielke]

Is PROT_SEM necessary anymore? 2.5.46 does not seem to include any
references to it that adjust behaviour for pages. Would it be
reasonable to remove it, or #define PROT_SEM to (0) to avoid
confusion?

I am beginning to play with the FUTEX system call. I am hoping that
PROT_SEM is not required, as I intend to scatter the words throughout
memory, and it would be a real pain to mprotect(PROT_SEM) each page
that contains a FUTEX word.

For systems that do not support the FUTEX system call (2.4.x?),
is sched_yield() the best alternative?

Thanks,
mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/