RFR: 8378354: Faulty assertion in checkInvariants method of ConcurrentHashMap
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red." ------------- Commit messages: - Update ConcurrentHashMap.java Changes: https://git.openjdk.org/jdk/pull/24612/files Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=24612&range=00 Issue: https://bugs.openjdk.org/browse/JDK-8378354 Stats: 1 line in 1 file changed: 0 ins; 0 del; 1 mod Patch: https://git.openjdk.org/jdk/pull/24612.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/24612/head:pull/24612 PR: https://git.openjdk.org/jdk/pull/24612
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
Thanks for spotting the faulty assertion! It's surprising that this has never triggered in tests. ------------- Marked as reviewed by dl (Reviewer). PR Review: https://git.openjdk.org/jdk/pull/24612#pullrequestreview-3832266970
On Fri, 20 Feb 2026 14:18:37 GMT, Doug Lea <dl@openjdk.org> wrote:
It's surprising that this has never triggered in tests.
The faulty assertion was weaker than the desired one: the desired assertion ensures there is no consecutive red nodes, while the faulty assertion checks there is no red node with both children being red. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3936422803
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
Marked as reviewed by liach (Reviewer). Makes sense. Since this is assertion code, there is really no way to add a test... ------------- PR Review: https://git.openjdk.org/jdk/pull/24612#pullrequestreview-3833597386 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-2800009831
On Sun, 13 Apr 2025 16:02:20 GMT, Chen Liang <liach@openjdk.org> wrote:
Makes sense. Since this is assertion code, there is really no way to add a test...
Hi, Chen Liang After half year, finally I pass the oca process. Do you know who can help me review this pr? And, seems this pr need a ticket number before merge it. I don't know how to get it. Contributing to JDK is a interesting thing. But If this pr not need merge, I can close it. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3466115598
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
ご連絡、ありがとうございます。これからもよろしくお願いします。 I have signed oca. But maybe the reviewer has not handle it yet. ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ご連絡、ありがとうございます。これからもよろしくお願いします。 ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-2799897820 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-2799899020 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-2874602240 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-2957624444 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3047313514 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3153730755 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3244175460 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3353716764 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3459499808 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3584441420 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3691171111 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3783256600 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3928387616
On Thu, 19 Feb 2026 16:33:07 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
ご連絡、ありがとうございます。これからもよろしくお願いします。
Hello @cdw200806,
And, seems this pr need a ticket number before merge it. I don't know how to get it. Contributing to JDK is a interesting thing. But If this pr not need merge, I can close it.
The OpenJDK contribution guide has details on how to propose changes to the JDK https://openjdk.org/guide/. For a change like this, that doesn't have a corresponding JBS issue already filed, the suggestion is to first ask in a relevant mailing list whether the change is worth doing. Can you create a discussion in the concurrency-dev mailing list https://mail.openjdk.org/mailman/listinfo/concurrency-discuss and explain what this change is about? The mailing list requires subscription, so please subscribe before posting. That mailing list link has details on how to subscribe. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3934657893
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
We should create an issue in JBS for this. The tests run with -esa so I would expect checkInvariants is run a lot in testing. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3935156711
On Fri, 20 Feb 2026 14:22:53 GMT, Alan Bateman <alanb@openjdk.org> wrote:
We should create an issue in JBS for this.
I've now filed https://bugs.openjdk.org/browse/JDK-8378354. @cdw200806, please update the title of this PR to `8378354: Faulty assertion in checkInvariants method of ConcurrentHashMap` to initiate an official review of this change. Please also merge the latest changes from master branch into this PR. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3935474761
On Fri, 20 Feb 2026 15:05:18 GMT, Jaikiran Pai <jpai@openjdk.org> wrote:
We should create an issue in JBS for this.
I've now filed https://bugs.openjdk.org/browse/JDK-8378354.
@cdw200806, please update the title of this PR to `8378354: Faulty assertion in checkInvariants method of ConcurrentHashMap` to initiate an official review of this change. Please also merge the latest changes from master branch into this PR.
@jaikiran @DougLea @AlanBateman @liach Hi Colleagues in JDK, I also have another findings, but it is hard to fix. So I just mention here, please check. If you decide to raise a ticket to me, please share the ticket number to me, thanks. Run this 4 line code in a main() method, JDK will throw StackOverflowError caused by recursion. Before throw err, the console print "{(this Map)=Some String}" ConcurrentHashMap map = new ConcurrentHashMap(); map.put(map, "Some String"); System.out.println(map); map.put(map, "Some String"); The toString() method of ConcurrentHashMap seems to fixed this issue by replace this map to "(this Map)" . But for hashCode() method of ConcurrentHashMap, it seems has not consider the recursion case. Why hard to fix: consider this case, the key has recursion it self, it will throw StackOverflowError too. ConcurrentHashMap map = new ConcurrentHashMap(); Map map2 = new HashMap(); map2.put(map2, "Some String"); map.put(map2, "Some String"); ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3936476482
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
Please describe the semantic impact of the violated assertion. Would it ever be observable? ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3936854687
On Fri, 20 Feb 2026 20:02:06 GMT, Roger Riggs <rriggs@openjdk.org> wrote:
Please describe the semantic impact of the violated assertion. Would it ever be observable?
If concurrent map use red-black-tree correctly(or use it normally as common red-balck-tree algorithm), this bug will never be observable. In the logic, It just like the old code assert 1 is a Object, but I fix it to 1 is a Integer. More correctly( if 1 is a String it will throw error) , but the old code is not a "bug" , will never throw error(if the tree is build and use correct). I find it by code review. This assert just like a ut lack some of branch,a ut not perfect, if the red-black-tree operation code is wrong and some case not as expect happen and it will not aware,but if the code run correctly, maybe it not need to fix, it decide by your team. @RogerRiggs ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3936977232
On Fri, 20 Feb 2026 20:23:27 GMT, cdw200806 <duke@openjdk.org> wrote:
Please describe the semantic impact of the violated assertion. Would it ever be observable?
Please describe the semantic impact of the violated assertion. Would it ever be observable?
If concurrent map use red-black-tree correctly(or use it normally as common red-balck-tree algorithm), this bug will never be observable. In the logic, It just like the old code assert 1 is a Object, but I fix it to 1 is a Integer. More correctly( if 1 is a String it will throw error) , but the old code is not a "bug" , will never throw error(if the tree is build and use correct). I find it by code review.
This assert just like a ut lack some of branch,a ut not perfect, if the red-black-tree operation code is wrong and some case not as expect happen and it will not aware,but if the code run correctly, maybe it not need to fix, it decide by your team.
@RogerRiggs
Hello @cdw200806, the line numbers in your change don't match the code in JDK master branch. Can you merge in the latest changes from master branch into yours and update this PR? I'm a bit surprised that the skara bots haven't tagged this PR with a merge-conflict label. While at it please also enable GitHub Actions in your repo so that the GitHub actions test jobs get run in this PR. See the message here which explains what needs to be done https://github.com/openjdk/jdk/pull/24612/checks?check_run_id=40460799667. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3937937691
On Fri, 20 Feb 2026 20:23:27 GMT, cdw200806 <duke@openjdk.org> wrote:
Please describe the semantic impact of the violated assertion. Would it ever be observable?
Please describe the semantic impact of the violated assertion. Would it ever be observable?
If concurrent map use red-black-tree correctly(or use it normally as common red-balck-tree algorithm), this bug will never be observable. In the logic, It just like the old code assert 1 is a Object, but I fix it to 1 is a Integer. More correctly( if 1 is a String it will throw error) , but the old code is not a "bug" , will never throw error(if the tree is build and use correct). I find it by code review.
This assert just like a ut lack some of branch,a ut not perfect, if the red-black-tree operation code is wrong and some case not as expect happen and it will not aware,but if the code run correctly, maybe it not need to fix, it decide by your team.
@RogerRiggs
Hello @cdw200806, the line numbers in your change don't match the code in JDK master branch. Can you merge in the latest changes from master branch into yours and update this PR? I'm a bit surprised that the skara bots haven't tagged this PR with a merge-conflict label.
While at it please also enable GitHub Actions in your repo so that the GitHub actions test jobs get run in this PR. See the message here which explains what needs to be done https://github.com/openjdk/jdk/pull/24612/checks?check_run_id=40460799667.
Hi colleagues, I raise a new PR to resolve conflict issue. We can close this outdated PR. https://github.com/openjdk/jdk/pull/29857 @jaikiran @AlanBateman @viktorklang-ora ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3939087442
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
It is a common case when a data structure contains cycles; when it is expensive to detect and avoid the cycle, the burden is on the user to avoid creating the cycle or to avoid calling functions that do not know when to quit. StackOverflow is the warning that a design or api principle has been violated. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3936889888
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
I've run tier1+tier2 with the tighter check and the assert checkInvariants didn't trip. I agree with Jai that the PR branch should be sync'ed up as it's baseline is from 9 months ago. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3938444058
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
Seconding Alan's comment ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3939010005
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
Since PR(https://github.com/openjdk/jdk/pull/29857 ) has been merged, then I close this PR now. Since PR(https://github.com/openjdk/jdk/pull/29857 ) has been merged, then I close this PR now. ------------- PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3950883298 PR Comment: https://git.openjdk.org/jdk/pull/24612#issuecomment-3950884225
On Sun, 13 Apr 2025 10:31:34 GMT, cdw200806 <duke@openjdk.org> wrote:
"In Red-Black Trees, a red node cannot have any red children; this rule is violated even if only one child is red, not just when both children are red."
This pull request has been closed without being integrated. ------------- PR: https://git.openjdk.org/jdk/pull/24612
participants (7)
-
Alan Bateman
-
cdw200806
-
Chen Liang
-
Doug Lea
-
Jaikiran Pai
-
Roger Riggs
-
Viktor Klang