Skip to content

It is necessary to set MAX_CAPACITY to ArrayTernaryTrie/ArrayTrie #7271

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
tinswzy opened this issue Dec 14, 2021 · 1 comment · Fixed by #7405
Closed

It is necessary to set MAX_CAPACITY to ArrayTernaryTrie/ArrayTrie #7271

tinswzy opened this issue Dec 14, 2021 · 1 comment · Fixed by #7405
Labels
Bug For general bugs on Jetty side

Comments

@tinswzy
Copy link

tinswzy commented Dec 14, 2021

Jetty version(s)
9.3+, 9.4+

Java version/vendor (use: java -version)
All

OS type/version
All

Description
It is necessary to backport MAX_CAPACITY bugfix to ArrayTernaryTrie/ArrayTrie,as there are still many mainstream projects using jetty9.x.
In 9.x, the ContextHandlerCollection uses the ArrayTernaryTrie data structure by default. The data types of _rows&_tree in ArrayTernaryTrie are char/char[]. Their capacity is limited, otherwise routing bugs will occur if the value is exceeded.

How to reproduce?
@test
public void testArrayTernaryTrieBug() throws Exception
{
Trie trie = new ArrayTernaryTrie<>(false,400000);

// put root path
boolean success = trie.put("","/");
assertTrue(success);
String bestUrl = trie.get("/",1,0);
assertEquals("/",bestUrl);

// put a large path or many paths
char[] c1 = new char[65535];
Arrays.fill(c1,'a');
success = trie.put(new String(c1),"/"+new String(c1));
// expect put failed, but now it success
assertFalse(success);

bestUrl = trie.get("/",1,0);
assertEquals("/",bestUrl);

}

@tinswzy tinswzy added the Bug For general bugs on Jetty side label Dec 14, 2021
tinswzy added a commit to tinswzy/jetty.project that referenced this issue Dec 14, 2021
Signed-off-by: tinswzy <tinswzy@gmail.com>
tinswzy added a commit to tinswzy/jetty.project that referenced this issue Dec 14, 2021
Signed-off-by: tinswzy <tinswzy@gmail.com>
tinswzy added a commit to tinswzy/jetty.project that referenced this issue Dec 15, 2021
Signed-off-by: tinswzy <tinswzy@gmail.com>
tinswzy added a commit to tinswzy/jetty.project that referenced this issue Jan 15, 2022
Signed-off-by: tinswzy <tinswzy@gmail.com>
lorban added a commit that referenced this issue Jan 17, 2022
Signed-off-by: Ludovic Orban <lorban@bitronix.be>
lorban added a commit that referenced this issue Jan 17, 2022
Signed-off-by: Ludovic Orban <lorban@bitronix.be>
lorban added a commit that referenced this issue Jan 19, 2022
Signed-off-by: Ludovic Orban <lorban@bitronix.be>
@lorban lorban linked a pull request Jan 24, 2022 that will close this issue
sbordet added a commit that referenced this issue Jan 27, 2022

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
…city

 #7271 add checks for max capacity in tries
@sbordet
Copy link
Contributor

sbordet commented Jan 27, 2022

Fixed by #7405.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Bug For general bugs on Jetty side
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants