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

1 files changed, 138 insertions, 0 deletions

diff --git a/src/share/vm/utilities/quickSort.hpp b/src/share/vm/utilities/quickSort.hpp
new file mode 100644
index 000000000..17eaf4693
--- /dev/null
+++ b/src/share/vm/utilities/quickSort.hpp
@@ -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