Getting stuck with tickless mode

ChibiOS public support forum for topics related to the STMicroelectronics STM32 family of micro-controllers.

Moderator: RoccoMarco

szmodz
Posts: 11
Joined: Thu Jul 11, 2013 1:07 am
Been thanked: 1 time

Re: Getting stuck with tickless mode

Post by szmodz »

It's not a compiler bug, it's a code bug. The code violates C aliasing rules.

The type of ch.vtlist is virtual_timers_list_t, while vt_next / vt_prev point to virtual_timer_t.

The compiler assumes that a pointer to virtual_timer_t cannot point to a virtual_timers_list_t, as they are different types. This is correct (according to the C standard) compiler behavior.

I already linked this in another thread:

http://dbp-consulting.com/tutorials/StrictAliasing.html

The page mentions a correct solution

An aggregate (struct or class) or union type can alias types contained inside them. (Example: If a function gets passed a pointer to an int, and a pointer to a struct or union containing an int, or possibly containing another struct or union containing an int, or containing...ad infinitum, it's possible that the int* points to an int contained inside the struct or union pointed at by the other pointer.)


Code: Select all

struct ch_virtual_timer_list_node {
  virtual_timer_t       *vt_next;   /**< @brief Next timer in the list.     */
  virtual_timer_t       *vt_prev;   /**< @brief Previous timer in the list. */
  systime_t             vt_delta;   /**< @brief Time delta before timeout.  */
};


Put that as a member in virtual_timers_list_t and virtual_timer_t and it should work without barriers.
Last edited by szmodz on Tue Mar 31, 2015 5:53 pm, edited 1 time in total.
User avatar
Giovanni
Site Admin
Posts: 14892
Joined: Wed May 27, 2009 8:48 am
Has thanked: 1202 times
Been thanked: 996 times

Re: Getting stuck with tickless mode

Post by Giovanni »

I agree and was fixing the code under that assumption, now I made the thing evident to the compiler this way:

Code: Select all

void chVTDoResetI(virtual_timer_t *vtp) {

  chDbgCheckClassI();
  chDbgCheck(vtp != NULL);
  chDbgAssert(vtp->vt_func != NULL, "timer not set or already triggered");

  /* The delta of the timer is added to the next timer.*/
  vtp->vt_next->vt_delta += vtp->vt_delta;

#if CH_CFG_ST_TIMEDELTA == 0
  /* Removing the element from the delta list.*/
  vtp->vt_prev->vt_next = vtp->vt_next;
  vtp->vt_next->vt_prev = vtp->vt_prev;
  vtp->vt_func = NULL;

  /* The above code changes the value in the header when the removed element
     is the last of the list, restoring it.*/
  ch.vtlist.vt_delta = (systime_t)-1;
#else /* CH_CFG_ST_TIMEDELTA > 0 */
  systime_t nowdelta, delta;

  /* If the timer is not the first of the list then it is simply unlinked
     else the operation is more complex.*/
  if (ch.vtlist.vt_next != vtp) {
    /* Removing the element from the delta list.*/
    vtp->vt_prev->vt_next = vtp->vt_next;
    vtp->vt_next->vt_prev = vtp->vt_prev;
    vtp->vt_func = NULL;

    /* The above code can change the value in the header when the removed
       element is the last of the list, restoring it.*/
    ch.vtlist.vt_delta = (systime_t)-1;

    return;
  }

  /* Removing the first timer from the list.*/
  ch.vtlist.vt_next = vtp->vt_next;
  ch.vtlist.vt_next->vt_prev = (virtual_timer_t *)&ch.vtlist;

  /* The above code can change the value in the header when the removed
     element is the last of the list, restoring it.*/
  ch.vtlist.vt_delta = (systime_t)-1;

  /* If the list is empty then the alarm timer is stopped.*/
  if (&ch.vtlist == (virtual_timers_list_t *)ch.vtlist.vt_next) {
    port_timer_stop_alarm();
    return;
  }

  /* If the new first element has a delta of zero then the alarm is not
     modified, the already programmed alarm will serve it.*/
  if (ch.vtlist.vt_next->vt_delta == 0) {
    return;
  }

  /* Distance in ticks between the last alarm event and current time.*/
  nowdelta = chVTGetSystemTimeX() - ch.vtlist.vt_lasttime;

  /* If the current time surpassed the time of the next element in list
     then the event interrupt is already pending, just return.*/
  if (nowdelta >= ch.vtlist.vt_next->vt_delta) {
    return;
  }

  /* Distance from the next scheduled event and now.*/
  delta = ch.vtlist.vt_next->vt_delta - nowdelta;

  /* Making sure to not schedule an event closer than CH_CFG_ST_TIMEDELTA
     ticks from now.*/
  if (delta < (systime_t)CH_CFG_ST_TIMEDELTA) {
    delta = (systime_t)CH_CFG_ST_TIMEDELTA;
  }

  port_timer_set_alarm(ch.vtlist.vt_lasttime + nowdelta + delta);
#endif /* CH_CFG_ST_TIMEDELTA > 0 */
}


In this version ch.vtlist.vt_next is never changed in an hidden way and it is working.

I am testing on an F4 with systick at 1MHz and delta = 6, this allows resolutions of about 10uS, very close to the intrinsic jitter.

Giovanni
szmodz
Posts: 11
Joined: Thu Jul 11, 2013 1:07 am
Been thanked: 1 time

Re: Getting stuck with tickless mode

Post by szmodz »

I think it's still incorrect. I edited my last reply to include a correct solution.

Define another struct containing the common elements of both virtual_timer_t and virtual_timers_list_t and place that as a member in both.

Code: Select all

ch.vtlist.vt_next->vt_prev = (virtual_timer_t *)&ch.vtlist;


Code: Select all

  /* If the list is empty then the alarm timer is stopped.*/
  if (&ch.vtlist == (virtual_timers_list_t *)ch.vtlist.vt_next) {
    port_timer_stop_alarm();
    return;
  }


Still looks wrong, and will break sooner or later.
User avatar
Giovanni
Site Admin
Posts: 14892
Joined: Wed May 27, 2009 8:48 am
Has thanked: 1202 times
Been thanked: 996 times

Re: Getting stuck with tickless mode

Post by Giovanni »

I see, that assumption about equivalence of structures is not used just in timers, also other kind of lists like threads. This function broke because the changes that I did yesterday to the tickless path, now the change to the timers header is explicit, I think it is safe.

The problem was removing the element using its pointer then access the same list again using the header, this violated the aliasing rules, now the access to the list is only performed after removing the element starting from the header, there are two separate codepaths.

Node structures are a good idea anyway, I will reserve it for the next major rework in the kernel, those are already used in some objects like semaphores, mutexes, condvars etc so it makes sense to extend them.

I committed this version for tests.

Giovanni
steved
Posts: 834
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 12 times
Been thanked: 138 times

Re: Getting stuck with tickless mode

Post by steved »

FYI the previous version (with assertion in line 480 commented out) ran with no problems for 51 hours.

Applied the very latest updates about 2 hours ago. Have done two test runs, and in both cases it halted with 'stStopAlarm' within 10-20 minutes.

It may be relevant that the ChibiOs plugin is showing zero active timers, which is wrong - as a minimum, my main loop is a simple while (1)chThdSleepMilliseconds(500);

This happened off a USART received character interrupt; probably the first of a new message. Thus it would be starting a 'stopped' timer (which is then retriggered on successive received characters).

Any other information I can extract for you?
User avatar
Giovanni
Site Admin
Posts: 14892
Joined: Wed May 27, 2009 8:48 am
Has thanked: 1202 times
Been thanked: 996 times

Re: Getting stuck with tickless mode

Post by Giovanni »

This is very wrong, it looks like something happened when the last timers has been removed, it stops when the list is empty by calling stStopAlarm() twice for some reason...

My test case did not trigger this.

Giovanni
User avatar
Giovanni
Site Admin
Posts: 14892
Joined: Wed May 27, 2009 8:48 am
Has thanked: 1202 times
Been thanked: 996 times

Re: Getting stuck with tickless mode

Post by Giovanni »

Hi Steved,

Are you sure it is "stStopAlarm"? I am asking because that function does not have an assertion. Please post the full stack trace if you can.

Giovanni
steved
Posts: 834
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 12 times
Been thanked: 138 times

Re: Getting stuck with tickless mode

Post by steved »

Giovanni wrote:Hi Steved,

Are you sure it is "stStopAlarm"? I am asking because that function does not have an assertion. Please post the full stack trace if you can.

Giovanni

Sorry, was falling asleep when I wrote that - it was stStartAlarm.

Here's stack trace as well.
Stack trace leading to stStartAlarm
Stack trace leading to stStartAlarm
Call_Stack_010415.png (15.25 KiB) Viewed 6538 times
User avatar
Giovanni
Site Admin
Posts: 14892
Joined: Wed May 27, 2009 8:48 am
Has thanked: 1202 times
Been thanked: 996 times

Re: Getting stuck with tickless mode

Post by Giovanni »

Thanks, I am working on creating better tests for this beast.

Is the UART interrupt at higher priority than systick? this would explain the problem: UART preempts systick after the list has been emptied but the alarm is still active, then the UART callback calls chVTSetI() and the alarm is started again triggering the assertion.

Easily fixed, tomorrow I will commit this fix and other general improvements to tickless mode.

Giovanni
steved
Posts: 834
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 12 times
Been thanked: 138 times

Re: Getting stuck with tickless mode

Post by steved »

Giovanni wrote:Thanks, I am working on creating better tests for this beast.

Is the UART interrupt at higher priority than systick? this would explain the problem: UART preempts systick after the list has been emptied but the alarm is still active, then the UART callback calls chVTSetI() and the alarm is started again triggering the assertion.
Giovanni

I wondered that. Thought it was OK, but maybe I'm reading the numbers wrong.

Pretty much everything is as the 32F051 Discovery demo unless I had good reason to change it.
#define STM32_ST_IRQ_PRIORITY 2
#define STM32_ST_USE_TIMER 2
#define STM32_UART_USART1_IRQ_PRIORITY 3
#define STM32_UART_USART2_IRQ_PRIORITY 3
Post Reply