For heaven’s sake, stop creating big endian protocols!

This post does not reflect the views of current, past, or future employers. The opinions in this article are my own.

In Unraveling the Endianness Mess we discussed endianness and how the industry managed to arrive at what I call “The great discrepancy” — most CPU architectures are little endian, but Internet protocols are big endian. For the most part we’ve accepted the discrepancy as a part of life, and for the most part programmers never need to worry about it, and for the most part endianness doesn’t matter as the cost of doing endianness conversion, i.e. byte swap, is insignificant. Hmm, that’s a lot of “for the most part”s! The reality is that the endianness war was never truly settled and it still pops up as an issue as we saw in Linux last week.

Can we elimiate the need and cost for byte swaps on protocol fields?

Big endian in RISC-V and the Linux push back

RISC-V has support for big endian but it’s not widely supported in commercial software so they want to change that. The operative quote from the riscv.org web site is:

There are still applications where the way data is stored matters, such as the protocols that move data across the Internet, which are defined as big-endian. So when a little-endian system needs to inspect or modify a network packet, it has to swap the big-endian values to little-endian and back, a process that can take as many as 10–20 instructions on a RISC-V target which doesn’t implement the Zbb extension

Patches to fix Linux to support RISC-V big endian were proposed, and apparently Linus Torvalds is pushing back. Of course, when Linus pushes back he doesn’t mince words! Here’s what he said:

Seriously, that sounds like just stupid. Is there some actual real reason for this, or is it more of the “RISC-V is used in academic design classes and so people just want to do endianness for academic reasons”?

Let’s not complicate things for no good reason. And there is NO reason to add new endianness.

Linus even quoted the RISC-V blurb above and said in response:

In other words, it is suggesting that RISC-V add a big-endian mode due to

(a) internet protocols — where byte swapping is not an issue

(b) using “some RISC-V implementations don’t do the existing Zbb extension” as an excuse

I’m going to side with Linus on this one. The only reason to introduce new endianess, i.e. big endian, in an architecture is for compatibility with Internet protocols. Supporting big endian is non-trivial, and the Zbb extension addresses the 10–20 instructions cost on RISC-V targets.

While I may agree with Linus, I don’t believe it’s the end of the story. The discrepancy between CPU and protocol endianness is an issue. It becomes evident in transport protocols in AI/ML where performance requirements are so stringent that even byte swaps can materially degrade performance. But it’s not just byte swaps, dealing with bit fields for different bit endianances between CPUs and protocols is potentially an even bigger performance hit. I believe we need a fix, but the RISC-V guys are barking up the wrong tree!

Big endian is wrong endian!

After writing about endianness, I continued to think about the problem and how we wound up with this mess. The one question I kept asking myself is whether there is a substantive technical difference that would tell us which endianness is better. All the literature seems to think there is no difference. Disregarding endianness conversion, arithmetic operations on words work with equal efficiency between little endian and big endian architectures such that the programmer never needs to worry about endianness. But that only considers endianness for individual words, what about values that are larger than the word size of the machine? Does the choice of endianness matter for them?

Endianness across multiple words

How would endianness work across multiple words? First off, we need a use case where a single value spans multiple words and we want to perform arithmetic operations on that value. Conceptually we could conceive of 128-bit, 256-bit, or 1024-bit integers on sixty-four bit machines. There are libraries for that, but they’re not commonly used and I think it’s a bit academic for our discussion. The more practical use case I’m thinking of is multi-word bitmaps. Multi-word bitmaps are becoming more prevalent and are appearing in some protocols (like Falcon that we talk about below).

As we described previously, a multi-word bit map can be constructed from an array of words of some size. We can determine the “bitmap endianness” by which word contains the zeroth bit in the bitmap. If the first word contains the zeroth bit then the bitmap is little endian. if the last word contains the zeroth bit then the bitmap is big endian. Now let’s look at the operations to set a bit in a multi-word bit map with thirty-two bit words:

bitmap_set_le(__u32 *bitmap, int pos) = bitmap[pos / 32] | (1U << (pos % 32))

bitmap_set_be(__u32 *bitmap, int pos, int num_words) = bitmap[num_words -1- pos/32] | (1U << (pos % 32))

So the big endian variant needs an extra argument that gives the number of words in the bitmap and at least one extra arithmetic operation. I don’t see any way around this. This extra cost is needed for all bitmap operations, and neither can the CPU architecture hide this from the programmer since multiple words are being operated on.

An epiphany

The reason multi-word bitmaps require extra work for big endian is that they’re really arrays, and arrays are little endian with regard to how they’re indexed. Array elements are counted from zero in memory — the first element is at the first memory location, the second is at the second location, etc. Multi-word big endian wants reversed indexing, the largest array index is at the first memory location, the second largest index is at the second, and so on. Big endian forces arrays to be indexed as big endian, but that’s not how arrays inherently work hence extra steps are needed to map indices from big endian to little endian. Note that this is independent of machine endianness, arrays are always indexed as little endian.

