Ipv4 fragmentation refactored #236

podhrmic · 2018-06-13T22:30:16Z

Based on #190 except rebased on the recent master.

Notes based on the previous reviews:

the reassembly algorithm was tested and works
to actually reassemble packets, it requires adding ethernet header lenght to MTU. This will be handled in a separate PR
FragmentSet being backed by ManagedSlice is tested and working. ManagedMap will not work in "no-std" environments

…acket reassembly tests

podhrmic · 2018-06-15T18:15:29Z

Added tests and the Ethernet header size to MTU, instead of #237

podhrmic · 2018-06-15T18:24:41Z

@pothos It turns out that counting in the ethernet header is strictly speaking needed only for UDP packets. With MTU of 1500, linux sends ethernet frames that are 1514 bytes long. For TCP packets, they are only 1500 bytes long (including the header). You can try this with a wireshark and see for yourself.

ICMP (ping) works too - try for example ping 192.168.69.1 -s 1700 and you get a reply now.
I cannot test on windows, so I don't know what is the status there, but at least you can run the UDP tests now.

Sending large amount of TCP data is OK, try socat stdio tcp4-connect:192.168.69.1:6972 >/dev/null on a regular server. It correctly sends 1514 bytes long packets as expected.

podhrmic · 2018-06-19T20:11:44Z

@pothos @whitequark any feedback here?

podhrmic · 2018-06-22T16:25:31Z

@dlrobertson is there anything else I should change in this PR?

dlrobertson

Thanks for working on this! I'm pumped about getting IP fragmentation support into smoltcp.

Just an initial read through. I'll need to read through a few more times.

dlrobertson · 2018-06-23T14:34:52Z

src/iface/ethernet.rs

@@ -675,14 +695,97 @@ impl<'b, 'c, 'e> InterfaceInner<'b, 'c, 'e> {
        }
    }

+/// Process an IPv4 fragment


dlrobertson · 2018-06-23T14:35:58Z

Cargo.toml

@@ -34,6 +34,7 @@ verbose = []
 "phy-raw_socket" = ["std", "libc"]
 "phy-tap_interface" = ["std", "libc"]
 "proto-ipv4" = []
+"fragmentation-ipv4" = ["proto-ipv4"]


🚲 🏠 : ipv4-fragmentation? Will it ever make sense to have a single generic ip-fragmentation feature? Is there a reason to keep two separate features for ipv4 and ipv6?

I am not familiar with Ipv6 so I cannot comment on how similar to IPv4 it is. But it can be refactored in the future, if someone with more knowledge about Ipv6 can pitch in. I would keep it separate for now, better some fragmentation support than none:-)

dlrobertson · 2018-06-23T14:45:57Z

src/iface/fragments.rs

+    }
+
+    /// Get a packet with given key
+    pub fn get_packet(&mut self, id: u16, src_addr: Ipv4Address, dst_addr: Ipv4Address, time: Instant) -> Option<&mut Packet<'a>> {


The is O(3n) right? Is there a way we could make this faster? What if we used a ManagedMap instead of a ManagedSlice?

There is a thread in the old PR where I tried to explain why ManagedMap doesn't work. In short, to insert a new packet to ManagedMap you need to allocate memory for it somewhere. And either you create a new Vec<u8> which is easy but requires alloc. Or you have a static buffers somewhere, and that effectively makes it a ManagedSlice.

