[Top] [All Lists]

patches for test-and-set without ll/sc (Re: thread-ready ABIs)

Subject: patches for test-and-set without ll/sc (Re: thread-ready ABIs)
From: Machida Hiroyuki <>
Date: Tue, 22 Jan 2002 15:27:44 +0900
In-reply-to: <>
References: <> <002c01c1a1a9$b9f0de40$0deca8c0@Ulysses> <>
Hi, all.

As I said at 1/20, I'll post the short descriptions about our
test-and-set implementation and patches for linux-2.4.17 and


We implemented the fast and safe user level test and set function for 
single MIPS CPUs. You don't need to use LL/SC and sysmips() with
this method. (excatly say, sysmips() is needed for initializing, but
once initialized, we don't use it any more).

  NOTE: We assume the single processor to use this method, You can
  not use our method for SMP.  


  * kernel side change #1
        Set specific constant (we call this value
        "_TST_ACCESS_MAGIC") to K1 on every transition from kernel
        mode to user mode. This means you can use k1 in any
        exception handler as same as before our method introduced,
        except that you have to do 
                "li     k1, _TST_ACCESS_MAGIC" 
        at the very previous of
                "j      k0;
        We choose the value of _TST_ACCESS_MAGIC, to cause SEGV
        fault when you use this value as address.

  * kernel side change #2
        On memory fault hander, kernel check write-access to 
        _TST_ACCESS_MAGIC from fixed address range of user process.
        If the condtion is met, kernel restart user process 
        from _TST_START_MAGIC. 

  * kernel side change #3
        We add pseudo device driver "/dev/tst" to provide
        test_and_set procedure at the same virtual address
        (_TST_START_MAGIC) to any user process. 

                .set noreorder
                move    k1, a0
                lw      v0, 0(a0)
                bnez    v0, 1f
                bne     k1, a0, 0b
                nop                     ....<point A>
                sw      a1, 0(k1)
                jr      ra

  * glibc change:

        We implement  test_and_set(addr, val) as follows,

                Do mmap /dev/tst to _TST_START_MAGIC, if not yet mapped.
                call _TST_START_MAGIC(addr, val)
        If we can't open /dev/tst then, use sysmips() as final resort.

        If  no context-switch is occured in _TST_START_MAGIC()
        procedure,  nobody changes the mutex var. It's no problem. 
        So you can do _TST_START_MAGIC() porcedure as you see.

        But, if some context-swtich is occured in _TST_START_MAGIC() 
        somebody chages the mutex var. It's a problem.
        We must not store to the mutex var, if context-swtich is
        occured at <point A>.  
        In our method, kernel sets k1 as _TST_ACCESS_MAGIC on
        transition to user mode.  "sw      a1, 0(k1)"  causes
        SEGV-fault if context-swtich is occured at <point A>. 
        The SEGV-fault hander catch this situation, restart user
        process from top of _TST_START_MAGIC().


I attached three patches;
        1. patch for linux kernel 2.4.17 (SourceForge tree)
        2. patch for glibc 2.2.3  (of HHL 2.0)
        3. patch for linuxthread 2.2.3 (of HHL 2.0)

To test those patches; you must
        turn on CONFIG_MIPS_TST_DEV on config kernel,
        have working version of sysmips(MIPS_ATOMIC_SET),
        update kernel headers before building glibc and
        make /dev/tst device ("mknod c /dev/tst 123 0", 123 is a
        tempoary major number for this device) 

I'v tested  at ITE board. On testing, I'v made lettle changes into
"drivers/char/" and "arch/mips/kernel/sysmip.c" to enable
CONFIG_MIPS_TST_DEV and to work sysmips() at ITE board. Those chages
are not included in the patch set.


    You can find the paper about it in
        (sorry in japanese only)

    The abstract of the paper is following;

        The Implementation of user level test-and-set on PS2 Linux
        In the multi-thread environment like Linux, a fast
        user-level mutual exclusion mechanism is strongly
        required. But MIPS chips designed for embedded and single
        processor, like the Emotion Engine, have no atomic
        test-and-set instruction. We implemented the fast user-level
        mutual exclusion without invoking system-call and its costs,
        on the PS2 Linux. This method utilizes the memory protection 
        facility of Operating System, to detect preemption and
        nullify the operation. In this paper, we present the method
        and its evaluation.  

Hiroyuki Machida
Sony Corp.

Attachment: linux-2.4-mips-tas.patch
Description: Text document

Attachment: glibc-2.2.3-mips-tas.patch
Description: Text document

Attachment: linuxthread-2.2.3-mips-tas.patch
Description: Text document

<Prev in Thread] Current Thread [Next in Thread>