Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-1239410

fp.bugs 3587 segmentation violation in multithreaded code

    XMLWordPrintable

    Details

    • Subcomponent:
    • CPU:
      sparc
    • OS:
      solaris_2.5

      Description

      >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


        Attachments

          Issue Links

            Activity

              People

              Assignee:
              tlindholsunw Timothy Lindholm (Inactive)
              Reporter:
              bhagen Benjamin Hagen (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: