32bit overflow does not work  #125

Activity

1. kfessel commented on Feb 7, 2022

   

   kfessel

   on Feb 7, 2022

   Last edited by kfessel

   Author

   More actions

   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)
2. kfessel commented on Feb 7, 2022

   

   kfessel

   on Feb 7, 2022

   Author

   More actions

   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)
3. boaks commented on Mar 29, 2022

   

   boaks

   on Mar 29, 2022

   Contributor

   More actions

   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?
4. boaks commented on Mar 29, 2022

   

   boaks

   on Mar 29, 2022

   Contributor

   More actions

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

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

   👍React with 👍1Reacted by Karl Fessel
5. kfessel commented on Mar 29, 2022

   

   kfessel

   on Mar 29, 2022

   Last edited by kfessel

   Author

   More actions

   ((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)

   Details

   #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
6. boaks

   added 5 commits that reference this issue on Mar 29, 2022

   dtls.c, netq.c: consider 32bit time overflow.

   ...

   544c37f

   dtls.c, netq.c: consider 32bit time overflow.

   ...

   2ec3051

   dtls.c, netq.c: consider 32bit time overflow.

   ...

   dd8affc

   dtls.c, netq.c: consider 32bit time overflow.

   ...

   9fb395d

   dtls.c, netq.c: consider 32bit time overflow.

   ...

   cde751a
7. obgm commented on May 27, 2022

   

   obgm

   on May 27, 2022

   Contributor

   More actions

   @kfessel did you have a change to check with PR #131 merged?
8. kfessel commented on May 27, 2022

   

   kfessel

   on May 27, 2022

   Author

   More actions

   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)
9. boaks commented on May 27, 2022

   

   boaks

   on May 27, 2022

   Contributor

   More actions

   I think, adding some unit test for the calculation may be an idea. But for now, there is too much other stuff already pending.
10. obgm commented on May 27, 2022

    

    obgm

    on May 27, 2022

    Contributor

    More actions

    @kfessel sorry for the confusion