Bug in nrf_sortlist

[nrbrook]

I use App timer V2 in the nRF5 SDK and sometimes (not sure of the circumstances) it will insert a timer into the internal m_app_timer_sortlist that is already present in the list. With the nrf_sortlist implementation in nRF5 SDK 17.1.0 this sets the item's p_next to point to itself, and then the next time an item is added into the sortlist, nrf_sortlist_add gets stuck in the while loop. Here is my modification to resolve it:

void nrf_sortlist_add(nrf_sortlist_t const * p_list, nrf_sortlist_item_t * p_item)
{
    ASSERT(p_list);
    ASSERT(p_item);

    nrf_sortlist_item_t ** pp_curr = &(p_list->p_cb->p_head);


    while(*pp_curr != NULL)
    {
        if(*pp_curr == p_item) {
            NRF_LOG_INFO("List:%s, adding duplicate item:%08X, removing then re-adding to ensure order", p_list->p_name, p_item);
            // remove from list
            *pp_curr = p_item->p_next;
            // ensure we can't get stuck in a loop if item pointed to itself
            p_item->p_next = NULL;
            // restart
            pp_curr = &(p_list->p_cb->p_head);
        }
        if(!(p_list->compare_func(*pp_curr, p_item)))
        {
            // pp_curr (pointer to current next pointer) pointer value is higher than p_item, break
            break;
        }
        pp_curr = &((*pp_curr)->p_next);

        if(*pp_curr == p_list->p_cb->p_head) {
            // should never happen
            NRF_LOG_ERROR("List:%s, returned to list head, could not insert", p_list->p_name);
            return;
        }
    }

    // p_item next pointer is current item next pointer
    p_item->p_next = *pp_curr;
    // pp_curr next pointer should be p_item
    *pp_curr = p_item;

#if NRF_LOG_LEVEL >= 3
    nrf_sortlist_item_t *prev = NULL;
    if(pp_curr != &(p_list->p_cb->p_head)) {
        prev = (nrf_sortlist_item_t *)((uint8_t *)pp_curr - offsetof(nrf_sortlist_item_t, p_next));
    }

    NRF_LOG_INFO("List:%s, adding element:%08X after:%08X, before:%08X",
                                  p_list->p_name, p_item, prev, p_item->p_next);
#endif
}

[Federico]

Hi,

I'm also encountering the same error, which is a bit weird considering they had a nearly identical bug in the previous implementation. I read your fix and I have a question: since you "break" when you find the place in the list to insert, aren't you missing the case where the timer is already in the list but the new insert location is reached before reaching the timer, so you don't remove it? I think you need to go through the whole list every time.

Thanks!

[nrbrook]

The list is sorted from low to high, so if the next value is higher than p_item then any of the remaining unchecked items in the list will not be p_item.

[Federico]

Great! thanks!

[Federico]

Wait, follow up question. Couldn't it be possible that the timer end_val got assigned again to a smaller value but the place in the list is still the same when nrf_sortlist_add is called?

Take this code for example. Here end_val gets modified and then nrf_sortlist_add is called. In this case, the end_val is incremented, but if it were decremented, wouldn't this cause what I said?

/* check active flag as it may have been stopped in the user handler */
if (p_timer->repeat_period && !APP_TIMER_IS_IDLE(p_timer))
{
    p_timer->end_val += p_timer->repeat_period;
    cont = true;
}
else
{
    cont = false;
}
CRITICAL_REGION_EXIT();

if (cont)
{
    nrf_sortlist_add(&m_app_timer_sortlist, &p_timer->list_item);
    ret = true;
}

[nrbrook]

yes, probably. I haven't looked at the code in a while but that would make sense.