Duplicate UNIQUE_IDs with mod_http2

[mkauf]

It can happen that the same request ID (UNIQUE_ID) is calculated twice by mod_unique_id when HTTP/2 is used. This is not a theoretical problem, it really occurs on busy servers.

mod_unique_id uses the current connection ID as an input for calculating the UNIQUE_ID. For HTTP 1.x, the current thread number is used as connection ID.

For HTTP/2, mod_h2 calculates a connection ID per stream, in h2_task_do(). For a 64-bit system:

task->c->id = (c->master->id << 32) ^ task->stream_id;

mod_unique_id only uses the lower 32 bits of this value in gen_unique_id():

new_unique_id.thread_index = htonl((unsigned int)c->id);

So effectively this is executed:

new_unique_id.thread_index = htonl((unsigned int)task->stream_id);

There is not enough "uniqueness" in this value.

Bugfix

This problem can be fixed in several ways:

• change mod_h2 to calculate the connection ID on 64-bit systems like on 32-bit systems
• change mod_unique_id to include all 64 bits of the connection ID into UNIQUE_ID
• change mod_unique_id to XOR the lower 32 bits of the connection ID with the upper 32 bits of the connection ID, and then use the resulting value for the UNIQUE_ID

The last approach could be implemented like this:

if (sizeof(long) > sizeof(int)) {
    new_unique_id.thread_index = htonl((unsigned int)(c->id >> (sizeof(int) * 8) ^ c->id));
}
else {
    new_unique_id.thread_index = htonl((unsigned int)c->id);
}

Unfortunately, duplicated IDs still showed up even with this patch. So probably including all 64 bits of the connection ID into UNIQUE_ID is the better approach.

[icing]

urgs, just looked at mod_unique_id. Do I see this right that the cur_unique_id.counter is not atomic and will not necessarily increase every time?

It "cleverly" relies on not being invoked from multiple threads for the same c->id mod 32bit. Interesting. And broken. It relies on a http/1.x processing model.

But of course no one can know what a change in mod_unique_id's implementation would trigger...But ultimately, this discussion needs to be done on the httpd dev list.

connection ids are implemented by the mpm and mpm_event indeed does

  #define ID_FROM_CHILD_THREAD(c, t)    ((c * thread_limit) + t)
  long conn_id = ID_FROM_CHILD_THREAD(my_child_num, my_thread_num);

Hmm. Maybe h2 should calc the id like this?

-        task->c->id = (c->master->id << free_bits)^slave_id;
+        task->c->id = (c->master->id << 8)^worker_id;

Maybe that works better, but there will still be configurations where collisions are possible. Maybe not very common ones.

Could you test this?

[mkauf]

You‘re right, the counter in mod_unique_id is not increased atomically. As a bugfix, mod_unique_id could increase the counter atomically and ignore the connection id. Not sure what this means for the performance, probably atomic operations were slow when mod_unique_id was created.

I‘m currently on holiday, I can test your proposed change next week.

[icing]

Enjoy your holiday!

[mkauf]

Thanks! I have tested this change:

-        task->c->id = (c->master->id << free_bits)^slave_id;
+        task->c->id = (c->master->id << 8)^worker_id;

It works fine, I got no duplicate UNIQUE_IDs so far 👍

For the test, I have used mod_asis and mod_include with this file:

Status: 200 OK
Content-Type: text/plain

<!--#echo var="UNIQUE_ID" -->

I have collected UNIQUE_IDs for approximately an hour, in 5 different terminals:

while true; do curl -k -s https://localhost/ https://localhost/ https://localhost/ https://localhost/ https://localhost/ >> /data/curl1.log; done

while true; do curl -k -s https://localhost/ https://localhost/ https://localhost/ https://localhost/ https://localhost/ >> /data/curl2.log; done

while true; do curl -k -s https://localhost/ https://localhost/ https://localhost/ https://localhost/ https://localhost/ >> /data/curl3.log; done

while true; do curl -k -s https://localhost/ https://localhost/ https://localhost/ https://localhost/ https://localhost/ >> /data/curl4.log; done

while true; do curl -k -s https://localhost/ https://localhost/ https://localhost/ https://localhost/ https://localhost/ >> /data/curl5.log; done

Check for duplicate UNIQUE_IDs:

cat /data/curl*.log | sort | uniq -c | grep -v '1 '

[mkauf]

For comparison: nginx uses 16 random bytes for "$request_id" - no counters involved.

[mkauf]

Is task->c->id = (c->master->id << 8)^worker_id; a "good enough" solution, or do we need to think about other options?

[icing]

If it works for you, I tend to consider it good enough. I can make the change in the module and apache subversion and propose for backport.

I'd dare not change the general implementation in 2.4.x, because there is bound to be someone using HTTP/1.1 who is relying on the current characteristics.

Works for you?

[mkauf]

Yes, works for me, thanks!