Consider indexing the RX payload fragments by offset

[pavel-kirienko]

This is needed to allow logarithmic buffer indexing time as opposed to linear that is available currently. LibUDPard traverses the fragment tree once, during the transfer finalization, to build the linked list of fragments:

libudpard/libudpard/udpard.c

Lines 1044 to 1097 in 6c7c12e

	/// This function finalizes the fragmented transfer payload by doing multiple things in one pass through the tree:
	///
	/// - Compute the transfer-CRC. The caller should verify the result.
	/// - Build a linked list of fragments ordered by frame index, as the application would expect it.
	/// - Truncate the payload according to the specified size limit.
	/// - Free the tree nodes and their payload buffers past the size limit.
	///
	/// It is guaranteed that the output list is sorted by frame index. It may be empty.
	/// After this function is invoked, the tree will be destroyed and cannot be used anymore;
	/// hence, in the event of invalid transfer being received (bad CRC), the fragments will have to be freed
	/// by traversing the linked list instead of the tree.
	///
	/// The payload shall contain at least the transfer CRC, so the minimum size is TRANSFER_CRC_SIZE_BYTES.
	/// There shall be at least one fragment (because a Cyphal transfer contains at least one frame).
	///
	/// The return value indicates whether the transfer is valid (CRC is correct).
	static inline bool rxSlotEject(size_t* const out_payload_size,
	struct UdpardFragment* const out_payload_head,
	RxFragmentTreeNode* const fragment_tree,
	const size_t received_total_size, // With CRC.
	const size_t extent,
	const RxMemory memory)
	{
	UDPARD_ASSERT((received_total_size >= TRANSFER_CRC_SIZE_BYTES) && (fragment_tree != NULL) &&
	(out_payload_size != NULL) && (out_payload_head != NULL));
	bool result = false;
	RxSlotEjectContext eject_ctx = {
	.head = NULL,
	.predecessor = NULL,
	.crc = TRANSFER_CRC_INITIAL,
	.retain_size = smaller(received_total_size - TRANSFER_CRC_SIZE_BYTES, extent),
	.offset = 0,
	.memory = memory,
	};
	rxSlotEjectFragment(fragment_tree->this, &eject_ctx);
	UDPARD_ASSERT(eject_ctx.offset == received_total_size); // Ensure we have traversed the entire tree.
	if (TRANSFER_CRC_RESIDUE_BEFORE_OUTPUT_XOR == eject_ctx.crc)
	{
	result = true;
	*out_payload_size = eject_ctx.retain_size;
	*out_payload_head = (eject_ctx.head != NULL)
	? (*eject_ctx.head) // Slice off the derived type fields as they are not needed.
	: (struct UdpardFragment){.next = NULL, .view = {0, NULL}, .origin = {0, NULL}};
	// This is the single-frame transfer optimization suggested by Scott: we free the first fragment handle
	// early by moving the contents into the rx_transfer structure by value.
	// No need to free the payload buffer because it has been transferred to the transfer.
	memFree(memory.fragment, sizeof(RxFragment), eject_ctx.head); // May be empty.
	}
	else // The transfer turned out to be invalid. We have to free the fragments. Can't use the tree anymore.
	{
	rxFragmentDestroyList(eject_ctx.head, memory);
	}
	return result;
	}

In the process it discards the fragment metadata; the discarded metadata includes the fragment tree linking where the fragments are ordered by the frame index (from zero up to the transfer fragment count):

libudpard/libudpard/udpard.c

Lines 808 to 815 in 6c7c12e

	/// This is designed to be convertible to/from UdpardFragment, so that the application could be
	/// given a linked list of these objects represented as a list of UdpardFragment.
	typedef struct RxFragment
	{
	struct UdpardFragment base;
	RxFragmentTreeNode tree;
	uint32_t frame_index;
	} RxFragment;

The discardment is done by slicing off the metadata fields. We could enhance the publicly visible struct UdpardFragment with the tree-related fields to allow the user to choose whether the fragments should be indexed linearly as a linked list or logarithmically through the tree. Now, in order to implement the latter the tree should be indexed by offset rather than the frame index (the client doesn't care about the frame index, it's a very low-level trait); however, a tree ordered by frame index is obviously identical to a tree ordered by the offset (formal proof anyone?). LibUDPard will only need to initialize the offset fields while building the linked list -- it is also done in the same single pass.

@serges147 FYI

[serges147]

Just as a memo here is what I see needs to be done at high/API level:

• introduce another version of udpardGather which supports extra offset_bytes parameter:
  • Signature will be like

    size_t udpardGather(const struct UdpardFragment head,
                        const size_t offset_bytes,
                        const size_t destination_size_bytes,
                        void* const destination,
                        struct UdpardFragment** hint) 
    

  • New offset_bytes param will be used to find (in the exposed tree as described above by @pavel-kirienko) proper start fragment which contains first required byte of data.
  • New optional (could be null) hint param could be used as a "hint" for subsequent accesses. If not null then on return it will be filled with address of the last fragment node (according to offset_bytes + destination_size_bytes position) encountered. This will allow to make subsequent/continuous forward only accesses faster b/c there will be no need to find starting fragment on a next udpardGather call. We will fallback to normal (O(log(N)) tree search if hint is not provided or out of sync with offset_bytes.
• Extend struct UdpardFragment with extra fields so that in addition to current linear list there will be also the tree node exposed.
• Currently existing more simple udpardGather will stay as is: always starting from zero offset, and using single linked list of nodes to progress from the head up to destination_size_bytes copied).

@pavel-kirienko Does it sounds good?