core: mutex: several optimizations #4557

kaspar030 · 2015-12-29T12:46:11Z

re-use a thread's "rq_entry" for mutex queue
re-use mutex queue to indicate a locked mutex
don't use atomic variable for mutex
unify mutex_lock and mutex_trylock

(The last three were adopted from @Kijewski's #4555)

kaspar030 · 2015-12-29T12:49:38Z

Result is 4% more speed, 20 bytes code saved and sizeof(mutex) == sizeof(void*).

kaspar030 · 2015-12-29T12:50:15Z

core/mutex.c


 #define ENABLE_DEBUG    (0)
 #include "debug.h"

-static void mutex_wait(struct mutex_t *mutex);
+#define MUTEX_LOCKED ((void*)0xFFFFFFFF)


(this needs 16bit adjustments)

Just use -1 instead of 0xFF…FF.

Kijewski · 2015-12-29T20:06:47Z

Re-usuing tcb_t::rq_entry makes sense. I did not look into the diff properly, yet.

kaspar030 · 2015-12-29T21:05:43Z

addressed @Kijewski's comments.

One advantage of reusing "rq_entry" is that mutexes don't need any space in tcb_t anymore. Before, they shared "wait_data" with msg.

kaspar030 · 2016-01-04T11:47:52Z

found another ~2.5%

jnohlgard · 2016-02-08T13:58:13Z

needs rebase

kaspar030 · 2016-02-08T14:01:57Z

rebased

jnohlgard · 2016-02-08T14:14:37Z

Could you make a short summary of the benefits of the new linked list implementation?
There's already core/include/clist.h and sys/include/utlist.h.

The casts from list_node_t* to clist_node_t* to get the tcb_t looks a bit hairy to me and I would expect them to possibly break in unexpected creative ways on some changes to the clist implementation.

jnohlgard · 2016-02-08T14:15:50Z

core/thread.c

+    list_node_t *new_node = (list_node_t*)&thread->rq_entry;
+    new_node->next = NULL;
+
+    while (list->next) {


I don't think this will exit on next == MUTEX_LOCKED.

Doesn't _mutex_lock() catch that case before calling thread_add_to_list()?

kaspar030 · 2016-02-08T14:47:09Z

Could you make a short summary of the benefits of the new linked list implementation?
There's already core/include/clist.h and sys/include/utlist.h.

The main difference to clist is that clist is doubly-linked and circular, while the new list is only singly-linked and has two ends.
Both are designed to be intrusive.
The new list only needs one pointer per list object, so unless the rq_entry type becomes < sizeof(void*), the cast should be fine. I used rq_entry as a thread is either on a runqueue or in a mutex waiting list.

This way, mutex_t is only one-field-sized (a list entry).

(After a short ~~list~~ edit look into utlist.h, I decided a singly linked list is simple enough to re-implement. utlist.h would have never made it through our current coding best practices.)

kaspar030 · 2016-02-22T00:23:14Z

rebased

miri64 · 2016-02-28T14:46:19Z

core/include/list.h

+ * @param[in] node      list node before new entry
+ * @param[in] new_node  list node to insert
+ */
+static inline void list_add(list_node_t *node, list_node_t *new_node) {


I would do

static inline void list_add(list_node_t **node, list_node_t *new_node) { if (*node == NULL) { *node = new_node; } else { new_node->next = node->next; node->next = new_node; } }

To make the API more consistent with clist_node_t (empty list is NULL).

edit: fixed dereferencialization in if statement.

Somehow I dislike replacing two lines with four for API consistency.

Then how is an empty list represented in your version?

As pointer to the first element. edit misread.

A list is represented as pointer to the first element, and that struct is conveniently the same as that of a list node. So if the list is empty, the list node representing the list has a NULL next ptr.

So you always need one extra element in memory? That's not ideal either ;-)

Ah okay. I did not read it that way. So an empty list is still a NULL pointer in your version? Wouldn't this just require the user to add the check I introduced above anyways i.e. just put the code outside the API?

Well, every list is a "list_node_t". That struct just happens to only contain a pointer. If there are elements, that pointer points to the first element, if not, it is NULL.
The add function inserts an element after another. If the root node of the list is specified as first parameter, the new object will be the new head of the list.
The remove_head function removes the first and returns it, if any.
No further checks needed.

This function is never called.

This function is never called.

Really... But it might be kinda handy for a linked list?

I don't have the time to understand the full PR, I'm just a bit confused why you introduce a new list implementation and use only the "remove head" function.

kaspar030 · 2016-02-28T20:17:02Z

The casts from list_node_t* to clist_node_t* to get the tcb_t looks a bit hairy to me and I would expect them to possibly break in unexpected creative ways on some changes to the clist implementation.

Could be solved by using a union...

OlegHahm · 2016-03-23T22:48:28Z

Needs a rebase.

kaspar030 · 2016-03-23T23:06:20Z

rebased

haukepetersen · 2016-03-29T17:38:56Z

core/include/list.h

+ */
+
+#ifndef __LIST_H
+#define __LIST_H


I thought these underscores were forbidden?

haukepetersen · 2016-03-29T18:08:16Z

core/thread.c

+        list = list->next;
+    }
+
+    list->next = new_node;


shouldn't you use list_add() here, so you don't break the list? So if the current list->next is somewhere in the middle of the list, and we run the line above, the items that have been pointed to by list->next before are dropped from the list, right?

ups, overlooked l119, so everything should be ok. You might want to more l119 out of the loop and remove l114 though.

kaspar030 · 2016-03-29T19:05:58Z

addressed comments

haukepetersen · 2016-03-29T19:47:21Z

Code looks good, tested with #5190 and mutex_unlock_and_sleep on native and on some ARM boards. ACK

kaspar030 · 2016-03-29T19:50:51Z

squashed

cgundogan · 2016-03-29T19:53:13Z

core/include/list.h

+ * the container_of() macro in list operations.
+ * See @ref thread_add_to_list() as example.
+ */
+typedef struct list_node {


we don't want the struct name here, or am I missing something?

yes, I missed the next line. sorry (:

cgundogan · 2016-03-29T20:24:52Z

code looks good. ACK

kaspar030 · 2016-03-29T20:25:40Z

And go. Thanks for reviewing!

kaspar030 assigned Kijewski Dec 29, 2015

kaspar030 mentioned this pull request Dec 29, 2015

core: mutexes memorize holding thread id #4555

Closed

kaspar030 reviewed Dec 29, 2015
View reviewed changes

kaspar030 added CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR and removed State: WIP State: The PR is still work-in-progress and its code is not in its final presentable form yet labels Jan 26, 2016

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from 351a2fe to c4e3849 Compare February 8, 2016 14:01

jnohlgard reviewed Feb 8, 2016
View reviewed changes

OlegHahm added the CI: needs squashing Commits in this PR need to be squashed; If set, CI systems will mark this PR as unmergable label Feb 8, 2016

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from c4e3849 to 48acafa Compare February 22, 2016 00:18

kaspar030 mentioned this pull request Feb 22, 2016

core: mutex: don't use atomic function whith ISR's disabled #4365

Closed

OlegHahm mentioned this pull request Feb 28, 2016

core: mbox: initial commit #4919

Merged

1 task

miri64 reviewed Feb 28, 2016
View reviewed changes

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from 48acafa to 7cad459 Compare February 28, 2016 23:04

This was referenced Feb 29, 2016

core: make clist singly-linked #4923

Merged

core: reduce types of tcb->status and tcb->priority #4924

Merged

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from 4cc6e0e to 3cbcf3c Compare March 21, 2016 10:56

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from 3cbcf3c to 0b5ea41 Compare March 23, 2016 23:05

haukepetersen reviewed Mar 29, 2016
View reviewed changes

core/include/list.h

*/

#ifndef __LIST_H

#define __LIST_H

Copy link

Contributor

haukepetersen Mar 29, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I thought these underscores were forbidden?

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from 0b5ea41 to a93196c Compare March 29, 2016 18:08

haukepetersen reviewed Mar 29, 2016
View reviewed changes

kaspar030 removed the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Mar 29, 2016

haukepetersen mentioned this pull request Mar 29, 2016

tests: added test for mutex unlock order #5190

Merged

kaspar030 added 4 commits March 29, 2016 21:50

core: introduce intrusive singly linked list

7c39134

core: mutex: use of intrusive linked list instead of priority queue

350c341

sys: posix: pthread: fix mutex usage

c0f39bb

sys: cpp11-compat: adapt to changed mutex implementation

3d9020e

kaspar030 force-pushed the introduce_intrusive_singly_linked_list branch from f60ec99 to 3d9020e Compare March 29, 2016 19:50

kaspar030 added the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Mar 29, 2016

cgundogan reviewed Mar 29, 2016
View reviewed changes

kaspar030 merged commit f626ee5 into RIOT-OS:master Mar 29, 2016

kaspar030 deleted the introduce_intrusive_singly_linked_list branch March 29, 2016 20:25

kaspar030 restored the introduce_intrusive_singly_linked_list branch March 29, 2016 22:22

jnohlgard mentioned this pull request Jul 17, 2016

core: improve clist #5629

Merged

jnohlgard mentioned this pull request Jul 26, 2016

cpp11: clang doesn't allow mutex_t to be used with constexpr #4583

Closed

kaspar030 deleted the introduce_intrusive_singly_linked_list branch February 7, 2017 22:12

core: mutex: several optimizations #4557

core: mutex: several optimizations #4557

Uh oh!

Conversation

kaspar030 commented Dec 29, 2015

Uh oh!

kaspar030 commented Dec 29, 2015

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Kijewski commented Dec 29, 2015

Uh oh!

kaspar030 commented Dec 29, 2015

Uh oh!

kaspar030 commented Jan 4, 2016

Uh oh!

jnohlgard commented Feb 8, 2016

Uh oh!

kaspar030 commented Feb 8, 2016

Uh oh!

jnohlgard commented Feb 8, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kaspar030 commented Feb 8, 2016

Uh oh!

kaspar030 commented Feb 22, 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kaspar030 Mar 23, 2016 via email

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kaspar030 commented Feb 28, 2016

Uh oh!

OlegHahm commented Mar 23, 2016

Uh oh!

kaspar030 commented Mar 23, 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!

kaspar030 commented Mar 29, 2016

Uh oh!

haukepetersen commented Mar 29, 2016

Uh oh!

kaspar030 commented Mar 29, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cgundogan commented Mar 29, 2016

Uh oh!

kaspar030 commented Mar 29, 2016

Uh oh!

Uh oh!