Putting all this explanation together, Q.E.D. as they say:

Big endian is “wrong endian” and little endian is “right endian”

Well there you have it! CPUs are right endian and Internet protocols are wrong endian. So, duh! We need to fix the protocols, not the CPUs!

New protocols should be little endian

If little endian is indeed “right endian” then the good news is that most CPU architectures are good to go :-) Linus can add to his pushback that RISC-V supporting big endian is not just wrong but a regression! Of course, the problem becomes that most Internet protocols are wrong endian. We can’t change endianness of existing protocols like IP and TCP — that ship has sailed. But we can make new protocols little endian. This might be contrary to the whole “network byte order” is big endian dogma (going back to RFC791), and there will undoubtedly be purists who will push back (TBH, ten years ago I probably would have one of them :-) ). But the writing is on the wall — it’s time to evolve and start resolving the great discrepancy.

Practically in the state of current affairs

There’s a clear trend that almost all new Internet protocols are going to be encapsulated in UDP. This is helpful. The wonders of a layered protocol architecture make it easy to use little endian in UDP payloads. QUIC already does that so it’s quite the trend setter, but there’s a host of emerging protocols encapsulated in UDP, including new transport protocols for AI workloads, that are good candidates to make the plunge to little endian.

Endianness in IP and UDP

Before we talk about protocols that can go little endian, let’s talk about the ones that can’t. Looking at the IPv4 header there are six multi-byte fields, but only one, “Total Length”, that really needs endianness conversion. For the IPv6 header there’s four multi-byte fields and only the “Payload Length” needs endianness conversion. For UDP, there’s four multi-byte fields, but only the “UDP Length” field needs endianness conversion. So the IP/UDP header needs a total of two byte swaps in transmit and receive processing. For comparison, TCP has three multi-byte words in the base header needing endianness conversion and probably more in TCP options like Selective Acknowledgements. Transport protocols over UDP will be similar to TCP and likely have many more fields needing to be byte swapped than IP/UDP. So by this logic, using little endian for encapsulated UDP protocols is a win.

Example: Falcon and little endian

As an example of applying little endianness, let’s look at Falcon. Falcon is a high performance transport protocol for RDMA and NVMe. It’s similar to UET that we’ve talked about, but a lot simpler to analyze. Falcon, like UET, is network byte order, i.e. big endian, endianness. I believe Falcon is a good candidate to be a little endian protocol.

The base ACK header

Let’s take a look at one of the Falcon protocol header formats. Here is the Base Acknowledgement header format:

Falcon Base Acknowledgement header.

The C data structure for this header is defined in falcon.h in XDP2:

/* Base ACK packet. Packet type is FALCON_PKT_TYPE_BACK */
struct falcon_base_ack_pkt {
#if defined(__BIG_ENDIAN_BITFIELD)
     __u32 version: 4;
     __u32 rsvd1: 4;
#else
     __u32 rsvd1: 4;
     __u32 version: 4;
#endif
     __u32 dest_cid: 24;

     __u32 rsvd2: 24;
#if defined(__BIG_ENDIAN_BITFIELD)
     __u32 rsvd3: 3;
     __u32 pkt_type: 4;
     __u32 rsvd4: 1;
#else
     __u32 rsvd3: 1;
     __u32 pkt_type: 4;
     __u32 rsvd4: 3;
#endif

     __be32 ack_data_psn;
     __be32 ack_req_psn;
     __be32 timestamp_t1;
     __be32 timestamp_t2;

#if defined(__BIG_ENDIAN_BITFIELD)
     __u32 hop_count: 4;
     __u32 rx_buffer_occ: 5;
     __u32 ecn_rx_pkt_cnt: 14;
     __u32 rsvd5: 1;
#else
     __u32 rx_buffer_occ1: 4;
     __u32 hop_count: 4;
     __u32 ecn_rx_pkt_cnt1: 7;
     __u32 rx_buffer_occ2: 1;
     __u32 rsvd5: 1;Falcon Extended Acknowledgement header.
     __u32 ecn_rx_pkt_cnt2: 7;
#endif
     __u32 rsvd6: 8;

     __u32 rsvd7: 8;
#if defined(__BIG_ENDIAN_BITFIELD)
     __u32 rsvd8: 1;
     __u32 rue_info: 21
     __u32 oo_wind_notify: 2;
#else
     __u32 rue_info1: 7;
     __u32 rsvd8: 1;
     __u32 rue_info2: 8;
     __u32 oo_wind_notify: 2;
     __u32 rue_info3: 6;
#endif

} __packed;

