13 ms·

Let's code a TCP/IP stack, 1: Ethernet & ARP (2016)

287 points by maastaar 8y ago

panic 8y ago
In case you didn't realize it at first (I didn't until I happened to click on "/home"), this is the first of a 5-part series: 1. Ethernet & ARP (this post) 2. IPv4 & ICMPv4: http://www.saminiir.com/lets-code-tcp-ip-stack-2-ipv4-icmpv4/ http://www.saminiir.com/lets-code-tcp-ip-stack-2-ipv4-icmpv4... 3. TCP Basics & Handshake: http://www.saminiir.com/lets-code-tcp-ip-stack-3-tcp-handshake/ http://www.saminiir.com/lets-code-tcp-ip-stack-3-tcp-handsha... 4. TCP Data Flow & Socket API: http://www.saminiir.com/lets-code-tcp-ip-stack-4-tcp-data-flow-socket-api/ http://www.saminiir.com/lets-code-tcp-ip-stack-4-tcp-data-fl... 5. TCP Retransmission: http://www.saminiir.com/lets-code-tcp-ip-stack-5-tcp-retransmission/ http://www.saminiir.com/lets-code-tcp-ip-stack-5-tcp-retrans...
0x00000000 8y ago
Does anyone know why you would use an unsigned char array to store the MAC address instead of uint8_t? Char is one byte but a but a byte is not guaranteed to be 8 bits yet MAC is defined as 48 bits
- dyu 8y ago
  It might not be the author's intention, but I think there is now a push for MAC addresses to be 64 bits instead of 48.
