long time reader, first time poster.
I have a serial link between a sensor and a base station via bluetooth. The bluetooth link is incredibly unreliable and drops packets like you wouldnt believe. I'm using this as a positive and going to design a robust serial protocol that can survive a shit link.
Just wanna bounce some ideas off of people as i'm the only embedded developer in the office.
Plan is to use byte stuffing to create packets with start (STX) and end (ETX) bytes, index number and CRC. Am planning on using an escape character (DLE) when the STX and ETX and DLE characters come up. That part is all pretty clear and here is said code that should do that
static void SendCommand(struct usart_module * const usart_module, uint16_t cmd,
uint8_t *data, uint8_t len)
{
//[STX] ( { [IDX] [CMD_H] [CMD_L] [LEN] ...[DATA]... } [CRC] ) [ETX] // Data in {} brackets is XORed together for the CRC. // Data in () is the packet length
static uint8_t idx;
uint8_t packet[256];
uint8_t crc, packetLength, i;
if (len > 250)
return;
packetLength = len + 5;
packet[0] = idx++;
packet[1] = (cmd >> 8);
packet[2] = (cmd & 0x00FF);
packet[3] = packetLength;
crc = 0;
for (i = 0; i <= 3; i++)
{
crc ^= packet[i];
}
for (i = 0; i < len; i++)
{
packet[4 + i] = data[i];
crc ^= data[i];
}
packet[4 + len] = crc;
// Send Packet
uart_putc(usart_module, STX);
for (i = 0; i < packetLength; i++)
{
if ((packet[i] == STX) || (packet[i] == ETX) || (packet[i] == DLE))
{
uart_putc(usart_module, DLE);
}
uart_putc(usart_module, packet[i]);
}
uart_putc(usart_module, ETX);
}
So that will send a packet, but now i need to add some code to keep track of the packets and retransmit the failed ones automatically and thats where i need some help with some ideas.
Couple options i had; -Easiest, assign a giant array of 256 packets, each with enough room to store a packet and after transmitting the packet, put it in the buffer and if i dont receive an ACK after x amount of time, transmit it again. Then if i do receive an ACK, delete that record from the array so that entry is blank so i know it got received just fine.
Issue with that is that if i use the worst case packet size of 256 bytes, and 256 instances of them, thats 64K of RAM and i dont have that (and even if i did, thats a terrible idea)
-Next idea, create a linked list of all the packets and dynamically assign memory using the malloc commands etc. and remove the ones that got acknowledged, and keep the ones that havent so i know which to retransmit after x time.
Issues i have with that is the entire malloc idea. Truthfully, i've never used it and i dont like the idea of using it in an embedded environment with limited memory. Maybe thats just me being silly, but i feel like thats opening the door to a bucket load of other problems i dont need.
-Potential solution, create a linked list for all packets like mentioned above, but create them in a fifo, and move all the records around to keep them in the fifo.
e.g.
send packet 1, put packet in in the fifo
send packet 2, put packet in in the fifo
receive NACK for packet 1, do nothing
send packet 3, put packet in in the fifo
receive ACK for packet 2, memset packet 2 to 0x00 in fifo
receive ACK for packet 3, memset packet 2 to 0x00 in fifo
send packet 4, put packet in in the fifo
send packet 5, put packet in in the fifo
no more room in FIFO, go through and shuffle everything to the front because where packet 2 and 3 were is empty now.
Could keep them shuffled in real time, but then we need to shuffle a whole fifo after every packet received and that seems like a lot of unnecessary work?
What i'm looking for is for one of you to say "Jeez Ned, thats not bad, but if you just do xyz, then that saves you heaps of work or RAM or complexity" or something.
Just want a couple people to bounce ideas off of really as thats how you generally get the best solution. I like my solution, but i feel like i'm missing something, or am over complicating it maybe? not sure... i just dont feel 100% happy with this idea i dont think, but just cant think of a better way.
You don't need to use malloc. Just statically allocate all your packets, perhaps as an array of struct. But don't use the array to iterate through the packets at run time. Rather, expand upon your linked-list idea. Create two lists, one for packets awaiting an ACK and another for free (i.e. available) packets. At startup, add every packet to the free-list. When you send a packet, remove it from the free-list and add it to the awaiting-ACK list. Make the awaiting-ACK list doubly-linked so that you can remove a packet from the middle of the list and return it to the free-list.
If your packet size varies greatly and you want to support more packets with less memory then you can create multiple free-lists for different sized packets. For example, the max-size-free-list holds the largest packets while the economy-size-free-list holds the smaller packets. The awaiting-ACK list can hold both sizes as long as it can be known which free-list to return the packets to. And that can be known by adding a flag to the packet struct.
typedef enum PacketSizeType
PACKET_SIZE_MAX = 0,
PACKET_SIZE_ECONOMY
} PacketSizeType;
typedef struct PacketBase{
PacketBase * next;
PacketBase * prev;
PacketSizeType type;
uint8_t data[1]; // a place holder (must be last)
} PacketBase;
typedef struct PacketMax
{
PacketBase base; // inherit from PacketBase (must be first)
uint8_t data[255];
} PacketMax;
typedef struct PacketEconomy
{
PacketBase base; // inherit from PacketBase (must be first)
uint8_t data[30];
} PacketEconomy;
PacketMax MaxSizedPackets[100];
PacketEconomy EconomySizedPackets[100];
Packet *free_list_max;
Packet *free_list_economy;
Packet *awaiting_ack_list;
The initialization code should cycle through both arrays, set the base.type member to either MAX or ECONOMY, and add the packet to the appropriate free-list. The transmit code gets a packet from the appropriately sized free-list and moves it to the awaiting-ACK list. The awaiting-ACK list can contain both types of packets because they both inherit from the PacketBase. The ACK handler code should check base.type to return the packet to the appropriate free-list.