# HG changeset patch
# User brutisso
# Date 1309263807 -7200
# Node ID 04760e41b01e9dc7a54a4f71cc7c8e50ce555e1a
# Parent  5f6f2615433a9682c393b902bb7719eb41781428
7016112: CMS: crash during promotion testing
Summary: Also reviewed by mikael.gerdin@oracle.com; stdlib:qsort() does byte-by-byte swapping on Windows. This leads to pointer shearing. Fix is to implement a quicksort that does full pointer updates.
Reviewed-by: never, coleenp, ysr

diff -r 5f6f2615433a -r 04760e41b01e src/share/vm/oops/methodOop.cpp
--- a/src/share/vm/oops/methodOop.cpp	Fri Jun 24 12:38:49 2011 -0400
+++ b/src/share/vm/oops/methodOop.cpp	Tue Jun 28 14:23:27 2011 +0200
@@ -49,6 +49,7 @@
 #include "runtime/relocator.hpp"
 #include "runtime/sharedRuntime.hpp"
 #include "runtime/signature.hpp"
+#include "utilities/quickSort.hpp"
 #include "utilities/xmlstream.hpp"
 
 
@@ -1204,41 +1205,6 @@
   if (WizardMode) signature()->print_symbol_on(st);
 }
 
-
-extern "C" {
-  static int method_compare(methodOop* a, methodOop* b) {
-    return (*a)->name()->fast_compare((*b)->name());
-  }
-
-  // Prevent qsort from reordering a previous valid sort by
-  // considering the address of the methodOops if two methods
-  // would otherwise compare as equal.  Required to preserve
-  // optimal access order in the shared archive.  Slower than
-  // method_compare, only used for shared archive creation.
-  static int method_compare_idempotent(methodOop* a, methodOop* b) {
-    int i = method_compare(a, b);
-    if (i != 0) return i;
-    return ( a < b ? -1 : (a == b ? 0 : 1));
-  }
-
-  // We implement special compare versions for narrow oops to avoid
-  // testing for UseCompressedOops on every comparison.
-  static int method_compare_narrow(narrowOop* a, narrowOop* b) {
-    methodOop m = (methodOop)oopDesc::load_decode_heap_oop(a);
-    methodOop n = (methodOop)oopDesc::load_decode_heap_oop(b);
-    return m->name()->fast_compare(n->name());
-  }
-
-  static int method_compare_narrow_idempotent(narrowOop* a, narrowOop* b) {
-    int i = method_compare_narrow(a, b);
-    if (i != 0) return i;
-    return ( a < b ? -1 : (a == b ? 0 : 1));
-  }
-
-  typedef int (*compareFn)(const void*, const void*);
-}
-
-
 // This is only done during class loading, so it is OK to assume method_idnum matches the methods() array
 static void reorder_based_on_method_index(objArrayOop methods,
                                           objArrayOop annotations,
@@ -1262,6 +1228,14 @@
   }
 }
 
+// Comparer for sorting an object array containing
+// methodOops.
+template <class T>
+static int method_comparator(T a, T b) {
+  methodOop m = (methodOop)oopDesc::decode_heap_oop_not_null(a);
+  methodOop n = (methodOop)oopDesc::decode_heap_oop_not_null(b);
+  return m->name()->fast_compare(n->name());
+}
 
 // This is only done during class loading, so it is OK to assume method_idnum matches the methods() array
 void methodOopDesc::sort_methods(objArrayOop methods,
@@ -1284,30 +1258,19 @@
         m->set_method_idnum(i);
       }
     }
