changeset 273:9b6b671dd1e0

Generators: SeqCstTraceGenerator should generate the threads directly, without prior permutations
author shade
date Tue, 24 May 2016 00:58:53 +0300
parents ff8922143fdf
children c496ad24fb3b
files jcstress-core/src/main/java/org/openjdk/jcstress/util/HashMultimap.java jcstress-core/src/main/java/org/openjdk/jcstress/util/Multimap.java jcstress-core/src/main/java/org/openjdk/jcstress/util/TreeMultimap.java jcstress-core/src/main/java/org/openjdk/jcstress/util/TreesetMultimap.java jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/MultiThread.java jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Op.java jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Phase.java jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/SeqCstTraceGenerator.java jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Trace.java
diffstat 9 files changed, 222 insertions(+), 272 deletions(-) [+]
line wrap: on
line diff
--- a/jcstress-core/src/main/java/org/openjdk/jcstress/util/HashMultimap.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-core/src/main/java/org/openjdk/jcstress/util/HashMultimap.java	Tue May 24 00:58:53 2016 +0300
@@ -97,13 +97,18 @@
     @Override
     public Collection<V> values() {
         Collection<V> result = new ArrayList<>();
-        for (K key : map.keySet()) {
-            result.addAll(map.get(key));
+        for (Collection<V> vs : map.values()) {
+            result.addAll(vs);
         }
         return result;
     }
 
     @Override
+    public Collection<Collection<V>> valueGroups() {
+        return map.values();
+    }
+
+    @Override
     public void remove(K key) {
         map.remove(key);
     }
--- a/jcstress-core/src/main/java/org/openjdk/jcstress/util/Multimap.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-core/src/main/java/org/openjdk/jcstress/util/Multimap.java	Tue May 24 00:58:53 2016 +0300
@@ -93,6 +93,8 @@
 
     Collection<V> values();
 
+    Collection<Collection<V>> valueGroups();
+
     void remove(K key);
 
 }
