March 2011 - core-libs-dev

Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
by Vladimir Yaroslavskiy 27 Feb '16

27 Feb '16

Hello All, I'd like to share with you new Dual-Pivot Quicksort which is faster than the known implementations (theoretically and experimental). I'd like to propose to replace the JDK's Quicksort implementation by new one. Description ----------- The classical Quicksort algorithm uses the following scheme: 1. Pick an element P, called a pivot, from the array. 2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot element is in its final position. 3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements. The invariant of classical Quicksort is: [ <= p | >= p ] There are several modifications of the schema: [ < p | = p | > p ] or [ = p | < p | > p | = p ] But all of them use *one* pivot. The new Dual-Pivot Quicksort uses *two* pivots elements in this manner: 1. Pick an elements P1, P2, called pivots from the array. 2. Assume that P1 <= P2, otherwise swap it. 3. Reorder the array into three parts: those less than the smaller pivot, those larger than the larger pivot, and in between are those elements between (or equal to) the two pivots. 4. Recursively sort the sub-arrays. The invariant of the Dual-Pivot Quicksort is: [ < P1 | P1 <= & <= P2 } > P2 ] The new Quicksort is faster than current implementation of Quicksort in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort. The full description of the Dual-Pivot Quicksort you can find on my page: http://iaroslavski.narod.ru/quicksort Performance tests ----------------- Here is result of running on different types of input data: Client VM all 85% organ 0..1 0..4 random ascend descend equal equal pipes random 010101 random Dual-Pivot: 16.83 5.31 5.47 0.35 0.68 10.59 1.06 1.02 2.18 Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49 Server VM all 85% organ 0..1 0..4 random ascend descend equal equal pipes random 010101 random Dual-Pivot: 23.94 6.68 6.63 0.43 0.62 17.14 1.42 1.96 3.41 Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39 The a lot of other tests have been run under client and server mode. The most interesting is BentleyBasher test framework. It runs battery of tests for all cases: { 100, 1000, 10000, 1000000 } x { sawtooth, rand, stagger, plateau, shuffle } x { ident, reverse, reverse_front, reverse_back, sort, dither} where 100, ... , 1000000 - array length sawtooth: x[i] =i%m rand: x[i] = rand() % m stagger: x[i] = (i*m + i) % n plateau: x[i] = min(i, m) shuffle: x[i] = rand()%m? (j+=2): (k+=2) ident(x) - a copy of x reverse(x, 0, n) - reversed copy reverse_front(x, 0, n/2) - front half reversed reverse_back(x, n/2, n) - back half reversed sort(x) - an ordered copy dither(x) - add i%5 to x[i] Here is the result of execution: Server VM: http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html Client VM: http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&… Mathematical investigations --------------------------- It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. Diff between current and new implementation of Quicksort -------------------------------------------------------- Here is the link to the diff for java.util.Arrays class: http://cr.openjdk.java.net/~alanb/6880672/webrev.00 If you like to look and play with new algorithm, please, take attached class DualPivotQuicksort.java Feedback -------- Also I'd like to share a feedback from Joshua Bloch and Jon Bentley who spent a lot of time investigating this algorithm, who gave me many advices and tips how to make new Quicksort better. -------- Original Message -------- Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7 Date: Thu, 10 Sep 2009 07:20:11 -0700 From: Joshua Bloch <jjb(a)google.com> Jon also says that Vladimir should make every reasonable improvement to the basic method before checking in the code. In his words, "It would be horrible to put the new code into the library, and then have someone else come along and speed it up by another 20% by using standard techniques." I believe it's not unlikely that this code may end up getting ported to many languages and widely deployed in much the manner of Bentley and McIlroy's fine sort (which is nearing 20 successful years in the field). Jon will help Vladimir do this. -------- Original Message -------- Subject: Dual-Pivot Quicksort: Next Steps Date: Wed, 09 Sep 2009 15:02:25 -0400 From: Jon Bentley <jbentley(a)avaya.com> Vladimir, Josh, I *finally* feel like I understand what is going on. Now that I (think that) I see it, it seems straightforward and obvious. Tony Hoare developed Quicksort in the early 1960s. I was very proud to make minor contributions to a particularly clean (binary) quicksort in the mid 1980s, to a relatively straightforward, industrial strength Quicksort with McIlroy in the early 1990s, and then to algorithms and data structures for strings with Sedgewick in the mid 1990s. I think that Vladimir's contributions to Quicksort go way beyond anything that I've ever done, and rank up there with Hoare's original design and Sedgewick's analysis. I feel so privileged to play a very, very minor role in helping Vladimir with the most excellent work! ----------------------------------------------- Let me know, if you have any questions/comments. Thank you, Vladimir Here is the details between steps (1) and (2) in the case of Dual-Pivot Quicksort: ----------------------------------------------------------------------------- >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = 1 + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + 1*i + C_{j-i-1} + 2*(j-i- 1) + C_{n-j-1} + 2*(n-j-1)} Equation (1) means that total number is the sum of the comparison numbers of all cases of partitions into 3 parts plus number of comparisons for elements from left part (one comparison), center and right parts (2 comparisons). !!! It can be rewritten in other way: !!! (2) C_n = 1 + R*(n-2) + 2/(n(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} where R is the average number of comparisons during one iteration. This constant R can be found as average value (1 + 2 + 2) / 3 = 5/3 ~ 1.6666. ----------------------------------------------------------------------------- How it can be rewritten: We should show that 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i + 2*(j-i- 1) + 2*(n-j-1)} equals to 5/3 * (n-2). Let's consider the double sum: sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i + 2*(j-i- 1) + 2*(n-j-1)} = = sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {2*n - 4} - sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i} = = 2*(n-2)*sum_{i=0}^{n-2} {n-1-i} - sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i} = = 2*(n-2)*((n-1)^2 - (n-1)*(n-2)/2) - (n-1)*sum_{i=0}^{n-2} {i} + sum_{i=0}^{n-2} {i*i} = ------------------------------------------------------------------ here we use the property: sum_{k=1}{n} {k^2} = n^3/3 + n^2/2 + n/6 ------------------------------------------------------------------ = 2*(n-2)*((n-1)^2 - (n-1)*(n-2)/2) - (n-1)*(n-1)*(n-2)/2 + (n-2)^3/3 + (n-2)^2/2 + (n-2)/6 = = 1/6 * (12*(n-1)^2*(n-2) - 6*(n-1)*(n-2)^2 - 3*(n-1)^2*(n-2) + 2*(n-2)^3 + 3*(n-2)^2 + (n-2)) = = 1/6 * (3*(n-1)*(n-2)*(3*(n-1) - 2*(n-2)) + (n-2)*(2*(n-2)^2 + 3*(n-2) + 1))) = = 1/6 * (3*(n-1)*(n-2)*(n+1) + (n-2)*(2*n^2 - 5*n + 3)) = = 1/6 * (n-2)*(5*n^2 - 5*n) = 5/6 * n*(n-1)*(n-2) Substitute the result into equation (1): (1.1) C_n = 1 + 2/(n*(n-1)) * 5/6 * n*(n-1)*(n-2) + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} or (1.2) C_n = 1 + 5/3*(n-2) + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} We see that (1.2) is same as (2). /** * @author Vladimir Yaroslavskiy * @version 2009.09.10 m765 */ public class DualPivotQuicksort { public static void sort(int[] a) { sort(a, 0, a.length); } public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); dualPivotQuicksort(a, fromIndex, toIndex - 1, 3); } private static void rangeCheck(int length, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > length) { throw new ArrayIndexOutOfBoundsException(toIndex); } } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } private static void dualPivotQuicksort(int[] a, int left, int right, int div) { int len = right - left; if (len < 27) { // insertion sort for tiny array for (int i = left + 1; i <= right; i++) { for (int j = i; j > left && a[j] < a[j - 1]; j--) { swap(a, j, j - 1); } } return; } int third = len / div; // "medians" int m1 = left + third; int m2 = right - third; if (m1 <= left) { m1 = left + 1; } if (m2 >= right) { m2 = right - 1; } if (a[m1] < a[m2]) { swap(a, m1, left); swap(a, m2, right); } else { swap(a, m1, right); swap(a, m2, left); } // pivots int pivot1 = a[left]; int pivot2 = a[right]; // pointers int less = left + 1; int great = right - 1; // sorting for (int k = less; k <= great; k++) { if (a[k] < pivot1) { swap(a, k, less++); } else if (a[k] > pivot2) { while (k < great && a[great] > pivot2) { great--; } swap(a, k, great--); if (a[k] < pivot1) { swap(a, k, less++); } } } // swaps int dist = great - less; if (dist < 13) { div++; } swap(a, less - 1, left); swap(a, great + 1, right); // subarrays dualPivotQuicksort(a, left, less - 2, div); dualPivotQuicksort(a, great + 2, right, div); // equal elements if (dist > len - 13 && pivot1 != pivot2) { for (int k = less; k <= great; k++) { if (a[k] == pivot1) { swap(a, k, less++); } else if (a[k] == pivot2) { swap(a, k, great--); if (a[k] == pivot1) { swap(a, k, less++); } } } } // subarray if (pivot1 < pivot2) { dualPivotQuicksort(a, less, great, div); } } } At first consider the classic Quicksort scheme and find the average number of comparisons and swaps for it. We assume that input data is random permutation of n numbers from the range [1..n]. Classic Quicksort ================= 1. Choose a pivot element (take random), 2. Compare each (n-1) elements with the pivot 3. and swap it, if necessary, to have the partitions: [ <= pivot | >= pivot ] 4. Sort recursively left and right parts. >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = (n-1) + 1/n * sum_{k=0}^{n-1} {C_k + C_{n-k-1}} and last sum can be rewritten: (2) C_n = (n-1) + 2/n * sum_{k=0}^{n-1} C_k Write formula (2) for n+1: (3) C_{n+1} = n + 2/(n+1) * sum_{k=0}^{n} C_k Multiply (2) by n and (3) by (n+1) and subtract one from other, we have: (4) (n+1)*C_{n+1} - n*C_n = 2*n + 2*C_n Sorting an array of n elements may be considered as selecting one permutation of the n elements among all possible permutations. The number of possible permutations of n elements is n!, so the task for any sorting algorithm is to determine the one permutation out of n! possibilities. The minimum number of operations (swap and comparisons) for sorting n elements is const*ln(n!). >From the Stirling's formula the approximation of the number of operations is A*n*ln(n) + B*n + C, where A, B and C are constant coefficients. The coefficients B and C are not important for large n. Therefore, the function C_n may be approximated by the equation: (5) C_n = A*n*ln(n) The function C_n is substituted from equation (5) into equation (4), which yields the following equation: (6) (n+1)*A*(n+1)*ln(n+1) - n*A*n*ln(n) = 2*n + 2*A*n*ln(n) Using the properties of logarithms, equation (6) can then be reduced to: (7) n*ln(1+1/n) + 2*ln(1+1/n) + (1/n) * ln(n+1) = 2/A Using a property of logarithm: ln(1 + x) -> x, if x -> 0, and other property: ln(n) / n -> 0, when n -> +oo, equation (7) will be approximated by: (8) 1 + 0 + 0 = 2/A So, the coefficient A is equal to 2 and the average number of comparisons in sorting of n size arrays is (9) C_n = 2*n*ln(n). To find the approximation of the average number of swaps, we use the similar approach as in the case of comparisons. The average number of swaps S_n as a function of the number of elements may be represented by the equation: (10) S_n = 1/2*(n-1) + 2/n * sum_{k=0}^{n-1} S_k We assume that average number of swaps during one iteration is 1/2*(n-1). It means that in average one half of elements is swapped only. Using the same approach, we find that the coefficient A equals to 1. Therefore, the function S_n may be approximated by the equation: (11) S_n = n*ln(n) ------------------------------------------------------------------------------- Now consider the Dual-Pivot Quicksort scheme and find the average number of comparisons and swaps for it. We assume that input data is random permutation of n numbers from the range [1..n]. Dual-Pivot Quicksort ==================== 1. Choose 2 pivot elements pivot1 and pivot2 (take random), 2. pivot1 must be less or equal than pivot2, otherwise they are swapped 3. Compare each (n-2) elements with the pivots 4. and swap it, if necessary, to have the partitions: [ <= p1 | p1 <= & <= p2 | >= p2 ] 5. Sort recursively left, center and right parts. >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = 1 + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + 1*i + C_{j-i-1} + 2*(j-i-1) + C_{n-j-1} + 2*(n-j-1)} Equation (1) means that total number is the sum of the comparison numbers of all cases of partitions into 3 parts plus number of comparisons for elements from left part (one comparison), center and right parts (2 comparisons). It can be rewritten in other way: (2) C_n = 1 + R*(n-2) + 2/(n(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} where R is the average number of comparisons during one iteration. This constant R can be found as average value (1 + 2 + 2) / 3 = 5/3, which means that elements from left part are required only one comparison, and elements form center and right parts - two comparisons. The double sum in equation (2) can be reduced: (3) C_n = 1 + 5/3*(n-2) + 2/(n*(n-1)) * sum_{k=0}^{n-2} {3 * (n-k-1) * C_k} Denote 1 + 5/3*(n-2) by f_n and multiply to n*(n-1): (4) n*(n-1)*C_n = n*(n-1)*f_n + 6 * sum_{k=0}^{n-2} {(n-k-1) * C_k} Write formula (4) for n+1: (5) n*(n+1)*C_{n+1} = n*(n+1)*f_n + 6 * sum_{k=0}^{n-1} {(n-k) * C_k} Subtract (4) from (5), we have: (6) n*(n+1)*C_{n+1} - n*(n-1)*C_n = n*(n+1)*f_n - n*(n-1)*f_n + 6 * sum_{k=0}^{n-2} C_k + 6*C_{n-1} Denote n*(n+1)*C_{n+1} - n*(n-1)*C_n by X_n and n*(n+1)*f_n - n*(n-1)*f_n by F_n: (7) X_n = F_n + 6 * sum_{k=0}^{n-2} C_k + 6*C_{n-1} Write formula (7) for n+1: (8) X_{n+1} = F_{n+1} + 6 * sum_{k=0}^{n-1} C_k + 6*C_n Subtract (7) from (8), we have: (9) X_{n+1} - X_n = F_{n+1} - F_n + 6*C_n Resolving of F_{n+1} - F_n gives: (10) X_{n+1} - X_n = 2 + 10*n + 6*C_n The function X_n is substituted into equation (10), which yields the following equation: (11) (n+1)*(n+2)C_{n+2} -2*n(n+1)*C_{n+1} + (n*(n-1) - 6)*C_n = 2 + 10*n We will find the function C_n approximated by the equation: (12) C_n = A*n*ln(n) The function C_n is substituted from equation (12) into equation (11), which yields the following equation: (13) (n^3+5*n^2+8*n+4)*ln(n+2) - (2*n^3+4*n^2+2*n)*ln(n+1) + (n^3-n^2-6*n)*ln(n) = (10*n+2) / A Using the properties of logarithms, equation (13) can then be reduced to: (14) n^3*(ln(n+2)-2*ln(n+1)+ln(n)) + n^2*(5*ln(n+2)-4*ln(n+1)-ln(n)) + n*(8*ln(n+2)-2*ln(n+1)-6*ln(n)) + 4*ln(n+2) = (10*n+2) / A Using a property of logarithm: ln(1 + x) -> x, if x -> 0, and other property: ln(n) / n -> 0, when n -> +oo, equation (15) will be approximated by: (15) -1 + 4 + 2 + 0 + 0 = 10 / A So, the coefficient A is equal to 2 and the average number of comparisons in sorting of n size arrays is (9) C_n = 2*n*ln(n). To find the approximation of the average number of swaps, we use the similar approach as in the case of comparisons. The average number of swaps S_n as a function of the number of elements may be represented by the equation: (10) S_n = 4 + 2/3*(n-2) + 2/(n*(n-1)) * sum_{k=0}^{n-2} {(n-k-1)*S_k} We assume that average number of swaps during one iteration is 2/3*(n-2). It means that in average one third of elements is swapped only. Using the same approach, we find that the coefficient A equals to 0.8. Therefore, the function S_n may be approximated by the equation: (11) S_n = 0.8*n*ln(n) ------------------------------------------------------------------------- And as summary: The value of the coefficient A: dual-pivot classic comparison: 2.0 2.0 swap: 0.8 1.0

14 20

A method with return type size_t returns negative value
by Jing LV 29 Nov '11

29 Nov '11

Hello, I found a problem in windows/native/java/io/io_util_md.c, method handleRead(). The return type of the method is size_t, which is defined as unsigned int. However we see the method would return negative values while it meets some error. This may be a problem as the API comsumer and later developer may have misunderstand it. I suggest modify it to ssize_t (or SSIZE_T as it is on windows). Any comments? -- Best Regards, Jimmy, Jing LV

5 21

Are the faster versions of HashMap and BigInteger going into jdk7?
by Paulo Levi 03 Sep '11

03 Sep '11

Just a question.

8 12

Review request for 7020513 : Add com.sun.xml.internal to the "package.access" property in java.security
by Rama Pulavarthi 29 Aug '11

29 Aug '11

Hi, Need reviewer for CR 7020513: Add com.sun.xml.internal to the "package.access" property in $JAVA_HOME/lib/security/java.security Webrev is available at http://cr.openjdk.java.net/~ohair/openjdk7/jdk7-tl-jaxws-7020513/webrev/ thanks, Rama Pulavarthi

6 12

BufferedOutputStream does not throw exception after it's closed
by Jing LV 25 Jul '11

25 Jul '11

Hello, Find a similar problem with the one in the last mail(BufferedWriter), this time is BufferedOutputStream, and it has a delegated output stream and behave the same with BufferedWriter, I believe the two problems are just the same - it needs to check the open status before store the contents even if it does not need to flush. A similar testcase can be: private int bufferSize = 1024; public void test() throws Exception { OutputStream out = new BufferedOutputStream(new ClosableByteArrayOutputStream(), bufferSize); out.close(); try { out.write(new byte[] { 7, 3, 4, 5 }); fail("expected already closed exception"); } catch (IOException expected) { } } private static class ClosableByteArrayOutputStream extends OutputStream { private final ByteArrayOutputStream bytesOut = new ByteArrayOutputStream(); private boolean closed = false; @Override public void close() throws IOException { closed = true; } @Override public void write(int oneByte) throws IOException { if (closed) { throw new IOException(); } bytesOut.write(oneByte); } } Any comments? I'd like to raise this problem on the bug-tracker system.

4 6

Request for approval: Bug 100057 - Potential stack corruption in GetJavaProperties
by Andrew Haley 18 May '11

18 May '11

https://bugs.openjdk.java.net/show_bug.cgi?id=100057 GetJavaProperties has a stack-allocated fixed size buffer for holding a copy of a string returned by setlocale(3). However, there is no guarantee that the string will fit into this buffer. This one is probably due to Solaris code being reused for Linux. The patch has been in IcedTea for a long while. OK to push, OpenJDK 7 and 6? Andrew. --- oldopenjdk6/jdk/src/solaris/native/java/lang/java_props_md.c 2008-08-28 04:15:51.000000000 -0400 +++ openjdk/jdk/src/solaris/native/java/lang/java_props_md.c 2008-09-15 10:37:26.000000000 -0400 @@ -211,7 +211,9 @@ * <language name>_<country name>.<encoding name>@<variant name> * <country name>, <encoding name>, and <variant name> are optional. */ - char temp[64]; + char * temp; + temp = (char*) malloc(strlen(lc)+1); + char *language = NULL, *country = NULL, *variant = NULL, *encoding = NULL; char *std_language = NULL, *std_country = NULL, *std_variant = NULL, @@ -323,6 +325,9 @@ /* return same result nl_langinfo would return for en_UK, * in order to use optimizations. */ std_encoding = (*p != '\0') ? p : "ISO8859-1"; + + /* Free temp */ + free(temp); #ifdef __linux__

6 17

Code review request for 7026898 DriverManager to now use CopyOnWriteArrayList
by Lance Andersen - Oracle 27 Apr '11

27 Apr '11

Hi, I have posted the diffs to DriverManager for review at http://cr.openjdk.java.net/~lancea/7026898/. This change utilizes CopyOnWriteArrayList instead of the Vectors previously used. Regards, Lance Lance Andersen| Principal Member of Technical Staff | +1.781.442.2037 Oracle Java Engineering 1 Network Drive Burlington, MA 01803 Lance.Andersen(a)oracle.com Oracle is committed to developing practices and products that help protect the environment

7 10

Suspected regression: fix for 6735255 causes delay in GC of ZipFile InputStreams, increase in heap demand
by Neil Richards 18 Apr '11

18 Apr '11

Hi, I've noticed that the fix introduced to address bug 6735255 [1] [2] had an unfortunate side-effect. That fix stores references to the InputStream objects returned from ZipFile.getInputStream(ZipEntry) in a HashSet (within ZipFile), so that the close() method may be called upon those objects when ZipFile.close() is called. It does this to conform to the existing API description, and to avoid a native memory leak which would occur if the InputStream is GC'd without its close() being called. However, by holding these InputStreams in a set within their ZipFile object, their lifecycle is now prolonged until the ZipFile object either has its close() method called, or is finalized (prior to GC). I've found scenarios (in user code) were ZipFile objects are held onto for a long time (eg. the entire lifetime of the process), but where InputStream objects from that ZipFile (for individual entries in the zip file) are obtained, used, then abandoned on a large number of occasions. (An example here might be a user-defined, long-lasting class loader, which might retain a ZipFile instance for each jar file in its search path, but which will create transitory input streams to read out particular files from those (large) jar files). I see that the InputStream objects returned from ZipFile.getInputStream(ZipEntry) tend to hold references to a couple of sizeable byte arrays, one 512 bytes in size, the other 1002 bytes. So by prolonging the life span of these objects, the fix for 6735255 can inadvertently cause a significant increase in the demand/usage on the heap (in practice, running into many Mb's). (This is not so if the user code is good-mannered enough to explicitly always call close() on the InputStreams in question. However, experience shows that user code cannot be relied upon to behave so benignly). I believe this introduced problem can be addressed by: 1. Holding references to the InputStreams in the 'streams' Set within ZipFile via WeakReferences, so they may be GC'd as soon as they are no longer externally (strongly) referenced. 2. Adding finalization logic to the InputStream implementation classes, which ensures their close() method is called prior to GC. 3. Prevent Inflater objects from being returned to the pool (in the ZipFile object) if close() has been called from finalize(). To that end, please find below an 'hg export' of a proposed change which implements these aspects, together with a testcase to demonstrate the problem/fix. Any comments / suggestions on this gratefully received, Thanks, Neil [1] http://bugs.sun.com/view_bug.do?bug_id=6735255 [2] http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/49478a651a28 -- Unless stated above: IBM email: neil_richards at uk.ibm.com IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU # HG changeset patch # User Neil Richards <neil.richards(a)ngmr.net>, <neil_richards(a)uk.ibm.com> # Date 1300289208 0 # Branch zip-heap # Node ID 34642c56c6febfd845c6c4ffd0344c3257f0b848 # Parent 554adcfb615e63e62af530b1c10fcf7813a75b26 Summary: Allow unreferenced ZipFile InputStreams to be finalized, GC'd Contributed-by: <neil.richards(a)ngmr.net> diff -r 554adcfb615e -r 34642c56c6fe src/share/classes/java/util/zip/ZipFile.java --- a/src/share/classes/java/util/zip/ZipFile.java Wed Mar 16 15:01:07 2011 -0700 +++ b/src/share/classes/java/util/zip/ZipFile.java Wed Mar 16 15:26:48 2011 +0000 @@ -30,11 +30,14 @@ import java.io.IOException; import java.io.EOFException; import java.io.File; +import java.lang.ref.ReferenceQueue; +import java.lang.ref.WeakReference; import java.nio.charset.Charset; import java.util.Vector; import java.util.Enumeration; import java.util.Set; import java.util.HashSet; +import java.util.Iterator; import java.util.NoSuchElementException; import java.security.AccessController; import sun.security.action.GetPropertyAction; @@ -315,7 +318,16 @@ private static native void freeEntry(long jzfile, long jzentry); // the outstanding inputstreams that need to be closed. - private Set<InputStream> streams = new HashSet<>(); + private final Set<WeakReference<InputStream>> streams = new HashSet<>(); + private final ReferenceQueue<? super InputStream> staleStreamQueue = + new ReferenceQueue<>(); + + private void clearStaleStreams() { + Object staleStream; + while (null != (staleStream = staleStreamQueue.poll())) { + streams.remove(staleStream); + } + } /** * Returns an input stream for reading the contents of the specified @@ -339,6 +351,7 @@ ZipFileInputStream in = null; synchronized (this) { ensureOpen(); + clearStaleStreams(); if (!zc.isUTF8() && (entry.flag & EFS) != 0) { jzentry = getEntry(jzfile, zc.getBytesUTF8(entry.name), false); } else { @@ -351,51 +364,19 @@ switch (getEntryMethod(jzentry)) { case STORED: - streams.add(in); + streams.add( + new WeakReference<InputStream>(in, staleStreamQueue)); return in; case DEFLATED: - final ZipFileInputStream zfin = in; // MORE: Compute good size for inflater stream: long size = getEntrySize(jzentry) + 2; // Inflater likes a bit of slack if (size > 65536) size = 8192; if (size <= 0) size = 4096; - InputStream is = new InflaterInputStream(zfin, getInflater(), (int)size) { - private boolean isClosed = false; - - public void close() throws IOException { - if (!isClosed) { - super.close(); - releaseInflater(inf); - isClosed = true; - } - } - // Override fill() method to provide an extra "dummy" byte - // at the end of the input stream. This is required when - // using the "nowrap" Inflater option. - protected void fill() throws IOException { - if (eof) { - throw new EOFException( - "Unexpected end of ZLIB input stream"); - } - len = this.in.read(buf, 0, buf.length); - if (len == -1) { - buf[0] = 0; - len = 1; - eof = true; - } - inf.setInput(buf, 0, len); - } - private boolean eof; - - public int available() throws IOException { - if (isClosed) - return 0; - long avail = zfin.size() - inf.getBytesWritten(); - return avail > (long) Integer.MAX_VALUE ? - Integer.MAX_VALUE : (int) avail; - } - }; - streams.add(is); + InputStream is = + new ZipFileInflaterInputStream(in, getInflater(), + (int)size); + streams.add( + new WeakReference<InputStream>(is, staleStreamQueue)); return is; default: throw new ZipException("invalid compression method"); @@ -403,6 +384,58 @@ } } + private class ZipFileInflaterInputStream extends InflaterInputStream { + private boolean isClosed = false; + private boolean eof = false; + private final ZipFileInputStream zfin; + private boolean inFinalizer = false; + + ZipFileInflaterInputStream(ZipFileInputStream zfin, Inflater inf, + int size) { + super(zfin, inf, size); + this.zfin = zfin; + } + + public void close() throws IOException { + synchronized (ZipFile.this) { + if (!isClosed) { + super.close(); + if (false == inFinalizer) + releaseInflater(inf); + isClosed = true; + } + } + } + // Override fill() method to provide an extra "dummy" byte + // at the end of the input stream. This is required when + // using the "nowrap" Inflater option. + protected void fill() throws IOException { + if (eof) { + throw new EOFException("Unexpected end of ZLIB input stream"); + } + len = in.read(buf, 0, buf.length); + if (len == -1) { + buf[0] = 0; + len = 1; + eof = true; + } + inf.setInput(buf, 0, len); + } + + public int available() throws IOException { + if (isClosed) + return 0; + long avail = zfin.size() - inf.getBytesWritten(); + return (avail > (long) Integer.MAX_VALUE ? + Integer.MAX_VALUE : (int) avail); + } + + protected void finalize() throws IOException { + inFinalizer = true; + close(); + } + } + /* * Gets an inflater from the list of available inflaters or allocates * a new one. @@ -543,11 +576,14 @@ synchronized (this) { closeRequested = true; - if (streams.size() !=0) { - Set<InputStream> copy = streams; - streams = new HashSet<>(); - for (InputStream is: copy) + Iterator<WeakReference<InputStream>> streamsIterator = + streams.iterator(); + while (streamsIterator.hasNext()) { + InputStream is = streamsIterator.next().get(); + if (null != is) { is.close(); + } + streamsIterator.remove(); } if (jzfile != 0) { @@ -684,9 +720,12 @@ freeEntry(ZipFile.this.jzfile, jzentry); jzentry = 0; } - streams.remove(this); } } + + protected void finalize() { + close(); + } } diff -r 554adcfb615e -r 34642c56c6fe test/java/util/zip/ZipFile/ClearStaleZipFileInputStreams.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/zip/ZipFile/ClearStaleZipFileInputStreams.java Wed Mar 16 15:26:48 2011 +0000 @@ -0,0 +1,148 @@ +/* + * 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. + */ + +/* + * Portions Copyright (c) 2011 IBM Corporation + */ + +/* + * @test + * @bug %BUG% + * @summary Allow stale InputStreams from ZipFiles to be GC'd + * @author Neil Richards <neil.richards(a)ngmr.net>, <neil_richards(a)uk.ibm.com> + */ +import java.lang.ref.ReferenceQueue; +import java.lang.ref.WeakReference; +import java.io.File; +import java.io.FileOutputStream; +import java.io.InputStream; +import java.util.Enumeration; +import java.util.HashSet; +import java.util.Random; +import java.util.Set; +import java.util.zip.ZipEntry; +import java.util.zip.ZipFile; +import java.util.zip.ZipOutputStream; + +public class ClearStaleZipFileInputStreams { + private static final int ZIP_ENTRY_NUM = 5; + + private static final byte[][] data; + + static { + data = new byte[ZIP_ENTRY_NUM][]; + Random r = new Random(); + for (int i = 0; i < ZIP_ENTRY_NUM; i++) { + data[i] = new byte[1000]; + r.nextBytes(data[i]); + } + } + + private static File createTestFile(int compression) throws Exception { + File tempZipFile = + File.createTempFile("test-data" + compression, ".zip"); + tempZipFile.deleteOnExit(); + + ZipOutputStream zos = + new ZipOutputStream(new FileOutputStream(tempZipFile)); + zos.setLevel(compression); + + try { + for (int i = 0; i < ZIP_ENTRY_NUM; i++) { + String text = "Entry" + i; + ZipEntry entry = new ZipEntry(text); + zos.putNextEntry(entry); + try { + zos.write(data[i], 0, data[i].length); + } finally { + zos.closeEntry(); + } + } + } finally { + zos.close(); + } + + return tempZipFile; + } + + private static void startGcInducingThread(final int sleepMillis) { + final Thread gcInducingThread = new Thread() { + public void run() { + while (true) { + System.gc(); + try { + Thread.sleep(sleepMillis); + } catch (InterruptedException e) { } + } + } + }; + + gcInducingThread.setDaemon(true); + gcInducingThread.start(); + } + + public static void main(String[] args) throws Exception { + startGcInducingThread(500); + runTest(ZipOutputStream.DEFLATED); + runTest(ZipOutputStream.STORED); + } + + private static void runTest(int compression) throws Exception { + ReferenceQueue<InputStream> rq = new ReferenceQueue<>(); + + System.out.println("Testing with a zip file with compression level = " + + compression); + File f = createTestFile(compression); + try { + ZipFile zf = new ZipFile(f); + try { + Set<Object> refSet = createTransientInputStreams(zf, rq); + + System.out.println("Waiting for 'stale' input streams from ZipFile to be GC'd ..."); + System.out.println("(The test will hang on failure)"); + while (false == refSet.isEmpty()) { + refSet.remove(rq.remove()); + } + System.out.println("Test PASSED."); + System.out.println(); + } finally { + zf.close(); + } + } finally { + f.close(); + } + } + + private static Set<Object> createTransientInputStreams(ZipFile zf, + ReferenceQueue<InputStream> rq) throws Exception { + Enumeration<? extends ZipEntry> zfe = zf.entries(); + Set<Object> refSet = new HashSet<>(); + + while (zfe.hasMoreElements()) { + InputStream is = zf.getInputStream(zfe.nextElement()); + refSet.add(new WeakReference<InputStream>(is, rq)); + } + + return refSet; + } +}

