[DOC] Please document how the synchronisation works

[davidchisnall]

The synchronisation in the waiting packet lists is incredibly subtle. I believe it is probably correct and the requirements are:

• Insertions and removals must be atomic operations (interrupts disabled)
• Traversal is not atomic but does not delete the list objects.

Even after reading the code five times, I am still not 100% sure because listGET_OWNER_OF_NEXT_ENTRY non-atomically mutates the pxIndex field of the list, but vListInsertEnd uses this value, and so even if vListInsertEnd is atomic, it can happen in the middle of the update of pxIndex. If this were incorrect, I think it would lead to memory leaks and have been detected, so I presume it is correct, but it's incredibly hard to determine this from the code / comments. Some comments around the vTaskSuspendAll / taskENTER_CRITICAL calls (for example, here) explaining what this needs to be atomic with respect to and what the invariants are would help.

It would be great to have some comments in the code (or a higher-level design doc) explaining why this is safe.

[htibosch]

Thanks for raising this subject. I read it with great interest and I will come back to it here.
One question: did you find an issue with List access, or is it more a theoretical interest?

[davidchisnall]

Thanks for raising this subject. I read it with great interest and I will come back to it here.

Thank you!

One question: did you find an issue with List access, or is it more a theoretical interest?

I did not find an issue, but I was trying to convince myself that there wasn't one and failing.