I am not sure how much fragmented packets you normally encounter (TCP doesn't use fragmented packets typically), in our tests the performance penalty was negligible (with large UDP packets).

But - to use fragmentation in no-std builds, you still need to solve problem with From conversion for ManagedSlice here: https://github.com/m-labs/rust-managed/blob/master/src/slice.rs#L74

If you don't have alloc/std then rust doesn't know how to create a FragmentSet from static buffers. It would be cool to be able to do fragmentation without alloc, but I am not sure what is the best way around this.

Edit: I realized even the loopback.rs example you have to run with at least alloc because of the From trait implementation. This definitely limits smoltcp's usage on bare metal systems:-(

And either you create a new Vec which is easy but requires alloc. Or you have a static buffers somewhere, and that effectively makes it a ManagedSlice.

Yeah it is basically the same, but you get massivly improved lookup times due to the use of a btree. Couldn't you just use something like the following.

const FRAGMENT_BUFFER_SIZE: usize = // ... static FRAGMENT_BUFFER: [Option<Ident, FragmentPacket> ; FRAGMENT_BUFFER_SIZE] = [None; FRAGMENT_BUFFER_SIZE]; let fragment_set = FragmentSet::new(FRAGMENT_BUFFER);

I am not sure how much fragmented packets you normally encounter (TCP doesn't use fragmented packets typically), in our tests the performance penalty was negligible (with large UDP packets).

Lots of embedded applicaitons make heavy use of fragmented packets. See 6LoWPAN (RFC 4944 and RFC 6282). As smoltcp matures this is going to become more and more important. IMO the next two big hurdles are this and breaking up the EthernetInterface.

Thanks @dlrobertson, these are my thoughts exactly. I would really like to merge this but I'm afraid using ManagedMap is a requirement.

m-labs-homu · 2018-06-24T07:41:07Z

☔ The latest upstream changes (presumably 94d7338) made this pull request unmergeable. Please resolve the merge conflicts.

podhrmic · 2018-07-20T22:11:10Z

@whitequark @dlrobertson I switched FragmentedSet to ManagedMap.

The unresolved things are:

when and how to purge stale fragments? Should I iterate over all fragments every time I call get_packet? Or should I somehow check the size of the map, and remove old fragments only when the size is too large? Stale means the fragmented packet is not completed, and it wasn't modified for more than a timeout (e.g. 500ms)?
how to remove (K,V) pairs from the map? I can do a copy of the buffer and create a new packet here: https://github.com/podhrmic/smoltcp/blob/867edfefeaa7f8e5dc1f75676a7a27e35f52a3d9/src/iface/ethernet.rs#L760 but fragments are still mutually borrowed at that point so I cannot borrow it again.
ManagedMap means you need alloc at least, so it won't work anymore on bare-metal systems.

what do you think is the best way to tackle these problems?

dlrobertson · 2018-07-21T01:48:22Z

ManagedMap means you need alloc at least, so it won't work anymore on bare-metal systems.

I don't think this is true. See the implementation in rust-managed.

when and how to purge stale fragments? Should I iterate over all fragments every time I call get_packet? Or should I somehow check the size of the map, and remove old fragments only when the size is too large? Stale means the fragmented packet is not completed, and it wasn't modified for more than a timeout (e.g. 500ms)?

I think the cleanup implementation for the neighbor cache turned out to be a clean implementation. Maybe something like that would work here? I think some sort of count threshold makes more sense. Especially since IIRC the Borrowed variant of the ManagedMap does this.

podhrmic · 2018-07-24T22:41:24Z

I am having a problem using ManagedMap in no-std mode. If I do something like this in loopback.rs:

const FRAGMENT_BUFFER_SIZE: usize = 6;
    static FRAGMENT_BUFFER: [Option<(FragmentedKey, FragmentedPacket)> ; FRAGMENT_BUFFER_SIZE] = [None; FRAGMENT_BUFFER_SIZE];
    let fragment_set = FragmentSet::new(FRAGMENT_BUFFER);

I get this error:

error[E0277]: the trait bound `smoltcp::iface::Packet<'static>: core::marker::Copy` is not satisfied in `(smoltcp::iface::Key, smoltcp::iface::Packet<'static>)`
   --> examples/loopback.rs:123:96
    |
123 |     static FRAGMENT_BUFFER: [Option<(FragmentKey, FragmentedPacket)> ; FRAGMENT_BUFFER_SIZE] = [None; FRAGMENT_BUFFER_SIZE];
    |                                                                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ within `(smoltcp::iface::Key, smoltcp::iface::Packet<'static>)`, the trait `core::marker::Copy` is not implemented for `smoltcp::iface::Packet<'static>`
    |
    = note: required because it appears within the type `(smoltcp::iface::Key, smoltcp::iface::Packet<'static>)`
    = note: required because of the requirements on the impl of `core::marker::Copy` for `core::option::Option<(smoltcp::iface::Key, smoltcp::iface::Packet<'static>)>`
    = note: the `Copy` trait is required because the repeated element will be copied

I am compiling without std or alloc. Packet indeed doesn't implement Copy, but how to go around this limit?

pothos · 2018-07-27T08:10:18Z

src/phy/mod.rs

+/// Ethernet header length to be added to the MTU, since the header is not counted into MTU
+/// 6 bytes src addr, 6 bytes dst addr, 2 bytes EthType,
+/// the optionbal 4 bytes of IEEE 802.1Q Header are not accounted for
+pub const ETHERNET_HAEDER_MAX_LEN: usize = 14;


I think it would be better to use 18 here as correct maximal length because otherwise you could just use EthernetFrame::<&[u8]>::header_len() which is 14.

When using 18, this has to be changed as well:

diff --git a/src/iface/ethernet.rs b/src/iface/ethernet.rs index e44abb4..e3fd029 100644 --- a/src/iface/ethernet.rs +++ b/src/iface/ethernet.rs @@ -388,7 +388,7 @@ impl<'b, 'c, 'e, DeviceT> Interface<'b, 'c, 'e, DeviceT> fn socket_egress(&mut self, sockets: &mut SocketSet, timestamp: Instant) -> Result<bool> { let mut caps = self.device.capabilities(); - caps.max_transmission_unit -= EthernetFrame::<&[u8]>::header_len(); + caps.max_transmission_unit -= ETHERNET_HAEDER_MAX_LEN; let mut emitted_any = false; for mut socket in sockets.iter_mut() { @@ -1122,7 +1122,7 @@ impl<'b, 'c, 'e> InterfaceInner<'b, 'c, 'e> { // I'm really not happy about this "solution" but I don't know what else to do. if let Some(max_burst_size) = caps.max_burst_size { let mut max_segment_size = caps.max_transmission_unit; - max_segment_size -= EthernetFrame::<&[u8]>::header_len(); + max_segment_size -= ETHERNET_HAEDER_MAX_LEN; max_segment_size -= ip_repr.buffer_len(); max_segment_size -= tcp_repr.header_len();

m-labs-homu · 2018-08-01T02:36:38Z

☔ The latest upstream changes (presumably 58a5473) made this pull request unmergeable. Please resolve the merge conflicts.

jean-airoldie · 2019-07-27T09:23:35Z

@podhrmic This issue is caused because rust requires elements to implement copy when using the [type; size] array init syntax for some reason. Its kind of a pain since you usually have to manually initialize the array (this example comes to mind).

However in this case, since Option<T> implements Default as None you should be able to write:

    static FRAGMENT_BUFFER: [Option<(FragmentedKey, FragmentedPacket)> FRAGMENT_BUFFER_SIZE] = Default::default();

MabezDev · 2019-09-03T10:40:29Z

Is there any movement on this? It looks so close to complete it would be a shame to not see it merged.

podhrmic · 2019-09-03T21:37:11Z

Unfortunately I don't have time to finish this, so somebody else would have to step in. I think a little bit more work is needed, but I had the algorithm working in a fork of smoltcp last year.

591: Fragmentation mechanism r=Dirbaio a=thvdveld This contains the fragmentation mechanism used in #580 (which is heavily based on #236 taking into account the remarks that were made there). I tried to decouple it from the 6LoWPAN implementation such that it can be used for other protocols as well. I opened a separate PR for this such that #580 will only contain the mechanisms that are part of 6LoWPAN only. Co-authored-by: Thibaut Vandervelden <thvdveld@vub.be>

580: 6LoWPAN fragmentation r=Dirbaio a=thvdveld This adds the fragmentation part of 6LoWPAN from [RFC4944 5.3](https://datatracker.ietf.org/doc/html/rfc4944#section-5.3). This is still a work in progress: - [x] Add wire format of the fragmentation header of 6LoWPAN. - [x] Update documentation in wire. - [x] Use packet assembler (based on the IPv4 assembling #236). - [x] Use assembling in the interface for incoming packets. - [x] Assemble packets. - [x] Correct checksum (still need to find out why my checksums are incorrect). - [x] Check the interval between incoming fragments. - [x] Fragment outgoing packets (still not sure how to do this part). - [x] Add overlap detection in `Assembler`. - [x] Handle stale fragments. - [x] Do the correct thing when encountering fragment overlaps. - [x] Finish address resolution for 6LoWPAN. - [x] Try not to use a temporary buffer when trying to fragment outgoing packets. ~~**NOTE**: This requires more changes. For example: the emit function for UDP requires that the whole buffer is passed to it such that even the payload fits in it. However, IEEE802154 only has buffers of 127 bytes (125 bytes without the CRC).~~ Co-authored-by: Thibaut Vandervelden <thvdveld@vub.be> Co-authored-by: AntoonBeres <35069455+AntoonBeres@users.noreply.github.com>

624: IPv4 packet reassembly r=Dirbaio a=thvdveld This adds IPv4 packet reassembly. Replacement for #236. Depends on the fragmentation work of #580. When #580 gets merged I will rebase on master. Co-authored-by: Thibaut Vandervelden <thvdveld@vub.be>

Dirbaio · 2022-06-09T13:23:33Z

Closing in favor of #624

Ipv4 fragmentation refactored

eccbeb2

podhrmic mentioned this pull request Jun 13, 2018

Support for receiving fragmented IPv4 packets #190

Closed

podhrmic added 4 commits June 13, 2018 15:57

Compilation fixes

704d2af

Compilation fixes

9217a45

Remove forgotten line

4a0f030

Add ethernet header size to MTU, and add appropriate UDP fragmented p…

f334740

…acket reassembly tests

podhrmic mentioned this pull request Jun 15, 2018

Fix MTU settings so fragmented packets can be received #237

Closed

Travis compilation fixes

200ec19

dlrobertson reviewed Jun 23, 2018

View reviewed changes

podhrmic and others added 3 commits June 25, 2018 09:35

Fixed whitespace

dcbc010

Merge branch 'master' into fragmentation_rebased

069142a

Switch FragmetsSet to ManagedMap

867edfe

pothos reviewed Jul 27, 2018

View reviewed changes

podhrmic mentioned this pull request Sep 24, 2018

Implementing IGMP protocol and multicast support #51

Closed

thvdveld mentioned this pull request Dec 17, 2021

6LoWPAN fragmentation #580

Merged

13 tasks

thvdveld mentioned this pull request Feb 22, 2022

Fragmentation mechanism #591

Merged

thvdveld mentioned this pull request Jun 2, 2022

IPv4 packet reassembly #624

Merged

Dirbaio marked this pull request as draft June 5, 2022 21:11

Dirbaio closed this Jun 9, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Ipv4 fragmentation refactored #236

Ipv4 fragmentation refactored #236

podhrmic commented Jun 13, 2018

podhrmic commented Jun 15, 2018

podhrmic commented Jun 15, 2018

podhrmic commented Jun 19, 2018

podhrmic commented Jun 22, 2018

dlrobertson left a comment

dlrobertson Jun 23, 2018

podhrmic Jun 25, 2018

dlrobertson Jun 23, 2018

podhrmic Jun 25, 2018

dlrobertson Jun 23, 2018

podhrmic Jun 25, 2018

podhrmic Jun 25, 2018

dlrobertson Jun 25, 2018

whitequark Jul 10, 2018 •

edited

m-labs-homu commented Jun 24, 2018

podhrmic commented Jul 20, 2018

dlrobertson commented Jul 21, 2018

podhrmic commented Jul 24, 2018

pothos Jul 27, 2018

m-labs-homu commented Aug 1, 2018

jean-airoldie commented Jul 27, 2019 •

edited

MabezDev commented Sep 3, 2019

podhrmic commented Sep 3, 2019

Dirbaio commented Jun 9, 2022

Ipv4 fragmentation refactored #236

Ipv4 fragmentation refactored #236

Conversation

podhrmic commented Jun 13, 2018

podhrmic commented Jun 15, 2018

podhrmic commented Jun 15, 2018

podhrmic commented Jun 19, 2018

podhrmic commented Jun 22, 2018

dlrobertson left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

whitequark Jul 10, 2018 • edited

Choose a reason for hiding this comment

m-labs-homu commented Jun 24, 2018

podhrmic commented Jul 20, 2018

dlrobertson commented Jul 21, 2018

podhrmic commented Jul 24, 2018

Choose a reason for hiding this comment

m-labs-homu commented Aug 1, 2018

jean-airoldie commented Jul 27, 2019 • edited

MabezDev commented Sep 3, 2019

podhrmic commented Sep 3, 2019

Dirbaio commented Jun 9, 2022

whitequark Jul 10, 2018 •

edited

jean-airoldie commented Jul 27, 2019 •

edited