It is currently Mon, 26 Oct 2020 04:20:40 GMT



 
Author Message
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

This is the generic portion of lockless gettimeofday. It defines frlock
and changes locking of xtime_lock from rwlock to frlock.

  frlock-xtime.patch
8K Download


 Sun, 17 Jul 2005 00:50:15 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

These need to be mb(), not wmb(), if you want the bits in between
to actually happen in between, as with your xtime example.  At
present there's nothing stoping xtime from being *read* before
your read from pre_sequence happens.

r~
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Sun, 17 Jul 2005 08:10:11 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

But with frlocks we synchronise writers with a spinlock, so shouldnt it
provide that synchronisation?

Anton
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Sun, 17 Jul 2005 08:40:13 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

Richard is referring to the new fr_write_begin/end code, which doesn't take a
spinlock because it assumes that writer serialisation has been provided by
external means.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Sun, 17 Jul 2005 09:50:13 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

First, write_begin/end can only be safely used when there is separate
writer synchronization such as a spin_lock or semaphore.  
As far as I know, semaphore or spin_lock guarantees a barrier.
So xtime or anything else can not be read before the spin_lock.

Using mb() is more paranoid than necessary.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 02:20:13 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

yes, it should only generate a superflous lock on x86.

it shouldn't even be necessary in fr_write_trylock.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 02:40:06 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

If you want stuff to happen *between* the write_begin/end, or
indeed for the begin/end not to be interleaved, then mb() is
absolutely necessary.  The most likely dynamic reordering of

        //begin
        t1 = rw->pre_sequence
        t1 += 1
        rw->pre_sequence = t1
        wmb()

        //stuff
        xtimensec = xtime.tv_nsec

        //end
        wmb()
        t2 = rw->post_sequence
        t2 += 1
        rw->post_sequence = t2

is

        t1 = rw->pre_sequence
        t2 = rw->post_sequence
        xtimensec = xtime.tv_nsec
        t1 += 1;
        t2 += 2;
        rw->pre_sequence = t1
        wmb()
        wmb()
        rw->post_sequence = t2

Why?  Because pre_sequence and post_sequence are in the same
cache line, and both reads could be satisfied in the same
cycle by the same line fill from main memory.

If you don't care about stuff happening in between the
write_begin/end, then why are you using them at all?

r~
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 02:50:05 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

No it's:

        t1 = rw->pre_sequence
        t2 = rw->post_sequence
        t1 += 1;
        t2 += 2;
        rw->pre_sequence = t1
        wmb()
        xtimensec = xtime.tv_nsec
        wmb()
        rw->post_sequence = t2

you're missing xtimensec is a write.

or this if you prefer:

        spin_lock() / now xtime can't change under us

        t1 = rw->pre_sequence
        t2 = rw->post_sequence
        t3 = xtime.tv_nsec
        t1 += 1;
        t2 += 2;
        rw->pre_sequence = t1
        wmb()
        xtimensec = t3
        wmb()
        rw->post_sequence = t2

        spin_unlock() / now xtime can change again

and the above is the optimal implementation of the write-side. We
definitely don't want to forbid those reoderings. if gcc or cpu thinks
it's worthwhile they must be allowed to optimize it since it's legal.

I believe wmb() is correct, and mb() is overkill.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 03:00:14 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

[snip - memory barrier for fr_write_begin]

What about the memory barrier in fr_read_begin?
If I understand the Intel documentation correctly, then i386 doesn't need them:
"Writes by a single processor are observed in the same order by all processors"

I think "smp_read_barrier_depends()" (i.e. a nop for i386) is sufficient. Attached is a test app - could someone try it? I don't have access to a SMP system right now.

What about permitting arch overrides for the memory barriers? E.g. ia64 has acquire and release memory barriers - it doesn't map to the Linux wmb()/rmb() scheme.

--
        Manfred

[ frlock.cpp 2K ]
/*
 * frlock: test for Intel memory ordering.
 * Copyright (C) 1999,2003 by Manfred Spraul.
 *
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL)
 * $Header: /pub/home/manfred/cvs-tree/movopt/frlock.cpp,v 1.2 2003/01/26 10:41:39 manfred Exp $
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <assert.h>

static volatile int g_val1;
static volatile int g_val2;
static volatile int g_seq1;
static volatile int g_seq2;

static volatile int start;
#define MB()    __asm__ __volatile__ ("lock;addl $0,(%%esp)\n\t" \
                                        :/* no output*/ \
                                        :/* no input*/:"cc","memory")

