32bit overflow does not work

[kfessel]

dtls_time.h seems to be uint32_t aware:

tinydtls/dtls_time.h

Line 64 in 68b2521

typedef uint32_t clock_time_t;

but these lines may produce problems with 32bit overflow:

these calculate possibly overflowing time stamps:

tinydtls/dtls.c

Line 1763 in 68b2521

n->t = now + 2 * CLOCK_SECOND;

tinydtls/dtls.c

Line 4534 in 68b2521

node->t = now + (node->timeout << node->retransmit_cnt);

these do not deal with overflowing timestamps:
calculating if the timeout happend: (timestamp passed by)

tinydtls/dtls.c

Line 4596 in 68b2521

while (node && node->t <= now) {

inserting (sorted) into the netq

tinydtls/netq.c

Line 96 in 68b2521

while(p && p->t <= node->t) {

In #123 @boaks and me pointed that out

reference / line number are current develop branch

[kfessel]

read later comment

(node && (now - node->t) < (((clock_time_t)0 - 1) / 2))

is true if (now > node->t) (taking overflow semantic into account)
(assuming (clock_time_t is some kind of unsigned integer -> defined overflow)

[kfessel]

I did a bit of testing using https://godbolt.org/z/qKPeoazhr

overflow seems to be applied when the whole calculation is done ->

calculate an offset

const clock_time_t offset = (((clock_time_t)~0) >> 1);

add offset to difference then cast to _t and compare to offset

if (node && ((offset + now - node->t) > offset)){
  //now is later than node->t
}

(this works as well if for any reason clock_time_t would be signed)

[boaks]

typedef int32_t clock_time_s_t;
typedef uint32_t clock_time_u_t;

...

  clock_time_s_t ts1, ts2;
  clock_time_u_t tu1, tu2;

  // signed overflow
  ts1 = 0x7ffffff0;
  ts2 = ts1 + 32;

  tu1 = 0x7ffffff0;
  tu2 = tu1 + 32;

  dtls_warn("signed: %d %d %d %d\n", ts1, ts2, (ts2 - ts1) > 0, (ts2 - ts1) < 0);
  dtls_warn("unsign: %u %u %d %d\n", tu1, tu2, (tu2 - tu1) > 0,  (tu2 - tu1) < 0);

  // unsigned overflow
  ts1 = 0xfffffff0;
  ts2 = ts1 + 32;

  tu1 = 0xfffffff0;
  tu2 = tu1 + 32;

  dtls_warn("signed: %d %d %d %d\n", ts1, ts2, (ts2 - ts1) > 0, (ts2 - ts1) < 0);
  dtls_warn("unsign: %u %u %d %d\n", tu1, tu2, (tu2 - tu1) > 0,  (tu2 - tu1) < 0);

Prints

signed: 2147483632 -2147483632 1 0
unsign: 2147483632 2147483664 1 0
signed: -16 16 1 0
unsign: 4294967280 16 1 0

I'm not sure, why (((clock_time_t)0 - 1) / 2) should be used?

[boaks]

I'm not sure, why (((clock_time_t)0 - 1) / 2) should be used?#

OK, it's not that simple as in java ;-).

[kfessel]

((offset + now - node->t) > offset

should be used
instead of

now - node->t > 0

since the later might lead into UB since singed overflow is not defined and might not work as expected if optimized and the compiler chose to do the substraction and the comparison on an larger type.
example:
loop1: is the working one (with magic offset) (magic offset can be written as ((T)~0)>>1 or ((T)0-1)/2)
loop2: works for signed values
loop3: is allways kindof wrong

the c off all loops is expected to equal the number of loops (300) or 0 (if TN_OFFSET if defined negative)

#include <stdio.h>
#include <stdint.h>

#define TN_OFFSET (50)

typedef uint8_t clock_time_t;

int main(void){
    volatile clock_time_t t = 0;
    volatile clock_time_t n = 0;
    const clock_time_t magic_offset = (((clock_time_t)~0) >> 1);
    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((clock_time_t)(magic_offset + n - t) < magic_offset){
            c++;
        }
    }
    printf("loop 1 c:%d \n", c);
    }

    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((clock_time_t)(n - t) < 0){
            c++;
        }
    }
    printf("loop 2 c:%d \n", c);
    }

    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((n - t) < 0){
            c++;
        }
    }
    printf("loop 3 c:%d \n", c);
    }

    printf("%d\n", magic_offset);
    
    return 0;
}

compiler explorer example

[obgm]

@kfessel did you have a change to check with PR #131 merged?

[kfessel]

Hi @obgm: since @boaks detected this issue though reading the code, I described it, @boaks developed the fixing PR (hence he solver what he read by writing) and I gave my cent to it (correct overflow handling regardless of singnedness).
I think we can consider this solved.
I never had a test for that other than reading. (I think this would require a Multiday session of DTLS)

[boaks]

I think, adding some unit test for the calculation may be an idea. But for now, there is too much other stuff already pending.

[obgm]

@kfessel sorry for the confusion