nt lockNoLock = 2;

  private UpdatableSeq read = new LinkedList();
  private UpdatableSeq write = new LinkedList();
  private UpdatableSeq wait = new LinkedList();
  private Semaphore s = new Semaphore(1);
  private int value = lockNoLock; // state of the lock
  private boolean debug = false;

  public Lock() {
  }

  public Lock(boolean debug) {
    this.debug = debug;
  }

  public void lock(Thread t, int type) {

    s.down();
    
    if (debug) System.out.println("lock start " + t.getName());

      if (value == lockNoLock) {
if (type == lockShared)
read.insertLast(t);
else // type == lockExclusive
write.insertLast(t);
value = type;
      }
      else if (value == lockShared) {
if (type == lockShared)
if (write.isEmpty())
read.insertLast(t);
else {
wait.insertLast(t);
s.up(); // problem here, race condition, since
// the thread may receive a resume
// before it suspends. however, it
// isn't possible to reverse these
// statements
// what is the solution? pass the
// suspend call to the semaphore?
if (debug) System.out.println("suspend " + t.getName());
t.suspend();
if (debug) System.out.println("wake " + t.getName());
s.down();
value = lockShared;
}
else { // type == lockExclusive
write.insertLast(t);
s.up();
if (debug) System.out.println("suspend " + t.getName());
t.suspend();
if (debug) System.out.println("wake " + t.getName());
s.down();
value = lockExclusive;
}
      }
      else // value == lockExclusive
if (type == lockShared) {
wait.insertLast(t);
s.up();
if (debug) System.out.println("suspend " + t.getName());
t.suspend();
if (debug) System.out.println("wake " + t.getName());
s.down();
value = lockShared;
}
else { // type == lockExclusive
write.insertLast(t);
s.up();
if (debug) System.out.println("suspend " + t.getName());
t.suspend();
if (debug) System.out.println("wake " + t.getName());
s.down();
value = lockExclusive;
}
    
    if (debug) System.out.println("lock end " + t.getName());

    if (debug) System.out.println("state " + value);

    s.up();

  }

  public void unlock(Thread t) {

    s.down();
    
    if (debug) System.out.println("unlock start " + t.getName());

      if (value == lockShared) {
read.removeOneOf(t);
if (read.isEmpty())
if (write.isEmpty())
value = lockNoLock;
else {
if (debug) System.out.println("resume " + ((Thread) write.first()).getName());
((Thread) write.first()).resume();
value = lockExclusive;
}
      }
      else { // value == lockExclusive
write.removeFirst(); // t must be head of queue
if (wait.isEmpty())
if (write.isEmpty())
value = lockNoLock;
else {
if (debug) System.out.println("resume " + ((Thread) write.first()).getName());
((Thread) write.first()).resume();
}
else {
// is this a bad move? this means that a thead sleeps with
// its thread on one queue and wakes with its thread on
// another queue
read = wait; // move all waiters to readers. must
// be no readers, of course
wait = new LinkedList(); // no waiters now
for (Enumeration e = read.elements(); e.hasMoreElements();) {
Thread tmp = (Thread) e.nextElement();
if (debug) System.out.println("resume " + tmp.getName());
tmp.resume();
}
value = lockShared;
}
      }

    if (debug) System.out.println("unlock end " + t.getName());
    
    if (debug) System.out.println("state " + value);

    s.up();
  }
}
-----------------------------
8. here's what i get when i execute the code
there seems to be alot of nulls in the output. i've stripped them out.
thus, the two lines in the output, starting with ", sys_thread_t" and with "d queue lock"
had a bunch of nulls at the beginning.


> make runbug
CLASSPATH=/home/cao/tomasic/disco; export CLASSPATH; javac bug/LockTest.java
CLASSPATH=/home/cao/tomasic/disco; export CLASSPATH; java bug.LockTest
0 0
10 10
10 10
20 20
10 10
20 20
20 20
30 30
10 10
20 20
20 20
30 30
20 20
30 30
30 30
SIGSEGV 11* segmentation violation
    si_signo [11]: SIGSEGV 11* segmentation violation
    si_errno [0]: Error 0
    si_code [1]: SEGV_ACCERR [addr: 0xef437de0]
, sys_thread_t:0xef5fdde0) prio=11
    "main" (TID:0xee3000a0, sys_thread_t:0x74480) prio=5 *current thread*
