Add "killer" input from "algorithmic complexity attacks and libc

qsort()".  This causes quadratic behavior with the 4.4BSD qsort's
"switch to insertion sort" optimization when the input appears to
be mostly sorted.  That optimization was removed in qsort.c r1.12
but it is worth having in the regress test too.

1 files changed, 12 insertions, 0 deletions

diff --git a/src/regress/lib/libc/qsort/qsort_test.c b/src/regress/lib/libc/qsort/qsort_test.c
index f78137504a..b23f3e6190 100644
--- a/src/regress/lib/libc/qsort/qsort_test.c
+++ b/src/regress/lib/libc/qsort/qsort_test.c
@@ -24,6 +24,8 @@
 /*
  * Test program based on Bentley & McIlroy's "Engineering a Sort Function".
  * Uses heapsort(3) to check the results.
+ * The "killer" input is from:
+ *  http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
  */
 
 enum distribution {
@@ -32,6 +34,7 @@ enum distribution {
     STAGGER,
     PLATEAU,
     SHUFFLE,
+    KILLER,
     INVALID
 };
 
@@ -106,6 +109,15 @@ fill_test_array(int *x, int n, int dist, int m)
                 case SHUFFLE:
                         x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2);
                         break;
+                case KILLER:
+                        k = n / 2;
+                        if (i < k)
+                                x[i] = k - i;
+                        else if (i > k)
+                                x[i] = n + k + 1 - i;
+                        else
+                                x[i] = k + 1;
+                        break;
                 default:
                         err(1, "unexpected distribution %d", dist);
                 }