- jws 8y ago
  Unless you are adding TCP to your CDC6600 or PDP-8, bytes are 8 bits. Any suggestion to the contrary in standards is fantasy. That said, since the next field is a uint16_t, you may as well stay in Rome and call them uint8_t. short really is variable on some live architectures. (Ok, or some DSPs only address words larger than 8 bits, but there's no reason for your compiler not to pick up the slack.) Also, TIL that __attribute__((packed)) assumes the struct can be malevolently aligned and for some architectures generates very large and slow code to handle that. If you must pack, also add the ",aligned(2)" or whatever you can get away with to mitigate this.
  - wglb 8y ago
    Might I suggest reading https://www.ietf.org/rfc/rfc4042.txt https://www.ietf.org/rfc/rfc4042.txt? There they talk about bytes being 9 bits.
  - thr0w__4w4y 8y ago
    I have another TIL for you... maybe you're a desktop/server developer... there are many embedded processor platforms where a byte is not 8 bits. TI's C2000 microcontrollers - a byte is 16 bits. Other TI DSPs also have 16 bit bytes.
    - Ivoah 8y ago
      Did you mean char?
      - deleted 8y ago
        [deleted]
      - antoinealb 8y ago
        In C, char is defined to be 1 byte. So its the same here. But they have 16-bit bytes. This is one of the rare cases where byte != octet.
  - xxpor 8y ago
    I don't see any reason in modern C to use int/short/long over explicit int32_t/int8_t/int64_t other than they're shorter to type.
    - berti 8y ago
      I tend to use int for loops (where I know there will always be less than 2^16 iterations!), return codes etc. purely because it allows the compiler to pick a fast word size everywhere (e.g. if somebody compiles your code for AVR, and your loops are all int32_t, your API returns int32_t, they're gonna have a worse time). Otherwise, I fully agree.
- deleted 8y ago
  [deleted]
- mh7 8y ago
  Since the fixed width integer types are optional, and if available must be 8, 16, 32 and 64 bits (and two's compl) I don't think CHAR_BITS > 8 is allowed if stdint.h types are supported since sizeof(uint8_t) must be 1.
  - caf 8y ago
    They're individually optional - so uint16_t can exist without uint8_t. But you're right - if uint8_t exists, it must be the same as unsigned char.
jacob019 8y ago
I use SLiRP over SSH as a poor man's VPN. It's ancient. The bulk of the code is a userspace TCP stack that performs NAT. I can use any SSH host as full VPN with only basic user privileges. I spent quite a bit of time poking around the code to try to improve performance. Increasing the receive window was sufficient to achieve >1Mb/s over a high latency link, but I can't go much higher without <100ms latency. It turns out that SLiRP never implemented window scaling, it was unnecessary for the links back then. The code has been reused for virtualization applications like VirtualBox, etc; but window scaling was never needed for that since client-host latency is basically zero there. Digging through old network code gives an appreciation for how far we've come.
- plasticchris 8y ago
  Sounds like sshuttle! Low bandwidth as you said but very useful, I like to use it to vpn to my home where the gateway router is an ssh server.
  - jacob019 8y ago
    sshuttle is great too! Great for road-warrior applications where a basic SOCKS proxy won't do, but last time I tried it I found it unstable under heavy load and the iptables routing to a user process can be somewhat restrictive, still super cool though. I don't know why but network tunneling is just fun.
- Sami_Lehtinen 8y ago
  SLiRP, that's something which was used back in early 90's. With Trumpet Winsock and the one and only NCSA Mosaic browser.
algorithmsRcool 8y ago
Not directly related to the article, but there is an experimental effort to develop a userland TCP stack in .NET right now. It's interesting to see how this looks in a higher level language. https://github.com/ProjectMagma/Magma https://github.com/ProjectMagma/Magma
- voltagex_ 8y ago
  Are there any blog posts about this? It looks like "Magma" is also something to do with Minecraft so it's really hard to find info about it.
- pjmlp 8y ago
  In addition to that, here are some other examples. Go in Fuchsia, https://fuchsia.googlesource.com/third_party/netstack/ https://fuchsia.googlesource.com/third_party/netstack/ Oberon in Oberon (network stack but not TCP/IP though) https://www.inf.ethz.ch/personal/wirth/ProjectOberon/Sources/SCC.Mod.txt https://www.inf.ethz.ch/personal/wirth/ProjectOberon/Sources... http://www.projectoberon.com/ http://www.projectoberon.com/ Active Oberon in A2 - BlueBottle OS (TCP/IP stack) https://github.com/btreut/a2/blob/48dcfc1f1a6ed2bec110ca3af3674657d4229d16/source/TCP.Mod https://github.com/btreut/a2/blob/48dcfc1f1a6ed2bec110ca3af3... https://github.com/btreut/a2 https://github.com/btreut/a2 Mesa at Xerox PARC (Courier RPC, XNX) http://www.bitsavers.org/pdf/xerox/mesa/3.0_1977/listing/ http://www.bitsavers.org/pdf/xerox/mesa/3.0_1977/listing/ Sing# on Singularity https://archive.codeplex.com/?p=singularity https://archive.codeplex.com/?p=singularity Start at sourceCode\sourceCode\base\Libraries\System.Net\Sockets
  - dannas 8y ago
    Mirage OS written in ocaml has a tcp/ip stack as well. The marshal and unmarshal code is very succint compared to C implementations.
    - pjmlp 8y ago
      Thanks, forgot about that one, it is even part of Docker for macOS. https://blog.docker.com/2016/05/docker-unikernels-open-source/ https://blog.docker.com/2016/05/docker-unikernels-open-sourc...
pjmlp 8y ago
For those that rather learn how to implement it in a safer language, Fuchsia's TPC/IP stack is written in Go. https://fuchsia.googlesource.com/third_party/netstack/ https://fuchsia.googlesource.com/third_party/netstack/
- legulere 8y ago
  Isn’t garbage collection going to introduce jitter?
  - pjmlp 8y ago
    Not necessarily, there are several OSes written in GC enabled systems programming languages. Just because a language has a GC it doesn't mean it is the only means to allocate memory. Go also allows for global statics, stack and plain old C style manual allocations. It is a matter to learn how to use them. And make use of profilers as well. For example, on performance critical paths always use a standard for loop, never a for range one.
    - kazen44 8y ago
      > For example, on performance critical paths always use a standard for loop, never a for range one. i am curious, why would one use a normal for loop, instead of a range one?
      - pjmlp 8y ago
        A range one might introduce boxing depending on the types being iterated.
        GenericsMotors 8y ago
        Or use a language with reified generics :)
        dullgiulio 8y ago
i_don_t_know 8y ago
Operating System Design: Internet Working With Xinu by Douglas Comer (1987) is a nice explanation with lots of C code of how to add a networking stack to an operating system, in this case his educational unix-inspired XINU.
- jacksmith21006 8y ago
  Highly recommend. The first TCP/IP stack wrote was before this book and had to write off of RFCs. But man the three volume Comer books made things so much easier.
- bogomipz 8y ago
  I actually can't find the book you are referencing. I do see: "Operating System Design: The Xinu Approach" and also the books "Internetworking with TCP /IPvolumes1-3." Might you have a link to the title you are referencing here? I have read the Internetworking series which is excellent.
  - bblough 8y ago
    This seems to be the book - https://www.amazon.com/Operating-System-Design-Vol-Internetworking/dp/013637414X https://www.amazon.com/Operating-System-Design-Vol-Internetw... It looks the the second volume that goes with "Operating System Design". I can't be 100% certain, as I didn't find a table of content for either of the 1st edition books, but the 2nd edition of "Operating System Design" includes a section in implementing ethernet, so perhaps the two volumes got combined into one for the second edition.
    - bogomipz 8y ago
      I see that now. Great, this looks interesting. Thanks for checking.
    - i_don_t_know 8y ago
      That's indeed the book I was referring to. Thank you for clarifying.
jacksmith21006 8y ago
Written three TCP/IP stacks and the first was pretty bad as wrote off of RFCs before the Comer books. But then purchased the Comer books and made it so much easier. Highly recommend buying the Comer books if really interested in writing a TCP/IP stack. Also if you really want to learning something you write an implementation. To this day makes it so much easier to deal with IP problems, configuration, buying products, etc. https://www.amazon.com/Internetworking-TCP-IP-One-6th/dp/013608530X https://www.amazon.com/Internetworking-TCP-IP-One-6th/dp/013... https://www.amazon.com/Internetworking-TCP-Vol-Implementation-Internals/dp/0139738436 https://www.amazon.com/Internetworking-TCP-Vol-Implementatio... https://www.amazon.com/Internetworking-TCP-Vol-III-Client-Server/dp/0130320714 https://www.amazon.com/Internetworking-TCP-Vol-III-Client-Se...

287 points by maastaar 8y ago

In case you didn't realize it at first (I didn't until I happened to click on "/home"), this is the first of a 5-part series: 1. Ethernet & ARP (this post) 2. IPv4 & ICMPv4: http://www.saminiir.com/lets-code-tcp-ip-stack-2-ipv4-icmpv4/ http://www.saminiir.com/lets-code-tcp-ip-stack-2-ipv4-icmpv4... 3. TCP Basics & Handshake: http://www.saminiir.com/lets-code-tcp-ip-stack-3-tcp-handshake/ http://www.saminiir.com/lets-code-tcp-ip-stack-3-tcp-handsha... 4. TCP Data Flow & Socket API: http://www.saminiir.com/lets-code-tcp-ip-stack-4-tcp-data-flow-socket-api/ http://www.saminiir.com/lets-code-tcp-ip-stack-4-tcp-data-fl... 5. TCP Retransmission: http://www.saminiir.com/lets-code-tcp-ip-stack-5-tcp-retransmission/ http://www.saminiir.com/lets-code-tcp-ip-stack-5-tcp-retrans...

0x00000000 8y ago

Does anyone know why you would use an unsigned char array to store the MAC address instead of uint8_t? Char is one byte but a but a byte is not guaranteed to be 8 bits yet MAC is defined as 48 bits

dyu 8y ago
It might not be the author's intention, but I think there is now a push for MAC addresses to be 64 bits instead of 48.
jws 8y ago
Unless you are adding TCP to your CDC6600 or PDP-8, bytes are 8 bits. Any suggestion to the contrary in standards is fantasy. That said, since the next field is a uint16_t, you may as well stay in Rome and call them uint8_t. short really is variable on some live architectures. (Ok, or some DSPs only address words larger than 8 bits, but there's no reason for your compiler not to pick up the slack.) Also, TIL that __attribute__((packed)) assumes the struct can be malevolently aligned and for some architectures generates very large and slow code to handle that. If you must pack, also add the ",aligned(2)" or whatever you can get away with to mitigate this.
- wglb 8y ago
  Might I suggest reading https://www.ietf.org/rfc/rfc4042.txt https://www.ietf.org/rfc/rfc4042.txt? There they talk about bytes being 9 bits.
- thr0w__4w4y 8y ago
  I have another TIL for you... maybe you're a desktop/server developer... there are many embedded processor platforms where a byte is not 8 bits. TI's C2000 microcontrollers - a byte is 16 bits. Other TI DSPs also have 16 bit bytes.
  - Ivoah 8y ago
    Did you mean char?
    - deleted 8y ago
      [deleted]
    - antoinealb 8y ago
      In C, char is defined to be 1 byte. So its the same here. But they have 16-bit bytes. This is one of the rare cases where byte != octet.
- xxpor 8y ago
  I don't see any reason in modern C to use int/short/long over explicit int32_t/int8_t/int64_t other than they're shorter to type.
  - berti 8y ago
    I tend to use int for loops (where I know there will always be less than 2^16 iterations!), return codes etc. purely because it allows the compiler to pick a fast word size everywhere (e.g. if somebody compiles your code for AVR, and your loops are all int32_t, your API returns int32_t, they're gonna have a worse time). Otherwise, I fully agree.
deleted 8y ago
[deleted]
mh7 8y ago
Since the fixed width integer types are optional, and if available must be 8, 16, 32 and 64 bits (and two's compl) I don't think CHAR_BITS > 8 is allowed if stdint.h types are supported since sizeof(uint8_t) must be 1.
- caf 8y ago
  They're individually optional - so uint16_t can exist without uint8_t. But you're right - if uint8_t exists, it must be the same as unsigned char.

jacob019 8y ago

I use SLiRP over SSH as a poor man's VPN. It's ancient. The bulk of the code is a userspace TCP stack that performs NAT. I can use any SSH host as full VPN with only basic user privileges. I spent quite a bit of time poking around the code to try to improve performance. Increasing the receive window was sufficient to achieve >1Mb/s over a high latency link, but I can't go much higher without <100ms latency. It turns out that SLiRP never implemented window scaling, it was unnecessary for the links back then. The code has been reused for virtualization applications like VirtualBox, etc; but window scaling was never needed for that since client-host latency is basically zero there. Digging through old network code gives an appreciation for how far we've come.

plasticchris 8y ago
Sounds like sshuttle! Low bandwidth as you said but very useful, I like to use it to vpn to my home where the gateway router is an ssh server.
- jacob019 8y ago
  sshuttle is great too! Great for road-warrior applications where a basic SOCKS proxy won't do, but last time I tried it I found it unstable under heavy load and the iptables routing to a user process can be somewhat restrictive, still super cool though. I don't know why but network tunneling is just fun.
Sami_Lehtinen 8y ago
SLiRP, that's something which was used back in early 90's. With Trumpet Winsock and the one and only NCSA Mosaic browser.

algorithmsRcool 8y ago

Not directly related to the article, but there is an experimental effort to develop a userland TCP stack in .NET right now. It's interesting to see how this looks in a higher level language. https://github.com/ProjectMagma/Magma https://github.com/ProjectMagma/Magma

voltagex_ 8y ago
Are there any blog posts about this? It looks like "Magma" is also something to do with Minecraft so it's really hard to find info about it.
pjmlp 8y ago
In addition to that, here are some other examples. Go in Fuchsia, https://fuchsia.googlesource.com/third_party/netstack/ https://fuchsia.googlesource.com/third_party/netstack/ Oberon in Oberon (network stack but not TCP/IP though) https://www.inf.ethz.ch/personal/wirth/ProjectOberon/Sources/SCC.Mod.txt https://www.inf.ethz.ch/personal/wirth/ProjectOberon/Sources... http://www.projectoberon.com/ http://www.projectoberon.com/ Active Oberon in A2 - BlueBottle OS (TCP/IP stack) https://github.com/btreut/a2/blob/48dcfc1f1a6ed2bec110ca3af3674657d4229d16/source/TCP.Mod https://github.com/btreut/a2/blob/48dcfc1f1a6ed2bec110ca3af3... https://github.com/btreut/a2 https://github.com/btreut/a2 Mesa at Xerox PARC (Courier RPC, XNX) http://www.bitsavers.org/pdf/xerox/mesa/3.0_1977/listing/ http://www.bitsavers.org/pdf/xerox/mesa/3.0_1977/listing/ Sing# on Singularity https://archive.codeplex.com/?p=singularity https://archive.codeplex.com/?p=singularity Start at sourceCode\sourceCode\base\Libraries\System.Net\Sockets
- dannas 8y ago
  Mirage OS written in ocaml has a tcp/ip stack as well. The marshal and unmarshal code is very succint compared to C implementations.
  - pjmlp 8y ago
    Thanks, forgot about that one, it is even part of Docker for macOS. https://blog.docker.com/2016/05/docker-unikernels-open-source/ https://blog.docker.com/2016/05/docker-unikernels-open-sourc...

pjmlp 8y ago

For those that rather learn how to implement it in a safer language, Fuchsia's TPC/IP stack is written in Go. https://fuchsia.googlesource.com/third_party/netstack/ https://fuchsia.googlesource.com/third_party/netstack/

legulere 8y ago
Isn’t garbage collection going to introduce jitter?
- pjmlp 8y ago
  Not necessarily, there are several OSes written in GC enabled systems programming languages. Just because a language has a GC it doesn't mean it is the only means to allocate memory. Go also allows for global statics, stack and plain old C style manual allocations. It is a matter to learn how to use them. And make use of profilers as well. For example, on performance critical paths always use a standard for loop, never a for range one.
  - kazen44 8y ago
    > For example, on performance critical paths always use a standard for loop, never a for range one. i am curious, why would one use a normal for loop, instead of a range one?
    - pjmlp 8y ago
      A range one might introduce boxing depending on the types being iterated.
      - GenericsMotors 8y ago
        Or use a language with reified generics :)
        dullgiulio 8y ago

i_don_t_know 8y ago

Operating System Design: Internet Working With Xinu by Douglas Comer (1987) is a nice explanation with lots of C code of how to add a networking stack to an operating system, in this case his educational unix-inspired XINU.

jacksmith21006 8y ago
Highly recommend. The first TCP/IP stack wrote was before this book and had to write off of RFCs. But man the three volume Comer books made things so much easier.
bogomipz 8y ago
I actually can't find the book you are referencing. I do see: "Operating System Design: The Xinu Approach" and also the books "Internetworking with TCP /IPvolumes1-3." Might you have a link to the title you are referencing here? I have read the Internetworking series which is excellent.
- bblough 8y ago
  This seems to be the book - https://www.amazon.com/Operating-System-Design-Vol-Internetworking/dp/013637414X https://www.amazon.com/Operating-System-Design-Vol-Internetw... It looks the the second volume that goes with "Operating System Design". I can't be 100% certain, as I didn't find a table of content for either of the 1st edition books, but the 2nd edition of "Operating System Design" includes a section in implementing ethernet, so perhaps the two volumes got combined into one for the second edition.
  - bogomipz 8y ago
    I see that now. Great, this looks interesting. Thanks for checking.
  - i_don_t_know 8y ago
    That's indeed the book I was referring to. Thank you for clarifying.

jacksmith21006 8y ago

Written three TCP/IP stacks and the first was pretty bad as wrote off of RFCs before the Comer books. But then purchased the Comer books and made it so much easier. Highly recommend buying the Comer books if really interested in writing a TCP/IP stack. Also if you really want to learning something you write an implementation. To this day makes it so much easier to deal with IP problems, configuration, buying products, etc. https://www.amazon.com/Internetworking-TCP-IP-One-6th/dp/013608530X https://www.amazon.com/Internetworking-TCP-IP-One-6th/dp/013... https://www.amazon.com/Internetworking-TCP-Vol-Implementation-Internals/dp/0139738436 https://www.amazon.com/Internetworking-TCP-Vol-Implementatio... https://www.amazon.com/Internetworking-TCP-Vol-III-Client-Server/dp/0130320714 https://www.amazon.com/Internetworking-TCP-Vol-III-Client-Se...