--- a/jcstress-core/src/main/java/org/openjdk/jcstress/util/TreeMultimap.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-core/src/main/java/org/openjdk/jcstress/util/TreeMultimap.java	Tue May 24 00:58:53 2016 +0300
@@ -97,13 +97,18 @@
     @Override
     public Collection<V> values() {
         Collection<V> result = new ArrayList<>();
-        for (K key : map.keySet()) {
-            result.addAll(map.get(key));
+        for (Collection<V> vs : map.values()) {
+            result.addAll(vs);
         }
         return result;
     }
 
     @Override
+    public Collection<Collection<V>> valueGroups() {
+        return map.values();
+    }
+
+    @Override
     public void remove(K key) {
         map.remove(key);
     }
--- a/jcstress-core/src/main/java/org/openjdk/jcstress/util/TreesetMultimap.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-core/src/main/java/org/openjdk/jcstress/util/TreesetMultimap.java	Tue May 24 00:58:53 2016 +0300
@@ -98,13 +98,18 @@
     @Override
     public Collection<V> values() {
         Collection<V> result = new ArrayList<>();
-        for (K key : map.keySet()) {
-            result.addAll(map.get(key));
+        for (Collection<V> vs : map.values()) {
+            result.addAll(vs);
         }
         return result;
     }
 
     @Override
+    public Collection<Collection<V>> valueGroups() {
+        return map.values();
+    }
+
+    @Override
     public void remove(K key) {
         map.remove(key);
     }
--- a/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/MultiThread.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/MultiThread.java	Tue May 24 00:58:53 2016 +0300
@@ -25,22 +25,17 @@
 package org.openjdk.jcstress.generator.seqcst;
 
 import org.openjdk.jcstress.util.HashMultimap;
-import org.openjdk.jcstress.util.HashMultiset;
 import org.openjdk.jcstress.util.Multimap;
-import org.openjdk.jcstress.util.Multiset;
 
 import java.util.*;
 import java.util.stream.Collectors;
 
 public class MultiThread {
-    private final Trace original;
     private final List<Trace> threads;
 
-    public MultiThread(Trace original, Collection<Trace> copy) {
-        this.original = original;
-
+    public MultiThread(Collection<Trace> ts) {
         this.threads = new ArrayList<>();
-        for (Trace t : copy) {
+        for (Trace t : ts) {
             if (!t.ops().isEmpty())
                 threads.add(t);
         }
@@ -63,7 +58,7 @@
             Trace cT = copy.get(t);
             if (cT.ops().isEmpty()) {
                 copy.remove(t);
-                newTraces.addAll(new MultiThread(original, copy).linearize());
+                newTraces.addAll(new MultiThread(copy).linearize());
             } else {
                 Op op = cT.ops().get(0);
                 copy.set(t, cT.removeFirst());
@@ -72,7 +67,7 @@
                     copy.remove(t);
                 }
 
-                for (Trace trace : new MultiThread(original, copy).linearize()) {
+                for (Trace trace : new MultiThread(copy).linearize()) {
                     newTraces.add(trace.pushHead(op));
                 }
             }
@@ -137,23 +132,22 @@
     }
 
     public boolean hasNoIntraThreadPairs() {
-        Multiset<Integer> vars = new HashMultiset<>();
+        BitSet global = new BitSet();
+        BitSet touched = new BitSet();
+
         for (Trace trace : threads) {
-            Set<Integer> touched =
-                    trace.ops().stream()
-                            .map(Op::getVarId)
-                            .collect(Collectors.toSet());
-            touched.forEach(vars::add);
+            BitSet thisThreadTouched = new BitSet();
+            for (Op op : trace.ops()) {
+                int id = op.getVarId();
+                if (touched.get(id)) {
+                    global.set(id);
+                } else {
+                    thisThreadTouched.set(id);
+                }
+            }
+            touched.or(thisThreadTouched);
         }
-
-        for (Integer v : vars.keys()) {
-            if (vars.count(v) == 1) return false;
-        }
-        return true;
-    }
-
-    public boolean isMultiThread() {
-        return threads.size() > 1;
+        return global.equals(touched);
     }
 
     public Set<Result> allResults() {
--- a/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Op.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Op.java	Tue May 24 00:58:53 2016 +0300
@@ -31,26 +31,6 @@
     private final Type type;
     protected final int varId;
 
-    public static Op newLoad(int varId) {
-        return new LoadOp(varId);
-    }
-
-    public static Op newLoad(Op op, Result res) {
-        LoadOp t = new LoadOp(op.getVarId());
-        t.setResult(res);
-        return t;
-    }
-
-    public static Op newStore(int varId) {
-        return new StoreOp(varId);
-    }
-
-    public static Op newStore(Op op, Value value) {
-        StoreOp t = new StoreOp(op.getVarId());
-        t.setValue(value);
-        return t;
-    }
-
     private Op(Type type, int varId) {
         this.type = type;
         this.varId = varId;
@@ -73,16 +53,14 @@
     }
 
     public abstract Result getResult();
-    public abstract void setResult(Result res);
-
     public abstract Value getValue();
-    public abstract void setValue(Value value);
 
     public static class LoadOp extends Op {
-        private Result res;
+        private final Result res;
 
-        public LoadOp(int varId) {
+        public LoadOp(int varId, Result res) {
             super(Type.LOAD, varId);
+            this.res = res;
         }
 
         @Override
@@ -91,21 +69,11 @@
         }
 
         @Override
-        public void setResult(Result res) {
-            this.res = res;
-        }
-
-        @Override
         public Value getValue() {
             throw new UnsupportedOperationException();
         }
 
         @Override
-        public void setValue(Value value) {
-            throw new UnsupportedOperationException();
-        }
-
-        @Override
         public String toString() {
             return "r" + res + " = x" + varId;
         }
@@ -113,10 +81,11 @@
     }
 
     public static class StoreOp extends Op {
-        private Value value;
+        private final Value value;
 
-        public StoreOp(int varId) {
+        public StoreOp(int varId, Value value) {
             super(Type.STORE, varId);
+            this.value = value;
         }
 
         @Override
@@ -125,11 +94,6 @@
         }
 
         @Override
-        public void setResult(Result res) {
-            throw new UnsupportedOperationException();
-        }
-
-        @Override
         public Value getValue() {
             if (value == null) {
                 throw new IllegalStateException("valueId unset");
@@ -138,11 +102,6 @@
         }
 
         @Override
-        public void setValue(Value value) {
-            this.value = value;
-        }
-
-        @Override
         public String toString() {
             return "x" + varId + " = C" + value;
         }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Phase.java	Tue May 24 00:58:53 2016 +0300
@@ -0,0 +1,159 @@
+/*
+ * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.openjdk.jcstress.generator.seqcst;
+
+import org.openjdk.jcstress.util.HashMultimap;
+import org.openjdk.jcstress.util.Multimap;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.stream.Collectors;
+import java.util.stream.LongStream;
+
+class Phase {
+    private static final int TYPES = 2;
+
+    private final int count;
+    private final long cases;
+    private final int threads;
+    private final int vars;
+
+    public Phase(int count, int vars, int threads) {
+        this.count = count;
+        this.vars = vars;
+        this.threads = threads;
+        this.cases = (long) Math.pow(vars * threads * TYPES, count);
+    }
+
+    public List<MultiThread> run() {
+        System.out.printf("Generating test cases for %d ops, %d variable(s), %d thread(s)... %10d testcases to filter... ",
+                count, vars, threads, cases);
+
+        Set<String> canonicalIds = Collections.newSetFromMap(new ConcurrentHashMap<>());
+
+        List<MultiThread> list = LongStream.range(0, cases)
+                .parallel()
+                .filter(this::filterTrace)
+                .mapToObj(ticket -> {
+                    Multimap<Integer, Op> threadOps = generateTrace(ticket);
+                    List<Trace> threads = threadOps.valueGroups().stream()
+                            .map(Trace::new)
+                            .collect(Collectors.toList());
+                    return new MultiThread(threads);
+                })
+                .filter(MultiThread::hasNoSingleLoadThreads)        // single load threads blow up the test case count
+                .filter(MultiThread::hasNoIntraThreadPairs)         // no load-stores within a single thread
+                .filter(mt -> canonicalIds.add(mt.canonicalId()))   // pass only a canonical order of arguments
+                .collect(Collectors.toList());
+
+        System.out.printf("%5d interesting testcases%n", list.size());
+        return list;
+    }
+
+    private Multimap<Integer, Op> generateTrace(long ticket) {
+        Multimap<Integer, Op> result = new HashMultimap<>();
+        int valId = Value.initial();
+        int resId = 1;
+
+        long t = ticket;
+        for (int c = 0; c < count; c++) {
+            int thread = (int) (t % threads);
+            t /= threads;
+
+            int type = (int) (t % TYPES);
+            t /= TYPES;
+
+            int varId = (int) (t % vars);
+            t /= vars;
+
+            Op op;
+            switch (type) {
+                case 0:
+                    Result res = new Result(resId++);
+                    op = new Op.LoadOp(varId, res);
+                    break;
+                case 1:
+                    Value value = Value.newOne(valId++);
+                    op = new Op.StoreOp(varId, value);
+                    break;
+                default:
+                    throw new IllegalStateException();
+            }
+
+            result.put(thread, op);
+        }
+
+        return result;
+    }
+
+    private boolean filterTrace(long ticket) {
+        long usedThreadsMask = 0L;
+        long usedVarsMask = 0L;
+        long storeMask = 0L;
+
+        long t = ticket;
+        for (int c = 0; c < count; c++) {
+            int thread = (int) (t % threads);
+            t /= threads;
+
+            usedThreadsMask |= (1 << thread);
+
+            int type = (int) (t % TYPES);
+            t /= TYPES;
+
+            int varId = (int) (t % vars);
+            t /= vars;
+
+            usedVarsMask |= (1 << varId);
+            switch (type) {
+                case 0:
+                    break;
+                case 1:
+                    storeMask |= (1 << varId);
+                    break;
+                default:
+                    throw new IllegalStateException();
+            }
+        }
+
+        if (t > 0) {
+            throw new IllegalStateException("Unclaimed ticket bits: " + t);
+        }
+
+        // Has loads without stores, bail
+        if (usedVarsMask != storeMask) return false;
+
+        // All vars are used? If not, bail
+        if (usedVarsMask != ((1 << vars) - 1)) return false;
+
+        // All threads are used? If not, bail
+        if (usedThreadsMask != ((1 << threads) - 1)) return false;
+
+        return true;
+    }
+
+}
--- a/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/SeqCstTraceGenerator.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/SeqCstTraceGenerator.java	Tue May 24 00:58:53 2016 +0300
@@ -31,8 +31,6 @@
 import java.io.FileNotFoundException;
 import java.io.PrintWriter;
 import java.util.*;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.stream.Collectors;
 
 public class SeqCstTraceGenerator {
 
@@ -54,114 +52,25 @@
 
     public void generate() {
         /*
-           Step 1. Generate all possible traces from the available ops:
+           Step 1. Distribute load-stores between threads, yielding all possible scenarios.
          */
+        List<MultiThread> multiThreads = new ArrayList<>();
 
-        System.out.print("Generating load/store permutations... ");
+        final int MAX_COUNT = 6;
+        final int MAX_VARS = 3;
+        final int MAX_THREADS = 4;
 
-        List<Trace> allTraces = new ArrayList<>();
-        {
-            List<Op> possibleOps = new ArrayList<>();
-            for (int v = 0; v < 2; v++) {
-                possibleOps.add(Op.newStore(v));
-                possibleOps.add(Op.newLoad(v));
-                possibleOps.add(Op.newLoad(v));
-            }
-
-            List<Trace> traces = Collections.singletonList(new Trace());
-            for (int l = 0; l < possibleOps.size(); l++) {
-                traces = product(traces, possibleOps);
-                allTraces.addAll(traces);
+        for (int count = 1; count <= MAX_COUNT; count++) {
+            for (int vars = 1; vars <= Math.min(MAX_VARS, count); vars++) {
+                for (int threads = Math.max(2, count / 2); threads <= Math.min(MAX_THREADS, count); threads++) {
+                    multiThreads.addAll(new Phase(count, vars, threads).run());
+                }
             }
         }
-
-        {
-            List<Op> possibleOps = new ArrayList<>();
-            for (int v = 0; v < 3; v++) {
-                possibleOps.add(Op.newStore(v));
-                possibleOps.add(Op.newLoad(v));
-            }
-
-            List<Trace> traces = Collections.singletonList(new Trace());
-            for (int l = 0; l < possibleOps.size(); l++) {
-                traces = product(traces, possibleOps);
-                allTraces.addAll(traces);
-            }
-        }
-
-        List<Trace> traces = allTraces;
-        System.out.print(" " + traces.size() + " found... ");
+        System.out.println(multiThreads.size() + " interesting testcases");
 
         /*
-           Step 2. Filter out non-interesting traces.
-         */
-
-        Set<String> canonicalTraces = new HashSet<>();
-        traces = allTraces.stream()
-                .filter(Trace::hasStores)                          // Has modifications to observe
-                .filter(Trace::matchedLoads)                       // All loads have at least one matching store
-                .filter(t -> canonicalTraces.add(t.canonicalId())) // Only a canonical order of vars accepted
-                .collect(Collectors.toList());
-
-        for (Trace trace : traces) {
-            trace.assignResults();
-        }
-
-        System.out.println(traces.size() + " are interesting.");
-
-        /*
-           Step 3. Distribute load-stores between threads, yielding all possible scenarios.
-         */
-        final int THREADS = 4;
-
-        System.out.print("Generating test cases that distribute load/stores among " + THREADS + " threads... ");
-
-        List<MultiThread> multiThreads = new ArrayList<>();
-        for (Trace trace : traces) {
-
-            int len = trace.getLength();
-            int bitsNeeded = 2*len;
-            if (bitsNeeded > 63) {
-                throw new IllegalStateException("Cannot handle large traces like that");
-            }
-
-            long bound = 1 << bitsNeeded;
-
-            for (long c = 0; c < bound; c++) {
-                Map<Integer, List<Op>> newT = new HashMap<>();
-                for (int t = 0; t < THREADS; t++) {
-                    newT.put(t, new ArrayList<>());
-                }
-
-                long ticket = c;
-                for (Op op : trace.ops()) {
-                    int thread = (int)(ticket & 3);
-                    newT.get(thread).add(op);
-                    ticket = ticket >> 2;
-                }
-
-                MultiThread mt = new MultiThread(trace, newT.values().stream().map(Trace::new).collect(Collectors.toList()));
-                multiThreads.add(mt);
-            }
-        }
-        System.out.print(multiThreads.size() + " testcases generated... ");
-
-        /*
-           Step 4. Apply more filters to reduce
-         */
-        Set<String> canonicalIds = Collections.newSetFromMap(new ConcurrentHashMap<>());
-
-        multiThreads = multiThreads.parallelStream()
-                .filter(MultiThread::isMultiThread)               // really have multiple threads
-                .filter(MultiThread::hasNoSingleLoadThreads)      // threads with single loads produce duplicate tests
-                .filter(MultiThread::hasNoIntraThreadPairs)       // has no operations that do not span threads
-                .filter(mt -> canonicalIds.add(mt.canonicalId())) // pass only one canonical
-                .collect(Collectors.toList());
-
-        System.out.println(multiThreads.size() + " interesting.");
-
-        /*
-            Step 5. Figure out what executions are sequentially consistent (needed for grading!),
+            Step 2. Figure out what executions are sequentially consistent (needed for grading!),
             and emit the tests.
          */
 
@@ -201,10 +110,10 @@
                 System.out.print(".");
         }
         System.out.println();
-        System.out.println("Found " + testCount + " interesting test cases");
+        System.out.println("Generated " + testCount + " interesting testcases");
 
         /*
-            Step 6. Check that no important cases were filtered.
+            Step 3. Check that no important cases were filtered.
 
             The nomenclature is derived from Maranget, Sarkar, Sewell,
               "A Tutorial Introduction to the ARM and POWER Relaxed Memory Models"
--- a/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Trace.java	Mon May 23 17:12:38 2016 +0300
+++ b/jcstress-test-gen/src/main/java/org/openjdk/jcstress/generator/seqcst/Trace.java	Tue May 24 00:58:53 2016 +0300
@@ -65,14 +65,9 @@
     }
 
     public TraceResult interpret() {
-        int vars = 0;
+        Map<Integer, Value> values = new HashMap<>();
         for (Op op : ops) {
-            vars = Math.max(vars, op.getVarId());
-        }
-
-        Map<Integer, Value> values = new HashMap<>();
-        for (int v = 0; v <= vars; v++) {
-            values.put(v, Value.defaultOne());
+            values.put(op.getVarId(), Value.defaultOne());
         }
 
         SortedMap<Result, Value> resValues = new TreeMap<>();
@@ -167,87 +162,4 @@
         return sb.toString();
     }
 
-    public String canonicalId() {
-        int varId = 0;
-        Map<Integer, Integer> varMap = new HashMap<>();
-        for (Op op : ops) {
-            Integer id = varMap.get(op.getVarId());
-            if (id == null) {
-                id = varId++;
-                varMap.put(op.getVarId(), id);
-            }
-        }
-
-        StringBuilder sb = new StringBuilder();
-        for (Op op : ops) {
-            switch (op.getType()) {
-                case LOAD:
-                    sb.append("L");
-                    break;
-                case STORE:
-                    sb.append("S");
-                    break;
-                default:
-                    throw new IllegalStateException();
-            }
-            sb.append(varMap.get(op.getVarId()) + 1);
-            sb.append("_");
-        }
-        return sb.toString();
-    }
-
-    public boolean matchedLoadStores() {
-        Set<Integer> loads = new HashSet<>();
-        Set<Integer> stores = new HashSet<>();
-        for (Op op : ops) {
-            switch (op.getType()) {
-                case STORE:
-                    stores.add(op.getVarId());
-                    break;
-                case LOAD:
-                    loads.add(op.getVarId());
-                    break;
-            }
-        }
-
-        return loads.equals(stores);
-    }
-
-    public boolean matchedLoads() {
-        Set<Integer> loads = new HashSet<>();
-        Set<Integer> stores = new HashSet<>();
-        for (Op op : ops) {
-            switch (op.getType()) {
-                case STORE:
-                    stores.add(op.getVarId());
-                    loads.add(op.getVarId());
-                    break;
-                case LOAD:
-                    loads.add(op.getVarId());
-                    break;
-            }
-        }
-
-        return loads.equals(stores);
-    }
-
-    public void assignResults() {
-        int valId = Value.initial();
-        int resId = 1;
-        for (int c = 0; c < ops.size(); c++) {
-            Op op = ops.get(c);
-            switch (op.getType()) {
-                case LOAD: {
-                    ops.set(c, Op.newLoad(op, new Result(resId++)));
-                    break;
-                }
-                case STORE: {
-                    ops.set(c, Op.newStore(op, Value.newOne(valId++)));
-                    break;
-                }
-                default:
-                    throw new IllegalStateException();
-            }
-        }
-    }
 }