gnrc: Add priority packet queue module to gnrc #5950

zhuoshuguo · 2016-10-14T17:11:56Z

This PR aim to priority packet queue module to gnrc.

PS: this module here is extracted/sorted from the packet queue management block of Lw-MAC.

miri64 · 2016-10-16T20:10:47Z

sys/include/net/gnrc/gnrc_mac/packet_queue.h

+ * @{
+ * @ingroup     net_gnrc_mac
+ * @file
+ * @brief       Wrapper for priority_queue that holds gnrc_pktsnip_t* and is


What's wrong with gnrc_pktqueue that you introduce another packet queue?

@daniel-k Can you help explain here? I remember, as you have stated somewhere, was it first due to the unawareness of "gnrc_pktqueue " when creating the packet queue module for Lw-MAC, or does it due to that we want the queue to be aware of its length?

Then the preferred way would be to expand the gnrc_pktqueue module not write your own.

Can you help explain here? I remember, as you have stated somewhere, was it first due to the unawareness of "gnrc_pktqueue " when creating the packet queue module for Lw-MAC

Yes, that's right.

or does it due to that we want the queue to be aware of its length?

This definetely helps during runtime, but the queues should be quite small anyway.

All in all my packet queue implementation was something I was planning to refactor and maybe merge with the existing one, so in general I'm with @miri64.

zhuoshuguo · 2016-10-17T09:55:55Z

sys/include/net/gnrc/gnrc_mac/packet_queue.h

+    packet_queue_node_t* buffer;
+    size_t buffer_size;
+} packet_queue_t;
+


By the way, @miri64 , I think the packet_queue introduced here is more attached to the priority_queue but not gnrc_pktqueue, since the packet_queue_t here support priority while gnrc_pktqueue does not. So, it is a more wrapper to priority_queue.

Also, do you think we can leave this issue here and currently only use it in MAC layer, and solve it (i.e., extand gnrc_pktqueue or priority_queue and delete this new packet_queue module) after the merge of Lw-MAC?

You're right! Though it is documented that gnrc_pktqueue is based on priority queue it isn't. Will fix. So maybe (since this might not just be of interest to MAC) rename this module gnrc_priority_pktqueue?

I think this packet_queue module here is still not ready for universal usage yet. Just my opinion. This is because, if you check the packet_queue_t structure above, it contains a buffer (type of packet_queue_node_t, which is actually priority_queue_node_t). This means that you need to define a packet buffer first for holding your packets before using queue management.
In short, the queue management module here relies on a predefined packet buffer which is assumed to be created and initiated before start using the queue management provided here. check the example case in Lw-MAC: buffer define, init function and init before use.

So, currently it is more MAC-oriented... and I tend to revise it after the merge of the Lw-MAC.

I think that because of this the contrary is the case: it is even more suitable for general use. Compare e.g. the packet buffer which only allows for one central array to be the packet buffer. The implementation here can however be cleaned up a little bit. That I agree. But I still don't see any reason why this makes it dependent on MAC ;-).

OK, with your support, I will update it now, move it out of gnrc_mac. :-)

By the way, @miri64 where do you think I can place this gnrc_priority_pktqueue.c, in /RIOT/sys/net/gnrc/pkt?

No, it's its own module, so I would suggest to pout it into sys/net/gnrc/priority_pktqueue (you need to add a makefile to that directory and also need to update sys/net/gnrc/Makefile)

OK, I see. Will do it now.

zhuoshuguo · 2016-10-17T13:34:19Z

@miri64 Updated.

miri64 · 2016-10-17T13:35:32Z

sys/include/net/gnrc/gnrc_priority_pktqueue.h