d queue lock: unowned
    Class lock: unowned
    Java stack lock: unowned
    Code rewrite lock: unowned
    Heap lock: unowned
    Has finalization queue lock: unowned
    Monitor IO lock: unowned
    Child death monitor: unowned
    Event monitor: unowned
    I/O monitor: unowned
    Alarm monitor: unowned
        Waiting to be notified:
            "clock handler"
    Sbrk lock: unowned
    Monitor cache lock: unowned
    Monitor registry: monitor owner: "main"
Thread Alarm Q:
*** Error code 134
make: Fatal error: Command failed for target `runbug'
> ls -l core
-rw-rw-r-- 1 tomasic 1871200 Feb 13 19:03 core
>
-------------------------
9. here's the trace

WARNING: i had to copy the core file to another machine, where dbx was running. so starting up
dbx gives me alot of complaints, but i do get a stack trace. if you want me to eliminate this
problem, i can do it, but it will take some time

(dbx) where
=>[1] _dostrfmon_unlocked(0xb, 0xefffeb00, 0xefffe940, 0x0, 0x2, 0x5), at 0xef6956c8
  [2] _ptrace(0xb, 0xefffeb00, 0xefffe940, 0x220, 0x0, 0xef437de0), at 0xef66ae34
  [3] allocateContextAndStack(0xefffecac, 0xef437de0, 0x0, 0x0, 0x562a0, 0x2), at 0x37c30
  [4] sysThreadCreate(0x20000, 0x1, 0x32fcc, 0xefffecac, 0xee308990, 0x1), at 0x3ccc0
  [5] threadCreate(0xee308990, 0x1, 0x20000, 0x32fcc, 0x562a0, 0x2), at 0x337bc
  [6] java_lang_Thread_start(0xee308990, 0xee34c1a0, 0x0, 0x0, 0xfffffff9, 0x1), at 0x3318c
  [7] Java_java_lang_Thread_start_stub(0x5ab6c, 0xeffffb14, 0x5aab8, 0x0, 0xfffffff9, 0x1), at 0x2379c
  [8] invokeSynchronizedNativeMethod(0xee308990, 0x619b4, 0x5ab6c, 0xeffffb14, 0x5ab44, 0x60900), at 0x22b4c
  [9] ExecuteJava(0xeffffb24, 0x5ab68, 0x5ab20, 0xffff, 0x5ab44, 0x5ab5c), at 0x2d9cc
  [10] do_execute_java_method_vararg(0x0, 0x79c01, 0x0, 0x5aacc, 0x5aaf4, 0x78ad8), at 0x2a080
  [11] do_execute_java_method(0xeffffb14, 0x78ad8, 0x0, 0x0, 0x79d60, 0x1), at 0x29aa4
  [12] start_java(0x78ad8, 0x3, 0xeffffb8c, 0x79d60, 0xeffffb8c, 0xeffffc84), at 0x308bc
(dbx)
----------------------

good luck -- i'm curious if this problem can been reported before.

Anthony Tomasic
From: Anthony Tomasic <###@###.###>
This does not look like form output to me.



1. bug report
2. jdk
3.
> java -version
java version "1.0beta2"
4. segmentation violation in multithreaded code
5.

> cat /etc/motd
Sun Microsystems Inc. SunOS 5.3 Generic September 1993

it's a sparc processor

6. no URL

7. okay, the code consist of two chunks. the first chunk is three classes, Lock, LockTest, and
Semaphore. the code for this is below.

the second part consists of the collections package, which i do not include (since
it is huge) the address is

http://g.oswego.edu/dl/classes/collections/index.html

and i'm not using the most recent version, but i doubt it matters.

to reproduce the bug, compile and execute the code.

the code for semaphore creates a Dijskra semaphore. the code for Lock creates a lock object. a
lock is in one of three states: none, shared, or exclusive.

all readers share the lock, writers use exclusive mode. and the lock is starvation free.
thus, readers and writers alternate. this the purpose of the wait queue.

--------------------------------
package bug;

public class Semaphore {
  private int count;
  private int initial;

  public Semaphore(int initial) {
    count = initial;
    this.initial = initial;
  }

  public synchronized void down() {
    while (count <= 0) {
      try {
        wait();
      } catch (InterruptedException e) {
      }
    }
    count --;
  }

  public synchronized void up() {
    count ++;
    notify();
  }
}
--------------------------
package bug;

import collections.*;
import java.util.*;
class LockTest extends Thread {
  private static int count;
  private static Lock l;

  private static boolean debug = false;
  private boolean read = false;// true if we read the counter

  public static void main(String args[]) {
// debug = true; l = new Lock(true); test(1);

// l = new Lock(); test(5); // this works
    l = new Lock(); test(6); // this does not

  }

  public LockTest(String s, boolean read) {
    super(s);
    this.read = read;
    if (debug) System.out.println("create " + s + " " + read);
  }

  private static void test(int num) {
    LinkedList ll = new LinkedList();
    int power = 1 << num;

    for (int i = 0; i < power; i++) {
      int result = 0;

      ll.clear();
      for (int j = 0; j < num; j++) {
        boolean read = (i>>j) % 2 == 0;
        ll.insertFirst(new LockTest("lock " + j, read));
        if (!read) result += 10;
      }

      count = 0;

      for (Enumeration e = ll.elements(); e.hasMoreElements();)
        ((Thread) e.nextElement()).start();
      
      boolean isalive;
      do {
        yield();
        isalive = false;
        for (Enumeration f = ll.elements(); f.hasMoreElements();)
          isalive = ((Thread) f.nextElement()).isAlive() || isalive;
      }
      while (isalive);
      
      System.out.println(count + " " + result);
    }
  }

  public void run () {
    if (debug) System.out.println("run " + getName());
    for (int i = 0; i < 10; i++) {
      yield();
      if (read) {
        try {
          l.lock(this, Lock.lockShared);
        }
        catch (Exception e) {
          System.out.println(e);
        };
      }
      else {
        try {
          l.lock(this, Lock.lockExclusive);
        }
        catch (Exception e) {
          System.out.println(e);
        };
        yield();
        int j = count;
        yield();
        j++;
        yield();
        count = j;
      }
      yield();
      try {
        l.unlock(this);
      }
      catch (Exception e) {
        System.out.println(e);
      };
    }
    if (debug) System.out.println("halt " + getName());
  }
}
------------------------------
package bug;

import collections.*;
import java.util.*;

public class Lock {
  public static final int lockShared = 0;
  public static final int lockExclusive = 1;
  public static final int lockNoLock = 2;

  private UpdatableSeq read = new LinkedList();
  private UpdatableSeq write = new LinkedList();
  private UpdatableSeq wait = new LinkedList();
  private Semaphore s = new Semaphore(1);
  private int value = lockNoLock; // state of the lock
  private boolean debug = false;

  public Lock() {
  }

  public Lock(boolean debug) {
    this.debug = debug;
  }

  public void lock(Thread t, int type) {

    s.down();
    
    if (debug) System.out.println("lock start " + t.getName());

      if (value == lockNoLock) {
        if (type == lockShared)
          read.insertLast(t);
        else // type == lockExclusive
          write.insertLast(t);
        value = type;
      }
      else if (value == lockShared) {
        if (type == lockShared)
          if (write.isEmpty())
            read.insertLast(t);
          else {
            wait.insertLast(t);
            s.up(); // problem here, race condition, since
                // the thread may receive a resume
                                // before it suspends. however, it
                                // isn't possible to reverse these
                                // statements
                                // what is the solution? pass the
                                // suspend call to the semaphore?
            if (debug) System.out.println("suspend " + t.getName());
            t.suspend();
            if (debug) System.out.println("wake " + t.getName());
            s.down();
            value = lockShared;
          }
        else { // type == lockExclusive
          write.insertLast(t);
          s.up();
          if (debug) System.out.println("suspend " + t.getName());
          t.suspend();
          if (debug) System.out.println("wake " + t.getName());
          s.down();
          value = lockExclusive;
        }
      }
      else // value == lockExclusive
        if (type == lockShared) {
          wait.insertLast(t);
          s.up();
          if (debug) System.out.println("suspend " + t.getName());
          t.suspend();
          if (debug) System.out.println("wake " + t.getName());
          s.down();
          value = lockShared;
        }
        else { // type == lockExclusive
          write.insertLast(t);
          s.up();
          if (debug) System.out.println("suspend " + t.getName());
          t.suspend();
          if (debug) System.out.println("wake " + t.getName());
          s.down();
          value = lockExclusive;
        }
    
    if (debug) System.out.println("lock end " + t.getName());

    if (debug) System.out.println("state " + value);

    s.up();

  }

  public void unlock(Thread t) {

    s.down();
    
    if (debug) System.out.println("unlock start " + t.getName());

      if (value == lockShared) {
        read.removeOneOf(t);
        if (read.isEmpty())
          if (write.isEmpty())
            value = lockNoLock;
          else {
            if (debug) System.out.println("resume " + ((Thread) write.first()).getName());
            ((Thread) write.first()).resume();
            value = lockExclusive;
          }
      }
      else { // value == lockExclusive
        write.removeFirst(); // t must be head of queue
        if (wait.isEmpty())
          if (write.isEmpty())
            value = lockNoLock;
          else {
            if (debug) System.out.println("resume " + ((Thread) write.first()).getName());
            ((Thread) write.first()).resume();
          }
        else {
          // is this a bad move? this means that a thead sleeps with
          // its thread on one queue and wakes with its thread on
          // another queue
          read = wait; // move all waiters to readers. must
          // be no readers, of course
          wait = new LinkedList(); // no waiters now
          for (Enumeration e = read.elements(); e.hasMoreElements();) {
            Thread tmp = (Thread) e.nextElement();
            if (debug) System.out.println("resume " + tmp.getName());
            tmp.resume();
          }
          value = lockShared;
        }
      }

    if (debug) System.out.println("unlock end " + t.getName());
    
    if (debug) System.out.println("state " + value);

    s.up();
  }
}
-----------------------------
8. here's what i get when i execute the code
there seems to be alot of nulls in the output. i've stripped them out.
thus, the two lines in the output, starting with ", sys_thread_t" and with "d queue lock"
had a bunch of nulls at the beginning.


> make runbug
CLASSPATH=/home/cao/tomasic/disco; export CLASSPATH; javac bug/LockTest.java
CLASSPATH=/home/cao/tomasic/disco; export CLASSPATH; java bug.LockTest
0 0
10 10
10 10
20 20
10 10
20 20
20 20
30 30
10 10
20 20
20 20
30 30
20 20
30 30
30 30
SIGSEGV 11* segmentation violation
    si_signo [11]: SIGSEGV 11* segmentation violation
    si_errno [0]: Error 0
    si_code [1]: SEGV_ACCERR [addr: 0xef437de0]
, sys_thread_t:0xef5fdde0) prio=11
    "main" (TID:0xee3000a0, sys_thread_t:0x74480) prio=5 *current thread*
d queue lock: unowned
    Class lock: unowned
    Java stack lock: unowned
    Code rewrite lock: unowned
    Heap lock: unowned
    Has finalization queue lock: unowned
    Monitor IO lock: unowned
    Child death monitor: unowned
    Event monitor: unowned
    I/O monitor: unowned
    Alarm monitor: unowned
        Waiting to be notified:
            "clock handler"
    Sbrk lock: unowned
    Monitor cache lock: unowned
    Monitor registry: monitor owner: "main"
Thread Alarm Q:
*** Error code 134
make: Fatal error: Command failed for target `runbug'
> ls -l core
-rw-rw-r-- 1 tomasic 1871200 Feb 13 19:03 core
>
-------------------------
9. here's the trace

