How efficient is nginx prefix-based location handling implementation?

Question

How is the prefix string location handling implemented within nginx?

• http://nginx.org/r/location

Specifically, it's widely reported that the http://nginx.org/r/server_name matching is done through a hash table — http://nginx.org/docs/http/server_names.html — but there isn't a similar level of detail on the implementation of the location directive.

Answer 1

The prefix-based location tree is defined to have 3 child node elements at each node:

http://ngx.su/src/http/ngx_http_core_module.h#ngx_http_location_tree_node_s

462struct ngx_http_location_tree_node_s {
463    ngx_http_location_tree_node_t   *left;
464    ngx_http_location_tree_node_t   *right;
465    ngx_http_location_tree_node_t   *tree;

This would appear to be a sort of a data-structure known as a prefix tree, or a trie:

https://en.wikipedia.org/wiki/Trie

To find the longest-matching location prefix string, in the presence of exact shorter-matching ones, nginx descends further into what it calls the inclusive match, into the tree child element, keeping in mind the parts of the URI string that have already been matched; otherwise, the structure acts as a regular BST, where, depending on the result of the comparison operation of the URL against the current name of the node (performed by the likes of memcmp(3)), nginx descends either into the left or the right node of the sorted tree:

http://ngx.su/src/http/ngx_http_core_module.c#ngx_http_core_find_static_location

1626    len = r->uri.len;
…
1631    for ( ;; ) {
…
1642        rc = ngx_filename_cmp(uri, node->name, n);
1643
1644        if (rc != 0) {
1645            node = (rc < 0) ? node->left : node->right;
1646
1647            continue;
1648        }
1649
1650        if (len > (size_t) node->len) {
1651
1652            if (node->inclusive) {
1653
1654                r->loc_conf = node->inclusive->loc_conf;
1655                rv = NGX_AGAIN;
1656
1657                node = node->tree;
1658                uri += n;
1659                len -= n;
1660
1661                continue;
1662            }

An exact match (location =) results in somewhat of a special case of going into the right tree, without a prefix optimisation:

1663
1664            /* exact only */
1665
1666            node = node->right;
1667
1668            continue;
1669        }

The tree is assembled by initially storing all location nodes in a queue, sorting the queue through insertion sort, and then assembling the prefix tree from the middle of the sorted queue:

http://ngx.su/src/http/ngx_http.c#ngx_http_block

277    /* create location trees */
…
283        if (ngx_http_init_locations(cf, cscfp[s], clcf) != NGX_OK) {
…
287        if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) {

http://ngx.su/src/http/ngx_http.c#ngx_http_init_locations

689    ngx_queue_sort(locations, ngx_http_cmp_locations);

http://ngx.su/src/core/ngx_queue.c#ngx_queue_sort

48/* the stable insertion sort */

http://ngx.su/src/http/ngx_http.c#ngx_http_init_static_location_trees

835    pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0);

http://ngx.su/src/http/ngx_http.c#ngx_http_create_locations_tree

1075    q = ngx_queue_middle(locations);
…