7 37

Request for review: 6597112: Referential integrity loophole during remote object export
by Neil Richards 14 Apr '11

14 Apr '11

Bug 6597112 [1] reports that the implementation of java.rmi.server.UnicastRemoteObject.exportObject(Remote) has a window in which the Remote object given to the method is only weakly referenced by the implementation. Due to this window, an unfortunately timed GC cycle can free up the Remote object, causing an exception to be thrown at a later point (still) within the exportObject() implementation. In the implementation, the window occurs in sun.rmi.server.UnicastServerRef.exportObject(), between the creation of a sun.rmi.transport.Target object (which currently holds the object being exported weakly), and the call to ref.exportObject(), which retrieves a reference for the Remote from (the weak reference within) the Target, completes the export of the Remote, storing the retrieved (strong) reference in sun.rmi.transport.ObjectTable. The weak reference within Target is actually an instance of sun.rmi.transport.WeakRef (which extends java.lang.ref.WeakReference), a package private class that is used only for storing refs within Target objects, and (transiently) for performing lookups within the ObjectTable. WeakRef provides a facility for "pinning" (and unpinning) its object, whereby it can hold a strong reference to the object (in addition to the weak reference), thus preventing it (whilst pinned) from being GC'd. Currently, a new WeakRef starts life "unpinned". The attached suggested fix (in webrev zip file form) changes the behaviour of WeakRef such that its reference is initally pinned. This prevents the referred to (Remote) object from being initially GC-able, until the call which places a (strong) reference to it in ObjectTable has completed, at which point it can be unpinned. In order to be able to unpin it at this point, the suggested fix modifies the access modifier to Target.unpinImpl() (which calls onto WeakRef.unpin()) from 'default' (ie. package private) to 'public'. (This is necessary as the caller, UnicastServerRef, is in a different package to Target). Also included is a testcase which is likely to demonstrate the problem, based on the code given in the original bug submission. Without the fix, on my machine (a Linux x86 dual Pentium 4 - gasp at the sheer *power*), the problem is seen within around 5000 iterations, so I've set the maximum iteration count (ie. the point at which the test concludes the problem doesn't exist) to be 10x that. Please review the suggested fix attached, and reply with your comments/suggestions, Thanks, Neil -- Unless stated above: IBM email: neil_richards at uk.ibm.com IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU

4 12

Need reviewers: Update of jaxp 1.4.5 source drop bundle
by Kelly O'Hair 10 Apr '11

10 Apr '11

Need reviewer for change in jaxp source drop bundle 7023289: jaxp 1.4.5 development jdk7 2nd integration http://cr.openjdk.java.net/~ohair/openjdk7/jdk7-tl-jaxp-145dev1/webrev/ Joe or someone from the JAXP team may want to comment on the specific changes in this new source bundle. -kto

5 7