#define DELAY()         do { int i; for(i=0;i<1000;i++); } while(0)

void* threadfnc(void* param)
{
        while(!start);
        if(1 == (int)param)
                goto cpu1;
        if(2 == (int)param)
                goto cpu2;
        assert(0);
cpu1:
        {       // reader:
                for(;;) {
                        int x1,x2,val1,val2;

                        x1 = g_seq1;
                        val1 = g_val1;
                        val2 = g_val2;
                        x2 = g_seq2;
                        if (x1 == x2) {
                                if (val1 != val2) {
                                        printf("Bad! memory ordering violation with %d/%d: %d/%d.\n", x1, x2, val1, val2);
                                }
                        }
                }
        }
cpu2:
        {       // writer:
                int target = 0;
                for (;;) {

                        // write 1:
                        target++;
                        g_seq1 = target;
                        g_val1 = target;
                        g_val2 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 2:
                        target++;
                        g_seq1 = target;
                        g_val1 = target;
                        MB();
                        g_val2 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 3:
                        target++;
                        g_seq1 = target;
                        g_val2 = target;
                        g_val1 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 4:
                        target++;
                        g_seq1 = target;
                        g_val2 = target;
                        MB();
                        g_val1 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 5:
                        target++;
                        g_seq1 = target;
                        g_val1 = target;
                        MB(); MB();
                        g_val2 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 6:
                        target++;
                        g_seq1 = target;
                        g_val1 = target;
                        MB(); DELAY();
                        g_val2 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 7:
                        target++;
                        g_seq1 = target;
                        g_val2 = target;
                        MB(); MB();
                        g_val1 = target;
                        g_seq2 = target;
                        DELAY();

                        // write 8:
                        target++;
                        g_seq1 = target;
                        g_val2 = target;
                        MB(); DELAY();
                        g_val1 = target;
                        g_seq2 = target;
                        DELAY();
                }
        }

void start_thread(int id)
{
        pthread_t thread;
        int res;

        res = pthread_create(&thread,NULL,threadfnc,(void*)id);
        if(res != 0)
                assert(false);

int main()
{
        printf("movopt:\n");
        start_thread(1);
        start_thread(2);
        printf(" starting, please wait.\n");
        fflush(stdout);
        start = 1;
        for(;;) sleep(1000);



 Mon, 18 Jul 2005 19:30:19 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

I don't see what you mean, there is no dependency we can rely on between
the read of the sequence number and the critical section reads, the
critical section reads has nothing to do with the sequence number reads
and the frlock itself.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 19:30:25 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

You are right - "observed in the same order by all processors" only
means that the memory interface of the cpus see all writes in order, not
that instruction executed by the cpus will observe the writes in order.

That leaves ia64 with the acquire/release barriers.

--
    Manfred

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 20:10:17 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

Try to put [g_val1, g_seq1] and [g_val2, g_seq2] on two different cache
lines and run it on a SMP system using CPUs with a partitioned cache
architecture. Even if you do an WMB on writer side, you might see a
different order w/out an RMB on the reader side. This because the two
cache lines might be committed to different partitions with different
loads, and the latest ( in time order ) commit might see a fastest path
due a lower traffic. An RMB on the reader side ( that is usually expensive )
wait for all CPUs's memory controllers to flush their stuff before
resuming execution.

- Davide

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 20:50:21 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

See the PPro errata. There are some constraints on this in the real
world. You may need locked ops on the ppro and earlier cpus while
being able to do it the fast way on PII and higher

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Mon, 18 Jul 2005 22:40:11 GMT   
 (1/4) 2.5.59 fast reader/writer lock for gettimeofday

Eh?  xtimensec is a register.

r~
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Tue, 19 Jul 2005 01:50:12 GMT   
 
   [ 16 post ]  Go to page: [1] [2]

Similar Threads

1. (2/4) 2.5.59 fast reader/writer lock for gettimeofday

2. (4/4) 2.5.59 fast reader/writer lock for gettimeofday

3. (3/4) 2.5.59 fast reader/writer lock for gettimeofday

4. (0/4) 2.5.59 fast reader/writer lock for gettimeofday

5. fast reader/writer lock for gettimeofday 2.5.30

6. fast reader/writer lock for gettimeofday 2.5.30

7. "tee", but with fast writer, 1 slow reader and 1 fast reader

8. kernel performance issue - spins on readers/writer locks

9. how to implement readers/writer lock

10. reader-writer spin locks


 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software