#27 _order_timestamp can't handle time wraps

[chrysn]

the current implementation of _order_timestamp, as used to sort the the nodes in the send queue, does not treat time wraps correctly. time wraps happen every 50 days in the posix implementation on platforms where int is 32bits ((2**32 / 1024.0)/60/60/24).

as a result, whenever a time wrap occurs and coap requests are pending, the send queue does not get sorted properly.

for reference, the current implementation looks like this:

int _order_timestamp( coap_queue_t *lhs, coap_queue_t *rhs ) {
  return lhs && rhs && ( lhs->t < rhs->t ) ? -1 : 1;
}

(static int in the pabigot branch).

given the _order_timestamp function should not query the current time, the easiest approach would be to change it to

( (signed int)(lhs->t - rhs->t) < 0 )

. this, however, does not quite cut it, because the definition of coap_tick_t, the type of [lr]hs->t, is platform depent. we'd need a coap_signed_tick_t definition for every platform to correctly cast this; still, that would be the easiest way.

for a solution that is cleaner in my opinion, i'd consider (and offer implementing, if it would be taken up in master) switching the semantics of the ->t parameter from absolute timestamps to timestamps relative to the previous item in the queue. this might sound confusing at first, but eliminates all problems with clock wrapping, and is used very successfully in the timer implementation of lwip.

the retransmission implementation would then -- in the only place in code that would still have to consider wraps -- compute the last time the retransmission queue was treated as delta. then, it would reduce the ->t of the first item in the send queue by delta, or it would resend it, subtract its t from delta, and loop, depending on how they compare.

[Olaf Bergmann]

You are right, the quick-and-dirty comparison function is crap. I like your proposal to use relative timestamps in the send queue and would be happy to put it into the master.

[Olaf Bergmann]

I have started an implementation of this solution in the branch relative-timestamps. (Needs testing and perhaps a small change described in commit 1df1ef5483c7d.)

[chrysn]

thank you for fixing this bug.

i'm using its branch now, and it goes over time wraps well. i don't think that sendqueue_basetime is a problem. two issues i had are fixed in the patches branch:

• there is an assert(context->sendqueue_basetime <= now); -- that's counterproductive here, as the whole point is to wrap. i've slightly rephrased the line this relates to so it becomes obvious where the wrapping is ok to happen.
• when there is only a single pending request and that gets removed (in coap_remove_from_queue), things segfault.

both patches (edab7b4, 3d2f21a) can be fetched from the git@gitorious.org:coap-lwip/coap-lwip.git repository (patches branch). some more patches reside in that branch, and can be viewed at [1]; i have not opened tickets for all of them yet, as i just recently factored them out from my lwip branch.

[1] https://gitorious.net/coap-lwip/coap-lwip/commits/c5f88316e1aac9b8ed573b078522fd89616282e6