I am not quite sure what I'd expect to go wrong in the racy case. It's either a memory leak, or some packets not being processed because iterators skip over them. In the latter case, higher-level parts of the stack will correct and simply treat it as packet loss (though I'm not quite sure what would free it in that case).

If the contention is sufficiently rare then it's possible that it does show up in production occasionally and just results in one buffer being lost, then it may not be noticed. The probability of hitting the problematic cases looks very low (the producer and consumer threads are each doing tens of thousands of cycles work and need to both hit the wrong point - a window of a handful of instructions - at the same time).

[moninom1]

Hi @davidchisnall

Thank you for raising the request. We are looking into it and will add the required documentation soon. Thank you

[htibosch]

Summary:

In two cases, the scheduler is suspended:

1. When a new UDP packet is received and inserted into xWaitingPacketsList.
2. A packet is removed from xWaitingPacketsList and passed to the user.

Critical sections are created as well, but suspending the scheduler would be enough.

The scheduler is not suspended in these cases:

• Unprotected access to read UBaseType_t uxNumberOfItems, which is assumed to be an atomic access.
• Unprotected access during creation and during deletion of he socket.

Details:

In this analysis, I only looked at the List_t xWaitingPacketsList, the list that stores incoming UDP packets.

EDIT
A module like FreeRTOS_TCP_WIN.c uses List_ts to store information about the TCP sliding windows. As it has sole access, no protection is needed.

Within FreeRTOS+TCP, sockets can not be shared among tasks, except when one task is reading, and the other task is writing to it.
When a socket is shared among a reader/and a writer task, the application programmer is responsible to synchronise the closure of the socket.

During FreeRTOS_socket() and vSocketClose(), it it assumed that the socket is not used in the application. vSocketClose() removes all received UDP packets, with any protection.

// FreeRTOS_Sockets.c : List initialisation
Socket_t FreeRTOS_socket()
{
    vListInitialise( &( pxSocket->u.xUDP.xWaitingPacketsList ) );
}

// List deletion, along with the received packets.
void * vSocketClose( FreeRTOS_Socket_t * pxSocket )
{
    // Socket is closing, remove/delete received packets
    while( listCURRENT_LIST_LENGTH( &( pxSocket->u.xUDP.xWaitingPacketsList ) ) > 0U )
    {
        pxNetworkBuffer = ( ( NetworkBufferDescriptor_t * ) listGET_OWNER_OF_HEAD_ENTRY( &( pxSocket->u.xUDP.xWaitingPacketsList ) ) );
        ( void ) uxListRemove( &( pxNetworkBuffer->xBufferListItem ) );
        vReleaseNetworkBufferAndDescriptor( pxNetworkBuffer );
    }
}

Access from xProcessReceivedUDPPacket_IPv4() and xProcessReceivedUDPPacket_IPv6():

First read how many packets are stored already

#if ( ipconfigUDP_MAX_RX_PACKETS > 0U )
{
    if( xReturn == pdPASS )
    {
        // Reading length field
        // Looks atomic "UBaseType_t uxNumberOfItems"
        if( listCURRENT_LIST_LENGTH( &( pxSocket->u.xUDP.xWaitingPacketsList ) ) >= pxSocket->u.xUDP.uxMaxPackets )
        {
            // No space.
            xReturn = pdFAIL; /* we did not consume or release the buffer */
        }
    }
}

Both the addition as well as removal of packets is protected in a critical section. The taskENTER_CRITICAL()/taskEXIT_CRITICAL() are not useful because xWaitingPacketsList will never be accessed from an interrupt.

if( xReturn == pdPASS )
{
    vTaskSuspendAll();
    {
        taskENTER_CRITICAL();
        {
            /* Add the network packet to the list of packets to be
             * processed by the socket. */
            vListInsertEnd( &( pxSocket->u.xUDP.xWaitingPacketsList ), &( pxNetworkBuffer->xBufferListItem ) );
            /* Here it is assumed that xRxSegments.pxIndex points to xListEnd. */
        }
        taskEXIT_CRITICAL();
    }
    ( void ) xTaskResumeAll();
}

Called from recvfrom(), receive UDP packet and remove it from list.

static NetworkBufferDescriptor_t * prvRecvFromWaitForPacket( FreeRTOS_Socket_t const * pxSocket,
                                                             BaseType_t xFlags,
                                                             EventBits_t * pxEventBits )
{
    if( lPacketCount > 0 )
    {
        // A block protected by vTaskSuspendAll()/xTaskResumeAll() would be good enough here.
        taskENTER_CRITICAL();
        {
            /* The owner of the list item is the network buffer. */
            // Get the oldest item, which is "xListEnd->pxNext->pvOwner"
            pxNetworkBuffer = ( ( NetworkBufferDescriptor_t * ) listGET_OWNER_OF_HEAD_ENTRY( &( pxSocket->u.xUDP.xWaitingPacketsList ) ) );
    
            if( ( ( UBaseType_t ) xFlags & ( UBaseType_t ) FREERTOS_MSG_PEEK ) == 0U )
            {
                /* Remove the network buffer from the list of buffers waiting to
                 * be processed by the socket. */
                ( void ) uxListRemove( &( pxNetworkBuffer->xBufferListItem ) );
            }
        }
        taskEXIT_CRITICAL();
    }
}

Reading length field
Looks atomic "UBaseType_t uxNumberOfItems"

void vSocketSelect( const SocketSelect_t * pxSocketSet )
{
    /* Select events for UDP are simpler. */
    if( ( ( pxSocket->xSelectBits & ( EventBits_t ) eSELECT_READ ) != 0U ) &&
        ( listCURRENT_LIST_LENGTH( &( pxSocket->u.xUDP.xWaitingPacketsList ) ) > 0U ) )
    {
        xSocketBits |= ( EventBits_t ) eSELECT_READ;
    }
}

My recommendation is the following:

 vTaskSuspendAll();
 {
-    taskENTER_CRITICAL();
-    {
         /* Remove (or add) an item from xUDP.xWaitingPacketsList. */
-    }
-    taskEXIT_CRITICAL();
 }
 ( void ) xTaskResumeAll();

[davidchisnall]

Thanks for the detailed write-up, that's great.

I presume that the close case also relies on packets destined for that socket being dropped rather than being added to the waiting list, as a result of updating the socket state machine?

[htibosch]

I'm afraid I do not understand exactly what you're asking for.

UDP messages aren't stored anywhere, except in the short moment between the IP-task function xProcessReceivedUDPPacket() and FreeRTOS_recvfrom().

Network interface calls xSendEventStructToIPTask() for an eNetworkRxEvent event.
The IP-task calls xProcessReceivedUDPPacket(), which may add ( or drop ) the UDP packet.

The user process calls the function FreeRTOS_recvfrom() and uses a critical section to access the list xWaitingPacketsList. This was not implemented as an API to get faster responses.

[amazonKamath]

@davidchisnall closing this issue since the PR addressing the critical section is merged. Please re-open if you have further questions. Thank you.