dist, dev: Fixed the packet ordering in etherswitch

Information
Submitter:	Mohammad Alian
Repository:	gem5
Branch:	default
Bugs:
Depends On:
Reviewers
Groups:	Default
People:

Description

Changeset 11472:d97d6bf2206b
---------------------------
dist, dev: Fixed the packet ordering in etherswitch
This patch fixes the order that packets gets pushed into the output fifo
of etherswitch. If two packets arrive at the same tick to the etherswitch,
we sort and push them based on their source port id.
In dist-gem5 simulations, if there is no ordering inforced while two
packets arrive at the same tick, it can lead to non-deterministic simulations

Testing Done

Issue Summary

Description	From	Last Updated	Status
nullptr ?	Gabor Dozsa	May 16, 2016, 7:55 p.m.	Resolved
I would suggest to use a std::set instead of std::list for the fifo. You can define a compare object that ...	Gabor Dozsa	May 16, 2016, 7:55 p.m.	Resolved
'const' modifier?	Gabor Dozsa	May 16, 2016, 7:56 p.m.	Resolved
The preferred way for serializing child objects is using 'serializeSection' from the parent. PortFifo should derive from 'Serializable' and then ...	Gabor Dozsa	May 16, 2016, 7:56 p.m.	Resolved
If the fifo were a std::set with a custom comparator (using recvTick as primary and sourceId as secondary key) then ...	Gabor Dozsa	May 18, 2016, 1:03 p.m.	Resolved
You can use the fifo.front() accessor instead of creating a temporary copy of the entry.	Gabor Dozsa	May 16, 2016, 7:58 p.m.	Resolved
This could be simplified as 'for (auto i : fifo)'	Gabor Dozsa	May 16, 2016, 7:59 p.m.	Resolved
You can avoid the extra copy by using fifo.emplace(...) instead of fifo.insert(). Even better would be to use fifo.emplace_hint(fifo.rbegin(), ...) ...	Gabor Dozsa	May 18, 2016, 1:03 p.m.	Resolved
You can replace std::prev(fifo.end()) by fifo.rbegin() (in the next line, too).	Gabor Dozsa	May 20, 2016, 11:39 a.m.	Dropped
Return	Gabor Dozsa	May 18, 2016, 1:06 p.m.	Resolved
return	Gabor Dozsa	May 18, 2016, 1:06 p.m.	Resolved
The check could be simpler by comparing only the (shared) packet pointer (EthPacketPtr). However, can there be a problem here ...	Gabor Dozsa	May 18, 2016, 1:06 p.m.	Resolved
_maxsize is also serialized but it is not unserialized here	Gabor Dozsa	May 18, 2016, 1:06 p.m.	Resolved
This is not needed here I think.	Gabor Dozsa	May 23, 2016, 1:11 p.m.	Resolved
Should this be <set> instead?	Gabor Dozsa	May 20, 2016, 11:38 a.m.	Resolved
Delete empty line.	Gabor Dozsa	May 20, 2016, 11:38 a.m.	Resolved
This include should be after etherswitch.hh and before the m5 includes according to coding styles.	Gabor Dozsa	May 20, 2016, 11:38 a.m.	Resolved
I think this will still create a temporary PortFifoEntry object in this form. To avoid the extra object and copy, ...	Gabor Dozsa	May 20, 2016, 11:38 a.m.	Resolved
Could you add an extra DPRINTF message here in case when the fifo is empty? That may be a big ...	Gabor Dozsa	May 23, 2016, 3:48 a.m.	Dropped
This DPRINTF is useful but I am still concerned a bit about hitting the pathological case when the packet is ...	Gabor Dozsa	May 23, 2016, 1:11 p.m.	Resolved
all these members could be const?	Andreas Hansson	May 29, 2016, 10:52 p.m.	Resolved
unsigned? if not it really needs a comment	Andreas Hansson	May 29, 2016, 7:44 p.m.	Resolved
== it is unsigned	Andreas Hansson	May 24, 2016, 8:34 p.m.	Resolved
should this perhaps even be a warn (or do we ever expect this to happen in a correct setup?	Andreas Hansson	May 30, 2016, 6:33 a.m.	Resolved
could you add an assert here that size >= packet->length?	Andreas Hansson	May 24, 2016, 8:37 p.m.	Resolved
all reschedule instead?	Andreas Hansson	May 29, 2016, 7:44 p.m.	Resolved
Does this break checkpoint compatibility? If so that needs to be addressed.	Andreas Hansson	May 29, 2016, 7:47 p.m.	Resolved
I would say we either need to allow for these to be optional (there is a macro for that if ...	Andreas Hansson	May 29, 2016, 7:47 p.m.	Resolved

Hi Mohammad, nice catch, thanks for fixing this!

src/dev/net/etherswitch.hh (Diff revision 1)

nullptr ?

Show all issues

src/dev/net/etherswitch.hh (Diff revision 1)

I would suggest to use a std::set instead of std::list for the fifo. You can define a compare object that uses the recvTick and the sourceId as the primary and secondary key, respectively. The fifo.push() method could then be much simpler. (See my futher commnents there.)

Show all issues

Mohammad Alian May 16, 2016, 8:23 p.m. (May 16, 2016, 8:23 p.m.)

Thanks for the suggestion. I change the implementation like what you suggest.

src/dev/net/etherswitch.hh (Diff revision 1)

'const' modifier?

Show all issues

src/dev/net/etherswitch.hh (Diff revision 1)

The preferred way for serializing child objects is using 'serializeSection' from the parent. PortFifo should derive from 'Serializable' and then you can drop the extra 'base' argument here and for 'unserialize()', too.

Show all issues

Mohammad Alian May 16, 2016, 8:23 p.m. (May 16, 2016, 8:23 p.m.)

I fixed them all. Plz let me know if there is any issues left.

src/dev/net/etherswitch.cc (Diff revision 1)

If the fifo were a std::set with a custom comparator (using recvTick as primary and sourceId as secondary key) then you could simply call 'fifo.insert(entry)'. All entries would be kept in the correct order by the container. If the size of fifo is too big after the insert then you could simply erase the last element (i.e. at fifo.rbegin()) to drop a single packet (instead of dropping potentially many packets with the current code). Does that make sense?

Show all issues

Mohammad Alian May 16, 2016, 8:23 p.m. (May 16, 2016, 8:23 p.m.)

I think we still need to drop as many packet as enough to make space for the new pakcet with higher priority to push in to the fifo. E.g. if there are two packets with size 10 Bytes at the end of fifo and we receive a new packet with size 20 Bytes while fifo is full (and the newly arrived packet has arrived at the same tick as the already pushed packets but has higher priority), then we should drop two small packets and push one large packet. Does that make sense? So I still keep the code which drop multiple packets.

Gabor Dozsa May 18, 2016, 8:01 a.m. (May 18, 2016, 8:01 a.m.)
```
You are right, I missed that point before.
```

src/dev/net/etherswitch.cc (Diff revision 1)

You can use the fifo.front() accessor instead of creating a temporary copy of the entry.

Show all issues

src/dev/net/etherswitch.cc (Diff revision 1)

This could be simplified as 'for (auto i : fifo)'

Show all issues

Description:

~		Changeset 11472:91d189fd406a
	~	Changeset 11472:c7242a550140

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 2 (+197 -34)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

src/dev/net/etherswitch.cc (Diff revision 2)

You can avoid the extra copy by using fifo.emplace(...) instead of fifo.insert(). Even better would be to use fifo.emplace_hint(fifo.rbegin(), ...) which can make the common case insertion path faster. (I guess the common case is when the packet gets inserted at the end of the fifo.)

Show all issues

Mohammad Alian May 18, 2016, 1:08 p.m. (May 18, 2016, 1:08 p.m.)
```
Thanks for the good suggestions. I fixed it.
```

src/dev/net/etherswitch.cc (Diff revision 2)

You can replace std::prev(fifo.end()) by fifo.rbegin() (in the next line, too).

Show all issues

Mohammad Alian May 18, 2016, 1:08 p.m. (May 18, 2016, 1:08 p.m.)

I think we cannot use reverse pointers in std::set to erase an object. I get error and this is my understanding after doing some google search. Please let me know if there is still a better way to handle this.

Gabor Dozsa May 19, 2016, 6:46 a.m. (May 19, 2016, 6:46 a.m.)

You are right, reverse iterator would not make this simpler since erase() does not work with it. Just drop this issue please.

src/dev/net/etherswitch.cc (Diff revision 2)

Return

Show all issues

src/dev/net/etherswitch.cc (Diff revision 2)

return

Show all issues

src/dev/net/etherswitch.cc (Diff revision 2)

The check could be simpler by comparing only the (shared) packet pointer (EthPacketPtr).

However, can there be a problem here in the pathological case when the fifo is empty originally but the size of the current packet is larger then max_size ? Then, at this point the fifo would be empty.

Show all issues

Mohammad Alian May 18, 2016, 1:08 p.m. (May 18, 2016, 1:08 p.m.)

Good point:). I added a check whether the fifo is empty or not. If it's empty we return false and don't schedule any event.

src/dev/net/etherswitch.cc (Diff revision 2)

_maxsize is also serialized but it is not unserialized here

Show all issues

Description:

~		Changeset 11472:c7242a550140
	~	Changeset 11472:1d2b55391506

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 3 (+196 -34)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

Diff:

Revision 4 (+196 -34)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

Description:

~		Changeset 11472:1d2b55391506
	~	Changeset 11472:2ca9b29819aa

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 5 (+196 -34)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

src/dev/net/etherswitch.hh (Diff revision 5)

This is not needed here I think.

Show all issues

Gabor Dozsa May 23, 2016, 3:50 a.m. (May 23, 2016, 3:50 a.m.)
```
I can still see this in the newest revision.
```
Mohammad Alian May 23, 2016, 1:11 p.m. (May 23, 2016, 1:11 p.m.)
```
Sorry my mistake.  I removed it.
```

src/dev/net/etherswitch.hh (Diff revision 5)

Should this be <set> instead?

Show all issues

src/dev/net/etherswitch.hh (Diff revision 5)

Delete empty line.

Show all issues

src/dev/net/etherswitch.cc (Diff revision 5)

This include should be after etherswitch.hh and before the m5 includes according to coding styles.

Show all issues

src/dev/net/etherswitch.cc (Diff revision 5)

I think this will still create a temporary PortFifoEntry object in this form. To avoid the extra object and copy, change this to:

fifo.emplace_hint(fifo.end, ptr, curTick(), senderId);

Show all issues

src/dev/net/etherswitch.cc (Diff revision 5)

Could you add an extra DPRINTF message here in case when the fifo is empty? That may be a big help to find the issue if somebody hits this by accident.

Show all issues

Mohammad Alian May 20, 2016, 11:39 a.m. (May 20, 2016, 11:39 a.m.)
```
I added a DPRINT when we drop packets.
```

Description:

~		Changeset 11472:2ca9b29819aa
	~	Changeset 11472:80706f711d39

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 6 (+202 -35)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

src/dev/net/etherswitch.cc (Diff revision 6)

This DPRINTF is useful but I am still concerned a bit about hitting the pathological case when the packet is too long to go through even if the fifo is empty (regardless how may times the user application tries to re-send it). Could you please add another DPRINTF after this loop to catch that, i.e. something like:

if (empty()) {

 DPRINTF(Ethernet, "Packet length (%d) exceeds the maximum storage capacity of port fifo (%d)", ptr->length, _maxsize);

}

Show all issues

Mohammad Alian May 23, 2016, 1:11 p.m. (May 23, 2016, 1:11 p.m.)

Thanks for the elaboration on your comment. I added the dpritf.

Description:

~		Changeset 11472:80706f711d39
	~	Changeset 11472:d4fada3b46ac

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 7 (+207 -36)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

It looks good to me! Thanks again for fixing this!

src/dev/net/etherswitch.hh (Diff revision 7)

all these members could be const?

Show all issues

Mohammad Alian May 24, 2016, 8:50 p.m. (May 24, 2016, 8:50 p.m.)

I don't think so. We set them inside "EtherSwitch::Interface::PortFifoEntry::unserialize"

src/dev/net/etherswitch.hh (Diff revision 7)

unsigned? if not it really needs a comment

Show all issues

Mohammad Alian May 24, 2016, 8:50 p.m. (May 24, 2016, 8:50 p.m.)
```
I added a comment. I used "int" intentionally.
```

src/dev/net/etherswitch.hh (Diff revision 7)

==
it is unsigned

Show all issues

src/dev/net/etherswitch.cc (Diff revision 7)

should this perhaps even be a warn (or do we ever expect this to happen in a correct setup?

Show all issues

Mohammad Alian May 24, 2016, 8:50 p.m. (May 24, 2016, 8:50 p.m.)

I would say It can happen in a correct setup. If someone set the fifo size of the ethernet switch smaller than MTU of ethernet packets then it would happen. But I can change it to warn if you think it's better.

Andreas Hansson May 29, 2016, 10:53 p.m. (May 29, 2016, 10:53 p.m.)

I think a warn is better. If someone "misconfigures" the system they will not have a clue with the current DPRINTF unless they run with the very speficic flag. Agreed?

Mohammad Alian May 30, 2016, 6:32 a.m. (May 30, 2016, 6:32 a.m.)
```
Agree. I changed it to warn.
```

src/dev/net/etherswitch.cc (Diff revision 7)

could you add an assert here that size >= packet->length?

Show all issues

src/dev/net/etherswitch.cc (Diff revision 7)

all reschedule instead?

Show all issues

Mohammad Alian May 24, 2016, 8:50 p.m. (May 24, 2016, 8:50 p.m.)
```
good point. Fixed.
```

src/dev/net/etherswitch.cc (Diff revision 7)

Does this break checkpoint compatibility?

If so that needs to be addressed.

Show all issues

Mohammad Alian May 24, 2016, 8:50 p.m. (May 24, 2016, 8:50 p.m.)
```
It probably does. How should I address that?
```

Description:

~		Changeset 11472:d4fada3b46ac
	~	Changeset 11472:24da17267b22

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 8 (+207 -37)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc

src/dev/net/etherswitch.cc (Diff revision 7)

I would say we either need to allow for these to be optional (there is a macro for that if I remember correctly), or alternatively the cpt_upgrader.py in util needs to be updated and add the field.

Show all issues

Mohammad Alian May 29, 2016, 7:48 p.m. (May 29, 2016, 7:48 p.m.)
```
I've added a cpt_upgrader to fix this issue.
```
Andreas Hansson May 29, 2016, 10:53 p.m. (May 29, 2016, 10:53 p.m.)
```
Fantastic. Thanks for that!
```

Mohammad Alian June 1, 2016, 5:37 p.m. (June 1, 2016, 5:37 p.m.)

Andreas, Is there any further issue with this patch? Or it looks good?
Thanks.

Description:

~		Changeset 11472:24da17267b22
	~	Changeset 11472:7977ab53fb94

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 9 (+228 -37)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc
	util/cpt_upgraders/etherswitch.py

Description:

~		Changeset 11472:7977ab53fb94
	~	Changeset 11472:d97d6bf2206b

		dist, dev: Fixed the packet ordering in etherswitch
		This patch fixes the order that packets gets pushed into the output fifo
		of etherswitch. If two packets arrive at the same tick to the etherswitch,
		we sort and push them based on their source port id.
		In dist-gem5 simulations, if there is no ordering inforced while two
		packets arrive at the same tick, it can lead to non-deterministic simulations

Diff:

Revision 10 (+228 -37)

Show changes

	src/dev/net/etherswitch.hh
	src/dev/net/etherswitch.cc
	util/cpt_upgraders/etherswitch.py

Ship It!

You have a pending review.

Review Board 2.0.15

This change has been marked as submitted.

Screenshots

Files

Issue Summary

Description:

Changeset 11472:91d189fd406a

Changeset 11472:c7242a550140

Diff:

Description:

Changeset 11472:c7242a550140

Changeset 11472:1d2b55391506

Diff:

Diff:

Description:

Changeset 11472:1d2b55391506

Changeset 11472:2ca9b29819aa

Diff:

Description:

Changeset 11472:2ca9b29819aa

Changeset 11472:80706f711d39

Diff:

Description:

Changeset 11472:80706f711d39

Changeset 11472:d4fada3b46ac

Diff:

Description:

Changeset 11472:d4fada3b46ac

Changeset 11472:24da17267b22

Diff:

Description:

Changeset 11472:24da17267b22

Changeset 11472:7977ab53fb94

Diff:

Description:

Changeset 11472:7977ab53fb94

Changeset 11472:d97d6bf2206b

Diff:

Status: Closed (submitted)