Day 47 - locations, ngx_queue_t and ngx_http_location_tree_t

As a follow-up to my previous post on debugging locations, I went even further in the location internals and that's what I'm about to share with you. But before we get ourselves carried away, I would like to apologize for an unforgivable mistake in my previous post: I called the structure used to retrieve static locations a "red-black (or binary) tree".

Shame on me. For this, I probably deserve to have to run Windows Vista for at least a week... ;)

No worries, I'm not going to do it.

After spending quite some time on wikipedia, it appears that I was quite mistaken on binary trees, red-black trees and the like. I'll just take a short moment to tell you what I now understand to be the difference (and hopefully be less verbose that wikipedia):

• A binary tree is simply a tree in which each node can have up to 2 children.
• A binary search tree is a binary tree which guarantees that all nodes on the left of a given node (let's call it N) are before N and that all nodes on the right of N are after it. This kind of structure is great for searching things fast. Or at least it's great on "average" (it's in O(log(n)), n being the number of nodes in the tree). Of course, if you are out of luck and the tree is "unbalanced" and you are looking for something at the very end of the tree), then it is as bad as looking at each node individually. That's called being in O(n) and it's pretty bad.
• So, a bunch of smart people invented "self-balancing binary search trees" (there are tons of variations on this theme). And the most famous of these structures is known as red-black tree. I always thought that red and black were just different names for the left and right edges that come out of a node. I was wrong. Red and black refer to colors that you give to nodes. The color of a node comes very handy when you need to insert (or delete) a node in the binary tree still keeping the overall tree balanced. The nice thing about red-black trees is that they do such a good job at keeping themselves balanced that they are fast (i.e. O(log(n)) ) even in the worst case scenario.

That should clear things up and if you want to dig more, there are an impressive number of binary tree structures documented on wikipedia. Now, what nginx uses to store locations (see how to debug location) is not a red-black tree. It's some kind of a mix between a radix tree (which is a kind of trie) and a binary search tree. I still might be slightly wrong here, so if you have a better name for what ngx_http_location_tree_t is, just comment here. I must say that after finding out how many different trees and data structures there are behind something I always considered simple (binary search trees), I decided to let it go and thought again about reading Donald Knuth's "The Art of Computer Programming" (still haven't purchased it though as I'm a bit afraid to discover how little I know after all those years).

Now that apologies and theory are behind us, let's have a closer look at the process that builds this tree. Nginx is an engine. Locations processing being specific to HTTP, it is handled by the corresponding module (namely the HttpCoreModule). This module handles (among other things) the processing of the http and location blocks. Here is how this goes:

• http block is parsed. It triggers parsing of server and location blocks (which must be inside http to respect the configuration file syntax).
• As a result, the "main" configuration (structure ngx_http_core_main_conf_t) is filled with an array (field servers) of server configurations (structure ngx_http_core_srv_conf_t), each of them containing a ngx_queue_t of locations.
• The ngx_http_init_locations function will sort those locations and split them into three different queues: the "named" locations, the "regexp" locations and the "static" locations. Processing for the "named" and "regexp" locations pretty much stops here (they are then used in their order of appearance in the configuration).
• "static" locations must be transformed into the final search tree. Function ngx_http_init_static_location_trees does exactly that and the algorithm goes:
  • Join "exact" and "starts with" locations if they have the same "name" (e.g location /foo {...} and location = /foo {...}). In the final tree structure they both will be attached to the same node (the one containing "/foo" in our example). This is function ngx_http_join_exact_locations
  • Group locations families (function ngx_http_create_locations_list). For example, if location 1 is "/foo" and location 2 is "/foo/bar", then the second location is attached to the first one (through field list of structure ngx_http_location_queue_t). Note that this function won't group "/fuu/bar" and "/fuu/baz" because "/fuu/baz" is not a child of "/fuu/bar".
  • Build the "search" tree (function ngx_http_create_locations_tree):
    • Split the list in two.
    • Assign the location in the middle to the root node of the tree. If this location has "children" locations, recursively process them (through ngx_http_create_locations_tree) and store the result as subtree of the node.
    • Recursively process the first sub-list and assign it to the left edge of the node.
    • Recursively process the second sub-list and assign it to the right edge of the node.

In this code Igor makes extensive use of the ngx_queue_t structure:

typedef struct ngx_queue_s  ngx_queue_t;
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

It is defined in ngx_queue.h and comes with a lot of macros (yes: macros, not functions - for performance reasons, of course) for its manipulation. The names are good enough so comments are not needed. Still I added "type" information that you would likely have if they were functions (don't be surprised by the difference if you look at the code):

void ngx_queue_init(ngx_queue_t* q);
bool ngx_queue_empty(ngx_queue_t* q);
void ngx_queue_insert_head(ngx_queue_t* q, ngx_queue_t* new_item);
void ngx_queue_insert_after(ngx_queue_t* after_item, ngx_queue_t* new_item);
void ngx_queue_insert_tail(ngx_queue_t* q, ngx_queue_t* new_item);
ngx_queue_t* ngx_queue_head(ngx_queue_t* q);
ngx_queue_t* ngx_queue_last(h);
ngx_queue_t* ngx_queue_sentinel(h);
ngx_queue_t* ngx_queue_next(q);
ngx_queue_t* ngx_queue_prev(q);
void ngx_queue_remove(ngx_queue_t* item_to_remove);
void ngx_queue_split(ngx_queue_t* q, ngx_queue_t* split_item, ngx_queue_t* tail_queue);
void ngx_queue_add(ngx_queue_t* queue1, ngx_queue_t* queue2);

Now, I see the java guys barking: "This is not strongly typed, this russian kiddo is mistaking a queue for its item". Look at the java version of a queue and you will see that a queue is not mistaken for its items... ;) Well, C is C. What did you expect? Arguably, one could do a better job using a few typedefs but it's beyond the point. The thing is that using a double-linked list to implement a queue is a very good way to have excellent performance on insertion, deletion, splitting and sorting (moving an item around is just a few pointers assignments). And to top things, you can even do this for any kind of object as items. If you are smart enough to build the items as a structure that starts with a ngx_queue_t structure. Just like:

typedef struct {
    ngx_queue_t                      queue;
    ngx_http_core_loc_conf_t        *exact;
    [...]
} ngx_http_location_queue_t;

And now, you can even call the function ngx_queue_sort that takes as arguments the queue to sort and a comparator function that knows how to compare two items of this queue. Yes, javaboys are going to argue that this is all a poor man's way of implementing inheritance and/or templates. And code is less readable. Yes, it's all true. But the result is very fast and uses very little memory. Anyway, I thought that might be interesting to explain as this is exactly the way the sorting in ngx_http_init_locations is implemented (the comparator is ngx_http_cmp_locations and it sorts according to a very particular order: the one needed by the rest of the algorithm for the grouping described above).

The ngx_queue_t structure being really a "circle", it uses a sentinel node which acts as the marker of the beginning and end of the queue but also as the queue itself. In all the macros/functions above you are supposed to hand over the sentinel as q parameter. If you don't, you might get unexpected results. So, in the end the queue is not mistaken for its items. It's just not very strongly typed...

One last note on the static locations tree. I said at the beginning that it is part-radix-tree. The reason why it is not a true radix tree is that if it were, in the example mentionned earlier the presence of locations "/fuu/bar" and "/fuu/baz" would create a tree like that:

/fuu/ba--r
  |
  z

And such a tree where some node might not be locations would not be so efficient during request processing because you don't know how far you would have to backtrack in order to get a "containing" location. With the current implementation you know you only have to go one level up.

OK, I have to stop with these super-long posts. But, hey we are really diving into the core of the thing and waters are not always as shallow as it looks.