Problem with timecounters and memory model

[Konstantin Belousov]

On Fri, May 29, 2015 at 03:00:48PM +0200, Sebastian Huber wrote:
> Hello,
> 
> we ported the FreeBSD timecounters to the RTEMS real-time operating 
> system. On PowerPC with GCC 4.9 I noticed the following problem.  We have
> 
> void
> binuptime(struct bintime *bt)
> {
>      struct timehands *th;
>      u_int gen;
> 
>      do {
>          th = timehands;
>          gen = th->th_generation;
>          *bt = th->th_offset;
>          bintime_addx(bt, th->th_scale * tc_delta(th));
>      } while (gen == 0 || gen != th->th_generation);
> }
> 
> This is only valid if th->th_offset is read after th->th_generation and 
> the last write to th->th_generation is observable to all consumers 
> before the next write to th->th_offset etc.
> 
> On PowerPC we get the following code via GCC 4.9:
> 
> binuptime:
>      stwu 1,-32(1)     #,,
>      mflr 0     #,
>      stw 26,8(1)     #,
>      stw 0,36(1)     #,
>      stw 27,12(1)     #,
>      stw 28,16(1)     #,
>      stw 29,20(1)     #,
>      stw 31,28(1)     #,
>      stw 30,24(1)     #,
>      mr 30,3     # bt, bt
> .L41:
>      lwz 31,timehands at sdarel(13)     # timehands, th
>      lwz 28,0(31)     # th_3->th_counter, tc
>      lwz 8,40(31)     # th_3->th_offset, th_3->th_offset
>      lwz 9,0(28)     # tc_13->tc_get_timecount, tc_13->tc_get_timecount
>      mr 3,28     #, tc
>      lwz 10,44(31)     # th_3->th_offset, th_3->th_offset
>      lwz 6,32(31)     # th_3->th_offset, th_3->th_offset
>      mtctr 9     #, tc_13->tc_get_timecount
>      lwz 7,36(31)     # th_3->th_offset, th_3->th_offset
> 
> <- we read th_generation after th_offset
> 
>      lwz 27,64(31)     # th_3->th_generation, gen
>      stw 8,8(30)     # *bt_5(D), th_3->th_offset
>      stw 10,12(30)     # *bt_5(D), th_3->th_offset
>      stw 6,0(30)     # *bt_5(D), th_3->th_offset
>      stw 7,4(30)     # *bt_5(D), th_3->th_offset
>      lwz 26,20(31)     # th_3->th_scale, D.6097
>      lwz 29,16(31)     # th_3->th_scale, D.6097
>      bctrl     #
> 
> Adding a compiler memory barrier yields:
> 
> void
> binuptime(struct bintime *bt)
> {
>      struct timehands *th;
>      uint32_t gen;
> 
>      do {
>          th = timehands;
>          gen = th->th_generation;
>          __asm__ volatile("" ::: "memory");
>          *bt = th->th_offset;
>          bintime_addx(bt, th->th_scale * tc_delta(th));
>      } while (gen == 0 || gen != th->th_generation);
> }
> 
> binuptime:
>      stwu 1,-32(1)     #,,
>      mflr 0     #,
>      stw 26,8(1)     #,
>      stw 0,36(1)     #,
>      stw 27,12(1)     #,
>      stw 28,16(1)     #,
>      stw 29,20(1)     #,
>      stw 31,28(1)     #,
>      stw 30,24(1)     #,
>      mr 30,3     # bt, bt
> .L41:
>      lwz 31,timehands at sdarel(13)     # timehands, th
>      lwz 27,64(31)     # th_3->th_generation, gen
> 
> <- we read th_generation before th_offset
> 
>      lwz 28,0(31)     # th_3->th_counter, tc
>      lwz 9,44(31)     # th_3->th_offset, th_3->th_offset
>      lwz 8,36(31)     # th_3->th_offset, th_3->th_offset
>      mr 3,28     #, tc
>      lwz 10,40(31)     # th_3->th_offset, th_3->th_offset
>      lwz 7,32(31)     # th_3->th_offset, th_3->th_offset
>      stw 9,12(30)     # *bt_6(D), th_3->th_offset
>      lwz 9,0(28)     # tc_14->tc_get_timecount, tc_14->tc_get_timecount
>      stw 8,4(30)     # *bt_6(D), th_3->th_offset
>      mtctr 9     #, tc_14->tc_get_timecount
>      stw 10,8(30)     # *bt_6(D), th_3->th_offset
>      stw 7,0(30)     # *bt_6(D), th_3->th_offset
>      lwz 26,20(31)     # th_3->th_scale, D.6097
>      lwz 29,16(31)     # th_3->th_scale, D.6097
>      bctrl     #
> 
> This version seems to work at least on uni-processor systems. Shouldn't 
> there be real memory barriers the synchronize the reads/writes to 
> th_generation for SMP machines?

Yes, you are right. It is probably somewhat correct only on TSO
architectures, i.e. x86 and sparc64. Even there, it is 'somewhat' since
compilers can reorder the accesses.

I was unable to convince myself to leave the code as-is when I coded
the shared-page access to the timehands from usermode.  Please take
a look at the lib/libc/sys/__vdso_gettimeofday.c:binuptime().  The
normal FreeBSD' atomics ops could not be used there due to cmpxcgh
requiring a writeable memory.