In preparation to limit the scope of a list iterator to the list
traversal loop, use a dedicated pointer to point to the found element [1].
Before, the code implicitly used the head when no element was found
when using &pos->list. Since the new variable is only set if an
element was found, the list_add() is performed within the loop
and only done after the loop if it is done on the list head directly.
Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
Signed-off-by: Jakob Koschel <[email protected]>
---
drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
1 file changed, 9 insertions(+), 5 deletions(-)
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index b7e95d60a6e4..cfcae4d19eef 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
if (list_empty(&gating_cfg->entries)) {
list_add(&e->list, &gating_cfg->entries);
} else {
- struct sja1105_gate_entry *p;
+ struct sja1105_gate_entry *p = NULL, *iter;
- list_for_each_entry(p, &gating_cfg->entries, list) {
- if (p->interval == e->interval) {
+ list_for_each_entry(iter, &gating_cfg->entries, list) {
+ if (iter->interval == e->interval) {
NL_SET_ERR_MSG_MOD(extack,
"Gate conflict");
rc = -EBUSY;
goto err;
}
- if (e->interval < p->interval)
+ if (e->interval < iter->interval) {
+ p = iter;
+ list_add(&e->list, iter->list.prev);
break;
+ }
}
- list_add(&e->list, p->list.prev);
+ if (!p)
+ list_add(&e->list, gating_cfg->entries.prev);
}
gating_cfg->num_entries++;
--
2.25.1
On Thu, 7 Apr 2022 12:28:47 +0200 Jakob Koschel wrote:
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..cfcae4d19eef 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> if (list_empty(&gating_cfg->entries)) {
> list_add(&e->list, &gating_cfg->entries);
> } else {
> - struct sja1105_gate_entry *p;
> + struct sja1105_gate_entry *p = NULL, *iter;
>
> - list_for_each_entry(p, &gating_cfg->entries, list) {
> - if (p->interval == e->interval) {
> + list_for_each_entry(iter, &gating_cfg->entries, list) {
> + if (iter->interval == e->interval) {
> NL_SET_ERR_MSG_MOD(extack,
> "Gate conflict");
> rc = -EBUSY;
> goto err;
> }
>
> - if (e->interval < p->interval)
> + if (e->interval < iter->interval) {
> + p = iter;
> + list_add(&e->list, iter->list.prev);
> break;
> + }
> }
> - list_add(&e->list, p->list.prev);
> + if (!p)
> + list_add(&e->list, gating_cfg->entries.prev);
This turns a pretty slick piece of code into something ugly :(
I'd rather you open coded the iteration here than make it more
complex to satisfy "safe coding guidelines".
Also the list_add() could be converted to list_add_tail().
Le 07/04/2022 à 12:28, Jakob Koschel a écrit :
> In preparation to limit the scope of a list iterator to the list
> traversal loop, use a dedicated pointer to point to the found element [1].
>
> Before, the code implicitly used the head when no element was found
> when using &pos->list. Since the new variable is only set if an
> element was found, the list_add() is performed within the loop
> and only done after the loop if it is done on the list head directly.
>
> Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
> Signed-off-by: Jakob Koschel <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
> 1 file changed, 9 insertions(+), 5 deletions(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..cfcae4d19eef 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> if (list_empty(&gating_cfg->entries)) {
> list_add(&e->list, &gating_cfg->entries);
> } else {
> - struct sja1105_gate_entry *p;
> + struct sja1105_gate_entry *p = NULL, *iter;
>
> - list_for_each_entry(p, &gating_cfg->entries, list) {
> - if (p->interval == e->interval) {
> + list_for_each_entry(iter, &gating_cfg->entries, list) {
> + if (iter->interval == e->interval) {
> NL_SET_ERR_MSG_MOD(extack,
> "Gate conflict");
> rc = -EBUSY;
> goto err;
> }
>
> - if (e->interval < p->interval)
> + if (e->interval < iter->interval) {
> + p = iter;
> + list_add(&e->list, iter->list.prev);
> break;
> + }
> }
> - list_add(&e->list, p->list.prev);
> + if (!p)
> + list_add(&e->list, gating_cfg->entries.prev);
> }
>
> gating_cfg->num_entries++;
This change looks ugly, why duplicating the list_add() to do the same ?
At the end of the loop the pointer contains gating_cfg->entries, so it
was cleaner before.
If you don't want to use the loop index outside the loop, fair enough,
all you have to do is:
struct sja1105_gate_entry *p, *iter;
list_for_each_entry(iter, &gating_cfg->entries, list) {
if (iter->interval == e->interval) {
NL_SET_ERR_MSG_MOD(extack,
"Gate conflict");
rc = -EBUSY;
goto err;
}
p = iter;
if (e->interval < iter->interval)
break;
}
list_add(&e->list, p->list.prev);
Christophe
Hello Jakob,
On Thu, Apr 07, 2022 at 12:28:47PM +0200, Jakob Koschel wrote:
> In preparation to limit the scope of a list iterator to the list
> traversal loop, use a dedicated pointer to point to the found element [1].
>
> Before, the code implicitly used the head when no element was found
> when using &pos->list. Since the new variable is only set if an
> element was found, the list_add() is performed within the loop
> and only done after the loop if it is done on the list head directly.
>
> Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
> Signed-off-by: Jakob Koschel <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
> 1 file changed, 9 insertions(+), 5 deletions(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..cfcae4d19eef 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> if (list_empty(&gating_cfg->entries)) {
> list_add(&e->list, &gating_cfg->entries);
> } else {
> - struct sja1105_gate_entry *p;
> + struct sja1105_gate_entry *p = NULL, *iter;
>
> - list_for_each_entry(p, &gating_cfg->entries, list) {
> - if (p->interval == e->interval) {
> + list_for_each_entry(iter, &gating_cfg->entries, list) {
> + if (iter->interval == e->interval) {
> NL_SET_ERR_MSG_MOD(extack,
> "Gate conflict");
> rc = -EBUSY;
> goto err;
> }
>
> - if (e->interval < p->interval)
> + if (e->interval < iter->interval) {
> + p = iter;
> + list_add(&e->list, iter->list.prev);
> break;
> + }
> }
> - list_add(&e->list, p->list.prev);
> + if (!p)
> + list_add(&e->list, gating_cfg->entries.prev);
> }
>
> gating_cfg->num_entries++;
> --
> 2.25.1
>
I apologize in advance if I've misinterpreted the end goal of your patch.
I do have a vague suspicion I understand what you're trying to achieve,
and in that case, would you mind using this patch instead of yours?
I think it still preserves the intention of the code in a clean manner.
-----------------------------[ cut here ]-----------------------------
From 7aed740750d1bc3bff6e85fd33298f5905bb4e01 Mon Sep 17 00:00:00 2001
From: Vladimir Oltean <[email protected]>
Date: Fri, 8 Apr 2022 13:55:14 +0300
Subject: [PATCH] net: dsa: sja1105: avoid use of type-confused pointer in
sja1105_insert_gate_entry()
It appears that list_for_each_entry() leaks a type-confused pointer when
the iteration loop ends with no early break, since "*p" will no longer
point to a "struct sja1105_gate_entry", but rather to some memory in
front of "gating_cfg->entries".
This isn't actually a problem here, because if the element we insert has
the highest interval, therefore we never exit the loop early, "p->list"
(which is all that we use outside the loop) will in fact point to
"gating_cfg->entries" even though "p" itself is invalid.
Nonetheless, there are preparations to increase the safety of
list_for_each_entry() by making it impossible to use the encapsulating
structure of the iterator element outside the loop. So something needs
to change here before those preparations go in, even though this
constitutes legitimate use.
Make it clear that we are not dereferencing members of the encapsulating
"struct sja1105_gate_entry" outside the loop, by using the regular
list_for_each() iterator, and dereferencing the struct sja1105_gate_entry
only within the loop.
With list_for_each(), the iterator element at the end of the loop does
have a sane value in all cases, and we can just use that as the "head"
argument of list_add().
Signed-off-by: Vladimir Oltean <[email protected]>
---
drivers/net/dsa/sja1105/sja1105_vl.c | 12 +++++++++---
1 file changed, 9 insertions(+), 3 deletions(-)
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index c0e45b393fde..fe93c80fe5ef 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -27,9 +27,15 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
if (list_empty(&gating_cfg->entries)) {
list_add(&e->list, &gating_cfg->entries);
} else {
- struct sja1105_gate_entry *p;
+ struct list_head *pos;
+
+ /* We cannot safely use list_for_each_entry()
+ * because we dereference "pos" after the loop
+ */
+ list_for_each(pos, &gating_cfg->entries) {
+ struct sja1105_gate_entry *p;
- list_for_each_entry(p, &gating_cfg->entries, list) {
+ p = list_entry(pos, struct sja1105_gate_entry, list);
if (p->interval == e->interval) {
NL_SET_ERR_MSG_MOD(extack,
"Gate conflict");
@@ -40,7 +46,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
if (e->interval < p->interval)
break;
}
- list_add(&e->list, p->list.prev);
+ list_add(&e->list, pos->prev);
}
gating_cfg->num_entries++;
-----------------------------[ cut here ]-----------------------------
On Sat, 9 Apr 2022 01:58:29 +0200 Jakob Koschel wrote:
> > This turns a pretty slick piece of code into something ugly :(
> > I'd rather you open coded the iteration here than make it more
> > complex to satisfy "safe coding guidelines".
>
> I'm not entirely sure I understand what you mean with
> "open coded the iteration". But maybe the solution proposed by Vladimir [1]
> works for you?
Yup, that's what I meant!
> I'm planning to rewrite the cases in that way for the relevant ones.
>
> > Also the list_add() could be converted to list_add_tail().
>
> Good point, I wasn't sure if that's considered as something that should be
> done as a separate change. I'm happy to include it in v2.
Ack, separate patch would be better for that. I guess Vladimir may have
used .prev on purpose, since _tail() doesn't intuitively scream _after()
Anyway, not important.
Hello Jakub,
> On 8. Apr 2022, at 05:54, Jakub Kicinski <[email protected]> wrote:
>
> On Thu, 7 Apr 2022 12:28:47 +0200 Jakob Koschel wrote:
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index b7e95d60a6e4..cfcae4d19eef 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> if (list_empty(&gating_cfg->entries)) {
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> - struct sja1105_gate_entry *p;
>> + struct sja1105_gate_entry *p = NULL, *iter;
>>
>> - list_for_each_entry(p, &gating_cfg->entries, list) {
>> - if (p->interval == e->interval) {
>> + list_for_each_entry(iter, &gating_cfg->entries, list) {
>> + if (iter->interval == e->interval) {
>> NL_SET_ERR_MSG_MOD(extack,
>> "Gate conflict");
>> rc = -EBUSY;
>> goto err;
>> }
>>
>> - if (e->interval < p->interval)
>> + if (e->interval < iter->interval) {
>> + p = iter;
>> + list_add(&e->list, iter->list.prev);
>> break;
>> + }
>> }
>> - list_add(&e->list, p->list.prev);
>> + if (!p)
>> + list_add(&e->list, gating_cfg->entries.prev);
>
> This turns a pretty slick piece of code into something ugly :(
> I'd rather you open coded the iteration here than make it more
> complex to satisfy "safe coding guidelines".
I'm not entirely sure I understand what you mean with
"open coded the iteration". But maybe the solution proposed by Vladimir [1]
works for you? I'm planning to rewrite the cases in that way for the relevant
ones.
>
> Also the list_add() could be converted to list_add_tail().
Good point, I wasn't sure if that's considered as something that should be
done as a separate change. I'm happy to include it in v2.
Thanks for the input.
Jakob
[1] https://lore.kernel.org/linux-kernel/20220408114120.tvf2lxvhfqbnrlml@skbuf/
On Sat, Apr 09, 2022 at 01:58:29AM +0200, Jakob Koschel wrote:
> Hello Jakub,
> > Also the list_add() could be converted to list_add_tail().
>
> Good point, I wasn't sure if that's considered as something that should be
> done as a separate change. I'm happy to include it in v2.
By now you probably studied more list access patterns than I did,
but I wrote that deliberately using list_add(..., pos->prev) rather than
list_add_tail(), because even though the code is the same, I tend to
think of the "head" argument of list_add_tail() as being the actual head
of the list, and therefore the head->prev being the tail of the list
(hence the name), something which doesn't hold true here where we're
inserting in the middle of the list. Anyway it's just a name and that's
what felt natural to me at the time, I won't oppose the change, but do
make it a separate change and not clump it together with the unrelated
list_for_each_entry() -> list_for_each() change.
Hey Christophe,
> On 8. Apr 2022, at 09:47, Christophe Leroy <[email protected]> wrote:
>
>
>
> Le 07/04/2022 à 12:28, Jakob Koschel a écrit :
>> In preparation to limit the scope of a list iterator to the list
>> traversal loop, use a dedicated pointer to point to the found element [1].
>>
>> Before, the code implicitly used the head when no element was found
>> when using &pos->list. Since the new variable is only set if an
>> element was found, the list_add() is performed within the loop
>> and only done after the loop if it is done on the list head directly.
>>
>> Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
>> Signed-off-by: Jakob Koschel <[email protected]>
>> ---
>> drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
>> 1 file changed, 9 insertions(+), 5 deletions(-)
>>
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index b7e95d60a6e4..cfcae4d19eef 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> if (list_empty(&gating_cfg->entries)) {
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> - struct sja1105_gate_entry *p;
>> + struct sja1105_gate_entry *p = NULL, *iter;
>>
>> - list_for_each_entry(p, &gating_cfg->entries, list) {
>> - if (p->interval == e->interval) {
>> + list_for_each_entry(iter, &gating_cfg->entries, list) {
>> + if (iter->interval == e->interval) {
>> NL_SET_ERR_MSG_MOD(extack,
>> "Gate conflict");
>> rc = -EBUSY;
>> goto err;
>> }
>>
>> - if (e->interval < p->interval)
>> + if (e->interval < iter->interval) {
>> + p = iter;
>> + list_add(&e->list, iter->list.prev);
>> break;
>> + }
>> }
>> - list_add(&e->list, p->list.prev);
>> + if (!p)
>> + list_add(&e->list, gating_cfg->entries.prev);
>> }
>>
>> gating_cfg->num_entries++;
>
> This change looks ugly, why duplicating the list_add() to do the same ?
> At the end of the loop the pointer contains gating_cfg->entries, so it
> was cleaner before.
>
> If you don't want to use the loop index outside the loop, fair enough,
> all you have to do is:
>
> struct sja1105_gate_entry *p, *iter;
>
> list_for_each_entry(iter, &gating_cfg->entries, list) {
> if (iter->interval == e->interval) {
> NL_SET_ERR_MSG_MOD(extack,
> "Gate conflict");
> rc = -EBUSY;
> goto err;
> }
> p = iter;
>
> if (e->interval < iter->interval)
> break;
> }
> list_add(&e->list, p->list.prev);
Thanks for the review and input.
The code you are showing here would have an uninitialized access to 'p'
if the list is empty.
Also 'p->list.prev' will be the second last entry if the list iterator
ran through completely, whereas the original code was pointing to the last
entry of the list.
IMO Vladimir Oltean posted a nice alternative way to solve it, see [1].
That way it keeps the semantics of the code the same and doesn't duplicate
the list_add.
>
>
>
> Christophe
[1] https://lore.kernel.org/linux-kernel/20220408114120.tvf2lxvhfqbnrlml@skbuf/
Thanks,
Jakob
On Sun, Apr 10, 2022 at 12:51:56PM +0200, Jakob Koschel wrote:
> I've just looked at this again in a bit more detail while integrating it into the patch series.
>
> I realized that this just shifts the 'problem' to using the 'pos' iterator variable after the loop.
> If the scope of the list iterator would be lowered to the list traversal loop it would also make sense
> to also do it for list_for_each().
Yes, but list_for_each() was never formulated as being problematic in
the same way as list_for_each_entry(), was it? I guess I'm starting to
not understand what is the true purpose of the changes.
> What do you think about doing it this way:
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..f5b0502c1098 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> list_add(&e->list, &gating_cfg->entries);
> } else {
> struct sja1105_gate_entry *p;
> + struct list_head *pos = NULL;
>
> list_for_each_entry(p, &gating_cfg->entries, list) {
> if (p->interval == e->interval) {
> @@ -37,10 +38,14 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> goto err;
> }
>
> - if (e->interval < p->interval)
> + if (e->interval < p->interval) {
> + pos = &p->list;
> break;
> + }
> }
> - list_add(&e->list, p->list.prev);
> + if (!pos)
> + pos = &gating_cfg->entries;
> + list_add(&e->list, pos->prev);
> }
>
> gating_cfg->num_entries++;
> --
>
> >
> > Thanks for the suggestion.
> >
> >> }
> >>
> >> gating_cfg->num_entries++;
> >> -----------------------------[ cut here ]-----------------------------
> >
> > [1] https://lore.kernel.org/linux-kernel/[email protected]/
> >
> > Jakob
>
> Thanks,
> Jakob
> On 10. Apr 2022, at 14:39, Jakob Koschel <[email protected]> wrote:
>
>
>
>> On 10. Apr 2022, at 13:05, Vladimir Oltean <[email protected]> wrote:
>>
>> On Sun, Apr 10, 2022 at 12:51:56PM +0200, Jakob Koschel wrote:
>>> I've just looked at this again in a bit more detail while integrating it into the patch series.
>>>
>>> I realized that this just shifts the 'problem' to using the 'pos' iterator variable after the loop.
>>> If the scope of the list iterator would be lowered to the list traversal loop it would also make sense
>>> to also do it for list_for_each().
>>
>> Yes, but list_for_each() was never formulated as being problematic in
>> the same way as list_for_each_entry(), was it? I guess I'm starting to
>> not understand what is the true purpose of the changes.
>
> Sorry for having caused the confusion. Let me elaborate a bit to give more context.
>
> There are two main benefits of this entire effort.
>
> 1) fix the architectural bugs and avoid any missuse of the list iterator after the loop
> by construction. This only concerns the list_for_each_entry_*() macros and your change
> will allow lowering the scope for all of those. It might be debatable that it would be
> more consistent to lower the scope for list_for_each() as well, but it wouldn't be
> strictly necessary.
>
> 2) fix *possible* speculative bugs. In our project, Kasper [1], we were able to show
> that this can be an issue for the list traversal macros (and this is how the entire
> effort started).
> The reason is that the processor might run an additional loop iteration in speculative
> execution with the iterator variable computed based on the head element. This can
> (and we have verified this) happen if the CPU incorrectly
> assumes !list_entry_is_head(pos, head, member).
>
> If this happens, all memory accesses based on the iterator variable *potentially* open
> the chance for spectre [2] gadgets. The proposed mitigation was setting the iterator variable
> to NULL when the terminating condition is reached (in speculative safe way). Then,
> the additional speculative list iteration would still execute but won't access any
> potential secret data.
>
> And this would also be required for list_for_each() since combined with the list_entry()
> within the loop it basically is semantically identical to list_for_each_entry()
> for the additional speculative iteration.
>
> Now, I have no strong opinion on going all the way and since 2) is not the main motivation
> for this I'm also fine with sticking to your proposed solution, but it would mean that implementing
> a "speculative safe" list_for_each() will be more difficult in the future since it is using
> the iterator of list_for_each() past the loop.
>
> I hope this explains the background a bit better.
>
>>
>>> What do you think about doing it this way:
>>>
>>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>>> index b7e95d60a6e4..f5b0502c1098 100644
>>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>>> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>>> list_add(&e->list, &gating_cfg->entries);
>>> } else {
>>> struct sja1105_gate_entry *p;
>>> + struct list_head *pos = NULL;
>>>
>>> list_for_each_entry(p, &gating_cfg->entries, list) {
>>> if (p->interval == e->interval) {
>>> @@ -37,10 +38,14 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>>> goto err;
>>> }
>>>
>>> - if (e->interval < p->interval)
>>> + if (e->interval < p->interval) {
>>> + pos = &p->list;
>>> break;
>>> + }
>>> }
>>> - list_add(&e->list, p->list.prev);
>>> + if (!pos)
>>> + pos = &gating_cfg->entries;
>>> + list_add(&e->list, pos->prev);
>>> }
>>>
>>> gating_cfg->num_entries++;
>>> --
>>>
>>>>
>>>> Thanks for the suggestion.
>>>>
>>>>> }
>>>>>
>>>>> gating_cfg->num_entries++;
>>>>> -----------------------------[ cut here ]-----------------------------
>>>>
>>>> [1] https://lore.kernel.org/linux-kernel/[email protected]/
>>>>
>>>> Jakob
>>>
>>> Thanks,
>>> Jakob
>
> Thanks,
> Jakob
>
> [1] https://www.vusec.net/projects/kasper/
> [2] https://spectreattack.com/spectre.pdf
Btw, I just realized that the if (!pos) is not necessary. This should simply do it:
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index b7e95d60a6e4..2d59e75a9e3d 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
list_add(&e->list, &gating_cfg->entries);
} else {
+ struct list_head *pos = &gating_cfg->entries;
struct sja1105_gate_entry *p;
list_for_each_entry(p, &gating_cfg->entries, list) {
if (p->interval == e->interval) {
@@ -37,10 +38,12 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
goto err;
}
- if (e->interval < p->interval)
+ if (e->interval < p->interval) {
+ pos = &p->list;
break;
+ }
}
- list_add(&e->list, p->list.prev);
+ list_add(&e->list, pos->prev);
}
gating_cfg->num_entries++;
--
2.25.1
Thanks,
Jakob
Hello Vladimir,
> On 8. Apr 2022, at 13:41, Vladimir Oltean <[email protected]> wrote:
>
> Hello Jakob,
>
> On Thu, Apr 07, 2022 at 12:28:47PM +0200, Jakob Koschel wrote:
>> In preparation to limit the scope of a list iterator to the list
>> traversal loop, use a dedicated pointer to point to the found element [1].
>>
>> Before, the code implicitly used the head when no element was found
>> when using &pos->list. Since the new variable is only set if an
>> element was found, the list_add() is performed within the loop
>> and only done after the loop if it is done on the list head directly.
>>
>> Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
>> Signed-off-by: Jakob Koschel <[email protected]>
>> ---
>> drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
>> 1 file changed, 9 insertions(+), 5 deletions(-)
>>
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index b7e95d60a6e4..cfcae4d19eef 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> if (list_empty(&gating_cfg->entries)) {
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> - struct sja1105_gate_entry *p;
>> + struct sja1105_gate_entry *p = NULL, *iter;
>>
>> - list_for_each_entry(p, &gating_cfg->entries, list) {
>> - if (p->interval == e->interval) {
>> + list_for_each_entry(iter, &gating_cfg->entries, list) {
>> + if (iter->interval == e->interval) {
>> NL_SET_ERR_MSG_MOD(extack,
>> "Gate conflict");
>> rc = -EBUSY;
>> goto err;
>> }
>>
>> - if (e->interval < p->interval)
>> + if (e->interval < iter->interval) {
>> + p = iter;
>> + list_add(&e->list, iter->list.prev);
>> break;
>> + }
>> }
>> - list_add(&e->list, p->list.prev);
>> + if (!p)
>> + list_add(&e->list, gating_cfg->entries.prev);
>> }
>>
>> gating_cfg->num_entries++;
>> --
>> 2.25.1
>>
>
> I apologize in advance if I've misinterpreted the end goal of your patch.
> I do have a vague suspicion I understand what you're trying to achieve,
> and in that case, would you mind using this patch instead of yours?
I think you are very much spot on!
> I think it still preserves the intention of the code in a clean manner.
>
> -----------------------------[ cut here ]-----------------------------
> From 7aed740750d1bc3bff6e85fd33298f5905bb4e01 Mon Sep 17 00:00:00 2001
> From: Vladimir Oltean <[email protected]>
> Date: Fri, 8 Apr 2022 13:55:14 +0300
> Subject: [PATCH] net: dsa: sja1105: avoid use of type-confused pointer in
> sja1105_insert_gate_entry()
>
> It appears that list_for_each_entry() leaks a type-confused pointer when
> the iteration loop ends with no early break, since "*p" will no longer
> point to a "struct sja1105_gate_entry", but rather to some memory in
> front of "gating_cfg->entries".
>
> This isn't actually a problem here, because if the element we insert has
> the highest interval, therefore we never exit the loop early, "p->list"
> (which is all that we use outside the loop) will in fact point to
> "gating_cfg->entries" even though "p" itself is invalid.
>
> Nonetheless, there are preparations to increase the safety of
> list_for_each_entry() by making it impossible to use the encapsulating
> structure of the iterator element outside the loop. So something needs
> to change here before those preparations go in, even though this
> constitutes legitimate use.
>
> Make it clear that we are not dereferencing members of the encapsulating
> "struct sja1105_gate_entry" outside the loop, by using the regular
> list_for_each() iterator, and dereferencing the struct sja1105_gate_entry
> only within the loop.
>
> With list_for_each(), the iterator element at the end of the loop does
> have a sane value in all cases, and we can just use that as the "head"
> argument of list_add().
>
> Signed-off-by: Vladimir Oltean <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 12 +++++++++---
> 1 file changed, 9 insertions(+), 3 deletions(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index c0e45b393fde..fe93c80fe5ef 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -27,9 +27,15 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> if (list_empty(&gating_cfg->entries)) {
> list_add(&e->list, &gating_cfg->entries);
> } else {
> - struct sja1105_gate_entry *p;
> + struct list_head *pos;
> +
> + /* We cannot safely use list_for_each_entry()
> + * because we dereference "pos" after the loop
> + */
> + list_for_each(pos, &gating_cfg->entries) {
> + struct sja1105_gate_entry *p;
>
> - list_for_each_entry(p, &gating_cfg->entries, list) {
> + p = list_entry(pos, struct sja1105_gate_entry, list);
> if (p->interval == e->interval) {
> NL_SET_ERR_MSG_MOD(extack,
> "Gate conflict");
> @@ -40,7 +46,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> if (e->interval < p->interval)
> break;
> }
> - list_add(&e->list, p->list.prev);
> + list_add(&e->list, pos->prev);
I was actually considering doing it this way before but wasn't sure if this would be preferred.
I've done something like this in [1] and it does turn out quite well.
I'll integrate this in the v2 series.
Thanks for the suggestion.
> }
>
> gating_cfg->num_entries++;
> -----------------------------[ cut here ]-----------------------------
[1] https://lore.kernel.org/linux-kernel/[email protected]/
Jakob
> On 10. Apr 2022, at 13:05, Vladimir Oltean <[email protected]> wrote:
>
> On Sun, Apr 10, 2022 at 12:51:56PM +0200, Jakob Koschel wrote:
>> I've just looked at this again in a bit more detail while integrating it into the patch series.
>>
>> I realized that this just shifts the 'problem' to using the 'pos' iterator variable after the loop.
>> If the scope of the list iterator would be lowered to the list traversal loop it would also make sense
>> to also do it for list_for_each().
>
> Yes, but list_for_each() was never formulated as being problematic in
> the same way as list_for_each_entry(), was it? I guess I'm starting to
> not understand what is the true purpose of the changes.
Sorry for having caused the confusion. Let me elaborate a bit to give more context.
There are two main benefits of this entire effort.
1) fix the architectural bugs and avoid any missuse of the list iterator after the loop
by construction. This only concerns the list_for_each_entry_*() macros and your change
will allow lowering the scope for all of those. It might be debatable that it would be
more consistent to lower the scope for list_for_each() as well, but it wouldn't be
strictly necessary.
2) fix *possible* speculative bugs. In our project, Kasper [1], we were able to show
that this can be an issue for the list traversal macros (and this is how the entire
effort started).
The reason is that the processor might run an additional loop iteration in speculative
execution with the iterator variable computed based on the head element. This can
(and we have verified this) happen if the CPU incorrectly
assumes !list_entry_is_head(pos, head, member).
If this happens, all memory accesses based on the iterator variable *potentially* open
the chance for spectre [2] gadgets. The proposed mitigation was setting the iterator variable
to NULL when the terminating condition is reached (in speculative safe way). Then,
the additional speculative list iteration would still execute but won't access any
potential secret data.
And this would also be required for list_for_each() since combined with the list_entry()
within the loop it basically is semantically identical to list_for_each_entry()
for the additional speculative iteration.
Now, I have no strong opinion on going all the way and since 2) is not the main motivation
for this I'm also fine with sticking to your proposed solution, but it would mean that implementing
a "speculative safe" list_for_each() will be more difficult in the future since it is using
the iterator of list_for_each() past the loop.
I hope this explains the background a bit better.
>
>> What do you think about doing it this way:
>>
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index b7e95d60a6e4..f5b0502c1098 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> struct sja1105_gate_entry *p;
>> + struct list_head *pos = NULL;
>>
>> list_for_each_entry(p, &gating_cfg->entries, list) {
>> if (p->interval == e->interval) {
>> @@ -37,10 +38,14 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> goto err;
>> }
>>
>> - if (e->interval < p->interval)
>> + if (e->interval < p->interval) {
>> + pos = &p->list;
>> break;
>> + }
>> }
>> - list_add(&e->list, p->list.prev);
>> + if (!pos)
>> + pos = &gating_cfg->entries;
>> + list_add(&e->list, pos->prev);
>> }
>>
>> gating_cfg->num_entries++;
>> --
>>
>>>
>>> Thanks for the suggestion.
>>>
>>>> }
>>>>
>>>> gating_cfg->num_entries++;
>>>> -----------------------------[ cut here ]-----------------------------
>>>
>>> [1] https://lore.kernel.org/linux-kernel/[email protected]/
>>>
>>> Jakob
>>
>> Thanks,
>> Jakob
Thanks,
Jakob
[1] https://www.vusec.net/projects/kasper/
[2] https://spectreattack.com/spectre.pdf
On Sun, Apr 10, 2022 at 08:24:37PM +0200, Jakob Koschel wrote:
> Btw, I just realized that the if (!pos) is not necessary. This should simply do it:
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..2d59e75a9e3d 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> list_add(&e->list, &gating_cfg->entries);
> } else {
> + struct list_head *pos = &gating_cfg->entries;
> struct sja1105_gate_entry *p;
>
> list_for_each_entry(p, &gating_cfg->entries, list) {
> if (p->interval == e->interval) {
> @@ -37,10 +38,12 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> goto err;
> }
>
> - if (e->interval < p->interval)
> + if (e->interval < p->interval) {
> + pos = &p->list;
> break;
> + }
> }
> - list_add(&e->list, p->list.prev);
> + list_add(&e->list, pos->prev);
> }
>
> gating_cfg->num_entries++;
> --
> 2.25.1
I think we can give this a turn that is actually beneficial for the driver.
I've prepared and tested 3 patches on this function, see below.
Concrete improvements:
- that thing with list_for_each_entry() and list_for_each()
- no more special-casing of an empty list
- simplifying the error path
- that thing with list_add_tail()
What do you think about the changes below?
From 5b952b75e239cbe96729cf78c17e8d9725c9617c Mon Sep 17 00:00:00 2001
From: Vladimir Oltean <[email protected]>
Date: Sun, 10 Apr 2022 22:21:41 +0300
Subject: [PATCH 1/3] net: dsa: sja1105: remove use of iterator after
list_for_each_entry() loop
Jakob Koschel explains in the link below that there is a desire to
syntactically change list_for_each_entry() and list_for_each() such that
it becomes impossible to use the iterator variable outside the scope of
the loop.
Although sja1105_insert_gate_entry() makes legitimate use of the
iterator pointer when it breaks out, the pattern it uses may become
illegal, so it needs to change.
It is deemed acceptable to use a copy of the loop iterator, and
sja1105_insert_gate_entry() only needs to know the list_head element
before which the list insertion should be made. So let's profit from the
occasion and refactor the list iteration to a dedicated function.
An additional benefit is given by the fact that with the helper function
in place, we no longer need to special-case the empty list, since it is
equivalent to not having found any gating entry larger than the
specified interval in the list. We just need to insert at the tail of
that list (list_add vs list_add_tail on an empty list does the same
thing).
Link: https://patchwork.kernel.org/project/netdevbpf/patch/[email protected]/#24810127
Signed-off-by: Vladimir Oltean <[email protected]>
---
drivers/net/dsa/sja1105/sja1105_vl.c | 46 ++++++++++++++++++----------
1 file changed, 29 insertions(+), 17 deletions(-)
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index b7e95d60a6e4..369be2ac3587 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -7,6 +7,27 @@
#define SJA1105_SIZE_VL_STATUS 8
+static struct list_head *
+sja1105_first_entry_longer_than(struct list_head *entries,
+ s64 interval,
+ struct netlink_ext_ack *extack)
+{
+ struct sja1105_gate_entry *p;
+
+ list_for_each_entry(p, entries, list) {
+ if (p->interval == interval) {
+ NL_SET_ERR_MSG_MOD(extack, "Gate conflict");
+ return ERR_PTR(-EBUSY);
+ }
+
+ if (interval < p->interval)
+ return &p->list;
+ }
+
+ /* Empty list, or specified interval is largest within the list */
+ return entries;
+}
+
/* Insert into the global gate list, sorted by gate action time. */
static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
struct sja1105_rule *rule,
@@ -14,6 +35,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
struct netlink_ext_ack *extack)
{
struct sja1105_gate_entry *e;
+ struct list_head *pos;
int rc;
e = kzalloc(sizeof(*e), GFP_KERNEL);
@@ -24,25 +46,15 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
e->gate_state = gate_state;
e->interval = entry_time;
- if (list_empty(&gating_cfg->entries)) {
- list_add(&e->list, &gating_cfg->entries);
- } else {
- struct sja1105_gate_entry *p;
-
- list_for_each_entry(p, &gating_cfg->entries, list) {
- if (p->interval == e->interval) {
- NL_SET_ERR_MSG_MOD(extack,
- "Gate conflict");
- rc = -EBUSY;
- goto err;
- }
-
- if (e->interval < p->interval)
- break;
- }
- list_add(&e->list, p->list.prev);
+ pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
+ e->interval, extack);
+ if (IS_ERR(pos)) {
+ rc = PTR_ERR(pos);
+ goto err;
}
+ list_add(&e->list, pos->prev);
+
gating_cfg->num_entries++;
return 0;
--
2.25.1
From b6385f62d730b69007ea218e885461542ca4c44c Mon Sep 17 00:00:00 2001
From: Vladimir Oltean <[email protected]>
Date: Sun, 10 Apr 2022 22:34:35 +0300
Subject: [PATCH 2/3] net: dsa: sja1105: reorder
sja1105_first_entry_longer_than with memory allocation
sja1105_first_entry_longer_than() does not make use of the full struct
sja1105_gate_entry *e, just of e->interval which is set from the passed
entry_time.
This means that if there is a gate conflict, we have allocated e for
nothing, just to free it later. Reorder the memory allocation and the
function call, to avoid that and simplify the error unwind path.
Signed-off-by: Vladimir Oltean <[email protected]>
---
drivers/net/dsa/sja1105/sja1105_vl.c | 17 +++++------------
1 file changed, 5 insertions(+), 12 deletions(-)
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index 369be2ac3587..e5ea8eb9ec4e 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -36,7 +36,11 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
{
struct sja1105_gate_entry *e;
struct list_head *pos;
- int rc;
+
+ pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
+ entry_time, extack);
+ if (IS_ERR(pos))
+ return PTR_ERR(pos);
e = kzalloc(sizeof(*e), GFP_KERNEL);
if (!e)
@@ -45,22 +49,11 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
e->rule = rule;
e->gate_state = gate_state;
e->interval = entry_time;
-
- pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
- e->interval, extack);
- if (IS_ERR(pos)) {
- rc = PTR_ERR(pos);
- goto err;
- }
-
list_add(&e->list, pos->prev);
gating_cfg->num_entries++;
return 0;
-err:
- kfree(e);
- return rc;
}
/* The gate entries contain absolute times in their e->interval field. Convert
--
2.25.1
From 8aa272b8a3f53aba7b80f181b275e040b9aaed8d Mon Sep 17 00:00:00 2001
From: Vladimir Oltean <[email protected]>
Date: Sun, 10 Apr 2022 22:37:14 +0300
Subject: [PATCH 3/3] net: dsa: sja1105: use list_add_tail(pos) instead of
list_add(pos->prev)
When passed a non-head list element, list_add_tail() actually adds the
new element to its left, which is what we want. Despite the slightly
confusing name, use the dedicated function which does the same thing as
the open-coded list_add(pos->prev).
Suggested-by: Jakub Kicinski <[email protected]>
Signed-off-by: Vladimir Oltean <[email protected]>
---
drivers/net/dsa/sja1105/sja1105_vl.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index e5ea8eb9ec4e..7fe9b18f1cbd 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -49,7 +49,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
e->rule = rule;
e->gate_state = gate_state;
e->interval = entry_time;
- list_add(&e->list, pos->prev);
+ list_add_tail(&e->list, pos);
gating_cfg->num_entries++;
--
2.25.1
On Sun, Apr 10, 2022 at 10:30:31PM +0200, Jakob Koschel wrote:
> > On 10. Apr 2022, at 22:02, Vladimir Oltean <[email protected]> wrote:
> >
> > On Sun, Apr 10, 2022 at 08:24:37PM +0200, Jakob Koschel wrote:
> >> Btw, I just realized that the if (!pos) is not necessary. This should simply do it:
> >>
> >> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> >> index b7e95d60a6e4..2d59e75a9e3d 100644
> >> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> >> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> >> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> >> list_add(&e->list, &gating_cfg->entries);
> >> } else {
> >> + struct list_head *pos = &gating_cfg->entries;
> >> struct sja1105_gate_entry *p;
> >>
> >> list_for_each_entry(p, &gating_cfg->entries, list) {
> >> if (p->interval == e->interval) {
> >> @@ -37,10 +38,12 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> >> goto err;
> >> }
> >>
> >> - if (e->interval < p->interval)
> >> + if (e->interval < p->interval) {
> >> + pos = &p->list;
> >> break;
> >> + }
> >> }
> >> - list_add(&e->list, p->list.prev);
> >> + list_add(&e->list, pos->prev);
> >> }
> >>
> >> gating_cfg->num_entries++;
> >> --
> >> 2.25.1
> >
> > I think we can give this a turn that is actually beneficial for the driver.
> > I've prepared and tested 3 patches on this function, see below.
> > Concrete improvements:
> > - that thing with list_for_each_entry() and list_for_each()
> > - no more special-casing of an empty list
> > - simplifying the error path
> > - that thing with list_add_tail()
> >
> > What do you think about the changes below?
>
> Thanks for all the good cooperation and help. The changes look great.
> I'll include them in v2 unless you want to do that separately, then I'll
> just remove them from the patch series.
I think it's less of a synchronization hassle if you send them along
with your list of others. Good luck.
> On 10. Apr 2022, at 22:02, Vladimir Oltean <[email protected]> wrote:
>
> On Sun, Apr 10, 2022 at 08:24:37PM +0200, Jakob Koschel wrote:
>> Btw, I just realized that the if (!pos) is not necessary. This should simply do it:
>>
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index b7e95d60a6e4..2d59e75a9e3d 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> + struct list_head *pos = &gating_cfg->entries;
>> struct sja1105_gate_entry *p;
>>
>> list_for_each_entry(p, &gating_cfg->entries, list) {
>> if (p->interval == e->interval) {
>> @@ -37,10 +38,12 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> goto err;
>> }
>>
>> - if (e->interval < p->interval)
>> + if (e->interval < p->interval) {
>> + pos = &p->list;
>> break;
>> + }
>> }
>> - list_add(&e->list, p->list.prev);
>> + list_add(&e->list, pos->prev);
>> }
>>
>> gating_cfg->num_entries++;
>> --
>> 2.25.1
>
> I think we can give this a turn that is actually beneficial for the driver.
> I've prepared and tested 3 patches on this function, see below.
> Concrete improvements:
> - that thing with list_for_each_entry() and list_for_each()
> - no more special-casing of an empty list
> - simplifying the error path
> - that thing with list_add_tail()
>
> What do you think about the changes below?
Thanks for all the good cooperation and help. The changes look great.
I'll include them in v2 unless you want to do that separately, then I'll
just remove them from the patch series.
>
> From 5b952b75e239cbe96729cf78c17e8d9725c9617c Mon Sep 17 00:00:00 2001
> From: Vladimir Oltean <[email protected]>
> Date: Sun, 10 Apr 2022 22:21:41 +0300
> Subject: [PATCH 1/3] net: dsa: sja1105: remove use of iterator after
> list_for_each_entry() loop
>
> Jakob Koschel explains in the link below that there is a desire to
> syntactically change list_for_each_entry() and list_for_each() such that
> it becomes impossible to use the iterator variable outside the scope of
> the loop.
>
> Although sja1105_insert_gate_entry() makes legitimate use of the
> iterator pointer when it breaks out, the pattern it uses may become
> illegal, so it needs to change.
>
> It is deemed acceptable to use a copy of the loop iterator, and
> sja1105_insert_gate_entry() only needs to know the list_head element
> before which the list insertion should be made. So let's profit from the
> occasion and refactor the list iteration to a dedicated function.
>
> An additional benefit is given by the fact that with the helper function
> in place, we no longer need to special-case the empty list, since it is
> equivalent to not having found any gating entry larger than the
> specified interval in the list. We just need to insert at the tail of
> that list (list_add vs list_add_tail on an empty list does the same
> thing).
>
> Link: https://patchwork.kernel.org/project/netdevbpf/patch/[email protected]/#24810127
> Signed-off-by: Vladimir Oltean <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 46 ++++++++++++++++++----------
> 1 file changed, 29 insertions(+), 17 deletions(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index b7e95d60a6e4..369be2ac3587 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -7,6 +7,27 @@
>
> #define SJA1105_SIZE_VL_STATUS 8
>
> +static struct list_head *
> +sja1105_first_entry_longer_than(struct list_head *entries,
> + s64 interval,
> + struct netlink_ext_ack *extack)
> +{
> + struct sja1105_gate_entry *p;
> +
> + list_for_each_entry(p, entries, list) {
> + if (p->interval == interval) {
> + NL_SET_ERR_MSG_MOD(extack, "Gate conflict");
> + return ERR_PTR(-EBUSY);
> + }
> +
> + if (interval < p->interval)
> + return &p->list;
> + }
> +
> + /* Empty list, or specified interval is largest within the list */
> + return entries;
> +}
> +
> /* Insert into the global gate list, sorted by gate action time. */
> static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> struct sja1105_rule *rule,
> @@ -14,6 +35,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> struct netlink_ext_ack *extack)
> {
> struct sja1105_gate_entry *e;
> + struct list_head *pos;
> int rc;
>
> e = kzalloc(sizeof(*e), GFP_KERNEL);
> @@ -24,25 +46,15 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> e->gate_state = gate_state;
> e->interval = entry_time;
>
> - if (list_empty(&gating_cfg->entries)) {
> - list_add(&e->list, &gating_cfg->entries);
> - } else {
> - struct sja1105_gate_entry *p;
> -
> - list_for_each_entry(p, &gating_cfg->entries, list) {
> - if (p->interval == e->interval) {
> - NL_SET_ERR_MSG_MOD(extack,
> - "Gate conflict");
> - rc = -EBUSY;
> - goto err;
> - }
> -
> - if (e->interval < p->interval)
> - break;
> - }
> - list_add(&e->list, p->list.prev);
> + pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
> + e->interval, extack);
> + if (IS_ERR(pos)) {
> + rc = PTR_ERR(pos);
> + goto err;
> }
>
> + list_add(&e->list, pos->prev);
> +
> gating_cfg->num_entries++;
>
> return 0;
> --
> 2.25.1
>
> From b6385f62d730b69007ea218e885461542ca4c44c Mon Sep 17 00:00:00 2001
> From: Vladimir Oltean <[email protected]>
> Date: Sun, 10 Apr 2022 22:34:35 +0300
> Subject: [PATCH 2/3] net: dsa: sja1105: reorder
> sja1105_first_entry_longer_than with memory allocation
>
> sja1105_first_entry_longer_than() does not make use of the full struct
> sja1105_gate_entry *e, just of e->interval which is set from the passed
> entry_time.
>
> This means that if there is a gate conflict, we have allocated e for
> nothing, just to free it later. Reorder the memory allocation and the
> function call, to avoid that and simplify the error unwind path.
>
> Signed-off-by: Vladimir Oltean <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 17 +++++------------
> 1 file changed, 5 insertions(+), 12 deletions(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index 369be2ac3587..e5ea8eb9ec4e 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -36,7 +36,11 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> {
> struct sja1105_gate_entry *e;
> struct list_head *pos;
> - int rc;
> +
> + pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
> + entry_time, extack);
> + if (IS_ERR(pos))
> + return PTR_ERR(pos);
>
> e = kzalloc(sizeof(*e), GFP_KERNEL);
> if (!e)
> @@ -45,22 +49,11 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> e->rule = rule;
> e->gate_state = gate_state;
> e->interval = entry_time;
> -
> - pos = sja1105_first_entry_longer_than(&gating_cfg->entries,
> - e->interval, extack);
> - if (IS_ERR(pos)) {
> - rc = PTR_ERR(pos);
> - goto err;
> - }
> -
> list_add(&e->list, pos->prev);
>
> gating_cfg->num_entries++;
>
> return 0;
> -err:
> - kfree(e);
> - return rc;
> }
>
> /* The gate entries contain absolute times in their e->interval field. Convert
> --
> 2.25.1
>
> From 8aa272b8a3f53aba7b80f181b275e040b9aaed8d Mon Sep 17 00:00:00 2001
> From: Vladimir Oltean <[email protected]>
> Date: Sun, 10 Apr 2022 22:37:14 +0300
> Subject: [PATCH 3/3] net: dsa: sja1105: use list_add_tail(pos) instead of
> list_add(pos->prev)
>
> When passed a non-head list element, list_add_tail() actually adds the
> new element to its left, which is what we want. Despite the slightly
> confusing name, use the dedicated function which does the same thing as
> the open-coded list_add(pos->prev).
>
> Suggested-by: Jakub Kicinski <[email protected]>
> Signed-off-by: Vladimir Oltean <[email protected]>
> ---
> drivers/net/dsa/sja1105/sja1105_vl.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
> index e5ea8eb9ec4e..7fe9b18f1cbd 100644
> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
> @@ -49,7 +49,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
> e->rule = rule;
> e->gate_state = gate_state;
> e->interval = entry_time;
> - list_add(&e->list, pos->prev);
> + list_add_tail(&e->list, pos);
>
> gating_cfg->num_entries++;
>
> --
> 2.25.1
>
Hey Vladimir,
> On 9. Apr 2022, at 01:54, Jakob Koschel <[email protected]> wrote:
>
> Hello Vladimir,
>
>> On 8. Apr 2022, at 13:41, Vladimir Oltean <[email protected]> wrote:
>>
>> Hello Jakob,
>>
>> On Thu, Apr 07, 2022 at 12:28:47PM +0200, Jakob Koschel wrote:
>>> In preparation to limit the scope of a list iterator to the list
>>> traversal loop, use a dedicated pointer to point to the found element [1].
>>>
>>> Before, the code implicitly used the head when no element was found
>>> when using &pos->list. Since the new variable is only set if an
>>> element was found, the list_add() is performed within the loop
>>> and only done after the loop if it is done on the list head directly.
>>>
>>> Link: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/ [1]
>>> Signed-off-by: Jakob Koschel <[email protected]>
>>> ---
>>> drivers/net/dsa/sja1105/sja1105_vl.c | 14 +++++++++-----
>>> 1 file changed, 9 insertions(+), 5 deletions(-)
>>>
>>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>>> index b7e95d60a6e4..cfcae4d19eef 100644
>>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>>> @@ -27,20 +27,24 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>>> if (list_empty(&gating_cfg->entries)) {
>>> list_add(&e->list, &gating_cfg->entries);
>>> } else {
>>> - struct sja1105_gate_entry *p;
>>> + struct sja1105_gate_entry *p = NULL, *iter;
>>>
>>> - list_for_each_entry(p, &gating_cfg->entries, list) {
>>> - if (p->interval == e->interval) {
>>> + list_for_each_entry(iter, &gating_cfg->entries, list) {
>>> + if (iter->interval == e->interval) {
>>> NL_SET_ERR_MSG_MOD(extack,
>>> "Gate conflict");
>>> rc = -EBUSY;
>>> goto err;
>>> }
>>>
>>> - if (e->interval < p->interval)
>>> + if (e->interval < iter->interval) {
>>> + p = iter;
>>> + list_add(&e->list, iter->list.prev);
>>> break;
>>> + }
>>> }
>>> - list_add(&e->list, p->list.prev);
>>> + if (!p)
>>> + list_add(&e->list, gating_cfg->entries.prev);
>>> }
>>>
>>> gating_cfg->num_entries++;
>>> --
>>> 2.25.1
>>>
>>
>> I apologize in advance if I've misinterpreted the end goal of your patch.
>> I do have a vague suspicion I understand what you're trying to achieve,
>> and in that case, would you mind using this patch instead of yours?
>
> I think you are very much spot on!
>
>> I think it still preserves the intention of the code in a clean manner.
>>
>> -----------------------------[ cut here ]-----------------------------
>> From 7aed740750d1bc3bff6e85fd33298f5905bb4e01 Mon Sep 17 00:00:00 2001
>> From: Vladimir Oltean <[email protected]>
>> Date: Fri, 8 Apr 2022 13:55:14 +0300
>> Subject: [PATCH] net: dsa: sja1105: avoid use of type-confused pointer in
>> sja1105_insert_gate_entry()
>>
>> It appears that list_for_each_entry() leaks a type-confused pointer when
>> the iteration loop ends with no early break, since "*p" will no longer
>> point to a "struct sja1105_gate_entry", but rather to some memory in
>> front of "gating_cfg->entries".
>>
>> This isn't actually a problem here, because if the element we insert has
>> the highest interval, therefore we never exit the loop early, "p->list"
>> (which is all that we use outside the loop) will in fact point to
>> "gating_cfg->entries" even though "p" itself is invalid.
>>
>> Nonetheless, there are preparations to increase the safety of
>> list_for_each_entry() by making it impossible to use the encapsulating
>> structure of the iterator element outside the loop. So something needs
>> to change here before those preparations go in, even though this
>> constitutes legitimate use.
>>
>> Make it clear that we are not dereferencing members of the encapsulating
>> "struct sja1105_gate_entry" outside the loop, by using the regular
>> list_for_each() iterator, and dereferencing the struct sja1105_gate_entry
>> only within the loop.
>>
>> With list_for_each(), the iterator element at the end of the loop does
>> have a sane value in all cases, and we can just use that as the "head"
>> argument of list_add().
>>
>> Signed-off-by: Vladimir Oltean <[email protected]>
>> ---
>> drivers/net/dsa/sja1105/sja1105_vl.c | 12 +++++++++---
>> 1 file changed, 9 insertions(+), 3 deletions(-)
>>
>> diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
>> index c0e45b393fde..fe93c80fe5ef 100644
>> --- a/drivers/net/dsa/sja1105/sja1105_vl.c
>> +++ b/drivers/net/dsa/sja1105/sja1105_vl.c
>> @@ -27,9 +27,15 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> if (list_empty(&gating_cfg->entries)) {
>> list_add(&e->list, &gating_cfg->entries);
>> } else {
>> - struct sja1105_gate_entry *p;
>> + struct list_head *pos;
>> +
>> + /* We cannot safely use list_for_each_entry()
>> + * because we dereference "pos" after the loop
>> + */
>> + list_for_each(pos, &gating_cfg->entries) {
>> + struct sja1105_gate_entry *p;
>>
>> - list_for_each_entry(p, &gating_cfg->entries, list) {
>> + p = list_entry(pos, struct sja1105_gate_entry, list);
>> if (p->interval == e->interval) {
>> NL_SET_ERR_MSG_MOD(extack,
>> "Gate conflict");
>> @@ -40,7 +46,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
>> if (e->interval < p->interval)
>> break;
>> }
>> - list_add(&e->list, p->list.prev);
>> + list_add(&e->list, pos->prev);
>
> I was actually considering doing it this way before but wasn't sure if this would be preferred.
> I've done something like this in [1] and it does turn out quite well.
>
> I'll integrate this in the v2 series.
I've just looked at this again in a bit more detail while integrating it into the patch series.
I realized that this just shifts the 'problem' to using the 'pos' iterator variable after the loop.
If the scope of the list iterator would be lowered to the list traversal loop it would also make sense
to also do it for list_for_each().
What do you think about doing it this way:
diff --git a/drivers/net/dsa/sja1105/sja1105_vl.c b/drivers/net/dsa/sja1105/sja1105_vl.c
index b7e95d60a6e4..f5b0502c1098 100644
--- a/drivers/net/dsa/sja1105/sja1105_vl.c
+++ b/drivers/net/dsa/sja1105/sja1105_vl.c
@@ -28,6 +28,7 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
list_add(&e->list, &gating_cfg->entries);
} else {
struct sja1105_gate_entry *p;
+ struct list_head *pos = NULL;
list_for_each_entry(p, &gating_cfg->entries, list) {
if (p->interval == e->interval) {
@@ -37,10 +38,14 @@ static int sja1105_insert_gate_entry(struct sja1105_gating_config *gating_cfg,
goto err;
}
- if (e->interval < p->interval)
+ if (e->interval < p->interval) {
+ pos = &p->list;
break;
+ }
}
- list_add(&e->list, p->list.prev);
+ if (!pos)
+ pos = &gating_cfg->entries;
+ list_add(&e->list, pos->prev);
}
gating_cfg->num_entries++;
--
>
> Thanks for the suggestion.
>
>> }
>>
>> gating_cfg->num_entries++;
>> -----------------------------[ cut here ]-----------------------------
>
> [1] https://lore.kernel.org/linux-kernel/[email protected]/
>
> Jakob
Thanks,
Jakob