ArrayTenaryTrie bug. Infinite Loop with many Handlers

[lambdaupb]

import org.eclipse.jetty.util.ArrayTernaryTrie;

public class ArrayTenaryTrieTest {

    public void loopTest(int size) throws Exception {
        int calcSize = 0;
        for(int i = 0; i< size; i++) {
            calcSize += "/test/group".length()+ Integer.toString(i).length();
        }

        System.out.println("Estimated size: "+calcSize);

        ArrayTernaryTrie<Integer> trie = new ArrayTernaryTrie<>(calcSize*3);
        for(int i = 0; i< size; i++) {
            boolean added = trie.put("/test/group" + i, i);
            if(!added) {
                throw new Exception("Could not add entry "+"/test/group" + i);
            }
        }

        System.out.println("added "+size+" entries successfully");
        System.out.println("trie.size() = "+trie.size());

        for(int i = 0; i< size; i++) {
            Integer integer = trie.get("/test/group" + i);
            if(integer == null) {
                throw new Exception("missing entry for '/test/group" + i+"'");
            } else if(integer.intValue() != i) {
                throw new Exception("incorrect value for '/test/group" + i+"' ("+integer+")");
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new ArrayTenaryTrieTest().loopTest(60_000);
    }
}

fails with

Estimated size: 948890
added 60000 entries successfully
trie.size() = 15375
Exception in thread "main" java.lang.Exception: missing entry for '/test/group0'

The trie only contains ~15k entries of the 60k that were all acknowledged with a true return on .put().

This fails no matter what capacity is given to the Trie.

This leads to an infinite loop in org.eclipse.jetty.server.handler.ContextHandlerCollection.newHandlers with a lot (>50k im my case) of handlers.

[gregw]

It fails at 32_763, so fells like a power of 2 thing going on....

[lambdaupb]

Maybe some wraparound. Could try replacing the math with Math.xxxExact(a,b), especially the hilo() method looks risky with its MAX_VALUE thing.

Haven't tried this though, don't have the project checked out.

[lambdaupb]

scratch the hilo() bit, that does not seem to be called in put()

[joakime]

Some discoveries on loopTest(size) ...

• size is 21841 the last time you get 100% success.
• size is 21842 you get 0 correct, 21842 missing, 0 incorrect.
• size is 21843 you get 1 correct, 20,066 missing, 1776 incorrect.

[gregw]

OK I can see what is going on..... but before I get into the details I'll just say.... > 50k context handlers ... whaaaaaaaaaaaaat!?!?!?!
I'm sure there is some very good reason for that, but it is kind of exceptional.... and we like jetty to be used in exceptional circumstances.... but still wow!!!!

So the problem is that ArrayTenaryTrie's main data structure is a character array, with each 4 characters representing a row in the table and 3 of entries in the row are actually indexes into the table! So once the number of rows in the table becomes greater than Character.MaxValue (0xFFFF = 32768), then the table indexing breaks down!

So first bug is that the class needs to check it's bounds and if we get too many rows it needs to throw... or probably it should have already thrown in the constructor if the capacity is too much.

Then how do we support the demand for larger numbers? I can see several solutions:

• The indexes in the char table can be divided by the ROW_SIZE, so we'd get a 4 times larger at the cost of an extra multiplication per char lookup.
• The array could be an array of ints, giving us a much bigger range, but costing a bit in size.
• Use a different Trie impl

Note that ArrayTrie itself goes to a much bigger size, but I think it may also have issues with not checking it's bounds. So we need to make sure that it does.

For ContextHandlerCollection, it can either:

1. Use an ArrayTernaryTrie with expanded capacity.
2. use ArrayTrie (with bounds checking)
3. Start using ArrayTernayTrie and if the size demands increase beyond limit start using ArrayTrie

2 is a quick fix for the OP, but we need to evaluate the space/time tradeoffs with all our Tries.

[gregw]

@lorban I think this is a good one for you post your current rabbit hole!

[lambdaupb]

OK I can see what is going on..... but before I get into the details I'll just say.... > 50k context handlers ... whaaaaaaaaaaaaat!?!?!?!
I'm sure there is some very good reason for that, but it is kind of exceptional.... and we like jetty to be used in exceptional circumstances.... but still wow!!!!

😃
Its either that, or essentially re-implementing path dispatch again in a catch-all handler, which was not very appealing.

[joakime]

You might want to look into the PathMappings component in Jetty.

https://www.eclipse.org/jetty/javadoc/current/org/eclipse/jetty/http/pathmap/PathMappings.html

Examples: https://github.com/eclipse/jetty.project/blob/jetty-9.4.x/jetty-http/src/test/java/org/eclipse/jetty/http/pathmap/PathMappingsTest.java

[gregw]

I've created PR #5293 with a quick fix. It lacks test harnesses and leaks impl details to the usage of the Trie.
But perhaps we sneak something like this into the next release while we contemplate a better solution.... @lambdaupb would you be able to work with your own local build of the PR branch to get you further while we take a few weeks to come up with a nicer solution?

I think we still need to review all our Trie implementations for bounds checks and check that size/speed tradeoffs are still relevant.

I also think that perhaps we should stop allowing specific Tries to be constructed.... instead have a static factory mechanism that can take the requirements: case insensitive, capacity, growing, expected characters etc. and then we can pick an impl for them. This will alllow us to be smarter in future about swapping out Trie impls.

[lambdaupb]

Possibly related: #1353 ?

---

But perhaps we sneak something like this into the next release while we contemplate a better solution.... @lambdaupb would you be able to work with your own local build of the PR branch to get you further while we take a few weeks to come up with a nicer solution?

For better or for worse, for the time being, I'll probably have to re-implement the path lookup with a catch-all handler on our side, that seems a lower maintenance burden, so take your time to do it right.

[joakime]

For better or for worse, for the time being, I'll probably have to re-implement the path lookup with a catch-all handler on our side

Here's a template for you to start with ...

package org.eclipse.jetty.server.handlers;

import java.io.IOException;
import java.util.List;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.eclipse.jetty.http.pathmap.MappedResource;
import org.eclipse.jetty.http.pathmap.PathMappings;
import org.eclipse.jetty.http.pathmap.PathSpec;
import org.eclipse.jetty.server.Handler;
import org.eclipse.jetty.server.Request;
import org.eclipse.jetty.server.handler.AbstractHandler;
import org.eclipse.jetty.util.component.LifeCycle;

public class PathMappingHandler extends AbstractHandler
{
    public static final String ATTR_PATH_SPEC = PathMappingHandler.class.getName() + ".pathSpec";
    private final PathMappings<Handler> mappings = new PathMappings<>();

    public void addMapping(PathSpec pathSpec, Handler handler)
    {
        mappings.put(pathSpec, handler);
    }

    @Override
    public void handle(String target, Request baseRequest, HttpServletRequest request, HttpServletResponse response) throws IOException, ServletException
    {
        List<MappedResource<Handler>> matches = mappings.getMatches(target);
        if (matches != null)
        {
            for (MappedResource<Handler> mappedResource : matches)
            {
                PathSpec pathSpec = mappedResource.getPathSpec();
                request.setAttribute(ATTR_PATH_SPEC, pathSpec);
                Handler handler = mappedResource.getResource();
                handler.handle(target, baseRequest, request, response);
                if (baseRequest.isHandled())
                    return;
            }
        }

        response.setStatus(404);
        baseRequest.setHandled(true);
    }

    @Override
    protected void doStart() throws Exception
    {
        for (MappedResource<Handler> handler : mappings.getMappings())
        {
            if (handler instanceof LifeCycle)
            {
                LifeCycle lifeCycle = (LifeCycle)handler;
                if (!lifeCycle.isStarted())
                {
                    lifeCycle.start();
                }
            }
        }

        super.doStart();
    }
}

You use it like this ...

package org.eclipse.jetty.server.handlers;

import org.eclipse.jetty.http.pathmap.RegexPathSpec;
import org.eclipse.jetty.http.pathmap.ServletPathSpec;
import org.eclipse.jetty.server.Server;
import org.eclipse.jetty.server.handler.DefaultHandler;

public class PathMappingHandlerTest
{
    public static void main(String[] args) throws Exception
    {
        Server server = new Server(9090);
        PathMappingHandler pathMappingHandler = new PathMappingHandler();
        server.setHandler(pathMappingHandler);

        pathMappingHandler.addMapping(new ServletPathSpec("/hello"), new HelloHandler("greetings"));
        pathMappingHandler.addMapping(new RegexPathSpec("/hello/.*/earthling"), new HelloHandler("earthling"));
        // final "default" path-spec that will be used if nothing above matches
        pathMappingHandler.addMapping(new ServletPathSpec("/"), new DefaultHandler());

        server.start();
        server.join();
    }
}

Example results.

[joakim@hyperion junk][master*]$ curl http://localhost:9090/hello
greetings
[joakim@hyperion junk][master*]$ curl http://localhost:9090/hello/fellow/earthling
earthling
[joakim@hyperion junk][master*]$ curl http://localhost:9090/something/not/found
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
<title>Error 404 Not Found</title>
</head>
<body><h2>HTTP ERROR 404 Not Found</h2>
<table>
<tr><th>URI:</th><td>/something/not/found</td></tr>
<tr><th>STATUS:</th><td>404</td></tr>
<tr><th>MESSAGE:</th><td>Not Found</td></tr>
<tr><th>SERVLET:</th><td>-</td></tr>
</table>
<hr><a href="http://eclipse.org/jetty">Powered by Jetty:// 9.4.30.v20200611</a><hr/>

</body>
</html>

[github-actions]

This issue has been automatically marked as stale because it has been a
full year without activity. It will be closed if no further activity occurs.
Thank you for your contributions.

[github-actions]

This issue has been closed due to it having no activity.

[sbordet]

@lorban is this actually fixed or needs to be reopened?

[lorban]

@sbordet this was solved in 10/11 with #5736 and 9.4 at least should be done with the infinite loop thanks to #7271.