WARNING: i had to copy the core file to another machine, where dbx was running. so starting up
dbx gives me alot of complaints, but i do get a stack trace. if you want me to eliminate this
problem, i can do it, but it will take some time

(dbx) where
=>[1] _dostrfmon_unlocked(0xb, 0xefffeb00, 0xefffe940, 0x0, 0x2, 0x5), at 0xef6956c8
  [2] _ptrace(0xb, 0xefffeb00, 0xefffe940, 0x220, 0x0, 0xef437de0), at 0xef66ae34
  [3] allocateContextAndStack(0xefffecac, 0xef437de0, 0x0, 0x0, 0x562a0, 0x2), at 0x37c30
  [4] sysThreadCreate(0x20000, 0x1, 0x32fcc, 0xefffecac, 0xee308990, 0x1), at 0x3ccc0
  [5] threadCreate(0xee308990, 0x1, 0x20000, 0x32fcc, 0x562a0, 0x2), at 0x337bc
  [6] java_lang_Thread_start(0xee308990, 0xee34c1a0, 0x0, 0x0, 0xfffffff9, 0x1), at 0x3318c
  [7] Java_java_lang_Thread_start_stub(0x5ab6c, 0xeffffb14, 0x5aab8, 0x0, 0xfffffff9, 0x1), at 0x2379c
  [8] invokeSynchronizedNativeMethod(0xee308990, 0x619b4, 0x5ab6c, 0xeffffb14, 0x5ab44, 0x60900), at 0x22b4c
  [9] ExecuteJava(0xeffffb24, 0x5ab68, 0x5ab20, 0xffff, 0x5ab44, 0x5ab5c), at 0x2d9cc
  [10] do_execute_java_method_vararg(0x0, 0x79c01, 0x0, 0x5aacc, 0x5aaf4, 0x78ad8), at 0x2a080
  [11] do_execute_java_method(0xeffffb14, 0x78ad8, 0x0, 0x0, 0x79d60, 0x1), at 0x29aa4
  [12] start_java(0x78ad8, 0x3, 0xeffffb8c, 0x79d60, 0xeffffb8c, 0xeffffc84), at 0x308bc
(dbx)
----------------------

good luck -- i'm curious if this problem can been reported before.

Anthony Tomasic

The description field as copied from bug report 1239410 follows:

>From: Anthony Tomasic <###@###.###>
This does not look like form output to me.



1. bug report
2. jdk
3.
> java -version
java version "1.0beta2"
4. segmentation violation in multithreaded code
5.

> cat /etc/motd
Sun Microsystems Inc. SunOS 5.3 Generic September 1993

it's a sparc processor

6. no URL

7. okay, the code consist of two chunks. the first chunk is three classes, Lock, LockTest, and
Semaphore. the code for this is below.

the second part consists of the collections package, which i do not include (since
it is huge) the address is

http://g.oswego.edu/dl/classes/collections/index.html

and i'm not using the most recent version, but i doubt it matters.

to reproduce the bug, compile and execute the code.

the code for semaphore creates a Dijskra semaphore. the code for Lock creates a lock object. a
lock is in one of three states: none, shared, or exclusive.

all readers share the lock, writers use exclusive mode. and the lock is starvation free.
thus, readers and writers alternate. this the purpose of the wait queue.

--------------------------------
package bug;

public class Semaphore {
  private int count;
  private int initial;

  public Semaphore(int initial) {
    count = initial;
    this.initial = initial;
  }

  public synchronized void down() {
    while (count <= 0) {
      try {
wait();
      } catch (InterruptedException e) {
      }
    }
    count --;
  }

  public synchronized void up() {
    count ++;
    notify();
  }
}
--------------------------
package bug;

import collections.*;
import java.util.*;

class LockTest extends Thread {
  private static int count;
  private static Lock l;

  private static boolean debug = false;
  private boolean read = false;// true if we read the counter

  public static void main(String args[]) {
// debug = true; l = new Lock(true); test(1);

// l = new Lock(); test(5); // this works
    l = new Lock(); test(6); // this does not

  }

  public LockTest(String s, boolean read) {
    super(s);
    this.read = read;
    if (debug) System.out.println("create " + s + " " + read);
  }

  private static void test(int num) {
    LinkedList ll = new LinkedList();
    int power = 1 << num;

    for (int i = 0; i < power; i++) {
      int result = 0;

      ll.clear();
      for (int j = 0; j < num; j++) {
boolean read = (i>>j) % 2 == 0;
ll.insertFirst(new LockTest("lock " + j, read));
if (!read) result += 10;
      }

      count = 0;

      for (Enumeration e = ll.elements(); e.hasMoreElements();)
((Thread) e.nextElement()).start();
      
      boolean isalive;
      do {
yield();
isalive = false;
for (Enumeration f = ll.elements(); f.hasMoreElements();)
isalive = ((Thread) f.nextElement()).isAlive() || isalive;
      }
      while (isalive);
      
      System.out.println(count + " " + result);
    }
  }

  public void run () {
    if (debug) System.out.println("run " + getName());
    for (int i = 0; i < 10; i++) {
      yield();
      if (read) {
try {
l.lock(this, Lock.lockShared);
}
catch (Exception e) {
System.out.println(e);
};
      }
      else {
try {
l.lock(this, Lock.lockExclusive);
}
catch (Exception e) {
System.out.println(e);
};
yield();
int j = count;
yield();
j++;
yield();
count = j;
      }
      yield();
      try {
l.unlock(this);
      }
      catch (Exception e) {
System.out.println(e);
      };
    }
    if (debug) System.out.println("halt " + getName());
  }
}
------------------------------
package bug;

import collections.*;
import java.util.*;

public class Lock {
  public static final int lockShared = 0;
  public static final int lockExclusive = 1;
  public static final i