-
-    // Use a simple bubble sort for small number of methods since
-    // qsort requires a functional pointer call for each comparison.
-    if (length < 8) {
-      bool sorted = true;
-      for (int i=length-1; i>0; i--) {
-        for (int j=0; j<i; j++) {
-          methodOop m1 = (methodOop)methods->obj_at(j);
-          methodOop m2 = (methodOop)methods->obj_at(j+1);
-          if ((uintptr_t)m1->name() > (uintptr_t)m2->name()) {
-            methods->obj_at_put(j, m2);
-            methods->obj_at_put(j+1, m1);
-            sorted = false;
-          }
-        }
-        if (sorted) break;
-          sorted = true;
+    {
+      No_Safepoint_Verifier nsv;
+      if (UseCompressedOops) {
+        QuickSort::sort<narrowOop>((narrowOop*)(methods->base()), length, method_comparator<narrowOop>, idempotent);
+      } else {
+        QuickSort::sort<oop>((oop*)(methods->base()), length, method_comparator<oop>, idempotent);
       }
-    } else {
-      compareFn compare =
-        (UseCompressedOops ?
-         (compareFn) (idempotent ? method_compare_narrow_idempotent : method_compare_narrow):
-         (compareFn) (idempotent ? method_compare_idempotent : method_compare));
-      qsort(methods->base(), length, heapOopSize, compare);
+      if (UseConcMarkSweepGC) {
+        // For CMS we need to dirty the cards for the array
+        BarrierSet* bs = Universe::heap()->barrier_set();
+        assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt");
+        bs->write_ref_array(methods->base(), length);
+      }
     }
 
     // Sort annotations if necessary
diff -r 5f6f2615433a -r 04760e41b01e src/share/vm/prims/jni.cpp
--- a/src/share/vm/prims/jni.cpp	Fri Jun 24 12:38:49 2011 -0400
+++ b/src/share/vm/prims/jni.cpp	Tue Jun 28 14:23:27 2011 +0200
@@ -3296,6 +3296,19 @@
   return ret;
 }
 
+#ifndef PRODUCT
+
+#include "utilities/quickSort.hpp"
+
+void execute_internal_vm_tests() {
+  if (ExecuteInternalVMTests) {
+    assert(QuickSort::test_quick_sort(), "test_quick_sort failed");
+    tty->print_cr("All tests passed");
+  }
+}
+
+#endif
+
 HS_DTRACE_PROBE_DECL3(hotspot_jni, CreateJavaVM__entry, vm, penv, args);
 DT_RETURN_MARK_DECL(CreateJavaVM, jint);
 
@@ -3386,6 +3399,7 @@
   }
 
   NOT_PRODUCT(test_error_handler(ErrorHandlerTest));
+  NOT_PRODUCT(execute_internal_vm_tests());
   return result;
 }
 
diff -r 5f6f2615433a -r 04760e41b01e src/share/vm/runtime/globals.hpp
--- a/src/share/vm/runtime/globals.hpp	Fri Jun 24 12:38:49 2011 -0400
+++ b/src/share/vm/runtime/globals.hpp	Tue Jun 28 14:23:27 2011 +0200
@@ -1944,6 +1944,9 @@
           "Number of ObjArray elements to push onto the marking stack"      \
           "before pushing a continuation entry")                            \
                                                                             \