@@ -0,0 +1,68 @@
+/*


please remove the leading gnrc_ in the headers name. It is already reflected in the sub-directory gnrc/

miri64 · 2016-10-17T13:36:19Z

sys/include/net/gnrc/gnrc_priority_pktqueue.h

+
+/**
+ * @{
+ * @ingroup     net_gnrc_oriority_pktqueue Priority packet queue


* @defgroup net_gnrc_priority_pktqueue Priority packet queue * @ingroup net_gnrc

miri64 · 2016-10-17T13:38:09Z

sys/include/net/gnrc/gnrc_priority_pktqueue.h

+    uint32_t length;
+    packet_queue_node_t* buffer;
+    size_t buffer_size;
+} packet_queue_t;


Can you please harmonize the type's name with the modules name? Also I think that having both length and buffer_size is superfluous.

(e.g gnrc_priority_pktqueue_t)

Well, the buffer_size reflects the central buffer size which is needed when initializing the queue, while the length is the queue's length..

Ah... I would store neither in this struct... ^^

Haha, what is why I thought it may not be ready for general usage..:-)

miri64 · 2016-10-17T13:40:27Z

sys/include/net/gnrc/gnrc_priority_pktqueue.h

+                                       uint32_t priority);
+
+void packet_queue_init(packet_queue_t* q,
+                       packet_queue_node_t buffer[],


After thinking about it, I don't see any benefit in doing this way. A user of this API can just as well have their buffer stored somewhere instead of wasting up to 8 byte on buffer and buffer size...

so, what do you suggest now? :-)

@miri64 so I still keep this in my gnrc_mac module and revise it in the future? Just put this issue aside?

No, let's find some API we both are happy with.

Will try to rework this PR.

zhuoshuguo · 2016-10-19T08:18:11Z

sys/include/net/gnrc/priority_pktqueue.h

+    priority_queue_t queue;
+    packet_queue_node_t* buffer;
+    size_t buffer_size;
+} gnrc_priority_pktqueue_t;


@miri64 Updated, deleted length and updated the method for getting the queue length.
But I still keep the buffer_size parameter for queue initialization, since I couldn't think up a way to initialize the queue without it, i.e., how to be aware of the buffer size if we only pass in the *buffer when doing initialization.
Do you have some tips for this? :-)

See zhuoshuguo#1 for my proposal.

miri64 · 2016-10-20T13:34:40Z

sys/include/net/gnrc/priority_pktqueue.h

+
+#define PRIORITY_PKTQUEUE_NODE_INIT(priority, pkt) { NULL, priority, pkt }
+
+static inline void priority_pktqueue_node_init(gnrc_priority_pktqueue_node_t *node,


Please prefix these functions and macros with gnrc_. I know I introduced some of these, but I tried to keep style with the current status of this PR.

miri64 · 2016-10-20T13:35:43Z

sys/include/net/gnrc/priority_pktqueue.h

+    *q = qn;
+}
+
+static inline uint32_t priority_pktqueue_length(gnrc_priority_pktqueue_t *q)


This function is quiet big for an inline function. Please un-inline.

miri64 · 2016-10-20T13:35:51Z

sys/include/net/gnrc/priority_pktqueue.h

+
+static inline uint32_t priority_pktqueue_length(gnrc_priority_pktqueue_t *q)
+{
+	uint32_t length = 0;


Indentation

Just to ensure, you mean I should use four spaces here? instead of a tab, right? :-)

@miri64 ping

Yes, sorry thought I already replied 😄

Thanks! :-)

miri64 · 2016-10-20T13:36:52Z

sys/net/gnrc/priority_pktqueue/priority_pktqueue.c

+
+gnrc_pktsnip_t* priority_pktqueue_pop(gnrc_priority_pktqueue_t* q)
+{
+    if(!q || (priority_pktqueue_length(q) == 0))


Here, I should add a braces right?

miri64 · 2016-10-20T13:36:57Z

sys/net/gnrc/priority_pktqueue/priority_pktqueue.c

+
+gnrc_pktsnip_t* priority_pktqueue_head(gnrc_priority_pktqueue_t* q)
+{
+    if(!q || (priority_pktqueue_length(q) == 0))


miri64 · 2016-10-20T13:37:02Z

sys/net/gnrc/priority_pktqueue/priority_pktqueue.c

+
+void priority_pktqueue_flush(gnrc_priority_pktqueue_t* q)
+{
+    if(priority_pktqueue_length(q) == 0)


miri64 · 2016-10-20T13:37:24Z

sys/net/gnrc/priority_pktqueue/priority_pktqueue.c

+        return;
+
+    gnrc_priority_pktqueue_node_t* node;
+    while( (node = (gnrc_priority_pktqueue_node_t *)priority_queue_remove_head(q)) )


Style: Please put the brace on the same line as the while and remove the whitespaces between the parans.

zhuoshuguo · 2016-10-24T14:12:43Z

@miri64 can you give some tips about how to run the unittests locally (maybe on the samr21 boards?) Thus to evaluate the unittests codes written. Thanks.

miri64 · 2016-10-24T14:18:52Z

Sure, just follow the steps in https://github.com/RIOT-OS/RIOT/blob/master/tests/unittests/README.md. To build for a dedicated board you need to define it as an environment variable variable (as you normally would do with other applications) and flash in between build and term step.

zhuoshuguo · 2016-10-24T14:38:12Z

@miri64 Thanks!

zhuoshuguo · 2016-10-25T16:24:33Z

@miri64 Updated, corrected style and added unittests.

miri64

I think the assertion in the unittests are far to excessive. oO but the line below caught my eye in particular

miri64 · 2016-10-25T20:52:57Z

tests/unittests/tests-priority_pktqueue/tests-priority_pktqueue.c

+    res = gnrc_priority_pktqueue_pop(&pkt_queue);
+
+    TEST_ASSERT(res == &pkt2);
+    TEST_ASSERT_EQUAL_INT(0,((priority_queue_node_t *)&elem2)->data);


The compiler flags for the boards do not allow for such type-punning. Also, why is this line even here? And shouldn't this be the address value of pkt2?

I did this assert since, inside gnrc_priority_pktqueue_pop, it will call _free_node() in which priority_queue_node_init() will be further called to initialize the popped elem. So I want to check the result of initialization of elem. I checked that priority_queue_node_init() will set the data to 0, that's why I did this kind of assert..

But, you are right, I should do this more concisely by TEST_ASSERT_NULL(elem2.pkt);

Ah right, and yes: TEST_ASSERT_NULL() should is the better option.

zhuoshuguo · 2016-10-26T07:57:16Z

@miri64 sorry, I tried to be more careful when building tests. Will reduce assertions.

zhuoshuguo · 2016-10-26T11:49:11Z

Updated.

miri64 · 2016-10-31T14:32:17Z

Let's try to get this into the release.

miri64

One last minor request.

miri64 · 2016-10-31T14:32:40Z

sys/include/net/gnrc/priority_pktqueue.h

+ */
+static inline void gnrc_priority_pktqueue_node_init(gnrc_priority_pktqueue_node_t *node,
+                                               uint32_t priority,
+                                               gnrc_pktsnip_t *pkt)