ack_data_psn, ack_req_psn, timestamp_t1, and timestamp_t2 are thirty-bit big endian fields that could easily be converted to little endian. The bitfields are a little trickier. You’ll notice that ecn_rx_pkt_cnt and rx_buffer_occ need to be split into two bitfields and rue_info is split into three bitfields for little endian. This split is not transparent. Getting and setting these fields requires a lot of work. There’s helper functions to do that following the structure definition in the source code. Here’s the helpers for rue_info.

/* Helper functions to get/set RUE info from bitfields in base ACK */
static inline __u32 falcon_base_ack_get_rue_info(const void *vhdr)
{
   const struct falcon_base_ack_pkt *bhdr = vhdr;

#if defined(__BIG_ENDIAN_BITFIELD)
   return bhdr->rue_info;
#else
   return (bhdr->rue_info1 << 14) | (bhdr->rue_info2 << 6) |
         bhdr->rue_info3;
#endif
}

static inline void falcon_base_ack_set_rue_info(void *vhdr, __u32 rue_info)
{
   struct falcon_base_ack_pkt *bhdr = vhdr;

#if defined(__BIG_ENDIAN_BITFIELD)
   bhdr->rue_info = val;
#else
     bhdr->rue_info1 = rue_info >> 14;
     bhdr->rue_info2 = (rue_info >> 6) & 0xff;
     bhdr->rue_info3 = rue_info & 0x3f;
#endif
}

This splitting fields unpleasantness arises when odd length fields straddle byte boundaries. The most painful cases are when both the start and end of the field are unaligned byte boundaries which is why rue_info needs to be split three ways.

Making bitfields zoom with little endian

We could change the packet format to be more little endian centric. Let’s consider the last thirty-bits of the Falcon Base ACK header that contains rue_info. Suppose we define it in source code like this for little endian (making it look like the big endian definition):

__u32 rsvd7: 8;
__u32 rsvd8: 1;
__u32 rue_info: 21
__u32 oo_wind_notify: 2;

This eliminates the need to split rue_info for little endian as well as the hoops we need to jump through to set or get rue_info. So on a little endian system we can do simple assignments instead of calling helper functions:

hdr->rue_info = value; / To set rue_info / value = hdr->rue_info; / To get rue_info /

That’s a good improvement, but the packet format now looks like this:

The picture shows that we doubled the number of protocol fields. Eeek! That’s ugly! But here’s the thing: computers don’t see beauty the same way humans do. If rearranging header fields makes implementations run faster then an ugly protocol diagram in the text book is a small price to pay! :-)

Extended ACK

I want to mention the Extended ACK header in Falcon since it’s an example of a multi-word bitmap in action. The header format is:

Falcon Extended Acknowledgement header.

There’s two 128-bit bitmaps and two sixty-four bit bitmaps in the header. Most CPU architectures are sixty-four bit, so at least the 128-bit bitmaps are almost certainly multi-word in an implementation. Falcon clearly depicts big endian bitmaps, but as we described above most CPU architectures are going to be happier with little endian bitmaps. Let’s illustrate.

For setting the receive data ACK bitmap field in big endian from a little endian CPU we would do:

ehdr->rcv_ack_data_bitmap[0] = htonll(conn->ack_data_bitmap[1]);
ehdr->rcv_ack_data_bitmap[1] = htonll(conn->ack_data_bitmap[0]);

If the receive data ACK field is little endian then we can set it by:

memcpy(&ehdr->rcv_ack_data_bitmap, conn->ack_data_bitmap, 16);

The memcpy is faster on two accounts. 1) Two htonll byte swaps are eliminated, and 2) memcpy is quite optimized, for instance in x86 the SSE move instructions allow moving sixteen bytes in one instruction.

We can optimize the little endian case even more. If we strategically pack all the bitmaps into the connection PCB with the same layout as the header format, then we can do:

memcpy(&ehdr->rcv_ack_data_bitmap, conn->ack_data_bitmap, 48);

This copies all the bitmap fields into the packet in one shot. This is about as fast as things get, much faster then having to muck with byte swaps, and we start to see how CPUs can process protocols at the speed of hardware.

Wait a second mister, Falcon et al are hardware protocols

Falcon, and other similar protocols like UET, are touted as “hardware protocols”. So there may be an argument that big endian is sufficient since hardware can deal with it. Indulge me to make two counter arguments:

• It’s risky to design a transport protocol up front such that it can only be implemented in fixed function hardware. Why exclude potential use cases for running the protocol in a CPU by design?
• Hardware doesn’t care about endianness. Supporting little endian at the hardware level should just be a matter of rewiring gates. Of course we know this is feasible since CPUs have been doing it for fifty years!