+  notproduct(bool, ExecuteInternalVMTests, false,                           \
+          "Enable execution of internal VM tests.")                         \
+                                                                            \
   product_pd(bool, UseTLAB, "Use thread-local object allocation")           \
                                                                             \
   product_pd(bool, ResizeTLAB,                                              \
diff -r 5f6f2615433a -r 04760e41b01e src/share/vm/utilities/quickSort.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/utilities/quickSort.cpp	Tue Jun 28 14:23:27 2011 +0200
@@ -0,0 +1,218 @@
+/*
+ * Copyright (c) 2011, 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.
+ *
+ * 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.
+ *
+ */
+
+#include "precompiled.hpp"
+#include "utilities/quickSort.hpp"
+
+#ifndef PRODUCT
+
+// Unit tests
+
+#include "runtime/os.hpp"
+#include <stdlib.h>
+
+static int test_comparator(int a, int b) {
+  if (a == b) {
+    return 0;
+  }
+  if (a < b) {
+    return -1;
+  }
+  return 1;
+}
+
+static int test_even_odd_comparator(int a, int b) {
+  bool a_is_odd = (a % 2) == 1;
+  bool b_is_odd = (b % 2) == 1;
+  if (a_is_odd == b_is_odd) {
+    return 0;
+  }
+  if (a_is_odd) {
+    return -1;
+  }
+  return 1;
+}
+
+static int test_stdlib_comparator(const void* a, const void* b) {
+  int ai = *(int*)a;
+  int bi = *(int*)b;
+  if (ai == bi) {
+    return 0;
+  }
+  if (ai < bi) {
+    return -1;
+  }
+  return 1;
+}
+
+void QuickSort::print_array(const char* prefix, int* array, int length) {
+  tty->print("%s:", prefix);
+  for (int i = 0; i < length; i++) {
+    tty->print(" %d", array[i]);
+  }
+  tty->print_cr("");
+}
+
+bool QuickSort::compare_arrays(int* actual, int* expected, int length) {
+  for (int i = 0; i < length; i++) {
+    if (actual[i] != expected[i]) {
+      print_array("Sorted array  ", actual, length);
+      print_array("Expected array", expected, length);
+      return false;
+    }
+  }
+  return true;
+}
+
+template <class C>
+bool QuickSort::sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent) {
+  sort<int, C>(arrayToSort, length, comparator, idempotent);
+  return compare_arrays(arrayToSort, expectedResult, length);
+}
+
+bool QuickSort::test_quick_sort() {
+  tty->print_cr("test_quick_sort\n");
+  {
+    int* test_array = NULL;
+    int* expected_array = NULL;
+    assert(sort_and_compare(test_array, expected_array, 0, test_comparator), "Empty array not handled");
+  }
+  {
+    int test_array[] = {3};
+    int expected_array[] = {3};
+    assert(sort_and_compare(test_array, expected_array, 1, test_comparator), "Single value array not handled");
+  }
+  {
+    int test_array[] = {3,2};
+    int expected_array[] = {2,3};
+    assert(sort_and_compare(test_array, expected_array, 2, test_comparator), "Array with 2 values not correctly sorted");
+  }
+  {
+    int test_array[] = {3,2,1};
+    int expected_array[] = {1,2,3};
+    assert(sort_and_compare(test_array, expected_array, 3, test_comparator), "Array with 3 values not correctly sorted");
+  }
+  {
+    int test_array[] = {4,3,2,1};
+    int expected_array[] = {1,2,3,4};
+    assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "Array with 4 values not correctly sorted");
+  }
+  {
+    int test_array[] = {7,1,5,3,6,9,8,2,4,0};
+    int expected_array[] = {0,1,2,3,4,5,6,7,8,9};
+    assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Array with 10 values not correctly sorted");
+  }
+  {
+    int test_array[] = {4,4,1,4};
+    int expected_array[] = {1,4,4,4};
+    assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "3 duplicates not sorted correctly");
+  }
+  {
+    int test_array[] = {0,1,2,3,4,5,6,7,8,9};
+    int expected_array[] = {0,1,2,3,4,5,6,7,8,9};
+    assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Already sorted array not correctly sorted");
+  }
+  {
+    // one of the random arrays that found an issue in the partion method.
+    int test_array[] = {76,46,81,8,64,56,75,11,51,55,11,71,59,27,9,64,69,75,21,25,39,40,44,32,7,8,40,41,24,78,24,74,9,65,28,6,40,31,22,13,27,82};
+    int expected_array[] = {6,7,8,8,9,9,11,11,13,21,22,24,24,25,27,27,28,31,32,39,40,40,40,41,44,46,51,55,56,59,64,64,65,69,71,74,75,75,76,78,81,82};
+    assert(sort_and_compare(test_array, expected_array, 42, test_comparator), "Not correctly sorted");
+  }
+  {
+    int test_array[] = {2,8,1,4};
+    int expected_array[] = {1,4,2,8};
+    assert(sort_and_compare(test_array, expected_array, 4, test_even_odd_comparator), "Even/odd not sorted correctly");
+  }
+  {  // Some idempotent tests
+    {
+      // An array of lenght 3 is only sorted by find_pivot. Make sure that it is idempotent.
+      int test_array[] = {1,4,8};
+      int expected_array[] = {1,4,8};
+      assert(sort_and_compare(test_array, expected_array, 3, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {1,7,9,4,8,2};
+      int expected_array[] = {1,7,9,4,8,2};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {1,9,7,4,2,8};
+      int expected_array[] = {1,9,7,4,2,8};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {7,9,1,2,8,4};
+      int expected_array[] = {7,9,1,2,8,4};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {7,1,9,2,4,8};
+      int expected_array[] = {7,1,9,2,4,8};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {9,1,7,4,8,2};
+      int expected_array[] = {9,1,7,4,8,2};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+    {
+      int test_array[] = {9,7,1,4,2,8};
+      int expected_array[] = {9,7,1,4,2,8};
+      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
+    }
+  }
+
+  // test sorting random arrays
+  for (int i = 0; i < 1000; i++) {
+    int length = os::random() % 100;
+    int* test_array = new int[length];
+    int* expected_array = new int[length];
+    for (int j = 0; j < length; j++) {
+        // Choose random values, but get a chance of getting duplicates
+        test_array[j] = os::random() % (length * 2);
+        expected_array[j] = test_array[j];
+    }
+
+    // Compare sorting to stdlib::qsort()
+    qsort(expected_array, length, sizeof(int), test_stdlib_comparator);
+    assert(sort_and_compare(test_array, expected_array, length, test_comparator), "Random array not correctly sorted");
+
+    // Make sure sorting is idempotent.
+    // Both test_array and expected_array are sorted by the test_comparator.
+    // Now sort them once with the test_even_odd_comparator. Then sort the
+    // test_array one more time with test_even_odd_comparator and verify that
+    // it is idempotent.
+    sort(expected_array, length, test_even_odd_comparator, true);
+    sort(test_array, length, test_even_odd_comparator, true);
+    assert(compare_arrays(test_array, expected_array, length), "Sorting identical arrays rendered different results");
+    sort(test_array, length, test_even_odd_comparator, true);
+    assert(compare_arrays(test_array, expected_array, length), "Sorting already sorted array changed order of elements - not idempotent");
+
+    delete[] test_array;
+    delete[] expected_array;
+  }
+  return true;
+}
+
+#endif
diff -r 5f6f2615433a -r 04760e41b01e src/share/vm/utilities/quickSort.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/utilities/quickSort.hpp	Tue Jun 28 14:23:27 2011 +0200
@@ -0,0 +1,138 @@
+/*
+ * Copyright (c) 2011, 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.
+ *
+ * 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.
+ *
+ */
+
+#ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP
+#define SHARE_VM_UTILITIES_QUICKSORT_HPP
+
+#include "memory/allocation.hpp"
+#include "runtime/globals.hpp"
+#include "utilities/debug.hpp"
+
+class QuickSort : AllStatic {
+
+ private:
+  template<class T>
+  static void swap(T* array, int x, int y) {
+    T tmp = array[x];
+    array[x] = array[y];
+    array[y] = tmp;
+  }
+
+  // As pivot we use the median of the first, last and middle elements.
+  // We swap in these three values at the right place in the array. This
+  // means that this method not only returns the index of the pivot
+  // element. It also alters the array so that:
+  //     array[first] <= array[middle] <= array[last]
+  // A side effect of this is that arrays of length <= 3 are sorted.
+  template<class T, class C>
+  static int find_pivot(T* array, int length, C comparator) {
+    assert(length > 1, "length of array must be > 0");
+
+    int middle_index = length / 2;
+    int last_index = length - 1;
+
+    if (comparator(array[0], array[middle_index]) == 1) {
+      swap(array, 0, middle_index);
+    }
+    if (comparator(array[0], array[last_index]) == 1) {
+      swap(array, 0, last_index);
+    }
+    if (comparator(array[middle_index], array[last_index]) == 1) {
+      swap(array, middle_index, last_index);
+    }
+    // Now the value in the middle of the array is the median
+    // of the fist, last and middle values. Use this as pivot.
+    return middle_index;
+  }
+
+  template<class T, class C, bool idempotent>
+  static int partition(T* array, int pivot, int length, C comparator) {
+    int left_index = -1;
+    int right_index = length;
+    T pivot_val = array[pivot];
+
+    while (true) {
+      do {
+        left_index++;
+      } while (comparator(array[left_index], pivot_val) == -1);
+      do {
+        right_index--;
+      } while (comparator(array[right_index], pivot_val) == 1);
+
+      if (left_index < right_index) {
+        if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
+          swap(array, left_index, right_index);
+        }
+      } else {
+        return right_index;
+      }
+    }
+
+    ShouldNotReachHere();
+    return 0;
+  }
+
+  template<class T, class C, bool idempotent>
+  static void inner_sort(T* array, int length, C comparator) {
+    if (length < 2) {
+      return;
+    }
+    int pivot = find_pivot(array, length, comparator);
+    if (length < 4) {
+      // arrays up to length 3 will be sorted after finding the pivot
+      return;
+    }
+    int split = partition<T, C, idempotent>(array, pivot, length, comparator);
+    int first_part_length = split + 1;
+    inner_sort<T, C, idempotent>(array, first_part_length, comparator);
+    inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator);
+  }
+
+ public:
+  // The idempotent parameter prevents the sort from
+  // reordering a previous valid sort by not swapping
+  // fields that compare as equal. This requires extra
+  // calls to the comparator, so the performance
+  // impact depends on the comparator.
+  template<class T, class C>
+  static void sort(T* array, int length, C comparator, bool idempotent) {
+    // Switch "idempotent" from function paramter to template parameter
+    if (idempotent) {
+      inner_sort<T, C, true>(array, length, comparator);
+    } else {
+      inner_sort<T, C, false>(array, length, comparator);
+    }
+  }
+
+  // for unit testing
+#ifndef PRODUCT
+  static void print_array(const char* prefix, int* array, int length);
+  static bool compare_arrays(int* actual, int* expected, int length);
+  template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false);
+  static bool test_quick_sort();
+#endif
+};
+
+
+#endif //SHARE_VM_UTILITIES_QUICKSORT_HPP