Style, please fix indentation

miri64 · 2016-10-31T14:32:53Z

sys/include/net/gnrc/priority_pktqueue.h

+ * @param[in]       node    the node to add.
+ */
+void gnrc_priority_pktqueue_push(gnrc_priority_pktqueue_t* queue,
+                                            gnrc_priority_pktqueue_node_t *node);


Style: please fix indentation

zhuoshuguo · 2016-10-31T15:55:59Z

@miri64 Fixed style and squashed commits. :-)

miri64

ACK and go when Travis is happy

miri64 · 2016-11-01T06:55:54Z

Congrats on your first feature PR! :-)

kYc0o · 2016-11-01T10:43:33Z

Congrats Shuguo! ;-) (@miri64 it wasn't Murdock who helped? :P )

zhuoshuguo · 2016-11-01T11:08:02Z

@miri64 @kYc0o Thanks a lot for your help! :-)

daniel-k · 2016-11-02T11:48:29Z

Congrats from my side too! And thanks for messing with my code 😃

miri64 reviewed Oct 16, 2016

View reviewed changes

miri64 self-assigned this Oct 16, 2016

miri64 added Area: network Area: Networking Type: new feature The issue requests / The PR implemements a new feature for RIOT GNRC labels Oct 16, 2016

zhuoshuguo commented Oct 17, 2016

View reviewed changes

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch from 2e37a41 to 55d6818 Compare October 17, 2016 13:30

zhuoshuguo changed the title ~~gnrc: Add packet queue module to gnrc mac~~ gnrc: Add priority packet queue module to gnrc Oct 17, 2016

miri64 requested changes Oct 17, 2016

View reviewed changes

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch from 55d6818 to cf3b7da Compare October 19, 2016 08:04

zhuoshuguo commented Oct 19, 2016

View reviewed changes

miri64 mentioned this pull request Oct 19, 2016

gnrc_priority_pktqueue: simplify API zhuoshuguo/RIOT#1

Merged

miri64 requested changes Oct 20, 2016

View reviewed changes

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch 2 times, most recently from 04fa627 to dd96570 Compare October 24, 2016 11:36

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch 3 times, most recently from a24527a to 2c09a67 Compare October 25, 2016 16:20

miri64 requested changes Oct 25, 2016

View reviewed changes

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch from 2c09a67 to 7b941a6 Compare October 26, 2016 11:48

miri64 added this to the Release 2016.10 milestone Oct 31, 2016

miri64 requested changes Oct 31, 2016

View reviewed changes

gnrc: add priority packet queue module.

0ebe2a0

zhuoshuguo force-pushed the add_packet_queue_module_to_gnrc_mac branch from 7b941a6 to 0ebe2a0 Compare October 31, 2016 15:55

miri64 added the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Oct 31, 2016

miri64 approved these changes Oct 31, 2016

View reviewed changes

miri64 merged commit 6dac4bd into RIOT-OS:master Nov 1, 2016

miri64 mentioned this pull request Nov 7, 2016

gnrc_netdev2: link-layer retransmissions outside the transceiver driver #4795

Closed


		#define PRIORITY_PKTQUEUE_NODE_INIT(priority, pkt) { NULL, priority, pkt }

		static inline void priority_pktqueue_node_init(gnrc_priority_pktqueue_node_t *node,

gnrc: Add priority packet queue module to gnrc #5950

gnrc: Add priority packet queue module to gnrc #5950

Uh oh!

Conversation

zhuoshuguo commented Oct 14, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuoshuguo Oct 17, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuoshuguo commented Oct 17, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuoshuguo Oct 17, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuoshuguo Oct 17, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuoshuguo Oct 19, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

zhuoshuguo commented Oct 14, 2016 •

edited

Loading

zhuoshuguo Oct 17, 2016 •

edited

Loading

zhuoshuguo Oct 17, 2016 •

edited

Loading

zhuoshuguo Oct 17, 2016 •

edited

Loading

zhuoshuguo Oct 19, 2016 •

edited

Loading

zhuoshuguo Oct 21, 2016 •

edited

Loading